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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、 State Reproduction） 在迭代過程中用部分優(yōu)質新子個體來更新群體中部分父個體，作為下一代種群。沒有重串的穩(wěn)態(tài)繁殖（Steady State Reproduction without Duplicates） 在穩(wěn)態(tài)繁殖的基礎上，形成下一代新種群時，使其中的個體不重復。 個體選擇概率確定后，可以選用的常用選擇算法有輪盤賭選擇法（Roulette Wheel Selection）、隨機遍歷抽樣法（Stochastic Universal Sampling）、局部選擇法（Local Selection）、截斷選擇法（Truncation Selection）和錦標賽選擇法（Tourn

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

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

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

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

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

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

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

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

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

28、高的個體(即31（11111）)出現(xiàn)為止。 首先計算種群S1中各個體 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的適應度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 = 3613、遺傳算法簡單舉例：函數(shù)極值再計算種群S1中各個體的選擇概率。選擇概率的計算公式為 由此可求得 P(s1) = P P(s2) = P(24) = 0.49 P(s3) =

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

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

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

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

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

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

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

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

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

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

39、矩陣元素，便可實現(xiàn)解碼。一行的前30個元素為一個個體30個城市的訪問次序該種訪問次序路徑的距離利用矩陣來存儲：4 遺傳算法求解巡回旅行商問題（2）適應度函數(shù)：在TSP問題中，用路徑的總長度作為適應度函數(shù)來衡量求解結果是否最優(yōu)，路徑越短對應的個體越優(yōu)，其適應度值應越大。 兩城市間的距離為： 個體代表的路徑的總長度為： 則可采用倒數(shù)法將適應度函數(shù)取為： （3）選擇操作：將群體中適應度較大的C個個體直接替換適應度較小的C個個體。其中C值與選擇算子和群體規(guī)模的關系在這里取為：A1：（ 3 4 5 6 ）第一步：保留交叉點的中間部分第二步：交換對應位置的子串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 遺傳算法求解巡回旅行商問題 本例中采用有序交叉執(zhí)行交叉操作。有序交叉能夠有效地繼承雙親的部分基因成分，達到了進化的遺傳功能，使該遺傳算法并不盲目搜索，二是趨向于使群體具有更多的優(yōu)良基因。交叉后，考察父個體與子個體的適應度來決定是否更新種群。具體操作過程如下（以09編碼為例）：（4）交叉操作 父個體：（“|”表示交叉點）301248664變異后子代個體：5 6 7 | 8 4 1 2 | 3 9 04 遺傳算法求解巡回旅行商問題 變異操作中，若變異后子代的適應度值更加優(yōu)異，則保留子代染色體，否則仍保留父代染色體

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

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

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

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

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