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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、段車輛行駛的速度（單位：米/秒）。 在實(shí)際電子地圖中，節(jié)點(diǎn)相當(dāng)于道路的交叉點(diǎn)，弧相當(dāng)于實(shí)際道路。7/29/202227北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系第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北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系第28頁，共48頁。2.2 遺傳算法的具體應(yīng)用（1）路徑的表示方法 這里采用符號編碼方式表示實(shí)際路網(wǎng)中的路徑。 對于圖6中一條從A點(diǎn)到P點(diǎn)的路徑，采用符號編碼方式得到的個(gè)體為A、B、E、H、L、O、P。圖7 仿真地圖中的一條路徑ABEHLOP7/29/202229北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系第29頁，共48頁。（2）初始路徑的產(chǎn)生傳統(tǒng)遺傳算法 隨機(jī)生成初始路徑，會產(chǎn)生斷路或環(huán)路。改進(jìn)遺傳算法（a）克服斷路的思路 從起始點(diǎn)出發(fā)，隨機(jī)選取與起始點(diǎn)直接相連的一個(gè)點(diǎn)作為下一個(gè)節(jié)點(diǎn)，如此反復(fù)直到找到終點(diǎn)為止。 在路徑的產(chǎn)生過程中為了避免出現(xiàn)環(huán)路，

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

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

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

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

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

32、相連，則刪除兩個(gè)節(jié)點(diǎn)之間的所有節(jié)點(diǎn)，結(jié)束此次刪除操作；否則，取消本次刪除操作。 下面也結(jié)合仿真地圖舉例說明刪除操作的具體實(shí)現(xiàn)方法。 設(shè)隨機(jī)選擇的個(gè)體為A、C、E、F、I、L、O、P； 檢查發(fā)現(xiàn)E、I直接相連，則刪除兩者之間的節(jié)點(diǎn)F，從而得到新個(gè)體A、C、E、I、L、O、P7/29/202238北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系第38頁，共48頁。PLOFCIAE圖10 刪除操作示意圖7/29/202239北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系第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距離個(gè)體標(biāo)號表6 初始種群及其距離7/29/202240北京科技大學(xué)自動(dòng)化學(xué)院控制科學(xué)與工程系第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