第7章：遺傳算法2課件

確定問題的編碼方案確定適配值函數(shù)遺傳算子的設(shè)計算法參數(shù)的選取算法終止準則從算法流程看，GA算法按照以下步驟進行算法關(guān)鍵參數(shù)與操作的設(shè)計一、編碼目的：將問題的解用一種碼表示，將問題的狀態(tài)空間與GA的碼空間相對應(yīng)。碼長碼制1、問題空間與GA空間遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的、由基因按一定結(jié)構(gòu)組成的染色體或個體。這一轉(zhuǎn)換過程實際上是將問題空間轉(zhuǎn)換為GA空間，它們的對應(yīng)關(guān)系如下圖表示。圖GA空間與問題空間的對應(yīng)關(guān)系P2P1CP1P2C交叉GA空間問題空間編碼譯碼2、編碼評估規(guī)范評估編碼策略常采用以下3個規(guī)范：完備性（Completeness）：問題空間中的所有點（后選解）都能作為GA空間中的點（染色體）表現(xiàn)。問題空間的所有解都能表示為所設(shè)計的基因型。健全性（Soundness）：GA空間中的染色體能對應(yīng)所有問題空間中的解。任何一個基因型都對應(yīng)于一個可能解。非冗余性（Non-redundancy）：染色體和后選解一一對應(yīng)。問題空間和表達空間一一對應(yīng)。3、編碼技術(shù)遺傳算法用到的一般編碼技術(shù)有：一維染色體編碼多參數(shù)映射編碼可變?nèi)旧w長度編碼二維染色體編碼樹結(jié)構(gòu)編碼多種編碼方式二進制編碼；浮點數(shù)編碼；格雷碼編碼；符號編碼；復(fù)數(shù)編碼；DNA編碼等。二進制編碼與浮點數(shù)編碼的比較在交叉操作時，二進制編碼比浮點數(shù)編碼產(chǎn)生新個體的可能性多；在變異操作時，二進制編碼的種群穩(wěn)定性比浮點數(shù)編碼差。二、群體設(shè)定1、初始群體的設(shè)定

一般來講，初始群體的設(shè)定可采取如下的策略：根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這個過程不斷迭代，直到初始群體中個體個數(shù)達到要求。一般情況下，遺傳算法在群體初始化階段采用的是隨機數(shù)初始化方法。采用生成隨機數(shù)的方法，對染色體的每一維變量進行初始化賦值。初始化染色體時必須注意染色體是否滿足優(yōu)化問題對有效解的定義。如果在進化開始時保證初始群體已經(jīng)是一定程度上的優(yōu)良群體的話，將能夠有效提高算法找到全局最優(yōu)解的能力。2、群體多樣性根據(jù)模式定理，在二進制編碼的前提下，為了滿足GA的隱并行性，群體個體數(shù)只要設(shè)定為即可，其中為染色體長度。或稱適應(yīng)度函數(shù)。目的：對個體進行評價，是優(yōu)化過程的依據(jù)。三、適配值函數(shù)1、目標函數(shù)映射成適應(yīng)度函數(shù)2、適應(yīng)度函數(shù)的設(shè)計對GA的影響評估函數(shù)用于評估各個染色體的適應(yīng)值，進而區(qū)分優(yōu)劣。影響算法對種群的選擇，恰當?shù)脑u估函數(shù)應(yīng)該能夠?qū)θ旧w的優(yōu)劣做出合適的區(qū)分，保證選擇機制的有效性，從而提高群體的進化能力。評估函數(shù)的設(shè)置同優(yōu)化問題的求解目標有關(guān)。比如在求解函數(shù)優(yōu)化問題時，問題定義的目標函數(shù)可以作為評估函數(shù)的原型。評估函數(shù)應(yīng)滿足較優(yōu)染色體的適應(yīng)值較大的規(guī)定。因此對于一些求解最大值的數(shù)值優(yōu)化問題，我們可以直接套用問題定義的函數(shù)表達式。為了更好地提高選擇的效能，可以對評估函數(shù)做出一定的修正。目前主要的評估函數(shù)修正方法有：線性變換；乘冪變換；指數(shù)變換等。適應(yīng)度函數(shù)的重要性

適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標函數(shù)變換而成的，對目標函數(shù)值域的某種映射變換稱為適應(yīng)度的尺度變換（fitnessscaling）。幾種常見的適應(yīng)度函數(shù)直接轉(zhuǎn)換若目標函數(shù)為最大化問題：Fit(f(x))=f(x)

若目標函數(shù)為最小化問題：Fit(f(x))=-f(x)幾種常見的適應(yīng)度函數(shù)界限構(gòu)造法1

若目標函數(shù)為最大化問題：若目標函數(shù)為最小化問題：適應(yīng)度函數(shù)的作用

適應(yīng)度函數(shù)設(shè)計不當有可能出現(xiàn)欺騙問題：（1）進化初期，個別超常個體控制選擇過程；（2）進化末期，個體差異太小導(dǎo)致陷入局部極值。適應(yīng)度函數(shù)的設(shè)計單值、連續(xù)、非負、最大化合理、一致性計算量小通用性強理論上還沒有完全解決，影響算法的性能！種群數(shù)目交叉概率變異概率四、算法參數(shù)群體規(guī)模N

染色體長度L

影響算法的搜索能力和運行效率。若N設(shè)置較大，一次進化所覆蓋的模式較多，可以保證群體的多樣性，從而提高算法的搜索能力，但是由于群體中染色體的個數(shù)較多，勢必增加算法的計算量，降低了算法的運行效率。若N設(shè)置較小，雖然降低了計算量，但是同時降低了每次進化中群體包含更多較好染色體的能力。N的設(shè)置一般為20~100。影響算法的計算量和交配變異操作的效果。L的設(shè)置跟優(yōu)化問題密切相關(guān)，一般由問題定義的解的形式和選擇的編碼方法決定。對于二進制編碼方法，染色體的長度L根據(jù)解的取值范圍和規(guī)定精度要求選擇大小。對于浮點數(shù)編碼方法，染色體的長度L

跟問題定義的解的維數(shù)D相同。除了染色體長度一定的編碼方法，Goldberg等人還提出了一種變長度染色體遺傳算法MessyGA，其染色體的長度并不是固定的。參數(shù)設(shè)計交配概率Pc

變異概率Pm

決定了進化過程種群參加交配的染色體平均數(shù)目。取值一般為0.4至0.99。也可采用自適應(yīng)方法調(diào)整算法運行過程中的交配概率。增加群體進化的多樣性，決定了進化過程中群體發(fā)生變異的基因平均個數(shù)。Pm的值不宜過大。因為變異對已找到的較優(yōu)解具有一定的破壞作用，如果Pm的值太大，可能會導(dǎo)致算法目前處于的較好的搜索狀態(tài)倒退回原來較差的情況。Pm的取值一般為0.001至0.1之間。也可采用自適應(yīng)方法調(diào)整算法運行過程中的Pm值。參數(shù)設(shè)計復(fù)制交叉變異為了避免有效基因的損失用于組合新的個體，降低對有效模式的破壞增加種群的有效性五、遺傳算子確定性采樣排擠模型最佳個體保存模型適應(yīng)值比例模型排序模型隨機錦標賽模型無回放余數(shù)隨機采樣期望值模型選擇算子交配算子單性孢子交配算子邊重組交配算子循環(huán)交配算子順序交配算子部分匹配交配算子多點交配算子算術(shù)交配算子均勻交配算子兩點交配算子邊集合交配算子變異算子非均勻變異算子高斯變異算子邊界變異算子算子選擇1、選擇算子設(shè)群體大小為，其中個體的適應(yīng)度為

，則被選擇的概率

為:

遺傳操作（1）適應(yīng)度比例方法(fitnessproportionmodel)適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法。它也叫賭輪或蒙特卡羅（MonteCarlo）選擇。在該方法中，各個個體的選擇概率和其適應(yīng)度值成比例。14.4%49.2%30.9%5.5%1234使用賭輪方法的選擇（2）最佳個體保存方法（elitistmodel）該方法的思想是把群體中適應(yīng)度最高的個體不進行配對交叉而直接復(fù)制到下一代中，此種選擇操作又稱復(fù)制。DeJong對此方法作了如下定義：設(shè)到時刻t（第t代）時，群體中a*(t)為最佳個體。又設(shè)A(t+1)為新一代群體，若A(t+1)中不存在a*(t)，則把a*(t)作為A(t+1)中的第n+1個個體。選擇

適應(yīng)度計算：按比例的適應(yīng)度函數(shù)（proportionalfitnessassignment）基于排序的適應(yīng)度計算（Rank-basedfitnessassignment）

選擇算法：輪盤賭選擇（roulettewheelselection）選擇

選擇算法：隨機遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截斷選擇（truncationselection）錦標賽選擇（tournamentselection）除了上述選擇算子外，還有期望值方法(expectedvaluemodel)排序選擇方法(rank-basedmodel)聯(lián)賽選擇方法(tournamentselectionmodel)排擠方法(crowdingmodel)等個體選擇概率的常用分配方法按比例的適應(yīng)度分配（proportionalfitnessassignment）

某個體i，其適應(yīng)度為fi，則其被選取的概率Pi為：

個體ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09常用選擇方法輪盤賭選擇法（roulettewheelselection）

個體1234567891011適應(yīng)度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計概率0.180.340.490.620.730.820.890.950.981.001.00常用選擇方法隨機遍歷抽樣法（stochasticuniversalsampling）

個體1234567891011適應(yīng)度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計概率0.180.340.490.620.730.820.890.950.981.001.00常用選擇方法局部選擇法（localselection）

(1)線形鄰集在局部選擇法中，每個個體處于一個約束環(huán)境中，稱為局部鄰域(而其他選擇方法中視整個種群為個體之鄰域)，個體僅與其鄰近個體產(chǎn)生交互，該鄰域的定義由種群的分布結(jié)構(gòu)給出。鄰域可被當作潛在的交配伙伴。首先均勻隨機地選擇一半交配種群，選擇方法可以是隨機遍歷方法也可以是截斷選擇方法，然后對每個被選個體定義其局部鄰域，在鄰域內(nèi)部選擇交配伙伴。常用選擇方法局部選擇法（localselection）

(2)兩對角鄰集常用選擇方法局部選擇法（localselection）

(2)兩對角鄰集常用選擇方法截斷選擇法（truncationselection）

個體按適應(yīng)度排列，只有優(yōu)秀個體能夠稱為父個體，參數(shù)為截斷閥值（被選作父個體的百分比）。常用選擇方法錦標賽選擇法（tournamentselection）隨機從種群中挑選一定數(shù)目個體，其中最好的個體作為父個體，此過程重復(fù)進行完成個體的選擇。交叉點（1）一點交叉（one-pointcrossover）具體操作是：在個體串中隨機設(shè)定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結(jié)構(gòu)進行互換，并生成兩個新個體。如：個體A10011111001000新個體A個體B00110000011111新個體B2、交叉算子此外還有多點交叉和一致交叉（uniformcrossover）等交叉算子。設(shè)置兩個交叉點，如：個體A10011111011111新個體A個體B00110000001000新個體B（2）兩點交叉（two-pointcrossover）在染色體交配階段，每個染色體能否進行交配由交配概率Pc（一般取值為0.4到0.99之間）決定，其具體過程為：對于每個染色體，如果Random(0,1)小于Pc則表示該染色體可進行交配操作（其中Random(0,1)為[0,1]間均勻分布的隨機數(shù)），否則染色體不參與交配直接復(fù)制到新種群中。每兩個按照Pc交配概率選擇出來的染色體進行交配，經(jīng)過交換各自部分基因，產(chǎn)生兩個新的子代染色體。具體操作是隨機產(chǎn)生一個有效的交配位置，染色體交換位于該交配位置后的所有基因。交叉或基因重組

實值重組（realvaluedrecombination）：離散重組（discreterecombination）中間重組（intermediaterecombination）線性重組（linearrecombination）擴展線性重組（extendedlinearrecombination）交叉或基因重組

二進制交叉（binaryvaluedcrossover）：單點交叉(single-pointcrossover)多點交叉(multiple-pointcrossover)均勻交叉(uniformcrossover)洗牌交叉(shufflecrossover)縮小代理交叉(crossoverwithreducedsurrogate)實值重組離散重組

子個體的每個變量可以按等概率隨機地挑選父個體。父個體112

25

5父個體2123

4

34子個體1123

4

5子個體212

4

34實值重組中間重組

子個體＝父個體1＋α×（父個體2－父個體1）

α是比例因子，由[-d,1+d]上均勻分布地隨機數(shù)產(chǎn)生。

d=0時為中間重組，一般取d=0.25。子代的每個變量均產(chǎn)生一個α。實值重組中間重組

父個體1

12255父個體2

123434子個體1子個體2α值樣本1

0.51.1-0.1α值樣本2

0.10.80.512＋0.5×（123－12）=67.567.525＋1.1×（4－25）=1.91.92.112＋0.1×（123－12）=23.123.18.219.5實值重組中間重組

實值重組線性重組

父個體1

12255父個體2

123434子個體1子個體2α值樣本10.5α值樣本20.112＋0.5×（123－12）=67.567.525＋0.5×（4－25）=14.514.519.512＋0.1×（123－12）=23.123.122.97.9實值重組線性重組

二進制交叉均勻交叉

父個體1

01110011010

父個體210101100101子個體1

1

11

011

11

1

1

1子個體2

0

01

100

00

0

0

0

樣本101100011010樣本210011100101變異點（1）基本變異算子對群體個體串隨機挑選一個或多個基因，并對這些基因做變動。如：個體A10011111101011新個體A

3、變異算子逆轉(zhuǎn)點個體A1001011110101011新個體A（2）逆轉(zhuǎn)算子（inversionoperator）染色體的變異作用于基因之上，對于交配后新種群中染色體的每一位基因，根據(jù)變異概率Pm判斷該基因是否進行變異。如果Random(0,1)小于Pm，則改變該基因的取值（其中Random(0,1)為[0,1]間均勻分布的隨機數(shù)）。否則該基因不發(fā)生變異，保持不變。事先給定最大進化步數(shù)，或者判斷最優(yōu)值在連續(xù)若干步?jīng)]有變化。六、算法終止條件編碼表示:初始化:適配值:二進制選擇策略:遺傳算子:雜交變異停止準則:已經(jīng)找到能接受的解;迭代了預(yù)置的次數(shù).研究重點主要集中在以下幾方面：算法的數(shù)學(xué)基礎(chǔ)：包括算法的收斂性理論，早熟現(xiàn)象與欺騙問題，交叉算子的數(shù)學(xué)意義與統(tǒng)計解釋，參數(shù)設(shè)置對算法的影響等。算法與其他優(yōu)化技術(shù)的比較和融合：充分利用遺傳算法的大范圍群體搜索性能，與快速收斂的局部優(yōu)化方法混合產(chǎn)生有效的全局優(yōu)化方法，從根本上提高遺傳算法計算性能。算法的改進和深化：據(jù)實際應(yīng)用不斷改進和完善算法的編碼策略、基因操作方法、參數(shù)選擇等。算法的并行化研究：并行遺傳算法(PGA)正成為一個重要的研究方向。第五節(jié)遺傳算法的改進及其并行性算法改進遺傳算法本質(zhì)上依賴于問題的編碼以及遺傳操作算子，要發(fā)展遺傳算法也要以這幾個方面作為突破口解決實際問題，經(jīng)驗往往要起到?jīng)Q定性作用，不要期望能很快很好的解決問題多親和單親遺傳算法多目標優(yōu)化問題和其他優(yōu)化算法整合，取長補短

遺傳算法的改進

改進的途徑改變遺傳算法的組成成分；采用混合遺傳算法；采用動態(tài)自適應(yīng)技術(shù)；采用非標準的遺傳操作算子；采用并行遺傳算法等。

遺傳算法的改進

改進思路1991年Eshelman提出的一種改進遺傳算法；C：跨代精英選擇（Crossgenerationalelitistselection）策略；H：異物種重組（Heterogeneousrecombination）；C：大變異（Cataclysmicmutation）。

1、CHC算法

遺傳算法的改進

選擇上一代種群與通過新的交叉方法產(chǎn)生的個體群混合起來，從中按一定概率選擇較優(yōu)的個體；即使交叉操作產(chǎn)生較劣個體偏多，由于原種群大多數(shù)個體殘留，不會引起個體的評價值降低；可以更好地保持遺傳多樣性；排序方法，克服比例適應(yīng)度計算的尺度問題。

1、CHC算法

遺傳算法的改進

交叉均勻交叉的改進：當兩個父個體位值相異的位數(shù)為m時，從中隨機選取m/2個位置，實行父個體位值的交換；顯然，這樣的操作對模式具有很強的破壞性。確定一閾值，當個體間距離低于該閾值時，不進行交叉操作。進化收斂的同時，逐漸地減小該閾值。

1、CHC算法

遺傳算法的改進

變異在進化前期不采取變異操作，當種群進化到一定收斂時期，從最優(yōu)個體中選擇一部分個體進行初始化；初始化：選擇一定比例（擴散率，一般0.35）的基因座，隨機地決定它們的位值。

1、CHC算法

遺傳算法的改進

參數(shù)分析交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性；Pc越大，新個體產(chǎn)生的速度就越快，但過大會使優(yōu)秀個體的結(jié)構(gòu)很快被破壞；Pc過小，搜索過程緩慢，以至停止不前；Pm過小，不易產(chǎn)生新個體結(jié)構(gòu)，Pm過大，變成純粹的隨機搜索；

2、自適應(yīng)遺傳算法

遺傳算法的改進

自適應(yīng)策略Srinvivas等提出一種自適應(yīng)遺傳算法，Pc和Pm能夠隨適應(yīng)度自動改變：當種群各個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，使Pc和Pm增加；而當群體適應(yīng)度比較分散時，使Pc和Pm減少；對于適應(yīng)度較高的個體，對應(yīng)于較低的Pc和Pm

；而較低適應(yīng)度的個體，對應(yīng)于較高的Pc和Pm

。

2、自適應(yīng)遺傳算法

自適應(yīng)方法

fmax——群體中最大的適應(yīng)度值；

favg——每代群體的平均適應(yīng)度值；

f’——要交叉的兩個個體中較大的適應(yīng)度值；

f——要交叉或變異的個體適應(yīng)度值；k1、k2、k3、k4取(0,1)的值

遺傳算法的改進

2、自適應(yīng)遺傳算法

自適應(yīng)方法進一步改進適用于進化后期，不適于進化前期，因為前期的優(yōu)秀個體有可能是局部最優(yōu)點；使最大適應(yīng)度個體的交叉概率和變異概率由0提高到Pc2和Pm2

；采用精英選擇策略；

遺傳算法的改進

2、自適應(yīng)遺傳算法

自適應(yīng)方法進一步改進

遺傳算法的改進

2、自適應(yīng)遺傳算法

小生境概念小生境（niche）：生物學(xué)中,特定環(huán)境中的一種組織功能；在自然界中,往往特征、性狀相似的物種相聚在一起,并在同類中交配繁衍后代。在SGA中，容易“近親繁殖”；NGA(NicheGenericAlgorithm),將每一代個體劃分為若干類,每類選出優(yōu)秀個體組成一個種群；優(yōu)勢：保持解的多樣性,提高全局搜索能力,適合復(fù)雜多峰函數(shù)的優(yōu)化。

遺傳算法的改進

3、基于小生境技術(shù)的遺傳算法

選擇策略預(yù)選擇機制、排擠機制、分享機制；預(yù)選擇（preselection,1970）機制當子個體的適應(yīng)度超過其父個體適應(yīng)度時，子個體才可以替代父個體，否則父個體仍保留；有效維持種群多樣性，造就小生境進化環(huán)境。

遺傳算法的改進

3、基于小生境技術(shù)的遺傳算法

排擠（crowding,1975）機制設(shè)置排擠因子CF（CF=2或3），隨機選取1/CF的個體組成排擠成員，排擠與其相似（用距離來度量）的個體；個體之間的相似性可用個體編碼串之間的海明距離來度量。

遺傳算法的改進

3、基于小生境技術(shù)的遺傳算法

共享（sharing,1987）機制通過個體之間的相似性程度的共享函數(shù)來調(diào)整各個體的適應(yīng)度；共享函數(shù)的目的：將搜索空間的多個峰值在地理上區(qū)分開來，每一個峰值處接受一定比例數(shù)目的個體，比例數(shù)目與峰值高度有關(guān)；

遺傳算法的改進

3、基于小生境技術(shù)的遺傳算法

共享（sharing,1987）機制共享函數(shù)的值越大，表明個體之間越相似，記為Sh(dij)，dij為兩個個體i和j之間的距離；

σshare是niche的半徑，由使用者給定。

遺傳算法的改進

3、基于小生境技術(shù)的遺傳算法

共享（sharing,1987）機制共享法將個體的適應(yīng)度降低，即適應(yīng)度值fi除以一個niche計數(shù)mi：在距離為σshare的范圍內(nèi)的個體彼此削減適應(yīng)度，這些個體將收斂在一個niche內(nèi)，避免了整個種群的收斂。

遺傳算法的改進

3、基于小生境技術(shù)的遺傳算法

是生命科學(xué)中免疫原理與傳統(tǒng)遺傳算法的結(jié)合。核心免疫算子接種疫苗免疫選擇理論上是概率1收斂的。免疫遺傳算法引言遺傳算法的迭代搜索過程：“產(chǎn)生----測試”一定程度上不可避免退化現(xiàn)象出現(xiàn)忽視特征信息，缺少靈活性深入挖掘和利用人類的智能資源，這是免疫遺傳算法的出發(fā)點。全免疫(fullimmunity)目標免疫(targetimmunity)非特異性特異性全免疫指種群中每個個體在遺傳算子作用后，對其每一環(huán)節(jié)進行一次免疫操作。目標免疫指在進行了遺傳操作后，經(jīng)過一定的判斷，個體僅在作用點處發(fā)生免疫操作。一、免疫遺傳算法首先，對所求解問題進行具體分析，從中提取最基本的特征信息。其次，對特征信息進行處理，將其轉(zhuǎn)化為求解問題的一種方案?？乖?antigen)疫苗(vaccine)抗體(antibody)最后，將此方案以適當?shù)男问睫D(zhuǎn)化為免疫算子，以實現(xiàn)具體操作。實際操作過程1、接種疫苗方法與目的：按照先驗知識來修改其某些基因位上的基因，使所得個體以較大概率具有更高的適應(yīng)值。其一、每一基因位上的信息都錯誤，則轉(zhuǎn)移概率為0。其二、每一基因位都是正確的，則轉(zhuǎn)移概率為1。實現(xiàn)考慮以下兩種特殊情況：2、免疫選擇目的：改進退化個體。第一步是免疫檢測，不如父代則被父代代替。否則進行第二步。第二步是退火選擇。操作分兩步完成：算法步驟：Step1隨機產(chǎn)生初始父代群體A1;Step2根據(jù)先驗知識提取疫苗;Step3若當前種群包含了最佳個體，結(jié)束;否則進行以下的步驟;Step4對種群Ak進行交叉操作得到種群Bk;Step5對種群Bk進行變異操作得到種群Ck;Step6對種群Ck進行接種疫苗操作得到種群Dk;Step7對種群Dk進行免疫操作得到下一代父代種群Ak+1，轉(zhuǎn)step3。算法收斂性分析：定理免疫遺傳算法是概率1收斂的，若算法中略去免疫算子，則該算法將不再保證收斂到全局最優(yōu)值。免疫疫苗的選取示例：1、分析待求問題，搜集特征信息最短距離法2、根據(jù)特征信息制作免疫疫苗在最終方案中，必然包括相鄰城市間最短距離。由此作為提取疫苗的依據(jù)。3接種疫苗0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011

遺傳算法的基本操作

簡單實例產(chǎn)生初始種群計算適應(yīng)度（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）簡單實例選擇個體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.08695758＋5＋2＋10＋7＋12＋5＋19＋10＋140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174

遺傳算法的基本操作

簡單實例選擇個體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000

遺傳算法的基本操作

簡單實例選擇在0～1之間產(chǎn)生一個隨機數(shù)：個體染色體適應(yīng)度選擇概率累積概率100011000008201011110015300000001012410011101001051010101010