遺傳算法及其在路徑規(guī)劃中的應(yīng)用演示文稿

遺傳算法及其在路徑規(guī)劃中的應(yīng)用演示文稿第一頁(yè)，共四十七頁(yè)。遺傳算法及其在路徑規(guī)劃中的應(yīng)用第二頁(yè)，共四十七頁(yè)。參考書目：（1）周德儉，吳斌.智能控制.重慶：重慶大學(xué)出版社，2005（2）李少遠(yuǎn)，王景成.智能控制.北京：機(jī)械工業(yè)出版社，2005（3）李人厚.智能控制理論和方法.西安：西安電子科技大學(xué)出版社，1999（4）王順晃，舒迪前.智能控制系統(tǒng)及其應(yīng)用（第二版）.北京：機(jī)械工業(yè)出版社，2005第三頁(yè)，共四十七頁(yè)。20世紀(jì)60年代，美、德等國(guó)家的一些科學(xué)家開始模仿生物和人類進(jìn)化的方法來求解復(fù)雜優(yōu)化問題，從而形成了模擬進(jìn)化優(yōu)化方法（OptimizationMethodbySimulatedEvolution），其代表性方法有遺傳算法（GA：GeneticAlgorithms）、進(jìn)化規(guī)劃（EP：EvolutionaryProgramming）、進(jìn)化策略（ES：EvolutionaryStrategies）。本講將主要對(duì)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)化問題。由于它們采用隨機(jī)優(yōu)化技術(shù)，所以會(huì)以較大的概率求得全局最優(yōu)解。其計(jì)算費(fèi)用較高的問題也因計(jì)算機(jī)軟硬件技術(shù)的飛速發(fā)展而不再成為制約因素。1遺傳算法產(chǎn)生的背景第四頁(yè)，共四十七頁(yè)。1.1遺傳算法的基本概念1.1.1進(jìn)化的基本理論（1）Darwin生物進(jìn)化論（2）Mendel自然遺傳學(xué)說1.1.2遺傳算法術(shù)語簡(jiǎn)介（1）個(gè)體（染色體）：遺傳算法求解實(shí)際問題時(shí)，首先對(duì)待優(yōu)化問題的參數(shù)進(jìn)行編碼（一般采用二進(jìn)制碼串表示），從而得到一個(gè)字符串，該字符串被稱為一個(gè)個(gè)體（individual）或一個(gè)染色體（chromosome）。（2）種群（群體）：所有個(gè)體的集合（population）。（3）種群規(guī)模：種群中個(gè)體的數(shù)量稱為種群規(guī)模（populationsize）。（4）基因：個(gè)體中的每一位稱為一個(gè)基因（gene）。（5）適應(yīng)度函數(shù)：能夠評(píng)價(jià)個(gè)體對(duì)環(huán)境適應(yīng)能力的函數(shù)（fitnessfunction）。第五頁(yè)，共四十七頁(yè)。1.1.3遺傳算法應(yīng)用引例例：求的最大值。解：（1）編碼方式的確定采用五位二進(jìn)制代碼表示變量x。表1產(chǎn)生的初始種群標(biāo)號(hào)初始種群x值1011011321100024301000841001119（2）初始種群的產(chǎn)生設(shè)種群規(guī)模N=4，隨機(jī)產(chǎn)生初始種群如表1所示。第六頁(yè)，共四十七頁(yè)。（3）適應(yīng)度函數(shù)值的計(jì)算取適應(yīng)度函數(shù)為f(x)=x2，則4個(gè)樣本的適應(yīng)度值分別如下表所示。表2適應(yīng)度函數(shù)計(jì)算標(biāo)號(hào)初始種群適應(yīng)度值f(x)=x210110116921100057630100064410011361總計(jì)1170平均值292.5最大值576x值1324819第七頁(yè)，共四十七頁(yè)。（4）復(fù)制采用賭輪法計(jì)算各個(gè)個(gè)體被復(fù)制的次數(shù)。表3復(fù)制操作過程標(biāo)號(hào)初始種群適應(yīng)度f(x)=x210110116921100057630100064410011361總計(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.971201412第八頁(yè)，共四十七頁(yè)。（5）交叉采用隨機(jī)交叉配對(duì)，一點(diǎn)交叉方式進(jìn)行交叉。表4交叉操作過程標(biāo)號(hào)復(fù)制后匹配池中的個(gè)體1011013211000431100014100112總計(jì)平均值最大值新種群01000110011110110010f(x)=x235358252918646258413241854463.5841配對(duì)對(duì)象（隨機(jī)選取）交叉點(diǎn)（隨機(jī)選?。﹛值第九頁(yè)，共四十七頁(yè)。（6）變異采用單點(diǎn)隨機(jī)變異方式進(jìn)行變異操作。表5變異操作過程標(biāo)號(hào)交叉后的種群101000211001311101410010總計(jì)平均值最大值新種群01100110011110110010f(x)=x23///122529181446258413241934483.5841變異點(diǎn)位置x值第十頁(yè)，共四十七頁(yè)。1.2遺傳算法的基本步驟1.2.1遺傳算法的流程確定表示問題解的編碼隨機(jī)生成初始種群確定適應(yīng)度函數(shù)f計(jì)算種群中各個(gè)體的適應(yīng)度fi選擇高適應(yīng)度的個(gè)體進(jìn)行復(fù)制交叉變異輸出最優(yōu)解是否滿足收斂判據(jù)？是否圖1遺傳算法的基本流程圖第十一頁(yè)，共四十七頁(yè)。1.2.2遺傳算法的具體實(shí)現(xiàn)（1）編碼方式的選取利用遺傳算法求解實(shí)際問題時(shí)，問題的解是用字符串來表示的，遺傳算子也是直接對(duì)字符串進(jìn)行操作的。因此，如何用適當(dāng)?shù)淖址幋a來表示問題的解成為了遺傳算法應(yīng)用過程中的首要問題。目前所使用的字符串編碼方式主要有：二進(jìn)制、實(shí)數(shù)（浮點(diǎn)數(shù)）和符號(hào)等。（1）采用二進(jìn)制形式編碼，個(gè)體的位數(shù)多，描述得比較細(xì)致，從而加大了搜索范圍；但交叉運(yùn)算的計(jì)算量較大，并且由于大量的具體問題本身都是十進(jìn)制的，所以還需對(duì)實(shí)際參數(shù)進(jìn)行編碼和譯碼，從而增加了額外的計(jì)算時(shí)間。（2）采用實(shí)數(shù)（浮點(diǎn)數(shù)）編碼，交叉運(yùn)算的計(jì)算量較小，但變異過程難于進(jìn)行。（3）符號(hào)編碼方式通常在一些專門的應(yīng)用場(chǎng)合使用。第十二頁(yè)，共四十七頁(yè)。（2）初始種群的產(chǎn)生初始種群對(duì)應(yīng)著問題的初始解，通常有兩種方式產(chǎn)生：

①完全隨機(jī)方式產(chǎn)生（字符串每一位均隨機(jī)產(chǎn)生）；

②隨機(jī)數(shù)發(fā)生器方式產(chǎn)生（整個(gè)字符串用隨機(jī)數(shù)發(fā)生器一次產(chǎn)生）。

另外，如果對(duì)于尋優(yōu)問題有某些先驗(yàn)知識(shí)，則可先將這些先驗(yàn)知識(shí)轉(zhuǎn)變?yōu)楸仨殱M足的一組約束，然后再在滿足這些約束的解中隨機(jī)地選取個(gè)體以組成初始種群。（3）適應(yīng)度函數(shù)的確定適應(yīng)度函數(shù)是遺傳算法與實(shí)際優(yōu)化問題之間的接口。在遺傳算法中要求適應(yīng)度函數(shù)值是非負(fù)的，且任何情況下都希望其值越大越好；而實(shí)際優(yōu)化問題的目標(biāo)函數(shù)并不一定滿足這個(gè)條件，有的是正的，有的可能為負(fù)，甚至可能是復(fù)數(shù)值。因此，對(duì)于任意優(yōu)化問題，首先應(yīng)把其數(shù)學(xué)形式表示為遺傳算法適于求解的形式，同時(shí)要保證二者在數(shù)學(xué)優(yōu)化層面上是等價(jià)的。這個(gè)過程稱為適應(yīng)度轉(zhuǎn)換。第十三頁(yè)，共四十七頁(yè)。適應(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)度函數(shù)為f(x)，則有：

①可以將適應(yīng)度函數(shù)表示為實(shí)際優(yōu)化問題目標(biāo)函數(shù)的線性形式，即有其中，a，b是系數(shù)，可根據(jù)具體問題的特征及所期望適應(yīng)度的分散程度來確定。

②對(duì)于最小化問題，一般采用如下轉(zhuǎn)換形式：其中，cmax既可以是到目前為止所有進(jìn)化代中目標(biāo)函數(shù)J(x)的最大值（此時(shí)cmax將隨著進(jìn)化而有所變化），也可以根據(jù)經(jīng)驗(yàn)人為設(shè)定。當(dāng)其它第十四頁(yè)，共四十七頁(yè)。

③對(duì)于最大化問題（如需要），一般采用如下轉(zhuǎn)換形式：其中，cmin既可以是當(dāng)前代中目標(biāo)函數(shù)J(x)

的最小值，也可以根據(jù)經(jīng)驗(yàn)人為設(shè)定。

④采用如下的指數(shù)函數(shù)形式：在最大化問題時(shí)，c一般取1.618或2；而在最小化問題時(shí)，c可取為0.618。這樣，既保證了適應(yīng)度值非負(fù)，又使適應(yīng)度值增大方向和目標(biāo)函數(shù)優(yōu)化方向一致。當(dāng)其它第十五頁(yè)，共四十七頁(yè)。（4）復(fù)制（選擇）（ReproductionorSelection）復(fù)制是基于適者生存理論而提出的，是指種群中每一個(gè)體按照適應(yīng)度函數(shù)進(jìn)入到匹配池中的過程。適應(yīng)度值高于種群平均適應(yīng)度的個(gè)體在下一代中將有更多的機(jī)會(huì)繁殖一個(gè)或多個(gè)后代，而低于平均適應(yīng)度的個(gè)體則有可能被淘汰掉。復(fù)制的目的在于保證那些適應(yīng)度高的優(yōu)良個(gè)體在進(jìn)化中生存下去，復(fù)制不會(huì)產(chǎn)生新的個(gè)體。常用的復(fù)制方法有：①賭輪法②兩兩競(jìng)爭(zhēng)法

從種群中隨機(jī)地選擇兩個(gè)個(gè)體，將其中適應(yīng)度較大的個(gè)體作為被復(fù)制的個(gè)體；若兩個(gè)體適應(yīng)度相同，則任意選擇一個(gè)。③排序法

首先根據(jù)目標(biāo)函數(shù)值的大小將個(gè)體排序，根據(jù)具體問題應(yīng)用各個(gè)體的排序序號(hào)分配各自進(jìn)入匹配池的概率。適應(yīng)度可以按序號(hào)線性變化，也可以按某種非線性關(guān)系變化。第十六頁(yè)，共四十七頁(yè)。（5）交叉（Crossover）交叉是指對(duì)從匹配池中隨機(jī)選出的兩個(gè)個(gè)體按一定的交叉概率pc部分地交換某些基因的過程。一般分兩步實(shí)現(xiàn)：第一步是將新復(fù)制產(chǎn)生的匹配池中的個(gè)體隨機(jī)兩兩配對(duì)；第二步是進(jìn)行交叉繁殖，產(chǎn)生一對(duì)新的個(gè)體。交叉的目的是為了生成新的個(gè)體，產(chǎn)生新的基因組合，避免每代種群中個(gè)體的重復(fù)。①單點(diǎn)交叉（One-PointCrossover）

對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)父代個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體，如下圖所示。交叉前individual11100111001individual20101000110圖2單點(diǎn)交叉交叉后11001001100101011001第十七頁(yè)，共四十七頁(yè)。②兩點(diǎn)交叉（Two-PointCrossover）

按交叉概率隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，然后交換兩個(gè)父代個(gè)體在兩個(gè)交叉點(diǎn)之間的基因。③均勻交叉（UniformCrossover）其操作過程是：先選出兩個(gè)父代個(gè)體，之后依據(jù)交叉概率pc產(chǎn)生一個(gè)與父代個(gè)體同樣長(zhǎng)度的二進(jìn)制串，這里稱其為模板（template）。若模板中的某位為0，則兩個(gè)父代個(gè)體對(duì)應(yīng)位不進(jìn)行交換；反之，模板中的某位為1時(shí)，則交換兩個(gè)父代個(gè)體對(duì)應(yīng)位的基因。交叉前individual11101011000individual21010110101圖3兩點(diǎn)交叉交叉后11101100001001011101第十八頁(yè)，共四十七頁(yè)。④算數(shù)交叉（ArithmeticCrossover）算數(shù)交叉的操作對(duì)象一般是由浮點(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ù)交叉。交叉前individual10101100110template1001010101圖4均勻交叉individual20110010001交叉后01001100110111000100第十九頁(yè)，共四十七頁(yè)。（6）變異（Mutation）一般的變異操作只作用于采用二進(jìn)制編碼的某單個(gè)個(gè)體，它以一定的變異概率pm對(duì)個(gè)體的某些位進(jìn)行取反操作。如同自然界很少發(fā)生基因突變一樣，變異概率pm一般都取得比較小。變異的目的是為了增加種群個(gè)體的多樣性，防止丟失一些有用的遺傳模式。在簡(jiǎn)單遺傳算法中，變異就是將某個(gè)體中某一位的值作取反運(yùn)算。變異前1100110111圖5變異操作示意圖變異后1100010111第二十頁(yè)，共四十七頁(yè)。（7）收斂判據(jù)常規(guī)的優(yōu)化方法有數(shù)學(xué)上比較嚴(yán)格的收斂判據(jù)，而遺傳算法的收斂判據(jù)通常是啟發(fā)式的。由于遺傳算法沒有利用梯度信息，因此要從數(shù)學(xué)上構(gòu)造比較嚴(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)收斂。第二十一頁(yè)，共四十七頁(yè)。（8）約束條件的處理遺傳算法在求解有約束的優(yōu)化問題時(shí)，需對(duì)約束條件進(jìn)行必要的處理。處理方式有：①直接體現(xiàn)在字符串的編碼中對(duì)于優(yōu)化問題中變量的上、下限約束，可以讓字符串表示的最大值和最小值分別對(duì)應(yīng)于實(shí)際約束變量的上、下限值。設(shè)待優(yōu)化變量x的變化范圍為[xmin,xmax]，如用l位的二進(jìn)制字符串y來表示，則x、y之間有如下關(guān)系：②判斷舍棄法

在遺傳算法的運(yùn)算過程中，檢查得到字符串所對(duì)應(yīng)的解是否為可行解。若是，則加入到下一代種群中；否則將其舍棄。③懲罰函數(shù)法

如果一個(gè)解違反了某個(gè)約束，則視其違反程度給予一定的懲罰，使其具有較小的適應(yīng)度。越限越嚴(yán)重，適應(yīng)度就越小。第二十二頁(yè)，共四十七頁(yè)。1.3遺傳算法的特點(diǎn)目前常規(guī)的優(yōu)化方法主要有3種類型：解析法、枚舉法和隨機(jī)法。解析法是優(yōu)化方法中研究最多的一種，它又分為直接法和間接法。直接法是一種通過沿著梯度信息最陡的方向逐漸運(yùn)動(dòng)來尋找局部極值的方法；間接法則是一種通過使目標(biāo)函數(shù)梯度為零，進(jìn)而通過求解一組非線性方程來尋找局部極值的方法。（1）解析法解析法的主要問題在于：（1）要求目標(biāo)函數(shù)連續(xù)光滑且可微；（2）一般只能找到局部極值而非全局極值，故對(duì)于存在多峰極值的優(yōu)化問題有時(shí)顯得無能為力。第二十三頁(yè)，共四十七頁(yè)。隨機(jī)法能夠克服上述兩種方法的缺陷，它在搜索空間中隨機(jī)地漫游并記錄下所找到的最優(yōu)結(jié)果，當(dāng)搜索到一定程度后便終止。當(dāng)然，它所找到的結(jié)果往往也不是最優(yōu)解。實(shí)際上，隨機(jī)法也是枚舉法中的一種。（2）枚舉法枚舉法能夠克服解析法的兩點(diǎn)不足，它可以找到全局極值且不要求目標(biāo)函數(shù)連續(xù)光滑。但其致命缺點(diǎn)是計(jì)算效率太低，對(duì)于許多實(shí)際問題往往會(huì)因?yàn)樗阉骺臻g太大而不可能將所有的情況一一搜索到。（3）隨機(jī)法第二十四頁(yè)，共四十七頁(yè)。遺傳算法是基于自然選擇和基因遺傳學(xué)原理的搜索方法，它將“優(yōu)勝劣汰、適者生存”的生物進(jìn)化原理引入到由待優(yōu)化參數(shù)形成的編碼串種群中，按照一定的適應(yīng)度函數(shù)及一系列遺傳操作對(duì)各個(gè)個(gè)體進(jìn)行篩選，使適應(yīng)度值較高的個(gè)體被保留下來，從而組成新的種群，新種群中包含了上一代的大量信息，并且引入了新的優(yōu)于上一代的個(gè)體。如此周而復(fù)始，種群中各個(gè)體的適應(yīng)度不斷提高，直至滿足一定的收斂條件。最后，以種群中適應(yīng)度值最高的個(gè)體作為待優(yōu)化參數(shù)的最優(yōu)解。（4）遺傳算法遺傳算法也用到了隨機(jī)搜索技術(shù)，但它通過對(duì)參數(shù)空間的隨機(jī)編碼并用適應(yīng)度函數(shù)作為工具來引導(dǎo)搜索過程向著更有效的方向發(fā)展，因而它不同于常規(guī)的隨機(jī)法。第二十五頁(yè)，共四十七頁(yè)。與常規(guī)優(yōu)化方法相比，遺傳算法的魯棒性較好，其主要特點(diǎn)在于：

①遺傳算法對(duì)參數(shù)的編碼進(jìn)行操作，而不是對(duì)參數(shù)本身；

②遺傳算法從多個(gè)初始點(diǎn)開始操作，而不是從某一個(gè)點(diǎn)開始，這在很大程度上避免了搜索過程過早地收斂于局部極值，因此更有可能求得全局極值；

③遺傳算法通過目標(biāo)函數(shù)計(jì)算適應(yīng)度，它不需要其它的推導(dǎo)運(yùn)算和附加信息，因而對(duì)問題的依賴性小；

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

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

⑥遺傳算法對(duì)于待尋優(yōu)的問題基本沒有限制，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，也可以是映射矩陣或神經(jīng)網(wǎng)絡(luò)表示的隱函數(shù)，同時(shí)也不要求待優(yōu)化函數(shù)連續(xù)、可微；第二十六頁(yè)，共四十七頁(yè)。

⑦遺傳算法所具有的隱含并行性的特點(diǎn)，使其可以通過大規(guī)模并行搜索來提高計(jì)算速度；

⑧遺傳算法適合復(fù)雜的、高度非線性問題的優(yōu)化。1.4遺傳算法的研究熱點(diǎn)（1）編碼方式的確定；（2）專用遺傳算子的設(shè)計(jì)；（3）控制參數(shù)的選擇；①種群規(guī)模：N=20~100；②交叉概率：pc=0.60~0.95；③變異概率：pm=0.001~0.01。李擎、張偉、尹怡欣、王志良．一種新的調(diào)節(jié)交叉和變異概率的自適應(yīng)算法．控制與決策，2008年1月第23卷第1期：79～83第二十七頁(yè)，共四十七頁(yè)。2遺傳算法的應(yīng)用實(shí)例——車載導(dǎo)航系統(tǒng)路徑規(guī)劃算法的設(shè)計(jì)2.1問題簡(jiǎn)介所謂車載導(dǎo)航系統(tǒng)路徑規(guī)劃，就是在電子地圖中找到一條從起點(diǎn)到終點(diǎn)在距離（或時(shí)間）上最短的路徑。下圖為一個(gè)路徑規(guī)劃用仿真地圖，其上共有15個(gè)節(jié)點(diǎn)，24條弧。弧下的數(shù)據(jù)表示路徑的長(zhǎng)度（單位：公里），弧上的數(shù)據(jù)則表示該路段車輛行駛的速度（單位：米/秒）。在實(shí)際電子地圖中，節(jié)點(diǎn)相當(dāng)于道路的交叉點(diǎn)，弧相當(dāng)于實(shí)際道路。第二十八頁(yè)，共四十七頁(yè)。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ī)劃用仿真地圖第二十九頁(yè)，共四十七頁(yè)。2.2遺傳算法的具體應(yīng)用（1）路徑的表示方法這里采用符號(hào)編碼方式表示實(shí)際路網(wǎng)中的路徑。對(duì)于圖6中一條從A點(diǎn)到P點(diǎn)的路徑，采用符號(hào)編碼方式得到的個(gè)體為A、B、E、H、L、O、P。圖7仿真地圖中的一條路徑ABEHLOP第三十頁(yè)，共四十七頁(yè)。（2）初始路徑的產(chǎn)生①傳統(tǒng)遺傳算法

隨機(jī)生成初始路徑，會(huì)產(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)路，規(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)路的思路第三十一頁(yè)，共四十七頁(yè)。（3）適應(yīng)度函數(shù)的確定①距離最短優(yōu)化原則下的適應(yīng)度函數(shù)②時(shí)間最優(yōu)優(yōu)化原則下的適應(yīng)度函數(shù)其中，為第i個(gè)染色體（路徑）；為第i條路徑第j段的路徑長(zhǎng)度。其中，仍為第i條路徑第j段的路徑長(zhǎng)度；為第i條路徑第j段的行駛速度。第三十二頁(yè)，共四十七頁(yè)。不能象傳統(tǒng)遺傳算法那樣隨機(jī)進(jìn)行一點(diǎn)、兩點(diǎn)或多點(diǎn)交叉操作，因?yàn)檫@樣很容易產(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è)體。第三十三頁(yè)，共四十七頁(yè)。下面將結(jié)合仿真地圖舉例說明交叉操作是如何實(shí)現(xiàn)的。

①設(shè)選取的兩個(gè)待交叉樣本為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和第三十四頁(yè)，共四十七頁(yè)。圖8交叉操作示意圖PLOCBHIAEN第三十五頁(yè)，共四十七頁(yè)。（6）變異操作不能采用傳統(tǒng)遺傳算法中隨機(jī)選擇變異點(diǎn)的做法，因?yàn)檫@樣同樣容易產(chǎn)生斷路或環(huán)路。這里采用的變異操作，其基本步驟如下：①隨機(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)全部選遍。第三十六頁(yè)，共四十七頁(yè)?，F(xiàn)結(jié)合仿真地圖舉例說明變異操作的具體實(shí)現(xiàn)方法。①選擇待變異個(gè)體為A、C、E、I、L、O、P；⑤經(jīng)過檢查發(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、P第三十七頁(yè)，共四十七頁(yè)。PLOFCBHIAE圖9變異操作示意圖第三十八頁(yè)，共四十七頁(yè)。（7）刪除操作刪除操作的具體步驟如下：

①隨機(jī)選擇一個(gè)個(gè)體；

②檢查該個(gè)體中任意兩個(gè)不相鄰節(jié)點(diǎn)（包括起點(diǎn)和終點(diǎn)）之間是否直接相連。如果直接相連，則刪除兩個(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、P第三十九頁(yè)，共四十七頁(yè)。PLOFCIAE圖10刪除操作示意圖第四十頁(yè)，共四十七頁(yè)。（8）仿真結(jié)果①初始種群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