數(shù)學(xué)建模專題之遺傳算法要求

1、數(shù)學(xué)建模專題之遺傳算法要求Contents遺傳算法概述1標(biāo)準(zhǔn)遺傳算法2遺傳算法簡(jiǎn)單舉例：函數(shù)極值3遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)5遺傳算法求解TSP問(wèn)題4遺傳算法的實(shí)現(xiàn)6Contents of Section 1什么是遺傳算法遺傳算法的特點(diǎn)遺傳算法的發(fā)展歷程遺傳算法的研究和應(yīng)用領(lǐng)域1 遺傳算法概述1 遺傳算法概述1.1 遺傳算法（Genetic Algorithm, GA）一種仿生全局優(yōu)化算法模仿生物的遺傳進(jìn)化原理（Darwins theory of evolution & Mendels law of inheritance)，通過(guò)選擇（Selection）、交叉（Crossover）與變異（Muta

2、tion）等操作機(jī)制，使種群中個(gè)體的適應(yīng)性（Fitness）不斷提高核心思想：物競(jìng)天擇，適者生存 （“天”適應(yīng)度函數(shù)，F(xiàn)itness Function)1 遺傳算法概述 遺傳算法的特點(diǎn)四大優(yōu)點(diǎn)：良好的并行性（操作對(duì)象是一組可行解；搜索軌道有多條）強(qiáng)大的通用性（只需利用目標(biāo)的取值信息，無(wú)需梯度等高價(jià)值信息）良好的全局優(yōu)化性和魯棒性良好的可操作性兩個(gè)缺點(diǎn)：未成熟收斂問(wèn)題收斂速度較慢，算法實(shí)時(shí)性欠佳1 遺傳算法概述 遺傳算法的發(fā)展歷史年份貢獻(xiàn)者內(nèi)容1962Holland程序漫游元胞計(jì)算機(jī)自適應(yīng)系統(tǒng)框架1968Holland模式定理的建立1971Hollstein具有交配和選擇規(guī)則的二維函數(shù)優(yōu)化197

3、2BosworthFoo, Zeigler提出具有復(fù)雜變異、類似于遺傳算法的基因操作1972Frantz位置非線性和倒位操作研究1973Holland遺傳算法中試驗(yàn)的最優(yōu)配置和雙臂強(qiáng)盜問(wèn)題1973Martin類似遺傳算法的概率算法理論1975De Jong用于5個(gè)測(cè)試函數(shù)的研究基本遺傳短發(fā)基準(zhǔn)參數(shù)1975Holland出版開(kāi)創(chuàng)性著作Adaptation in Natural and Artificial Systems表1.1 遺傳算法理論的經(jīng)典研究成果第一階段：20世紀(jì)60年代至70年代中期（萌芽期）1 遺傳算法概述年份貢獻(xiàn)者內(nèi)容1981Bethke應(yīng)用Walsh函數(shù)分析模式1981Brin

4、dle研究遺傳算法中的選擇和支配問(wèn)題1983Pettit, Swigger遺傳算法應(yīng)用于非穩(wěn)定問(wèn)題的粗略研究1983Wetzel用遺傳算法解決旅行商問(wèn)題（TSP)1984Mauldin基本遺傳算法中用啟發(fā)知識(shí)維持遺傳多樣性1985Baker試驗(yàn)基于排序的選擇方法1985Booker建議采用部分分配計(jì)分、分享操作和交配限制法1985Goldberg, LingleTSP問(wèn)題中采用部分匹配交叉1985Grefenstette, Fitzpattrick對(duì)含噪聲的函數(shù)進(jìn)行測(cè)試1985Schaffer多種群遺傳算法解決多目標(biāo)優(yōu)化問(wèn)題續(xù)表1 遺傳算法概述年份貢獻(xiàn)者內(nèi)容1986Goldberg最優(yōu)種群大小

5、估計(jì)1986Grefenstette元級(jí)遺傳算法控制的遺傳算法1987Baker選擇中隨機(jī)誤差的較少方法1987Goldberg復(fù)制和交叉時(shí)最小欺騙問(wèn)題（MDP）1987Goldberg, Richardson借助分享函數(shù)的小生境和物種歸納法1987Goldberg, Segrest復(fù)制和交叉的有限馬爾科夫鏈1987Goldberg, Smith雙倍染色體遺傳算法應(yīng)用于非穩(wěn)定函數(shù)優(yōu)化1987Oliver, Smith, Holland排列重組算子的模擬和分析1987Schaffer, Morishima串編碼自適應(yīng)交叉試驗(yàn)1987Whitley子孫測(cè)試應(yīng)用于遺傳算法的選擇操作續(xù)表第二階段：20

6、世紀(jì)80年代（蓬勃發(fā)展期）1 遺傳算法概述 遺傳算法的應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化（經(jīng)典應(yīng)用）（2）組合優(yōu)化（旅行商問(wèn)題已成為衡量算法優(yōu)劣的標(biāo)準(zhǔn)、背包問(wèn)題、裝箱問(wèn)題等）（3）生產(chǎn)調(diào)度問(wèn)題（4）自動(dòng)控制（如航空控制系統(tǒng)的優(yōu)化設(shè)計(jì)、模糊控制器優(yōu)化設(shè)計(jì)和在線修改隸屬度函數(shù)、人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)和調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)等優(yōu)化問(wèn)題）（5）機(jī)器人智能控制（如移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解等）（6）圖像處理和模式識(shí)別（如圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識(shí)別等）（7）機(jī)器學(xué)習(xí)（將GA用于知識(shí)獲取，構(gòu)建基于GA的機(jī)器學(xué)習(xí)系統(tǒng)） 此外，遺傳算法在人工生命、遺傳程序設(shè)計(jì)、社會(huì)和經(jīng)

7、濟(jì)領(lǐng)域等方面的應(yīng)用盡管不是很成熟，但還是取得了一定的成功。在日后，必定有更深入的發(fā)展。Hotspot背包問(wèn)題(Knapsack problem)是一種組合優(yōu)化的NP完全問(wèn)題。問(wèn)題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問(wèn)題的名稱來(lái)源于如何選擇最合適的物品放置于給定背包中。相似問(wèn)題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，計(jì)算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。也可以將背包問(wèn)題描述為決定性問(wèn)題，即在總重量不超過(guò)W的前提下，總價(jià)值是否能達(dá)到V？它是在1978年由Merkel和Hellman提出的。NP完全問(wèn)題，是世界七大數(shù)學(xué)難題之一。 N

8、P的英文全稱是Non-deterministic Polynomial的問(wèn)題，即多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題。簡(jiǎn)單的寫法是 NP=P？，問(wèn)題就在這個(gè)問(wèn)號(hào)上，到底是NP等于P，還是NP不等于P。這七個(gè)“世界難題”是：NP完全問(wèn)題、霍奇猜想、龐加萊猜想、黎曼假設(shè)、楊米爾斯理論、納衛(wèi)爾-斯托可方程、BSD猜想。所謂集裝箱裝載問(wèn)題，就是將若干大小不同的長(zhǎng)方體裝進(jìn)一個(gè)大小已知的長(zhǎng)方體容器，其目標(biāo)是最大化容器的積載率。生產(chǎn)調(diào)度問(wèn)題Contents of Section 2遺傳算法的生物學(xué)基礎(chǔ)遺傳算法的基本流程遺傳算法的若干基本概念遺傳算法的應(yīng)用步驟欺騙問(wèn)題和未成熟收斂問(wèn)題2 標(biāo)準(zhǔn)遺傳算法 遺傳算法的生物學(xué)

9、基礎(chǔ)細(xì)胞（Cell）染色體（Chromosome） 脫氧核糖核酸（Deoxyribonucleic Acid，DNA） 基因（Gene）、等位基因（Allele） 基因型（Genotype） 表現(xiàn)型（Phenotype） 復(fù)制（Reproduction）交叉（Crossover）變異（Mutation）對(duì)環(huán)境的適應(yīng)性“種瓜得瓜，種豆得豆”2 標(biāo)準(zhǔn)遺傳算法 遺傳算法的生物學(xué)基礎(chǔ)個(gè)體（Individual） 種群（Population） 適應(yīng)度（Fitness） 進(jìn)化（Evolution） 生存（Survival） LowHigh“物競(jìng)天擇，適者生存”死亡（Death） 滅絕（Extinction

10、） 2 標(biāo)準(zhǔn)遺傳算法 標(biāo)準(zhǔn)遺傳算法的基本流程實(shí)際問(wèn)題參數(shù)集參數(shù)編碼成為染色體初始化群體計(jì)算每一個(gè)體的適應(yīng)度對(duì)染色體進(jìn)行解碼滿足終止條件？得到問(wèn)題最優(yōu)解進(jìn)行遺傳操作群體新群體P(t)P(t+1)1、選擇2、交叉3、變異2 標(biāo)準(zhǔn)遺傳算法 遺傳算法的若干概念個(gè)體(Individual) 稱 為個(gè)體空間，個(gè)體空間的元素 稱為個(gè)體，它是染色體帶有特征的實(shí)體。分量 稱為基因，正整數(shù) 稱為個(gè)體的基因長(zhǎng)度。 種群(Population) 稱個(gè)體空間S中N個(gè)個(gè)體組成的一個(gè)子集（個(gè)體允許重復(fù)）稱為一個(gè)種群，記為：其中 ，N稱為種群規(guī)模。2 標(biāo)準(zhǔn)遺傳算法 遺傳算法的若干概念適應(yīng)度（Fitness） 在研究自然界中生

11、物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕。在遺傳算法中，一般通過(guò)適應(yīng)度函數(shù)（Fitness function）來(lái)衡量某一個(gè)體的適應(yīng)度高低。 2 標(biāo)準(zhǔn)遺傳算法解碼（Decoding） 解碼是將遺傳算法所搜索到的最優(yōu)個(gè)體的染色體轉(zhuǎn)換成待求解問(wèn)題的實(shí)際最優(yōu)解的過(guò)程，即編碼的逆過(guò)程。 遺傳算法的若干概念編碼（Coding） 將一個(gè)待求解的問(wèn)題的實(shí)際可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間（即個(gè)體空間）的過(guò)程，就稱為編碼。2 標(biāo)準(zhǔn)遺傳

12、算法選擇操作（Selection） 根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中。一般地，選擇操作通過(guò)選擇算子（Selection Operator）進(jìn)行。 遺傳算法的若干概念交叉操作（Crossover） 將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一對(duì)個(gè)體，以某個(gè)概率（稱為交叉概率，Crossover Rate）遵循某一種規(guī)則交換它們之間的部分染色體。變異操作（Mutation） 對(duì)群體P(t)中的每一個(gè)個(gè)體，以某一概率（稱為變異概率，Mutation Rate）改變某一個(gè)或某一些基因座上的基因值為其他的等位基因。2 標(biāo)準(zhǔn)遺

13、傳算法 遺傳算法的應(yīng)用步驟（1）確定決策變量及各種約束條件，即確定出個(gè)體的表現(xiàn)型X和問(wèn)題的解空間。（2）建立優(yōu)化模型，確定出目標(biāo)函數(shù)的類型及其數(shù)學(xué)描述形式或量化方法。（3）確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型X*，及遺傳算法的搜索空間。 編碼是遺傳算法解決問(wèn)題的先決條件和關(guān)鍵步驟:不僅決定個(gè)體基因的排列形式（從而決定選擇與繁殖等操作的作用方式），而且也決定從搜索空間的基因型到解空間的表現(xiàn)型的解碼方式（從而決定對(duì)GA所獲解的翻譯與理解）；決定GA搜索的困難度與復(fù)雜性；決定對(duì)問(wèn)題的求解精度。 常用的遺傳算法編碼方法主要有：二進(jìn)制編碼、浮點(diǎn)數(shù)編碼等?？梢宰C明，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼搜

14、索能力強(qiáng)，但浮點(diǎn)數(shù)編碼比二進(jìn)制編碼在變異操作上能夠保持更好的種群多樣性。2 標(biāo)準(zhǔn)遺傳算法 遺傳算法的應(yīng)用步驟（4）確定解碼方法，即確定出由個(gè)體基因型X*，到個(gè)體表現(xiàn)型X的對(duì)應(yīng)關(guān)系和轉(zhuǎn)換方法。 標(biāo)準(zhǔn)遺傳算法多采用二進(jìn)制編碼方法，將決策變量用二進(jìn)制字符串表示，二進(jìn)制編碼串的長(zhǎng)度由所求精度決定。然后將各決策變量的二進(jìn)制編碼串連接在一起，構(gòu)成一個(gè)染色體。 例如：變量x的定義域?yàn)?2，3，要求其精度為10-5，則需要將-2，3分成至少500 000個(gè)等長(zhǎng)小區(qū)域，而每個(gè)小區(qū)域用一個(gè)二進(jìn)制串表示。于是有，2L=500 000，即向上取整，可得到L=19。即可用19位二進(jìn)制串a(chǎn)18a17a0 來(lái)表示。 例如：

15、對(duì)于二進(jìn)制編碼，其解碼過(guò)程如下：若X*的取值范圍為Xl,Xr，參數(shù)的二進(jìn)制編碼碼長(zhǎng)為L(zhǎng)，碼串對(duì)應(yīng)的十進(jìn)制整數(shù)為k，則解碼公式為:式中， Xl,Xr參數(shù)最小、最大值； L參數(shù)編碼長(zhǎng)度； k二進(jìn)制串對(duì)應(yīng)的實(shí)數(shù)值。2 標(biāo)準(zhǔn)遺傳算法（5）確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，就是確定出由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則。標(biāo)準(zhǔn)遺傳算法的適應(yīng)度函數(shù)常用一下三種： 遺傳算法的應(yīng)用步驟直接以待求解的目標(biāo)函數(shù)為適應(yīng)度函數(shù) 若目標(biāo)函數(shù)為最大值問(wèn)題，則Fit(f(X)=f(X) 若目標(biāo)函數(shù)為最小值問(wèn)題，則Fit(f(X)=f(X)界限構(gòu)造法優(yōu)點(diǎn)：簡(jiǎn)單直觀；缺點(diǎn)：其一，可能不滿足非負(fù)的要求；其二，某些代求解的函數(shù)值分布相差很

16、大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能。 若目標(biāo)函數(shù)為最大值問(wèn)題，則Cmax為f(x)的最大值估計(jì)。2 標(biāo)準(zhǔn)遺傳算法 倒數(shù)法 若目標(biāo)函數(shù)為最小值問(wèn)題，則 遺傳算法的應(yīng)用步驟該方法是第一種方法的改進(jìn)，但有時(shí)存在界限值預(yù)先估計(jì)困難或估計(jì)不精確等問(wèn)題。Cmin為f(x)的最小值估計(jì)。 若目標(biāo)函數(shù)為最小值問(wèn)題，則 若目標(biāo)函數(shù)為最大值問(wèn)題，則C為目標(biāo)函數(shù)界限的保守估計(jì)值。2 標(biāo)準(zhǔn)遺傳算法（6）確定各遺傳具體操作方法。 遺傳算法的應(yīng)用步驟選擇算子和選擇操作個(gè)體選擇概率的常用分配方法有以下兩種：A 按比例的適應(yīng)度分配（Proportional Fitness Assignment） 亦可稱為選

17、擇的蒙特卡羅方法，是利用比例于各個(gè)個(gè)體適應(yīng)度的概率決定其子孫的遺留可能性。若某個(gè)個(gè)體i，其適應(yīng)度為fi，則其被選取的概率表示為, 顯然選擇概率大的個(gè)體，能多次被選中，它的遺傳因子就會(huì)在種群中擴(kuò)大。B 基于排序的適應(yīng)度分配（Rank-based Fitness Assignment） 在基于排序的適應(yīng)度分配中，種群按目標(biāo)值進(jìn)行排序。適應(yīng)度僅僅取決于個(gè)體在種群中的序位，而不是實(shí)際的目標(biāo)值。 排序方法比比例方法表現(xiàn)出更好的魯棒性，它能在一定程度上克服了比例適應(yīng)度計(jì)算的尺度問(wèn)題和過(guò)早收斂問(wèn)題。2 標(biāo)準(zhǔn)遺傳算法 遺傳算法的應(yīng)用步驟另外，還可采用以下的幾種提高遺傳算法性能的選擇方法：穩(wěn)態(tài)繁殖（Steady

18、 State Reproduction） 在迭代過(guò)程中用部分優(yōu)質(zhì)新子個(gè)體來(lái)更新群體中部分父?jìng)€(gè)體，作為下一代種群。沒(méi)有重串的穩(wěn)態(tài)繁殖（Steady State Reproduction without Duplicates） 在穩(wěn)態(tài)繁殖的基礎(chǔ)上，形成下一代新種群時(shí)，使其中的個(gè)體不重復(fù)。 個(gè)體選擇概率確定后，可以選用的常用選擇算法有輪盤賭選擇法（Roulette Wheel Selection）、隨機(jī)遍歷抽樣法（Stochastic Universal Sampling）、局部選擇法（Local Selection）、截?cái)噙x擇法（Truncation Selection）和錦標(biāo)賽選擇法（Tourn

19、ament Selection）等。標(biāo)準(zhǔn)遺傳算法常用的輪盤賭選擇法的原理如右下圖所示。pointer關(guān)于選擇算子：如果對(duì)解的質(zhì)量要求不高，要求收斂快，可取較高的選擇強(qiáng)度；反之，可取較低的選擇強(qiáng)度。標(biāo)準(zhǔn)遺傳算法達(dá)到收斂的世代數(shù)與選擇強(qiáng)度成反比。2 標(biāo)準(zhǔn)遺傳算法 交叉率及交叉操作 交叉，也可以稱為基因重組（Recombination），是遺傳算法獲取新的優(yōu)良個(gè)體的最重要的手段，決定了遺傳算法的全局搜索能力。 一般地，當(dāng)隨機(jī)產(chǎn)生的概率大于交叉率，遺傳算法就會(huì)按一定規(guī)則選擇兩個(gè)個(gè)體，執(zhí)行交叉操作。交叉率的選擇決定了交叉的頻率，較大的交叉率使各代充分交叉，但群體中的優(yōu)良模式遭到破壞的可能性增大，以致產(chǎn)生

20、較大的代溝，從而使搜索走向隨機(jī)化；交叉率越低，產(chǎn)生的代溝越小，就會(huì)使得更多的個(gè)體直接復(fù)制到下一代，遺傳搜索可能陷入停滯狀態(tài)，一般建議取值范圍。對(duì)于二進(jìn)制編碼，常用的交叉方法有：?jiǎn)吸c(diǎn)交叉、多點(diǎn)交叉和均勻交叉等。一個(gè)單點(diǎn)交叉的例子如下圖所示。2 標(biāo)準(zhǔn)遺傳算法變異率及變異操作 變異本身是一種局部隨機(jī)搜索，使遺傳算法具有局部的隨機(jī)搜索能力；同時(shí)使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。 一般地，隨機(jī)產(chǎn)生的概率大于變異率就會(huì)觸發(fā)變異操作。變異率一般可取。變異率不能取得太大，如果大于，遺傳算法就退化為隨機(jī)搜索，而遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力也不復(fù)存在了。 常用的變異操作方法有：實(shí)值變異

21、法和二進(jìn)制變異法等。實(shí)值變異法a(i)以概率1/m取值1，以概率1-1/m取值0，通常m=20 此外，還有部分匹配交叉（Partially Matched Crossover）、順序交叉（Ordered Crossover）、洗牌交叉（Shuffle Crossover）等等。二進(jìn)制變異法2 標(biāo)準(zhǔn)遺傳算法（7）確定遺傳算法的有關(guān)運(yùn)行參數(shù)，包括群體規(guī)模(Population Size)、迭代次數(shù)（一般取為100500）、選擇算子、交叉率、變異率等等。（8）初始化群體。初始群體一般隨機(jī)產(chǎn)生初始值最好能在解空間中均勻采樣（收斂速度比較快 ）對(duì)于非二進(jìn)制編碼，還要考慮所生成的染色體是否在可行區(qū)域內(nèi)。（

22、9）計(jì)算群體中個(gè)體解碼后的適應(yīng)值。（10）按照遺傳策略，運(yùn)用所選定的選擇、交叉和變異算子作用于群體，生成下一代群體。（11）判斷群體性能是否滿足某一指標(biāo)或是否完成預(yù)定迭代次數(shù)，不滿足則返回（9）。popsize取值較小時(shí)提高運(yùn)算和收斂速度卻降低了群體多樣性，可能引起早熟現(xiàn)象取值較大時(shí)含有較多模式，可提高GA搜索質(zhì)量但計(jì)算量增大，收斂速度降低一般取為201002 標(biāo)準(zhǔn)遺傳算法 欺騙問(wèn)題和未成熟收斂問(wèn)題2.6.1 欺騙問(wèn)題（Deceptive Problem）競(jìng)爭(zhēng)模式：若模式H與H中，*的位置完全一致，但任一確定位的編碼均不一樣，則稱H與H互為競(jìng)爭(zhēng)模式。欺騙性：假設(shè)f(X)的最大值對(duì)應(yīng)的X集合為X

23、*，H為一包含X*的m階模式。H的競(jìng)爭(zhēng)模式為H，而且f(H)f(H)，則f為m階欺騙。欺騙問(wèn)題：在遺傳算法中，將所有妨礙評(píng)價(jià)值高的個(gè)體生成從而影響遺傳算法正常工作的問(wèn)題統(tǒng)稱為欺騙問(wèn)題。 如對(duì)于一個(gè)2位二進(jìn)制編碼的模式，如果f(11) 為最大值，則以下不等式任意一個(gè)成立，則存在欺騙性問(wèn)題： f(*1) f(*0) ， f(*1) f(0*) ，f(1*) f (0*) ， f(1*) f(*0) 欺騙性問(wèn)題的產(chǎn)生往往與基因編碼方法、適應(yīng)度函數(shù)的確定和調(diào)整等因素相關(guān)，一般可以相應(yīng)地采用不同的編碼方法或者調(diào)整適應(yīng)度函數(shù)等方法來(lái)化解。2 標(biāo)準(zhǔn)遺傳算法（1）未成熟收斂現(xiàn)象 未成熟收斂現(xiàn)象是遺傳算法中的特

24、有現(xiàn)象，且十分常見(jiàn)。它是指，當(dāng)遺傳算法還沒(méi)找到全局最優(yōu)解或滿意解時(shí)，群體中不能再產(chǎn)生性能超過(guò)父代的后代，群體中的各個(gè)個(gè)體非常相似。未成熟收斂的重要特征是群體中個(gè)體結(jié)構(gòu)的多樣性急劇減少。2.6.2 未成熟收斂問(wèn)題（Premature Convergence）（2）未成熟收斂產(chǎn)生的原因理論上考慮的選擇、交叉、變異操作都是絕對(duì)精確的，他們相互協(xié)調(diào)，能搜索到整個(gè)解空間，但實(shí)際不然；存在隨機(jī)誤差（主要包括取樣誤差和選擇誤差）；所求解的問(wèn)題是遺傳算法欺騙問(wèn)題。（3）未成熟收斂的防止重新啟動(dòng)法替代策略（Replacement Strategies ）重組策略（Recombination Strategies

25、 ）匹配策略（Mating Strategies）提高多樣性遺傳算法具體步驟選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；定義適應(yīng)度函數(shù)，便于計(jì)算適應(yīng)值；確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數(shù)；隨機(jī)產(chǎn)生初始化群體；計(jì)算群體中的個(gè)體或染色體解碼后的適應(yīng)值；按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體；判斷群體性能是否滿足某一指標(biāo)，或者已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步，或者修改遺傳策略再返回第六步2 標(biāo)準(zhǔn)遺傳算法2 標(biāo)準(zhǔn)遺傳算法程序流程圖開(kāi)始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)

26、度從左至右依次執(zhí)行遺傳算子j = 0j = 0j = 0根據(jù)適應(yīng)度選擇復(fù)制個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)執(zhí)行變異執(zhí)行交叉執(zhí)行復(fù)制將復(fù)制的個(gè)體添入新群體中將交叉后的兩個(gè)新個(gè)體添入新群體中將變異后的個(gè)體添入新群體中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1輸出結(jié)果終止YNYYYNNNpcpm例1 利用遺傳算法求解區(qū)間0,31上的二次函數(shù)y=x2的最大值，精度要求達(dá)到個(gè)位。y=x2 31 XY3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值 分析 原問(wèn)題可轉(zhuǎn)化為在區(qū)間0, 31中搜索能使y取最大值的點(diǎn)a的問(wèn)題。那么，0, 31 中的點(diǎn)x就是個(gè)體

27、, 函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間0, 31就是一個(gè)(解)空間 。這樣, 只要能給出個(gè)體x的適當(dāng)染色體編碼, 該問(wèn)題就可以用遺傳算法來(lái)解決。3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值(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 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值(3) 計(jì)算各代種群中的各個(gè)體的適應(yīng)度, 并對(duì)其染色體進(jìn)行遺傳操作,直到適應(yīng)度最

28、高的個(gè)體(即31（11111）)出現(xiàn)為止。 首先計(jì)算種群S1中各個(gè)體 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的適應(yīng)度f(wàn) (si) 。容易求得： f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 3613、遺傳算法簡(jiǎn)單舉例：函數(shù)極值再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為 由此可求得 P(s1) = P P(s2) = P(24) = 0.49 P(s3) =

29、 P P(s4) = P3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值 輪盤賭選擇示意圖s40.31s20.49s10.14s30.063、遺傳算法簡(jiǎn)單舉例：函數(shù)極值選擇-復(fù)制 染色體 適應(yīng)度選擇概率選中次數(shù)s1=01101 169 0.14 1s2=11000 576 0.49 2s3=01000 64 0.06 0s4=10011 361 0.31 1于是，經(jīng)選擇復(fù)制得群體： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值交叉 設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。 設(shè)s1與s2配對(duì)，

30、s3與s4配對(duì)。分別交換后兩位基因，得新染色體： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值變異 設(shè)變異率pm。這樣，群體S1中共有 54位基因可以變異。位顯然不足1位，所以本輪遺傳操作不做變異。 于是，得到第二代種群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值 第二代種群S2中各染色體的情況 染色體 適應(yīng)度選擇概率 估計(jì)的選中次數(shù)s1=11001 625 0.36 1s2=01100 144 0.08

31、 0s3=11011 729 0.41 2s4=10000 256 0.15 13、遺傳算法簡(jiǎn)單舉例：函數(shù)極值假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體： s1=11001（25）, s2= 11011（27） s3=11011（27）, s4= 10000（16） 做交叉運(yùn)算，讓s1與s2，s3與s4 分別交換后三位基因，得 s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19） 這一輪仍然不會(huì)發(fā)生變異。 于是，得第三代種群S3： s1=11100（28）, s2=01001（9） s3=11000（2

32、4）, s4=10011（19） 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值 第三代種群S3中各染色體的情況 染色體 適應(yīng)度選擇概率 估計(jì)的選中次數(shù)s1=11100 784 0.44 2s2=01001 81 0.04 0s3=11000 576 0.32 1s4=10011 361 0.20 13、遺傳算法簡(jiǎn)單舉例：函數(shù)極值 設(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）,

33、s4=10000（16） 這一輪仍然不會(huì)發(fā)生變異。 于是，得第四代種群S4： s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值 顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。 將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961。 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值YYy=x2 8 13 19 24 X第一代種群及其適應(yīng)度y=x2 12 16 2

34、5 27 XY第二代種群及其適應(yīng)度y=x2 9 19 24 28 XY第三代種群及其適應(yīng)度y=x2 16 24 28 31 X第四代種群及其適應(yīng)度課堂練習(xí)求一元函數(shù)f(x)的最大值： 要求求解精度到6位小數(shù)編碼 表現(xiàn)型：x 基因型：二進(jìn)制編碼（串長(zhǎng)取決于求解精度） 按編碼原理：假設(shè)要求求解精度到6位小數(shù)，區(qū)間長(zhǎng)度為2-(-1)3，即需將區(qū)間分為3/0.000001=3106等份。 所以編碼的二進(jìn)制串長(zhǎng)應(yīng)為22位。產(chǎn)生初始種群 產(chǎn)生的方式：隨機(jī) 產(chǎn)生的結(jié)果：長(zhǎng)度為22的二進(jìn)制串 產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50 計(jì)算適應(yīng)度直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù) 解碼：將個(gè)體s轉(zhuǎn)化為-1,2區(qū)間

35、的實(shí)數(shù)： sx 計(jì)算x的函數(shù)值（適應(yīng)度）： f(x)=xsin(10 x遺傳操作 選擇：比例選擇法； 交叉：?jiǎn)吸c(diǎn)交叉； 變異：小概率變異模擬結(jié)果 設(shè)置的參數(shù)： 種群大小50；交叉概率；變異概率；最大代數(shù)200。 得到的最佳個(gè)體： smax xmax=1.8506; f(xmax)=3.8503;模擬結(jié)果 進(jìn)化的過(guò)程：世代數(shù)自變量適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503考慮問(wèn)題：能否用遺傳算法解決以下問(wèn)題1、

36、2、3、Contents of Section 4巡回旅行商問(wèn)題基本操作計(jì)算仿真結(jié)果4 遺傳算法求解巡回旅行商問(wèn)題4 遺傳算法求解巡回旅行商問(wèn)題 巡回旅行商問(wèn)題City5City1City2City3City4 巡回旅行商問(wèn)題（Traveling salesman problem, TSP）可描述如下：已知N個(gè)城市之間的相互距離，現(xiàn)有一推銷員必須遍歷這N個(gè)城市，并且每個(gè)城市只能訪問(wèn)一次，最后又必須返回出發(fā)城市，如何安排他訪問(wèn)這些城市的次序，使其旅行路線總長(zhǎng)度最短？ 4 遺傳算法求解巡回旅行商問(wèn)題CHN31問(wèn)題60 Cities4 遺傳算法求解巡回旅行商問(wèn)題 TSP具有廣泛的應(yīng)用背景和重要理論價(jià)

37、值，特別在機(jī)器人運(yùn)動(dòng)規(guī)劃中得到許多應(yīng)用，例如：移動(dòng)機(jī)器人的全局路徑規(guī)劃問(wèn)題（如右上圖）、焊接機(jī)器人的任務(wù)規(guī)劃問(wèn)題（如右下圖）等等。 但是，巡回旅行商問(wèn)題中可能的路徑數(shù)目與城市數(shù)目N呈指數(shù)型增長(zhǎng)，所有的旅程路線組合數(shù)為其已經(jīng)被證明屬于NP難題。例如30個(gè)城市的路線對(duì)應(yīng)約有對(duì)龐大的搜索空間尋求最優(yōu)解，常規(guī)方法和現(xiàn)有的計(jì)算工具存在著諸多的計(jì)算困難。 4 遺傳算法求解巡回旅行商問(wèn)題序號(hào)X坐標(biāo)Y坐標(biāo)序號(hào)X坐標(biāo)Y坐標(biāo)序號(hào)X坐標(biāo)Y坐標(biāo)1185411714421764287761264602222603747813685823256247171148369246232525381558692587765835

38、1654622691387450175167278346813401837842841269184019419429452110244220299304435本例所用30個(gè)城市的XY坐標(biāo)：4 遺傳算法求解巡回旅行商問(wèn)題 基本操作（1）編碼與解碼 采用對(duì)訪問(wèn)城市序列進(jìn)行排列組合的方法編碼，即某個(gè)巡回路徑的染色體是該巡回路徑的城市序列。對(duì)于N（N為城市總數(shù)）進(jìn)制編碼，即每個(gè)基因僅從1到N得整數(shù)里面取一個(gè)值，每個(gè)個(gè)體的長(zhǎng)度為N。 根據(jù)編碼方法，一次求解得出的最優(yōu)解（個(gè)體）是所訪問(wèn)的城市的次序，需要轉(zhuǎn)換成相應(yīng)的城市坐標(biāo)進(jìn)行輸出，則只需將個(gè)體的染色體值作為存儲(chǔ)30個(gè)城市坐標(biāo)的矩陣的下標(biāo)來(lái)引用，輸出對(duì)應(yīng)的

39、矩陣元素，便可實(shí)現(xiàn)解碼。一行的前30個(gè)元素為一個(gè)個(gè)體30個(gè)城市的訪問(wèn)次序該種訪問(wèn)次序路徑的距離利用矩陣來(lái)存儲(chǔ)：4 遺傳算法求解巡回旅行商問(wèn)題（2）適應(yīng)度函數(shù)：在TSP問(wèn)題中，用路徑的總長(zhǎng)度作為適應(yīng)度函數(shù)來(lái)衡量求解結(jié)果是否最優(yōu)，路徑越短對(duì)應(yīng)的個(gè)體越優(yōu)，其適應(yīng)度值應(yīng)越大。 兩城市間的距離為： 個(gè)體代表的路徑的總長(zhǎng)度為： 則可采用倒數(shù)法將適應(yīng)度函數(shù)取為： （3）選擇操作：將群體中適應(yīng)度較大的C個(gè)個(gè)體直接替換適應(yīng)度較小的C個(gè)個(gè)體。其中C值與選擇算子和群體規(guī)模的關(guān)系在這里取為：A1：（ 3 4 5 6 ）第一步：保留交叉點(diǎn)的中間部分第二步：交換對(duì)應(yīng)位置的子串A2：（ 0 8 5 3 ）A2：（4 2 9

40、0 8 5 31 7 6）A1：（0 1 23 4 5 67 8 9）2917974 遺傳算法求解巡回旅行商問(wèn)題 本例中采用有序交叉執(zhí)行交叉操作。有序交叉能夠有效地繼承雙親的部分基因成分，達(dá)到了進(jìn)化的遺傳功能，使該遺傳算法并不盲目搜索，二是趨向于使群體具有更多的優(yōu)良基因。交叉后，考察父?jìng)€(gè)體與子個(gè)體的適應(yīng)度來(lái)決定是否更新種群。具體操作過(guò)程如下（以09編碼為例）：（4）交叉操作 父?jìng)€(gè)體：（“|”表示交叉點(diǎn)）301248664變異后子代個(gè)體：5 6 7 | 8 4 1 2 | 3 9 04 遺傳算法求解巡回旅行商問(wèn)題 變異操作中，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則仍保留父代染色體

41、。本例中，采用倒置變異法。例如：假設(shè)當(dāng)前個(gè)體為“5678412390”，如果當(dāng)前隨機(jī)值p0，1pmutation，則隨機(jī)選擇來(lái)自同一個(gè)體的兩個(gè)點(diǎn)（設(shè)為“8”和“2” ），執(zhí)行變異操作，即倒置該兩點(diǎn)的中間部分。產(chǎn)生的新個(gè)體為“5672148390”。 （5）變異操作 （6）群體初始化2變異前父代個(gè)體：5 6 7 | | 3 9 0148pop=zeros(s,t);for i=1:s pop(i,1:t-1)=randperm(t-1); end4 遺傳算法求解巡回旅行商問(wèn)題4.3 計(jì)算仿真結(jié)果990.0829 路徑長(zhǎng)度：遷移代數(shù)：504遺傳算法求解巡回旅行商問(wèn)題4.3 計(jì)算仿真結(jié)果701.77

42、54 路徑長(zhǎng)度：遷移代數(shù)：1004 遺傳算法求解巡回旅行商問(wèn)題4.3 計(jì)算仿真結(jié)果624.1821 路徑長(zhǎng)度：遷移代數(shù)：1504 遺傳算法求解巡回旅行商問(wèn)題4.3 計(jì)算仿真結(jié)果523.2674 路徑長(zhǎng)度：遷移代數(shù)：2004 遺傳算法求解巡回旅行商問(wèn)題4.3 計(jì)算仿真結(jié)果491.4063 路徑長(zhǎng)度：遷移代數(shù)：2504 遺傳算法求解巡回旅行商問(wèn)題4.3 計(jì)算仿真結(jié)果路徑長(zhǎng)度：遷移代數(shù)：3004 遺傳算法求解巡回旅行商問(wèn)題4.3 計(jì)算仿真結(jié)果430.3986 路徑長(zhǎng)度：遷移代數(shù)：3504.3 計(jì)算仿真結(jié)果424.8693 路徑長(zhǎng)度：遷移代數(shù)：400Best4 遺傳算法求解巡回旅行商問(wèn)題距離為的訪問(wèn)次

43、序距離為的訪問(wèn)次序（最優(yōu)）距離為的訪問(wèn)次序4 遺傳算法求解巡回旅行商問(wèn)題距離為的訪問(wèn)次序（最優(yōu)）距離為的訪問(wèn)次序距離為的訪問(wèn)次序4 遺傳算法求解巡回旅行商問(wèn)題4.4 關(guān)于遺傳算法操作算子的驗(yàn)證4 遺傳算法求解巡回旅行商問(wèn)題“實(shí)驗(yàn)數(shù)據(jù)”課程所做的正交試驗(yàn)極差分析結(jié)果（遷移500代后退出的結(jié)果）。對(duì)于上表，有（驗(yàn)證）以下基本結(jié)論：（1）遺傳算法搜索求解能力與四個(gè)因素有關(guān)：群體規(guī)模、選擇算子、交叉率和變異率 。（2）從主到次依次為：交叉率群體規(guī)模選擇算子變異率。（3）A3-B2-C1-D3是優(yōu)選方案。4 遺傳算法求解巡回旅行商問(wèn)題左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次遷移1000代，有36次能收斂到全局

44、最優(yōu)解）是比較優(yōu)的參數(shù)組合。實(shí)際上可看出，迭代進(jìn)行到450代之后，所得到得最優(yōu)個(gè)體基本不再發(fā)生變化，且其最優(yōu)路徑與真實(shí)的最有路徑差距非常小。4 遺傳算法求解巡回旅行商問(wèn)題左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次遷移1000代，有24次能收斂到全局最優(yōu)解）表明：選擇算子取值太大，收斂速度很快，但陷入局部最優(yōu)解的可能性大大提高，而基本上不可能再跳出來(lái)。約350代便收斂4 遺傳算法求解巡回旅行商問(wèn)題左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次迭代1000代，僅有6次能收斂到全局最優(yōu)解）表明：交叉率選取太大，導(dǎo)致群體中的優(yōu)良模式遭到破壞，產(chǎn)生較大的代溝，從而使搜索走向隨機(jī)化。450Km左右4 遺傳算法求解巡回旅行商問(wèn)

45、題左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次遷移1000代，有18次能收斂到全局最優(yōu)解）表明：變異率選取太大，遺傳算法幾乎退化為隨機(jī)搜索，陷入局部最優(yōu)解后比較難跳出來(lái)。約380代左右4 遺傳算法求解巡回旅行商問(wèn)題83GA優(yōu)化NN的權(quán)重（結(jié)構(gòu)確定）GA優(yōu)化NN的結(jié)構(gòu)：神經(jīng)元數(shù)和連接狀況x1輸出層隱藏層輸入層x2yxnw1wiwn5遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)84 編碼（實(shí)數(shù)編碼)1、GA優(yōu)化NN的權(quán)重85定義適應(yīng)度直接采用方差和.評(píng)估過(guò)程：對(duì)每個(gè)解進(jìn)行樣本測(cè)試（前向計(jì)算），計(jì)算其實(shí)際輸出和期望輸出的誤差（適應(yīng)度）。如果有一個(gè)個(gè)體的適應(yīng)度滿足精度要求，則結(jié)束1、GA優(yōu)化NN的權(quán)重86遺傳操作：交叉1、GA優(yōu)化NN的權(quán)重871、GA優(yōu)化NN的權(quán)重遺傳操作：變異881、GA優(yōu)化NN的權(quán)重89BP算法和GA算法結(jié)合 GA擅長(zhǎng)全局優(yōu)化搜索，BP擅長(zhǎng)局部?jī)?yōu)化搜索；兩者結(jié)合，可提高收斂速度?？朔礼A過(guò)早收斂的問(wèn)題1、GA優(yōu)化NN的權(quán)重90先用GA找出全局最優(yōu)解的大概位置，然后采用BP算法微調(diào)得到全