智能控制技術(shù)(第7章-遺傳算法)課件

1、第七章 遺 傳 算 法 遺傳算法簡(jiǎn)稱(chēng)GA（Genetic Algorithms）是1962年由美國(guó)Michigan大學(xué)的Holland教授提出的模擬自然界遺傳機(jī)制和生物進(jìn)化論而成的一種并行隨機(jī)搜索最優(yōu)化方法。 遺傳算法是以達(dá)爾文的自然選擇學(xué)說(shuō)為基礎(chǔ)發(fā)展起來(lái)的。遺傳算法的基本原理遺 傳 算 法自然選擇學(xué)說(shuō)包括以下三個(gè)方面：（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個(gè)特征，物種才能穩(wěn)定存在。（2）變異：親代和子代之間以及子代的不同個(gè)體之間的差異，稱(chēng)為變異。變異是隨機(jī)發(fā)生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭(zhēng)和適者生存：具有

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

3、n Operator） 復(fù)制是從一個(gè)舊種群中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過(guò)程。具有高適應(yīng)度的位串更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。 復(fù)制操作可以通過(guò)隨機(jī)方法來(lái)實(shí)現(xiàn)。首先產(chǎn)生01之間均勻分布的隨機(jī)數(shù)，若某串的復(fù)制概率為40%，則當(dāng)產(chǎn)生的隨機(jī)數(shù)在0.401.0之間時(shí)，該串被復(fù)制，否則被淘汰。遺傳算法的基本操作遺 傳 算 法 交叉體現(xiàn)了自然界中信息交換的思想。交叉有一點(diǎn)交叉、多點(diǎn)交叉、還有一致交叉、順序交叉和周期交叉。一點(diǎn)交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點(diǎn)有一處，例：遺 傳 算 法遺傳算法的基本操作（3）變異(Mutation Operator) 變異運(yùn)算用來(lái)模擬生物在自然的

4、遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)地改變遺傳基因（表示染色體的符號(hào)串的某一位）的值。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由1變?yōu)?，或由0變?yōu)?。遺 傳 算 法遺傳算法的基本操作（1）遺傳算法是對(duì)參數(shù)的編碼進(jìn)行操作，而非對(duì)參數(shù)本身，這就是使得我們?cè)趦?yōu)化計(jì)算過(guò)程中可以借鑒生物學(xué)中染色體和基因等概念，模仿自然界中生物的遺傳和進(jìn)化等機(jī)理；（2）遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。傳統(tǒng)的優(yōu)化方法往往是從解空間的單個(gè)初始點(diǎn)開(kāi)始最優(yōu)解的迭代搜索過(guò)程，單個(gè)搜索點(diǎn)所提供的信息不多，搜索效率不高，有時(shí)甚至使搜索過(guò)程局限于局部最優(yōu)解而停滯不前。遺傳算法的特點(diǎn)遺 傳

5、 算 法 遺傳算法從由很多個(gè)體組成的一個(gè)初始群體開(kāi)始最優(yōu)解的搜索過(guò)程，而不是從一個(gè)單一的個(gè)體開(kāi)始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。（3）遺傳算法直接以目標(biāo)函數(shù)作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標(biāo)函數(shù)值變換來(lái)的適應(yīng)度函數(shù)值，就可以確定進(jìn)一步的搜索方向和搜索范圍，無(wú)需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。遺 傳 算 法遺傳算法的特點(diǎn) 遺傳算法可應(yīng)用于目標(biāo)函數(shù)無(wú)法求導(dǎo)數(shù)或?qū)?shù)不存在的函數(shù)的優(yōu)化問(wèn)題，以及組合優(yōu)化問(wèn)題等。（4）遺傳算法使用概率搜索技術(shù)。遺傳算法的選擇、交叉、變異等

6、運(yùn)算都是以一種概率的方式來(lái)進(jìn)行的，因而遺傳算法的搜索過(guò)程具有很好的靈活性。隨著進(jìn)化過(guò)程的進(jìn)行，遺傳算法新的群體會(huì)更多地產(chǎn)生出許多新的優(yōu)良的個(gè)體。遺 傳 算 法遺傳算法的特點(diǎn)（1）函數(shù)優(yōu)化。 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。尤其是對(duì)非線(xiàn)性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，采用其他優(yōu)化方法較難求解，而遺傳算法卻可以得到較好的結(jié)果。遺傳算法的應(yīng)用領(lǐng)域遺 傳 算 法（2）組合優(yōu)化。 隨著問(wèn)題的增大，組合優(yōu)化問(wèn)題的搜索空間也急劇擴(kuò)大，采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解。遺傳算法是尋求這種滿(mǎn)意解的最佳工具。例如，遺傳算法已經(jīng)在求解旅行商問(wèn)題、背包問(wèn)題、裝箱問(wèn)題、圖形劃分問(wèn)

7、題等方面得到成功的應(yīng)用。遺 傳 算 法遺傳算法的應(yīng)用領(lǐng)域（4）自動(dòng)控制。 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問(wèn)題需要求解，遺傳算法已經(jīng)在其中得到了初步的應(yīng)用。例如，利用遺傳算法進(jìn)行控制器參數(shù)的優(yōu)化、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化和權(quán)值學(xué)習(xí)等。遺 傳 算 法遺傳算法的應(yīng)用領(lǐng)域（5）機(jī)器人 例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。（6）圖像處理 遺傳算法可用于圖像處理過(guò)程中的掃描、特征提取、圖像分割等的優(yōu)化計(jì)算。目前遺傳算法已經(jīng)在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方

8、面得到了應(yīng)用。遺 傳 算 法遺傳算法的應(yīng)用領(lǐng)域遺傳算法的構(gòu)成要素（1）染色體編碼方法 基本遺傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)來(lái)表示群體中的個(gè)體，其等位基因是由二值符號(hào)集0,1所組成。初始個(gè)體基因值可用均勻分布的隨機(jī)值生成，如就可表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度是18。遺傳算法的優(yōu)化設(shè)計(jì)遺 傳 算 法（2）個(gè)體適應(yīng)度評(píng)價(jià)：基本遺傳算法與個(gè)體適應(yīng)度成正比的概率來(lái)決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的概率多少。為正確計(jì)算這個(gè)概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。因此，必須先確定由目標(biāo)函數(shù)值J到個(gè)體適應(yīng)度f(wàn)之間的轉(zhuǎn)換規(guī)則。遺 傳 算 法遺傳算法的優(yōu)化設(shè)計(jì)（3）遺傳算子：基本遺傳算法使用下述三種遺

9、傳算子： 選擇運(yùn)算:使用比例選擇算子； 交叉運(yùn)算:使用單點(diǎn)交叉算子； 變異運(yùn)算:使用基本位變異算子或均勻變異算子。遺 傳 算 法遺傳算法的優(yōu)化設(shè)計(jì)（4）基本遺傳算法的運(yùn)行參數(shù) 有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20100；G：遺傳算法的終止進(jìn)化代數(shù)，一般取為100500；Pc：交叉概率，一般取為0.40.99；Pm：變異概率，一般取為0.00010.1。遺 傳 算 法遺傳算法的優(yōu)化設(shè)計(jì)第三步：確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型x及遺傳算法的搜索空間；第四步：確定解碼方法，即確定出由個(gè)體基因型x到個(gè)體表現(xiàn)型X的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法；第五

10、步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則；第六步：設(shè)計(jì)遺傳算子，即確定選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法。第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即M,G,Pc,Pm等參數(shù)。遺 傳 算 法遺傳算法的應(yīng)用步驟遺傳算法流程圖 遺傳算法的操作過(guò)程遺 傳 算 法二進(jìn)制編碼遺傳算法求函數(shù)極大值 求解該問(wèn)題遺傳算法的構(gòu)造過(guò)程：（1）確定決策變量和約束條件；（2）建立優(yōu)化模型；（3）確定編碼方法 遺 傳 算 法遺傳算法求函數(shù)極值 用長(zhǎng)度為10位的二進(jìn)制編碼串來(lái)分別表示兩個(gè)決策變量x1,x2。10位二進(jìn)制編碼串可以表示從0到1023之間的1024個(gè)不同的數(shù)，故

11、將x1,x2的定義域離散化為1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有1024個(gè)不同的離散點(diǎn)。 從離散點(diǎn)-2.048到離散點(diǎn)2.048 ，分別對(duì)應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。遺 傳 算 法遺傳算法求函數(shù)極值 將x1,x2分別表示的兩個(gè)10位長(zhǎng)的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長(zhǎng)的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對(duì)應(yīng)的關(guān)系。例如： 表示一個(gè)個(gè)體的基因型，其中前10位表示x1，后10位表示x2。遺 傳 算 法遺傳算法求函數(shù)極值（4）確定解碼方法：解碼時(shí)需要將2

12、0位長(zhǎng)的二進(jìn)制編碼串切斷為兩個(gè)10位長(zhǎng)的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。 依據(jù)個(gè)體編碼方法和對(duì)定義域的離散化方法可知，將代碼y轉(zhuǎn)換為變量x的解碼公式為 例如，對(duì)個(gè)體遺 傳 算 法遺傳算法求函數(shù)極值 它由兩個(gè)代碼所組成 上述兩個(gè)代碼經(jīng)過(guò)解碼后，可得到兩個(gè)實(shí)際的值（5）確定個(gè)體評(píng)價(jià)方法：由于Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故可將個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，即遺 傳 算 法遺傳算法求函數(shù)極值選個(gè)體適應(yīng)度的倒數(shù)作為目標(biāo)函數(shù)（6）設(shè)計(jì)遺傳算子：選擇運(yùn)算使用比例選擇算子，交叉運(yùn)算使用單點(diǎn)交叉算子，變異運(yùn)算使用基本

13、位變異算子。（7）確定遺傳算法的運(yùn)行參數(shù)：群體大小M=80，終止進(jìn)化代數(shù)G=100，交叉概率Pc=0.60，變異概率Pm=0.10。 上述七個(gè)步驟構(gòu)成了用于求函數(shù)極大值的優(yōu)化計(jì)算基本遺傳算法。遺 傳 算 法遺傳算法求函數(shù)極值 采用上述方法進(jìn)行仿真，經(jīng)過(guò)100步迭代，最佳樣本為即當(dāng) 時(shí)，Rosenbrock函數(shù)具有極大值，極大值為3905.9。遺 傳 算 法遺傳算法求函數(shù)極值 遺傳算法的優(yōu)化過(guò)程是目標(biāo)函數(shù)J和適應(yīng)度函數(shù)F的變化過(guò)程。 由仿真結(jié)果可知，隨著進(jìn)化過(guò)程的進(jìn)行，群體中適應(yīng)度較低的一些個(gè)體被逐漸淘汰掉，而適應(yīng)度較高的一些個(gè)體會(huì)越來(lái)越多，并且它們都集中在所求問(wèn)題的最優(yōu)點(diǎn)附近，從而搜索到問(wèn)題的

14、最優(yōu)解。遺 傳 算 法遺傳算法求函數(shù)極值實(shí)數(shù)編碼遺傳算法求函數(shù)極大值求解該問(wèn)題遺傳算法的構(gòu)造過(guò)程：（1）確定決策變量和約束條件；（2）建立優(yōu)化模型；（3）確定編碼方法：用2個(gè)實(shí)數(shù)分別表示兩個(gè)決策變量，分別將的定義域離散化為從離散點(diǎn)-2.048到離散點(diǎn)2.048的Size個(gè)實(shí)數(shù)。遺 傳 算 法遺傳算法求函數(shù)極值（4）確定個(gè)體評(píng)價(jià)方法： 個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，即 選個(gè)體適應(yīng)度的倒數(shù)作為目標(biāo)函數(shù) 遺 傳 算 法遺傳算法求函數(shù)極值（5）設(shè)計(jì)遺傳算子：選擇運(yùn)算使用比例選擇算子，交叉運(yùn)算使用單點(diǎn)交叉算子，變異運(yùn)算使用基本位變異算子。（6）確定遺傳算法的運(yùn)行參數(shù)：群體大小M=500，終止進(jìn)化

15、代數(shù)G=200，交叉概率Pc=0.90，采用自適應(yīng)變異概率即變異概率與適應(yīng)度有關(guān)，適應(yīng)度越小，變異概率越大。 遺 傳 算 法遺傳算法求函數(shù)極值 上述六個(gè)步驟構(gòu)成了用于求函數(shù)Rosenbrock極大值的優(yōu)化計(jì)算的實(shí)數(shù)編碼遺傳算法。 十進(jìn)制編碼求函數(shù)Rosenbrock極大值。 仿真程序經(jīng)過(guò)200步迭代，最佳樣本為即當(dāng) ， 時(shí)，函數(shù)具有極大值，極大值為3880.3。 遺 傳 算 法遺傳算法求函數(shù)極值 在RBF網(wǎng)絡(luò)逼近算法中，網(wǎng)絡(luò)權(quán)值、高斯函數(shù)的中心矢量和基寬向量的初值難以確定，如果這些參數(shù)選擇不當(dāng)，會(huì)造成逼近精度的下降甚至RBF網(wǎng)絡(luò)的發(fā)散。采用遺傳算法可實(shí)現(xiàn)RBF網(wǎng)絡(luò)參數(shù)的優(yōu)化。遺傳算法的優(yōu)化原理

16、遺 傳 算 法 為獲取滿(mǎn)意的逼近精度，采用誤差絕對(duì)值指標(biāo)作為參數(shù)選擇的最小目標(biāo)函數(shù)。 式中， 為逼近的總步驟， 為第 步RBF網(wǎng)絡(luò)的逼近誤差。 在應(yīng)用遺傳算法時(shí)，為了避免參數(shù)選取范圍過(guò)大，可以先按經(jīng)驗(yàn)選取一組參數(shù)，然后再在這組參數(shù)的周?chē)眠z傳算法進(jìn)行設(shè)計(jì)，從而大大減少初始尋優(yōu)的盲目性，節(jié)約計(jì)算量。遺 傳 算 法遺傳算法的優(yōu)化原理7.2、基本遺傳算法 基本遺傳算法（Simple Genetic Algorithms，簡(jiǎn)稱(chēng)SGA，又稱(chēng)簡(jiǎn)單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。 基本遺傳算法的組

17、成 （1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù) 編碼 GA是通過(guò)某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。 函數(shù)優(yōu)化示例 求下列一元函數(shù)的最大值： x-1,2 ，求解結(jié)果精確到6位小數(shù)。SGA對(duì)于本例的編碼 由于區(qū)間長(zhǎng)度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3106等份。又因?yàn)?21 3106 00 if f(X)+Cmin 0 對(duì)于求最小值問(wèn)題，變換如下：F(X) =Cmax - f(X) if f(X) Cmax0 if f

18、(X) Cmax 適應(yīng)度尺度變換 (1) 適應(yīng)度尺度變換的原因 在遺傳算法中，各個(gè)個(gè)體被遺傳到下一代群體中的概率是由該個(gè)體的適應(yīng)度來(lái) 確定的，應(yīng)用實(shí)踐表明，僅使用以上兩式來(lái)計(jì)算個(gè)體適應(yīng)度時(shí)，有些遺傳算法 會(huì)收斂得很快，也有些遺傳算法會(huì)收斂得很慢。 在遺傳算法運(yùn)行的初期階段 群體中可能會(huì)有少數(shù)幾個(gè)個(gè)體的適應(yīng)度相對(duì)其他個(gè)體來(lái)說(shuō)非常高。若按照常 用的比例選擇算子來(lái)確定個(gè)體的遺傳數(shù)量時(shí)，則這幾個(gè)相對(duì)較好的個(gè)體將在下 一代群體中占有很高的比例，在極端情況下或當(dāng)群體現(xiàn)模較小時(shí)，新的群體甚 至完全由這樣的少數(shù)幾個(gè)個(gè)體所組成。這時(shí)產(chǎn)生新個(gè)體作用較大的交叉算子就 起不了什么作用，因?yàn)橄嗤膬蓚€(gè)個(gè)體不論在何處進(jìn)行

19、交叉操作都永遠(yuǎn)不會(huì)產(chǎn) 生出新的個(gè)體，如下所示： A: 10101010 1010 10101010 1010 B: 10101010 1010 10101010 1010單點(diǎn)交叉 這樣就會(huì)使群體的多樣性降低，容易導(dǎo)致遺傳算法發(fā)生早熟現(xiàn)象（或稱(chēng)早期收 斂)，使遺傳算法所求到的解停留在某一局部最優(yōu)點(diǎn)上。 因此，我們希望在遺傳算法運(yùn)行的初期階段，算法能夠?qū)σ恍┻m應(yīng)度較高的個(gè) 體進(jìn)行控制，降低其適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，從而限制其復(fù) 制數(shù)量，以維護(hù)群體的多樣性。 在遺傳算法運(yùn)行的后期階段 群體中所有個(gè)體的平均適應(yīng)度可能會(huì)接近于群體中最佳個(gè)體的適應(yīng)度。也就 是說(shuō)，大部分個(gè)體的適應(yīng)度和最佳個(gè)體

20、的適應(yīng)度差異不大，它們之間無(wú)競(jìng)爭(zhēng)力， 都會(huì)有以相接近的概率被遺傳到下一代的可能性，從而使得進(jìn)化過(guò)程無(wú)競(jìng)爭(zhēng)性 可言，只是一種隨機(jī)的選擇過(guò)程。這將導(dǎo)致無(wú)法對(duì)某些重點(diǎn)區(qū)域進(jìn)行重點(diǎn)搜索， 從而影響遺傳算法的運(yùn)行效率。 因此，我們希望在遺傳算法運(yùn)行的后期階段，算法能夠?qū)€(gè)體的適應(yīng)度進(jìn)行 適當(dāng)?shù)姆糯?，擴(kuò)大最佳個(gè)體適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，以提高 個(gè)體之間的競(jìng)爭(zhēng)性。(2) 適應(yīng)度尺度變換定義 在遺傳算法運(yùn)行的不同階段，有時(shí)需要對(duì)個(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大或縮小。 這種對(duì)個(gè)體適應(yīng)度所做的擴(kuò)大或縮小變換就稱(chēng)為適應(yīng)度尺度變換。(3) 適應(yīng)度尺度變換方法 目前常用的個(gè)體適應(yīng)度尺度變換方法主要有三種：線(xiàn)性

21、尺度變換、乘冪尺度變 換和指數(shù)尺度變換。 . 線(xiàn)性尺度變換。 線(xiàn)性尺度變換的公式如下: F = aF + b 式中 F原適應(yīng)度； F變換后的新適應(yīng)度； a,b系數(shù)。 系數(shù)a,b直接影響到這個(gè)尺度變換的大小，所以對(duì)其選取有一定的要求，一般 希望它們滿(mǎn)足下面兩個(gè)條件: 條件1：尺度變換后全部個(gè)體的新適應(yīng)度的平均值 Favg 要等于其原適應(yīng)度平均值Favg 即： Favg = Favg 這條要求是為了保證群體中適應(yīng)度接近于平均適應(yīng)度的個(gè)體能夠有期待的數(shù) 量被遺傳到下一代群體中。 條件2：尺度變換后群體中新的最大適應(yīng)度 Fmax 要等于其原平均適應(yīng)度 Favg 的指定 倍數(shù)。即： Fmax = CFa

22、vg 式中，C為最佳個(gè)體的期望復(fù)制數(shù)量，對(duì)于群體規(guī)模大小為50 100個(gè)個(gè)體的 情況，一般取 C = 1.2 2。 這條要求是為了保證群體中最好的個(gè)體能夠期望復(fù)制C倍到新一代群體中。 如下圖所示。 最小適應(yīng)度為負(fù)時(shí)的處理： 在遺傳算法執(zhí)行的后期，個(gè)別劣質(zhì)個(gè)體的適應(yīng)度遠(yuǎn)遠(yuǎn)小于群體平均適應(yīng)度及最 大適應(yīng)度，并且后兩者比較接近。這時(shí)按上述方法縮放適應(yīng)度會(huì)使低適應(yīng)度變成 負(fù)值，如圖所示。這將會(huì)給后面的處理過(guò)程帶來(lái)不便，必須避免這種情況的發(fā)生， 解決這個(gè)問(wèn)題的方法是：把原最小適應(yīng)度Fmin映射為Fmin= 0，并且保持原平均適 應(yīng)度 Favg與新的平均適應(yīng)度 Favg 相等。 綜上所述，參數(shù)a, b的計(jì)

23、算方法如下： (1) 計(jì)算適應(yīng)度非負(fù)判別式： Fmin C Favg - FmaxC -1 若不等式滿(mǎn)足，則執(zhí)行(2)， 否則執(zhí)行(3)。 (2) 正常情況下的縮放： C - 1 a =Fmax - FavgFavgFmax - C Favg b =Fmax - FavgFavg(3) 負(fù)適應(yīng)度時(shí)的縮放： a =FavgFavg - Fmin b =Favg FminFavg - Fmin . 乘冪尺度變換 乘冪尺度變換的公式為： F = Fk 即新的適應(yīng)度是原有適應(yīng)度的某個(gè)指定乘冪。冪指數(shù)k與所求解的問(wèn)題有關(guān)， 并且在算法的執(zhí)行過(guò)程中需要不斷對(duì)其進(jìn)行修正才能使尺度變換滿(mǎn)足一定的伸 縮要求。

24、. 指數(shù)尺度變換 指數(shù)尺度變換的公式為： Fexp(-F) 即新的適應(yīng)度是原有適應(yīng)度的某個(gè)指數(shù)。式中系數(shù)決定了選擇的強(qiáng)制性， 越小，原有適應(yīng)度較高的個(gè)體的新適應(yīng)度就越與其他個(gè)體的新適應(yīng)度相差較 大，亦即越增加了選擇該個(gè)體的強(qiáng)制性。7.3.3 約束條件的處理方法 實(shí)際應(yīng)用中的優(yōu)化問(wèn)題一般都含有一定的約束條件，它們的描述形式各種各樣。 在遺傳算法的應(yīng)用中，必須對(duì)這些約束條件進(jìn)行處理，而目前還未找到一種能夠 處理各種約束條件的一般化方法。所以對(duì)約束條件進(jìn)行處理時(shí)，只能是針對(duì)具體 應(yīng)用問(wèn)題及約束條件的特征，再考慮遺傳算法中遺傳算子的運(yùn)行能力，選用不同 的處理方法。 在構(gòu)造遺傳算法時(shí)，處理約束條件的常用

25、方法主要有如下三種： 搜索空間限定法 罰函數(shù)法 可行解變換法 (1) 搜索空間限定法 基本思想 對(duì)遺傳算法的搜索空間的大小加以限制，使得搜索空間中表示一個(gè)個(gè)體的點(diǎn)與解空間中表示一個(gè)可行解的點(diǎn)有一一對(duì)應(yīng)的關(guān)系。此時(shí)的搜索空間與解空間的對(duì)應(yīng)關(guān)系如圖所示。 對(duì)一些比較簡(jiǎn)單的約束條件(如axb之類(lèi)) 在個(gè)體染色體的編碼方法上著手，就能夠達(dá)到這種搜索空間與解空間之間的對(duì) 應(yīng)的要求。 用這種處理方法能夠在遺傳算法中設(shè)置最小的搜索空間，所以它能夠提高遺傳 算法的搜索效率。 但需要注意的是：除了在編碼方法上想辦法之外，也必須保證經(jīng)過(guò)交叉、變異 等遺傳其子作用之后所產(chǎn)生出的新個(gè)體在解空間中也要有確 定的對(duì)應(yīng)解，

26、而不會(huì)產(chǎn)生無(wú)效解。 處理方法 方法一：用編碼方法來(lái)保證總是能夠產(chǎn)生出在解空間中有對(duì)應(yīng)可行解的染色體。 這個(gè)實(shí)現(xiàn)方法要求我們?cè)O(shè)計(jì)出一種比較好的個(gè)體編碼方案。 如前面我們講到的二進(jìn)制編碼方案即可實(shí)現(xiàn)上述要求。 方法二：用程序來(lái)保證直到產(chǎn)生出在解空間中有對(duì)應(yīng)可行解的染色體之前，一 直進(jìn)行交叉運(yùn)算和變異運(yùn)算。 雖然這個(gè)實(shí)現(xiàn)方法對(duì)編碼方法的要求不高，但它有可能需要反復(fù)地進(jìn) 行交叉運(yùn)算和變異運(yùn)算才能產(chǎn)生出一個(gè)滿(mǎn)足約束條件的可行解，這樣 就有可能會(huì)降低遺傳算法的運(yùn)行效率。 (2) 罰函數(shù)法 基本思想 對(duì)在解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體，計(jì)算其適應(yīng)度時(shí)，處以一個(gè)罰函數(shù)，從 而降低該個(gè)體適應(yīng)度，使該個(gè)體被遺傳到下一

27、代群體中的機(jī)會(huì)減少。即用下式 來(lái)對(duì)個(gè)體的適應(yīng)度進(jìn)行調(diào)整：F(X) X滿(mǎn)足約束條件時(shí)F(X) P(X) X不滿(mǎn)足約束條件時(shí)F(X)= 式中，F(xiàn)(X)為原適應(yīng)度; F(x)為考慮了罰函數(shù)之后的新適應(yīng)度; P(x)為罰函數(shù)。懲罰函數(shù) 設(shè)有優(yōu)化問(wèn)題的目標(biāo)函數(shù)： max F(x1,x2,xn) S.t. Hi(x1,x2,xn) i=1,2,m max 式中 懲罰函數(shù)； 懲罰系數(shù)。 . 最簡(jiǎn)單的懲罰函數(shù)形式是平方法，即：.也有人建議采用松緊法。在遺傳算法初期，懲罰輕一些；到了后期，則懲 罰重一些。具體的新目標(biāo)函數(shù)F為： 加入罰函數(shù)后，原來(lái)的問(wèn)題變?yōu)橄率鲆粋€(gè)新的目標(biāo)函數(shù)： 其中： K系數(shù)，可取 1/m；

28、t當(dāng)前的迭代代次； T終止迭代次數(shù)； 系數(shù)，1左右； f個(gè)體適應(yīng)度的平均值； di違背約束i的程度，視問(wèn)題的不同而定義。難點(diǎn) 如何確定合理的罰函數(shù)是這種處理方法的難點(diǎn)之所在，因?yàn)檫@時(shí)既要考慮如 何度量解對(duì)約束條件不滿(mǎn)足的程度，又要考慮遺傳算法在計(jì)算效率上的要求。 罰函數(shù)的強(qiáng)度太小的話(huà)，部分個(gè)體仍有可能破壞約束條件，所以保證不了遺 傳運(yùn)算所得到的個(gè)體一定是滿(mǎn)足約束條件的一個(gè)可行解； 罰函數(shù)的強(qiáng)度太大的話(huà)，又有可能使個(gè)體的適應(yīng)度差異不大，降低了個(gè)體之 間的競(jìng)爭(zhēng)力，從而影響遺傳算法的運(yùn)行效率。(3) 可行解變換法 基本思想 在由個(gè)體基因型到個(gè)體表現(xiàn)型 的變換中，增加使其滿(mǎn)足約束條 件的處理過(guò)程。 即

29、尋找出一種個(gè) 體基因型和個(gè)體表現(xiàn)型之間的多 對(duì)一的變換關(guān)系，使進(jìn)化過(guò)程中 所產(chǎn)生的個(gè)體總能夠通過(guò)這個(gè)變 換而轉(zhuǎn)化成解空間中滿(mǎn)足約束條 件的一個(gè)可行解。 下圖為該方法的示意圖。 優(yōu)劣 這種處理方法雖然對(duì)個(gè)體的編 碼方法、交叉運(yùn)算、變異運(yùn)算 等沒(méi)有附加的要求，但它卻是以 擴(kuò)大搜索空間為代價(jià)的，所以一 般會(huì)使得遺傳算法的運(yùn)行效率有 所下降。7.3.4 選擇算子 在生物的遺傳和自然進(jìn)化過(guò)程中，對(duì)生存環(huán)境適應(yīng)程度較高的物種將有更多 的機(jī)會(huì)遺傳到下一代； 遺傳算法中的選擇操作用來(lái)確定如何從父代群體中按某種方法選取哪些個(gè)體 遺傳到下一代群體中的一種遺傳運(yùn)算。選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng) 價(jià)的基礎(chǔ)上。

30、最常用的選擇算子是基本遺傳算法中的比例選擇算子。 但對(duì)于各種不同的問(wèn)題，比例選擇算子并不是最合適的一種選擇算子，所以 人們提出了其他一些選擇算于。下面介紹幾種常用選擇算子的操作方法。比例選擇 ( Fitness proportional selection ) 基本思想 各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。 設(shè)群體大小為M，個(gè)體i的適應(yīng)度為Fi，則個(gè)體i被選中的概率pis為： M pis= Fi / Fi i=1 i=1,2,M 特點(diǎn) 適應(yīng)度越高的個(gè)體被選中的概率也越大，適應(yīng)度越低的個(gè)體被選中的概 率也越小。 缺點(diǎn) 由于是隨機(jī)操作的原因，這種選擇方法的選擇誤差比較大，有時(shí)甚至連 適應(yīng)度較

31、高的個(gè)體也選擇不上。分級(jí)選擇 ( ranking selecton ) （或稱(chēng)排序選擇） (1) 產(chǎn)生原因 遺傳算法中個(gè)體適應(yīng)度數(shù)值上的差別有時(shí)會(huì)很大，尤其是在算法的早期這種差 別更是懸殊。因此，個(gè)別特優(yōu)個(gè)體會(huì)多次被選中進(jìn)行復(fù)制，經(jīng)過(guò)幾代后它們?cè)谌?體中數(shù)目愈來(lái)愈多，沖淡了群體的多樣性。因此，人們提出分級(jí)的概念，用連續(xù) 漸變的分級(jí)代替數(shù)值懸殊的適應(yīng)度。 (2) 方法 設(shè)群體中有m個(gè)個(gè)體，將它們按降序方法依次排序，規(guī)定個(gè)體優(yōu)劣的等級(jí)依 次為：1，2，3，i，M。 采用線(xiàn)性分級(jí)， 使各個(gè)個(gè)體被選中的可能性有如下線(xiàn)性關(guān)系： p(i) = q - ( i -1 )d 其中， q 最優(yōu)個(gè)體被選中的概率；

32、 d 相鄰個(gè)體被選中概率之差。 上述線(xiàn)性關(guān)系使p(i)構(gòu)成等差級(jí)數(shù)，即： q， q - d， q 2d， q - id，q (M-1)d 由于概率定義要求 ，按級(jí)數(shù)求和，有：即：下面按兩種情況討論： . 所有個(gè)體按相同概率選取，即 d=0 ，得： q = 1/M . 令最壞（最后）個(gè)體的的選取概率為0，即 q (M-1)d = 0，帶入 式，得： q = 2/M 于是，q可在這兩種極端情況下選取，即： 1/M q 2/M 有了q，由 式，可得：(3) 優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：消除個(gè)體適應(yīng)度差別懸殊時(shí)的影響，代替適應(yīng)度的縮放技術(shù)。 缺點(diǎn)：抹殺個(gè)體適應(yīng)度的實(shí)際差別，未能充分運(yùn)用遺傳信息。競(jìng)技選擇法 (tou

33、rnament selection) (1) 方法簡(jiǎn)介 這種選擇法通過(guò)相互競(jìng)爭(zhēng)，優(yōu)勝者成為下一代的個(gè)體。在每一代群體中，每次 都隨機(jī)選擇 k個(gè)個(gè)體構(gòu)成一個(gè)小群體，然后從這 k個(gè)個(gè)體中確定性地取適應(yīng)度最 大的個(gè)體復(fù)制，進(jìn)入下一代群體。被復(fù)制后的個(gè)體仍返回父代群體中，參加下 一次 k個(gè)個(gè)體的隨機(jī)選擇。這種隨機(jī)選擇重復(fù)M次，產(chǎn)生M個(gè)下一代個(gè)體 (2) 具體操作步驟 . 從第t代群體中隨機(jī)選擇 k個(gè)個(gè)體； . 比較 k個(gè)個(gè)體的適應(yīng)度，復(fù)制適應(yīng)度最大者進(jìn)入第 t+1 代，被復(fù)制的個(gè)體 仍保留在第 t 代； . 重復(fù)執(zhí)行、 M次，直至產(chǎn)生同 t 代一樣的個(gè)體數(shù)目。 (3) 特點(diǎn) 競(jìng)技選擇法中，選擇的力度取

34、決于 k值的大小。k值愈大，每次選出的優(yōu)勝者 具有很高的適應(yīng)度。反之，k值愈小，優(yōu)勝者的適應(yīng)度或高或低，隨機(jī)性很強(qiáng)。最優(yōu)保存策略（Elitist selection ) 在遺傳算法的運(yùn)行過(guò)程中通過(guò)對(duì)個(gè)體進(jìn)行交叉、變異等遺傳操作而不斷地產(chǎn) 生出新的個(gè)體。雖然隨著群體的進(jìn)化過(guò)程會(huì)產(chǎn)生出越來(lái)越多的優(yōu)良個(gè)體，但由 于選擇、交叉、變異等遺傳操作的隨機(jī)性，它們也有可能破壞掉當(dāng)前群體中適 應(yīng)度最好的個(gè)體。我們希望適應(yīng)度最好的個(gè)體要盡可能地保留到下一代群體中。 為達(dá)到這個(gè)目的，可以使用最優(yōu)保存策略進(jìn)化模型來(lái)進(jìn)行優(yōu)勝劣汰操作。 (1) 基本思想 當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是用它來(lái)替換

35、 掉本代群體中經(jīng)過(guò)交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體。 (2) 最優(yōu)保存策略進(jìn)化模型的具體操作過(guò)程 . 找出當(dāng)前群體中適應(yīng)度最高的個(gè)體和適應(yīng)度最低的個(gè)體。 . 若當(dāng)前群體中最佳個(gè)體的適應(yīng)度比總的迄今為止的最好個(gè)體的適應(yīng)度還要 高，則以當(dāng)前群體中的最佳個(gè)體作為新的迄今為止的最好個(gè)體。 . 用迄今為止的最好個(gè)體替換掉當(dāng)前群體中的最差個(gè)體。 (3) 特點(diǎn)：最優(yōu)保存策略可視為選擇操作的一部分。該策略的實(shí)施可保證迄今為止 所得到的最優(yōu)個(gè)體不會(huì)被交叉、變異等遺傳運(yùn)算所破壞，它是遺傳算 法收斂性的一個(gè)重要保證條件。 缺點(diǎn)：它容易使得某個(gè)局部最優(yōu)個(gè)體不易被淘汰掉反而快速擴(kuò)散，從而使得 算法的全局搜

36、索能力不強(qiáng)。 (4) 使用方法： 該方法一般要與其他一些選擇操作方法配合起來(lái)使用，方可有良好的效果。 另外，最優(yōu)保存策略還可加以推廣，即在每一代的進(jìn)化過(guò)程中保留多個(gè)最優(yōu)個(gè) 體不參加交叉、變異等遺傳運(yùn)算，而直接將它們復(fù)制到下一代群體中。這種選 擇方法也稱(chēng)為穩(wěn)態(tài)復(fù)制。確定式采樣選擇 ( Deterministic Sampling selection) (1) 基本思想：按照一種確定的方式來(lái)進(jìn)行選擇操作 (2) 具體操作過(guò)程： . 計(jì)算群體中各個(gè)個(gè)體在下一代群體中的期望生存數(shù)目Ni： . 用Ni 的整數(shù)部分 Ni 確定各個(gè)對(duì)應(yīng)個(gè)體在下一代群體中的生存數(shù)目 ( x 表示下取值，取不大于x的最大整數(shù)。

37、) . 按照Ni 的小數(shù)部分對(duì)個(gè)體進(jìn)行降序排序，順序取前 M 個(gè)個(gè)體 加入到下一代群體中。 至此可完全確定出下一代群體中的M個(gè)個(gè)體。 (3) 特點(diǎn)：這種選擇操作方法可保證適應(yīng)度較大的一些個(gè)體一定能夠被保留在下 一代群體中，并且操作也比較簡(jiǎn)單。 M Ni i=1i=1,2,M7.3.5交叉算子 在生物的自然進(jìn)化過(guò)程中，兩個(gè)同源染色體通過(guò)交配而重組，形成新的染色體， 從而產(chǎn)生出新的個(gè)體或物種。交配重組是生物遺傳和進(jìn)化過(guò)程中的一個(gè)主要環(huán) 節(jié)。模仿這個(gè)環(huán)節(jié)，在遺傳算法中也使用交叉算子來(lái)產(chǎn)生新的個(gè)體。 遺傳算法中的所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交 換其部分基因，從而形成兩個(gè)新的個(gè)

38、體。 交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與所研究的問(wèn)題密切相關(guān)，一般要求它既不要太多地破 壞個(gè)體編碼串中表示優(yōu)良性狀的優(yōu)良模式，又要能夠有效地產(chǎn)生出一些較好的 新個(gè)體模式。另外，交叉算子的設(shè)計(jì)要和個(gè)體編碼設(shè)計(jì)統(tǒng)一考慮。 交叉算子的設(shè)計(jì)包括以下兩方面的內(nèi)容: (1) 如何確定交叉點(diǎn)的位置? (2) 如何進(jìn)行部分基因交換? 單點(diǎn)交叉 ( One-point Crossover ) (1) 單點(diǎn)交叉：又稱(chēng)為簡(jiǎn)單交叉，它是指在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)， 然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。 (2) 特點(diǎn)：若鄰接基因座之間的關(guān)系能提供較好的個(gè)體性狀和較高的個(gè)體適應(yīng)度 的話(huà)，則這種單點(diǎn)交叉操作破壞這種個(gè)

39、體性狀和降低個(gè)體適應(yīng)度的可 能性最小。雙點(diǎn)交叉與多點(diǎn)交叉 (1) 雙點(diǎn)交叉 ( Two-point Crossover )： 指在個(gè)體編碼串中隨機(jī)設(shè)置了二個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換。 (2) 雙點(diǎn)交叉的具體操作過(guò)程 . 在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)。 . 交換兩個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。例如：(3) 多點(diǎn)交叉 ( Multi-point Crossover )： 指在個(gè)體編碼串中隨機(jī)設(shè)置多個(gè)交叉點(diǎn)，然后進(jìn)行基因交換。多點(diǎn)交叉又稱(chēng)為 廣義交叉。(4) 操作過(guò)程：與單點(diǎn)交叉和雙點(diǎn)交叉相類(lèi)似。 例如，三個(gè)交叉點(diǎn)時(shí)的交叉操作示例：(5) 說(shuō)明： 一般不大使用多

40、點(diǎn)交叉算子，因?yàn)樗锌赡芷茐囊恍┖玫哪Ｊ健Ｊ聦?shí)上， 隨著交叉點(diǎn)數(shù)的增多，個(gè)體的結(jié)構(gòu)被破壞的可能性也逐漸增大。均勻交叉 ( Uniform Crossover ) (1) 均勻交叉：指兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上的基因都以相同的交叉概率進(jìn) 行交換，從而形成兩個(gè)新的個(gè)體。均勻交叉實(shí)際上可歸屬于多點(diǎn) 交叉的范圍。 (2) 操作過(guò)程： . 隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼串長(zhǎng)度等長(zhǎng)的屏蔽字 W = w1 w2 wi wl , 其中l(wèi)為個(gè)體編碼串長(zhǎng)度。 . 由下述規(guī)則從A、B兩個(gè)父代個(gè)體中產(chǎn)生出兩個(gè)新的子代個(gè)體 A 、B : 若 wi = 0，則A 在第i個(gè)基因座上的基因值繼承A的對(duì)應(yīng)基因值，B 在第i個(gè) 基因座

41、上的基因值繼承B的對(duì)應(yīng)基因值； 若 wil，則A 在第i個(gè)基因座上的基因值繼承B的對(duì)應(yīng)基因值，B 在第i個(gè) 基因座上的基因值繼承A的對(duì)應(yīng)基因值。 例如，均勻交叉操作的示例如下:算術(shù)交叉 ( Arithmetic Crossover ) (1) 算術(shù)交叉：由兩個(gè)個(gè)體的線(xiàn)性組合而產(chǎn)生出兩個(gè)新的個(gè)體。 (2) 進(jìn)行算術(shù)交叉的條件：為了能夠進(jìn)行線(xiàn)性組合運(yùn)算，算術(shù)交叉的操作對(duì)象一 般是由浮點(diǎn)數(shù)編碼所表示的個(gè)體。 (3) 算術(shù)交叉產(chǎn)生的新個(gè)體： 式中： x 為個(gè)體； 為一參數(shù)，它可以是一個(gè)常數(shù)，此時(shí)所進(jìn)行的交叉運(yùn)算稱(chēng)為均勻 算術(shù)交叉； 它也可以是一個(gè)由進(jìn)化代數(shù)所決定的變量，此時(shí)所進(jìn) 行的交叉運(yùn)算稱(chēng)為非均勻

42、算術(shù)交叉。 (4) 算術(shù)交叉的主要操作過(guò)程 . 確定兩個(gè)個(gè)體進(jìn)行線(xiàn)性組合時(shí)的系數(shù)。 . 依據(jù)上式生成兩個(gè)新的個(gè)體。7.3.5 變異算子 (1) 從遺傳運(yùn)算過(guò)程中產(chǎn)生新個(gè)體的能力方面來(lái)說(shuō): 交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法，它決定了遺傳算法的全局搜索能力； 而變異運(yùn)算只是產(chǎn)生新個(gè)體的輔助方法，但它也是必不可少的一個(gè)運(yùn)算步驟， 因?yàn)樗鼪Q定了遺傳算法的局部搜索能力。 交叉算子與變異算子的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜 索，從而使得遺傳算法能夠以良好的搜索性能完成最優(yōu)化問(wèn)題的尋優(yōu)過(guò)程。 (2) 在遺傳算法中使用變異算子主要有以下兩個(gè)目的： (1) 改善遺傳算法的局部搜索能力； (2) 維

43、持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。 (3) 變異算子的設(shè)計(jì)包括如下兩方面的內(nèi)容： 如何確定變異點(diǎn)的位置? 如何進(jìn)行基因值替換? 下面介紹其中較常用的幾種變異操作方法，它們適合于二進(jìn)制編碼的個(gè)體和 浮點(diǎn)數(shù)編碼的個(gè)體?；疚蛔儺?Simple Mutation)均勻變異(Uniform Mutation) (1) 均勻變異操作 指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來(lái)替換個(gè)體 編碼串中各個(gè)基因座上的原有基因值。 (2) 均勻變異的具體操作過(guò)程 . 依次指定個(gè)體編碼串中的每個(gè)基因座為變異點(diǎn)。 . 對(duì)每一個(gè)變異點(diǎn)，以變異概率pm從對(duì)應(yīng)基因的取值范圍內(nèi)取一隨機(jī)數(shù)來(lái)替代 原有基因值。 (

44、3) 舉例 假設(shè)有一個(gè)體為X=x1x2xkxn , 若xk為變異點(diǎn)，其取值范圍為Ukmin,Ukmax, 在該點(diǎn)對(duì)個(gè)體X進(jìn)行均勻變異操作后，可得到一個(gè)新的個(gè)體X=x1x2xkxn, 其中變異點(diǎn)的新基因值是： xk = Ukmin + r (Ukmax Ukmin ) 式中，r 為0, 1 范圍內(nèi)符合均勻概率分布的一個(gè)隨機(jī)數(shù)。 (4) 適用范圍 均勻變異操作持別適合應(yīng)用于遺傳算法的初期運(yùn)行階段，它使得搜索點(diǎn)可以在整 個(gè)搜索空間內(nèi)自由地移動(dòng)，從而可以增加群體的多樣性，使算法處理更多的模式。邊界變異(Boundary mutation) (1) 邊界變異 均勻變異操作的一個(gè)變形算法。在進(jìn)行邊界變異操作時(shí)，隨