第七講遺傳算法第一頁，共六十九頁，2022年，8月28日英國的博物學(xué)家達爾文通過研究提出了被恩格斯贊譽為“19世紀自然科學(xué)三大發(fā)現(xiàn)”之一的生物進化學(xué)說。第二頁，共六十九頁，2022年，8月28日達爾文的“貝格爾號”考察路線太平洋印度洋亞洲歐洲非洲南美洲北美洲大洋州大西洋第三頁，共六十九頁，2022年，8月28日生物進化的過程和原因取食果實取食昆蟲取食仙人掌取食種子取食昆蟲喙鑿狀喙不變喙尖而長喙粗而尖加拉帕戈斯雀的進化第四頁，共六十九頁，2022年，8月28日長頸鹿的進化示意圖第五頁，共六十九頁，2022年，8月28日環(huán)境實驗灰色樺尺蛾黑色樺尺蛾未污染區(qū)放出只數(shù)496473重新捕捉只數(shù)6230重新捕捉百分比12.5%6.3%污染區(qū)放出只數(shù)201601重新捕捉只數(shù)32205重新捕捉百分比15.9%34.1%第六頁，共六十九頁，2022年，8月28日遺傳算法（GeneticAlgorithm，簡稱GA），是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算機算法，它由美國Holland教授1975年提出。遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡單通用、魯棒性強、適合并行處理及應(yīng)用范圍廣等顯著特點，奠定了它作為21世紀關(guān)鍵智能計算之一的地位。一、遺傳算法概述第七頁，共六十九頁，2022年，8月28日一、遺傳算法概述基本思想：基于模仿生物界遺傳學(xué)的遺傳過程，把問題的參數(shù)用基因來表示，把問題的解用染色體來表示代表（在計算機里用二進制碼表示），從而得到一個由具有不同染色體的個體組成的群體。這個群體在問題特定的環(huán)境里生存競爭，適者有最好的機會生存和產(chǎn)生后代，后代隨機化地繼承父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)這一過程。群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進化，最后收斂到一族最適應(yīng)環(huán)境的類似個體，即得到問題最優(yōu)解。第八頁，共六十九頁，2022年，8月28日一、遺傳算法概述與傳統(tǒng)的優(yōu)化算法相比，遺傳算法主要有以下幾個不同之處遺傳算法不是直接作用在參變量集上而是利用參變量集的某種編碼遺傳算法不是從單個點，而是從一個點的群體開始搜索；遺傳算法利用適應(yīng)值信息，無須導(dǎo)數(shù)或其它輔助信息；遺傳算法利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。第九頁，共六十九頁，2022年，8月28日一、遺傳算法概述遺傳算法的優(yōu)越性主要表現(xiàn)在：首先，它在搜索過程中不容易陷入局部最優(yōu)，即使所定義的適應(yīng)函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，它也能以很大的概率找到整體最優(yōu)解；其次，由于它固有的并行性，遺傳算法非常適用于大規(guī)模并行計算機。第十頁，共六十九頁，2022年，8月28日一、遺傳算法概述應(yīng)用

遺傳算法在自然科學(xué)、工程技術(shù)、商業(yè)、醫(yī)學(xué)、社會科學(xué)等領(lǐng)域都有應(yīng)用復(fù)雜數(shù)學(xué)函數(shù)的優(yōu)化；半導(dǎo)體器件、飛行器、通信網(wǎng)絡(luò)、天然氣管道系統(tǒng)、汽輪機的設(shè)計；神經(jīng)網(wǎng)絡(luò)的設(shè)計與訓(xùn)練；生產(chǎn)的規(guī)劃與排序；機器人的運動軌跡生成與運動學(xué)解；機器多故障診斷；自動裝配系統(tǒng)的優(yōu)化設(shè)計等。尤其適合于尋求多參數(shù)、多設(shè)計變量或多選擇的復(fù)雜工程問題的最優(yōu)數(shù)值解。第十一頁，共六十九頁，2022年，8月28日二、遺傳學(xué)相關(guān)概念個體與種群●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。

●種群(population)就是模擬生物種群而由若干個體組成的群體,它一般是整個搜索空間的一個很小的子集。第十二頁，共六十九頁，2022年，8月28日二、遺傳學(xué)相關(guān)概念適應(yīng)度與適應(yīng)度函數(shù)●適應(yīng)度(fitness)就是借鑒生物個體對環(huán)境的適應(yīng)程度,而對問題中的個體對象所設(shè)計的表征其優(yōu)劣的一種測度。●適應(yīng)度函數(shù)(fitnessfunction)就是問題中的全體個體與其適應(yīng)度之間的一個對應(yīng)關(guān)系。它一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評價函數(shù)。

第十三頁，共六十九頁，2022年，8月28日二、遺傳學(xué)相關(guān)概念染色體與基因

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

9----

1001（2，5，6）----010101110第十四頁，共六十九頁，2022年，8月28日二、遺傳學(xué)相關(guān)概念遺傳操作

亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體的運算。遺傳算法中有三種遺傳操作:

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

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

●變異(mutation，亦稱突變)第十五頁，共六十九頁，2022年，8月28日二、遺傳學(xué)相關(guān)概念遺傳學(xué)遺傳算法數(shù)學(xué)1個體要處理的基本對象、結(jié)構(gòu)也就是可行解2群體個體的集合被選定的一組可行解3染色體個體的表現(xiàn)形式可行解的編碼4基因染色體中的元素編碼中的元素5基因位某一基因在染色體中的位置元素在編碼中的位置6適應(yīng)值個體對于環(huán)境的適應(yīng)程度，或在環(huán)境壓力下的生存能力可行解所對應(yīng)的適應(yīng)函數(shù)值7種群被選定的一組染色體或個體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作保留或復(fù)制適應(yīng)值大的可行解，去掉小的可行解第十六頁，共六十九頁，2022年，8月28日二、遺傳學(xué)相關(guān)概念遺傳學(xué)遺傳算法數(shù)學(xué)9交叉一組染色體上對應(yīng)基因段的交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對應(yīng)基因段交換的概率（可能性大小）閉區(qū)間[0,1]上的一個值，一般為0.65~0.9011變異染色體水平上基因變化編碼的某些元素被改變12變異概率染色體上基因變化的概率（可能性大小）開區(qū)間(0,1)內(nèi)的一個值,一般為0.001~0.0113進化、適者生存?zhèn)€體進行優(yōu)勝劣汰的進化，一代又一代地優(yōu)化目標函數(shù)取到最大值，最優(yōu)的可行解第十七頁，共六十九頁，2022年，8月28日三、簡單遺傳算法

選擇-復(fù)制

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

這里的選擇概率P(xi)的計算公式為第十八頁，共六十九頁，2022年，8月28日三、簡單遺傳算法s40.309s20.492s10.144s30.055指針輪盤法第十九頁，共六十九頁，2022年，8月28日三、簡單遺傳算法

交叉：就是互換兩個染色體某些位上的基因。

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

例如,設(shè)染色體s1=01001011,s2=10010101,交換其后4位基因,即第二十頁，共六十九頁，2022年，8月28日三、簡單遺傳算法變異：就是改變?nèi)旧w某個(些)位上的基因。例如,設(shè)染色體s=11001101，將其第三位上的0變?yōu)?,即s=11001101→11101101=s′。s′也可以看做是原染色體s的子代染色體。第二十一頁，共六十九頁，2022年，8月28日三、簡單遺傳算法遺傳算法基本步驟：把這些可行解置于問題的“環(huán)境”中，按適者生存的原則，選取較適應(yīng)環(huán)境的“染色體”進行復(fù)制，并通過交叉、變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群把問題的解表示成“染色體”，在算法中就是以二進制編碼的串，給出一群“染色體”，也就是假設(shè)的可行解經(jīng)過這樣的一代一代地進化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解第二十二頁，共六十九頁，2022年，8月28日三、簡單遺傳算法遺傳算法具體步驟選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；定義適應(yīng)度函數(shù)，便于計算適應(yīng)值；確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數(shù)；隨機產(chǎn)生初始化群體；第二十三頁，共六十九頁，2022年，8月28日三、簡單遺傳算法計算群體中的個體或染色體解碼后的適應(yīng)值；按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代群體；判斷群體性能是否滿足某一指標，或者已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步，或者修改遺傳策略再返回第六步．第二十四頁，共六十九頁，2022年，8月28日遺傳算法具體步驟產(chǎn)生初始群體是否滿足終止條件得到結(jié)果是結(jié)束程序否計算每個個體的適應(yīng)值以概率選擇遺傳算子選擇一個個體復(fù)制到新群體選擇兩個個體進行

交叉插入到新群體選擇一個個體進行變異插入到新群體得到新群體第二十五頁，共六十九頁，2022年，8月28日四、遺傳算法應(yīng)用舉例1

例1利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。

y=x2

31

XY第二十六頁，共六十九頁，2022年，8月28日

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就可以用遺傳算法來解決。四、遺傳算法應(yīng)用舉例1第二十七頁，共六十九頁，2022年，8月28日

(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進制數(shù)編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應(yīng)度函數(shù),

取適應(yīng)度函數(shù)：f(x)=x2

四、遺傳算法應(yīng)用舉例1第二十八頁，共六十九頁，2022年，8月28日(3)計算各代種群中的各個體的適應(yīng)度,并對其染色體進行遺傳操作,直到適應(yīng)度最高的個體(即31（11111）)出現(xiàn)為止。

四、遺傳算法應(yīng)用舉例1第二十九頁，共六十九頁，2022年，8月28日

首先計算種群S1中各個體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應(yīng)度f(si)。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361四、遺傳算法應(yīng)用舉例1第三十頁，共六十九頁，2022年，8月28日再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31四、遺傳算法應(yīng)用舉例1第三十一頁，共六十九頁，2022年，8月28日賭輪選擇示意s40.31s20.49s10.14s30.06四、遺傳算法應(yīng)用舉例1第三十二頁，共六十九頁，2022年，8月28日選擇-復(fù)制

染色體適應(yīng)度選擇概率選中次數(shù)s1=011011690.141s2=110005760.492s3=01000640.060s4=100113610.311四、遺傳算法應(yīng)用舉例1第三十三頁，共六十九頁，2022年，8月28日于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）四、遺傳算法應(yīng)用舉例1第三十四頁，共六十九頁，2022年，8月28日交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運算。設(shè)s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

四、遺傳算法應(yīng)用舉例1第三十五頁，共六十九頁，2022年，8月28日變異設(shè)變異率pm=0.001。這樣，群體S1中共有5×4×0.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。四、遺傳算法應(yīng)用舉例1第三十六頁，共六十九頁，2022年，8月28日

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）四、遺傳算法應(yīng)用舉例1第三十七頁，共六十九頁，2022年，8月28日

第二代種群S2中各染色體的情況

染色體適應(yīng)度選擇概率估計的選中次數(shù)s1=110016250.361s2=011001440.080s3=110117290.412s4=100002560.151四、遺傳算法應(yīng)用舉例1第三十八頁，共六十九頁，2022年，8月28日假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個染色體都被選中，則得到群體：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍然不會發(fā)生變異。

四、遺傳算法應(yīng)用舉例1第三十九頁，共六十九頁，2022年，8月28日于是，得第三代種群S3：s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

四、遺傳算法應(yīng)用舉例1第四十頁，共六十九頁，2022年，8月28日第三代種群S3中各染色體的情況

染色體適應(yīng)度選擇概率估計的選中次數(shù)s1=111007840.442s2=01001810.040s3=110005760.321s4=100113610.201四、遺傳算法應(yīng)用舉例1第四十一頁，共六十九頁，2022年，8月28日設(shè)這一輪的選擇-復(fù)制結(jié)果為：s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會發(fā)生變異。四、遺傳算法應(yīng)用舉例1第四十二頁，共六十九頁，2022年，8月28日于是，得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

四、遺傳算法應(yīng)用舉例1第四十三頁，共六十九頁，2022年，8月28日顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。

四、遺傳算法應(yīng)用舉例1第四十四頁，共六十九頁，2022年，8月28日YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x2

16242831

X第四代種群及其適應(yīng)度第四十五頁，共六十九頁，2022年，8月28日

例4.2用遺傳算法求解TSP。分析

由于其任一可能解——一個合法的城市序列，即n個城市的一個排列，都可以事先構(gòu)造出來。于是，我們就可以直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。四、遺傳算法應(yīng)用舉例2第四十六頁，共六十九頁，2022年，8月28日

（1）定義適應(yīng)度函數(shù)我們將一個合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作為一個個體。這個序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個體s的適應(yīng)度，從而適應(yīng)度函數(shù)就是四、遺傳算法應(yīng)用舉例2第四十七頁，共六十九頁，2022年，8月28日

（2）對個體s=（c1,c2,…,cn,cn+1）進行編碼。但對于這樣的個體如何編碼卻不是一件直截了當?shù)氖虑椤Ｒ驗槿绻幋a不當，就會在實施交叉或變異操作時出現(xiàn)非法城市序列即無效解。例如，對于5個城市的TSP，我們用符號A、B、C、D、E代表相應(yīng)的城市，用這5個符號的序列表示可能解即染色體。四、遺傳算法應(yīng)用舉例2第四十八頁，共六十九頁，2022年，8月28日然后進行遺傳操作。設(shè)s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）實施常規(guī)的交叉或變異操作，如交換后三位，得s1’=（A,C,B,C,B,A），s2’=（A,E,D,E,D,A）或者將染色體s1第二位的C變?yōu)镋，得s1’’=（A,E,B,E,D,A）可以看出，上面得到的s1’，s2’和s1’’都是非法的城市序列。四、遺傳算法應(yīng)用舉例2第四十九頁，共六十九頁，2022年，8月28日為此，對TSP必須設(shè)計合適的染色體和相應(yīng)的遺傳運算。事實上，人們針對TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如順序編碼或整數(shù)編碼、隨機鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異等等。從而巧妙地用遺傳算法解決了TSP。四、遺傳算法應(yīng)用舉例2第五十頁，共六十九頁，2022年，8月28日為四個連鎖飯店尋找最好的經(jīng)營決策，其中一個經(jīng)營飯店的決策包括要做出以下三項決定：（1）價格漢堡包的價格應(yīng)該定在50美分還是1美元？（2）飲料和漢堡包一起供應(yīng)的應(yīng)該是酒還是可樂？（3）服務(wù)速度飯店應(yīng)該提供慢的還是快的服務(wù)？目的：找到這三個決定的組合以產(chǎn)生最高的利潤。上述問題的表示方案：共有8種表示方案用遺傳算法解這個問題的第一步就是選取一個適當?shù)谋硎痉桨浮Ｋ摹⑦z傳算法應(yīng)用舉例3第五十一頁，共六十九頁，2022年，8月28日飯店編號價格飲料速度二進制表示1高可樂快0112高酒快0013低可樂慢1104高可樂慢010表1飯店問題的表示方案（其中的4個）群體規(guī)模N＝4四、遺傳算法應(yīng)用舉例3第五十二頁，共六十九頁，2022年，8月28日第0代i串xi適應(yīng)值f（xi）10113200113110640102總和12最小值1平均值3.00最大值6表2初始群體中經(jīng)營決策的適應(yīng)值一個簡單的遺傳算法由復(fù)制、雜交、變異三個算子組成四、遺傳算法應(yīng)用舉例3第五十三頁，共六十九頁，2022年，8月28日第0代復(fù)制i串xi適應(yīng)值f（xi）f（xi）/f（xi）串f（xi）101130.250113200110.081106311060.501106401020.170102總和1217最小值12平均值3.004.25最大值66表3使用復(fù)制算子后產(chǎn)生的交叉1.復(fù)制算子：采用賭盤選擇第五十四頁，共六十九頁，2022年，8月28日2.雜交算子：采用一點交叉從交配池中選擇編號為1和2的串進行配對，且雜交點選在2（用分隔符|表示），雜交算子作用的結(jié)果為：01|

101011|0111對交配池中指定百分比的個體應(yīng)用雜交算子，假設(shè)交叉概率pc＝50％，交配池中余下的50％個體僅進行復(fù)制運算，即復(fù)制概率pr＝50％。第五十五頁，共六十九頁，2022年，8月28日第0代復(fù)制第1代i串xi適應(yīng)值f(xi)f（xi）/f(xi)串f（xi）交叉點xif（xi）101130.25011320102200110.08110621117311060.501106－1106401020.170102－0102總和121717最小值122平均值3.004.254.25最大值667表4使用復(fù)制和雜交算子的作用結(jié)果遺傳算法利用復(fù)制和雜交算子可以產(chǎn)生具有更高平均適應(yīng)值和更好個體的群體第五十六頁，共六十九頁，2022年，8月28日課堂練習(xí)設(shè)有6個個體，分別具有滿足度值5，10，15，25，50，100.試用指針輪盤法計算每個個體的復(fù)制次數(shù)。第五十七頁，共六十九頁，2022年，8月28日五、遺傳算法的理論基礎(chǔ)設(shè)滿足度函數(shù)為f(x),在遺傳算法中每一次迭代時，每一代個體的總數(shù)為m，每個個體的編碼長度為n，第g次迭代中的個體j的編碼為：遺傳算法的數(shù)學(xué)描述Xg,j=(x1g,j,x2g,j,…xng,j),j=1,2,…m,g=0,1,…

第五十八頁，共六十九頁，2022年，8月28日復(fù)制第五十九頁，共六十九頁，2022年，8月28日基因交換第六十頁，共六十九頁，2022年，8月28日基因突變第六十一頁，共六十九頁，2022年，8月28日1、綱——是一個相同的構(gòu)形，它描述的是一個串的子集，這個集合中串之間在某些位上相同。

例如，添加符號*表示不確定字母，即0或1，考慮串長為7的模式H＝*11*0**，則串A＝0111000是模式H的一個表示，對于基數(shù)為k的字母表，每一個串有（k＋1）l個模式。2、綱的階數(shù)——出現(xiàn)在模式中確定位置的數(shù)目。在二進制中，一個模式的階就是所有的1或0的數(shù)目。例如，模式H＝*11*0**的階為33、綱的定義長度——模式中第一個確定位置與最后一個確定位置之間的距離例如，模式H＝*11*0**的定義長度r＝5－2＝3五、遺傳算法的理論基礎(chǔ)