遺傳算法是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)之一。

達(dá)爾文的自然選擇學(xué)說是一種被人們廣泛接受的生物進(jìn)化學(xué)說。這種學(xué)說認(rèn)為，生物要生存下去，就必須進(jìn)行生存斗爭。生存斗爭包括種內(nèi)斗爭、種間斗爭以及生物跟無機(jī)環(huán)境之間的斗爭三個(gè)方面。在生存斗爭中，具有有利變異的個(gè)體容易存活下來，并且有更多的機(jī)會(huì)將有利變異傳給后代；具有不利變異的個(gè)體就容易被淘汰，產(chǎn)生后代的機(jī)會(huì)也少的多。因此，凡是在生存斗爭中獲勝的個(gè)體都是對(duì)環(huán)境適應(yīng)性比較強(qiáng)的。達(dá)爾文把這種在生存斗爭中適者生存，不適者淘汰的過程叫做自然選擇。它表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。自然界中的多種生物之所以能夠適應(yīng)環(huán)境而得以生存進(jìn)化，是和遺傳和變異生命現(xiàn)象分不開的。正是生物的這種遺傳特性，使生物界的物種能夠保持相對(duì)的穩(wěn)定；而生物的變異特性，使生物個(gè)體產(chǎn)生新的性狀，以致于形成新的物種，推動(dòng)了生物的進(jìn)化和發(fā)展。

遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有“生存＋檢測(cè)”的迭代過程的搜索算法。遺傳算法以一種群體中的所有個(gè)體為對(duì)象，并利用隨機(jī)化技術(shù)指導(dǎo)對(duì)一個(gè)被編碼的參數(shù)空間進(jìn)行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)設(shè)定五個(gè)要素組成了遺傳算法的核心內(nèi)容。 作為一種新的全局優(yōu)化搜索算法，遺傳算法以其簡單通用、魯棒性強(qiáng)、適于并行處理以及高效、實(shí)用等顯著特點(diǎn)，在各個(gè)領(lǐng)域得到了廣泛應(yīng)用，取得了良好效果，并逐漸成為重要的智能算法之一。

長度為L的n個(gè)二進(jìn)制串bi(i＝1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。根據(jù)進(jìn)化術(shù)語，對(duì)群體執(zhí)行的操作有三種：

1．選擇(Selection)

這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代。故有時(shí)也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱為非均勻再生(differential reproduction)。

2．交叉(Crossover)

這是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。

3．變異(Mutation)

這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串bi中，如果某位基因?yàn)?，產(chǎn)生變異時(shí)就是把它變成0；反亦反之。

遺傳算法的原理可以簡要給出如下：

choose an intial population

determine the fitness of each individual

perform selection

repeat

perform crossover

perform mutation

determine the fitness of each individual

perform selection

until some stopping criterion applies

這里所指的某種結(jié)束準(zhǔn)則一般是指個(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。

1．初始化

　　選擇一個(gè)群體，即選擇一個(gè)串或個(gè)體的集合bi，i=1，2，...n。這個(gè)初始的群體也就是問題假設(shè)解的集合。一般取n＝30-160。通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合bi,i＝1，2，...n。問題的最優(yōu)解將通過這些初始假設(shè)解進(jìn)化而求出。

2．選擇

　　根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。

給出目標(biāo)函數(shù)f，則f(bi)稱為個(gè)體bi的適應(yīng)度。以

(3-86)

為選中bi為下一代個(gè)體的次數(shù)。

顯然．從式(3—86)可知：

(1)適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。

(2)適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。

這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。對(duì)于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。

3．交叉

　　對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率P。在選中的位置實(shí)行交換。這個(gè)過程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。

例如有個(gè)體

　　S1=100101

　　S2=010111

選擇它們的左邊3位進(jìn)行交叉操作，則有

　　S1=010101

　　S2=100111

一般而言，交叉幌宰P。取值為0.25—0.75。

4．變異

　　根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。

　　例如有個(gè)體S＝101011。

　　對(duì)其的第1，4位置的基因進(jìn)行變異，則有

　　S'=001111

　　　單靠變異不能在求解中得到好處。但是，它能保證算法過程不會(huì)產(chǎn)生無法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。

5．全局最優(yōu)收斂(Convergence to the global optimum)

　　當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第2步即選擇操作處繼續(xù)循環(huán)執(zhí)行。

　　　　　　　　　　　　圖3—7中表示了遺傳算法的執(zhí)行過程

1．遺傳算法從問題解的中集開始嫂索，而不是從單個(gè)解開始。

這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，復(fù)蓋面大，利于全局擇優(yōu)。

2．遺傳算法求解時(shí)使用特定問題的信息極少，容易形成通用算法程序。

由于遺傳算法使用適應(yīng)值這一信息進(jìn)行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。遺傳算法只需適應(yīng)值和串編碼等通用信息，故幾乎可處理任何問題。

3．遺傳算法有極強(qiáng)的容錯(cuò)能力

遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息；通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串；這是一個(gè)強(qiáng)烈的濾波過程；并且是一個(gè)并行濾波機(jī)制。故而，遺傳算法有很高的容錯(cuò)能力。

4．遺傳算法中的選擇、交叉和變異都是隨機(jī)操作，而不是確定的精確規(guī)則。

這說明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的復(fù)蓋。

5．遺傳算法具有隱含的并行性

遺傳算法在神經(jīng)網(wǎng)絡(luò)中的應(yīng)用主要反映在3個(gè)方面：網(wǎng)絡(luò)的學(xué)習(xí)，網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計(jì)，網(wǎng)絡(luò)的分析。

1.遺傳算法在網(wǎng)絡(luò)學(xué)習(xí)中的應(yīng)用

在神經(jīng)網(wǎng)絡(luò)中，遺傳算法可用于網(wǎng)絡(luò)的學(xué)習(xí)。這時(shí)，它在兩個(gè)方面起作用

(1)學(xué)習(xí)規(guī)則的優(yōu)化

用遺傳算法對(duì)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)規(guī)則實(shí)現(xiàn)自動(dòng)優(yōu)化，從而提高學(xué)習(xí)速率。

(2)網(wǎng)絡(luò)權(quán)系數(shù)的優(yōu)化

用遺傳算法的全局優(yōu)化及隱含并行性的特點(diǎn)提高權(quán)系數(shù)優(yōu)化速度。

2.遺傳算法在網(wǎng)絡(luò)設(shè)計(jì)中的應(yīng)用

用遺傳算法設(shè)計(jì)一個(gè)優(yōu)秀的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，首先是要解決網(wǎng)絡(luò)結(jié)構(gòu)的編碼問題；然后才能以選擇、交叉、變異操作得出最優(yōu)結(jié)構(gòu)。編碼方法主要有下列3種：

(1)直接編碼法

這是把神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)直接用二進(jìn)制串表示，在遺傳算法中，“染色體”實(shí)質(zhì)上和神經(jīng)網(wǎng)絡(luò)是一種映射關(guān)系。通過對(duì)“染色體”的優(yōu)化就實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)的優(yōu)化。

(2)參數(shù)化編碼法

參數(shù)化編碼采用的編碼較為抽象，編碼包括網(wǎng)絡(luò)層數(shù)、每層神經(jīng)元數(shù)、各層互連方式等信息。一般對(duì)進(jìn)化后的優(yōu)化“染色體”進(jìn)行分析，然后產(chǎn)生網(wǎng)絡(luò)的結(jié)構(gòu)。

(3)繁衍生長法

這種方法不是在“染色體”中直接編碼神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，而是把一些簡單的生長語法規(guī)則編碼入“染色體”中；然后，由遺傳算法對(duì)這些生長語法規(guī)則不斷進(jìn)行改變，最后生成適合所解的問題的神經(jīng)網(wǎng)絡(luò)。這種方法與自然界生物地生長進(jìn)化相一致。

3.遺傳算法在網(wǎng)絡(luò)分析中的應(yīng)用

遺傳算法可用于分析神經(jīng)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)由于有分布存儲(chǔ)等特點(diǎn)，一般難以從其拓?fù)浣Y(jié)構(gòu)直接理解其功能。遺傳算法可對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行功能分析，性質(zhì)分析，狀態(tài)分析。

遺傳算法雖然可以在多種領(lǐng)域都有實(shí)際應(yīng)用，并且也展示了它潛力和寬廣前景；但是，遺傳算法還有大量的問題需要研究，目前也還有各種不足。首先，在變量多，取值范圍大或無給定范圍時(shí)，收斂速度下降；其次，可找到最優(yōu)解附近，但無法精確確定最擾解位置；最后，遺傳算法的參數(shù)選擇尚未有定量方法。對(duì)遺傳算法，還需要進(jìn)一步研究其數(shù)學(xué)基礎(chǔ)理論；還需要在理論上證明它與其它優(yōu)化技術(shù)的優(yōu)劣及原因；還需研究硬件化的遺傳算法；以及遺傳算法的通用編程和形式等。

案例一:遺傳算法在裝箱環(huán)節(jié)中的應(yīng)用^[1]

　　一、一維裝箱問題的描述

　　一維裝箱問題^[2]引可描述如下：

　　要將11個(gè)物品裝入許多箱子(最多n個(gè)箱子)。每個(gè)物品有重量(W_j > 0)。每個(gè)箱子有重量限制(c_i > O)。問題是尋找最好的將物品分配到箱子的方案，使得在每個(gè)箱子中物品的總重量不超過其限制，并且使用的箱子數(shù)量最少。

　　該問題可表示^[2]為：

　　重量及限制表

其中重量W_j和重量限制c_i是正實(shí)數(shù)裝箱問題的數(shù)學(xué)表示如下：

　　。

　　iin N=left{1,2,ldots,nright}。

　　。

　　y_i=0或1　　x_ij=0或1　　。

　　其中y_i = l表示箱子i被放入物品，反之則表示箱子i空著；X_ij = 1表示物品j放入箱子i，反之表示物品j未放入箱子i。

　　基于基本遺傳算法的求解方案。

　　由于近似算法有時(shí)并不能產(chǎn)生出一個(gè)優(yōu)秀的裝箱方案，在這里采用遺傳算法進(jìn)行優(yōu)化。

　　(一)染色體表示

　　對(duì)于一維裝箱問題，由于其裝箱費(fèi)用依賴于箱子中物體的群體，故在此問題中染色體的表示需要包含兩個(gè)部分，其一應(yīng)該提供哪個(gè)物品屬于哪個(gè)箱子(群體)的信息，另外對(duì)使用的箱子進(jìn)行編碼。故采用基于群體的表示方法^[2]，其中一個(gè)基因表示一個(gè)箱子。

　　設(shè)有六個(gè)物品，從1到6對(duì)其進(jìn)行編碼，染色體物品部分可以寫作1 4 2 3 2 5。表示第一個(gè)物品放入箱子1，第二個(gè)物品放入箱子4，第三個(gè)和第五個(gè)物品放入箱子2，第四個(gè)物品放入箱子3，第六個(gè)物品放入箱子5。染色體的群體部分僅表示箱子。下面我們采用字母而不是整數(shù)來表示箱子(比如，上述染色體可表示為ADBCBE)。通過查詢物品部分，可知群體的名字代表的含義，即A={1)，B=(3,5)，c={4)，D=(2),E=(6)。

　　包含兩部分的染色體的集成用圖表示如下：

　　(二)初始化種群

　　由于BFD算法對(duì)于很多數(shù)據(jù)均有較好的效果，所以本程序中把BFD算法作為一種方案放入初始的群體，這樣就可能不失去一些優(yōu)秀的解。

　　(三)選擇算子

　　選擇操作是建立在群體中個(gè)體的適應(yīng)度的評(píng)估的基礎(chǔ)上，在本算法中采用按正比與適應(yīng)度的輪盤賭的方式進(jìn)行隨機(jī)選擇，為了提高效率，選擇輪盤時(shí)采用折半查找的方法，這樣就能有效地減少比較次數(shù)，確保該過程的時(shí)間復(fù)雜度為0(log n)(n為種群大小)。

　　(四)雜交算子

　　因?yàn)槿旧w的表示包含兩個(gè)部分：箱子和物品的群體。因此需要處理可變長度的染色體，故其雜交過程^[2]如下：

　　第一步：隨機(jī)選擇兩個(gè)雜交位置，對(duì)每個(gè)父代選定雜交部分

　　第二步：將第一個(gè)父代雜交部分的內(nèi)容插入到第二個(gè)父代第一個(gè)雜交位置之前。由于雜交對(duì)染色體的部分群體進(jìn)行操作，這就意味著從第一個(gè)父代插入一些群體(箱子)到第二個(gè)父代中。

　　第三步：從產(chǎn)生的后代中原有的箱子中去掉所有重復(fù)出現(xiàn)的物品，使得這些物品原先的從屬關(guān)系讓位于“新”插入的箱子。因此產(chǎn)生的后代中的某些群體發(fā)生了改變。他們不再包含與先前相同的物品，原因是消除了一些物品。

　　第四步：改變兩個(gè)父代的角色并重新應(yīng)用第二步到第三步生成第2個(gè)子代。

　　雜交過程可用圖表示：

　　(五)變異算子

　　裝箱問題的變異算子必須針對(duì)箱子進(jìn)行操作，一般有兩種策略：啟用一個(gè)新箱子或消除一個(gè)已經(jīng)使用的箱子。

　　(六)適應(yīng)度函數(shù)

　　裝箱問題的目標(biāo)是：最小化使用的箱子數(shù)量同時(shí)盡量裝滿所使用的箱子。根據(jù)此要求，本文采用玄光南等所編教材《遺傳算法與工程優(yōu)化》中提到的適應(yīng)度函數(shù)^[2]。具體定義如下：

　　。

　　其中，N是解中使用的箱子數(shù)量，F_i是第i個(gè)箱子中所裝有物品的重量之和，C是箱子的重量限制，k是常數(shù)(k>1)。常數(shù)k表示了對(duì)裝得滿的箱子的重視程度。k越大，裝得滿的箱子比一般填充的箱子受到的重視就越大。一般，k取值為2得到的結(jié)果較好。

　　二、求解步驟

　　(一)確定問題的解空間和個(gè)體的表現(xiàn)型

　　我們把染色體表示為含有物品和箱子兩項(xiàng)信息的數(shù)據(jù)串。首先對(duì)待裝物品進(jìn)行編號(hào)1-n，對(duì)箱子進(jìn)行編號(hào)1-k，按照物品編號(hào)順序?qū)懗銎渌谙渥拥木幪?hào)序列即定義為染色體。具體含義在上節(jié)中介紹的比較詳細(xì)，這里將不再贅述。

　　(二)建立優(yōu)化模型，確定出目標(biāo)函數(shù)

　　該問題表面上是要求得所用箱子的最小數(shù)目，其實(shí)是最大化利用資源的問題，故目標(biāo)函數(shù)的類型應(yīng)該是求最大值的。由此，我們采用的適應(yīng)度函數(shù)為。

　　其中，N是解中使用的箱子數(shù)量，F_i是第i個(gè)箱子中所裝有物品的重量之和，C是箱子的重量限制，k取值為2。

　　(三)確定遺傳算子

　　見上節(jié)中對(duì)選擇、交叉、變異三種遺傳算子的設(shè)定,這里不再贅述。

　　(四)確定運(yùn)行參數(shù)

　　本文中,我們?cè)O(shè)定交叉概率P_c = 0.7,變異概率P_n = 0.1,代數(shù)gen=100,種群大小n=100。

　　三、計(jì)算舉例與結(jié)果分析。

　　為了闡明利用該算法的計(jì)算過程與結(jié)果,程序選定下列一組特殊數(shù)據(jù)：假設(shè)現(xiàn)有一個(gè)由l5個(gè)物體組成的物體隊(duì)列和足夠多的單位箱子,其中物體的重量如下：1-9號(hào)物品的重量：0.310-l5號(hào)物品的重量：0.2假設(shè)箱子容量為1,按照BFD算法,我們可以得到下列裝箱方案：。

　　(O.3,O.3,O.3),(0.3,0.3,0.3),(0.3,O.3,O.3),(O.2,0.2,0.2,0.2,0.2),(0.2)共用了5個(gè)箱子。

　　我們把上述利用BFD算法產(chǎn)生的裝箱方案作為利用遺傳算法進(jìn)行求解的初始群體,同時(shí),我們?nèi)〗徊娓怕?em>P_c = 0.7,變異概率P_n = 0.1,代數(shù)gen=100,種群大小n--100。得出結(jié)果為：(0.3,0.3,0.2,0.2),(0.3,0.3,0.2,0.2),(0.3,0.3,0.2,0.2),(0.3,0.3,0.3)共四個(gè)箱子,顯然結(jié)果比較理想。