人工智能遺傳算法PPT72張課件

《人工智能遺傳算法PPT72張課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能遺傳算法PPT72張課件（73頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、計(jì)算智能是信息科學(xué)和生命科學(xué)相互交叉的前沿領(lǐng)域,是現(xiàn)代科學(xué)技術(shù)發(fā)展的一個(gè)重要體現(xiàn)。計(jì)算智能涉及神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進(jìn)化計(jì)算和人工生命等領(lǐng)域，它的研究和發(fā)展反映了當(dāng)代科學(xué)技術(shù)多學(xué)科交叉與集成的重要發(fā)展趨勢(shì)。貝茲德克于1994年提出了一種A，B，C智能模型，從而表示ABC與神經(jīng)網(wǎng)絡(luò)、模式識(shí)別和智能之間的關(guān)系：A：Artificial,表示人工的、符號(hào)的（非生物的）B：Biological,表示生物的C：Computational,表示計(jì)算的計(jì)算智能是一種智力方式的底層認(rèn)知，它與人工智能的區(qū)別是認(rèn)知層次從中層下降到底層而已。中層系統(tǒng)含有知識(shí)，底層系統(tǒng)沒有知識(shí)。關(guān)于A，B，C智能計(jì)算智能與人工智能的區(qū)

2、別與聯(lián)系NN Neural Network 神經(jīng)網(wǎng)絡(luò)PR Pattern Recognition 模式識(shí)別計(jì)算智能系統(tǒng)與人工智能系統(tǒng)當(dāng)一個(gè)系統(tǒng)只涉及數(shù)值（底層）數(shù)據(jù)，含有模式識(shí)別部分，不應(yīng)用于人工智能意義上的知識(shí)，而且系統(tǒng)能夠呈現(xiàn)出：（1）計(jì)算適應(yīng)性（2）計(jì)算容錯(cuò)性（3）接近人的計(jì)算速度（4）計(jì)算誤差率與人接近則該系統(tǒng)就是計(jì)算智能系統(tǒng)。當(dāng)一個(gè)智能計(jì)算系統(tǒng)以非數(shù)值方式并加上知識(shí)，即為人工智能系統(tǒng)。神經(jīng)計(jì)算（Neural Computation）神經(jīng)計(jì)算研究的進(jìn)展1943年麥卡洛奇和皮茨提出神經(jīng)網(wǎng)絡(luò)模型的概念（稱為MP模型）20世紀(jì)60年代威德羅和霍夫提出了自適應(yīng)線性元件。60年代末到80年代初初

3、與研究的低潮期80年代后又大發(fā)展遺傳算法 遺遺傳傳算算法法簡(jiǎn)簡(jiǎn)稱稱GAGA（Genetic Genetic AlgorithmsAlgorithms）是是19751975年年由由美美國(guó)國(guó)Michigan(Michigan(密歇根州)大大學(xué)學(xué)的的J.J.HollandHolland教教授授提提出出的的模模擬擬自自然然界界生生物物遺遺傳傳學(xué)學(xué)（孟孟德德爾爾）和和生生物物進(jìn)進(jìn)化化論論（達(dá)達(dá)爾爾文文）通通過過人人工工方方式式所所構(gòu)構(gòu)造造的的一一類類并并行行隨隨機(jī)機(jī)搜搜索索最最優(yōu)優(yōu)化化方方法法，是是對(duì)對(duì)生生物物進(jìn)進(jìn)化化過過程程進(jìn)進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的重要形式。行的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的重要

4、形式。1 1、遺傳算法、遺傳算法 在生物系統(tǒng)中，進(jìn)化被認(rèn)為是一種成功的自適應(yīng)方法，具有很好的健壯性。其主要特點(diǎn)是(1)直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；(2)具有內(nèi)在的隱含并行性和更好的全局尋優(yōu)能力；(3)采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法已被廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)計(jì)算智能中的關(guān)鍵技術(shù)之一。遺遺傳傳算算法法是是以以達(dá)達(dá)爾爾文文的的自自然然選選擇擇學(xué)學(xué)說說為為基基礎(chǔ)礎(chǔ)發(fā)發(fā)展展起起來來的的。自自然然選擇學(xué)說包括以下三個(gè)方面：選擇學(xué)說包括以下三個(gè)方面：1

5、 1、遺傳算法、遺傳算法（1 1）遺遺傳傳：這這是是生生物物的的普普遍遍特特征征，親親代代把把生生物物信信息息交交給給子子代代，子子代代總總是是和和親親代代具具有有相相同同或或相相似似的的性性狀狀。生生物物有有了了這這個(gè)個(gè)特特征征，物物種種才才能穩(wěn)定存在。能穩(wěn)定存在。（2 2）變變異異：親親代代和和子子代代之之間間以以及及子子代代的的不不同同個(gè)個(gè)體體之之間間的的差差異異，稱稱為為變變異異。變變異異是是隨隨機(jī)機(jī)發(fā)發(fā)生生的的，變變異異的的選選擇擇和和積積累累是是生生命命多多樣樣性性的的根根源。源。（3 3）生生存存斗斗爭(zhēng)爭(zhēng)和和適適者者生生存存：具具有有適適應(yīng)應(yīng)性性變變異異的的個(gè)個(gè)體體被被保保留留下

6、下來來，不不具具有有適適應(yīng)應(yīng)性性變變異異的的個(gè)個(gè)體體被被淘淘汰汰，通通過過一一代代代代的的生生存存環(huán)環(huán)境境的的選選擇擇作作用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。遺遺傳傳算算法法將將“優(yōu)優(yōu)勝勝劣劣汰汰，適適者者生生存存”的的生生物物進(jìn)進(jìn)化化原原理理引引入入優(yōu)優(yōu)化化參參數(shù)數(shù)形形成成的的編編碼碼串串群群體體中中，按按所所選選擇擇的的適適應(yīng)應(yīng)度度函函數(shù)數(shù)并并通通過過遺遺傳傳中中的的復(fù)復(fù)制制、交交叉叉及及變變異異對(duì)對(duì)個(gè)個(gè)體體進(jìn)進(jìn)行行篩篩選選，適適應(yīng)應(yīng)度度高高的的個(gè)個(gè)體體被被保保留留下下來來，組組成成新新的的群群體體，新新的的群群體體既既繼繼承承了

7、了上上一一代代的的信信息息，又又優(yōu)優(yōu)于于上上一一代代。這這樣樣周周而而復(fù)復(fù)始始，群群體體中中個(gè)個(gè)體體適適應(yīng)應(yīng)度度不不斷斷提提高高，直直到到滿滿足足一一定定的的條條件件。遺遺傳傳算算法法的的算算法法簡(jiǎn)簡(jiǎn)單單，可可并并行行處處理理，并并能到全局最優(yōu)解。能到全局最優(yōu)解。如：愛斯基摩人，如：愛斯基摩人，非洲原始部落非洲原始部落2 2、遺傳算法的基本操作為：、遺傳算法的基本操作為：（1 1）復(fù)制（）復(fù)制（Reproduction OperatorReproduction Operator）復(fù)復(fù)制制是是從從一一個(gè)個(gè)舊舊種種群群中中選選擇擇生生命命力力強(qiáng)強(qiáng)的的個(gè)個(gè)體體位位串串產(chǎn)產(chǎn)生生新新種種群群的的過過程程

8、。具具有有高高適適應(yīng)應(yīng)度度的的位位串串更更有有可可能能在在下下一一代代中中產(chǎn)產(chǎn)生一個(gè)或多個(gè)子孫。生一個(gè)或多個(gè)子孫。復(fù)復(fù)制制操操作作可可以以通通過過隨隨機(jī)機(jī)方方法法來來實(shí)實(shí)現(xiàn)現(xiàn)。首首先先產(chǎn)產(chǎn)生生0101之之間間均均勻勻分分布布的的隨隨機(jī)機(jī)數(shù)數(shù)，若若某某串串的的復(fù)復(fù)制制概概率率為為40%40%，則則當(dāng)當(dāng)產(chǎn)產(chǎn)生生的隨機(jī)數(shù)在的隨機(jī)數(shù)在0.401.00.401.0之間時(shí)，該串被復(fù)制，否則被淘汰。之間時(shí)，該串被復(fù)制，否則被淘汰。（2 2）交叉（）交叉（Crossover OperatorCrossover Operator）復(fù)復(fù)制制操操作作能能從從舊舊種種群群中中選選擇擇出出優(yōu)優(yōu)秀秀者者，但但不不能能創(chuàng)創(chuàng)

9、造造新新的的染染色色體體。而而交交叉叉模模擬擬了了生生物物進(jìn)進(jìn)化化過過程程中中的的繁繁殖殖現(xiàn)現(xiàn)象象，通通過過兩兩個(gè)染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。個(gè)染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。交交叉叉的的過過程程為為：在在匹匹配配池池中中任任選選兩兩個(gè)個(gè)染染色色體體，隨隨機(jī)機(jī)選選擇擇一一點(diǎn)點(diǎn)或或多多點(diǎn)點(diǎn)交交換換點(diǎn)點(diǎn)位位置置；交交換換雙雙親親染染色色體體交交換換點(diǎn)點(diǎn)右右邊邊的的部部分分，即可得到兩個(gè)新的染色體數(shù)字串。即可得到兩個(gè)新的染色體數(shù)字串。交叉體現(xiàn)了自然界中信息交換的思想。交叉交叉體現(xiàn)了自然界中信息交換的思想。交叉有單點(diǎn)交叉、兩點(diǎn)交叉、還有一致交叉、順有單點(diǎn)交叉、兩點(diǎn)交叉、還有一致交叉、順

10、序交叉和周期交叉。單點(diǎn)交叉是最基本的方序交叉和周期交叉。單點(diǎn)交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點(diǎn)有一處，法，應(yīng)用較廣。它是指染色體切斷點(diǎn)有一處，例：例：（3 3）變異）變異(Mutation Operator)(Mutation Operator)變變異異運(yùn)運(yùn)算算用用來來模模擬擬生生物物在在自自然然的的遺遺傳傳環(huán)環(huán)境境中中由由于于各各種種偶偶然然因因素素引引起起的的基基因因突突變變，它它以以很很小小的的概概率率隨隨機(jī)機(jī)地地改改變變遺遺傳傳基基因因（表表示示染染色色體體的的符符號(hào)號(hào)串串的的某某一一位位）的的值值。在在染染色色體體以以二二進(jìn)進(jìn)制制編編碼碼的的系系統(tǒng)統(tǒng)中中，它它隨隨機(jī)機(jī)地

11、地將將染染色色體體的的某某一個(gè)基因由一個(gè)基因由1 1變?yōu)樽優(yōu)? 0，或由，或由0 0變?yōu)樽優(yōu)? 1。若若只只有有選選擇擇和和交交叉叉，而而沒沒有有變變異異，則則無無法法在在初初始始基基因因組組合合以以外外的的空空間間進(jìn)進(jìn)行行搜搜索索，使使進(jìn)進(jìn)化化過過程程在在早早期期就就陷陷入入局局部部解解而而進(jìn)進(jìn)入入終終止止過過程程，從從而而影影響響解解的的質(zhì)質(zhì)量量。為為了了在在盡盡可可能能大大的的空空間間中中獲獲得得質(zhì)質(zhì)量量較較高高的的優(yōu)優(yōu)化化解，必須采用變異操作。解，必須采用變異操作。17設(shè)自變量設(shè)自變量 x x 介于介于0 03131，求其二次函數(shù)的最大值，即：，求其二次函數(shù)的最大值，即：max f(x

12、)=x max f(x)=x2 2,x 0,31,x 0,313 3、遺傳算法示例、遺傳算法示例-f(x)=x-f(x)=x2 2 極大值問題極大值問題5001000 0 31 xf(x)當(dāng)然，利用簡(jiǎn)單的代數(shù)運(yùn)算，很容易求出該問題的解。現(xiàn)當(dāng)然，利用簡(jiǎn)單的代數(shù)運(yùn)算，很容易求出該問題的解。現(xiàn)在改用遺傳算法求解，遺傳算法通常包括下述內(nèi)容：在改用遺傳算法求解，遺傳算法通常包括下述內(nèi)容：18（1 1）編碼）編碼 遺傳算法首先要對(duì)實(shí)際問題進(jìn)行編碼，用字符串表達(dá)問題。這種字遺傳算法首先要對(duì)實(shí)際問題進(jìn)行編碼，用字符串表達(dá)問題。這種字符串相當(dāng)于遺傳學(xué)中的染色體。每一代所產(chǎn)生的字符串符串相當(dāng)于遺傳學(xué)中的染色體。每

13、一代所產(chǎn)生的字符串個(gè)體總和稱為群體個(gè)體總和稱為群體。為了實(shí)現(xiàn)的方便，通常字符串長(zhǎng)度固定，字符選為了實(shí)現(xiàn)的方便，通常字符串長(zhǎng)度固定，字符選0 0或或1 1。本例中，利用本例中，利用5 5位二進(jìn)制數(shù)表示位二進(jìn)制數(shù)表示x x值，采用隨機(jī)產(chǎn)生的方法，假設(shè)得值，采用隨機(jī)產(chǎn)生的方法，假設(shè)得出擁有四個(gè)個(gè)體的初始群體，即：出擁有四個(gè)個(gè)體的初始群體，即：0110101101，1100011000，0100001000，1001110011。x x值相值相應(yīng)為應(yīng)為1313，2424，8 8，1919。個(gè)體編號(hào)初始群體xi適應(yīng)度f(wàn)(xi)f(xi)/f(xi)f(xi)/fMp1234011011100001000

14、100111324819169576643610.140.490.060.310.581.970.221.231201總計(jì)f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412019（2）計(jì)算適應(yīng)度）計(jì)算適應(yīng)度 衡量字符串（染色體）好壞的指標(biāo)是衡量字符串（染色體）好壞的指標(biāo)是適應(yīng)度適應(yīng)度，它也就是遺傳算，它也就是遺傳算法的目標(biāo)函數(shù)。法的目標(biāo)函數(shù)。本例中適應(yīng)度比較簡(jiǎn)單，用本例中適應(yīng)度比較簡(jiǎn)單，用x2計(jì)算。計(jì)算。表中還列出了當(dāng)前適應(yīng)度的總和表中還列出了當(dāng)前適應(yīng)度的總和f(xi)及平均值及平均值f，即：，即：f(xi)=f(x1)

15、+f(x2)+f(x3)+f(x4)=1170 f=f(xi)/4=292.5(293)f(x1)/f=169/293=0.57679.個(gè)體編號(hào)初始群體xi適應(yīng)度f(wàn)(xi)f(xi)/f(xi)f(xi)/fMp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201總計(jì)f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412020（2）計(jì)算適應(yīng)度）計(jì)算適應(yīng)度 表中第表中第6列的列的 f(xi)/f 表示每個(gè)個(gè)體的表示每個(gè)個(gè)體的

16、相對(duì)適應(yīng)度相對(duì)適應(yīng)度，它反映了個(gè)，它反映了個(gè)體之間的相對(duì)優(yōu)劣性。如體之間的相對(duì)優(yōu)劣性。如2號(hào)個(gè)體的號(hào)個(gè)體的 f(xi)/f 值最高（值最高（1.97），為優(yōu)），為優(yōu)良個(gè)體，良個(gè)體，3號(hào)個(gè)體最低（號(hào)個(gè)體最低（0.22），為不良個(gè)體。），為不良個(gè)體。個(gè)體編號(hào)初始群體xi適應(yīng)度f(wàn)(xi)f(xi)/f(xi)f(xi)/fMp12345671234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201總計(jì)f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001

17、.970.22412021（3）復(fù)制）復(fù)制 為了將已有的群體變?yōu)橄乱淮后w，遺傳算法仿效為了將已有的群體變?yōu)橄乱淮后w，遺傳算法仿效進(jìn)化論中進(jìn)化論中“自然選擇、適者生存自然選擇、適者生存”的原則，從舊群體中的原則，從舊群體中選擇優(yōu)良個(gè)體進(jìn)行復(fù)制。選擇的依據(jù)是個(gè)體適應(yīng)度的大選擇優(yōu)良個(gè)體進(jìn)行復(fù)制。選擇的依據(jù)是個(gè)體適應(yīng)度的大小，適應(yīng)度大的個(gè)體接受復(fù)制，使之繁殖；適應(yīng)度小的小，適應(yīng)度大的個(gè)體接受復(fù)制，使之繁殖；適應(yīng)度小的個(gè)體則刪除掉，遭到淘汰。個(gè)體則刪除掉，遭到淘汰。22（3）復(fù)制）復(fù)制 在本例中，根據(jù)相對(duì)適應(yīng)度的大小對(duì)個(gè)體進(jìn)行取舍，在本例中，根據(jù)相對(duì)適應(yīng)度的大小對(duì)個(gè)體進(jìn)行取舍，2號(hào)個(gè)體號(hào)個(gè)體性能最優(yōu)

18、，予以復(fù)制繁殖。性能最優(yōu)，予以復(fù)制繁殖。3號(hào)個(gè)體性能最差，將它刪除，使之死號(hào)個(gè)體性能最差，將它刪除，使之死亡，表中的亡，表中的M表示傳遞給下一代的個(gè)體數(shù)目，其中表示傳遞給下一代的個(gè)體數(shù)目，其中2號(hào)個(gè)體占號(hào)個(gè)體占2個(gè)，個(gè)，3號(hào)個(gè)體為號(hào)個(gè)體為0，1號(hào)、號(hào)、4號(hào)個(gè)體保持為號(hào)個(gè)體保持為1個(gè)。個(gè)。這樣，就產(chǎn)生了下一代群體。這樣，就產(chǎn)生了下一代群體。個(gè)體編號(hào)初始群體xi適應(yīng)度f(wàn)(xi)f(xi)/f(xi)f(xi)/fMp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201總計(jì)f(xi)平均值f最大值

19、最小值1170293576641.000.250.490.064.001.001.970.22412023（3）復(fù)制）復(fù)制 從表中的第從表中的第4列可以看出，復(fù)制后產(chǎn)生的新一代群體的平均適應(yīng)列可以看出，復(fù)制后產(chǎn)生的新一代群體的平均適應(yīng)度明顯增加，由原來的度明顯增加，由原來的293增加到增加到421。造成平均適應(yīng)度增加的原因有。造成平均適應(yīng)度增加的原因有二：二：1）淘汰原來最差的個(gè)體。使最小適應(yīng)度由原來的）淘汰原來最差的個(gè)體。使最小適應(yīng)度由原來的64增加到增加到169。2）增加了優(yōu)良個(gè)體（）增加了優(yōu)良個(gè)體（2號(hào)）的個(gè)數(shù)，使適應(yīng)度累計(jì)值增加。號(hào)）的個(gè)數(shù)，使適應(yīng)度累計(jì)值增加。個(gè)體編號(hào)復(fù)制后群體xi復(fù)

20、制后適應(yīng)度f(wàn)(xi)交換對(duì)象交換位置交換后群體復(fù)制后適應(yīng)度f(wàn)(xi)1234（1）01101（2）11000（2）11000（4）10011132424191695765763612號(hào)1號(hào)4號(hào)3號(hào)443301100110011101110000144625729256總計(jì)平均值最大值最小值1682421576361175443972925624（4）交換）交換 通過復(fù)制產(chǎn)生的新群體，其性能得到改善，然通過復(fù)制產(chǎn)生的新群體，其性能得到改善，然而它不能產(chǎn)生新的個(gè)體。為了產(chǎn)生新的個(gè)體，遺傳而它不能產(chǎn)生新的個(gè)體。為了產(chǎn)生新的個(gè)體，遺傳算法仿照生物學(xué)中雜交的方法，對(duì)染色體（字符串）算法仿照生物學(xué)中雜交的

21、方法，對(duì)染色體（字符串）的某些部分進(jìn)行交叉換位。被交換的母體都選自經(jīng)的某些部分進(jìn)行交叉換位。被交換的母體都選自經(jīng)過復(fù)制產(chǎn)生的新一代個(gè)體（優(yōu)勝者）。過復(fù)制產(chǎn)生的新一代個(gè)體（優(yōu)勝者）。25（4）交換）交換 本例中，利用隨機(jī)配對(duì)的方法，決定本例中，利用隨機(jī)配對(duì)的方法，決定1號(hào)和號(hào)和2號(hào)個(gè)體、號(hào)個(gè)體、3號(hào)和號(hào)和4號(hào)個(gè)號(hào)個(gè)體分別交換，如表中第體分別交換，如表中第5列。再利用隨機(jī)定位的方法，確定這兩對(duì)母列。再利用隨機(jī)定位的方法，確定這兩對(duì)母體交叉換位的位置分別從字符長(zhǎng)度的第體交叉換位的位置分別從字符長(zhǎng)度的第4位及第位及第3位開始。如：位開始。如：3號(hào)、號(hào)、4號(hào)個(gè)體從字符長(zhǎng)度第號(hào)個(gè)體從字符長(zhǎng)度第3位開始交換

22、。交換開始的位置稱位開始交換。交換開始的位置稱交換點(diǎn)交換點(diǎn)。個(gè)體編號(hào)復(fù)制后群體xi復(fù)制后適應(yīng)度f(wàn)(xi)交換對(duì)象交換位置交換后群體復(fù)制后適應(yīng)度f(wàn)(xi)123401101110001100010011132424191695765763612號(hào)1號(hào)4號(hào)3號(hào)443301100110011101110000144625729256總計(jì)平均值最大值最小值168242157636117544397292561100010011110111000026（4）交換）交換 從表中可以看出，交換后出現(xiàn)優(yōu)異個(gè)體從表中可以看出，交換后出現(xiàn)優(yōu)異個(gè)體3號(hào)，其適應(yīng)度高達(dá)號(hào)，其適應(yīng)度高達(dá)729，大大高于交換前的最大值（大

23、大高于交換前的最大值（576）。與此同時(shí)，平均適應(yīng)度也從原來）。與此同時(shí)，平均適應(yīng)度也從原來的的421提高到提高到439，說明交換后的群體正朝優(yōu)良方向發(fā)展。，說明交換后的群體正朝優(yōu)良方向發(fā)展。個(gè)體編號(hào)復(fù)制后群體xi復(fù)制后適應(yīng)度f(wàn)(xi)交換對(duì)象交換位置交換后群體復(fù)制后適應(yīng)度f(wàn)(xi)123401101110001100010011132424191695765763612號(hào)1號(hào)4號(hào)3號(hào)443301100110011101110000144625729256總計(jì)平均值最大值最小值1682421576361175443972925627（5）突變）突變 遺傳算法模仿生物學(xué)中基因突變的方法，將個(gè)體字

24、符串某位符號(hào)遺傳算法模仿生物學(xué)中基因突變的方法，將個(gè)體字符串某位符號(hào)進(jìn)行逆變，即由進(jìn)行逆變，即由1變?yōu)樽優(yōu)?或由或由0變?yōu)樽優(yōu)?。例如，下式左側(cè)的個(gè)體于第。例如，下式左側(cè)的個(gè)體于第3位位突變，得到新個(gè)體如右側(cè)所示。突變，得到新個(gè)體如右側(cè)所示。上述（上述（2）（）（5）反復(fù)執(zhí)行，直至得出滿意的最優(yōu)解。）反復(fù)執(zhí)行，直至得出滿意的最優(yōu)解。由上可知，遺傳算法參考生物中有關(guān)進(jìn)化與遺傳的過程，利用復(fù)由上可知，遺傳算法參考生物中有關(guān)進(jìn)化與遺傳的過程，利用復(fù)制、交換、突變等操作，不斷循環(huán)執(zhí)行，制、交換、突變等操作，不斷循環(huán)執(zhí)行，逐漸逼近全局最優(yōu)解逐漸逼近全局最優(yōu)解。遺傳算法中，個(gè)體是否進(jìn)行突變以及在哪個(gè)部位突

25、變，都由遺傳算法中，個(gè)體是否進(jìn)行突變以及在哪個(gè)部位突變，都由事先給定的概率決定。通常，突變概率很小，約為事先給定的概率決定。通常，突變概率很小，約為0.008，本例的，本例的第一代中就沒有發(fā)生突變。第一代中就沒有發(fā)生突變。100001010028 從數(shù)學(xué)角度看，遺傳算法實(shí)質(zhì)上是一種搜索尋優(yōu)技從數(shù)學(xué)角度看，遺傳算法實(shí)質(zhì)上是一種搜索尋優(yōu)技術(shù)。它從某一初始群體出發(fā)，遵照一定的操作規(guī)則，不術(shù)。它從某一初始群體出發(fā)，遵照一定的操作規(guī)則，不斷迭代計(jì)算，逐步逼近最優(yōu)解。這種搜索技術(shù)，有如下斷迭代計(jì)算，逐步逼近最優(yōu)解。這種搜索技術(shù)，有如下特點(diǎn)：特點(diǎn)：4 4、遺傳算法的基本特征遺傳算法的基本特征 從上述簡(jiǎn)單例子

26、可以看出，遺傳算法仿照生物進(jìn)化從上述簡(jiǎn)單例子可以看出，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換、突變等操作，使優(yōu)勝和遺傳的規(guī)律，利用復(fù)制、交換、突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代一代地重復(fù)同樣的操作，最者繁殖，劣敗者消失，一代一代地重復(fù)同樣的操作，最終找出最優(yōu)解。終找出最優(yōu)解。29（1）智能式搜索）智能式搜索 遺傳算法的搜索策略，既不是盲目式的遺傳算法的搜索策略，既不是盲目式的亂搜索亂搜索，也不是，也不是窮舉式窮舉式的全面搜索，它是有指導(dǎo)的搜索。指導(dǎo)遺傳算法執(zhí)行的全面搜索，它是有指導(dǎo)的搜索。指導(dǎo)遺傳算法執(zhí)行搜索的依據(jù)是搜索的依據(jù)是適應(yīng)度適應(yīng)度，也就是它的目標(biāo)函數(shù)。利用適應(yīng)度，也

27、就是它的目標(biāo)函數(shù)。利用適應(yīng)度，使遺傳算法逐步逼近目標(biāo)值。使遺傳算法逐步逼近目標(biāo)值。（2）漸進(jìn)式優(yōu)化）漸進(jìn)式優(yōu)化 遺傳算法利用復(fù)制、交換、突變等操作，使新一代的結(jié)遺傳算法利用復(fù)制、交換、突變等操作，使新一代的結(jié)果優(yōu)越于舊一代，通過不斷迭代，逐漸得出最優(yōu)的結(jié)果，它果優(yōu)越于舊一代，通過不斷迭代，逐漸得出最優(yōu)的結(jié)果，它是一種反復(fù)迭代的過程。是一種反復(fù)迭代的過程。4 4、遺傳算法的基本特征遺傳算法的基本特征30（3）全局最優(yōu)解）全局最優(yōu)解 遺傳算法由于采用交換、突變等操作，產(chǎn)生新的個(gè)遺傳算法由于采用交換、突變等操作，產(chǎn)生新的個(gè)體，擴(kuò)大了搜索范圍，使得搜索得到的優(yōu)化結(jié)果是全局體，擴(kuò)大了搜索范圍，使得搜索得

28、到的優(yōu)化結(jié)果是全局最優(yōu)解而不是局部最優(yōu)解。最優(yōu)解而不是局部最優(yōu)解。（4）黑箱式結(jié)構(gòu)）黑箱式結(jié)構(gòu) 遺傳算法根據(jù)所解決問題的特性，進(jìn)行編碼和選擇遺傳算法根據(jù)所解決問題的特性，進(jìn)行編碼和選擇適應(yīng)度。一旦完成字符串和適應(yīng)度的表達(dá)，其余的復(fù)制、適應(yīng)度。一旦完成字符串和適應(yīng)度的表達(dá)，其余的復(fù)制、交換、突變等操作都可按常規(guī)手續(xù)執(zhí)行。個(gè)體的編碼如交換、突變等操作都可按常規(guī)手續(xù)執(zhí)行。個(gè)體的編碼如同輸入，適應(yīng)度如同輸出。因此遺傳算法從某種意義上同輸入，適應(yīng)度如同輸出。因此遺傳算法從某種意義上講是一種只考慮輸入與輸出關(guān)系的黑箱問題。講是一種只考慮輸入與輸出關(guān)系的黑箱問題。4 4、遺傳算法的基本特征遺傳算法的基本特征

29、31（5）通用性強(qiáng)）通用性強(qiáng) 傳統(tǒng)的優(yōu)化算法，需要將所解決的問題用傳統(tǒng)的優(yōu)化算法，需要將所解決的問題用數(shù)學(xué)式子數(shù)學(xué)式子表表示，常常要求解該數(shù)學(xué)函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)。采用示，常常要求解該數(shù)學(xué)函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)。采用遺傳算法，只用編碼及適應(yīng)度表示問題，并不要求明確的遺傳算法，只用編碼及適應(yīng)度表示問題，并不要求明確的數(shù)學(xué)方程及導(dǎo)數(shù)表達(dá)式。因此，遺傳算法通用性強(qiáng)，可應(yīng)數(shù)學(xué)方程及導(dǎo)數(shù)表達(dá)式。因此，遺傳算法通用性強(qiáng)，可應(yīng)用于離散問題及函數(shù)關(guān)系不明確的復(fù)雜問題，有人稱遺傳用于離散問題及函數(shù)關(guān)系不明確的復(fù)雜問題，有人稱遺傳算法是一種算法是一種框架型算法框架型算法，它只有一些簡(jiǎn)單的原則要求，在，它只有

30、一些簡(jiǎn)單的原則要求，在實(shí)施過程中可以賦予更多的含義。實(shí)施過程中可以賦予更多的含義。（6）并行式算法）并行式算法 遺傳算法是從初始群體出發(fā)，經(jīng)過復(fù)制、交換、突變遺傳算法是從初始群體出發(fā)，經(jīng)過復(fù)制、交換、突變等操作，產(chǎn)生一組新的群體。每次迭代計(jì)算，都是針對(duì)一等操作，產(chǎn)生一組新的群體。每次迭代計(jì)算，都是針對(duì)一組個(gè)體同時(shí)進(jìn)行，而不是針對(duì)某個(gè)個(gè)體進(jìn)行。因此，盡管組個(gè)體同時(shí)進(jìn)行，而不是針對(duì)某個(gè)個(gè)體進(jìn)行。因此，盡管遺傳算法是一種搜索算法，但是由于采用這種并行機(jī)理，遺傳算法是一種搜索算法，但是由于采用這種并行機(jī)理，搜索速度很高。這種并行式計(jì)算是遺傳算法的一個(gè)重要特搜索速度很高。這種并行式計(jì)算是遺傳算法的一個(gè)重

31、要特征。征。4 4、遺傳算法的基本特征遺傳算法的基本特征32 遺傳算法受生物進(jìn)化與遺傳的啟發(fā)，形成一種獨(dú)特的優(yōu)遺傳算法受生物進(jìn)化與遺傳的啟發(fā)，形成一種獨(dú)特的優(yōu)化方式，因此，遺傳算法的運(yùn)算原則常常與生物進(jìn)化及遺傳化方式，因此，遺傳算法的運(yùn)算原則常常與生物進(jìn)化及遺傳學(xué)說吻合，而且其術(shù)語(yǔ)也常常仿效生物學(xué)的術(shù)語(yǔ)。學(xué)說吻合，而且其術(shù)語(yǔ)也常常仿效生物學(xué)的術(shù)語(yǔ)。遺傳算法的運(yùn)算基礎(chǔ)是字符串，它就相當(dāng)于生物學(xué)中的遺傳算法的運(yùn)算基礎(chǔ)是字符串，它就相當(dāng)于生物學(xué)中的染色體。染色體。字符串由一系列字符組成，每個(gè)字符都有特定的含義，字符串由一系列字符組成，每個(gè)字符都有特定的含義，反應(yīng)所解決問題的某個(gè)特征，這就相當(dāng)于基因，

32、即染色體反應(yīng)所解決問題的某個(gè)特征，這就相當(dāng)于基因，即染色體DNA的片段。的片段。在進(jìn)行交換、突變操作時(shí)，遺傳算法只涉及到字符串某在進(jìn)行交換、突變操作時(shí)，遺傳算法只涉及到字符串某些片段，這就類似于遺傳過程只涉及某些基因而不是整個(gè)染些片段，這就類似于遺傳過程只涉及某些基因而不是整個(gè)染色體。色體。5 5、遺傳算法的生物學(xué)含義遺傳算法的生物學(xué)含義33 遺傳學(xué)很注重遺傳學(xué)很注重等位基因等位基因，它是反映生物某一形態(tài)所對(duì)應(yīng)的基因。，它是反映生物某一形態(tài)所對(duì)應(yīng)的基因。在遺傳算法的字符串中，每個(gè)字符都反映問題的某一特性，這也在遺傳算法的字符串中，每個(gè)字符都反映問題的某一特性，這也就相當(dāng)于等位基因，至于等位基因

33、的位置，也就相當(dāng)于該字符在就相當(dāng)于等位基因，至于等位基因的位置，也就相當(dāng)于該字符在字符串中的位置。字符串中的位置。在遺傳學(xué)中，雜交產(chǎn)生的子代里顯現(xiàn)出親本的性狀，稱作顯在遺傳學(xué)中，雜交產(chǎn)生的子代里顯現(xiàn)出親本的性狀，稱作顯性性狀，未顯現(xiàn)出來的親本性狀叫作隱性性狀?？刂骑@性性狀的性性狀，未顯現(xiàn)出來的親本性狀叫作隱性性狀?？刂骑@性性狀的基因是基因是顯性基因顯性基因，用大寫英文字母表示?？刂齐[性性狀的基因是，用大寫英文字母表示?？刂齐[性性狀的基因是隱性基因隱性基因，用小寫英文字母表示。在遺傳算法中，模仿這種大、，用小寫英文字母表示。在遺傳算法中，模仿這種大、小字母表達(dá)方式，對(duì)顯性基因和隱性基因采取不同的

34、操作。小字母表達(dá)方式，對(duì)顯性基因和隱性基因采取不同的操作。5 5、遺傳算法的生物學(xué)含義遺傳算法的生物學(xué)含義34 生物學(xué)術(shù)語(yǔ)在遺傳算法中的對(duì)應(yīng)意義如下表。生物學(xué)術(shù)語(yǔ)在遺傳算法中的對(duì)應(yīng)意義如下表。序號(hào)生物學(xué)遺傳算法123456染色體（Chromosome）基因（Gene）等位基因（Allele）基因位置（Locus）基因型（Genotype）表現(xiàn)型（Phenotype）字符串字符對(duì)應(yīng)的字符字符的位置字符串結(jié)構(gòu)字符串含義5 5、遺傳算法的生物學(xué)含義遺傳算法的生物學(xué)含義35 根據(jù)前面所講的示例，可以看出遺傳算法的根據(jù)前面所講的示例，可以看出遺傳算法的實(shí)施過程中包括編碼、產(chǎn)生群體、計(jì)算適應(yīng)度、實(shí)施過程中

35、包括編碼、產(chǎn)生群體、計(jì)算適應(yīng)度、復(fù)制、交換、突變等操作。復(fù)制、交換、突變等操作。遺傳算法的詳細(xì)流程如下圖。遺傳算法的詳細(xì)流程如下圖。6 6、遺傳算法的工作步驟遺傳算法的工作步驟36Gen：遺傳（迭代）的代次。表明遺傳算法反復(fù)執(zhí)行的次數(shù)，即已產(chǎn)生群體的代次數(shù)目。M：群體中擁有的個(gè)體數(shù)目。i：已處理個(gè)體的累計(jì)數(shù)，當(dāng)i等于M，表明這一代的個(gè)體已全部處理完畢，需要轉(zhuǎn)入下一代群體。交叉率 Pc 就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.40.99。變異率 Pm 是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.00010.1。復(fù)制概

36、率 Pt 用于控制復(fù)制與淘汰的個(gè)體數(shù)目。Pc Pt Pm No No Yes Gen：=0 隨機(jī)產(chǎn)生初始群體 滿足終止條件 計(jì)算群體中各個(gè)體的適應(yīng)度 i：=0 i：=M?選擇遺傳算子及概率 根據(jù)適應(yīng)度選擇兩個(gè)個(gè)體 i：=i+1 執(zhí)行交換 將兩個(gè)交換結(jié)果添入新群體 i：=i+1 將復(fù)制結(jié)果添入新群體 執(zhí)行復(fù)制 根據(jù)適應(yīng)度選擇一個(gè)個(gè)體 將突變結(jié)果添入新群體 執(zhí)行突變 Gen：=Gen+1 輸出結(jié)果 結(jié)束 Yes 37概括地講，遺傳算法主要執(zhí)行以下四步：概括地講，遺傳算法主要執(zhí)行以下四步：（1）隨機(jī)地建立由字符串組成的初始群體；隨機(jī)地建立由字符串組成的初始群體；（2）計(jì)算各個(gè)體的適應(yīng)度；計(jì)算各個(gè)體的

37、適應(yīng)度；（3）根據(jù)遺傳概率，利用下述操作產(chǎn)生新群體：根據(jù)遺傳概率，利用下述操作產(chǎn)生新群體：1）復(fù)制復(fù)制。將已有的優(yōu)良個(gè)體復(fù)制后添入新群體中，刪除劣。將已有的優(yōu)良個(gè)體復(fù)制后添入新群體中，刪除劣 質(zhì)個(gè)體；質(zhì)個(gè)體；2）交換交換。將選出的兩個(gè)個(gè)體進(jìn)行交換，所產(chǎn)生的新個(gè)體添。將選出的兩個(gè)個(gè)體進(jìn)行交換，所產(chǎn)生的新個(gè)體添 入新群體中。入新群體中。3）突變突變。隨機(jī)地改變某一個(gè)體的某個(gè)字符后添入新群體中。隨機(jī)地改變某一個(gè)體的某個(gè)字符后添入新群體中。（4）反復(fù)執(zhí)行（反復(fù)執(zhí)行（2）、（）、（3）后，一旦達(dá)到終止條件，）后，一旦達(dá)到終止條件，選擇最佳個(gè)體作為遺傳算法的結(jié)果。選擇最佳個(gè)體作為遺傳算法的結(jié)果。38 遺傳

38、算法的工作對(duì)象是字符串，因此對(duì)字符串的遺傳算法的工作對(duì)象是字符串，因此對(duì)字符串的編碼有兩點(diǎn)要求：一是字符串要反映所研究問題的性編碼有兩點(diǎn)要求：一是字符串要反映所研究問題的性質(zhì)；二是字符串的表達(dá)要便于計(jì)算處理。質(zhì)；二是字符串的表達(dá)要便于計(jì)算處理。遺傳算法關(guān)鍵問題遺傳算法關(guān)鍵問題（1 1）編碼）編碼 遺傳算法常常用二進(jìn)制的遺傳算法常常用二進(jìn)制的0/1字符編碼。當(dāng)問題比字符編碼。當(dāng)問題比較簡(jiǎn)單，例如只描述高較簡(jiǎn)單，例如只描述高/低、大低、大/小等布爾型性質(zhì)時(shí)，小等布爾型性質(zhì)時(shí)，每一位每一位0/1變量就代表一個(gè)性質(zhì)。變量就代表一個(gè)性質(zhì)。例如，某事物只涉及到貴例如，某事物只涉及到貴/賤、大賤、大/小及好

39、小及好/壞時(shí)，我們可用壞時(shí)，我們可用三位三位0/1字符表示，并規(guī)定第字符表示，并規(guī)定第1位字符代表貴位字符代表貴/賤，第賤，第2位字符代表位字符代表大大/小，第小，第3位字符代表好位字符代表好/壞。如壞。如111代表貴代表貴-大大-好，而好，而100代表貴代表貴-小小-好。好。39 當(dāng)問題的性質(zhì)要用數(shù)值描述時(shí)，則編碼變成用二當(dāng)問題的性質(zhì)要用數(shù)值描述時(shí)，則編碼變成用二進(jìn)制數(shù)表示十進(jìn)制數(shù)。例如，用進(jìn)制數(shù)表示十進(jìn)制數(shù)。例如，用4位位0/1字符串表示字符串表示1 16。根據(jù)排列計(jì)算，長(zhǎng)度（位數(shù)）為根據(jù)排列計(jì)算，長(zhǎng)度（位數(shù)）為L(zhǎng)的的0/1字符串，可以表達(dá)字符串，可以表達(dá)2*2*2 2=2L 種情況。種情

40、況。如果所描述性質(zhì)的最小值不是如果所描述性質(zhì)的最小值不是0時(shí)，即性質(zhì)介時(shí)，即性質(zhì)介于于UminUmax之間，為了減小字符串長(zhǎng)度，可之間，為了減小字符串長(zhǎng)度，可以采用映射的方法，用以采用映射的方法，用2L個(gè)二進(jìn)制數(shù)表示個(gè)二進(jìn)制數(shù)表示 Umin，Umax。這時(shí)，令。這時(shí)，令L個(gè)個(gè)0表示表示Umin，L個(gè)個(gè)1 表示表示Umax，其中，其中L大小取決于（大小取決于（Umax Umin），其余的數(shù)則用線性插值決定。例如，對(duì)），其余的數(shù)則用線性插值決定。例如，對(duì)于于 16，31 的十進(jìn)制數(shù)，我們可以用的十進(jìn)制數(shù)，我們可以用4位二位二進(jìn)制進(jìn)制0/1字符在字符在 0000，1111 范圍內(nèi)表示。范圍內(nèi)表示。（

41、1 1）編碼）編碼Umin 00Umax 11 40 對(duì)于兼有多種性質(zhì)的問題，可以采用長(zhǎng)字符串順對(duì)于兼有多種性質(zhì)的問題，可以采用長(zhǎng)字符串順序分別表示。例如，可選序分別表示。例如，可選25位位0/1字符串表示物體的體字符串表示物體的體積、重量及顏色，其中前積、重量及顏色，其中前10位數(shù)表示體積量，中間位數(shù)表示體積量，中間10位數(shù)表示重量，后位數(shù)表示重量，后5位數(shù)表示顏色。位數(shù)表示顏色。在遺傳算法中，字符串的長(zhǎng)度常常是固定的，以在遺傳算法中，字符串的長(zhǎng)度常常是固定的，以便按統(tǒng)一的方式執(zhí)行操作。個(gè)別研究者采用不等長(zhǎng)的便按統(tǒng)一的方式執(zhí)行操作。個(gè)別研究者采用不等長(zhǎng)的字符串，這時(shí)就需要跟蹤記錄，經(jīng)常調(diào)整操

42、作方式，字符串，這時(shí)就需要跟蹤記錄，經(jīng)常調(diào)整操作方式，比較煩瑣。比較煩瑣。從生物學(xué)角度看，編碼就相當(dāng)于選擇遺傳物質(zhì)，從生物學(xué)角度看，編碼就相當(dāng)于選擇遺傳物質(zhì)，它是研究遺傳的基礎(chǔ)。同樣，在遺傳算法中編碼也是它是研究遺傳的基礎(chǔ)。同樣，在遺傳算法中編碼也是一項(xiàng)基礎(chǔ)性工作。一項(xiàng)基礎(chǔ)性工作。（1 1）編碼）編碼41 在遺傳算法中，衡量個(gè)體優(yōu)劣的尺度是在遺傳算法中，衡量個(gè)體優(yōu)劣的尺度是適應(yīng)度適應(yīng)度。根據(jù)適應(yīng)度的大小，決定某些個(gè)體是繁殖或是消亡。根據(jù)適應(yīng)度的大小，決定某些個(gè)體是繁殖或是消亡。因此，適應(yīng)度是驅(qū)動(dòng)遺傳算法的動(dòng)力。從生物學(xué)角度因此，適應(yīng)度是驅(qū)動(dòng)遺傳算法的動(dòng)力。從生物學(xué)角度講，適應(yīng)度相當(dāng)于講，適應(yīng)度

43、相當(dāng)于“生存競(jìng)爭(zhēng)，適者生存生存競(jìng)爭(zhēng)，適者生存”的生物生的生物生存能力，在遺傳過程中具有重要意義。存能力，在遺傳過程中具有重要意義。通常，適應(yīng)度是通常，適應(yīng)度是費(fèi)用、贏利、方差費(fèi)用、贏利、方差等目標(biāo)的表達(dá)等目標(biāo)的表達(dá)式。在運(yùn)用過程中可以借鑒以下經(jīng)驗(yàn)。式。在運(yùn)用過程中可以借鑒以下經(jīng)驗(yàn)。（2 2）適應(yīng)度）適應(yīng)度42統(tǒng)一表達(dá)形式統(tǒng)一表達(dá)形式 在實(shí)際問題中，有時(shí)希望適應(yīng)度越大越好（如贏利、勞在實(shí)際問題中，有時(shí)希望適應(yīng)度越大越好（如贏利、勞動(dòng)生產(chǎn)率），有時(shí)要求適應(yīng)度越小越好（費(fèi)用、方差）。為動(dòng)生產(chǎn)率），有時(shí)要求適應(yīng)度越小越好（費(fèi)用、方差）。為了使遺傳算法有通用性，這種最大、最小值問題宜統(tǒng)一表達(dá)。了使遺傳算

44、法有通用性，這種最大、最小值問題宜統(tǒng)一表達(dá)。通常都統(tǒng)一按最大值問題處理，而且不允許適應(yīng)度小于通常都統(tǒng)一按最大值問題處理，而且不允許適應(yīng)度小于0。對(duì)于最小值問題，其適應(yīng)度按下式轉(zhuǎn)換：對(duì)于最小值問題，其適應(yīng)度按下式轉(zhuǎn)換：f(x)=Cmax-g(x)當(dāng)當(dāng)g(x)Cmax0 其他情況其他情況f(x)：轉(zhuǎn)換后的適應(yīng)度。：轉(zhuǎn)換后的適應(yīng)度。g(x)：最小值問題下的適應(yīng)度。：最小值問題下的適應(yīng)度。Cmax：足夠大的常數(shù)，可?。鹤銐虼蟮某?shù)，可取g(x)的最大值。的最大值。（2 2）適應(yīng)度）適應(yīng)度43統(tǒng)一表達(dá)形式統(tǒng)一表達(dá)形式 為了保證適應(yīng)度不出現(xiàn)負(fù)值，對(duì)于有可能產(chǎn)生負(fù)為了保證適應(yīng)度不出現(xiàn)負(fù)值，對(duì)于有可能產(chǎn)生負(fù)值

45、的最大值問題，可以采用下式進(jìn)行變換：值的最大值問題，可以采用下式進(jìn)行變換：f(x)=U(x)+Cmin 當(dāng)當(dāng)U(x)+Cmin 00 其他情況其他情況f(x)：變換后的適應(yīng)度。變換后的適應(yīng)度。U(x)：最大值問題下的適應(yīng)度。：最大值問題下的適應(yīng)度。Cmin：足夠大的常數(shù)。：足夠大的常數(shù)。（2 2）適應(yīng)度）適應(yīng)度44適應(yīng)度縮放適應(yīng)度縮放 在執(zhí)行遺傳算法的初始階段，各個(gè)個(gè)體的適應(yīng)度比較離散，在執(zhí)行遺傳算法的初始階段，各個(gè)個(gè)體的適應(yīng)度比較離散，某些個(gè)體的適應(yīng)度會(huì)很高或很低。對(duì)于個(gè)別適應(yīng)度很高的個(gè)體，會(huì)某些個(gè)體的適應(yīng)度會(huì)很高或很低。對(duì)于個(gè)別適應(yīng)度很高的個(gè)體，會(huì)連續(xù)多次被復(fù)制；對(duì)于適應(yīng)度很低的個(gè)體，會(huì)過

46、早被舍棄。這種不連續(xù)多次被復(fù)制；對(duì)于適應(yīng)度很低的個(gè)體，會(huì)過早被舍棄。這種不正常的取舍，對(duì)于個(gè)體數(shù)目不多的群體尤為嚴(yán)重，會(huì)把遺傳算法的正常的取舍，對(duì)于個(gè)體數(shù)目不多的群體尤為嚴(yán)重，會(huì)把遺傳算法的搜索引向誤區(qū)搜索引向誤區(qū)，過早地收斂于，過早地收斂于局部最優(yōu)解局部最優(yōu)解。為了克服這種缺陷，需。為了克服這種缺陷，需要采用適應(yīng)度縮放技術(shù)，將適應(yīng)度按下式變換：要采用適應(yīng)度縮放技術(shù)，將適應(yīng)度按下式變換：f ：縮放后的適應(yīng)度?？s放后的適應(yīng)度。f：原來的適應(yīng)度。：原來的適應(yīng)度。a、b：系數(shù)。：系數(shù)。f=a*f+b 利用這種縮放技術(shù)，縮小（放大）原來最大（最利用這種縮放技術(shù)，縮?。ǚ糯螅┰瓉碜畲螅ㄗ钚。┑倪m應(yīng)度，從

47、而可以減弱離散現(xiàn)象。?。┑倪m應(yīng)度，從而可以減弱離散現(xiàn)象。（2 2）適應(yīng)度）適應(yīng)度45 復(fù)制是遺傳算法的基本算子，它將優(yōu)良個(gè)體在下一代新群復(fù)制是遺傳算法的基本算子，它將優(yōu)良個(gè)體在下一代新群體中繁殖，體現(xiàn)了體中繁殖，體現(xiàn)了“適者生存適者生存”的自然選擇原則。的自然選擇原則。個(gè)體是否被復(fù)制的依據(jù)是其適應(yīng)度的大小，適應(yīng)度大者個(gè)體是否被復(fù)制的依據(jù)是其適應(yīng)度的大小，適應(yīng)度大者被復(fù)制，小者被淘汰，使新群體中的個(gè)體總數(shù)與原來群體相被復(fù)制，小者被淘汰，使新群體中的個(gè)體總數(shù)與原來群體相同。同。在遺傳算法中，常常采用在遺傳算法中，常常采用J.Holland教授提出的教授提出的輪盤賭方輪盤賭方式式選擇復(fù)制對(duì)象。選擇復(fù)

48、制對(duì)象。（3 3）復(fù)制）復(fù)制46 表中第一行說明有表中第一行說明有10個(gè)個(gè)體參與選擇，第二行表示各個(gè)體的個(gè)個(gè)體參與選擇，第二行表示各個(gè)體的適應(yīng)度，第三行標(biāo)記適應(yīng)度的累計(jì)值，總值為適應(yīng)度，第三行標(biāo)記適應(yīng)度的累計(jì)值，總值為76。然后，在。然后，在 0，76 區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)，如第四行所示。依次序?qū)⒌谌齾^(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)，如第四行所示。依次序?qū)⒌谌械睦塾?jì)適應(yīng)度與隨機(jī)數(shù)相比較，其值大于或等于隨機(jī)數(shù)的第一行的累計(jì)適應(yīng)度與隨機(jī)數(shù)相比較，其值大于或等于隨機(jī)數(shù)的第一個(gè)個(gè)體列為入選的復(fù)制對(duì)象。例如，第一個(gè)隨機(jī)數(shù)是個(gè)個(gè)體列為入選的復(fù)制對(duì)象。例如，第一個(gè)隨機(jī)數(shù)是23，除了，除了1號(hào)、號(hào)、2號(hào)個(gè)體

49、外，其余個(gè)體的累計(jì)適應(yīng)度均大于號(hào)個(gè)體外，其余個(gè)體的累計(jì)適應(yīng)度均大于23，然而，然而3號(hào)個(gè)體累計(jì)號(hào)個(gè)體累計(jì)值為值為27，是第一個(gè)大于，是第一個(gè)大于23的個(gè)體，所以它入選。的個(gè)體，所以它入選。個(gè)體序號(hào)12345678910適應(yīng)度8217721211737適應(yīng)度累計(jì)值8102734364859666976隨機(jī)數(shù)2349761312757被選中的個(gè)體37103137輪盤選擇示例：輪盤選擇示例：（3 3）復(fù)制）復(fù)制47（1）依次累計(jì)群體內(nèi)各個(gè)體的適應(yīng)度，得相應(yīng)的累計(jì)）依次累計(jì)群體內(nèi)各個(gè)體的適應(yīng)度，得相應(yīng)的累計(jì)值值Si，最后一個(gè)累計(jì)值為，最后一個(gè)累計(jì)值為Sn；（2）在）在 0，Sn 區(qū)間內(nèi)產(chǎn)生均勻分布的隨

50、機(jī)數(shù)區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)R；（3）依次用）依次用Si與與R相比較，第一個(gè)出現(xiàn)相比較，第一個(gè)出現(xiàn)Si大于或等于大于或等于R的個(gè)體的個(gè)體i被選為復(fù)制對(duì)象；被選為復(fù)制對(duì)象；（4）重復(fù)（）重復(fù)（2）、（）、（3），直至滿足所需要的個(gè)體數(shù)目。），直至滿足所需要的個(gè)體數(shù)目。上述選擇過程，可描述如下：上述選擇過程，可描述如下：（3 3）復(fù)制）復(fù)制48 因此，適應(yīng)度因此，適應(yīng)度f(wàn)i越大，越大，Si的距離越大，隨機(jī)數(shù)落的距離越大，隨機(jī)數(shù)落在這個(gè)區(qū)間的可能性越大，第在這個(gè)區(qū)間的可能性越大，第i個(gè)個(gè)體被選中的機(jī)會(huì)也個(gè)個(gè)體被選中的機(jī)會(huì)也越多。如下圖所示。越多。如下圖所示。表面上看，復(fù)制個(gè)體的選擇是隨機(jī)的。但是，

51、選表面上看，復(fù)制個(gè)體的選擇是隨機(jī)的。但是，選擇時(shí)是依據(jù)相鄰兩個(gè)適應(yīng)度累計(jì)值的差值擇時(shí)是依據(jù)相鄰兩個(gè)適應(yīng)度累計(jì)值的差值 Si：Si=Si Si-1=fifi表示第表示第i個(gè)個(gè)體的適應(yīng)度個(gè)個(gè)體的適應(yīng)度（3 3）復(fù)制）復(fù)制49 輪盤（賭）選擇原理輪盤（賭）選擇原理 S2S1S3S4SiSn-1Sn 圖中的指針固定不動(dòng)，圖中的指針固定不動(dòng)，外圈的圓環(huán)可以任意轉(zhuǎn)動(dòng)，外圈的圓環(huán)可以任意轉(zhuǎn)動(dòng)，圓環(huán)中每段對(duì)應(yīng)于適應(yīng)度的圓環(huán)中每段對(duì)應(yīng)于適應(yīng)度的大小。從統(tǒng)計(jì)意義上講，適大小。從統(tǒng)計(jì)意義上講，適應(yīng)度大的個(gè)體被復(fù)制的機(jī)會(huì)應(yīng)度大的個(gè)體被復(fù)制的機(jī)會(huì)越大。當(dāng)然，適應(yīng)度小的個(gè)越大。當(dāng)然，適應(yīng)度小的個(gè)體盡管被復(fù)制的概率小，但體

52、盡管被復(fù)制的概率小，但仍有可能被仍有可能被“破格破格”復(fù)制，復(fù)制，這樣就增加個(gè)體的多樣性，這樣就增加個(gè)體的多樣性，便于執(zhí)行交換及突變。所以，便于執(zhí)行交換及突變。所以，輪盤選擇方法既體現(xiàn)輪盤選擇方法既體現(xiàn)“適者適者生存生存”原則，又保持個(gè)體性原則，又保持個(gè)體性態(tài)多種多樣。態(tài)多種多樣。（3 3）復(fù)制）復(fù)制50 選擇復(fù)制個(gè)體的隨機(jī)方法還有別的形式，不過輪選擇復(fù)制個(gè)體的隨機(jī)方法還有別的形式，不過輪盤選擇法是最常用的方法。盤選擇法是最常用的方法。每代群體中，被復(fù)制的個(gè)體數(shù)目由復(fù)制概率每代群體中，被復(fù)制的個(gè)體數(shù)目由復(fù)制概率Pt控制，控制，Pt常取常取0.10.2，也就是說，群體中有，也就是說，群體中有10

53、%個(gè)體被復(fù)制，個(gè)體被復(fù)制，相應(yīng)地有相應(yīng)地有10%個(gè)體被淘汰，以保持群體大小。個(gè)體被淘汰，以保持群體大小。（3 3）復(fù)制）復(fù)制51 下表是個(gè)體兩兩交換的示例，字符串內(nèi)的下橫線下表是個(gè)體兩兩交換的示例，字符串內(nèi)的下橫線代表交換點(diǎn)的位置，交換點(diǎn)及其后面的字符串兩兩互代表交換點(diǎn)的位置，交換點(diǎn)及其后面的字符串兩兩互換。換。在遺傳算法中，交換是產(chǎn)生新個(gè)體的主要手段。它在遺傳算法中，交換是產(chǎn)生新個(gè)體的主要手段。它仿照生物學(xué)中雜交的原理，將兩個(gè)個(gè)體（染色體）的部仿照生物學(xué)中雜交的原理，將兩個(gè)個(gè)體（染色體）的部分字符（基因）互相交換。分字符（基因）互相交換。序號(hào)交換前交換后12親代1：1 1 1 1 1 1親代

54、2：0 0 0 0 0 0子代1：1 1 1 1 0 0子代2：0 0 0 0 1 134親代1：1 0 1 1 0 1親代2：0 0 1 1 0 0子代1：1 0 1 1 0 0子代2：0 0 1 1 0 1（4 4）交換）交換52 執(zhí)行交換的個(gè)體是隨機(jī)選擇的。首先，要確定交換的概率執(zhí)行交換的個(gè)體是隨機(jī)選擇的。首先，要確定交換的概率Pc，大，大致為致為0.50.8左右。這就是說，約左右。這就是說，約50%80%的個(gè)體要執(zhí)行交換。然后，的個(gè)體要執(zhí)行交換。然后，采用上述輪盤選擇的方法，按適應(yīng)度大小選擇被交換的個(gè)體，依次兩采用上述輪盤選擇的方法，按適應(yīng)度大小選擇被交換的個(gè)體，依次兩兩進(jìn)行交換。兩進(jìn)

55、行交換。交換點(diǎn)的選擇也是隨機(jī)的。假設(shè)字符串長(zhǎng)度為交換點(diǎn)的選擇也是隨機(jī)的。假設(shè)字符串長(zhǎng)度為L(zhǎng)，則在，則在 0，L 區(qū)區(qū)間內(nèi)產(chǎn)生隨機(jī)整數(shù)，該整數(shù)便是交換點(diǎn)的位置。需要注意的是，交換間內(nèi)產(chǎn)生隨機(jī)整數(shù)，該整數(shù)便是交換點(diǎn)的位置。需要注意的是，交換點(diǎn)不能選在第一個(gè)字符上。因此，長(zhǎng)度為點(diǎn)不能選在第一個(gè)字符上。因此，長(zhǎng)度為L(zhǎng)的字符串，可供選擇的交的字符串，可供選擇的交換點(diǎn)為（換點(diǎn)為（L-1）個(gè)。）個(gè)。根據(jù)交換點(diǎn)數(shù)目的不同，可分為根據(jù)交換點(diǎn)數(shù)目的不同，可分為一點(diǎn)交換一點(diǎn)交換和多和多點(diǎn)交換點(diǎn)交換，前者只選，前者只選取一個(gè)交換點(diǎn)，該點(diǎn)之后的字符全部參加交換。后者選擇兩個(gè)或多個(gè)取一個(gè)交換點(diǎn)，該點(diǎn)之后的字符全部參加交換

56、。后者選擇兩個(gè)或多個(gè)交換點(diǎn)，只有兩點(diǎn)間的字符才參加交換。當(dāng)字符串長(zhǎng)度大時(shí)，常采用交換點(diǎn)，只有兩點(diǎn)間的字符才參加交換。當(dāng)字符串長(zhǎng)度大時(shí)，常采用兩點(diǎn)交換。此外還有兩點(diǎn)交換。此外還有多點(diǎn)交換多點(diǎn)交換，即對(duì)長(zhǎng)字符串實(shí)行多段交換。，即對(duì)長(zhǎng)字符串實(shí)行多段交換。（4 4）交換）交換53 通過交換，子代的字符串不同于親代。有時(shí)，這種差別很明通過交換，子代的字符串不同于親代。有時(shí)，這種差別很明顯，如表中的第一組個(gè)體，被交換部分完全不一樣。有時(shí)，這種顯，如表中的第一組個(gè)體，被交換部分完全不一樣。有時(shí)，這種差別卻不大，如表中的第二組個(gè)體，被交換的三個(gè)字符中只有最差別卻不大，如表中的第二組個(gè)體，被交換的三個(gè)字符中只有

57、最后一個(gè)字符發(fā)生變化。后一種情況說明交換后產(chǎn)生的個(gè)體，其性后一個(gè)字符發(fā)生變化。后一種情況說明交換后產(chǎn)生的個(gè)體，其性態(tài)變化不大。盡管如此，交換仍然是遺傳算法產(chǎn)生新個(gè)體的主要態(tài)變化不大。盡管如此，交換仍然是遺傳算法產(chǎn)生新個(gè)體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。手段。正是有了交換操作，群體的性態(tài)才多種多樣。序號(hào)交換前交換后12親代1：1 1 1 1 1 1親代2：0 0 0 0 0 0子代1：1 1 1 1 0 0子代2：0 0 0 0 1 134親代1：1 0 1 1 0 1親代2：0 0 1 1 0 0子代1：1 0 1 1 0 0子代2：0 0 1 1 0 1 傳統(tǒng)的優(yōu)化算法，

58、例如動(dòng)態(tài)規(guī)劃法、個(gè)體性態(tài)不能增添，只傳統(tǒng)的優(yōu)化算法，例如動(dòng)態(tài)規(guī)劃法、個(gè)體性態(tài)不能增添，只能在原有的個(gè)體群體中擇優(yōu)，從而限制了搜索尋優(yōu)的范圍。因此，能在原有的個(gè)體群體中擇優(yōu)，從而限制了搜索尋優(yōu)的范圍。因此，可以說，如果沒有交換，遺傳算法就失去了其優(yōu)越性?？梢哉f，如果沒有交換，遺傳算法就失去了其優(yōu)越性。（4 4）交換）交換54 突變是遺傳算法中產(chǎn)生新個(gè)體的另一種方法，它是突變是遺傳算法中產(chǎn)生新個(gè)體的另一種方法，它是將某一個(gè)體的某一位字符進(jìn)行補(bǔ)運(yùn)算，使將某一個(gè)體的某一位字符進(jìn)行補(bǔ)運(yùn)算，使0變?yōu)樽優(yōu)?，或使，或使1變?yōu)樽優(yōu)?。突變個(gè)體的選擇以及突變位置的確定，都是采用隨突變個(gè)體的選擇以及突變位置的確定

59、，都是采用隨機(jī)的方法產(chǎn)生。首先，確定突變概率機(jī)的方法產(chǎn)生。首先，確定突變概率Pm，Pm通常較小，通常較小，約為約為0.0010.01。也就是說，。也就是說，1000個(gè)字符中有個(gè)字符中有110個(gè)個(gè)發(fā)生突變。然后，針對(duì)每個(gè)字符在發(fā)生突變。然后，針對(duì)每個(gè)字符在 0，1 之間產(chǎn)生三之間產(chǎn)生三位有效數(shù)的均勻分布隨機(jī)數(shù)。若位有效數(shù)的均勻分布隨機(jī)數(shù)。若Pm=0.008，凡是隨機(jī)，凡是隨機(jī)數(shù)小于數(shù)小于0.008所對(duì)應(yīng)的字符，將實(shí)現(xiàn)突變。示例如下：所對(duì)應(yīng)的字符，將實(shí)現(xiàn)突變。示例如下：（5 5）突變）突變55 表中有三個(gè)字符長(zhǎng)度為表中有三個(gè)字符長(zhǎng)度為4的舊個(gè)體。對(duì)應(yīng)每個(gè)字符，的舊個(gè)體。對(duì)應(yīng)每個(gè)字符，依次產(chǎn)生依次產(chǎn)

60、生 0，1 區(qū)間均勻分布的隨機(jī)數(shù)區(qū)間均勻分布的隨機(jī)數(shù)12個(gè)。表中只個(gè)。表中只有有2號(hào)個(gè)體的第號(hào)個(gè)體的第3個(gè)字符以及個(gè)字符以及3號(hào)個(gè)體的第號(hào)個(gè)體的第4個(gè)字符需要發(fā)個(gè)字符需要發(fā)生突變，因?yàn)樗鼈儗?duì)應(yīng)的隨機(jī)數(shù)小于生突變，因?yàn)樗鼈儗?duì)應(yīng)的隨機(jī)數(shù)小于0.008。序號(hào)舊個(gè)體隨機(jī)數(shù)新字符新個(gè)體1231010110000100.801 0.102 0.266 0.3730.120 0.096 0.005 0.8400.760 0.473 0.894 0.00111101011100011（5 5）突變）突變56 隨機(jī)確定突變的位置后，執(zhí)行突變的方法有兩種。一種是直接產(chǎn)生突變，將表中的2號(hào)和3號(hào)舊個(gè)體分別改寫作11

61、10及0011。另一種方法，按50%的概率隨機(jī)產(chǎn)生新字符0或1。表中2號(hào)個(gè)體產(chǎn)生的新字符為0，與需要突變的第三行字符恰好一樣，因此新個(gè)體等同于舊個(gè)體。表中3號(hào)個(gè)體產(chǎn)生的新字符（1）不同于待突變的原來字符（0），因此新個(gè)體不同于舊個(gè)體。很明顯，后一種突變方法的突變概率僅為前一種方法的50%。通常建議采用后一種方法，增加突變的隨機(jī)性。序號(hào)舊個(gè)體隨機(jī)數(shù)新字符新個(gè)體1231010110000100.801 0.102 0.266 0.3730.120 0.096 0.005 0.8400.760 0.473 0.894 0.00101101011000011（5 5）突變）突變57 還有一種執(zhí)行突變的

62、方法，是根據(jù)給定的概率還有一種執(zhí)行突變的方法，是根據(jù)給定的概率Pm1。隨機(jī)選擇突變的個(gè)體。當(dāng)被突變的個(gè)體選中后，在字長(zhǎng)隨機(jī)選擇突變的個(gè)體。當(dāng)被突變的個(gè)體選中后，在字長(zhǎng)范圍內(nèi)用均勻分布的隨機(jī)數(shù)選擇突變的字符，使該個(gè)體范圍內(nèi)用均勻分布的隨機(jī)數(shù)選擇突變的字符，使該個(gè)體發(fā)生突變。然而，這時(shí)的概率發(fā)生突變。然而，這時(shí)的概率Pm1，不同于突變概率，不同于突變概率Pm，后者是針對(duì)字符而言，前者是針對(duì)個(gè)體。遺傳算法中，后者是針對(duì)字符而言，前者是針對(duì)個(gè)體。遺傳算法中討論的正是字符的突變概率討論的正是字符的突變概率Pm，兩者間的關(guān)系與字長(zhǎng)，兩者間的關(guān)系與字長(zhǎng)L有關(guān)。有關(guān)。盡管突變和交換都能產(chǎn)生新個(gè)體，但是在遺傳算

63、法盡管突變和交換都能產(chǎn)生新個(gè)體，但是在遺傳算法中，交換的作用遠(yuǎn)比突變重要。中，交換的作用遠(yuǎn)比突變重要。（5 5）突變）突變58 遺傳算法是一種反復(fù)迭代的搜索方法，它通過多次遺傳算法是一種反復(fù)迭代的搜索方法，它通過多次進(jìn)化逐漸逼近最優(yōu)解而不是恰好等于最優(yōu)解，因此需要進(jìn)化逐漸逼近最優(yōu)解而不是恰好等于最優(yōu)解，因此需要確定終止條件。確定終止條件。其一其一,最常用的終止方法是規(guī)定遺傳（迭代）的代最常用的終止方法是規(guī)定遺傳（迭代）的代次。剛開始時(shí)，迭代次數(shù)小一些，如規(guī)定次。剛開始時(shí)，迭代次數(shù)小一些，如規(guī)定100次。然后次。然后視情況逐漸增加次數(shù)，可達(dá)到上千次。視情況逐漸增加次數(shù)，可達(dá)到上千次。（6 6）終

64、止條件）終止條件59 當(dāng)目標(biāo)函數(shù)是方差這一類有最優(yōu)目標(biāo)值的問題時(shí)，當(dāng)目標(biāo)函數(shù)是方差這一類有最優(yōu)目標(biāo)值的問題時(shí)，可采用控制偏差的方法實(shí)現(xiàn)終止。一旦遺傳算法得出的可采用控制偏差的方法實(shí)現(xiàn)終止。一旦遺傳算法得出的目標(biāo)函數(shù)值（適應(yīng)度）與實(shí)際目標(biāo)值之差小于允許值后，目標(biāo)函數(shù)值（適應(yīng)度）與實(shí)際目標(biāo)值之差小于允許值后，算法終止，即：算法終止，即：f(x)：遺傳算法得出的目標(biāo)函數(shù)值。遺傳算法得出的目標(biāo)函數(shù)值。f*：實(shí)際目標(biāo)值。：實(shí)際目標(biāo)值。：足夠小的數(shù)。：足夠小的數(shù)。|f(x)f*|（6 6）終止條件）終止條件60 第三種終止方法是檢查適應(yīng)度的變化。在遺傳算法第三種終止方法是檢查適應(yīng)度的變化。在遺傳算法后期，

65、一旦最優(yōu)個(gè)體的適應(yīng)度沒有變化或變化很小時(shí)，后期，一旦最優(yōu)個(gè)體的適應(yīng)度沒有變化或變化很小時(shí)，即令計(jì)算終止。即令計(jì)算終止。遺傳算法的另一個(gè)重要參數(shù)是每代群體中的個(gè)遺傳算法的另一個(gè)重要參數(shù)是每代群體中的個(gè)體數(shù)。很明顯，個(gè)體數(shù)目越多，搜索范圍越廣，容易體數(shù)。很明顯，個(gè)體數(shù)目越多，搜索范圍越廣，容易獲取全局最優(yōu)解。然而個(gè)體數(shù)目太多，每次迭代時(shí)間獲取全局最優(yōu)解。然而個(gè)體數(shù)目太多，每次迭代時(shí)間也長(zhǎng)。通常，個(gè)體數(shù)目可取也長(zhǎng)。通常，個(gè)體數(shù)目可取100-1000之間。之間。（6 6）終止條件）終止條件7 遺傳算法的應(yīng)用領(lǐng)域遺傳算法的應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化。）函數(shù)優(yōu)化。函函數(shù)數(shù)優(yōu)優(yōu)化化是是遺遺傳傳算算法法的的經(jīng)經(jīng)典

66、典應(yīng)應(yīng)用用領(lǐng)領(lǐng)域域，也也是是遺遺傳傳算算法法進(jìn)進(jìn)行行性性能能評(píng)評(píng)價(jià)價(jià)的的常常用用算算例例。尤尤其其是是對(duì)對(duì)非非線線性性、多多模模型型、多多目目標(biāo)標(biāo)的的函函數(shù)數(shù)優(yōu)優(yōu)化化問問題題，采采用用其其他他優(yōu)優(yōu)化化方方法法較較難難求求解解，而而遺遺傳算法卻可以得到較好的結(jié)果。傳算法卻可以得到較好的結(jié)果。（2）組合優(yōu)化。）組合優(yōu)化。隨隨著著問問題題的的增增大大，組組合合優(yōu)優(yōu)化化問問題題的的搜搜索索空空間間也也急急劇劇擴(kuò)擴(kuò)大大，采采用用傳傳統(tǒng)統(tǒng)的的優(yōu)優(yōu)化化方方法法很很難難得得到到最最優(yōu)優(yōu)解解。遺遺傳傳算算法法是是尋尋求求這這種種滿滿意意解解的的最最佳佳工工具具。例例如如，遺遺傳傳算算法法已已經(jīng)經(jīng)在在求求解解旅旅行行商商問問題題、背背包包問問題題、裝裝箱箱問問題題、圖圖形形劃分問題等方面得到成功的應(yīng)用。劃分問題等方面得到成功的應(yīng)用。（3）生產(chǎn)調(diào)度問題）生產(chǎn)調(diào)度問題 在在很很多多情情況況下下，采采用用建建立立數(shù)數(shù)學(xué)學(xué)模模型型的的方方法法難難以以對(duì)對(duì)生生產(chǎn)產(chǎn)調(diào)調(diào)度度問問題題進(jìn)進(jìn)行行精精確確求求解解。在在現(xiàn)現(xiàn)實(shí)實(shí)生生產(chǎn)產(chǎn)中中多多采采用用一一些些經(jīng)經(jīng)驗(yàn)驗(yàn)進(jìn)進(jìn)行行調(diào)調(diào)度度。遺遺傳傳算算法法是是解解決決復(fù)復(fù)雜雜調(diào)調(diào)度