遺傳算法最新版本課件(PPT 70頁)

1、遺傳算法原理與應(yīng)用趙 鵬1.第1頁，共70頁。1.遺傳算法起源 遺傳算法是由美國的J.Holland教授于1975年在他的專著自然界和人工系統(tǒng)的適應(yīng)性中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。 一、基本原理 2.第2頁，共70頁。生物進(jìn)化循環(huán)圖3.第3頁，共70頁。生物遺傳概念在遺傳算法中的對應(yīng)關(guān)系生物遺傳概念遺傳算法中的作用適者生存在算法停止時，最優(yōu)目標(biāo)值的解有最大的可能被保留個體(individual)解染色體(chromosome)解的編碼（字符串，向量等）基因(gene)解中每一分量的特征（如各分量的值）適應(yīng)性(fitness)適應(yīng)函數(shù)值群體(popula

2、tion)選定的一組解（其中解的個數(shù)為群體的規(guī)模）種群(reproduction)根據(jù)適應(yīng)函數(shù)值選取的一組解交配(crossover)通過交配原則產(chǎn)生一組新解的過程變異(mutation)編碼的某一個分量發(fā)生變化的過程4.第4頁，共70頁。遺傳算法的主要特征： 進(jìn)化發(fā)生在解的編碼上，這些編碼按生物學(xué)的術(shù)語稱為染色體。由于對解進(jìn)行了編碼，優(yōu)化問題的一切性質(zhì)都通過編碼來研究。編碼和解碼是遺傳算法的一個主題。 自然選擇規(guī)律決定哪些染色體產(chǎn)生超過平均數(shù)的后代。遺傳算法中，通過優(yōu)化問題的目標(biāo)而人為地構(gòu)造適應(yīng)函數(shù)以達(dá)到好的染色體產(chǎn)生超過平均數(shù)的后代。 當(dāng)染色體結(jié)合時，雙親的遺傳基因的結(jié)合使得子女保持父母的

3、特征。 當(dāng)染色體結(jié)合后，隨機(jī)的變異會造成子代同父代的不同。 5.第5頁，共70頁。遺傳算法主要處理步驟 首先是對優(yōu)化問題的解進(jìn)行編碼，稱一個解的編碼為一個染色體，組成編碼的元素稱為基因。編碼的目的主要是用于優(yōu)化問題解的表現(xiàn)形式和利于之后遺傳算法中的計(jì)算。 第二是適應(yīng)函數(shù)的構(gòu)造和應(yīng)用。適應(yīng)函數(shù)基本上依據(jù)優(yōu)化問題的目標(biāo)函數(shù)而定。當(dāng)適應(yīng)函數(shù)確定以后，自然選擇規(guī)律是以適應(yīng)函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰。生存下來的染色體組成種群，形成一個可以繁衍下一代的群體。 第三是染色體的結(jié)合。雙親的遺傳基因結(jié)合是通過編碼之間的交配達(dá)到下一代的產(chǎn)生。新一代的產(chǎn)生是一個生殖過程，它產(chǎn)生了

4、一個新解。 最后是變異。新解產(chǎn)生過程中可能發(fā)生基因變異，變異使某些解的編碼發(fā)生變化，使解有更大的遍歷性。 6.第6頁，共70頁。2、基本遺傳算法 基本遺傳算法（Simple Genetic Algorithms，簡稱SGA，又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。 基本遺傳算法的組成 （1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運(yùn)行參數(shù)7.第7頁，共70頁。函數(shù)優(yōu)化示例 求下列一元函數(shù)的最大值：x-1,2 ，求解結(jié)果精確到6位小數(shù)。 GA是通過某種

5、編碼機(jī)制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進(jìn)制串進(jìn)行編碼。 編碼 8.第8頁，共70頁。SGA對于本例的編碼 由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3106等份。又因?yàn)?21 3106 222 ，所以本例的二進(jìn)制編碼長度至少需要22位，本例的編碼過程實(shí)質(zhì)上是將區(qū)間-1，2內(nèi)對應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個二進(jìn)制串（b21b20b0）。9.第9頁，共70頁。幾個術(shù)語 基因型：1000101110110101000111 表現(xiàn)型：0.637197 編碼解碼個體（染色體）基因10.第10頁，共70頁

6、。初始種群 SGA采用隨機(jī)方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。 適應(yīng)度函數(shù) 遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。 11.第11頁，共70頁。選擇算子 遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對群體中的個體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法

7、。 12.第12頁，共70頁。輪盤賭選擇示意s40.31s20.49s10.14s30.06輪盤賭選擇法13.第13頁，共70頁。輪盤賭選擇方法 輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n ，個體i 的適應(yīng)度為 Fi，則個體i 被選中遺傳到下一代群體的概率為： 14.第14頁，共70頁。輪盤賭選擇方法的實(shí)現(xiàn)步驟（1） 計(jì)算群體中所有個體的適應(yīng)度函數(shù)值（需要解碼）；（2） 利用比例選擇算子的公式，計(jì)算每個個體被選中遺傳到下一代群體的概率；（3） 采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個個體遺傳到下一代群體的概率進(jìn)行匹配）來確

8、定各個個體是否遺傳到下一代群體中。15.第15頁，共70頁。交叉算子 所謂交叉運(yùn)算，是指對兩個相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。 SGA中交叉算子采用單點(diǎn)交叉算子。 16.第16頁，共70頁。單點(diǎn)交叉運(yùn)算 交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點(diǎn)17.第17頁，共70頁。變異算子

9、所謂變異運(yùn)算，是指依據(jù)變異概率 Pm 將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。 SGA中變異算子采用基本位變異算子。 18.第18頁，共70頁?；疚蛔儺愃阕?基本位變異算子是指對個體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對于基本遺傳算法中用二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)? 。 1

10、9.第19頁，共70頁?；疚蛔儺愃阕拥膱?zhí)行過程 變異前：000001110000000010000變異后：000001110001000010000變異點(diǎn)20.第20頁，共70頁。運(yùn)行參數(shù) （1）M ： 種群規(guī)模 （2）T ： 遺傳運(yùn)算的終止進(jìn)化代數(shù) （3）Pc ： 交叉概率 （4）Pm ： 變異概率 21.第21頁，共70頁。初始種群.第22頁，共70頁。遺傳算法應(yīng)用舉例 利用遺傳算法求解區(qū)間0,31上的二次函數(shù)y=x2的最大值。y=x2 31 XY23.第23頁，共70頁。 分析 原問題可轉(zhuǎn)化為在區(qū)間0, 31中搜索能使y取最大值的點(diǎn)a的問題。那么，0, 31 中的點(diǎn)x就是個體, 函數(shù)值

11、f(x)恰好就可以作為x的適應(yīng)度，區(qū)間0, 31就是一個(解)空間 。這樣, 只要能給出個體x的適當(dāng)染色體編碼, 該問題就可以用遺傳算法來解決。24.第24頁，共70頁。解(1) 設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。 將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個體組成初始種群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定義適應(yīng)度函數(shù), 取適應(yīng)度函數(shù)：f (x)=x2 25.第25頁，共70頁。(3) 計(jì)算各代種群中的各個體的適應(yīng)度, 并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個體(即31

12、（11111）)出現(xiàn)為止。 26.第26頁，共70頁。 首先計(jì)算種群S1中各個體 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的適應(yīng)度f (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 36127.第27頁，共70頁。再計(jì)算種群S1中各個體的選擇概率。選擇概率的計(jì)算公式為 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24)

13、 = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.3128.第28頁，共70頁。 賭輪選擇示意s40.31s20.49s10.14s30.06 賭輪選擇法29.第29頁，共70頁。在算法中賭輪選擇法可用下面的子過程來模擬: 在0, 1區(qū)間內(nèi)產(chǎn)生一個均勻分布的隨機(jī)數(shù)r。 若rq1,則染色體x1被選中。 若qk-1rqk(2kN), 則染色體xk被選中。 其中的qi稱為染色體xi (i=1, 2, , n)的積累概率, 其計(jì)算公式為 30.第30頁，共70頁。選擇-復(fù)制 設(shè)從區(qū)間0, 1中產(chǎn)生4個隨機(jī)數(shù)如下: r1 = 0.450126, r2 = 0.1

14、10347 r3 = 0.572496, r4 = 0.98503 染色體 適應(yīng)度選擇概率積累概率選中次數(shù)s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 131.第31頁，共70頁。于是，經(jīng)復(fù)制得群體：s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 32.第32頁，共70頁。交叉 設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。 設(shè)s1與s2配對，s3與s4配對。分別交換后兩位

15、基因，得新染色體： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）33.第33頁，共70頁。變異 設(shè)變異率pm=0.001。 這樣，群體S1中共有 540.001=0.02位基因可以變異。 0.02位顯然不足1位，所以本輪遺傳操作不做變異。34.第34頁，共70頁。 于是，得到第二代種群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）35.第35頁，共70頁。 第二代種群S2中各染色體的情況 染色體 適應(yīng)度選擇概率積累概率 估計(jì)的選中次數(shù)s1=11001 625 0.3

16、6 0.36 1s2=01100 144 0.08 0.44 1s3=11011 729 0.41 0.85 1s4=10000 256 0.15 1.00 136.第36頁，共70頁。 假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個染色體都被選中，則得到群體： 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ā)生變異。 37.第37頁，共7

17、0頁。于是，得第三代種群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=10011（19） 38.第38頁，共70頁。 第三代種群S3中各染色體的情況 染色體 適應(yīng)度選擇概率積累概率 估計(jì)的選中次數(shù)s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 139.第39頁，共70頁。 設(shè)這一輪的選擇-復(fù)制結(jié)果為： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19）

18、做交叉運(yùn)算，讓s1與s4，s2與s3 分別交換后兩位基因，得 s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 這一輪仍然不會發(fā)生變異。40.第40頁，共70頁。 于是，得第四代種群S4： s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 41.第41頁，共70頁。 顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。 將31代入函數(shù)y=x2

19、中，即得原問題的解，即函數(shù)y=x2的最大值為961。 42.第42頁，共70頁。YYy=x2 8 13 19 24 X第一代種群及其適應(yīng)度y=x2 12 16 25 27 XY第二代種群及其適應(yīng)度y=x2 9 19 24 28 XY第三代種群及其適應(yīng)度y=x2 16 24 28 31 X第四代種群及其適應(yīng)度43.第43頁，共70頁。遺傳算法的描述Step1 選擇問題的一個編碼；給出一個有N個染色體的初始群體pop(1),t:=1;Step2 對群體pop(t)中的每一個染色體popi(t)計(jì)算它的適應(yīng)函數(shù) fi=fitness(popi(t);Step3 若停止規(guī)則滿足，則算法停止；否則，計(jì)算

20、概率 Pi=fi/fi ,i=1,2,N并以概率從pop(t)中隨機(jī)選一些染色體構(gòu)成一個新的種群Newpop(t+1)=pop(t)|j=1,2,N;Step4 通過交配，交配概率為pc，得到一個有N個染色體的crosspop(t+1);Step5 以較小概率pm，使得一個染色體的基因發(fā)生變異，形成mutpop(t+1);t:=t+1,一個新的體群pop(t)=mutpop(t);返回step2.44.第44頁，共70頁。3、遺傳算法的特點(diǎn) （1）群體搜索，易于并行化處理； （2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。45.第45頁，共70頁。

21、二、理論基礎(chǔ)1、遺傳算法的數(shù)學(xué)基礎(chǔ) 2、遺傳算法的收斂性分析 3、遺傳算法的改進(jìn) 46.第46頁，共70頁。1、遺傳算法的數(shù)學(xué)基礎(chǔ)（1）模式定理 （2）積木塊假設(shè) 模式是指種群個體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，即 0 或者 1。 模式示例：10*1模式47.第47頁，共70頁。兩個定義定義1：模式 H 中確定位置的個數(shù)稱為模式 H 的階，記作O(H)。例如O(10*1)=3 。定義2：模式 H 中第一個確定位置和最后一個確定位置之間的距離稱為模式 H 的定義距，記作(H)。例如(10*

22、1)=4 。 模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 模式的階和定義距的含義48.第48頁，共70頁。模式定理 模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。 從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有更多的復(fù)制，交叉算子不容易破

23、壞高頻率出現(xiàn)的、短定義距的模式，而一般突變概率又相當(dāng)小，因而它對這些重要的模式幾乎沒有影響。 49.第49頁，共70頁。積木塊假設(shè) 積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。 定理 若參數(shù)滿足：變異概率0pm1,交配概率0pc 1,則簡單遺傳算法不收斂于全局最優(yōu)解。50.第50頁，共70頁。2、遺傳算法的收斂性分析 遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最

24、優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。 定理 如果改進(jìn)簡單遺傳算法按交配、變異、種群選取之后更新當(dāng)前最優(yōu)染色體的進(jìn)化循環(huán)過程，則收斂于全局最優(yōu)解。 改進(jìn)遺傳算法：進(jìn)化的每一代中，記錄前面各代最優(yōu)解并存放在群體的第一位，這個染色體不參與遺傳運(yùn)算。51.第51頁，共70頁。種群規(guī)模對收斂性的影響 通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計(jì)算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳

25、算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。選擇操作對收斂性的影響52.第52頁，共70頁。交叉概率對收斂性的影響 交叉操作用于個體對，產(chǎn)生新的個體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。 變異概率對收斂性的影響 變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法

26、。 53.第53頁，共70頁。遺傳算法的本質(zhì) 遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。 54.第54頁，共70頁。GA的局限性 在于 GA在進(jìn)化搜索過程中， 每代總要維持一定規(guī)模的群體，若群體規(guī)模太小，含有的信息量也少，不能使算法得到充分發(fā)揮，若群體規(guī)模大，包含的信息量也大，但計(jì)算次數(shù)會激劇增加，因而限制了算法的使用。 GA的另一個不足之處是“早熟”。造成這種成熟前收斂的原因，一方面是 GA中最重要的遺傳算子交叉算

27、子使群體中的染色體具有局部相似性，父代染色體的信息交換量小，從而使搜索停滯不前；另一方面是變異概率又太小，以至于不能使搜索轉(zhuǎn)向其它的解空間進(jìn)行搜索。 GA的爬山能力差，也是由于變異概率低造成的。55.第55頁，共70頁。3、遺傳算法的改進(jìn) 遺傳欺騙問題：在遺傳算法進(jìn)化過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運(yùn)算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個局部最優(yōu)解。 56.第56頁，共70頁。遺傳算法的改進(jìn)途徑（1）對編碼方式的改進(jìn) （2）對遺傳算子的改進(jìn)（3）對控制參數(shù)的改進(jìn) （4）對執(zhí)行策略的改進(jìn) 57.第57頁，共70頁。對編碼方式的改進(jìn) 二進(jìn)制編碼優(yōu)點(diǎn)

28、在于編碼、解碼操作簡單，交叉、變異等操作便于實(shí)現(xiàn)，缺點(diǎn)在于精度要求較高時，個體編碼串較長，使算法的搜索空間急劇擴(kuò)大，遺傳算法的性能降低。格雷編碼克服了二進(jìn)制編碼的不連續(xù)問題，浮點(diǎn)數(shù)編碼改善了遺傳算法的計(jì)算復(fù)雜性 。 58.第58頁，共70頁。TSP問題的基本遺傳算法(1) 編碼 自然數(shù)編碼，i1i2i3in(2) 適應(yīng)度函數(shù) fi ：巡回路長度的倒數(shù)(3)選擇操作 繁殖池； 賭輪選擇 (4)雜交算子 例，基于位置的雜交 父代1：1 2 3 4 5 6 7 8 9 10 父代2：5 9 2 4 6 1 10 7 3 8 所選位置 * * * * 子代1：1 9 2 3 6 4 5 7 8 10

29、子代2：9 2 3 4 5 6 1 8 10 7 (5) 變異算子 例，基于位置的變異、基于次序的變異、打亂變異59.第59頁，共70頁。對遺傳算子的改進(jìn)排序選擇 均勻交叉 逆序變異（1） 對群體中的所有個體按其適應(yīng)度大小進(jìn)行降序排序；（2） 根據(jù)具體求解問題，設(shè)計(jì)一個概率分配表，將各個概率值按上述排列次序分配給各個個體；（3） 以各個個體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。 60.第60頁，共70頁。對遺傳算子 的改進(jìn)排序選擇 均勻交叉 逆序變異（1） 隨機(jī)產(chǎn)生一個與個體編碼長度相同的二進(jìn)制屏蔽字P = W1W2Wn ；（2） 按下列規(guī)則從A、B兩個父代個體中產(chǎn)生兩個新個體X、Y：若Wi = 0，則X的第i個基因繼承A的對應(yīng)基因，Y的第i個基因繼承B的對應(yīng)基因；若Wi = 1，則A、B的第i個基因相互交換，從而生成X、Y的第i個基因。 61.第61頁，共70頁。對遺傳算子的改進(jìn)排序選擇 均勻交叉 逆序變異變異前：3 4 8 | 7 9 6 5 | 2 1變異后：3 4 8 | 5 6 9 7 | 2 162.第62頁，共70頁。對控制參數(shù)的改進(jìn) Schaffer建議的最優(yōu)參數(shù)范圍是： M = 20-100， T =