遺傳算法及其在路徑規(guī)劃中應用北京科技大學自動化學院控制科學與工程系4/25/20231北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第1頁參考書目：（1）周德儉，吳斌.智能控制.重慶：重慶大學出版社，（2）李少遠，王景成.智能控制.北京：機械工業(yè)出版社，（3）李人厚.智能控制理論和方法.西安：西安電子科技大學出版社，1999（4）王順晃，舒迪前.智能控制系統(tǒng)及其應用（第二版）.北京：機械工業(yè)出版社，4/25/20232北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第2頁20世紀60年代，美、德等國家一些科學家開始模仿生物和人類進化方法來求解復雜優(yōu)化問題，從而形成了模擬進化優(yōu)化方法（OptimizationMethodbySimulatedEvolution），其代表性方法有遺傳算法（GA：GeneticAlgorithms）、進化規(guī)劃（EP：EvolutionaryProgramming）、進化策略（ES：EvolutionaryStrategies）。本講將主要對GA進行詳細介紹。常規(guī)數學優(yōu)化技術基于梯度尋優(yōu)技術，計算速度快，但要求優(yōu)化問題含有可微性，且通常只能求得局部最優(yōu)解；而模擬進化方法無可微性要求，適合用于任意優(yōu)化問題，尤其適合用于求解組合優(yōu)化問題以及目標函數不可微或約束條件復雜非線性優(yōu)化問題。因為它們采取隨機優(yōu)化技術，所以會以較大概率求得全局最優(yōu)解。其計算費用較高問題也因計算機軟硬件技術飛速發(fā)展而不再成為制約原因。1遺傳算法產生背景4/25/20233北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第3頁1.1遺傳算法基本概念1.1.1進化基本理論（1）Darwin生物進化論（2）Mendel自然遺傳學說1.1.2遺傳算法術語介紹（1）個體（染色體）：遺傳算法求解實際問題時，首先對待優(yōu)化問題參數進行編碼（普通采取二進制碼串表示），從而得到一個字符串，該字符串被稱為一個個體（individual）或一個染色體（chromosome）。（2）種群（群體）：全部個體集合（population）。（3）種群規(guī)模：種群中個體數量稱為種群規(guī)模（populationsize）。（4）基因：個體中每一位稱為一個基因（gene）。（5）適應度函數：能夠評價個體對環(huán)境適應能力函數（fitnessfunction）。4/25/20234北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第4頁1.1.3遺傳算法應用引例例：求最大值。解：（1）編碼方式確實定采取五位二進制代碼表示變量x。表1產生初始種群標號初始種群x值1011011321100024301000841001119（2）初始種群產生設種群規(guī)模N=4，隨機產生初始種群如表1所表示。4/25/20235北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第5頁（3）適應度函數值計算取適應度函數為f(x)=x2，則4個樣本適應度值分別以下表所表示。表2適應度函數計算標號初始種群適應度值f(x)=x210110116921100057630100064410011361總計1170平均值292.5最大值576x值13248194/25/20236北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第6頁（4）復制采取賭輪法計算各個個體被復制次數。表3復制操作過程標號初始種群適應度f(x)=x210110116921100057630100064410011361總計1170平均值292.5最大值576x值1324819復制概率期望復制數實際得到復制數0.1440.4920.0550.3091.0000.250.4920.581.970.221.234.001.001.9712014124/25/20237北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第7頁（5）交叉采取隨機交叉配對，一點交叉方式進行交叉。表4交叉操作過程標號復制后匹配池中個體1011013211000431100014100112總計平均值最大值新種群01000110011110110010f(x)=x235358252918646258413241854463.5841配對對象（隨機選?。┙徊纥c（隨機選取）x值4/25/20238北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第8頁（6）變異采取單點隨機變異方式進行變異操作。表5變異操作過程標號交叉后種群101000211001311101410010總計平均值最大值新種群01100110011110110010f(x)=x23///122529181446258413241934483.5841變異點位置x值4/25/20239北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第9頁1.2遺傳算法基本步驟1.2.1遺傳算法流程確定表示問題解編碼隨機生成初始種群確定適應度函數f計算種群中各個體適應度fi選擇高適應度個體進行復制交叉變異輸出最優(yōu)解是否滿足收斂判據？是否圖1遺傳算法基本流程圖4/25/202310北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第10頁1.2.2遺傳算法詳細實現（1）編碼方式選取利用遺傳算法求解實際問題時，問題解是用字符串來表示，遺傳算子也是直接對字符串進行操作。所以，怎樣用適當字符串編碼來表示問題解成為了遺傳算法應用過程中首要問題。當前所使用字符串編碼方式主要有：二進制、實數（浮點數）和符號等。（1）采取二進制形式編碼，個體位數多，描述得比較細致，從而加大了搜索范圍；但交叉運算計算量較大，而且因為大量詳細問題本身都是十進制，所以還需對實際參數進行編碼和譯碼，從而增加了額外計算時間。（2）采取實數（浮點數）編碼，交叉運算計算量較小，但變異過程難于進行。（3）符號編碼方式通常在一些專門應用場所使用。4/25/202311北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第11頁（2）初始種群產生初始種群對應著問題初始解，通常有兩種方式產生：

①完全隨機方式產生（字符串每一位均隨機產生）；

②隨機數發(fā)生器方式產生（整個字符串用隨機數發(fā)生器一次產生）。

另外，假如對于尋優(yōu)問題有一些先驗知識，則可先將這些先驗知識轉變?yōu)楸仨殱M足一組約束，然后再在滿足這些約束解中隨機地選取個體以組成初始種群。（3）適應度函數確實定適應度函數是遺傳算法與實際優(yōu)化問題之間接口。在遺傳算法中要求適應度函數值是非負，且任何情況下都希望其值越大越好；而實際優(yōu)化問題目標函數并不一定滿足這個條件，有是正，有可能為負，甚至可能是復數值。所以，對于任意優(yōu)化問題，首先應把其數學形式表示為遺傳算法適于求解形式，同時要確保二者在數學優(yōu)化層面上是等價。這個過程稱為適應度轉換。4/25/202312北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第12頁適應度轉換首先要確保適應度值是非負，其次要求目標函數優(yōu)化方向應與適應度值增大方向一致。設實際優(yōu)化問題目標函數為J(x)，遺傳算法適應度函數為f(x)，則有：

①能夠將適應度函數表示為實際優(yōu)化問題目標函數線性形式，即有其中，a，b是系數，可依據詳細問題特征及所期望適應度分散程度來確定。

②對于最小化問題，普通采取以下轉換形式：其中，cmax既能夠是到當前為止全部進化代中目標函數J(x)最大值（此時cmax將伴隨進化而有所改變），也能夠依據經驗人為設定。當其它4/25/202313北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第13頁

③對于最大化問題（如需要），普通采取以下轉換形式：其中，cmin既能夠是當前代中目標函數J(x)

最小值，也能夠依據經驗人為設定。

④采取以下指數函數形式：在最大化問題時，c普通取1.618或2；而在最小化問題時，c可取為0.618。這么，既確保了適應度值非負，又使適應度值增大方向和目標函數優(yōu)化方向一致。當其它4/25/202314北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第14頁（4）復制（選擇）（ReproductionorSelection）復制是基于適者生存理論而提出，是指種群中每一個體按照適應度函數進入到匹配池中過程。適應度值高于種群平均適應度個體在下一代中將有更多機會繁殖一個或多個后代，而低于平均適應度個體則有可能被淘汰掉。復制目標在于確保那些適應度高優(yōu)良個體在進化中生存下去，復制不會產生新個體。慣用復制方法有：①賭輪法②兩兩競爭法

從種群中隨機地選擇兩個個體，將其中適應度較大個體作為被復制個體；若兩個體適應度相同，則任意選擇一個。③排序法

首先依據目標函數值大小將個體排序，依據詳細問題應用各個體排序序號分配各自進入匹配池概率。適應度能夠按序號線性改變，也能夠按某種非線性關系改變。4/25/202315北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第15頁（5）交叉（Crossover）交叉是指對從匹配池中隨機選出兩個個體按一定交叉概率pc部分地交換一些基因過程。普通分兩步實現：第一步是將新復制產生匹配池中個體隨機兩兩配對；第二步是進行交叉繁殖，產生一對新個體。交叉目標是為了生成新個體，產生新基因組合，防止每代種群中個體重復。①單點交叉（One-PointCrossover）

對每一對相互配正確個體，依設定交叉概率pc在其交叉點處相互交換兩個父代個體部分染色體，從而產生出兩個新個體，以下列圖所表示。交叉前individual11100111001individual20101000110圖2單點交叉交叉后110010011001010110014/25/202316北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第16頁②兩點交叉（Two-PointCrossover）

按交叉概率隨機設置兩個交叉點，然后交換兩個父代個體在兩個交叉點之間基因。③均勻交叉（UniformCrossover）其操作過程是：先選出兩個父代個體，之后依據交叉概率pc產生一個與父代個體一樣長度二進制串，這里稱其為模板（template）。若模板中某位為0，則兩個父代個體對應位不進行交換；反之，模板中某位為1時，則交換兩個父代個體對應位基因。交叉前individual11101011000individual21010110101圖3兩點交叉交叉后111011000010010111014/25/202317北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第17頁④算數交叉（ArithmeticCrossover）算數交叉操作對象普通是由浮點數編碼所表示個體，它經過兩個父代個體線性組合而產生出兩個新個體。

假設在兩個父代個體，之間進行算數交叉，則交叉運算后所產生出兩個新個體是式中為一參數，它若是一個常數，此時所進行交叉運算稱為均勻算數交叉；它也能夠是一個由進化代數所決定變量，此時所進行交叉運算稱為非均勻算數交叉。交叉前individual10101100110template1001010101圖4均勻交叉individual20110010001交叉后010011001101110001004/25/202318北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第18頁（6）變異（Mutation）普通變異操作只作用于采取二進制編碼某單個個體，它以一定變異概率pm對個體一些位進行取反操作。如同自然界極少發(fā)生基因突變一樣，變異概率pm普通都取得比較小。變異目標是為了增加種群個體多樣性，預防丟失一些有用遺傳模式。在簡單遺傳算法中，變異就是將某個體中某一位值作取反運算。變異前1100110111圖5變異操作示意圖變異后11000101114/25/202319北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第19頁（7）收斂判據常規(guī)優(yōu)化方法有數學上比較嚴格收斂判據，而遺傳算法收斂判據通常是啟發(fā)式。因為遺傳算法沒有利用梯度信息，所以要從數學上結構比較嚴格收斂判據相當困難。慣用收斂判據有：

①依據計算時間和所采取計算機性能確定收斂判據：普通采取指定最大迭代次數方法；

②從解質量方面確定判據：假如連續(xù)幾代（或幾十代）種群中最優(yōu)解沒有改變，則認為算法收斂；或種群中最優(yōu)個體適應度與平均適應度之差和平均適應度比值小于某一給定值時，也能夠認為算法已經收斂。4/25/202320北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第20頁（8）約束條件處理遺傳算法在求解有約束優(yōu)化問題時，需對約束條件進行必要處理。處理方式有：①直接表達在字符串編碼中對于優(yōu)化問題中變量上、下限約束，能夠讓字符串表示最大值和最小值分別對應于實際約束變量上、下限值。設待優(yōu)化變量x改變范圍為[xmin,xmax]，如用l位二進制字符串y來表示，則x、y之間有以下關系：②判斷舍棄法

在遺傳算法運算過程中，檢驗得到字符串所對應解是否為可行解。若是，則加入到下一代種群中；不然將其舍棄。③處罰函數法

假如一個解違反了某個約束，則視其違反程度給予一定處罰，使其含有較小適應度。越限越嚴重，適應度就越小。4/25/202321北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第21頁1.3遺傳算法特點當前常規(guī)優(yōu)化方法主要有3種類型：解析法、枚舉法和隨機法。解析法是優(yōu)化方法中研究最多一個，它又分為直接法和間接法。直接法是一個經過沿著梯度信息最陡方向逐步運動來尋找局部極值方法；間接法則是一個經過使目標函數梯度為零，進而經過求解一組非線性方程來尋找局部極值方法。（1）解析法解析法主要問題在于：（1）要求目標函數連續(xù)光滑且可微；（2）普通只能找到局部極值而非全局極值，故對于存在多峰極值優(yōu)化問題有時顯得無能為力。4/25/202322北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第22頁隨機法能夠克服上述兩種方法缺點，它在搜索空間中隨機地漫游并統(tǒng)計下所找到最優(yōu)結果，當搜索到一定程度后便終止。當然，它所找到結果往往也不是最優(yōu)解。實際上，隨機法也是枚舉法中一個。（2）枚舉法枚舉法能夠克服解析法兩點不足，它能夠找到全局極值且不要求目標函數連續(xù)光滑。但其致命缺點是計算效率太低，對于許多實際問題往往會因為搜索空間太大而不可能將全部情況一一搜索到。（3）隨機法4/25/202323北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第23頁遺傳算法是基于自然選擇和基因遺傳學原理搜索方法，它將“優(yōu)勝劣汰、適者生存”生物進化原理引入到由待優(yōu)化參數形成編碼串種群中，按照一定適應度函數及一系列遺傳操作對各個個體進行篩選，使適應度值較高個體被保留下來，從而組成新種群，新種群中包含了上一代大量信息，而且引入了新優(yōu)于上一代個體。如此周而復始，種群中各個體適應度不停提升，直至滿足一定收斂條件。最終，以種群中適應度值最高個體作為待優(yōu)化參數最優(yōu)解。（4）遺傳算法遺傳算法也用到了隨機搜索技術，但它經過對參數空間隨機編碼并用適應度函數作為工具來引導搜索過程向著更有效方向發(fā)展，因而它不一樣于常規(guī)隨機法。4/25/202324北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第24頁與常規(guī)優(yōu)化方法相比，遺傳算法魯棒性很好，其主要特點在于：

①遺傳算法對參數編碼進行操作，而不是對參數本身；

②遺傳算法從多個初始點開始操作，而不是從某一個點開始，這在很大程度上防止了搜索過程過早地收斂于局部極值，所以更有可能求得全局極值；

③遺傳算法經過目標函數計算適應度，它不需要其它推導運算和附加信息，因而對問題依賴性??；

④遺傳算法使用概率操作規(guī)則，而不是確定性規(guī)則；

⑤遺傳算法在解空間中采取啟發(fā)式搜索，而不是盲目標枚舉或完全隨機搜索，因而搜索效率高；

⑥遺傳算法對于待尋優(yōu)問題基本沒有限制，既能夠是數學解析式所表示顯函數，也能夠是映射矩陣或神經網絡表示隱函數，同時也不要求待優(yōu)化函數連續(xù)、可微；4/25/202325北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第25頁

⑦遺傳算法所含有隱含并行性特點，使其能夠經過大規(guī)模并行搜索來提升計算速度；

⑧遺傳算法適合復雜、高度非線性問題優(yōu)化。1.4遺傳算法研究熱點（1）編碼方式確實定；（2）專用遺傳算子設計；（3）控制參數選擇；①種群規(guī)模：N=20~100；②交叉概率：pc=0.60~0.95；③變異概率：pm=0.001~0.01。李擎、張偉、尹怡欣、王志良．一個新調整交叉和變異概率自適應算法．控制與決議，年1月第23卷第1期：79～834/25/202326北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第26頁2遺傳算法應用實例——車載導航系統(tǒng)路徑規(guī)劃算法設計2.1問題介紹所謂車載導航系統(tǒng)路徑規(guī)劃，就是在電子地圖中找到一條從起點到終點在距離（或時間）上最短路徑。下列圖為一個路徑規(guī)劃用仿真地圖，其上共有15個節(jié)點，24條弧?；∠聰祿硎韭窂介L度（單位：公里），弧上數據則表示該路段車輛行駛速度（單位：米/秒）。在實際電子地圖中，節(jié)點相當于道路交叉點，弧相當于實際道路。4/25/202327北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第27頁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ī)劃用仿真地圖4/25/202328北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第28頁2.2遺傳算法詳細應用（1）路徑表示方法這里采取符號編碼方式表示實際路網中路徑。對于圖6中一條從A點到P點路徑，采取符號編碼方式得到個體為A、B、E、H、L、O、P。圖7仿真地圖中一條路徑ABEHLOP4/25/202329北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第29頁（2）初始路徑產生①傳統(tǒng)遺傳算法

隨機生成初始路徑，會產生斷路或環(huán)路。②改進遺傳算法（a）克服斷路思緒從起始點出發(fā)，隨機選取與起始點直接相連一個點作為下一個節(jié)點，如此重復直到找到終點為止。在路徑產生過程中為了防止出現環(huán)路，要求在一條路徑中當一個路徑節(jié)點被選中以后，則給該節(jié)點一個標識，只有沒有標識節(jié)點才能被選作新路徑節(jié)點，每條初始路徑選擇完成后標識全部刷新。

（b）克服環(huán)路思緒4/25/202330北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第30頁（3）適應度函數確實定①距離最短優(yōu)化標準下適應度函數②時間最優(yōu)優(yōu)化標準下適應度函數其中，為第i個染色體（路徑）；為第i條路徑第j段路徑長度。其中，仍為第i條路徑第j段路徑長度；為第i條路徑第j段行駛速度。4/25/202331北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第31頁不能象傳統(tǒng)遺傳算法那樣隨機進行一點、兩點或多點交叉操作，因為這么很輕易產生斷路或環(huán)路。這里只允許使用在重復節(jié)點位置交叉且只進行一點交叉操作方式，詳細實現步驟以下：（5）交叉操作（4）復制（選擇）操作采取賭輪法進行復制操作。①隨機選取兩個個體作為待交叉?zhèn)€體；②找出兩個待交叉?zhèn)€體共同節(jié)點（起點和終點除外）集合；③從共同節(jié)點集合中隨機選擇一個節(jié)點作為交叉節(jié)點；④檢驗兩個待交叉?zhèn)€體在交叉節(jié)點之前或之后內容是否相同。如相同，則取消此次交叉操作；不然，二者交換交叉點之前（或之后）內容形成兩個新個體。4/25/202332北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第32頁下面將結合仿真地圖舉例說明交叉操作是怎樣實現。

①設選取兩個待交叉樣本為A、B、E、I、L、O、P和A、C、E、H、L、N、P；

②二者重復節(jié)點集合為{E、L}；

③隨機選擇E作為交叉節(jié)點；

④檢驗發(fā)覺二者待交叉樣本在E點之前和之后內容均不相同，所以能夠進行此次交叉操作，交叉后新個體為：A、B、E、H、L、N、PA、C、E、I、L、O、P和4/25/202333北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第33頁圖8交叉操作示意圖PLOCBHIAEN4/25/202334北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第34頁（6）變異操作不能采取傳統(tǒng)遺傳算法中隨機選擇變異點做法，因為這么一樣輕易產生斷路或環(huán)路。這里采取變異操作，其基本步驟以下：①隨機選取一個個體作為待變異個體；②在待變異個體中隨機選擇一個節(jié)點（起點和終點除外）作為待變異節(jié)點；③找到和該待變異節(jié)點直接相連節(jié)點集合（該集合中不包含起點、終點以及待變異個體中節(jié)點）；④從節(jié)點集合中隨機選取一個節(jié)點作為變異后節(jié)點；⑤檢驗待變異節(jié)點之前和之后節(jié)點是否與變異后節(jié)點直接相連。若直接相連，則用變異后節(jié)點替換待變異節(jié)點完成變異過程；不然，放棄此次操作，回到第④步，直至將節(jié)點集合中全部節(jié)點全部選遍。4/25/202335北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第35頁現結合仿真地圖舉例說明變異操作詳細實現方法。①選擇待變異個體為A、C、E、I、L、O、P；⑤經過檢驗發(fā)覺C和B不直接相連，所以取消此次變異操作；接著選取F作為變異后節(jié)點，檢驗發(fā)覺C和F、F和I直接相連，故可進行此次變異操作，變異后新個體為②隨機選取E作為待變異節(jié)點；③與E直接相連節(jié)點集合為{B、F、H}；④隨機選取B作為變異后節(jié)點；A、C、F、I、L、O、P4/25/202336北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第36頁PLOFCBHIAE圖9變異操作示意圖4/25/202337北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第37頁（7）刪除操作刪除操作詳細步驟以下：

①隨機選擇一個個體；

②檢驗該個體中任意兩個不相鄰節(jié)點（包含起點和終點）之間是否直接相連。假如直接相連，則刪除兩個節(jié)點之間全部節(jié)點，結束此次刪除操作；不然，取消此次刪除操作。

下面也結合仿真地圖舉例說明刪除操作詳細實現方法。①設隨機選擇個體為A、C、E、F、I、L、O、P；②檢驗發(fā)覺E、I直接相連，則刪除二者之間節(jié)點F，從而得到新個體A、C、E、I、L、O、P4/25/202338北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第38頁PLOFCIAE圖10刪除操作示意圖4/25/202339北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第39頁（8）仿真結果①初始種群33.5A、B、D、H、E、I、F、J、M、O、P1021.3A、C、F、I、M、O、P919.2A、B、E、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初始種群及其距離4/25/202340北京科技大學自動化學院控制科學與工程系遺傳算法及其在路徑規(guī)劃中的應用專家講座第40頁②基于距離最短標準優(yōu)化結果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、P618