【文章內(nèi)容簡介】 遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由一定數(shù)量的經(jīng)過了基因編碼的個體組成。每個個體實際上是染色體帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)為某種基因組合（即基因型），它決定了個體形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射，即編碼工作。由于仿照基因編碼的工作很復雜，我們往往將其簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度大小選擇個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼，可以作為問題近似最優(yōu)解。遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。搜索算法的共同特征為：　　①首先組成一組候選解；　?、谝罁?jù)某些適應性條件測算這些候選解的適應度；　　③根據(jù)適應度保留某些候選解，放棄其他候選解；　　④對保留的候選解進行某些操作，生成新的候選解?！　∵z傳算法還具有以下幾方面的特點：　?。?）遺傳算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)?！　。?）許多傳統(tǒng)搜索算法都是單點搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身易于實現(xiàn)并行化?！　。?）遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數(shù)值來評估個體，在此基礎上進行遺傳操作。適應度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設定。這一特點使得遺傳算法的應用范圍大大擴展。　?。?）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導他的搜索方向?！　。?）具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，硬度大的個體具有較高的生存概率并獲得更適應環(huán)境的基因結構。由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計算是不依賴于梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數(shù)和相應的適應度函數(shù)，所以遺傳算法提供了一種求解復雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于許多科學，下面對遺傳算法的一些主要應用領域做以介紹：（1）在組合優(yōu)化中的應用組合優(yōu)化問題是遺傳算法最基本也是最重要的應用領域。所謂組合優(yōu)化問題是指在離散的、有限的數(shù)學結構上，尋找一個滿足給定約束條件并使其目標函數(shù)達到最大或最小的解。在日常生活中，特別是在工程設計中，有許多這樣的問題。最典型的是巡回旅行商問題和背包問題?！。?）在生產(chǎn)調(diào)度問題中的應用　在很多情況下，生產(chǎn)調(diào)度問題建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結果與實際相差甚遠。目前，在現(xiàn)實生產(chǎn)中，主要是靠一些經(jīng)驗來進行調(diào)度?，F(xiàn)在遺傳算法已成為解決復雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、在流水線生產(chǎn)調(diào)度、任務分配等方面遺傳算法都得到了有效的應用。（3）在自動控制中的應用在自動控制領域中，有很多與優(yōu)化相關的問題需要求解。例如，遺傳算法進行航空控制系統(tǒng)的優(yōu)化、設計空間交會控制器等都顯示出在這些領域中應用的可能性。（4）在圖象處理中的應用　　圖象處理是計算機視覺中的一個重要研究領域，如目前已在模式識別（包括漢字識別）、圖像恢復、圖像邊緣特征提取等方面得到了應用。 （5）在機器學習領域中的應用 基于遺傳算法的機器學習是當前遺傳算法應用研究的熱點，特別是分類器系統(tǒng)，在很多領域中得到了應用。Holland的分類器系統(tǒng)是基于遺傳算法及其學習的一個典型例子，遺傳算法部分的主要任務是產(chǎn)生新的分類器，如獲取規(guī)則集合以預測公司的利潤。Brooker等對分類器系統(tǒng)和遺傳算法進行了更詳細的評述。 （6）在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術，它能夠從大型數(shù)據(jù)庫中提取隱含、未知、有潛力、有應用價值的知識和規(guī)則。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫可看作是搜索空間，挖掘算法看作是搜索策略。因此，應用遺傳算法在數(shù)據(jù)庫中搜索，對隨機產(chǎn)生的一組規(guī)則進化，直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。Sunil已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘工具，利用該工具對兩個飛機失事數(shù)據(jù)庫進行了數(shù)據(jù)挖掘?qū)嶒?，結果表明遺傳算法是進行數(shù)據(jù)挖掘的有效方法之一。 解決實際問題時遺傳算法流程圖（1）編碼：是因為遺傳算法不能直接處理空間的參數(shù)，必須把它們轉換成遺傳空間的由基因按一定結構組成的染色體或個體。（2）初始種群的選?。撼跏既后w中的個體是隨機產(chǎn)生的，但遵循兩種策略：①根據(jù)問題固有知識，設法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設定初始群體。②先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)達到了預先確定的規(guī)模。（3）收斂準則：由適應度函數(shù)決定，適應度函數(shù)是表示某一個體對環(huán)境的適應能力，也表示該個體繁殖后代的能力。它也被稱作評價函數(shù)，是用來判斷群體智能個的個體的優(yōu)略程度的指標，它是根據(jù)所求問題的目標函數(shù)來進行評估的。（4）遺傳過程：遺傳操作的三種基本遺傳算子：選擇、交叉、差異。個體向最優(yōu)解遷移的規(guī)則是隨機的。但遺傳操作進行的是高效有向的搜索而不是一般隨機搜索方法所進行的無向搜索。遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務就是對群體的個體按照它們對環(huán)境適應度(適應度評估)施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程。從優(yōu)化搜索的角度而言，遺傳操作可使問題的解，一代又一代地優(yōu)化，并逼進最優(yōu)解。 遺傳操作包括以下三個基本遺傳算子(genetic operator):選擇(selection)；交叉(crossover)；變異(mutation)。這三個遺傳算子有如下特點: 　　個體遺傳算子的操作都是在隨機擾動情況下進行的。因此，群體中個體向最優(yōu)解遷移的規(guī)則是隨機的。需要強調(diào)的是，這種隨機化操作和傳統(tǒng)的隨機搜索方法是有區(qū)別的。遺傳操作進行的高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。 遺傳過程(1)選擇　　從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫選擇。選擇算子有時又稱為再生算子(reproduction operator)。選擇的目的是把優(yōu)化的個體(或解)直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的，目前常用的選擇算子有以下幾種:適應度比例方法、隨機遍歷抽樣法、局部選擇法、局部選擇法。 其中輪盤賭選擇法 （roulette wheel selection）是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應度值成比例。設群體大小為n，其中個體i的適應度為，則i 被選擇的概率,為遺傳算法 　　顯然。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率后，為了選擇交配個體，需要進行多輪選擇。每一輪產(chǎn)生一個[0，1]之間均勻隨機數(shù)，將該隨機數(shù)作為選擇指針來確定被選個體。個體被選后，可隨機地組成交配對，以供后面的交叉操作。(2)交叉　　在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。 　　交叉算子根據(jù)交叉率將種群中的兩個個體隨機地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。根據(jù)編碼表示方法的不同，可以有以下的算法： 　　a)實值重組（real valued rebination） 　　1)離散重組（discrete rebination）； 　　2)中間重組（intermediate rebination）； 　　3)線性重組（linear rebination）； 　　4)擴展線性重組（extended linear rebination）。 　　b)二進制交叉（binary valued crossover） 　　1)單點交叉（singlepoint crossover）； 　　2)多點交叉（multiplepoint crossover）； 　　3)均勻交叉（uniform crossover）； 　　4)洗牌交叉（shuffle crossover）； 　　5)縮小代理交叉（crossover with reduced surrogate）。 　　最常用的交叉算子為單點交叉(onepoint crossover)。具體操作是:在個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新個體。下面給出了單點交叉的一個例子： 個體A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新個體個體B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新個體(3)變異　　變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。依據(jù)個體編碼表示方法的不同，可以有以下的算法： 　　a)實值變異； 　　b)二進制變異。 　　一般來說，變異算子操作的基本步驟如下: 　　a)對群中所有個體以事先設定的編譯概率判斷是否進行變異； 　　b)對進行變異的個體隨機選擇變異位進行變異。 　　遺傳算法導引入變異的目的有兩個:一是使遺傳算法具有局部的隨機搜索能力。當遺傳算法通過交叉算子已接近最優(yōu)解鄰域時，利用變異算子的這種局部隨機搜索能力可以加速向最優(yōu)解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優(yōu)解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時收斂概率應取較大值。 　　遺傳算法中，交叉算子因其全局搜索能力而作