數(shù)學(xué)建模專題之MATLAB遺傳算法資料

1、數(shù)學(xué)(shxu)建模專題之遺傳算法重慶理工大學(xué)主講(zhjing)：肖漢光Email:hgxiao共一百零一頁Contents遺傳算法概述1標(biāo)準(zhǔn)遺傳算法2遺傳算法簡單舉例：函數(shù)極值3遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)5遺傳算法求解TSP問題4遺傳算法的實(shí)現(xiàn)6共一百零一頁Contents of Section 11.4什么(shn me)是遺傳算法1.11.21.3遺傳算法的特點(diǎn)(tdin)遺傳算法的發(fā)展歷程遺傳算法的研究和應(yīng)用領(lǐng)域1 遺傳算法概述共一百零一頁1 遺傳算法概述(i sh)1.1 遺傳算法（Genetic Algorithm, GA）一種仿生全局優(yōu)化算法模仿生物的遺傳進(jìn)化原理（Darwins t

2、heory of evolution & Mendels law of inheritance)，通過選擇（Selection）、交叉（Crossover）與變異（Mutation）等操作機(jī)制，使種群中個(gè)體的適應(yīng)性（Fitness）不斷提高核心思想：物競天擇(w jn tin z)，適者生存 （“天”適應(yīng)度函數(shù)，F(xiàn)itness Function)共一百零一頁1 遺傳算法概述(i sh)1.2 遺傳算法的特點(diǎn)四大優(yōu)點(diǎn)：良好的并行性（操作對象是一組可行解；搜索軌道有多條）強(qiáng)大的通用性（只需利用目標(biāo)的取值信息，無需梯度等高價(jià)值信息）良好的全局(qunj)優(yōu)化性和魯棒性良好的可操作性兩個(gè)缺點(diǎn)：未成熟收

3、斂問題收斂速度較慢，算法實(shí)時(shí)性欠佳共一百零一頁1 遺傳算法概述(i sh)1.3 遺傳算法的發(fā)展(fzhn)歷史年份貢獻(xiàn)者內(nèi)容1962Holland程序漫游元胞計(jì)算機(jī)自適應(yīng)系統(tǒng)框架1968Holland模式定理的建立1971Hollstein具有交配和選擇規(guī)則的二維函數(shù)優(yōu)化1972BosworthFoo, Zeigler提出具有復(fù)雜變異、類似于遺傳算法的基因操作1972Frantz位置非線性和倒位操作研究1973Holland遺傳算法中試驗(yàn)的最優(yōu)配置和雙臂強(qiáng)盜問題1973Martin類似遺傳算法的概率算法理論1975De Jong用于5個(gè)測試函數(shù)的研究基本遺傳短發(fā)基準(zhǔn)參數(shù)1975Holland

4、出版開創(chuàng)性著作Adaptation in Natural and Artificial Systems表1.1 遺傳算法理論的經(jīng)典研究成果第一階段：20世紀(jì)60年代至70年代中期（萌芽期）共一百零一頁1 遺傳算法概述(i sh)年份貢獻(xiàn)者內(nèi)容1981Bethke應(yīng)用Walsh函數(shù)分析模式1981Brindle研究遺傳算法中的選擇和支配問題1983Pettit, Swigger遺傳算法應(yīng)用于非穩(wěn)定問題的粗略研究1983Wetzel用遺傳算法解決旅行商問題（TSP)1984Mauldin基本遺傳算法中用啟發(fā)知識維持遺傳多樣性1985Baker試驗(yàn)基于排序的選擇方法1985Booker建議采用部分分

5、配計(jì)分、分享操作和交配限制法1985Goldberg, LingleTSP問題中采用部分匹配交叉1985Grefenstette, Fitzpattrick對含噪聲的函數(shù)進(jìn)行測試1985Schaffer多種群遺傳算法解決多目標(biāo)優(yōu)化問題續(xù)表1.1共一百零一頁1 遺傳算法概述(i sh)年份貢獻(xiàn)者內(nèi)容1986Goldberg最優(yōu)種群大小估計(jì)1986Grefenstette元級遺傳算法控制的遺傳算法1987Baker選擇中隨機(jī)誤差的較少方法1987Goldberg復(fù)制和交叉時(shí)最小欺騙問題（MDP）1987Goldberg, Richardson借助分享函數(shù)的小生境和物種歸納法1987Goldberg

6、, Segrest復(fù)制和交叉的有限馬爾科夫鏈1987Goldberg, Smith雙倍染色體遺傳算法應(yīng)用于非穩(wěn)定函數(shù)優(yōu)化1987Oliver, Smith, Holland排列重組算子的模擬和分析1987Schaffer, Morishima串編碼自適應(yīng)交叉試驗(yàn)1987Whitley子孫測試應(yīng)用于遺傳算法的選擇操作續(xù)表1.1第二階段：20世紀(jì)(shj)80年代（蓬勃發(fā)展期）共一百零一頁1 遺傳算法概述(i sh)1.4 遺傳算法的應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化（經(jīng)典應(yīng)用）（2）組合優(yōu)化（旅行商問題已成為衡量算法優(yōu)劣的標(biāo)準(zhǔn)、背包問題、裝箱問題等）（3）生產(chǎn)調(diào)度問題（4）自動控制（如航空控制系統(tǒng)的優(yōu)化設(shè)計(jì)

7、、模糊控制器優(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)化問題）（5）機(jī)器人智能控制(kngzh)（如移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動軌跡規(guī)劃、機(jī)器人逆運(yùn)動學(xué)求解等）（6）圖像處理和模式識別（如圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識別等）（7）機(jī)器學(xué)習(xí)（將GA用于知識獲取，構(gòu)建基于GA的機(jī)器學(xué)習(xí)系統(tǒng)） 此外，遺傳算法在人工生命、遺傳程序設(shè)計(jì)、社會和經(jīng)濟(jì)領(lǐng)域等方面的應(yīng)用盡管不是很成熟，但還是取得了一定的成功。在日后，必定有更深入的發(fā)展。Hotspot共一百零一頁Contents of Section 22.4遺傳算法的生物學(xué)基礎(chǔ)(jch)2.12.22.

8、32.5遺傳算法的基本(jbn)流程遺傳算法的若干基本概念遺傳算法的應(yīng)用步驟欺騙問題和未成熟收斂問題共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法2.1 遺傳算法的生物學(xué)基礎(chǔ)(jch)細(xì)胞（Cell）染色體（Chromosome） 脫氧核糖核酸（Deoxyribonucleic Acid，DNA） 基因（Gene）、等位基因（Allele） 基因型（Genotype） 表現(xiàn)型（Phenotype） 復(fù)制（Reproduction）交叉（Crossover）變異（Mutation）對環(huán)境的適應(yīng)性“種瓜得瓜，種豆得豆”共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法2.1 遺傳算法的生物學(xué)基礎(chǔ)(jch)

9、個(gè)體（Individual） 種群（Population） 適應(yīng)度（Fitness） 進(jìn)化（Evolution） 生存（Survival） LowHigh“物競天擇，適者生存”死亡（Death） 滅絕（Extinction） 共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法2.2 標(biāo)準(zhǔn)(biozhn)遺傳算法的基本流程實(shí)際問題參數(shù)集參數(shù)編碼成為染色體初始化群體計(jì)算每一個(gè)體的適應(yīng)度對染色體進(jìn)行解碼滿足終止條件？得到問題最優(yōu)解進(jìn)行遺傳操作群體新群體P(t)P(t+1)1、選擇2、交叉3、變異共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法2.3 遺傳算法的若干概念個(gè)體(Individual) 稱 為個(gè)體空

10、間，個(gè)體空間的元素 稱為(chn wi)個(gè)體，它是染色體帶有特征的實(shí)體。分量 稱為(chn wi)基因，正整數(shù) 稱為(chn wi)個(gè)體的基因長度。 種群(Population) 稱個(gè)體空間S中N個(gè)個(gè)體組成的一個(gè)子集（個(gè)體允許重復(fù)）稱為一個(gè)種群，記為：其中 ，N稱為種群規(guī)模。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法2.3 遺傳算法的若干(rugn)概念適應(yīng)度（Fitness） 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語來度量某個(gè)物種對于生存環(huán)境的適應(yīng)程度。對生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會，而對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會就會相對較少，甚至逐漸

11、滅絕。在遺傳算法中，一般通過適應(yīng)度函數(shù)（Fitness function）來衡量某一個(gè)體的適應(yīng)度高低。 共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法解碼（Decoding） 解碼是將遺傳算法所搜索到的最優(yōu)個(gè)體的染色體轉(zhuǎn)換成待求解問題的實(shí)際最優(yōu)解的過程(guchng)，即編碼的逆過程(guchng)。 2.3 遺傳算法的若干概念編碼（Coding） 將一個(gè)待求解的問題的實(shí)際可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間（即個(gè)體空間）的過程，就稱為編碼。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法選擇操作（Selection） 根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則，從第t代群體P(t)中選擇出一

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

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

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

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

16、一，可能不滿足非負(fù)的要求；其二，某些代求解的函數(shù)值分布相差很大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能。 若目標(biāo)函數(shù)為最大值問題，則Cmax為f(x)的最大值估計(jì)。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法 倒數(shù)(do sh)法 若目標(biāo)函數(shù)為最小值問題，則2.4 遺傳算法的應(yīng)用步驟該方法是第一種方法的改進(jìn)，但有時(shí)存在界限值預(yù)先估計(jì)困難或估計(jì)不精確等問題。Cmin為f(x)的最小值估計(jì)。 若目標(biāo)函數(shù)為最小值問題，則 若目標(biāo)函數(shù)為最大值問題，則C為目標(biāo)函數(shù)界限的保守估計(jì)值。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法（6）確定各遺傳(ychun)具體操作方法。2.4 遺傳算法的應(yīng)用步驟

17、選擇算子和選擇操作個(gè)體選擇概率的常用分配方法有以下兩種：A 按比例的適應(yīng)度分配（Proportional Fitness Assignment） 亦可稱為選擇的蒙特卡羅方法，是利用比例于各個(gè)個(gè)體適應(yīng)度的概率決定其子孫的遺留可能性。若某個(gè)個(gè)體i，其適應(yīng)度為fi，則其被選取的概率表示為, 顯然選擇概率大的個(gè)體，能多次被選中，它的遺傳因子就會在種群中擴(kuò)大。B 基于排序的適應(yīng)度分配（Rank-based Fitness Assignment） 在基于排序的適應(yīng)度分配中，種群按目標(biāo)值進(jìn)行排序。適應(yīng)度僅僅取決于個(gè)體在種群中的序位，而不是實(shí)際的目標(biāo)值。 排序方法比比例方法表現(xiàn)出更好的魯棒性，它能在一定程度上

18、克服了比例適應(yīng)度計(jì)算的尺度問題和過早收斂問題。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法2.5 遺傳算法的應(yīng)用(yngyng)步驟另外，還可采用以下的幾種提高遺傳算法性能的選擇方法：穩(wěn)態(tài)繁殖（Steady State Reproduction） 在迭代過程中用部分優(yōu)質(zhì)新子個(gè)體來更新群體中部分父個(gè)體，作為下一代種群。沒有重串的穩(wěn)態(tài)繁殖（Steady State Reproduction without Duplicates） 在穩(wěn)態(tài)繁殖的基礎(chǔ)上，形成下一代新種群時(shí)，使其中的個(gè)體不重復(fù)。 個(gè)體選擇概率確定后，可以選用的常用選擇算法有輪盤賭選擇法（Roulette Wheel Selection）

19、、隨機(jī)遍歷抽樣法（Stochastic Universal Sampling）、局部選擇法（Local Selection）、截?cái)噙x擇法（Truncation Selection）和錦標(biāo)賽選擇法（Tournament Selection）等。標(biāo)準(zhǔn)遺傳算法常用的輪盤賭選擇法的原理如右下圖所示。pointer關(guān)于選擇算子：如果對解的質(zhì)量要求不高，要求收斂快，可取較高的選擇強(qiáng)度；反之，可取較低的選擇強(qiáng)度。標(biāo)準(zhǔn)遺傳算法達(dá)到收斂的世代數(shù)與選擇強(qiáng)度成反比。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法 交叉(jioch)率及交叉(jioch)操作 交叉，也可以稱為基因重組（Recombination），是遺

20、傳算法獲取新的優(yōu)良個(gè)體的最重要的手段，決定了遺傳算法的全局搜索能力。 一般地，當(dāng)隨機(jī)產(chǎn)生的概率大于交叉率，遺傳算法就會按一定規(guī)則選擇兩個(gè)個(gè)體，執(zhí)行交叉操作。交叉率的選擇決定了交叉的頻率，較大的交叉率使各代充分交叉，但群體中的優(yōu)良模式遭到破壞的可能性增大，以致產(chǎn)生較大的代溝，從而使搜索走向隨機(jī)化；交叉率越低，產(chǎn)生的代溝越小，就會使得更多的個(gè)體直接復(fù)制到下一代，遺傳搜索可能陷入停滯狀態(tài)，一般建議取值范圍0.40.9。對于二進(jìn)制編碼，常用的交叉方法有：單點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等。一個(gè)單點(diǎn)交叉的例子如下圖所示。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法變異率及變異操作 變異本身是一種局部隨機(jī)搜索

21、，使遺傳算法具有局部的隨機(jī)搜索能力；同時(shí)使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。 一般地，隨機(jī)產(chǎn)生的概率大于變異率就會觸發(fā)變異操作。變異率一般可取0.0010.1。變異率不能取得太大，如果(rgu)大于0.5，遺傳算法就退化為隨機(jī)搜索，而遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力也不復(fù)存在了。 常用的變異操作方法有：實(shí)值變異法和二進(jìn)制變異法等。實(shí)值變異法a(i)以概率1/m取值1，以概率1-1/m取值0，通常m=20 此外，還有部分匹配交叉（Partially Matched Crossover）、順序交叉（Ordered Crossover）、洗牌交叉（Shuffle Crossov

22、er）等等。二進(jìn)制變異法共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法（7）確定遺傳算法的有關(guān)運(yùn)行參數(shù)，包括群體規(guī)模(Population Size)、迭代次數(shù)（一般(ybn)取為100500）、選擇算子、交叉率、變異率等等。（8）初始化群體。初始群體一般隨機(jī)產(chǎn)生初始值最好能在解空間中均勻采樣（收斂速度比較快 ）對于非二進(jìn)制編碼，還要考慮所生成的染色體是否在可行區(qū)域內(nèi)。（9）計(jì)算群體中個(gè)體解碼后的適應(yīng)值。（10）按照遺傳策略，運(yùn)用所選定的選擇、交叉和變異算子作用于群體，生成下一代群體。（11）判斷群體性能是否滿足某一指標(biāo)或是否完成預(yù)定迭代次數(shù)，不滿足則返回（9）。popsize取值較小時(shí)提高運(yùn)算

23、和收斂速度卻降低了群體多樣性，可能引起早熟現(xiàn)象取值較大時(shí)含有較多模式，可提高GA搜索質(zhì)量但計(jì)算量增大，收斂速度降低一般取為20100共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法2.6 欺騙(qpin)問題和未成熟收斂問題2.6.1 欺騙問題（Deceptive Problem）競爭模式：若模式H與H中，*的位置完全一致，但任一確定位的編碼均不一樣，則稱H與H互為競爭模式。欺騙性：假設(shè)f(X)的最大值對應(yīng)的X集合為X*，H為一包含X*的m階模式。H的競爭模式為H，而且f(H)f(H)，則f為m階欺騙。欺騙問題：在遺傳算法中，將所有妨礙評價(jià)值高的個(gè)體生成從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題

24、。 如對于一個(gè)2位二進(jìn)制編碼的模式，如果f(11) 為最大值，則以下不等式任意一個(gè)成立，則存在欺騙性問題： f(*1) f(*0) ， f(*1) f(0*) ，f(1*) f (0*) ， f(1*) f(*0) 欺騙性問題的產(chǎn)生往往與基因編碼方法、適應(yīng)度函數(shù)的確定和調(diào)整等因素相關(guān)，一般可以相應(yīng)地采用不同的編碼方法或者調(diào)整適應(yīng)度函數(shù)等方法來化解。共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法（1）未成熟收斂現(xiàn)象 未成熟收斂現(xiàn)象是遺傳算法中的特有現(xiàn)象，且十分常見。它是指，當(dāng)遺傳算法還沒找到全局最優(yōu)解或滿意解時(shí)，群體中不能再產(chǎn)生性能超過父代的后代，群體中的各個(gè)個(gè)體非常相似。未成熟收斂的重要(zhn

25、gyo)特征是群體中個(gè)體結(jié)構(gòu)的多樣性急劇減少。2.6.2 未成熟收斂問題（Premature Convergence）（2）未成熟收斂產(chǎn)生的原因理論上考慮的選擇、交叉、變異操作都是絕對精確的，他們相互協(xié)調(diào)，能搜索到整個(gè)解空間，但實(shí)際不然；存在隨機(jī)誤差（主要包括取樣誤差和選擇誤差）；所求解的問題是遺傳算法欺騙問題。（3）未成熟收斂的防止重新啟動法替代策略（Replacement Strategies ）重組策略（Recombination Strategies ）匹配策略（Mating Strategies）提高多樣性共一百零一頁遺傳算法具體步驟選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)

26、構(gòu)空間(kngjin)；定義適應(yīng)度函數(shù)，便于計(jì)算適應(yīng)值；確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數(shù)；隨機(jī)產(chǎn)生初始化群體；計(jì)算群體(qnt)中的個(gè)體或染色體解碼后的適應(yīng)值；按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體；判斷群體性能是否滿足某一指標(biāo)，或者已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步，或者修改遺傳策略再返回第六步2 標(biāo)準(zhǔn)遺傳算法共一百零一頁2 標(biāo)準(zhǔn)(biozhn)遺傳算法程序(chngx)流程圖開始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(zhí)行遺傳算子j = 0j = 0j = 0根

27、據(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的最大值，精度要求(yoqi)達(dá)到個(gè)位。y=x2 31 XY3、遺傳算法簡單舉例：函數(shù)(hnsh)極值共一百零一頁 分析 原問題可轉(zhuǎn)化為在區(qū)間0, 31中搜索能使y取最大值的點(diǎn)a的問題。那么，0, 31 中的點(diǎn)x就是個(gè)體(gt),

28、 函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間0, 31就是一個(gè)(解)空間 。這樣, 只要能給出個(gè)體x的適當(dāng)染色體編碼, 該問題就可以用遺傳算法來解決。3、遺傳算法簡單舉例：函數(shù)(hnsh)極值共一百零一頁(1) 設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始(ch sh)種群。 將種群規(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、遺傳算法簡單舉例：函數(shù)(hnsh)極值共一百零一頁(3) 計(jì)算各代種群

29、(zhn qn)中的各個(gè)體的適應(yīng)度, 并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。 首先計(jì)算(j sun)種群S1中各個(gè)體 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 = 3613、遺傳算法簡單舉例：函數(shù)極值共一百零一頁再計(jì)算(j sun)種群S1中各個(gè)體的選擇

30、概率。選擇概率的計(jì)算公式為 由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.313、遺傳算法簡單舉例：函數(shù)(hnsh)極值共一百零一頁 輪盤(ln pn)賭選擇示意圖s40.31s20.49s10.14s30.063、遺傳算法簡單舉例：函數(shù)(hnsh)極值共一百零一頁選擇(xunz)-復(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于是

31、，經(jīng)選擇復(fù)制(fzh)得群體： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 3、遺傳算法簡單舉例：函數(shù)極值共一百零一頁交叉 設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。 設(shè)s1與s2配對(pi du)，s3與s4配對。分別交換后兩位基因，得新染色體： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）3、遺傳算法簡單舉例(j l)：函數(shù)極值共一百零一頁變異 設(shè)變異率pm=0.001。這樣，群體S1中共(zhn n)有 540.001=0.02位基因可以

32、變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。 于是，得到第二代種群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）3、遺傳算法簡單舉例：函數(shù)(hnsh)極值共一百零一頁 第二代種群(zhn qn)S2中各染色體的情況 染色體 適應(yīng)度選擇概率 估計(jì)的選中次數(shù)s1=11001 625 0.36 1s2=01100 144 0.08 0s3=11011 729 0.41 2s4=10000 256 0.15 13、遺傳算法簡單(jindn)舉例：函數(shù)極值共一百零一頁假設(shè)這一輪選擇-復(fù)制操作(cozu)中，種群S2中的4個(gè)染

33、色體都被選中，則得到群體： s1=11001（25）, s2= 11011（27） s3=11011（27）, s4= 10000（16） 做交叉運(yùn)算，讓s1與s2，s3與s4 分別(fnbi)交換后三位基因，得 s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19） 這一輪仍然不會發(fā)生變異。 于是，得第三代種群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=10011（19） 3、遺傳算法簡單舉例：函數(shù)極值共一百零一頁 第三代種群(zhn qn)S3中各染色體的情況 染色體 適應(yīng)度選擇

34、概率 估計(jì)的選中次數(shù)s1=11100 784 0.44 2s2=01001 81 0.04 0s3=11000 576 0.32 1s4=10011 361 0.20 13、遺傳算法簡單舉例(j l)：函數(shù)極值共一百零一頁 設(shè)這一輪的選擇-復(fù)制(fzh)結(jié)果為： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19） 做交叉(jioch)運(yùn)算，讓s1與s4，s2與s3 分別交換后兩位基因，得 s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 這一輪仍然不會發(fā)生變異。 于是，得第四代種群

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

36、群及其適應(yīng)度y=x2 9 19 24 28 XY第三代種群及其適應(yīng)度y=x2 16 24 28 31 X第四代種群及其適應(yīng)度共一百零一頁課堂練習(xí)求一元函數(shù)f(x)的最大值： 要求求解精度(jn d)到6位小數(shù)共一百零一頁編碼 表現(xiàn)型：x 基因型：二進(jìn)制編碼（串長取決于求解精度） 按編碼原理：假設(shè)要求(yoqi)求解精度到6位小數(shù)，區(qū)間長度為2-(-1)3，即需將區(qū)間分為3/0.000001=3106等份。 所以編碼的二進(jìn)制串長應(yīng)為22位。共一百零一頁產(chǎn)生(chnshng)初始種群 產(chǎn)生的方式：隨機(jī) 產(chǎn)生的結(jié)果：長度為22的二進(jìn)制串 產(chǎn)生的數(shù)量：種群的大小（規(guī)模），如30，50 11110100

37、11100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 共一百零一頁計(jì)算適應(yīng)度直接用目標(biāo)函數(shù)(hnsh)作為適應(yīng)度函數(shù)(hnsh) 解碼：將個(gè)體s轉(zhuǎn)化為-1,2區(qū)間的實(shí)數(shù)： s= x=0.637197 計(jì)算x的函數(shù)值（適應(yīng)度）： f(x)=xsin(10 x)+2.0=2.586345共一百零一頁遺傳操作 選擇：比例選擇法； 交叉：單點(diǎn)交叉； 變異(biny)：小概率變異(biny)共一百零一

38、頁模擬結(jié)果 設(shè)置(shzh)的參數(shù)： 種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。 得到的最佳個(gè)體： smax=; xmax=1.8506; f(xmax)=3.8503;共一百零一頁模擬結(jié)果(ji gu) 進(jìn)化的過程：世代數(shù)自變量適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503共一百零一頁考慮(kol)問題：能否用遺傳算法解決以下問題1、2、3、共一百零一頁Contents of Secti

39、on 4巡回旅行(lxng)商問題4.14.24.3基本操作計(jì)算(j sun)仿真結(jié)果4 遺傳算法求解巡回旅行商問題共一百零一頁4 遺傳算法求解(qi ji)巡回旅行商問題4.1 巡回旅行(lxng)商問題City5City1City2City3City4 巡回旅行商問題（Traveling salesman problem, TSP）可描述如下：已知N個(gè)城市之間的相互距離，現(xiàn)有一推銷員必須遍歷這N個(gè)城市，并且每個(gè)城市只能訪問一次，最后又必須返回出發(fā)城市，如何安排他訪問這些城市的次序，使其旅行路線總長度最短？ 共一百零一頁4 遺傳算法求解巡回(xnhu)旅行商問題CHN31問題(wnt)60

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

41、2877612646022226037478136858232562471711483692462325253815586925877658351654622691387450175167278346813401837842841269184019419429452110244220299304435本例所用30個(gè)城市(chngsh)的XY坐標(biāo)：共一百零一頁4 遺傳算法求解(qi ji)巡回旅行商問題4.2 基本操作（1）編碼(bin m)與解碼 采用對訪問城市序列進(jìn)行排列組合的方法編碼，即某個(gè)巡回路徑的染色體是該巡回路徑的城市序列。對于N（N為城市總數(shù)）進(jìn)制編碼，即每個(gè)基因僅從1到N得整數(shù)里

42、面取一個(gè)值，每個(gè)個(gè)體的長度為N。 根據(jù)編碼方法，一次求解得出的最優(yōu)解（個(gè)體）是所訪問的城市的次序，需要轉(zhuǎn)換成相應(yīng)的城市坐標(biāo)進(jìn)行輸出，則只需將個(gè)體的染色體值作為存儲30個(gè)城市坐標(biāo)的矩陣的下標(biāo)來引用，輸出對應(yīng)的矩陣元素，便可實(shí)現(xiàn)解碼。一行的前30個(gè)元素為一個(gè)個(gè)體30個(gè)城市的訪問次序該種訪問次序路徑的距離利用矩陣來存儲：共一百零一頁4 遺傳算法求解巡回旅行(lxng)商問題（2）適應(yīng)度函數(shù)(hnsh)：在TSP問題中，用路徑的總長度作為適應(yīng)度函數(shù)來衡量求解結(jié)果是否最優(yōu)，路徑越短對應(yīng)的個(gè)體越優(yōu)，其適應(yīng)度值應(yīng)越大。 兩城市間的距離為： 個(gè)體代表的路徑的總長度為： 則可采用倒數(shù)法將適應(yīng)度函數(shù)取為： （3）

43、選擇操作：將群體中適應(yīng)度較大的C個(gè)個(gè)體直接替換適應(yīng)度較小的C個(gè)個(gè)體。其中C值與選擇算子和群體規(guī)模的關(guān)系在這里取為：共一百零一頁A1：（ 3 4 5 6 ）第一步：保留交叉點(diǎn)的中間(zhngjin)部分第二步：交換對應(yīng)(duyng)位置的子串A2：（ 0 8 5 3 ）A2：（4 2 90 8 5 31 7 6）A1：（0 1 23 4 5 67 8 9）2917974 遺傳算法求解巡回旅行商問題 本例中采用有序交叉執(zhí)行交叉操作。有序交叉能夠有效地繼承雙親的部分基因成分，達(dá)到了進(jìn)化的遺傳功能，使該遺傳算法并不盲目搜索，二是趨向于使群體具有更多的優(yōu)良基因。交叉后，考察父個(gè)體與子個(gè)體的適應(yīng)度來決定是

44、否更新種群。具體操作過程如下（以09編碼為例）：（4）交叉操作 父個(gè)體：（“|”表示交叉點(diǎn)）301248664共一百零一頁變異后子代(zdi)個(gè)體：5 6 7 | 8 4 1 2 | 3 9 04 遺傳算法求解巡回(xnhu)旅行商問題 變異操作中，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則仍保留父代染色體。本例中，采用倒置變異法。例如：假設(shè)當(dāng)前個(gè)體為“5678412390”，如果當(dāng)前隨機(jī)值p0，1pmutation，則隨機(jī)選擇來自同一個(gè)體的兩個(gè)點(diǎn)（設(shè)為“8”和“2” ），執(zhí)行變異操作，即倒置該兩點(diǎn)的中間部分。產(chǎn)生的新個(gè)體為“5672148390”。 （5）變異操作 （6）群體初始

45、化2變異前父代個(gè)體：5 6 7 | | 3 9 0148pop=zeros(s,t);for i=1:s pop(i,1:t-1)=randperm(t-1); end共一百零一頁4 遺傳算法求解(qi ji)巡回旅行商問題4.3 計(jì)算(j sun)仿真結(jié)果990.0829 路徑長度：遷移代數(shù)：50共一百零一頁4遺傳算法求解(qi ji)巡回旅行商問題4.3 計(jì)算仿真(fn zhn)結(jié)果701.7754 路徑長度：遷移代數(shù)：100共一百零一頁4 遺傳算法求解巡回旅行(lxng)商問題4.3 計(jì)算(j sun)仿真結(jié)果624.1821 路徑長度：遷移代數(shù)：150共一百零一頁4 遺傳算法求解(qi

46、 ji)巡回旅行商問題4.3 計(jì)算(j sun)仿真結(jié)果523.2674 路徑長度：遷移代數(shù)：200共一百零一頁4 遺傳算法求解巡回(xnhu)旅行商問題4.3 計(jì)算(j sun)仿真結(jié)果491.4063 路徑長度：遷移代數(shù)：250共一百零一頁4 遺傳算法求解巡回旅行(lxng)商問題4.3 計(jì)算(j sun)仿真結(jié)果453.1959路徑長度：遷移代數(shù)：300共一百零一頁4 遺傳算法求解巡回旅行(lxng)商問題4.3 計(jì)算(j sun)仿真結(jié)果430.3986 路徑長度：遷移代數(shù)：350共一百零一頁4.3 計(jì)算(j sun)仿真結(jié)果424.8693 路徑(ljng)長度：遷移代數(shù)：400Be

47、st4 遺傳算法求解巡回旅行商問題共一百零一頁距離(jl)為426.64Km的訪問次序距離為424.78Km的訪問(fngwn)次序（最優(yōu)）距離為431.94Km的訪問次序4 遺傳算法求解巡回旅行商問題共一百零一頁距離(jl)為424.78Km的訪問次序（最優(yōu)）距離為466.30Km的訪問(fngwn)次序距離為454.75Km的訪問次序4 遺傳算法求解巡回旅行商問題共一百零一頁4.4 關(guān)于遺傳算法操作算子(sun z)的驗(yàn)證4 遺傳算法求解巡回(xnhu)旅行商問題“實(shí)驗(yàn)數(shù)據(jù)”課程所做的正交試驗(yàn)極差分析結(jié)果（遷移500代后退出的結(jié)果）。共一百零一頁對于上表，有（驗(yàn)證）以下基本結(jié)論：（1）遺傳

48、算法搜索求解能力與四個(gè)因素有關(guān)(yugun)：群體規(guī)模、選擇算子、交叉率和變異率 。（2）從主到次依次為：交叉率群體規(guī)模選擇算子變異率。（3）A3-B2-C1-D3是優(yōu)選方案。4 遺傳算法求解巡回旅行(lxng)商問題共一百零一頁左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次遷移1000代，有36次能收斂到全局(qunj)最優(yōu)解）是比較優(yōu)的參數(shù)組合。實(shí)際上可看出，迭代進(jìn)行到450代之后，所得到得最優(yōu)個(gè)體基本不再發(fā)生變化，且其最優(yōu)路徑與真實(shí)的最有路徑差距非常小。4 遺傳算法求解(qi ji)巡回旅行商問題共一百零一頁左圖（進(jìn)行50次獨(dú)立運(yùn)算(yn sun)求解，每次遷移1000代，有24次能收斂到全局最優(yōu)解

49、）表明：選擇算子取值太大，收斂速度很快，但陷入局部最優(yōu)解的可能性大大提高，而基本上不可能再跳出來。約350代便收斂(shulin)4 遺傳算法求解巡回旅行商問題共一百零一頁左圖（進(jìn)行50次獨(dú)立運(yùn)算(yn sun)求解，每次迭代1000代，僅有6次能收斂到全局最優(yōu)解）表明：交叉率選取太大，導(dǎo)致群體中的優(yōu)良模式遭到破壞，產(chǎn)生較大的代溝，從而使搜索走向隨機(jī)化。450Km左右(zuyu)4 遺傳算法求解巡回旅行商問題共一百零一頁左圖（進(jìn)行50次獨(dú)立(dl)運(yùn)算求解，每次遷移1000代，有18次能收斂到全局最優(yōu)解）表明：變異率選取太大，遺傳算法幾乎退化為隨機(jī)搜索，陷入局部最優(yōu)解后比較難跳出來。約380代

50、左右(zuyu)4 遺傳算法求解巡回旅行商問題共一百零一頁2022年7月27日79GA優(yōu)化NN的權(quán)重（結(jié)構(gòu)確定(qudng)）GA優(yōu)化NN的結(jié)構(gòu)：神經(jīng)元數(shù)和連接狀況x1輸出層隱藏層輸入層x2yxnw1wiwn5遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)共一百零一頁2022年7月27日80 編碼(bin m)（實(shí)數(shù)編碼(bin m)1、GA優(yōu)化NN的權(quán)重(qun zhn)共一百零一頁2022年7月27日81定義適應(yīng)度直接采用方差和.評估(pn )過程：對每個(gè)解進(jìn)行樣本測試（前向計(jì)算），計(jì)算其實(shí)際輸出和期望輸出的誤差（適應(yīng)度）。如果有一個(gè)個(gè)體的適應(yīng)度滿足精度要求，則結(jié)束1、GA優(yōu)化NN的權(quán)重(qun zhn)共一百零一

51、頁2022年7月27日82遺傳操作：交叉(jioch)1、GA優(yōu)化NN的權(quán)重(qun zhn)共一百零一頁2022年7月27日831、GA優(yōu)化NN的權(quán)重(qun zhn)遺傳操作：變異(biny)共一百零一頁2022年7月27日841、GA優(yōu)化NN的權(quán)重(qun zhn)共一百零一頁2022年7月27日85BP算法(sun f)和GA算法結(jié)合 GA擅長全局優(yōu)化搜索，BP擅長局部優(yōu)化搜索；兩者結(jié)合，可提高收斂速度(sd)?？朔礼A過早收斂的問題1、GA優(yōu)化NN的權(quán)重共一百零一頁2022年7月27日86先用GA找出全局(qunj)最優(yōu)解的大概位置，然后采用BP算法微調(diào)得到全局最優(yōu)解。1、GA優(yōu)化N

52、N的權(quán)重(qun zhn)BP算法和GA算法結(jié)合：方法一GA+BPGA轉(zhuǎn)換點(diǎn)共一百零一頁2022年7月27日871、GA優(yōu)化NN的權(quán)重(qun zhn)BP算法和GA算法結(jié)合(jih)：方法二交替使用BP和GA第一步:利用GA找出一個(gè)最優(yōu)解；第二步：利用BP對該最優(yōu)解進(jìn)行微調(diào)；第三步：如果發(fā)現(xiàn)微調(diào)后的最優(yōu)解不夠理想，則返回第一步；否則停止。共一百零一頁2022年7月27日88算法：1.隨機(jī)產(chǎn)生一個(gè)具有N個(gè)個(gè)體的初始群體；2.計(jì)算每個(gè)個(gè)體的適應(yīng)值，如果有一個(gè)個(gè)體的適應(yīng)度滿足精度(jn d)要求，則結(jié)束，否則進(jìn)行下一步；3.按適應(yīng)度比例挑選出父本群體；4.對父本群體進(jìn)行雜交、變異操作得到新的群體；5.找出當(dāng)前群體中適應(yīng)度最大的個(gè)體best；6.對best用BP進(jìn)行一到二次學(xué)習(xí)，得best；7.用best替代best，轉(zhuǎn)向2；1、GA優(yōu)化NN的權(quán)重(qun zhn)共一百零一頁2022年7月27日89編碼NN的連接拓?fù)淇梢杂靡粋€(gè)連接矩陣表示 矩陣中的每個(gè)元素若為0，則表示相應(yīng)(xingyng)的神經(jīng)元之間無連接；若為1，表示有連接。