遺傳算法及其在路徑規(guī)劃中的應用課件

1、遺傳算法及其在路徑規(guī)劃中的應用北京科技大學自動化學院控制科學與工程系7/29/20221北京科技大學自動化學院控制科學與工程系第1頁，共48頁。參考書目：（1）周德儉，吳斌. 智能控制. 重慶：重慶大學出版社，2005（2）李少遠，王景成. 智能控制. 北京：機械工業(yè)出版社，2005（3）李人厚. 智能控制理論和方法. 西安：西安電子科技大學出版社，1999（4）王順晃，舒迪前. 智能控制系統(tǒng)及其應用（第二版）. 北京：機械工業(yè)出版社，20057/29/20222北京科技大學自動化學院控制科學與工程系第2頁，共48頁。 20世紀60年代，美、德等國家的一些科學家開始模仿生物和人類進化的方法來求

2、解復雜優(yōu)化問題，從而形成了模擬進化優(yōu)化方法（Optimization Method by Simulated Evolution），其代表性方法有遺傳算法（GA：Genetic Algorithms）、進化規(guī)劃（EP：Evolutionary Programming）、進化策略（ES：Evolutionary Strategies）。本講將主要對GA進行詳細介紹。 常規(guī)的數(shù)學優(yōu)化技術(shù)基于梯度尋優(yōu)技術(shù)，計算速度快，但要求優(yōu)化問題具有可微性，且通常只能求得局部最優(yōu)解；而模擬進化方法無可微性要求，適用于任意的優(yōu)化問題，尤其適用于求解組合優(yōu)化問題以及目標函數(shù)不可微或約束條件復雜的非線性優(yōu)化問題。由于它

3、們采用隨機優(yōu)化技術(shù)，所以會以較大的概率求得全局最優(yōu)解。其計算費用較高的問題也因計算機軟硬件技術(shù)的飛速發(fā)展而不再成為制約因素。1 遺傳算法產(chǎn)生的背景7/29/20223北京科技大學自動化學院控制科學與工程系第3頁，共48頁。1.1 遺傳算法的基本概念1.1.1 進化的基本理論（1）Darwin生物進化論（2）Mendel自然遺傳學說1.1.2 遺傳算法術(shù)語簡介（1）個體（染色體）：遺傳算法求解實際問題時，首先對待優(yōu)化問題的參數(shù)進行編碼（一般采用二進制碼串表示），從而得到一個字符串，該字符串被稱為一個個體（individual ）或一個染色體（chromosome）。（2）種群（群體）：所有個體的

4、集合（population）。（3）種群規(guī)模：種群中個體的數(shù)量稱為種群規(guī)模（population size）。（4）基因：個體中的每一位稱為一個基因（gene）。（5）適應度函數(shù)：能夠評價個體對環(huán)境適應能力的函數(shù)（fitness function）。7/29/20224北京科技大學自動化學院控制科學與工程系第4頁，共48頁。1.1.3 遺傳算法應用引例例：求 的最大值。解：（1）編碼方式的確定 采用五位二進制代碼表示變量x。表1 產(chǎn)生的初始種群標號初始種群x值1011011321100024301000841001119 （2）初始種群的產(chǎn)生設種群規(guī)模N=4，隨機產(chǎn)生初始種群如表1所示。7/2

5、9/20225北京科技大學自動化學院控制科學與工程系第5頁，共48頁。（3）適應度函數(shù)值的計算 取適應度函數(shù)為f (x)=x2，則4個樣本的適應度值分別如下表所示。表2 適應度函數(shù)計算標號初始種群適應度值f (x)=x210110116921100057630100064410011361總 計1170平均值292.5最大值576x值13248197/29/20226北京科技大學自動化學院控制科學與工程系第6頁，共48頁。（4）復制 采用賭輪法計算各個個體被復制的次數(shù)。表3 復制操作過程標號初始種群適應度f (x)=x210110116921100057630100064410011361總

6、計1170平均值292.5最大值576x值1324819復制概率期望的復制數(shù)實際得到的復制數(shù)0.1440.4920.0550.3091.0000.250.4920.581.970.221.234.001.001.9712014127/29/20227北京科技大學自動化學院控制科學與工程系第7頁，共48頁。（5）交叉 采用隨機交叉配對，一點交叉方式進行交叉。表4 交叉操作過程標號復制后匹配池中的個體1011013211000431100014100112總 計平均值最大值新種群01000110011110110010f (x)=x235358252918646258413241854463.58

7、41配對對象（隨機選取）交叉點（隨機選?。﹛值7/29/20228北京科技大學自動化學院控制科學與工程系第8頁，共48頁。（6）變異 采用單點隨機變異方式進行變異操作。表5 變異操作過程標號交叉后的種群101000211001311101410010總 計平均值最大值新種群01100110011110110010f (x)=x23/122529181446258413241934483.5841變異點位置x值7/29/20229北京科技大學自動化學院控制科學與工程系第9頁，共48頁。1.2 遺傳算法的基本步驟1.2.1 遺傳算法的流程確定表示問題解的編碼隨機生成初始種群確定適應度函數(shù)f計算種群

8、中各個體的適應度 fi選擇高適應度的個體進行復制交叉變異輸出最優(yōu)解是否滿足收斂判據(jù)？是否圖1 遺傳算法的基本流程圖7/29/202210北京科技大學自動化學院控制科學與工程系第10頁，共48頁。1.2.2 遺傳算法的具體實現(xiàn)（1）編碼方式的選取 利用遺傳算法求解實際問題時，問題的解是用字符串來表示的，遺傳算子也是直接對字符串進行操作的。因此，如何用適當?shù)淖址幋a來表示問題的解成為了遺傳算法應用過程中的首要問題。 目前所使用的字符串編碼方式主要有：二進制、實數(shù)（浮點數(shù)）和符號等。 （1）采用二進制形式編碼，個體的位數(shù)多，描述得比較細致，從而加大了搜索范圍；但交叉運算的計算量較大，并且由于大量的

9、具體問題本身都是十進制的，所以還需對實際參數(shù)進行編碼和譯碼，從而增加了額外的計算時間。 （2）采用實數(shù)（浮點數(shù)）編碼，交叉運算的計算量較小，但變異過程難于進行。 （3）符號編碼方式通常在一些專門的應用場合使用。7/29/202211北京科技大學自動化學院控制科學與工程系第11頁，共48頁。（2）初始種群的產(chǎn)生 初始種群對應著問題的初始解，通常有兩種方式產(chǎn)生： 完全隨機方式產(chǎn)生（字符串每一位均隨機產(chǎn)生）； 隨機數(shù)發(fā)生器方式產(chǎn)生（整個字符串用隨機數(shù)發(fā)生器一次產(chǎn)生）。 另外，如果對于尋優(yōu)問題有某些先驗知識，則可先將這些先驗知識轉(zhuǎn)變?yōu)楸仨殱M足的一組約束，然后再在滿足這些約束的解中隨機地選取個體以組成初

10、始種群。（3）適應度函數(shù)的確定 適應度函數(shù)是遺傳算法與實際優(yōu)化問題之間的接口。在遺傳算法中要求適應度函數(shù)值是非負的，且任何情況下都希望其值越大越好；而實際優(yōu)化問題的目標函數(shù)并不一定滿足這個條件，有的是正的，有的可能為負，甚至可能是復數(shù)值。因此，對于任意優(yōu)化問題，首先應把其數(shù)學形式表示為遺傳算法適于求解的形式，同時要保證二者在數(shù)學優(yōu)化層面上是等價的。這個過程稱為適應度轉(zhuǎn)換。7/29/202212北京科技大學自動化學院控制科學與工程系第12頁，共48頁。 適應度轉(zhuǎn)換首先要保證適應度值是非負的，其次要求目標函數(shù)的優(yōu)化方向應與適應度值增大的方向一致。設實際優(yōu)化問題的目標函數(shù)為J(x)，遺傳算法的適應度

11、函數(shù)為f(x)，則有： 可以將適應度函數(shù)表示為實際優(yōu)化問題目標函數(shù)的線性形式，即有其中，a，b是系數(shù)，可根據(jù)具體問題的特征及所期望適應度的分散程度來確定。 對于最小化問題，一般采用如下轉(zhuǎn)換形式：其中，cmax既可以是到目前為止所有進化代中目標函數(shù) J(x) 的最大值（此時cmax將隨著進化而有所變化），也可以根據(jù)經(jīng)驗人為設定。當其它7/29/202213北京科技大學自動化學院控制科學與工程系第13頁，共48頁。 對于最大化問題（如需要），一般采用如下轉(zhuǎn)換形式：其中，cmin既可以是當前代中目標函數(shù) J(x) 的最小值，也可以根據(jù)經(jīng)驗人為設定。 采用如下的指數(shù)函數(shù)形式： 在最大化問題時，c一般取

12、1.618或2；而在最小化問題時，c可取為0.618。這樣，既保證了適應度值非負，又使適應度值增大方向和目標函數(shù)優(yōu)化方向一致。當其它7/29/202214北京科技大學自動化學院控制科學與工程系第14頁，共48頁。（4）復制（選擇）（Reproduction or Selection） 復制是基于適者生存理論而提出的，是指種群中每一個體按照適應度函數(shù)進入到匹配池中的過程。適應度值高于種群平均適應度的個體在下一代中將有更多的機會繁殖一個或多個后代，而低于平均適應度的個體則有可能被淘汰掉。復制的目的在于保證那些適應度高的優(yōu)良個體在進化中生存下去，復制不會產(chǎn)生新的個體。常用的復制方法有：賭輪法兩兩競爭

13、法 從種群中隨機地選擇兩個個體，將其中適應度較大的個體作為被復制的個體；若兩個體適應度相同，則任意選擇一個。排序法 首先根據(jù)目標函數(shù)值的大小將個體排序，根據(jù)具體問題應用各個體的排序序號分配各自進入匹配池的概率。適應度可以按序號線性變化，也可以按某種非線性關(guān)系變化。7/29/202215北京科技大學自動化學院控制科學與工程系第15頁，共48頁。（5）交叉（Crossover） 交叉是指對從匹配池中隨機選出的兩個個體按一定的交叉概率 pc 部分地交換某些基因的過程。一般分兩步實現(xiàn)：第一步是將新復制產(chǎn)生的匹配池中的個體隨機兩兩配對；第二步是進行交叉繁殖，產(chǎn)生一對新的個體。交叉的目的是為了生成新的個體

14、，產(chǎn)生新的基因組合，避免每代種群中個體的重復。單點交叉（One-Point Crossover） 對每一對相互配對的個體，依設定的交叉概率pc在其交叉點處相互交換兩個父代個體的部分染色體，從而產(chǎn)生出兩個新的個體，如下圖所示。交叉前individual 111001 11001individual 201010 00110圖2 單點交叉交叉后11001 0011001010 110017/29/202216北京科技大學自動化學院控制科學與工程系第16頁，共48頁。兩點交叉（Two-Point Crossover） 按交叉概率隨機設置兩個交叉點，然后交換兩個父代個體在兩個交叉點之間的基因。均勻交叉

15、（Uniform Crossover） 其操作過程是：先選出兩個父代個體，之后依據(jù)交叉概率 pc 產(chǎn)生一個與父代個體同樣長度的二進制串，這里稱其為模板（template）。若模板中的某位為0，則兩個父代個體對應位不進行交換；反之，模板中的某位為1時，則交換兩個父代個體對應位的基因。交叉前individual 111 01011 000individual 210 10110 101圖3 兩點交叉交叉后11 10110 00010 01011 1017/29/202217北京科技大學自動化學院控制科學與工程系第17頁，共48頁。算數(shù)交叉（Arithmetic Crossover） 算數(shù)交叉的操作

16、對象一般是由浮點數(shù)編碼所表示的個體，它通過兩個父代個體的線性組合而產(chǎn)生出兩個新的個體。 假設在兩個父代個體 ， 之間進行算數(shù)交叉，則交叉運算后所產(chǎn)生出的兩個新個體是式中 為一參數(shù)，它若是一個常數(shù)，此時所進行的交叉運算稱為均勻算數(shù)交叉；它也可以是一個由進化代數(shù)所決定的變量，此時所進行的交叉運算稱為非均勻算數(shù)交叉。交叉前individual 10101100110template1001010101圖4 均勻交叉individual 20110010001交叉后010011001101110001007/29/202218北京科技大學自動化學院控制科學與工程系第18頁，共48頁。（6）變異（Mut

17、ation） 一般的變異操作只作用于采用二進制編碼的某單個個體，它以一定的變異概率pm對個體的某些位進行取反操作。如同自然界很少發(fā)生基因突變一樣，變異概率pm一般都取得比較小。變異的目的是為了增加種群個體的多樣性，防止丟失一些有用的遺傳模式。 在簡單遺傳算法中，變異就是將某個體中某一位的值作取反運算。變異前1100110111圖5 變異操作示意圖變異后11000101117/29/202219北京科技大學自動化學院控制科學與工程系第19頁，共48頁。（7）收斂判據(jù) 常規(guī)的優(yōu)化方法有數(shù)學上比較嚴格的收斂判據(jù)，而遺傳算法的收斂判據(jù)通常是啟發(fā)式的。由于遺傳算法沒有利用梯度信息，因此要從數(shù)學上構(gòu)造比較

18、嚴格的收斂判據(jù)相當困難。常用的收斂判據(jù)有： 根據(jù)計算時間和所采用計算機的性能確定收斂判據(jù)：一般采用指定最大迭代次數(shù)的方法； 從解的質(zhì)量方面確定判據(jù)：如果連續(xù)幾代（或幾十代）種群中的最優(yōu)解沒有變化，則認為算法收斂；或種群中最優(yōu)個體的適應度與平均適應度之差和平均適應度的比值小于某一給定值時，也可以認為算法已經(jīng)收斂。7/29/202220北京科技大學自動化學院控制科學與工程系第20頁，共48頁。（8）約束條件的處理 遺傳算法在求解有約束的優(yōu)化問題時，需對約束條件進行必要的處理。處理方式有：直接體現(xiàn)在字符串的編碼中 對于優(yōu)化問題中變量的上、下限約束，可以讓字符串表示的最大值和最小值分別對應于實際約束變

19、量的上、下限值。設待優(yōu)化變量x的變化范圍為xmin, xmax，如用l 位的二進制字符串y來表示，則 x、y之間有如下關(guān)系：判斷舍棄法 在遺傳算法的運算過程中，檢查得到字符串所對應的解是否為可行解。若是，則加入到下一代種群中；否則將其舍棄。懲罰函數(shù)法 如果一個解違反了某個約束，則視其違反程度給予一定的懲罰，使其具有較小的適應度。越限越嚴重，適應度就越小。7/29/202221北京科技大學自動化學院控制科學與工程系第21頁，共48頁。1.3 遺傳算法的特點 目前常規(guī)的優(yōu)化方法主要有3種類型：解析法、枚舉法和隨機法。 解析法是優(yōu)化方法中研究最多的一種，它又分為直接法和間接法。直接法是一種通過沿著梯

20、度信息最陡的方向逐漸運動來尋找局部極值的方法；間接法則是一種通過使目標函數(shù)梯度為零，進而通過求解一組非線性方程來尋找局部極值的方法。（1）解析法 解析法的主要問題在于： （1）要求目標函數(shù)連續(xù)光滑且可微； （2）一般只能找到局部極值而非全局極值，故對于存在多峰極值的優(yōu)化問題有時顯得無能為力。7/29/202222北京科技大學自動化學院控制科學與工程系第22頁，共48頁。 隨機法能夠克服上述兩種方法的缺陷，它在搜索空間中隨機地漫游并記錄下所找到的最優(yōu)結(jié)果，當搜索到一定程度后便終止。當然，它所找到的結(jié)果往往也不是最優(yōu)解。實際上，隨機法也是枚舉法中的一種。（2）枚舉法 枚舉法能夠克服解析法的兩點不足

21、，它可以找到全局極值且不要求目標函數(shù)連續(xù)光滑。但其致命缺點是計算效率太低，對于許多實際問題往往會因為搜索空間太大而不可能將所有的情況一一搜索到。（3）隨機法7/29/202223北京科技大學自動化學院控制科學與工程系第23頁，共48頁。 遺傳算法是基于自然選擇和基因遺傳學原理的搜索方法，它將“優(yōu)勝劣汰、適者生存”的生物進化原理引入到由待優(yōu)化參數(shù)形成的編碼串種群中，按照一定的適應度函數(shù)及一系列遺傳操作對各個個體進行篩選，使適應度值較高的個體被保留下來，從而組成新的種群，新種群中包含了上一代的大量信息，并且引入了新的優(yōu)于上一代的個體。如此周而復始，種群中各個體的適應度不斷提高，直至滿足一定的收斂條

22、件。最后，以種群中適應度值最高的個體作為待優(yōu)化參數(shù)的最優(yōu)解。（4）遺傳算法 遺傳算法也用到了隨機搜索技術(shù)，但它通過對參數(shù)空間的隨機編碼并用適應度函數(shù)作為工具來引導搜索過程向著更有效的方向發(fā)展，因而它不同于常規(guī)的隨機法。7/29/202224北京科技大學自動化學院控制科學與工程系第24頁，共48頁。 與常規(guī)優(yōu)化方法相比，遺傳算法的魯棒性較好，其主要特點在于： 遺傳算法對參數(shù)的編碼進行操作，而不是對參數(shù)本身； 遺傳算法從多個初始點開始操作，而不是從某一個點開始，這在很大程度上避免了搜索過程過早地收斂于局部極值，因此更有可能求得全局極值； 遺傳算法通過目標函數(shù)計算適應度，它不需要其它的推導運算和附加

23、信息，因而對問題的依賴性??； 遺傳算法使用概率的操作規(guī)則，而不是確定性的規(guī)則； 遺傳算法在解空間中采用啟發(fā)式搜索，而不是盲目的枚舉或完全隨機的搜索，因而搜索的效率高； 遺傳算法對于待尋優(yōu)的問題基本沒有限制，既可以是數(shù)學解析式所表示的顯函數(shù)，也可以是映射矩陣或神經(jīng)網(wǎng)絡表示的隱函數(shù)，同時也不要求待優(yōu)化函數(shù)連續(xù)、可微；7/29/202225北京科技大學自動化學院控制科學與工程系第25頁，共48頁。 遺傳算法所具有的隱含并行性的特點，使其可以通過大規(guī)模并行搜索來提高計算速度； 遺傳算法適合復雜的、高度非線性問題的優(yōu)化。1.4 遺傳算法的研究熱點（1）編碼方式的確定；（2）專用遺傳算子的設計；（3）控制

24、參數(shù)的選擇；種群規(guī)模：N = 20100；交叉概率：pc = 0.600.95；變異概率：pm = 0.0010.01。李擎、張偉、尹怡欣、王志良一種新的調(diào)節(jié)交叉和變異概率的自適應算法控制與決策，2008年1月第23卷第1期：7983 7/29/202226北京科技大學自動化學院控制科學與工程系第26頁，共48頁。2 遺傳算法的應用實例車載導航系統(tǒng)路徑規(guī)劃算法的設計2.1 問題簡介 所謂車載導航系統(tǒng)路徑規(guī)劃，就是在電子地圖中找到一條從起點到終點在距離（或時間）上最短的路徑。 下圖為一個路徑規(guī)劃用仿真地圖，其上共有15個節(jié)點，24條弧?；∠碌臄?shù)據(jù)表示路徑的長度（單位：公里），弧上的數(shù)據(jù)則表示該路

25、段車輛行駛的速度（單位：米/秒）。 在實際電子地圖中，節(jié)點相當于道路的交叉點，弧相當于實際道路。7/29/202227北京科技大學自動化學院控制科學與工程系第27頁，共48頁。1.505.21.090.860.750.801.7112.006.001.332.402.001.330.750.920.801.201.503.001.091.714.001.203.001.501.333.4YX2.82.24.22.24.53.23.22.93.54.42.02.93.03.04.22.24.05.05.63.54.14.23.4DPNLOMFCBGKHIJAE圖6 路徑規(guī)劃用仿真地圖7/29/2

26、02228北京科技大學自動化學院控制科學與工程系第28頁，共48頁。2.2 遺傳算法的具體應用（1）路徑的表示方法 這里采用符號編碼方式表示實際路網(wǎng)中的路徑。 對于圖6中一條從A點到P點的路徑，采用符號編碼方式得到的個體為A、B、E、H、L、O、P。圖7 仿真地圖中的一條路徑ABEHLOP7/29/202229北京科技大學自動化學院控制科學與工程系第29頁，共48頁。（2）初始路徑的產(chǎn)生傳統(tǒng)遺傳算法 隨機生成初始路徑，會產(chǎn)生斷路或環(huán)路。改進遺傳算法（a）克服斷路的思路 從起始點出發(fā)，隨機選取與起始點直接相連的一個點作為下一個節(jié)點，如此反復直到找到終點為止。 在路徑的產(chǎn)生過程中為了避免出現(xiàn)環(huán)路，

27、規(guī)定在一條路徑中當一個路徑節(jié)點被選中以后，則給該節(jié)點一個標記，只有沒有標記的節(jié)點才能被選作新的路徑節(jié)點，每條初始路徑選擇完畢后標記全部刷新。 （b）克服環(huán)路的思路7/29/202230北京科技大學自動化學院控制科學與工程系第30頁，共48頁。（3）適應度函數(shù)的確定距離最短優(yōu)化原則下的適應度函數(shù)時間最優(yōu)優(yōu)化原則下的適應度函數(shù)其中， 為第i個染色體（路徑）； 為第i條路徑第j段的路徑長度。其中， 仍為第i條路徑第j段的路徑長度； 為第i條路徑第j段的行駛速度。7/29/202231北京科技大學自動化學院控制科學與工程系第31頁，共48頁。 不能象傳統(tǒng)遺傳算法那樣隨機進行一點、兩點或多點交叉操作，因

28、為這樣很容易產(chǎn)生斷路或環(huán)路。 這里只允許使用在重復節(jié)點位置交叉且只進行一點交叉的操作方式，具體實現(xiàn)步驟如下：（5）交叉操作（4）復制（選擇）操作 采用賭輪法進行復制操作。 隨機選取兩個個體作為待交叉?zhèn)€體； 找出兩個待交叉?zhèn)€體的共同節(jié)點（起點和終點除外）的集合； 從共同節(jié)點的集合中隨機選擇一個節(jié)點作為交叉節(jié)點； 檢查兩個待交叉?zhèn)€體在交叉節(jié)點之前或之后的內(nèi)容是否相同。如相同，則取消本次交叉操作；否則，兩者交換交叉點之前（或之后）的內(nèi)容形成兩個新個體。7/29/202232北京科技大學自動化學院控制科學與工程系第32頁，共48頁。 下面將結(jié)合仿真地圖舉例說明交叉操作是如何實現(xiàn)的。 設選取的兩個待交叉

29、樣本為A、B、E、I、L、O、P和A、C、E、H、L、N、P； 兩者重復節(jié)點的集合為E、L； 隨機選擇E作為交叉節(jié)點； 檢查發(fā)現(xiàn)兩者待交叉樣本在E點之前和之后的內(nèi)容均不相同，因此可以進行此次交叉操作，交叉后的新個體為：A、B、E、 H、L、N、PA、C、E、 I、L、O、P和7/29/202233北京科技大學自動化學院控制科學與工程系第33頁，共48頁。圖8 交叉操作示意圖PLOCBHIAEN7/29/202234北京科技大學自動化學院控制科學與工程系第34頁，共48頁。（6）變異操作 不能采用傳統(tǒng)遺傳算法中隨機選擇變異點的做法，因為這樣同樣容易產(chǎn)生斷路或環(huán)路。 這里采用的變異操作，其基本步驟

30、如下： 隨機選取一個個體作為待變異個體； 在待變異個體中隨機選擇一個節(jié)點（起點和終點除外）作為待變異節(jié)點； 找到和該待變異節(jié)點直接相連的節(jié)點集合（該集合中不包括起點、終點以及待變異個體中的節(jié)點）； 從節(jié)點集合中隨機選取一個節(jié)點作為變異后節(jié)點； 檢查待變異節(jié)點之前和之后的節(jié)點是否與變異后節(jié)點直接相連。若直接相連，則用變異后節(jié)點替代待變異節(jié)點完成變異過程；否則，放棄此次操作，回到第步，直至將節(jié)點集合中的所有節(jié)點全部選遍。7/29/202235北京科技大學自動化學院控制科學與工程系第35頁，共48頁。 現(xiàn)結(jié)合仿真地圖舉例說明變異操作的具體實現(xiàn)方法。 選擇待變異個體為A、C、E、I、L、O、P； 經(jīng)過

31、檢查發(fā)現(xiàn)C和B不直接相連，所以取消此次變異操作；接著選取F作為變異后節(jié)點，檢查發(fā)現(xiàn)C和F、F和I直接相連，故可進行此次變異操作，變異后的新個體為 隨機選取E作為待變異節(jié)點； 與E直接相連的節(jié)點集合為B、F、H； 隨機選取B作為變異后節(jié)點；A、C、F、I、L、O、P7/29/202236北京科技大學自動化學院控制科學與工程系第36頁，共48頁。PLOFCBHIAE圖9 變異操作示意圖7/29/202237北京科技大學自動化學院控制科學與工程系第37頁，共48頁。（7）刪除操作 刪除操作的具體步驟如下： 隨機選擇一個個體； 檢查該個體中任意兩個不相鄰節(jié)點（包括起點和終點）之間是否直接相連。如果直接

32、相連，則刪除兩個節(jié)點之間的所有節(jié)點，結(jié)束此次刪除操作；否則，取消本次刪除操作。 下面也結(jié)合仿真地圖舉例說明刪除操作的具體實現(xiàn)方法。 設隨機選擇的個體為A、C、E、F、I、L、O、P； 檢查發(fā)現(xiàn)E、I直接相連，則刪除兩者之間的節(jié)點F，從而得到新個體A、C、E、I、L、O、P7/29/202238北京科技大學自動化學院控制科學與工程系第38頁，共48頁。PLOFCIAE圖10 刪除操作示意圖7/29/202239北京科技大學自動化學院控制科學與工程系第39頁，共48頁。（8）仿真結(jié)果初始種群33.5A、B、D、H、E、I、F、J、M、O、P1021.3A、C、F、I、M、O、P919.2A、B、E

33、、I、L、N、P820.6A、B、E、I、L、O、P721.5A、C、E、H、K、N、P630.6A、C、F、J、M、I、E、H、L、N、P521.3A、C、F、I、L、O、P419.9A、C、E、I、L、N、P321.9A、B、D、H、L、O、P222.0A、B、D、G、K、N、P1距離個體標號表6 初始種群及其距離7/29/202240北京科技大學自動化學院控制科學與工程系第40頁，共48頁?；诰嚯x最短原則的優(yōu)化結(jié)果19.9A、C、F、I、L、N、P1020.8A、C、E、H、L、O、P919.9A、B、E、I、L、N、P818.7A、B、E、H、L、N、P719.4A、C、E、H、L、N、P