遺傳算法綜述

金玲，劉曉麗，李鵬飛，王妍

華北理工大學冀唐學院

遺傳算法綜述

金玲，劉曉麗，李鵬飛，王妍

華北理工大學冀唐學院

本文對遺傳算法的基本概念、運算過程和特點做了概述，并在此基礎上分析了遺傳算法的現狀及前景。

遺傳算法；生物進化；最優(yōu)化

1.引言

遺傳算法仿效自然選擇下的生物進化,是一種仿生物進化過程的隨機化搜索方法,該算法通過有限的代價來解決搜索和優(yōu)化問題，由于其隨機性和非線性為其他科學技術無法或難以解決的問題提供了新的模型，這與傳統的搜索和優(yōu)化方法不同。

2.基本概念

遺傳算法是仿照自然界適者生存優(yōu)勝劣汰的進化規(guī)律得到的一種隨機化搜索方法。對于優(yōu)化問題要求一個求函數的最大值，可以用下面的數學規(guī)劃模型來進行描述:

其中(1)式作為目標函數，X是決策變量，(2)式、(3)式作為約束條件，R是基本空間U的子集?？尚薪釾是指滿足約束條件的解，可行解集合R是指滿足約束條件的解所組成的集合。

3.遺傳算法定義

遺傳算法是從一個種群開始的，對于數學規(guī)劃模型就是從可行解集合開始的。染色體作為遺傳物質的主要載體，種群中一定數目的個體都是經過基因編碼得到的，個體的基因型決定了這個個體的表現型，我們需要通過編碼實現從表現型到基因型的映射，由于生物體內基因編碼的工作是非常復雜的，所以我們要做一下必要的簡化例如二進制編碼。根據適者生存優(yōu)勝劣汰的遺傳規(guī)律，首先要確定初代種群，在每一代的種群迭代中再按照個體的適應度函數以及進行交叉、變異算子的運算選出較優(yōu)的個體，進入下一代的演化從而逐代產生出一個最優(yōu)的種群。在逐代演化的過程中，種群的適應能力越來越強，最后通過對末代種群中最優(yōu)個體進行解碼就可以得到數學規(guī)劃模型的近似最優(yōu)解。

4.遺傳算法的特點

遺傳算法可以很好的解決搜索問題，具有以下幾方面的特點：

(1)遺傳算法是從一個種群開始同時處理種群中的每個個體而不是單個個體，這是遺傳算法與傳統優(yōu)化算法的最大區(qū)別。遺傳算法是從數學規(guī)劃模型的解集開始進行嫂索，同時評估搜索空間中的多個解而不是單個解。傳統優(yōu)化算法是從單個解開始迭代求最優(yōu)解常常會陷入局部最優(yōu)解，而遺傳算法不僅減少了這種風險而且易于實現并行化。

(2)遺傳算法對個體的評估只要借助適應度函數就可以完成，幾乎不需要搜索空間的知識或其它輔助信息。而適應度函數的定義域可以任意設定且不會受到連續(xù)可微的限制，那么這很大程度上擴展了遺傳算法的應用范圍。

(3)遺傳算法的搜索方向是由概率的變遷規(guī)則來引導，而不是確定性規(guī)則。

(4)遺傳算法在逐代演化的過程中通過得到的信息自行組織搜索時，硬度較大的個體相應的生存概率也較高并且他獲得的基因結構也更適應環(huán)境。遺傳算法具有自適應性、自組織性和自學習性。

5.運算過程

為實現優(yōu)勝劣汰的進化過程就需要根據環(huán)境適應度對群體中的個體施加一定的操作，使模型的解在優(yōu)化搜索的角度逐代優(yōu)化并逼近最優(yōu)解，這就是模擬生物基因遺傳的遺傳操作，包括選擇、交叉、變異三個基本遺傳算子，具有如下特點:

(1)選擇算子。選擇是在個體適應度評估的基礎上從群體中選擇優(yōu)勝淘汰劣質個體的操作，其目的是將較優(yōu)的個體遺傳到下一代，較優(yōu)的個體可能是直接遺傳到下一代的也可能是通過配對交叉產生新個體再遺傳到下一代的。目前常用的選擇算子有隨機遍歷抽樣法、適應度比例方法、局部選擇法等。

(2)交叉算子。交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作，交叉算子期望將有益基因組合在一起，對種群中的兩個個體根據交叉率隨機交換某些基因產生新的基因組合。生物進化過程中遺傳基因重組發(fā)揮了主要作用，交叉算子在遺傳算法中的地位就等同于基因重組，交叉算子很大程度上提高了遺傳算法的搜索能力。

(3)變異算子。變異算子是指改變群體中個體串的某些基因座上的基因值。變異算子使遺傳算法具有局部的隨機搜索能力，這種局部隨機搜索能力在遺傳算法通過交叉算子已接近最優(yōu)解鄰域時可以加速向最優(yōu)解收斂。另外，變異算子還能防止遺傳算法出現未成熟收斂現象從而維持群體多樣性。

交叉算子可以提高遺傳算法的全局搜索能力，而變異算子對提高遺傳算法的局部搜索能力有幫助，交叉算子和變異算子之間既相互配合又相互競爭，也正因為如此遺傳算法具有均衡的搜索能力。那么，交叉算子和變異算子如何有效地配合使用就成為目前遺傳算法的一個重要研究內容。

(4)終止條件。當出現以下情況時算法終止：最優(yōu)群體和個體的適應度不再上升；最優(yōu)個體的適應度達到給定的閥值；迭代次數達到預設的代數，預設的代數一般為100-500代。

6.遺傳算法的現狀

進入90年代遺傳算法在理論研究和應用研究方面都取得了很大的進展。遺傳算法不但應用研究的領域擴大而且利用遺傳算法解決優(yōu)化和規(guī)則問題的能力也顯著提高，同時對于產業(yè)應用方面的研究也在摸索之中。

由于遺傳算法思想簡單、易于實現在許多應用領域例取得了豐碩的成果與進展，例如如函數優(yōu)化、組合優(yōu)化、圖像處理和模式識別、人工生命、生產調度問題、機器學習和自動控制等領域。對于遺傳算法，我們應該從收斂性，編碼方法，增強算子適應性，適應度函數進行更為深入的研究。

[1]遺傳算法理論及應用.周明，孫樹棟編著.國防工業(yè)出版社1999

[2]遺傳算法：理論、應用與軟件實現.王小平、曹立明著.西安交通大學出版社2002

[3]遺傳算法的基本理論與應用.李敏強等著.科學出版社2002