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

數(shù)學(xué)建模專題之MATLAB遺傳算法第一頁，共九十七頁，編輯于2023年，星期六Contents遺傳算法概述1標(biāo)準(zhǔn)遺傳算法2遺傳算法簡單舉例：函數(shù)極值3遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)5遺傳算法求解TSP問題4遺傳算法的實現(xiàn)6第二頁，共九十七頁，編輯于2023年，星期六ContentsofSection11.4什么是遺傳算法1.11.21.3遺傳算法的特點遺傳算法的發(fā)展歷程遺傳算法的研究和應(yīng)用領(lǐng)域1遺傳算法概述第三頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述1.1遺傳算法（GeneticAlgorithm,GA）一種仿生全局優(yōu)化算法模仿生物的遺傳進(jìn)化原理（Darwin’stheoryofevolution&Mendel’slawofinheritance)，通過選擇（Selection）、交叉（Crossover）與變異（Mutation）等操作機制，使種群中個體的適應(yīng)性（Fitness）不斷提高核心思想：物競天擇，適者生存

（“天”——適應(yīng)度函數(shù)，F(xiàn)itnessFunction)第四頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述1.2遺傳算法的特點四大優(yōu)點：良好的并行性（操作對象是一組可行解；搜索軌道有多條）強大的通用性（只需利用目標(biāo)的取值信息，無需梯度等高價值信息）良好的全局優(yōu)化性和魯棒性良好的可操作性兩個缺點：未成熟收斂問題收斂速度較慢，算法實時性欠佳第五頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述1.3遺傳算法的發(fā)展歷史年份貢獻(xiàn)者內(nèi)容1962Holland程序漫游元胞計算機自適應(yīng)系統(tǒng)框架1968Holland模式定理的建立1971Hollstein具有交配和選擇規(guī)則的二維函數(shù)優(yōu)化1972BosworthFoo,Zeigler提出具有復(fù)雜變異、類似于遺傳算法的基因操作1972Frantz位置非線性和倒位操作研究1973Holland遺傳算法中試驗的最優(yōu)配置和雙臂強盜問題1973Martin類似遺傳算法的概率算法理論1975DeJong用于5個測試函數(shù)的研究基本遺傳短發(fā)基準(zhǔn)參數(shù)1975Holland出版開創(chuàng)性著作《AdaptationinNaturalandArtificialSystems》表1.1遺傳算法理論的經(jīng)典研究成果第一階段：20世紀(jì)60年代至70年代中期（萌芽期）第六頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述年份貢獻(xiàn)者內(nèi)容1981Bethke應(yīng)用Walsh函數(shù)分析模式1981Brindle研究遺傳算法中的選擇和支配問題1983Pettit,Swigger遺傳算法應(yīng)用于非穩(wěn)定問題的粗略研究1983Wetzel用遺傳算法解決旅行商問題（TSP)1984Mauldin基本遺傳算法中用啟發(fā)知識維持遺傳多樣性1985Baker試驗基于排序的選擇方法1985Booker建議采用部分分配計分、分享操作和交配限制法1985Goldberg,LingleTSP問題中采用部分匹配交叉1985Grefenstette,Fitzpattrick對含噪聲的函數(shù)進(jìn)行測試1985Schaffer多種群遺傳算法解決多目標(biāo)優(yōu)化問題續(xù)表1.1第七頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述年份貢獻(xiàn)者內(nèi)容1986Goldberg最優(yōu)種群大小估計1986Grefenstette元級遺傳算法控制的遺傳算法1987Baker選擇中隨機誤差的較少方法1987Goldberg復(fù)制和交叉時最小欺騙問題（MDP）1987Goldberg,Richardson借助分享函數(shù)的小生境和物種歸納法1987Goldberg,Segrest復(fù)制和交叉的有限馬爾科夫鏈1987Goldberg,Smith雙倍染色體遺傳算法應(yīng)用于非穩(wěn)定函數(shù)優(yōu)化1987Oliver,Smith,Holland排列重組算子的模擬和分析1987Schaffer,Morishima串編碼自適應(yīng)交叉試驗1987Whitley子孫測試應(yīng)用于遺傳算法的選擇操作續(xù)表1.1第二階段：20世紀(jì)80年代（蓬勃發(fā)展期）第八頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述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è)計、模糊控制器優(yōu)化設(shè)計和在線修改隸屬度函數(shù)、人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計和調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)等優(yōu)化問題）（5）機器人智能控制（如移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學(xué)求解等）（6）圖像處理和模式識別（如圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識別等）（7）機器學(xué)習(xí)（將GA用于知識獲取，構(gòu)建基于GA的機器學(xué)習(xí)系統(tǒng)）此外，遺傳算法在人工生命、遺傳程序設(shè)計、社會和經(jīng)濟領(lǐng)域等方面的應(yīng)用盡管不是很成熟，但還是取得了一定的成功。在日后，必定有更深入的發(fā)展。Hotspot第九頁，共九十七頁，編輯于2023年，星期六ContentsofSection22.4遺傳算法的生物學(xué)基礎(chǔ)2.12.22.32.5遺傳算法的基本流程遺傳算法的若干基本概念遺傳算法的應(yīng)用步驟欺騙問題和未成熟收斂問題第十頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.1遺傳算法的生物學(xué)基礎(chǔ)細(xì)胞（Cell）染色體（Chromosome）脫氧核糖核酸（DeoxyribonucleicAcid，DNA）基因（Gene）、

等位基因（Allele）基因型（Genotype）表現(xiàn)型（Phenotype）復(fù)制（Reproduction）交叉（Crossover）變異（Mutation）對環(huán)境的適應(yīng)性“種瓜得瓜，種豆得豆”第十一頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.1遺傳算法的生物學(xué)基礎(chǔ)個體（Individual）種群（Population）適應(yīng)度（Fitness）進(jìn)化（Evolution）生存（Survival）LowHigh“物競天擇，適者生存”死亡

（Death）滅絕（Extinction）第十二頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.2標(biāo)準(zhǔn)遺傳算法的基本流程實際問題參數(shù)集參數(shù)編碼成為染色體初始化群體計算每一個體的適應(yīng)度對染色體進(jìn)行解碼滿足終止條件？得到問題最優(yōu)解進(jìn)行遺傳操作群體←新群體P(t)←P(t+1)1、選擇2、交叉3、變異第十三頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.3遺傳算法的若干概念個體(Individual)稱為個體空間，個體空間的元素稱為個體，它是染色體帶有特征的實體。分量稱為基因，正整數(shù)稱為個體的基因長度。種群(Population)

稱個體空間S中N個個體組成的一個子集（個體允許重復(fù)）稱為一個種群，記為：

其中，N稱為種群規(guī)模。第十四頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.3遺傳算法的若干概念適應(yīng)度（Fitness）在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時，生物學(xué)家使用適應(yīng)度這個術(shù)語來度量某個物種對于生存環(huán)境的適應(yīng)程度。對生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機會，而對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機會就會相對較少，甚至逐漸滅絕。在遺傳算法中，一般通過適應(yīng)度函數(shù)（Fitnessfunction）來衡量某一個體的適應(yīng)度高低。第十五頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法解碼（Decoding）解碼是將遺傳算法所搜索到的最優(yōu)個體的染色體轉(zhuǎn)換成待求解問題的實際最優(yōu)解的過程，即編碼的逆過程。

2.3

遺傳算法的若干概念編碼（Coding）將一個待求解的問題的實際可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間（即個體空間）的過程，就稱為編碼。第十六頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法選擇操作（Selection）根據(jù)各個個體的適應(yīng)度，按照一定的規(guī)則，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中。一般地，選擇操作通過選擇算子（SelectionOperator）進(jìn)行。

2.3

遺傳算法的若干概念交叉操作（Crossover）將群體P(t)內(nèi)的各個個體隨機搭配成對，對每一對個體，以某個概率（稱為交叉概率，CrossoverRate）遵循某一種規(guī)則交換它們之間的部分染色體。變異操作（Mutation）對群體P(t)中的每一個個體，以某一概率（稱為變異概率，MutationRate）改變某一個或某一些基因座上的基因值為其他的等位基因。第十七頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.4遺傳算法的應(yīng)用步驟（1）確定決策變量及各種約束條件，即確定出個體的表現(xiàn)型X和問題的解空間。（2）建立優(yōu)化模型，確定出目標(biāo)函數(shù)的類型及其數(shù)學(xué)描述形式或量化方法。（3）確定表示可行解的染色體編碼方法，即確定出個體的基因型X*，及遺傳算法的搜索空間。

編碼是遺傳算法解決問題的先決條件和關(guān)鍵步驟:

①不僅決定個體基因的排列形式（從而決定選擇與繁殖等操作的作用方式），而且也決定從搜索空間的基因型到解空間的表現(xiàn)型的解碼方式（從而決定對GA所獲解的翻譯與理解）；

②決定GA搜索的困難度與復(fù)雜性；

③決定對問題的求解精度。常用的遺傳算法編碼方法主要有：二進(jìn)制編碼、浮點數(shù)編碼等?？梢宰C明，二進(jìn)制編碼比浮點數(shù)編碼搜索能力強，但浮點數(shù)編碼比二進(jìn)制編碼在變異操作上能夠保持更好的種群多樣性。第十八頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.4

遺傳算法的應(yīng)用步驟（4）確定解碼方法，即確定出由個體基因型X*，到個體表現(xiàn)型X的對應(yīng)關(guān)系和轉(zhuǎn)換方法。標(biāo)準(zhǔn)遺傳算法多采用二進(jìn)制編碼方法，將決策變量用二進(jìn)制字符串表示，二進(jìn)制編碼串的長度由所求精度決定。然后將各決策變量的二進(jìn)制編碼串連接在一起，構(gòu)成一個染色體。例如：變量x的定義域為[-2，3]，要求其精度為10-5，則需要將[-2，3]分成至少500000個等長小區(qū)域，而每個小區(qū)域用一個二進(jìn)制串表示。于是有，2L=500000，即向上取整，可得到L=19。即可用19位二進(jìn)制串a(chǎn)18a17…a0來表示。例如：對于二進(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ù)值。第十九頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法（5）確定個體適應(yīng)度的量化評價方法，就是確定出由目標(biāo)函數(shù)值到個體適應(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)點：簡單直觀；

缺點：其一，可能不滿足非負(fù)的要求；其二，某些代求解的函數(shù)值分布相差很大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能。若目標(biāo)函數(shù)為最大值問題，則Cmax為f(x)的最大值估計。第二十頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法Ⅲ倒數(shù)法若目標(biāo)函數(shù)為最小值問題，則2.4

遺傳算法的應(yīng)用步驟該方法是第一種方法的改進(jìn)，但有時存在界限值預(yù)先估計困難或估計不精確等問題。Cmin為f(x)的最小值估計。若目標(biāo)函數(shù)為最小值問題，則若目標(biāo)函數(shù)為最大值問題，則C為目標(biāo)函數(shù)界限的保守估計值。第二十一頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法（6）確定各遺傳具體操作方法。2.4

遺傳算法的應(yīng)用步驟①選擇算子和選擇操作個體選擇概率的常用分配方法有以下兩種：A按比例的適應(yīng)度分配（ProportionalFitnessAssignment）亦可稱為選擇的蒙特卡羅方法，是利用比例于各個個體適應(yīng)度的概率決定其子孫的遺留可能性。若某個個體i，其適應(yīng)度為fi，則其被選取的概率表示為,顯然選擇概率大的個體，能多次被選中，它的遺傳因子就會在種群中擴大。B基于排序的適應(yīng)度分配（Rank-basedFitnessAssignment）在基于排序的適應(yīng)度分配中，種群按目標(biāo)值進(jìn)行排序。適應(yīng)度僅僅取決于個體在種群中的序位，而不是實際的目標(biāo)值。排序方法比比例方法表現(xiàn)出更好的魯棒性，它能在一定程度上克服了比例適應(yīng)度計算的尺度問題和過早收斂問題。第二十二頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.5

遺傳算法的應(yīng)用步驟另外，還可采用以下的幾種提高遺傳算法性能的選擇方法：Ⅰ穩(wěn)態(tài)繁殖（SteadyStateReproduction）在迭代過程中用部分優(yōu)質(zhì)新子個體來更新群體中部分父個體，作為下一代種群。Ⅱ沒有重串的穩(wěn)態(tài)繁殖（SteadyStateReproductionwithoutDuplicates）在穩(wěn)態(tài)繁殖的基礎(chǔ)上，形成下一代新種群時，使其中的個體不重復(fù)。個體選擇概率確定后，可以選用的常用選擇算法有輪盤賭選擇法（RouletteWheelSelection）、隨機遍歷抽樣法（StochasticUniversalSampling）、局部選擇法（LocalSelection）、截斷選擇法（TruncationSelection）和錦標(biāo)賽選擇法（TournamentSelection）等。標(biāo)準(zhǔn)遺傳算法常用的輪盤賭選擇法的原理如右下圖所示。pointer關(guān)于選擇算子：如果對解的質(zhì)量要求不高，要求收斂快，可取較高的選擇強度；反之，可取較低的選擇強度。標(biāo)準(zhǔn)遺傳算法達(dá)到收斂的世代數(shù)與選擇強度成反比。第二十三頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法②交叉率及交叉操作交叉，也可以稱為基因重組（Recombination），是遺傳算法獲取新的優(yōu)良個體的最重要的手段，決定了遺傳算法的全局搜索能力。

一般地，當(dāng)隨機產(chǎn)生的概率大于交叉率，遺傳算法就會按一定規(guī)則選擇兩個個體，執(zhí)行交叉操作。交叉率的選擇決定了交叉的頻率，較大的交叉率使各代充分交叉，但群體中的優(yōu)良模式遭到破壞的可能性增大，以致產(chǎn)生較大的代溝，從而使搜索走向隨機化；交叉率越低，產(chǎn)生的代溝越小，就會使得更多的個體直接復(fù)制到下一代，遺傳搜索可能陷入停滯狀態(tài)，一般建議取值范圍0.4~0.9。對于二進(jìn)制編碼，常用的交叉方法有：單點交叉、多點交叉和均勻交叉等。一個單點交叉的例子如下圖所示。第二十四頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法③變異率及變異操作變異本身是一種局部隨機搜索，使遺傳算法具有局部的隨機搜索能力；同時使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。一般地，隨機產(chǎn)生的概率大于變異率就會觸發(fā)變異操作。變異率一般可取0.001~0.1。變異率不能取得太大，如果大于0.5，遺傳算法就退化為隨機搜索，而遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力也不復(fù)存在了。常用的變異操作方法有：實值變異法和二進(jìn)制變異法等。實值變異法a(i)以概率1/m取值1，以概率1-1/m取值0，通常m=20

此外，還有部分匹配交叉（PartiallyMatchedCrossover）、順序交叉（OrderedCrossover）、洗牌交叉（ShuffleCrossover）等等。二進(jìn)制變異法第二十五頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法（7）確定遺傳算法的有關(guān)運行參數(shù)，包括群體規(guī)模(PopulationSize)、迭代次數(shù)（一般取為100~500）、選擇算子、交叉率、變異率等等。（8）初始化群體。初始群體一般隨機產(chǎn)生初始值最好能在解空間中均勻采樣（收斂速度比較快）對于非二進(jìn)制編碼，還要考慮所生成的染色體是否在可行區(qū)域內(nèi)。（9）計算群體中個體解碼后的適應(yīng)值。（10）按照遺傳策略，運用所選定的選擇、交叉和變異算子作用于群體，生成下一代群體。（11）判斷群體性能是否滿足某一指標(biāo)或是否完成預(yù)定迭代次數(shù)，不滿足則返回（9）。popsize取值較小時提高運算和收斂速度卻降低了群體多樣性，可能引起早熟現(xiàn)象取值較大時含有較多模式，可提高GA搜索質(zhì)量但計算量增大，收斂速度降低一般取為20~100第二十六頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.6

欺騙問題和未成熟收斂問題2.6.1欺騙問題（DeceptiveProblem）競爭模式：若模式H與H’中，*的位置完全一致，但任一確定位的編碼均不一樣，則稱H與H’互為競爭模式。欺騙性：假設(shè)f(X)的最大值對應(yīng)的X集合為X*，H為一包含X*的m階模式。H的競爭模式為H’，而且f(H)>f(H’)，則f為m階欺騙。欺騙問題：在遺傳算法中，將所有妨礙評價值高的個體生成從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題。如對于一個2位二進(jìn)制編碼的模式，如果f(11)為最大值，則以下不等式任意一個成立，則存在欺騙性問題：

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ù)等方法來化解。第二十七頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法（1）未成熟收斂現(xiàn)象未成熟收斂現(xiàn)象是遺傳算法中的特有現(xiàn)象，且十分常見。它是指，當(dāng)遺傳算法還沒找到全局最優(yōu)解或滿意解時，群體中不能再產(chǎn)生性能超過父代的后代，群體中的各個個體非常相似。未成熟收斂的重要特征是群體中個體結(jié)構(gòu)的多樣性急劇減少。2.6.2未成熟收斂問題（PrematureConvergence）（2）未成熟收斂產(chǎn)生的原因①理論上考慮的選擇、交叉、變異操作都是絕對精確的，他們相互協(xié)調(diào)，能搜索到整個解空間，但實際不然；②存在隨機誤差（主要包括取樣誤差和選擇誤差）；③所求解的問題是遺傳算法欺騙問題。（3）未成熟收斂的防止重新啟動法替代策略（ReplacementStrategies）重組策略（RecombinationStrategies）匹配策略（MatingStrategies）提高多樣性第二十八頁，共九十七頁，編輯于2023年，星期六遺傳算法具體步驟選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；定義適應(yīng)度函數(shù)，便于計算適應(yīng)值；確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數(shù)；隨機產(chǎn)生初始化群體；計算群體中的個體或染色體解碼后的適應(yīng)值；按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代群體；判斷群體性能是否滿足某一指標(biāo)，或者已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步，或者修改遺傳策略再返回第六步．2標(biāo)準(zhǔn)遺傳算法第二十九頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法程序流程圖開始Gen=0編碼隨機產(chǎn)生M個初始個體滿足終止條件?計算群體中各個體適應(yīng)度從左至右依次執(zhí)行遺傳算子j=0j=0j=0根據(jù)適應(yīng)度選擇復(fù)制個體選擇兩個交叉?zhèn)€體選擇個體變異點執(zhí)行變異執(zhí)行交叉執(zhí)行復(fù)制將復(fù)制的個體添入新群體中將交叉后的兩個新個體添入新群體中將變異后的個體添入新群體中j=j+1j=j+2j=j+1

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1輸出結(jié)果終止YNYYYNNNpcpm第三十頁，共九十七頁，編輯于2023年，星期六

例1利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值，精度要求達(dá)到個位。

y=x2

31

XY3、遺傳算法簡單舉例：函數(shù)極值第三十一頁，共九十七頁，編輯于2023年，星期六

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。3、遺傳算法簡單舉例：函數(shù)極值第三十二頁，共九十七頁，編輯于2023年，星期六

(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

3、遺傳算法簡單舉例：函數(shù)極值第三十三頁，共九十七頁，編輯于2023年，星期六(3)計算各代種群中的各個體的適應(yīng)度,并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個體(即31（11111）)出現(xiàn)為止。

首先計算種群S1中各個體

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=3613、遺傳算法簡單舉例：函數(shù)極值第三十四頁，共九十七頁，編輯于2023年，星期六再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.313、遺傳算法簡單舉例：函數(shù)極值第三十五頁，共九十七頁，編輯于2023年，星期六輪盤賭選擇示意圖s40.31s20.49s10.14s30.063、遺傳算法簡單舉例：函數(shù)極值第三十六頁，共九十七頁，編輯于2023年，星期六選擇-復(fù)制

染色體適應(yīng)度選擇概率選中次數(shù)s1=011011690.141s2=110005760.492s3=01000640.060s4=100113610.311于是，經(jīng)選擇復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）3、遺傳算法簡單舉例：函數(shù)極值第三十七頁，共九十七頁，編輯于2023年，星期六交叉

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

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

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

3、遺傳算法簡單舉例：函數(shù)極值第三十八頁，共九十七頁，編輯于2023年，星期六變異設(shè)變異率pm=0.001。這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。于是，得到第二代種群S2：

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

s3=11011（27）,s4=10000（16）3、遺傳算法簡單舉例：函數(shù)極值第三十九頁，共九十七頁，編輯于2023年，星期六

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

染色體適應(yīng)度選擇概率估計的選中次數(shù)s1=110016250.361s2=011001440.080s3=110117290.412s4=100002560.1513、遺傳算法簡單舉例：函數(shù)極值第四十頁，共九十七頁，編輯于2023年，星期六假設(shè)這一輪選擇-復(fù)制操作中，種群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（24）,s4=10011（19）

3、遺傳算法簡單舉例：函數(shù)極值第四十一頁，共九十七頁，編輯于2023年，星期六第三代種群S3中各染色體的情況

染色體適應(yīng)度選擇概率估計的選中次數(shù)s1=111007840.442s2=01001810.040s3=110005760.321s4=100113610.2013、遺傳算法簡單舉例：函數(shù)極值第四十二頁，共九十七頁，編輯于2023年，星期六設(shè)這一輪的選擇-復(fù)制結(jié)果為：

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）,s4’’=10000（16）

這一輪仍然不會發(fā)生變異。于是，得第四代種群S4：

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

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

3、遺傳算法簡單舉例：函數(shù)極值第四十三頁，共九十七頁，編輯于2023年，星期六顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。

3、遺傳算法簡單舉例：函數(shù)極值第四十四頁，共九十七頁，編輯于2023年，星期六YYy=x2

8131924

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

12162527

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

9192428

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

16242831

X第四代種群及其適應(yīng)度第四十五頁，共九十七頁，編輯于2023年，星期六課堂練習(xí)求一元函數(shù)f(x)的最大值：要求求解精度到6位小數(shù)第四十六頁，共九十七頁，編輯于2023年，星期六編碼表現(xiàn)型：x

基因型：二進(jìn)制編碼（串長取決于求解精度）按編碼原理：假設(shè)要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。 所以編碼的二進(jìn)制串長應(yīng)為22位。第四十七頁，共九十七頁，編輯于2023年，星期六產(chǎn)生初始種群產(chǎn)生的方式：隨機產(chǎn)生的結(jié)果：長度為22的二進(jìn)制串產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……第四十八頁，共九十七頁，編輯于2023年，星期六計算適應(yīng)度 直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)①解碼：將個體s轉(zhuǎn)化為[-1,2]區(qū)間的實數(shù)：

s=<1000101110110101000111>→x=0.637197②計算x的函數(shù)值（適應(yīng)度）：

f(x)=xsin(10πx)+2.0=2.586345第四十九頁，共九十七頁，編輯于2023年，星期六遺傳操作選擇：比例選擇法；交叉：單點交叉；變異：小概率變異第五十頁，共九十七頁，編輯于2023年，星期六模擬結(jié)果

設(shè)置的參數(shù)：種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。

得到的最佳個體：

smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;第五十一頁，共九十七頁，編輯于2023年，星期六模擬結(jié)果

進(jìn)化的過程：世代數(shù)自變量適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503第五十二頁，共九十七頁，編輯于2023年，星期六考慮問題：能否用遺傳算法解決以下問題1、2、3、第五十三頁，共九十七頁，編輯于2023年，星期六ContentsofSection4巡回旅行商問題4.14.24.3基本操作計算仿真結(jié)果4遺傳算法求解巡回旅行商問題第五十四頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.1巡回旅行商問題City5City1City2City3City4巡回旅行商問題（Travelingsalesmanproblem,TSP）可描述如下：已知N個城市之間的相互距離，現(xiàn)有一推銷員必須遍歷這N個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市，如何安排他訪問這些城市的次序，使其旅行路線總長度最短？第五十五頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題CHN31問題60Cities第五十六頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題TSP具有廣泛的應(yīng)用背景和重要理論價值，特別在機器人運動規(guī)劃中得到許多應(yīng)用，例如：移動機器人的全局路徑規(guī)劃問題（如右上圖）、焊接機器人的任務(wù)規(guī)劃問題（如右下圖）等等。但是，巡回旅行商問題中可能的路徑數(shù)目與城市數(shù)目N呈指數(shù)型增長，所有的旅程路線組合數(shù)為其已經(jīng)被證明屬于NP難題。例如30個城市的路線對應(yīng)約有對龐大的搜索空間尋求最優(yōu)解，常規(guī)方法和現(xiàn)有的計算工具存在著諸多的計算困難。第五十七頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題序號X坐標(biāo)Y坐標(biāo)序號X坐標(biāo)Y坐標(biāo)序號X坐標(biāo)Y坐標(biāo)11854117144217642877612646022226037478136858232562471711483692462325253815586925877658351654622691387450175167278346813401837842841269184019419429452110244220299304435本例所用30個城市的XY坐標(biāo)：第五十八頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.2基本操作（1）編碼與解碼采用對訪問城市序列進(jìn)行排列組合的方法編碼，即某個巡回路徑的染色體是該巡回路徑的城市序列。對于N（N為城市總數(shù)）進(jìn)制編碼，即每個基因僅從1到N得整數(shù)里面取一個值，每個個體的長度為N。根據(jù)編碼方法，一次求解得出的最優(yōu)解（個體）是所訪問的城市的次序，需要轉(zhuǎn)換成相應(yīng)的城市坐標(biāo)進(jìn)行輸出，則只需將個體的染色體值作為存儲30個城市坐標(biāo)的矩陣的下標(biāo)來引用，輸出對應(yīng)的矩陣元素，便可實現(xiàn)解碼。一行的前30個元素為一個個體30個城市的訪問次序該種訪問次序路徑的距離利用矩陣來存儲：第五十九頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題（2）適應(yīng)度函數(shù)：在TSP問題中，用路徑的總長度作為適應(yīng)度函數(shù)來衡量求解結(jié)果是否最優(yōu)，路徑越短對應(yīng)的個體越優(yōu)，其適應(yīng)度值應(yīng)越大。兩城市間的距離為：個體代表的路徑的總長度為：則可采用倒數(shù)法將適應(yīng)度函數(shù)取為：（3）選擇操作：將群體中適應(yīng)度較大的C個個體直接替換適應(yīng)度較小的C個個體。其中C值與選擇算子和群體規(guī)模的關(guān)系在這里取為：第六十頁，共九十七頁，編輯于2023年，星期六A1：（

｜3456｜

）××××第一步：保留交叉點的中間部分第二步：交換對應(yīng)位置的子串A2：（

｜0853｜）×××A2：（429｜0853｜1

76）××A1：（012｜3456｜789）2917974遺傳算法求解巡回旅行商問題本例中采用有序交叉執(zhí)行交叉操作。有序交叉能夠有效地繼承雙親的部分基因成分，達(dá)到了進(jìn)化的遺傳功能，使該遺傳算法并不盲目搜索，二是趨向于使群體具有更多的優(yōu)良基因。交叉后，考察父個體與子個體的適應(yīng)度來決定是否更新種群。具體操作過程如下（以0~9編碼為例）：（4）交叉操作

父個體：（“|”表示交叉點）×××301248664第六十一頁，共九十七頁，編輯于2023年，星期六變異后子代個體：567|8412|3904遺傳算法求解巡回旅行商問題變異操作中，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則仍保留父代染色體。本例中，采用倒置變異法。例如：假設(shè)當(dāng)前個體為“5678412390”，如果當(dāng)前隨機值p∈[0，1]≥pmutation，則隨機選擇來自同一個體的兩個點（設(shè)為“8”和“2”），執(zhí)行變異操作，即倒置該兩點的中間部分。產(chǎn)生的新個體為“5672148390”。（5）變異操作（6）群體初始化2變異前父代個體：567|

|390148pop=zeros(s,t);fori=1:spop(i,1:t-1)=randperm(t-1);end第六十二頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計算仿真結(jié)果990.0829路徑長度：遷移代數(shù)：50第六十三頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計算仿真結(jié)果701.7754路徑長度：遷移代數(shù)：100第六十四頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計算仿真結(jié)果624.1821路徑長度：遷移代數(shù)：150第六十五頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計算仿真結(jié)果523.2674路徑長度：遷移代數(shù)：200第六十六頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計算仿真結(jié)果491.4063路徑長度：遷移代數(shù)：250第六十七頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計算仿真結(jié)果453.1959路徑長度：遷移代數(shù)：300第六十八頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計算仿真結(jié)果430.3986路徑長度：遷移代數(shù)：350第六十九頁，共九十七頁，編輯于2023年，星期六4.3計算仿真結(jié)果424.8693路徑長度：遷移代數(shù)：400Best4遺傳算法求解巡回旅行商問題第七十頁，共九十七頁，編輯于2023年，星期六距離為426.64Km的訪問次序距離為424.78Km的訪問次序（最優(yōu)）距離為431.94Km的訪問次序4遺傳算法求解巡回旅行商問題第七十一頁，共九十七頁，編輯于2023年，星期六距離為424.78Km的訪問次序（最優(yōu)）距離為466.30Km的訪問次序距離為454.75Km的訪問次序4遺傳算法求解巡回旅行商問題第七十二頁，共九十七頁，編輯于2023年，星期六4.4關(guān)于遺傳算法操作算子的驗證4遺傳算法求解巡回旅行商問題“實驗數(shù)據(jù)”課程所做的正交試驗極差分析結(jié)果（遷移500代后退出的結(jié)果）。第七十三頁，共九十七頁，編輯于2023年，星期六對于上表，有（驗證）以下基本結(jié)論：（1）遺傳算法搜索求解能力與四個因素有關(guān)：群體規(guī)模、選擇算子、交叉率和變異率。（2）從主到次依次為：交叉率——群體規(guī)?！x擇算子——變異率。（3）A3-B2-C1-D3是優(yōu)選方案。4遺傳算法求解巡回旅行商問題第七十四頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨立運算求解，每次遷移1000代，有36次能收斂到全局最優(yōu)解）是比較優(yōu)的參數(shù)組合。實際上可看出，迭代進(jìn)行到450代之后，所得到得最優(yōu)個體基本不再發(fā)生變化，且其最優(yōu)路徑與真實的最有路徑差距非常小。4遺傳算法求解巡回旅行商問題第七十五頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨立運算求解，每次遷移1000代，有24次能收斂到全局最優(yōu)解）表明：選擇算子取值太大，收斂速度很快，但陷入局部最優(yōu)解的可能性大大提高，而基本上不可能再跳出來。約350代便收斂4遺傳算法求解巡回旅行商問題第七十六頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨立運算求解，每次迭代1000代，僅有6次能收斂到全局最優(yōu)解）表明：交叉率選取太大，導(dǎo)致群體中的優(yōu)良模式遭到破壞，產(chǎn)生較大的代溝，從而使搜索走向隨機化。450Km左右4遺傳算法求解巡回旅行商問題第七十七頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨立運算求解，每次遷移1000代，有18次能收斂到全局最優(yōu)解）表明：變異率選取太大，遺傳算法幾乎退化為隨機搜索，陷入局部最優(yōu)解后比較難跳出來。約380代左右4遺傳算法求解巡回旅行商問題第七十八頁，共九十七頁，編輯于2023年，星期六2023年5月31日79GA優(yōu)化NN的權(quán)重（結(jié)構(gòu)確定）GA優(yōu)化NN的結(jié)構(gòu)：神經(jīng)元數(shù)和連接狀況x1輸出層隱藏層輸入層x2yxn…………w1wiwn5遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)第七十九頁，共九十七頁，編輯于2023年，星期六2023年5月31日80

編碼（實數(shù)編碼)1、GA優(yōu)化NN的權(quán)重第八十頁，共九十七頁，編輯于2023年，星期六2023年5月31日81定義適應(yīng)度直接采用方差和.評估過程：對每個解進(jìn)行樣本測試（前向計算），計算其實際輸出和期望輸出的誤差（適應(yīng)度）。如果有一個個體的適應(yīng)度滿足精度要求，則結(jié)束1、GA優(yōu)化NN的權(quán)重第八十一頁，共九十七頁，編輯于2023年，星期六2023年5月31日82遺傳操作：交叉1、GA優(yōu)化NN的權(quán)重第八十二頁，共九十七頁，編輯于2023年，星期六2023年5月31日831、GA優(yōu)化NN的權(quán)重遺傳操作：變異第