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

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

（“天”——適應(yīng)度函數(shù)，F(xiàn)itnessFunction)第四頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述1.2遺傳算法的特點(diǎn)四大優(yōu)點(diǎn)：良好的并行性（操作對(duì)象是一組可行解；搜索軌道有多條）強(qiáng)大的通用性（只需利用目標(biāo)的取值信息，無需梯度等高價(jià)值信息）良好的全局優(yōu)化性和魯棒性良好的可操作性兩個(gè)缺點(diǎn)：未成熟收斂問題收斂速度較慢，算法實(shí)時(shí)性欠佳第五頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述1.3遺傳算法的發(fā)展歷史年份貢獻(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類似遺傳算法的概率算法理論1975DeJong用于5個(gè)測(cè)試函數(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ā)知識(shí)維持遺傳多樣性1985Baker試驗(yàn)基于排序的選擇方法1985Booker建議采用部分分配計(jì)分、分享操作和交配限制法1985Goldberg,LingleTSP問題中采用部分匹配交叉1985Grefenstette,Fitzpattrick對(duì)含噪聲的函數(shù)進(jìn)行測(cè)試1985Schaffer多種群遺傳算法解決多目標(biāo)優(yōu)化問題續(xù)表1.1第七頁，共九十七頁，編輯于2023年，星期六1遺傳算法概述年份貢獻(xiàn)者內(nèi)容1986Goldberg最優(yōu)種群大小估計(jì)1986Grefenstette元級(jí)遺傳算法控制的遺傳算法1987Baker選擇中隨機(jī)誤差的較少方法1987Goldberg復(fù)制和交叉時(shí)最小欺騙問題（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ù)表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）自動(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)化問題）（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)濟(jì)領(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）對(duì)環(huán)境的適應(yīng)性“種瓜得瓜，種豆得豆”第十一頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.1遺傳算法的生物學(xué)基礎(chǔ)個(gè)體（Individual）種群（Population）適應(yīng)度（Fitness）進(jìn)化（Evolution）生存（Survival）LowHigh“物競(jìng)天擇，適者生存”死亡

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

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

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

2.3

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

2.3

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

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

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

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

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

遺傳算法的應(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]分成至少500000個(gè)等長(zhǎng)小區(qū)域，而每個(gè)小區(qū)域用一個(gè)二進(jìn)制串表示。于是有，2L=500000，即向上取整，可得到L=19。即可用19位二進(jìn)制串a(chǎn)18a17…a0來表示。例如：對(duì)于二進(jìn)制編碼，其解碼過程如下：若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ù)值。第十九頁，共九十七頁，編輯于2023年，星期六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ù)常用一下三種：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)：簡(jiǎn)單直觀；

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

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

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

一般地，當(dāng)隨機(jī)產(chǎn)生的概率大于交叉率，遺傳算法就會(huì)按一定規(guī)則選擇兩個(gè)個(gè)體，執(zhí)行交叉操作。交叉率的選擇決定了交叉的頻率，較大的交叉率使各代充分交叉，但群體中的優(yōu)良模式遭到破壞的可能性增大，以致產(chǎn)生較大的代溝，從而使搜索走向隨機(jī)化；交叉率越低，產(chǎn)生的代溝越小，就會(huì)使得更多的個(gè)體直接復(fù)制到下一代，遺傳搜索可能陷入停滯狀態(tài)，一般建議取值范圍0.4~0.9。對(duì)于二進(jìn)制編碼，常用的交叉方法有：?jiǎn)吸c(diǎn)交叉、多點(diǎn)交叉和均勻交叉等。一個(gè)單點(diǎn)交叉的例子如下圖所示。第二十四頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法③變異率及變異操作變異本身是一種局部隨機(jī)搜索，使遺傳算法具有局部的隨機(jī)搜索能力；同時(shí)使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。一般地，隨機(jī)產(chǎn)生的概率大于變異率就會(huì)觸發(fā)變異操作。變異率一般可取0.001~0.1。變異率不能取得太大，如果大于0.5，遺傳算法就退化為隨機(jī)搜索，而遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力也不復(fù)存在了。常用的變異操作方法有：實(shí)值變異法和二進(jìn)制變異法等。實(shí)值變異法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)運(yùn)行參數(shù)，包括群體規(guī)模(PopulationSize)、迭代次數(shù)（一般取為100~500）、選擇算子、交叉率、變異率等等。（8）初始化群體。初始群體一般隨機(jī)產(chǎn)生初始值最好能在解空間中均勻采樣（收斂速度比較快）對(duì)于非二進(jìn)制編碼，還要考慮所生成的染色體是否在可行區(qū)域內(nèi)。（9）計(jì)算群體中個(gè)體解碼后的適應(yīng)值。（10）按照遺傳策略，運(yùn)用所選定的選擇、交叉和變異算子作用于群體，生成下一代群體。（11）判斷群體性能是否滿足某一指標(biāo)或是否完成預(yù)定迭代次數(shù)，不滿足則返回（9）。popsize取值較小時(shí)提高運(yùn)算和收斂速度卻降低了群體多樣性，可能引起早熟現(xiàn)象取值較大時(shí)含有較多模式，可提高GA搜索質(zhì)量但計(jì)算量增大，收斂速度降低一般取為20~100第二十六頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法2.6

欺騙問題和未成熟收斂問題2.6.1欺騙問題（DeceptiveProblem）競(jìng)爭(zhēng)模式：若模式H與H’中，*的位置完全一致，但任一確定位的編碼均不一樣，則稱H與H’互為競(jìng)爭(zhēng)模式。欺騙性：假設(shè)f(X)的最大值對(duì)應(yīng)的X集合為X*，H為一包含X*的m階模式。H的競(jìng)爭(zhēng)模式為H’，而且f(H)>f(H’)，則f為m階欺騙。欺騙問題：在遺傳算法中，將所有妨礙評(píng)價(jià)值高的個(gè)體生成從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題。如對(duì)于一個(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ù)等方法來化解。第二十七頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法（1）未成熟收斂現(xiàn)象未成熟收斂現(xiàn)象是遺傳算法中的特有現(xiàn)象，且十分常見。它是指，當(dāng)遺傳算法還沒找到全局最優(yōu)解或滿意解時(shí)，群體中不能再產(chǎn)生性能超過父代的后代，群體中的各個(gè)個(gè)體非常相似。未成熟收斂的重要特征是群體中個(gè)體結(jié)構(gòu)的多樣性急劇減少。2.6.2未成熟收斂問題（PrematureConvergence）（2）未成熟收斂產(chǎn)生的原因①理論上考慮的選擇、交叉、變異操作都是絕對(duì)精確的，他們相互協(xié)調(diào)，能搜索到整個(gè)解空間，但實(shí)際不然；②存在隨機(jī)誤差（主要包括取樣誤差和選擇誤差）；③所求解的問題是遺傳算法欺騙問題。（3）未成熟收斂的防止重新啟動(dòng)法替代策略（ReplacementStrategies）重組策略（RecombinationStrategies）匹配策略（MatingStrategies）提高多樣性第二十八頁，共九十七頁，編輯于2023年，星期六遺傳算法具體步驟選擇編碼策略，把參數(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)遺傳算法第二十九頁，共九十七頁，編輯于2023年，星期六2標(biāo)準(zhǔn)遺傳算法程序流程圖開始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(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=pc·M?

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

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

y=x2

31

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

分析

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

(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ù)極值第三十三頁，共九十七頁，編輯于2023年，星期六(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對(duì)其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。

首先計(jì)算種群S1中各個(gè)體

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

由此可求得

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

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

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

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

3、遺傳算法簡(jiǎn)單舉例：函數(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、遺傳算法簡(jiǎn)單舉例：函數(shù)極值第三十九頁，共九十七頁，編輯于2023年，星期六

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

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

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

染色體適應(yīng)度選擇概率估計(jì)的選中次數(shù)s1=111007840.442s2=01001810.040s3=110005760.321s4=100113610.2013、遺傳算法簡(jiǎn)單舉例：函數(shù)極值第四十二頁，共九十七頁，編輯于2023年，星期六設(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）,s4’’=10000（16）

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

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

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

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

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

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

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

得到的最佳個(gè)體：

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

｜3456｜

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

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

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

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

|390148pop=zeros(s,t);fori=1:spop(i,1:t-1)=randperm(t-1);end第六十二頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計(jì)算仿真結(jié)果990.0829路徑長(zhǎng)度：遷移代數(shù)：50第六十三頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計(jì)算仿真結(jié)果701.7754路徑長(zhǎng)度：遷移代數(shù)：100第六十四頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計(jì)算仿真結(jié)果624.1821路徑長(zhǎng)度：遷移代數(shù)：150第六十五頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計(jì)算仿真結(jié)果523.2674路徑長(zhǎng)度：遷移代數(shù)：200第六十六頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計(jì)算仿真結(jié)果491.4063路徑長(zhǎng)度：遷移代數(shù)：250第六十七頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計(jì)算仿真結(jié)果453.1959路徑長(zhǎng)度：遷移代數(shù)：300第六十八頁，共九十七頁，編輯于2023年，星期六4遺傳算法求解巡回旅行商問題4.3計(jì)算仿真結(jié)果430.3986路徑長(zhǎng)度：遷移代數(shù)：350第六十九頁，共九十七頁，編輯于2023年，星期六4.3計(jì)算仿真結(jié)果424.8693路徑長(zhǎng)度：遷移代數(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)于遺傳算法操作算子的驗(yàn)證4遺傳算法求解巡回旅行商問題“實(shí)驗(yàn)數(shù)據(jù)”課程所做的正交試驗(yàn)極差分析結(jié)果（遷移500代后退出的結(jié)果）。第七十三頁，共九十七頁，編輯于2023年，星期六對(duì)于上表，有（驗(yàn)證）以下基本結(jié)論：（1）遺傳算法搜索求解能力與四個(gè)因素有關(guān)：群體規(guī)模、選擇算子、交叉率和變異率。（2）從主到次依次為：交叉率——群體規(guī)模——選擇算子——變異率。（3）A3-B2-C1-D3是優(yōu)選方案。4遺傳算法求解巡回旅行商問題第七十四頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次遷移1000代，有36次能收斂到全局最優(yōu)解）是比較優(yōu)的參數(shù)組合。實(shí)際上可看出，迭代進(jìn)行到450代之后，所得到得最優(yōu)個(gè)體基本不再發(fā)生變化，且其最優(yōu)路徑與真實(shí)的最有路徑差距非常小。4遺傳算法求解巡回旅行商問題第七十五頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次遷移1000代，有24次能收斂到全局最優(yōu)解）表明：選擇算子取值太大，收斂速度很快，但陷入局部最優(yōu)解的可能性大大提高，而基本上不可能再跳出來。約350代便收斂4遺傳算法求解巡回旅行商問題第七十六頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次迭代1000代，僅有6次能收斂到全局最優(yōu)解）表明：交叉率選取太大，導(dǎo)致群體中的優(yōu)良模式遭到破壞，產(chǎn)生較大的代溝，從而使搜索走向隨機(jī)化。450Km左右4遺傳算法求解巡回旅行商問題第七十七頁，共九十七頁，編輯于2023年，星期六左圖（進(jìn)行50次獨(dú)立運(yùn)算求解，每次遷移1000代，有18次能收斂到全局最優(yōu)解）表明：變異率選取太大，遺傳算法幾乎退化為隨機(jī)搜索，陷入局部最優(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í)數(shù)編碼)1、GA優(yōu)化NN的權(quán)重第八十頁，共九十七頁，編輯于2023年，星期六2023年5月31日81定義適應(yīng)度直接采用方差和.評(píng)估過程：對(duì)每個(gè)解進(jìn)行樣本測(cè)試（前向計(jì)算），計(jì)算其實(shí)際輸出和期望輸出的誤差（適應(yīng)度）。如果有一個(gè)個(gè)體的適應(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)重遺傳操作：變異第