遺傳算法自學(xué)材料

遺傳算法自學(xué)材料遺傳算法(GeneticAlgorithm)進(jìn)化算法(EvolutionaryAlgorithm)第2頁,共72頁，2024年2月25日，星期天遺傳算法(GA)Darwin(1859)：“物竟天擇，適者生存”JohnHolland(universityofMichigan,1975)

《AdaptationinNaturalandArtificialSystem》遺傳算法作為一種有效的工具，已廣泛地應(yīng)用于最優(yōu)化問題求解之中。遺傳算法是一種基于自然群體遺傳進(jìn)化機(jī)制的自適應(yīng)全局優(yōu)化概率搜索算法。它摒棄了傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過程，采用人工的方式對目標(biāo)空間進(jìn)行隨機(jī)化搜索。第3頁,共72頁，2024年2月25日，星期天遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。遺傳算法的搜索機(jī)制第4頁,共72頁，2024年2月25日，星期天適者生存(SurvivaloftheFittest)GA主要采用的進(jìn)化規(guī)則是“適者生存”較好的解保留，較差的解淘汰遺傳算法(GA)第5頁,共72頁，2024年2月25日，星期天基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA）是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應(yīng)用價值。第6頁,共72頁，2024年2月25日，星期天SGA實例1：函數(shù)最值SGA參數(shù):編碼方式:二進(jìn)制碼

e.g.000000;01101

13;1111131種群規(guī)模:4隨機(jī)初始群體“轉(zhuǎn)盤賭”選擇一點雜交，二進(jìn)制變異求函數(shù)f(x)=x2的最大值，x為自然數(shù)且0≤x≤31。手工方式完成演示SGA過程第7頁,共72頁，2024年2月25日，星期天SGA實例1maxx2:選擇操作第8頁,共72頁，2024年2月25日，星期天SGA實例1maxx2:交叉操作第9頁,共72頁，2024年2月25日，星期天SGA實例1maxx2:變異操作第10頁,共72頁，2024年2月25日，星期天SGA實例2:連續(xù)函數(shù)最值求下列函數(shù)的最大值：第11頁,共72頁，2024年2月25日，星期天SGA實例2:編碼高精度

編碼[x,y]

{0,1}L

必須可逆(一個表現(xiàn)型對應(yīng)一個基因型)

解碼算子：

:{0,1}L

[x,y]

染色體長度L決定可行解的最大精度長染色體(慢進(jìn)化)

實數(shù)問題：變量z為實數(shù)，如何把{a1,…,aL}

{0,1}Lz∈[x,y]第12頁,共72頁，2024年2月25日，星期天SGA實例2:編碼設(shè)定求解精確到6位小數(shù)，因區(qū)間長度為2-(-1)=3，則需將區(qū)間分為3×106等份。因2097152＝221<3X106≤222＝4194304。故編碼的二進(jìn)制串長L=22。將一個二進(jìn)制串(b21b20…b0)轉(zhuǎn)化為10進(jìn)制數(shù)：e.g.<0000000000000000000000>-1;<1111111111111111111111>2<1110000000111111000101>1.6278881.627888=-1+3x(1110000000111111000101)2

/(222-1)=-1+3x3674053/(222-1)第13頁,共72頁，2024年2月25日，星期天SGA實例2:初始化種群、適應(yīng)函數(shù)隨機(jī)初始化種群適應(yīng)函數(shù)本實例目標(biāo)函數(shù)在定義域內(nèi)均大于0，且是求函數(shù)最大值，故直接引用目標(biāo)函數(shù)作為適應(yīng)函數(shù)：

f(s)=f(x)

其中二進(jìn)制串s對于變量x的值。

e.g.s1=<0000001110000000010000>x1=-0.958973

適應(yīng)值:f(s1)=f(x1)=1.078878

s2=<1110000000111111000101>x2=1.627888

適應(yīng)值:f(s2)=f(x2)=3.250650第14頁,共72頁，2024年2月25日，星期天SGA實例2:遺傳操作選擇操作(“輪盤賭”選擇)交叉操作(單點交叉)

交叉前(父):

s1=<00000|01110000000010000>s2=<11100|00000111111000101>

交叉后(子):

s’1=<00000|

00000111111000101>s’2=<11100|

01110000000010000>

適應(yīng)值:f(s’1)=f(-0.998113)=1.940865f(s’2)=f(1.666028)=3.459245

s’2的適應(yīng)值比其雙親個體的適應(yīng)值高。第15頁,共72頁，2024年2月25日，星期天SGA實例2:遺傳操作變異操作

變異前(父):

s2=<1110000000111111000101>

變異后(子):

s’2=<1110100000111111000101>

適應(yīng)值

f(s’2)=f(1.721638)=0.917743

比f(s2)小

變異前(父):

s2=<1110000000111111000101>

變異后(子):

s”2=<1110000001111111000101>

適應(yīng)值

f(s”2)=f(1.630818)=3.343555比f(s2)大變異操作有”擾動”作用，同時具有增加種群多樣性的效果。第16頁,共72頁，2024年2月25日，星期天SGA實例2：模擬結(jié)果遺傳算法的參數(shù):

種群規(guī)模:50

染色體長度:L=22

最大進(jìn)化代數(shù):150

交叉概率:Pc=0.25

變異概率:Pm=0.01

第17頁,共72頁，2024年2月25日，星期天SGA實例2:模擬結(jié)果(最佳個體進(jìn)化情況)世代數(shù)染色體編碼變量x適應(yīng)值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.850274第18頁,共72頁，2024年2月25日，星期天

遺傳算法簡介

智能優(yōu)化計算遺傳算法的基本思路

遺傳算法的思路與特點

第19頁,共72頁，2024年2月25日，星期天

遺傳算法簡介

智能優(yōu)化計算自組織、自適應(yīng)和自學(xué)習(xí)性在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。

遺傳算法的思路與特點

概率轉(zhuǎn)換規(guī)則強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則不需求導(dǎo)只需目標(biāo)函數(shù)和適應(yīng)度函數(shù)本質(zhì)并行性內(nèi)在并行性與內(nèi)含并行性第20頁,共72頁，2024年2月25日，星期天生物進(jìn)化與遺傳算法對應(yīng)關(guān)系生物進(jìn)化遺傳算法適者生存適應(yīng)函數(shù)值最大的解被保留的概率最大個體問題的一個解染色體解的編碼基因編碼的元素群體被選定的一組解種群根據(jù)適應(yīng)函數(shù)選擇的一組解交叉以一定的方式由雙親產(chǎn)生后代的過程變異編碼的某些分量發(fā)生變化的過程生存能力適應(yīng)函數(shù)第21頁,共72頁，2024年2月25日，星期天遺傳算法的基本操作選擇(selection):

根據(jù)各個個體的適應(yīng)值，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中。交叉(crossover):

將群體P(t)內(nèi)的各個個體隨機(jī)搭配成對，對每一個個體，以某個概率Pc(稱為交叉概率，crossvoerrate)交換它們之間的部分染色體。變異(mutation):

對群體P(t)中的每一個個體，以某一概率Pm(稱為變異概率，mutationrate)改變某一個或一些基因座上基因值為其它的等位基因。第22頁,共72頁，2024年2月25日，星期天如何設(shè)計遺傳算法如何進(jìn)行編碼？如何產(chǎn)生初始種群？如何定義適應(yīng)函數(shù)？如何進(jìn)行遺傳操作(復(fù)制、交叉、變異)？如何產(chǎn)生下一代種群？如何定義停止準(zhǔn)則？第23頁,共72頁，2024年2月25日，星期天編碼(Coding)表現(xiàn)型空間編碼(Coding)解碼(Decoding)基因型空間={0,1}L0111010010100010011001001010010001第24頁,共72頁，2024年2月25日，星期天選擇(Selection)選擇(復(fù)制)操作把當(dāng)前種群的染色體按與適應(yīng)值成正比例的概率復(fù)制到新的種群中

主要思想:適應(yīng)值較高的染色體體有較大的選擇機(jī)會實現(xiàn)1：“輪盤賭”選擇(Roulettewheelselection)將種群中所有染色體編號，并根據(jù)各自適應(yīng)值計算按比例分配的概率依次計算染色體累加概率產(chǎn)生(0,1)之間隨機(jī)數(shù)，若其最多能大于序列中第m個值，則第m個染色體被隨機(jī)選擇第25頁,共72頁，2024年2月25日，星期天選擇(Selection)設(shè)種群的規(guī)模為Nxi是i為種群中第i個染色體AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=2染色體xi被選概率第26頁,共72頁，2024年2月25日，星期天選擇(Selection)染色體的適應(yīng)值和所占的比例輪盤賭選擇第27頁,共72頁，2024年2月25日，星期天選擇(Selection)隨機(jī)數(shù)23491338627所選號碼262514所選染色體110000001111000011000111010010染色體編號123456染色體011101100000100100100110000011適應(yīng)度81525128被選概率0.160.30.040.10.240.16累加概率8

23253042

50染色體被選的概率被選的染色體第28頁,共72頁，2024年2月25日，星期天選擇(Selection)輪盤上的片分配給群體的染色體，使得每一個片的大小與對于染色體的適應(yīng)值成比例從群體中選擇一個染色體可視為旋轉(zhuǎn)一個輪盤，當(dāng)輪盤停止時，指針?biāo)傅钠瑢τ诘娜旧w就時要選的染色體。模擬“輪盤賭”算法：r=random(0,1)，s=0，i=0；如果s≥r，則轉(zhuǎn)(4)；s=s+p(xi)，i=i+1,轉(zhuǎn)(2)xi即為被選中的染色體，輸出I結(jié)束第29頁,共72頁，2024年2月25日，星期天選擇(Selection)其他選擇法：隨機(jī)遍歷抽樣(Stochasticuniversalsampling)局部選擇(Localselection)截斷選擇(Truncationselection)競標(biāo)賽選擇(Tournamentselection)特點：選擇操作得到的新的群體稱為交配池，交配池是當(dāng)前代和下一代之間的中間群體，其規(guī)模為初始群體規(guī)模。選擇操作的作用效果是提高了群體的平均適應(yīng)值(低適應(yīng)值個體趨于淘汰，高適應(yīng)值個體趨于選擇)，但這也損失了群體的多樣性。選擇操作沒有產(chǎn)生新的個體，群體中最好個體的適應(yīng)值不會改變。第30頁,共72頁，2024年2月25日，星期天交叉(crossover,Recombination)遺傳交叉(雜交、交配、有性重組)操作發(fā)生在兩個染色體之間，由兩個被稱之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個具有雙親的部分基因的新的染色體，從而檢測搜索空間中新的點。選擇(復(fù)制)操作每次作用在一個染色體上，而交叉操作每次作用在從交配池中隨機(jī)選取的兩個個體上(交叉概率Pc)。交叉產(chǎn)生兩個子染色體，他們與其父代不同，且彼此不同,每個子染色體都帶有雙親染色體的遺傳基因。第31頁,共72頁，2024年2月25日，星期天單點交叉(1-pointcrossover)在雙親的父代染色體中隨機(jī)產(chǎn)生一個交叉點位置在交叉點位置分離雙親染色體互換交叉點位置右邊的基因碼產(chǎn)生兩個子代染色體交叉概率Pc一般范圍為(60%,90%)，平均約80%11111111父代1111000000000000子代111100000000000011111111交叉點位置第32頁,共72頁，2024年2月25日，星期天交叉(crossover,Recombination)單點交叉操作可以產(chǎn)生與父代染色體完全不同的子代染色體；它不會改變父代染色體中相同的基因。但當(dāng)雙親染色體相同時，交叉操作是不起作用的。假如交叉概率Pc＝50%,則交配池中50%的染色體(一半染色體)將進(jìn)行交叉操作，余下的50%的染色體進(jìn)行選擇(復(fù)制)操作。GA利用選擇和交叉操作可以產(chǎn)生具有更高平均適應(yīng)值和更好染色體的群體第33頁,共72頁，2024年2月25日，星期天變異(Mutation)以變異概率Pm改變?nèi)旧w的某一個基因,當(dāng)以二進(jìn)制編碼時，變異的基因由0變成1，或者由1變成0。變異概率Pm一般介于1/種群規(guī)模與1/染色體長度之間，平均約1-2%11010100父代01010101子代變異基因變異基因第34頁,共72頁，2024年2月25日，星期天變異(Mutation)比起選擇和交叉操作，變異操作是GA中的次要操作，但它在恢復(fù)群體中失去的多樣性方面具有潛在的作用。

在GA執(zhí)行的開始階段，染色體中一個特定位上的值1可能與好的性能緊密聯(lián)系，即搜索空間中某些初始染色體在那個位上的值1可能一致產(chǎn)生高的適應(yīng)值。因為越高的適應(yīng)值與染色體中那個位上的值1相聯(lián)系，選擇操作就越會使群體的遺傳多樣性損失。等到達(dá)一定程度時，值0會從整個群體中那個位上消失，然而全局最優(yōu)解可能在染色體中那個位上為0。如果搜索范圍縮小到實際包含全局最優(yōu)解的那部分搜索空間，在那個位上的值0就可能正好是到達(dá)全局最優(yōu)解所需要的。第35頁,共72頁，2024年2月25日，星期天適應(yīng)函數(shù)(FitnessFunction)GA在搜索中不依靠外部信息，僅以適應(yīng)函數(shù)為依據(jù)，利用群體中每個染色體(個體)的適應(yīng)值來進(jìn)行搜索。以染色體適應(yīng)值的大小來確定該染色體被遺傳到下一代群體中的概率。染色體適應(yīng)值越大，該染色體被遺傳到下一代的概率也越大；反之，染色體的適應(yīng)值越小，該染色體被遺傳到下一代的概率也越小。因此適應(yīng)函數(shù)的選取至關(guān)重要，直接影響到GA的收斂速度以及能否找到最優(yōu)解。群體中的每個染色體都需要計算適應(yīng)值適應(yīng)函數(shù)一般由目標(biāo)函數(shù)變換而成第36頁,共72頁，2024年2月25日，星期天適應(yīng)函數(shù)(FitnessFunction)適應(yīng)函數(shù)常見形式：直接將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)函數(shù)若目標(biāo)函數(shù)為最大化問題：

Fitness(f(x))=f(x)若目標(biāo)函數(shù)為最小化問題：

Fitness(f(x))=-f(x)缺點:(1)可能不滿足輪盤賭選擇中概率非負(fù)的要求

(2)某些代求解的函數(shù)值分布上相差很大，由此得到的評價適應(yīng)值可能不利于體現(xiàn)群體的評價性能，影響算法的性能。第37頁,共72頁，2024年2月25日，星期天適應(yīng)函數(shù)(FitnessFunction)界限構(gòu)造法

目標(biāo)函數(shù)為最大化問題其中Cmin為f(x)的最小估計值

目標(biāo)函數(shù)為最小化問題其中Cmaxn為f(x)的最大估計值第38頁,共72頁，2024年2月25日，星期天停止準(zhǔn)則(TerminationCriteria)種群中個體的最大適應(yīng)值超過預(yù)設(shè)定值種群中個體的平均適應(yīng)值超過預(yù)設(shè)定值種群中個體的進(jìn)化代數(shù)超過預(yù)設(shè)定值第39頁,共72頁，2024年2月25日，星期天基本步驟(StepbyStep)(1)隨機(jī)產(chǎn)生初始種群;(2)計算種群體中每個個體的適應(yīng)度值,判斷是否滿足停止條件，若不滿足，則轉(zhuǎn)第(3)步,否則轉(zhuǎn)第(6)步;(3)按由個體適應(yīng)值所決定的某個規(guī)則選擇進(jìn)入下一代的個體;(4)按交叉概率Pc進(jìn)行交叉操作,生產(chǎn)新的個體;(5)按變異概率Pm進(jìn)行變異操作,生產(chǎn)新的個體;(6)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。第40頁,共72頁，2024年2月25日，星期天流程圖(FlowChart)第41頁,共72頁，2024年2月25日，星期天SGA偽碼描述ProcedureGeneticAlgorithm

begint=0;初始化P(t);計算P(t)的適應(yīng)值;while(不滿足停止準(zhǔn)則)dobegint=t+1;

從P(t-1)中選擇P(t);%selection

重組P(t);%crossoverandmutation

計算P(t)的適應(yīng)值;end

end第42頁,共72頁，2024年2月25日，星期天無約束最優(yōu)化問題GA編碼：X=(x1,x2,…,xn)的各個變量可以按二進(jìn)制編碼方法分別編碼。對于變量xi的上、下限約束li≤xi≤

ui(i=1,2,…,n)，依據(jù)解的精度要求(有效位數(shù))求得各個變量X=(x1,x2,…,xn)的二進(jìn)制碼位數(shù)(m1,m2,…,mn)(確定方法類似于SGA實例2)，因此將n個二進(jìn)制位串順序連接起來，構(gòu)成一個個體的染色體編碼，編碼的總位數(shù)m＝m1+m2+…+mn。無約束最優(yōu)化問題:第43頁,共72頁，2024年2月25日，星期天無約束最優(yōu)化問題GA解碼：解碼時仍按各個變量的編碼順序分別實現(xiàn)常規(guī)的二進(jìn)制編碼解碼方法。二進(jìn)制遺傳編碼示意圖如下：第44頁,共72頁，2024年2月25日，星期天約束最優(yōu)化問題常規(guī)解法：(1)把約束問題轉(zhuǎn)化為無約束問題，在用無約束問題方法求解，如罰函數(shù)法(2)改進(jìn)無約束問題的方法，再用于約束問題，如梯度投影法、廣義簡約梯度法約束最優(yōu)化問題:第45頁,共72頁，2024年2月25日，星期天約束最優(yōu)化問題遺傳算法求解關(guān)鍵:約束條件的處理等式約束可以包含到適應(yīng)函數(shù)，僅考慮不等式約束。假設(shè)按無約束問題那樣求解，在搜索過程中計算目標(biāo)函數(shù)值，并檢查是否有約束違反。如果沒有違反，則表明是可行解，就根據(jù)目標(biāo)函數(shù)指定一適應(yīng)值；否則，就是不可行解，因而沒有適應(yīng)值(適應(yīng)值為0)。這樣的處理實際不可行，因為找到一個可行解幾乎與找到最優(yōu)解一樣困難。第46頁,共72頁，2024年2月25日，星期天一般解法：通過引入罰函數(shù)，從不可行解中得到一些信息。將罰函數(shù)包含到適應(yīng)函數(shù)中。關(guān)鍵是如何設(shè)計罰函數(shù)；不同問題需要設(shè)計不同的罰函數(shù)；對一般的約束處理，通常很困難。約束最優(yōu)化問題第47頁,共72頁，2024年2月25日，星期天組合最優(yōu)化問題典型問題：旅行商問題(TravelingSalesmanProblem)作業(yè)調(diào)度問題(JobShopSchedulingProblem)背包問題(KnapsackProblem)圖著色問題………很多組合最優(yōu)化問題是NP難問題或NP完全問題第48頁,共72頁，2024年2月25日，星期天旅行商問題(TSP)TSP，也稱貨郎擔(dān)問題，是一個NP完全問題。TSP描述：圖論:設(shè)圖G=(V,E),其中V是頂點集，E是邊集。設(shè)C=(cij)是與E相聯(lián)系的距離矩陣。尋找一條通過所有頂點且每個頂點只通過一次的最短距離回路(Hamilton回路)。實際應(yīng)用中，C也可解釋為費用或旅行時間矩陣。實際:一位推銷員從自己所在城市出發(fā)，必須遍訪所有城市之后又回到原來的城市，求使其旅行費用最少的路徑。第49頁,共72頁，2024年2月25日，星期天巡回旅行商問題(TSP)中國貨郎擔(dān)問題:城市數(shù):40城市編號1,2,…,40尋找一條最短路徑第50頁,共72頁，2024年2月25日，星期天TSP復(fù)雜性搜索空間龐大TSP涉及求多個變量的函數(shù)的最小值，求解很困難。其可能的路徑條數(shù)隨著城市數(shù)目n成指數(shù)增長，如，5個城市對應(yīng)12條路徑；10個城市對應(yīng)181440條路徑；100個城市對應(yīng)4.6663X10155條路徑。如此龐大的搜索空間，常規(guī)解法和計算工具都遇到計算上的困難。只能尋找近似解法，如神經(jīng)網(wǎng)絡(luò)方法、模擬退火法、遺傳算法等。第51頁,共72頁，2024年2月25日，星期天TSP編碼:路徑表示染色體表示成所有城市的一個排列，若有n個城市，一條可能路徑編碼為長度為n的整數(shù)向量(i1,i2,…,in),其中ik表示第ik個城市。例如:路徑編碼向量(517894623)直接表示一條旅行路程(5->1->7->8->9->4->6->2->3)。此向量是1到n的一個排列，即從1到n的每個整數(shù)在這個向量中正好出現(xiàn)一次,不能有重復(fù)。這樣，基本遺傳算法的基因操作生成的個體不能滿足這一約束條件，需尋求其他遺傳操作。第52頁,共72頁，2024年2月25日，星期天TSP交叉需其他方式的交叉(重組)操作,如部分匹配交叉(PartiallyMatchedCrossover,PMX)、順序交叉(OrderedCrossover,OX)、循環(huán)交叉(CycleCrossover,CX)、邊重組(EdgeRecombination)。12345543211232154345一般的交叉操作會產(chǎn)生不合適的解，如第53頁,共72頁，2024年2月25日，星期天TSP交叉1:部分匹配交叉(PMX)雙親P1,P2隨機(jī)選取兩個交叉點，得到一個匹配段,根據(jù)交叉點中間段給出映射關(guān)系。123456789937826514xxx4567xxxxx8265xxP1P2映射關(guān)系：48、52、75c1c2

交換兩個交叉點之間的編碼,(X表示未定碼)第54頁,共72頁，2024年2月25日，星期天TSP交叉1:部分匹配交叉(PMX)子個體C1，C2分別從其父個體中繼承未映射城市碼12345678993782651493x45671x1x38265x9P1P2c1c2映射關(guān)系：48、52、75932456718173826549c1c2

再根據(jù)映射關(guān)系，對以上未定碼，使用最初雙親碼，得到子個體的對應(yīng)碼。映射關(guān)系存在傳遞關(guān)系，則選擇未定碼交換。第55頁,共72頁，2024年2月25日，星期天TSP交叉2:順序交叉(OX)雙親P1,P2隨機(jī)選取兩個交叉點123456789937826514P1P2xxx4567xxxxx8265xxc1c2

兩個交叉點間的中間段保存不變

子個體C1的未定碼的確定需要父個體P2的未選定城市碼，子個體C2的未定碼的確定需要父個體P1的未選定城市碼。第56頁,共72頁，2024年2月25日，星期天TSP交叉2:順序交叉(OX)記取父個體P2從第二個交叉點開始城市碼的排列順序，當(dāng)?shù)竭_(dá)表尾時，返回表頭繼續(xù)記錄，直到第二個交叉點。937826514P2xxx4567xxc1382456719c1347826591c2

得到父個體P2的排列順序1-4-9-3-7-8-2-6-5,并將C1已有城市碼4,5,6,7從中去掉，得到排列順序1-9-3-8-2，再將此順序復(fù)制到C1，復(fù)制點也是從第二個交叉點開始，得到C1。同理的C2，第57頁,共72頁，2024年2月25日，星期天TSP交叉3:循環(huán)交叉(CX)CX操作中子個體中的城市碼順序根據(jù)任一父個體產(chǎn)生確定循環(huán)編碼

復(fù)制循環(huán)編碼到子個體第58頁,共72頁，2024年2月25日，星期天TSP變異InsertMutation隨機(jī)選取個體中兩個編碼，然后把第二個編碼放在第一個編碼之后，其他編碼順次調(diào)節(jié)位置。

Swapmutation隨機(jī)選取個體中兩個編碼，然后交換它們的位置。第59頁,共72頁，2024年2月25日，星期天TSP變異Inversionmutation隨機(jī)選取個體中一段編碼，然后顛倒這段編碼的順序。

Scramblemutation隨機(jī)選取個體上一段編碼,然后打亂這段編碼的順序。選取的編碼不一定是鄰接編碼第60頁,共72頁，2024年2月25日，星期天TSP的GA過程從N個隨機(jī)起點開始產(chǎn)生N條路徑，N為種群的規(guī)模;利用最優(yōu)方法搜索每條路徑的局部最優(yōu)解;選擇交叉對使在平均性能之上的個體得到更多的子代;交叉和變異;搜索每條路徑得到其極小解，如果不收斂，則回到第3步；否則，停止。第61頁,共72頁，2024年2月25日，星期天GA的MATLAB實現(xiàn)軟件平臺(SoftwarePlatforms):MATLAB7.xGeneticAlgorithmandDirectSearchToolbox

2.0.1

MATLAB6.x(or7.x)+GAOTGAOT:GeneticAlgorithmOptimizationToolbox美國NorthCarolinaStateUniversity開發(fā)MATLAB6.x(or7.x)+GEATbxGEATbx:GeneticandEvolutionaryAlgorithmToolbox英國TheUniversityofSheffield開發(fā)《MATLAB遺傳算法工具箱及應(yīng)用》(雷英杰等,西安電子科技大學(xué)出版社,2005)基于此工具箱

第62頁,共72頁，2024年2月25日，星期天GAOT工具箱核心函數(shù)：[pop]=initializega(num,bounds,eevalFN,eevalOps,options)------初始種群的生成函數(shù)【輸出參數(shù)】pop-----生成的初始種群【輸入?yún)?shù)】num-----種群中的個體數(shù)目

bounds-----代表變量的上下界的矩陣

eevalFN-----適應(yīng)度函數(shù)

eevalOps-----傳遞給適應(yīng)度函數(shù)的參數(shù)

options-----選擇編碼形式(浮點編碼或是二進(jìn)制編碼)與精度，如[typeprec]，type-----為1時選擇浮點編碼，否則為二進(jìn)制編碼prec-----變量進(jìn)行二進(jìn)制編碼時指定的精度，默認(rèn)[1e-61]第63頁,共72頁，2024年2月25日，星期天GAOT工具箱(2)[x,endPop,bPop,traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,termFN,termOps,selectFN,…selectOps,xOverFNs,xOverOps,mutFNs,mutOps)

---