遺傳算法簡述

關(guān)于遺傳算法簡述

遺傳算法（GeneticAlgorithm）●遺傳算法（GeneticAlgorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法?！褡畛跤擅绹鳰ichigan大學(xué)J.Holland教授于1975年首先提出來，并出版了頗有影響的專著《AdaptationinNaturalandArtificialSystems》，GA這個(gè)名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳算法（SGA）。第2頁,共80頁，2024年2月25日，星期天

1.1基本概念

1.個(gè)體與種群

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

●

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

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

●

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

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

第4頁,共80頁，2024年2月25日，星期天3.染色體與基因

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

9----

1001

（2，5，6）----010101110第5頁,共80頁，2024年2月25日，星期天4.遺傳操作

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

●

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

●

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

●

變異(mutation，亦稱突變)

第6頁,共80頁，2024年2月25日，星期天

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

這里的選擇概率P(xi)的計(jì)算公式為第7頁,共80頁，2024年2月25日，星期天

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

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

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

交換其后4位基因,即第8頁,共80頁，2024年2月25日，星期天

變異就是改變?nèi)旧w某個(gè)(些)位上的基因。例如,設(shè)染色體s=11001101將其第三位上的0變?yōu)?,即s=11001101→11101101=s′。s′也可以看做是原染色體s的子代染色體。第9頁,共80頁，2024年2月25日，星期天1.2基本遺傳算法

遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束第10頁,共80頁，2024年2月25日，星期天

算法中的一些控制參數(shù)：

■

種群規(guī)模

■

最大換代數(shù)

■

交叉率(crossoverrate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4～0.99。

■

變異率(mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.1。第11頁,共80頁，2024年2月25日，星期天

基本遺傳算法

步1

在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；

步2

隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計(jì)數(shù)器t=1；

步3

計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f()；

步4

若終止條件滿足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。第12頁,共80頁，2024年2月25日，星期天

步5按選擇概率P(xi)所決定的選中機(jī)會，每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1；

步6按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；第13頁,共80頁，2024年2月25日，星期天

步7

按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；

步8

將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；

第14頁,共80頁，2024年2月25日，星期天1.3遺傳算法應(yīng)用舉例

例4.1

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

y=x2

31

XY第15頁,共80頁，2024年2月25日，星期天

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。那么，［0,31］中的點(diǎn)x就是個(gè)體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(gè)(解)空間。這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。第16頁,共80頁，2024年2月25日，星期天

解

(1)

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

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

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

第17頁,共80頁，2024年2月25日，星期天

(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。

第18頁,共80頁，2024年2月25日，星期天首先計(jì)算種群S1中各個(gè)體

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第19頁,共80頁，2024年2月25日，星期天再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31第20頁,共80頁，2024年2月25日，星期天

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法第21頁,共80頁，2024年2月25日，星期天

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計(jì)算公式為第22頁,共80頁，2024年2月25日，星期天選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001第23頁,共80頁，2024年2月25日，星期天于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）第24頁,共80頁，2024年2月25日，星期天交叉

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

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

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

第25頁,共80頁，2024年2月25日，星期天變異設(shè)變異率pm=0.001。這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位，所以本輪遺傳操作不做變異。第26頁,共80頁，2024年2月25日，星期天

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

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

s3=11011（27）,s4=10000（16）第27頁,共80頁，2024年2月25日，星期天

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

染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001第28頁,共80頁，2024年2月25日，星期天

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：

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

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

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得

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

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

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

第29頁,共80頁，2024年2月25日，星期天于是，得第三代種群S3：

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

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

第30頁,共80頁，2024年2月25日，星期天

第三代種群S3中各染色體的情況

染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001第31頁,共80頁，2024年2月25日，星期天

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

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

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

做交叉運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得

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

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

這一輪仍然不會發(fā)生變異。第32頁,共80頁，2024年2月25日，星期天

于是，得第四代種群S4：

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

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

第33頁,共80頁，2024年2月25日，星期天顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。

第34頁,共80頁，2024年2月25日，星期天YYy=x2

8131924

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

12162527

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

9192428

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

16242831

X第四代種群及其適應(yīng)度第35頁,共80頁，2024年2月25日，星期天

例1.2

用遺傳算法求解TSP。分析

由于其任一可能解——一個(gè)合法的城市序列，即n個(gè)城市的一個(gè)排列，都可以事先構(gòu)造出來。于是，我們就可以直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。第36頁,共80頁，2024年2月25日，星期天

（1）定義適應(yīng)度函數(shù)我們將一個(gè)合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體s的適應(yīng)度，從而適應(yīng)度函數(shù)就是第37頁,共80頁，2024年2月25日，星期天

（2）對個(gè)體s=（c1,c2,…,cn,cn+1）進(jìn)行編碼。但對于這樣的個(gè)體如何編碼卻不是一件直截了當(dāng)?shù)氖虑?。因?yàn)槿绻幋a不當(dāng)，就會在實(shí)施交叉或變異操作時(shí)出現(xiàn)非法城市序列即無效解。例如，對于5個(gè)城市的TSP，我們用符號A、B、C、D、E代表相應(yīng)的城市，用這5個(gè)符號的序列表示可能解即染色體。第38頁,共80頁，2024年2月25日，星期天然后進(jìn)行遺傳操作。設(shè)

s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）實(shí)施常規(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’’都是非法的城市序列。第39頁,共80頁，2024年2月25日，星期天

為此，對TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算。事實(shí)上，人們針對TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異等等。從而巧妙地用遺傳算法解決了TSP。第40頁,共80頁，2024年2月25日，星期天遺傳算法2.1遺傳算法特點(diǎn)2.2遺傳算法的數(shù)學(xué)基礎(chǔ)2.3遺傳算法的收斂性分析2.4遺傳算法改進(jìn)2.5遺傳算法的融合

第41頁,共80頁，2024年2月25日，星期天2.1遺傳算法的特點(diǎn)與優(yōu)勢

◆傳統(tǒng)優(yōu)化算法

-枚舉法：枚舉出可行解集合內(nèi)的所有可行解，以求出精確最優(yōu)解。 *對于連續(xù)函數(shù)，要求先進(jìn)行離散化處理。枚舉空間比較大時(shí)，方法求解效率較低，甚至無法求解。

第42頁,共80頁，2024年2月25日，星期天

-啟發(fā)式算法：尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，已找到一個(gè)最優(yōu)解或近似最優(yōu)解。 *該方法的求解效率比較高，但對每一個(gè)需求解的問題必須找出其特有的啟發(fā)式規(guī)則，這個(gè)啟發(fā)式規(guī)則一般無通用性，不適合于其他問題。第43頁,共80頁，2024年2月25日，星期天

-搜索算法：尋求一種搜索算法，該算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作，已找到問題的最優(yōu)解或近似最優(yōu)解。 *該方法雖然保證不了能夠獲得問題的最優(yōu)解，但若適當(dāng)?shù)乩靡恍﹩l(fā)式規(guī)則，就可以在近似解的質(zhì)量和效率上達(dá)到一種較好的平衡。第44頁,共80頁，2024年2月25日，星期天

◆遺傳算法的主要特點(diǎn)

——遺傳算法一般是直接在解空間搜索,而不像圖搜索那樣一般是在問題空間搜索,最后才找到解，因而可以更加直接地應(yīng)用。

——遺傳算法是一種隨機(jī)搜索算法，搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集，避免使得算法總是陷入到相同的局部極小點(diǎn)（局部最優(yōu)值）。

第45頁,共80頁，2024年2月25日，星期天

——遺傳算法采用適應(yīng)度函數(shù)和遺傳操作，從而設(shè)法盡快找到解,所以遺傳算法又是一種優(yōu)化搜索算法?！z傳算法的搜索過程是從空間的一個(gè)點(diǎn)集(種群)到另一個(gè)點(diǎn)集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。因而它實(shí)際是一種并行搜索,適合大規(guī)模并行計(jì)算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。第46頁,共80頁，2024年2月25日，星期天

——遺傳算法的適應(yīng)性強(qiáng),除需知適應(yīng)度函數(shù)外,幾乎不需要其他的先驗(yàn)知識。

——遺傳算法長于全局搜索,它不受搜索空間的限制性假設(shè)的約束,不要求連續(xù)性,能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解。 ——遺傳算法對應(yīng)給定問題，可產(chǎn)生許多潛在解，并可由使用者來確定最終解。第47頁,共80頁，2024年2月25日，星期天2.2遺傳算法的數(shù)學(xué)基礎(chǔ)模式定理積木塊假設(shè)第48頁,共80頁，2024年2月25日，星期天模式是指種群個(gè)體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個(gè)字符集(0,1,*)的字符串，符號*代表任意字符，即0或者1。對于二進(jìn)制編碼串，當(dāng)串長為l時(shí)，共有3l個(gè)不同的模式，遺傳算法中串的運(yùn)算實(shí)際上是模式的運(yùn)算。模式示例：*1* 表示四元子集{010，011，110，111}第49頁,共80頁，2024年2月25日，星期天與模式0******相比，模式011***1在相似性方面有更明確的表示；模式0*0***與模式0****0相比要跨越整個(gè)串長更大的部分。定義1：模式H中確定位置的個(gè)數(shù)稱為模式H的階，記作O(H)。例如O(10**1)=3。定義2：模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如δ(10**1*)=4。第50頁,共80頁，2024年2月25日，星期天模式的階和定義距的含義：模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。第51頁,共80頁，2024年2月25日，星期天模式定理模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。第52頁,共80頁，2024年2月25日，星期天從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有更多的復(fù)制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當(dāng)小，因而它對這些重要的模式幾乎沒有影響。第53頁,共80頁，2024年2月25日，星期天積木塊假設(shè)：積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。第54頁,共80頁，2024年2月25日，星期天2.3遺傳算法的收斂性分析遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。第55頁,共80頁，2024年2月25日，星期天種群規(guī)模對收斂性的影響通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計(jì)算量，造成收斂時(shí)間太長，表現(xiàn)為收斂速度緩慢。第56頁,共80頁，2024年2月25日，星期天選擇操作對收斂性的影響選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。第57頁,共80頁，2024年2月25日，星期天交叉概率對收斂性的影響交叉操作用于個(gè)體對，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時(shí)，種群中個(gè)體更新很快，會造成高適應(yīng)度值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。第58頁,共80頁，2024年2月25日，星期天變異概率對收斂性的影響變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。第59頁,共80頁，2024年2月25日，星期天遺傳算法的本質(zhì)遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。第60頁,共80頁，2024年2月25日，星期天2.4遺傳算法的改進(jìn)

自從1975年J.H.Holland系統(tǒng)提出遺傳算法的完整結(jié)構(gòu)和理論以來，眾多學(xué)者一直致力于推動遺傳算法的發(fā)展，對編碼方式、控制參數(shù)的確定、選擇方式和交叉機(jī)理等進(jìn)行了深入研究，引入了動態(tài)策略和自適應(yīng)策略以改善遺傳算法的性能，提出了各種變形的遺傳算法。第61頁,共80頁，2024年2月25日，星期天

基本改進(jìn)途徑概括起來包括改變遺傳算法的組成成分或使用技術(shù)，如選用優(yōu)化控制參數(shù)、適合問題特性的編碼技術(shù)等采用混合遺傳算法采用動態(tài)自適應(yīng)技術(shù)，在進(jìn)化過程中調(diào)整算法控制參數(shù)和編碼粒度采用非標(biāo)準(zhǔn)的遺傳操作算子采用并行遺傳算法第62頁,共80頁，2024年2月25日，星期天對編碼方式的改進(jìn)二進(jìn)制編碼優(yōu)點(diǎn)在于編碼、解碼操作簡單，交叉、變異等操作便于實(shí)現(xiàn)，缺點(diǎn)在于精度要求較高時(shí)，個(gè)體編碼串較長，使算法的搜索空間急劇擴(kuò)大，遺傳算法的性能降低。格雷編碼克服了二進(jìn)制編碼的不連續(xù)問題，浮點(diǎn)數(shù)編碼改善了遺傳算法的計(jì)算復(fù)雜性。第63頁,共80頁，2024年2月25日，星期天對遺傳算子的改進(jìn)排序選擇均勻交叉逆序變異（1）對群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行降序排序；（2）根據(jù)具體求解問題，設(shè)計(jì)一個(gè)概率分配表，將各個(gè)概率值按上述排列次序分配給各個(gè)個(gè)體；（3）以各個(gè)個(gè)體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。第64頁,共80頁，2024年2月25日，星期天對遺傳算子的改進(jìn)排序選擇均勻交叉逆序變異（1）隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼長度相同的二進(jìn)制屏蔽字P=W1W2…Wn

；（2）按下列規(guī)則從A、B兩個(gè)父代個(gè)體中產(chǎn)生兩個(gè)新個(gè)體X、Y：若Wi=0，則X的第i個(gè)基因繼承A的對應(yīng)基因，Y的第i個(gè)基因繼承B的對應(yīng)基因；若Wi=1，則A、B的第i個(gè)基因相互交換，從而生成X、Y的第i個(gè)基因。第65頁,共80頁，2024年2月25日，星期天對遺傳算子的改進(jìn)排序選擇均勻交叉逆序變異變異前：348|7965|21變異前：348|5697|21第66頁,共80頁，2024年2月25日，星期天對控制參數(shù)的改進(jìn)Schaffer建議的最優(yōu)參數(shù)范圍是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

第67頁,共80頁，2024年2月25日，星期天對控制參數(shù)的改進(jìn)Srinvivas等人提出自適應(yīng)遺傳算法，即PC和Pm能夠隨適應(yīng)度自動改變，當(dāng)種群的各個(gè)個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使二者增加，而當(dāng)種群適應(yīng)度比較分散時(shí)，使二者減小，同時(shí)對適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，采用較低的PC和Pm，使性能優(yōu)良的個(gè)體進(jìn)入下一代，而低于平均適應(yīng)值的個(gè)體，采用較高的PC和Pm，使性能較差的個(gè)體被淘汰。第68頁,共80頁，2024年2月25日，星期天對執(zhí)行策略的改進(jìn)混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法第69頁,共80頁，2024年2月25日，星期天分層遺傳算法

分層遺傳算法基本流程框圖初始化N個(gè)子種群N個(gè)子種群獨(dú)立運(yùn)行遺傳算法一定代數(shù)N個(gè)結(jié)果種群及平均適應(yīng)度值記錄到R[1...N,1...n]及A[i]對R[1...N,1...n]進(jìn)行選擇和交叉對R[1...N,1...n]進(jìn)行變異操作對新的N個(gè)子種群重新開始遺傳算法操作性能滿足?結(jié)束第70頁,共80頁，2024年2月25日，星期天并行遺傳算法（parallelGA，PGA）遺傳算法中適應(yīng)度的計(jì)算最費(fèi)時(shí)間，再加上需要不斷產(chǎn)生新一代，而每一代又有若干個(gè)個(gè)體，隨意如何提高遺傳算法的運(yùn)行速率顯得尤為突出。由于遺傳算法的內(nèi)在并行機(jī)制，其并行處理是很自然的解決途徑。并行遺傳算法的實(shí)現(xiàn)方案全局型——主從式模式（master-slavemodel）獨(dú)立型——粗粒度模型（coarse-grainedmodel）；孤島模型；分布式遺傳算法分散型——細(xì)粒度模型（fine-