第八章 遺傳算法

1第1頁(yè)，共54頁(yè)，2023年，2月20日，星期三

GA的基本思想來(lái)源于Darwin的進(jìn)化論和Mendel的遺傳學(xué)說(shuō)。Darwin的進(jìn)化論認(rèn)為每一物種在不斷的發(fā)展過(guò)程中都是越來(lái)越適應(yīng)環(huán)境。物種的每個(gè)個(gè)體的基本特征被后代所繼承，但后代又不完全同于父代，這些新的變化，若適應(yīng)環(huán)境，則被保留下來(lái)。在某一環(huán)境中也是那些更能適應(yīng)環(huán)境的個(gè)體特征能被保留下來(lái)，這就是適者生存的原理。遺傳算法的由來(lái)2第2頁(yè)，共54頁(yè)，2023年，2月20日，星期三達(dá)爾文進(jìn)化論3第3頁(yè)，共54頁(yè)，2023年，2月20日，星期三同樣的，人類也是一代比一代聰明，可以說(shuō)人類近百年創(chuàng)造的文明比人類前面幾千年創(chuàng)造的文明還要多。4第4頁(yè)，共54頁(yè)，2023年，2月20日，星期三因此：我們得到的結(jié)論是：

生物一代比一代優(yōu)生物雖然一代比一代優(yōu)，但并不是說(shuō)后一代與前一代沒(méi)有任何的關(guān)系，后一代或多或少總與前一代有些相同，也有一些不同。生物的后一代總是或多或少的繼承了前一代的一些特性，這就叫遺傳。而后一代又不完全像前一代，這叫變異。生物在進(jìn)化的過(guò)程中既有遺傳，又有變異，生物就是在這樣的遺傳、變異的作用那個(gè)下，一代一代的繁衍下去，而且得到的是一代比一代優(yōu)。5第5頁(yè)，共54頁(yè)，2023年，2月20日，星期三8.1遺傳算法的基本概念

1.個(gè)體與種群

●個(gè)體就是模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象（一般就是問(wèn)題的解）的一種稱呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。

●

種群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集。6第6頁(yè)，共54頁(yè)，2023年，2月20日，星期三

2.適應(yīng)度與適應(yīng)度函數(shù)

●

適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度,而對(duì)問(wèn)題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。

●適應(yīng)度函數(shù)(fitnessfunction)就是問(wèn)題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。

7第7頁(yè)，共54頁(yè)，2023年，2月20日，星期三3.染色體與基因

染色體（chromosome）就是問(wèn)題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個(gè)體染色體9

----

1001染色體長(zhǎng)度l=4（2，5，6）----010101110l=38第8頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法基本概念和術(shù)語(yǔ)進(jìn)化（evolution）生物在其延續(xù)生存的過(guò)程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化。生物的進(jìn)化是以種群的形式進(jìn)行的。9第9頁(yè)，共54頁(yè)，2023年，2月20日，星期三4.遺傳操作亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作:

●

選擇-復(fù)制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

10第10頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法基本概念和術(shù)語(yǔ)選擇（selection）按照一定概率隨機(jī)地選擇兩對(duì)個(gè)體進(jìn)行繁殖(即生成后繼狀態(tài))

遺傳算法在很大程度上是一種偶然性現(xiàn)象，隨機(jī)過(guò)程在其中起重要作用。一般而言，選擇的過(guò)程是一種基于適應(yīng)度的優(yōu)勝劣汰的過(guò)程。11第11頁(yè)，共54頁(yè)，2023年，2月20日，星期三復(fù)制(又稱繁殖)是從一個(gè)舊種群(oldpopulation)中選擇生命力強(qiáng)的個(gè)體位串(或稱字符串)產(chǎn)生新種群的過(guò)程?；蛘哒f(shuō)，復(fù)制是個(gè)體位串根據(jù)其目標(biāo)函數(shù)(即適應(yīng)度函數(shù))拷貝自己的過(guò)程。根據(jù)位串的適應(yīng)度值拷貝位串意味著，具有較高適應(yīng)度值的位串更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)后代。顯然，這個(gè)操作是模仿自然選擇現(xiàn)象，將達(dá)爾文的適者生存理論應(yīng)用于位串的復(fù)制，適應(yīng)度值是該位串被復(fù)制或被淘汰的決定因素。8.1遺傳算法基本原理12第12頁(yè)，共54頁(yè)，2023年，2月20日，星期三

選擇-復(fù)制通常做法是：對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xi∈S的選擇概率P(xi)所決定的選中機(jī)會(huì),分N次從S中隨機(jī)選定N個(gè)染色體,并進(jìn)行復(fù)制。

這里的選擇概率P(xi)的計(jì)算公式為13第13頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法基本概念和術(shù)語(yǔ)交叉（crossover）

有性生殖生物在繁殖下一代時(shí)，兩個(gè)同源染色體通過(guò)交叉而重組，亦即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。這個(gè)過(guò)程又稱基因重組（recombination），俗稱“雜交”。14第14頁(yè)，共54頁(yè)，2023年，2月20日，星期三

交叉就是互換兩個(gè)染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

例如,設(shè)染色體s1=01001011,s2=10010101,

交換其后4位基因,即15第15頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法基本概念和術(shù)語(yǔ)變異（mutation）

在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀。16第16頁(yè)，共54頁(yè)，2023年，2月20日，星期三變異就是改變?nèi)旧w某個(gè)(些)位上的基因。（0變?yōu)?或1變?yōu)?）例如,設(shè)染色體s=11001101將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。其中變異的位置是隨機(jī)的。17第17頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳學(xué)相關(guān)概念遺傳學(xué)遺傳算法數(shù)學(xué)1個(gè)體要處理的基本對(duì)象、結(jié)構(gòu)也就是可行解2群體個(gè)體的集合被選定的一組可行解3染色體個(gè)體的表現(xiàn)形式可行解的編碼4基因染色體中的元素編碼中的元素5基因位某一基因在染色體中的位置元素在編碼中的位置6適應(yīng)值個(gè)體對(duì)于環(huán)境的適應(yīng)程度，或在環(huán)境壓力下的生存能力可行解所對(duì)應(yīng)的適應(yīng)函數(shù)值7種群被選定的一組染色體或個(gè)體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作保留或復(fù)制適應(yīng)值大的可行解，去掉小的可行解18第18頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳學(xué)相關(guān)概念遺傳學(xué)遺傳算法數(shù)學(xué)9交叉一組染色體上對(duì)應(yīng)基因段的交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對(duì)應(yīng)基因段交換的概率（可能性大?。╅]區(qū)間[0,1]上的一個(gè)值，一般為0.65~0.9011變異染色體水平上基因變化編碼的某些元素被改變12變異概率染色體上基因變化的概率（可能性大?。╅_(kāi)區(qū)間(0,1)內(nèi)的一個(gè)值,一般為0.001~0.0113進(jìn)化、適者生存?zhèn)€體進(jìn)行優(yōu)勝劣汰的進(jìn)化，一代又一代地優(yōu)化目標(biāo)函數(shù)取到最大值，最優(yōu)的可行解19第19頁(yè)，共54頁(yè)，2023年，2月20日，星期三函數(shù)極值的求解問(wèn)題由《數(shù)學(xué)分析》可知，一個(gè)在閉區(qū)間[a,b]上連續(xù)的函數(shù)必存在最大最小值，而且最大最小值可以通過(guò)以下方式得到：求出y=f（x）這個(gè)函數(shù)在[a,b]上所有的導(dǎo)數(shù)為0的點(diǎn)、不可導(dǎo)點(diǎn)、區(qū)間的端點(diǎn)。計(jì)算所有以上點(diǎn)的函數(shù)值，進(jìn)行比較，則最大的必定是最大值點(diǎn)、最小的必定是最小值點(diǎn)。對(duì)于導(dǎo)數(shù)為0的點(diǎn)，還可以通過(guò)二階導(dǎo)數(shù)來(lái)判斷是極小還是極大值。20第20頁(yè)，共54頁(yè)，2023年，2月20日，星期三求函數(shù)的極值很顯然：利用導(dǎo)數(shù)求函數(shù)的極值只能針對(duì)那些簡(jiǎn)單的函數(shù)才可以那樣做，如果函數(shù)比較復(fù)雜，則無(wú)法利用求導(dǎo)數(shù)的方法求函數(shù)的極值。求導(dǎo)數(shù)可能比較困難；即使求出導(dǎo)數(shù)，求導(dǎo)數(shù)為0的點(diǎn)也相當(dāng)?shù)睦щy。是否不需要利用函數(shù)的導(dǎo)數(shù)，也可以求函數(shù)的極值？？？關(guān)于不需要利用導(dǎo)數(shù)就可以直接求函數(shù)的極值的方法，現(xiàn)在有幾種比較好的算法，遺傳算法就是其中的一種，它不需要利用導(dǎo)數(shù)，只要有函數(shù)的表達(dá)式就可以求函數(shù)的極值。21第21頁(yè)，共54頁(yè)，2023年，2月20日，星期三我們得到的結(jié)論是：

生物一代比一代優(yōu)目的：模仿生物遺傳的方式設(shè)計(jì)一個(gè)求解函數(shù)極值的算法。例如：求y=x2的最小值任取一些值25-48-1012稱為第一代，其實(shí)就是自變量x的任意一些值。它們的函數(shù)值分別為4251664100144.22第22頁(yè)，共54頁(yè)，2023年，2月20日，星期三生物有染色體，根據(jù)染色體進(jìn)行遺傳與變異，從而得到下一代。人為的構(gòu)造這些染色體，用5位二進(jìn)制表示，第一位表示正負(fù)號(hào)，0表示正、1表示負(fù)。

25-48-1012000100010110100010001101001100

遺傳（雜交）00001001101010001000110000111016-48-81623第23頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳（雜交）000010011010100010001100001110變異得到第二代，產(chǎn)生變異的概率很小，一般變異的概率8%，即每一位的0或1都有8%的可能編碼1或者0第二代：00001001001010001000110000111014-48-816對(duì)應(yīng)的函數(shù)值

116166464169第二代比第一代好24第24頁(yè)，共54頁(yè)，2023年，2月20日，星期三第二代：000010010010100010001100001110

遺傳（雜交）000000010110100010001101001100

變異第三代：00000001011010001010110100110005-410-1012就已經(jīng)得到了函數(shù)的最小值點(diǎn)x=0，結(jié)束。25第25頁(yè)，共54頁(yè)，2023年，2月20日，星期三以上就是遺傳算法求解最優(yōu)問(wèn)題的簡(jiǎn)單設(shè)計(jì)，是模仿生物的遺傳機(jī)制而設(shè)計(jì)的算法，是最基本形式的遺傳算法。遺傳算法的不同形式：（對(duì)基本遺傳做出一些改動(dòng)）由于遺傳算法是模擬生物的遺傳與變異機(jī)制而設(shè)計(jì)的，而生物的遺傳與變異是通過(guò)染色體來(lái)進(jìn)行，所以遺傳算法必須編碼，因此，不同的編碼機(jī)制就得到不同形式的遺傳算法，從而，不同的遺傳算法的第一個(gè)區(qū)別就是編碼不同。26第26頁(yè)，共54頁(yè)，2023年，2月20日，星期三第一：編碼不同得到的遺傳算法就不一樣。例如：上面這個(gè)例子是用5位編碼，其實(shí)，我們也可以采用6位編碼、也可以采用7位或100位編碼都可以。習(xí)題：采用6位編碼采用不同的編碼方法就得到不同的遺傳算法。問(wèn)題：采用什么編碼好呢？這個(gè)問(wèn)題到現(xiàn)在為止還沒(méi)有答案，很多對(duì)遺傳算法進(jìn)行研究的人，就是對(duì)各種各樣的編碼方法進(jìn)行研究，看哪種編碼更好。27第27頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法是模擬生物的遺傳與變異機(jī)制而設(shè)計(jì)的，遺傳算法的兩個(gè)基本運(yùn)算就是遺傳雜交、變異。因此不同的選擇遺傳雜交方式與不同的變異方式就得到不同的遺傳算法。第二：不同的雜交方法得到不同的遺傳算法。例如：上面例子是每個(gè)個(gè)體都參與雜交。其實(shí)，我們知道自然界中的法則是優(yōu)勝劣汰。并不是每個(gè)個(gè)體都能找到伴侶。只有那些好的，才能找到伴侶，同樣的，這里也可以這樣做。先看哪些個(gè)體是好的，哪些個(gè)體是差的，讓好的個(gè)體多雜交，把那些差的直接淘汰。

哪些個(gè)體是好的，哪些個(gè)體是差的，怎么區(qū)分呢？28第28頁(yè)，共54頁(yè)，2023年，2月20日，星期三

求函數(shù)的最小值？25-48-1012000100010110100010001101001100函數(shù)值分別為4251664100144因?yàn)槭且蠛瘮?shù)的最小值，所以顯然函數(shù)值越小越好，函數(shù)值越大越不好。所以最好的點(diǎn)是2，最差的點(diǎn)是12，因此，可以直接淘汰12，而讓2這個(gè)點(diǎn)多雜交一次，因此雜交這一步可以這樣做：

25-48-10200010001011010001000110100001029第29頁(yè)，共54頁(yè)，2023年，2月20日，星期三上面只是給出了遺傳算法的一種基本的形式，而不同的編碼方法與不同的雜交策略可以變形出各種各樣的遺傳算法。同樣，還有不同的變異方式也得到不同的算法。30第30頁(yè)，共54頁(yè)，2023年，2月20日，星期三在進(jìn)行遺傳算法操作時(shí)：上面第一種方法是兩兩交叉遺傳，而第二種做法是先淘汰最差，用一個(gè)最好的去代替最差，再進(jìn)行交叉遺傳，也可以刪除兩個(gè)最差，用兩個(gè)好一點(diǎn)的取代。

25-48-1012000100010110100010001101001100淘汰一個(gè)最差的

25-48-102000100010110100010001101000010淘汰兩個(gè)最差的

25-482200010001011010001000000100001031第31頁(yè)，共54頁(yè)，2023年，2月20日，星期三到底淘汰幾個(gè)最差的？？？又用哪些好的取代差的，這些是可以有不同的數(shù)目的，這些數(shù)就叫控制參數(shù)。選擇不同的控制參數(shù)（控制策略），算法就不一樣。例如不刪除最差，每個(gè)都一樣的交叉遺傳，與刪除最差，用好的代替差的，算法不一樣。還有一個(gè)控制參數(shù)就是在進(jìn)行變異操作時(shí)，選多少個(gè)進(jìn)行變異，有選8%的個(gè)體進(jìn)行變異，也有選5%的個(gè)數(shù)進(jìn)行變異。這個(gè)百分?jǐn)?shù)通常稱為變異率。32第32頁(yè)，共54頁(yè)，2023年，2月20日，星期三可以把遺傳算法的基本形式描述為：Begin生成初始種群，選擇適當(dāng)?shù)木幋a方式；通過(guò)計(jì)算群體中各個(gè)體的適應(yīng)度對(duì)群體進(jìn)行評(píng)價(jià)；While未達(dá)到要求的目標(biāo)dobegina.選擇繁殖下一代群體的各個(gè)體

b.執(zhí)行雜交操作

c.執(zhí)行變異操作

d.對(duì)群體進(jìn)行評(píng)價(jià)

endend33第33頁(yè)，共54頁(yè)，2023年，2月20日，星期三例1.設(shè)f(x)=-x2+2x+0.5，求max

f(x),x[-1,2]。遺傳算法的實(shí)際應(yīng)用我們將通過(guò)這個(gè)簡(jiǎn)單的求最值問(wèn)題來(lái)詳細(xì)給出遺傳算法的整個(gè)過(guò)程。（1）編碼和產(chǎn)生初始群體首先需要確定編碼的策略，也就是說(shuō)如何把[-1,2]

區(qū)間內(nèi)的數(shù)用計(jì)算機(jī)語(yǔ)言表示出來(lái)。編碼就是從表現(xiàn)型到基因型的映射，編碼時(shí)要注意以下三個(gè)原則：完備性：?jiǎn)栴}空間中所有點(diǎn)（潛在解）都能成為GA編碼空間中的點(diǎn)（染色體位串）的表現(xiàn)型；健全性：GA編碼空間中的染色體位串必須對(duì)應(yīng)問(wèn)題空間中的某一潛在解；非冗余性：染色體和潛在解必須一一對(duì)應(yīng)．34第34頁(yè)，共54頁(yè)，2023年，2月20日，星期三編碼我們采用二進(jìn)制形式來(lái)解決編碼問(wèn)題，即將某個(gè)變量值代表的個(gè)體表示為一個(gè){0,1}二進(jìn)制串。串的長(zhǎng)度取決于求解的精度，例如假設(shè)求解精度為保留六位小數(shù)，由于區(qū)間[-1,2]的長(zhǎng)度為3，則必須將該區(qū)間分為3106

等分。因?yàn)?21<3106<222，所以編碼所用的二進(jìn)制串至少需要22位。二進(jìn)制串（b21b20b19…b1b0）與[a,b]

內(nèi)實(shí)數(shù)的一一映射：二進(jìn)制串十進(jìn)制數(shù)[a,b]

內(nèi)實(shí)數(shù)b21b20b19…b1b035第35頁(yè)，共54頁(yè)，2023年，2月20日，星期三編碼轉(zhuǎn)化到[-1,2]

內(nèi)的實(shí)數(shù)為：例.二進(jìn)制串a(chǎn)=<1000101110110101000111>

其對(duì)應(yīng)的十進(jìn)制數(shù)為：36第36頁(yè)，共54頁(yè)，2023年，2月20日，星期三產(chǎn)生初始群體隨機(jī)的產(chǎn)生一個(gè)初始群體。pop1={<1101011101001100011110>，%a1<1000011001010001000010>，%a2<0001100111010110000000>，%a3<0110101001101110010101>}%a4這里假設(shè)初始群體的個(gè)體數(shù)為4。轉(zhuǎn)化成[-1,2]

之間的十進(jìn)制數(shù)即為：下面就需要解決每個(gè)染色體個(gè)體的適應(yīng)值pop1={

1.523032,0.574022,-0.697235,0.247238}37第37頁(yè)，共54頁(yè)，2023年，2月20日，星期三適應(yīng)函數(shù)（2）定義適應(yīng)函數(shù)和適應(yīng)值由于目標(biāo)函數(shù)f(x)

在[-1,2]

內(nèi)的值有正有負(fù)，所以必須通過(guò)建立適應(yīng)函數(shù)與目標(biāo)函數(shù)的映射關(guān)系，保證映射后的適應(yīng)值非負(fù)，而且目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)于適應(yīng)值增大的方向，也為以后計(jì)算各個(gè)體的入選概率打下基礎(chǔ)。定義適應(yīng)函數(shù)：為了便于計(jì)算，這里的Fmin

采用了一個(gè)特定的輸入值例：如果取Fmin=-1，則f(x)=1對(duì)應(yīng)的適應(yīng)值為g(x)=238第38頁(yè)，共54頁(yè)，2023年，2月20日，星期三適應(yīng)函數(shù)和適應(yīng)值上述隨機(jī)產(chǎn)生的初始群體，取Fmin=-1，則它們的目標(biāo)函數(shù)值和適應(yīng)值分別為：f(pop1)={

1.226437,1.318543,-1.380607,0.933350}g(pop1)={

2.226437,2.318543,0,1.933350}39第39頁(yè)，共54頁(yè)，2023年，2月20日，星期三選擇標(biāo)準(zhǔn)（3）確定選擇標(biāo)準(zhǔn)用適應(yīng)值比例來(lái)作為入選概率。設(shè)給定的規(guī)模為n

的群體pop={a1,a2,...,an

}，個(gè)體ai

的適應(yīng)值為g(ai)，則其入選概率為上述隨機(jī)產(chǎn)生的初始群體，它們的入選概率分別為：p(pop1)=g(pop1)/sum(g(pop1))={0.343675,0.357892,0,0.298433}40第40頁(yè)，共54頁(yè)，2023年，2月20日，星期三產(chǎn)生種群（4）產(chǎn)生種群將入選概率大的個(gè)體選入種群，淘汰概率小的個(gè)體，并用概率最大的個(gè)體補(bǔ)入種群，得到與原群體大小同樣的種群。newpop1={<1101011101001100011110>，%a1<1000011001010001000010>，%a2<1000011001010001000010>，%a2<0110101001101110010101>}%a4在上述隨機(jī)產(chǎn)生的初始群體中，淘汰掉a3，再加入a2，得到新的種群：41第41頁(yè)，共54頁(yè)，2023年，2月20日，星期三交叉（5）交叉交叉也就是將一組染色體上對(duì)應(yīng)的基因段交換得到新的染色體，然后得到新的染色體組，組成新的群體。將前面得到的newpop1

的四個(gè)個(gè)體兩兩配對(duì)，重復(fù)的不配對(duì)，進(jìn)行交叉（可以在任一位進(jìn)行交叉）：<1101011101001100011110>

<1101011101010001000010>

<1000011001010001000010>

<1000011001001100011110><1000011001010001000010>

<1000011001010010010101><0110101001101110010101>

<0110101001101101000010>新的群體jchpop142第42頁(yè)，共54頁(yè)，2023年，2月20日，星期三變異（6）變異變異就是通過(guò)一個(gè)小概率改變?nèi)旧w位串上的某個(gè)基因?，F(xiàn)把jchpop1

中第3個(gè)個(gè)體中的第9位改變，就產(chǎn)生了變異，得到了新的群體pop2

：pop2={

<1101011101010001000010>,<1000011001001100011110>,<1000011011010010010101>,<0110101001101101000010>}然后重復(fù)上述的選擇、交叉、變異，直到滿足終止條件為止43第43頁(yè)，共54頁(yè)，2023年，2月20日，星期三終止條件（7）終止條件遺傳算法的終止條件有兩類常見(jiàn)條件：采用設(shè)定最大（遺傳）代數(shù)的方法，一般可設(shè)定為50代，此時(shí)就可能得出最優(yōu)解．此種方法簡(jiǎn)單易行，但可能不是很精確（Matlab程序參見(jiàn)附錄1）根據(jù)個(gè)體的差異來(lái)判斷，通過(guò)計(jì)算種群中基因多樣性測(cè)度，即所有基因位相似程度來(lái)進(jìn)行控制44第44頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法的收斂性遺傳算法通過(guò)對(duì)這些操作的適當(dāng)設(shè)計(jì)和運(yùn)行，可以實(shí)現(xiàn)兼顧全局搜索和局部搜索的所謂均衡搜索均衡搜索的具體實(shí)現(xiàn)圖示45第45頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法的收斂性遺傳算法雖然可以實(shí)現(xiàn)均衡的搜索，并且在許多復(fù)雜問(wèn)題的求解中往往能得到滿意的結(jié)果，但是該算法的全局優(yōu)化收斂性的理論分析尚待解決。目前普遍認(rèn)為，標(biāo)準(zhǔn)遺傳算法并不保證全局最優(yōu)收斂。但是，在一定的約束條件下，遺傳算法可以實(shí)現(xiàn)這一點(diǎn)。定理1

如果變異概率為，交叉概率為，同時(shí)采用比例選擇法(按個(gè)體適應(yīng)度占群體適應(yīng)度的比例進(jìn)行復(fù)制)，則標(biāo)準(zhǔn)遺傳算法的變換矩陣P

是基本的。46第46頁(yè)，共54頁(yè)，2023年，2月20日，星期三遺傳算法的收斂性定理2

標(biāo)準(zhǔn)遺傳算法（參數(shù)如定理1）不能收斂至全局最優(yōu)解。標(biāo)準(zhǔn)遺傳算法是不能收斂至全局最最優(yōu)解，對(duì)標(biāo)準(zhǔn)遺傳算法作一些改進(jìn)，就能夠保證其收斂性。

最佳個(gè)體保存方法（elitistmodel）的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中。設(shè)時(shí)刻t

(第t

代)時(shí)，群體中a*(t)為最佳個(gè)體，并設(shè)A(t+1)為新一代群體，若A(t+1)中不存在a*(t)，則把a(bǔ)*(t)作為A(t+1)中的第n+1

個(gè)個(gè)體(其中，n為群體大小)47第47頁(yè)，共54頁(yè)，2023年，2月20日，星期三最佳個(gè)體保存方法該方法的優(yōu)點(diǎn)：確保進(jìn)化過(guò)程中某一代的最優(yōu)解不被交叉和變異操作所破壞。