(1.10)-ch6-遺傳算法智能控制導(dǎo)論

第六章遺傳算法(GeneticAlgorithms,GA)1主要內(nèi)容6.5遺傳算法的特點

6.2遺傳算法的應(yīng)用領(lǐng)域6.1遺傳算法的基本原理6.3

遺傳算法的優(yōu)化設(shè)計6.4遺傳算法求函數(shù)極值2遺傳算法是以達(dá)爾文的自然選擇學(xué)說為基礎(chǔ)發(fā)展起來的。自然選擇學(xué)說包括以下三個方面：

（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個特征，物種才能穩(wěn)定存在。3

（2）變異：親代和子代之間以及子代的不同個體之間的差異，稱為變異。變異是隨機(jī)發(fā)生的，變異的選擇和積累是生命多樣性的根源。

（3）生存斗爭和適者生存：具有適應(yīng)性變異的個體被保留下來，不具有適應(yīng)性變異的個體被淘汰，通過一代代的生存環(huán)境的選擇作用，性狀逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。4遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制、交叉及變異對個體進(jìn)行篩選，使適應(yīng)度高的個體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個體適應(yīng)度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能到全局最優(yōu)解。5遺傳算法的基本操作為：

（1）復(fù)制（ReproductionOperator）復(fù)制是從一個舊種群中選擇生命力強(qiáng)的個體位串產(chǎn)生新種群的過程。具有高適應(yīng)度的位串更有可能在下一代中產(chǎn)生一個或多個子孫。常用的選擇方法――輪盤賭（RouletteWheelSelection）選擇法。假設(shè)種群數(shù)目n,某個個體i

其適應(yīng)度為fi,則其被選中的概率為：6假如有5條染色體，它們所對應(yīng)的適應(yīng)度分別為：5，7，10，13，15。累計總適應(yīng)度為:7所以各個個體被選中的概率分別為：8我們轉(zhuǎn)動輪盤，輪盤停下來的時候，指針會隨機(jī)地指向某一個個體所代表的區(qū)域，那么非常幸運地，這個個體被選中了。（很明顯，適應(yīng)度評分越高的個體被選中的概率越大。）9

（2）交叉（CrossoverOperator）復(fù)制操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體。而交叉模擬了生物進(jìn)化過程中的繁殖現(xiàn)象，通過兩個染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。交叉的過程為：在匹配池中任選兩個染色體，隨機(jī)選擇一點或多點交換點位置；交換雙親染色體交換點右邊的部分，即可得到兩個新的染色體數(shù)字串。10交叉體現(xiàn)了自然界中信息交換的思想。交叉有單點交叉、多點交叉、還有一致交叉、順序交叉和周期交叉。單點交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點有一處，例：11如果只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進(jìn)行搜索，使進(jìn)化過程在早期就陷入局部解而進(jìn)入終止過程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。12

（3）變異(MutationOperator)

變異運算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)地改變遺傳基因（表示染色體的符號串的某一位）的值。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個基因由1變?yōu)?，或由0變?yōu)?。13主要內(nèi)容6.5遺傳算法的特點

6.2遺傳算法的應(yīng)用領(lǐng)域6.1遺傳算法的基本原理6.3

遺傳算法的優(yōu)化設(shè)計6.4遺傳算法求函數(shù)極值146.2遺傳算法的應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評價的常用算例。尤其是對非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，采用其他優(yōu)化方法較難求解，而遺傳算法卻可以得到較好的結(jié)果。15（2）組合優(yōu)化隨著問題的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。16（3）生產(chǎn)調(diào)度問題在很多情況下，采用建立數(shù)學(xué)模型的方法難以對生產(chǎn)調(diào)度問題進(jìn)行精確求解。在現(xiàn)實生產(chǎn)中多采用一些經(jīng)驗進(jìn)行調(diào)度。遺傳算法是解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。17（4）自動控制在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已經(jīng)在其中得到了初步的應(yīng)用。例如，利用遺傳算法進(jìn)行控制器參數(shù)的優(yōu)化、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、基于遺傳算法的參數(shù)辨識、基于遺傳算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化和權(quán)值學(xué)習(xí)等。18（5）機(jī)器人例如，遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運動軌跡規(guī)劃、機(jī)器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。（6）圖像處理遺傳算法可用于圖像處理過程中的掃描、特征提取、圖像分割等的優(yōu)化計算。目前遺傳算法已經(jīng)在模式識別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。19主要內(nèi)容6.5遺傳算法的特點

6.2遺傳算法的應(yīng)用領(lǐng)域6.1遺傳算法的基本原理6.3

遺傳算法的優(yōu)化設(shè)計6.4遺傳算法求函數(shù)極值206.3.1遺傳算法的構(gòu)成要素（1）染色體編碼方法基本遺傳算法使用固定長度的二進(jìn)制符號來表示群體中的個體，其等位基因是由二值符號集{0,1}所組成。初始個體基因值可用均勻分布的隨機(jī)值生成，如就可表示一個個體，該個體的染色體長度是18。6.3遺傳算法的優(yōu)化設(shè)計21（2）個體適應(yīng)度評價：基本遺傳算法與個體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個個體遺傳到下一代群體中的概率多少。為正確計算這個概率，要求所有個體的適應(yīng)度必須為正數(shù)或零。因此，必須先確定由目標(biāo)函數(shù)值J到個體適應(yīng)度f之間的轉(zhuǎn)換規(guī)則。22（3）遺傳算子：基本遺傳算法使用下述三種遺傳算子：①選擇運算:使用比例選擇算子；②交叉運算:使用單點交叉算子；③變異運算:使用基本位變異算子或均勻變異算子。23（4）基本遺傳算法的運行參數(shù)。有下述4個運行參數(shù)需要提前設(shè)定：

M：群體大小，即群體中所含個體的數(shù)量，一般取為20~100；G：遺傳算法的終止進(jìn)化代數(shù)，一般取為100~500；Pc：交叉概率，一般取為0.4~0.99；Pm：變異概率，一般取為0.0001~0.1。24對于一個需要進(jìn)行優(yōu)化的實際問題，一般可按下述步驟構(gòu)造遺傳算法：第一步：確定決策變量及各種約束條件，即確定出個體的表現(xiàn)型X和問題的解空間；第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型及數(shù)學(xué)描述形式或量化方法；6.3.2遺傳算法的應(yīng)用步驟25第三步：確定表示可行解的染色體編碼方法，即確定出個體的基因型x及遺傳算法的搜索空間；第四步：確定解碼方法，即確定出由個體基因型x到個體表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)換方法；第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)值到個體適應(yīng)度的轉(zhuǎn)換規(guī)則；26第六步：設(shè)計遺傳算子，即確定選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。第七步：確定遺傳算法的有關(guān)運行參數(shù)，即M,G,Pc,Pm等參數(shù)。27以上操作過程可以用下圖來表示:

遺傳算法流程圖

種群1種群228主要內(nèi)容6.5遺傳算法的特點

6.2遺傳算法的應(yīng)用領(lǐng)域6.1遺傳算法的基本原理6.3

遺傳算法的優(yōu)化設(shè)計6.4遺傳算法求函數(shù)極值29 利用遺傳算法求Rosenbrock函數(shù)的極大值6.4遺傳算法求函數(shù)極值30二進(jìn)制編碼遺傳算法求函數(shù)極大值求解該問題遺傳算法的構(gòu)造過程：（1）確定決策變量和約束條件；（2）建立優(yōu)化模型；（3）確定編碼方法。31用長度為10位的二進(jìn)制編碼串來分別表示兩個決策變量x1,x2。10位二進(jìn)制編碼串可以表示從0到1023之間的1024個不同的數(shù)，故將x1,x2的定義域離散化為1023個均等的區(qū)域，包括兩個端點在內(nèi)共有1024個不同的離散點。從離散點-2.048到離散點2.048，分別對應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。32將x1,x2分別表示的兩個10位長的二進(jìn)制編碼串連接在一起，組成一個20位長的二進(jìn)制編碼串，它就構(gòu)成了這個函數(shù)優(yōu)化問題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對應(yīng)的關(guān)系。例如：表示一個個體的基因型，其中前10位表示x1，后10位表示x2。33（4）確定解碼方法：解碼時需要將20位長的二進(jìn)制編碼串切斷為兩個10位長的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。依據(jù)個體編碼方法和對定義域的離散化方法可知，將代碼y轉(zhuǎn)換為變量x的解碼公式為例如，對個體34它由兩個代碼所組成上述兩個代碼經(jīng)過解碼后，可得到兩個實際的值（5）確定個體評價方法：由于Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故可將個體的適應(yīng)度直接取為對應(yīng)的目標(biāo)函數(shù)值，即35選個體適應(yīng)度的倒數(shù)作為目標(biāo)函數(shù)（6）設(shè)計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。（7）確定遺傳算法的運行參數(shù)：群體大小M=80，終止進(jìn)化代數(shù)G=100，交叉概率Pc=0.60，變異概率Pm=0.10。上述七個步驟構(gòu)成了用于求函數(shù)極大值的優(yōu)化計算基本遺傳算法。36采用上述方法進(jìn)行仿真，經(jīng)過100步迭代，最佳樣本為即當(dāng)時，Rosenbrock函數(shù)具有極大值，極大值為3905.9。373839主要內(nèi)容6.5遺傳算法的特點

6.2遺傳算法的應(yīng)用領(lǐng)域6.1遺傳算法的基本原理6.3

遺傳算法的優(yōu)化設(shè)計6.4遺傳算法求函數(shù)極值406.5遺傳算法的特點

（1）遺傳算法是對參數(shù)的編碼進(jìn)行操作，而非對參數(shù)本身，這就是使得我們在優(yōu)化計算過程中可以借鑒生物學(xué)中染色體和基因等概念，模仿自然界中生物的遺傳和進(jìn)化等機(jī)理；（2）遺傳算法同時使用多個搜索點的搜索信息。傳統(tǒng)的優(yōu)化方法往往是從解空間的單個初始點開始最優(yōu)解的迭代搜索過程，單個搜索點所提供的信息不多，搜索效率不高，有時甚至使搜索過程局限于局部最優(yōu)解而停滯不前。41遺傳算法從由很多個體組成的一個初始群體開始最優(yōu)解的搜索過程，而不是從一個單一的個體開始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。（3）遺傳算法直接以目標(biāo)函數(shù)作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標(biāo)函數(shù)值變換來的適應(yīng)度函數(shù)值，就可以確定進(jìn)一步的搜索方向和搜索范圍，無需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。42遺傳算法可應(yīng)用于目標(biāo)函數(shù)無法求導(dǎo)數(shù)或?qū)?shù)不存在的函數(shù)的優(yōu)化問題，以及組合優(yōu)化問題等。（4）遺傳算法使用概率搜索技術(shù)。遺傳算法的選擇、交叉