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

1、3/7/2022.1遺傳算法及其在路徑規(guī)劃遺傳算法及其在路徑規(guī)劃中的應(yīng)用中的應(yīng)用北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系北京科技大學(xué)自動化學(xué)院控制科學(xué)與工程系3/7/2022.2參考書目：參考書目：（1）周德儉，吳斌）周德儉，吳斌. 智能控制智能控制. 重慶：重慶大學(xué)出重慶：重慶大學(xué)出版社，版社，2005（2）李少遠(yuǎn)，王景成）李少遠(yuǎn)，王景成. 智能控制智能控制. 北京：機(jī)械工業(yè)北京：機(jī)械工業(yè)出版社，出版社，2005（3）李人厚）李人厚. 智能控制理論和方法智能控制理論和方法. 西安：西安電西安：西安電子科技大學(xué)出版社，子科技大學(xué)出版社，1999（4）王順晃，舒迪前）王順晃，舒迪前. 智能控制系統(tǒng)

2、及其應(yīng)用（第智能控制系統(tǒng)及其應(yīng)用（第二版）二版）. 北京：機(jī)械工業(yè)出版社，北京：機(jī)械工業(yè)出版社，20053/7/2022.3 20世紀(jì)世紀(jì)60年代，美、德等國家的一些科學(xué)家開始模仿生物年代，美、德等國家的一些科學(xué)家開始模仿生物和人類進(jìn)化的方法來求解復(fù)雜優(yōu)化問題，從而形成了和人類進(jìn)化的方法來求解復(fù)雜優(yōu)化問題，從而形成了模擬進(jìn)化模擬進(jìn)化優(yōu)化方法優(yōu)化方法（Optimization Method by Simulated Evolution），），其代表性方法有遺傳算法（其代表性方法有遺傳算法（GA：Genetic Algorithms）、進(jìn)化）、進(jìn)化規(guī)劃（規(guī)劃（EP：Evolutionary Pro

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

4、由于它們采用隨機(jī)優(yōu)化技術(shù)，所以會以較大的線性優(yōu)化問題。由于它們采用隨機(jī)優(yōu)化技術(shù)，所以會以較大的概率求得全局最優(yōu)解。其計算費用較高的問題也因計算機(jī)軟硬概率求得全局最優(yōu)解。其計算費用較高的問題也因計算機(jī)軟硬件技術(shù)的飛速發(fā)展而不再成為制約因素。件技術(shù)的飛速發(fā)展而不再成為制約因素。1 遺傳算法產(chǎn)生的背景遺傳算法產(chǎn)生的背景3/7/2022.41.1 遺傳算法的基本概念遺傳算法的基本概念1.1.1 進(jìn)化的基本理論進(jìn)化的基本理論（1）Darwin生物進(jìn)化論生物進(jìn)化論（2）Mendel自然遺傳學(xué)說自然遺傳學(xué)說1.1.2 遺傳算法術(shù)語簡介遺傳算法術(shù)語簡介（1）個體（染色體）：遺傳算法求解實際問題時，首先對待）個

5、體（染色體）：遺傳算法求解實際問題時，首先對待優(yōu)化問題的優(yōu)化問題的參數(shù)參數(shù)進(jìn)行編碼（一般采用二進(jìn)制碼串表示），從而進(jìn)行編碼（一般采用二進(jìn)制碼串表示），從而得到一個字符串，該字符串被稱為一個個體（得到一個字符串，該字符串被稱為一個個體（individual ）或）或一個染色體（一個染色體（chromosome）。）。（2）種群（群體）：所有個體的集合（）種群（群體）：所有個體的集合（population）。）。（3）種群規(guī)模：種群中個體的數(shù)量稱為種群規(guī)模（）種群規(guī)模：種群中個體的數(shù)量稱為種群規(guī)模（population size）。）。（4）基因：個體中的每一位稱為一個基因（）基因：個體中的每一位

6、稱為一個基因（gene）。）。（5）適應(yīng)度函數(shù)：能夠評價個體對環(huán)境適應(yīng)能力的函數(shù)）適應(yīng)度函數(shù)：能夠評價個體對環(huán)境適應(yīng)能力的函數(shù)（fitness function）。）。3/7/2022.51.1.3 遺傳算法應(yīng)用引例遺傳算法應(yīng)用引例例：求例：求 的最大值。的最大值。2( ),0, 31f xxx解解：（：（1）編碼方式的確定）編碼方式的確定 采用五位二進(jìn)制代碼表示變量采用五位二進(jìn)制代碼表示變量x。表表1 產(chǎn)生的初始種群產(chǎn)生的初始種群標(biāo)號標(biāo)號初始種群初始種群x值值1011011321100024301000841001119 （2）初始種群的產(chǎn)生）初始種群的產(chǎn)生設(shè)種群規(guī)模設(shè)種群規(guī)模N=4，隨機(jī)產(chǎn)

7、生初始種群如表，隨機(jī)產(chǎn)生初始種群如表1所示。所示。3/7/2022.6（3）適應(yīng)度函數(shù)值的計算）適應(yīng)度函數(shù)值的計算 取適應(yīng)度函數(shù)為取適應(yīng)度函數(shù)為f (x)=x2，則，則4個樣本的適應(yīng)度值分別如下個樣本的適應(yīng)度值分別如下表所示。表所示。表表2 適應(yīng)度函數(shù)計算適應(yīng)度函數(shù)計算標(biāo)號標(biāo)號初始種群初始種群適應(yīng)度值適應(yīng)度值f (x)=x210110116921100057630100064410011361總總 計計1170平均值平均值292.5最大值最大值576x值值13248193/7/2022.7（4）復(fù)制）復(fù)制 采用賭輪法計算各個個體被復(fù)制的次數(shù)。采用賭輪法計算各個個體被復(fù)制的次數(shù)。表表3 復(fù)制操作

8、過程復(fù)制操作過程標(biāo)號標(biāo)號初始種群初始種群適應(yīng)度適應(yīng)度f (x)=x210110116921100057630100064410011361總總 計計1170平均值平均值292.5最大值最大值576x值值1324819復(fù)制概率復(fù)制概率期望的復(fù)制期望的復(fù)制數(shù)數(shù)實際得到實際得到的復(fù)制數(shù)的復(fù)制數(shù)0.1440.4920.0550.3091.0000.250.4920.581.970.221.234.001.001.971201412iiffiiff3/7/2022.8（5）交叉）交叉 采用隨機(jī)交叉配對，一點交叉方式進(jìn)行交叉。采用隨機(jī)交叉配對，一點交叉方式進(jìn)行交叉。表表4 交叉操作過程交叉操作過程標(biāo)號標(biāo)號

9、復(fù)制后匹配復(fù)制后匹配池中的個體池中的個體1011013211000431100014100112總總 計計平均值平均值最大值最大值新種群新種群01000110011110110010f (x)=x235358252918646258413241854463.5841配對對象配對對象（隨機(jī)選?。S機(jī)選?。┙徊纥c交叉點（隨機(jī)選?。S機(jī)選取）x值值3/7/2022.9（6）變異）變異 采用單點隨機(jī)變異方式進(jìn)行變異操作。采用單點隨機(jī)變異方式進(jìn)行變異操作。表表5 變異操作過程變異操作過程標(biāo)號標(biāo)號交叉后交叉后的種群的種群101000211001311101410010總總 計計平均值平均值最大值最大值

10、新種群新種群01100110011110110010f (x)=x23/122529181446258413241934483.5841變異點位置變異點位置x值值3/7/2022.101.2 遺傳算法的基本步驟遺傳算法的基本步驟1.2.1 遺傳算法的流程遺傳算法的流程確定表示問題解的編碼確定表示問題解的編碼隨機(jī)生成初始種群隨機(jī)生成初始種群確定適應(yīng)度函數(shù)確定適應(yīng)度函數(shù)f計算種群中各個體的適應(yīng)度計算種群中各個體的適應(yīng)度 fi選擇高適應(yīng)度的個體進(jìn)行復(fù)制選擇高適應(yīng)度的個體進(jìn)行復(fù)制交叉交叉變異變異輸出最優(yōu)解輸出最優(yōu)解是否滿足收斂判據(jù)？是否滿足收斂判據(jù)？是是否否圖圖1 遺傳算法的基本流程圖遺傳算法的基本流

11、程圖3/7/2022.111.2.2 遺傳算法的具體實現(xiàn)遺傳算法的具體實現(xiàn)（1）編碼方式的選?。┚幋a方式的選取 利用遺傳算法求解實際問題時，問題的解是用字符串來表利用遺傳算法求解實際問題時，問題的解是用字符串來表示的，示的，遺傳算子也是直接對字符串進(jìn)行操作的遺傳算子也是直接對字符串進(jìn)行操作的。因此，如何用。因此，如何用適當(dāng)?shù)淖址幋a來表示問題的解成為了遺傳算法應(yīng)用過程中適當(dāng)?shù)淖址幋a來表示問題的解成為了遺傳算法應(yīng)用過程中的首要問題。的首要問題。 目前所使用的字符串編碼方式主要有：目前所使用的字符串編碼方式主要有：二進(jìn)制、實數(shù)（浮二進(jìn)制、實數(shù)（浮點數(shù)）和符號點數(shù)）和符號等。等。 （1）采用二

12、進(jìn)制形式編碼，個體的位數(shù)多，描述得比較）采用二進(jìn)制形式編碼，個體的位數(shù)多，描述得比較細(xì)致，從而加大了搜索范圍；但交叉運算的計算量較大，并且細(xì)致，從而加大了搜索范圍；但交叉運算的計算量較大，并且由于大量的具體問題本身都是十進(jìn)制的，所以還需對實際參數(shù)由于大量的具體問題本身都是十進(jìn)制的，所以還需對實際參數(shù)進(jìn)行編碼和譯碼，從而增加了額外的計算時間。進(jìn)行編碼和譯碼，從而增加了額外的計算時間。 （2）采用實數(shù)（浮點數(shù)）編碼，交叉運算的計算量較小，）采用實數(shù)（浮點數(shù)）編碼，交叉運算的計算量較小，但變異過程難于進(jìn)行。但變異過程難于進(jìn)行。 （3）符號編碼方式通常在一些專門的應(yīng)用場合使用。）符號編碼方式通常在一些

13、專門的應(yīng)用場合使用。3/7/2022.12（2）初始種群的產(chǎn)生）初始種群的產(chǎn)生 初始種群對應(yīng)著問題的初始解，通常有兩種方式產(chǎn)生：初始種群對應(yīng)著問題的初始解，通常有兩種方式產(chǎn)生： 完全隨機(jī)方式產(chǎn)生（字符串每一位均隨機(jī)產(chǎn)生）；完全隨機(jī)方式產(chǎn)生（字符串每一位均隨機(jī)產(chǎn)生）； 隨機(jī)數(shù)發(fā)生器方式產(chǎn)生（整個字符串用隨機(jī)數(shù)發(fā)生器一隨機(jī)數(shù)發(fā)生器方式產(chǎn)生（整個字符串用隨機(jī)數(shù)發(fā)生器一次產(chǎn)生）。次產(chǎn)生）。 另外，如果對于尋優(yōu)問題有某些先驗知識，則可先將這些另外，如果對于尋優(yōu)問題有某些先驗知識，則可先將這些先驗知識轉(zhuǎn)變?yōu)楸仨殱M足的一組約束，然后再在滿足這些約束先驗知識轉(zhuǎn)變?yōu)楸仨殱M足的一組約束，然后再在滿足這些約束的解中

14、隨機(jī)地選取個體以組成初始種群。的解中隨機(jī)地選取個體以組成初始種群。（3）適應(yīng)度函數(shù)的確定）適應(yīng)度函數(shù)的確定 適應(yīng)度函數(shù)是遺傳算法與實際優(yōu)化問題之間的接口。在遺適應(yīng)度函數(shù)是遺傳算法與實際優(yōu)化問題之間的接口。在遺傳算法中傳算法中要求適應(yīng)度函數(shù)值是非負(fù)的，且任何情況下都希望其要求適應(yīng)度函數(shù)值是非負(fù)的，且任何情況下都希望其值越大越好值越大越好；而實際優(yōu)化問題的目標(biāo)函數(shù)并不一定滿足這個條；而實際優(yōu)化問題的目標(biāo)函數(shù)并不一定滿足這個條件，有的是正的，有的可能為負(fù)，甚至可能是復(fù)數(shù)值。因此，件，有的是正的，有的可能為負(fù)，甚至可能是復(fù)數(shù)值。因此，對于任意優(yōu)化問題，首先應(yīng)把其數(shù)學(xué)形式表示為遺傳算法適于對于任意優(yōu)化問

15、題，首先應(yīng)把其數(shù)學(xué)形式表示為遺傳算法適于求解的形式，同時要保證二者在數(shù)學(xué)優(yōu)化層面上是等價的。這求解的形式，同時要保證二者在數(shù)學(xué)優(yōu)化層面上是等價的。這個過程稱為適應(yīng)度轉(zhuǎn)換。個過程稱為適應(yīng)度轉(zhuǎn)換。3/7/2022.13 適應(yīng)度轉(zhuǎn)換首先要保證適應(yīng)度值是非負(fù)的，其次要求目標(biāo)適應(yīng)度轉(zhuǎn)換首先要保證適應(yīng)度值是非負(fù)的，其次要求目標(biāo)函數(shù)的優(yōu)化方向應(yīng)與適應(yīng)度值增大的方向一致。設(shè)實際優(yōu)化問函數(shù)的優(yōu)化方向應(yīng)與適應(yīng)度值增大的方向一致。設(shè)實際優(yōu)化問題的目標(biāo)函數(shù)為題的目標(biāo)函數(shù)為J(x)，遺傳算法的適應(yīng)度函數(shù)為，遺傳算法的適應(yīng)度函數(shù)為f(x)，則有：，則有： 可以將適應(yīng)度函數(shù)表示為實際優(yōu)化問題目標(biāo)函數(shù)的線性可以將適應(yīng)度函數(shù)表

16、示為實際優(yōu)化問題目標(biāo)函數(shù)的線性形式，即有形式，即有bxJaxf)()(其中，其中，a，b是系數(shù)，可根據(jù)具體問題的特征及所期望適應(yīng)度的是系數(shù)，可根據(jù)具體問題的特征及所期望適應(yīng)度的分散程度來確定。分散程度來確定。 對于最小化問題，一般采用如下轉(zhuǎn)換形式：對于最小化問題，一般采用如下轉(zhuǎn)換形式：其中，其中，cmax既可以是到目前為止所有進(jìn)化代中目標(biāo)函數(shù)既可以是到目前為止所有進(jìn)化代中目標(biāo)函數(shù) J(x) 的的最大值（此時最大值（此時cmax將隨著進(jìn)化而有所變化），也可以根據(jù)經(jīng)驗將隨著進(jìn)化而有所變化），也可以根據(jù)經(jīng)驗人為設(shè)定。人為設(shè)定。maxmax( )( )( )0cJ xJ xcf x當(dāng)當(dāng)其它其它3/7/

17、2022.14 對于最大化問題（如需要），一般采用如下轉(zhuǎn)換形式：對于最大化問題（如需要），一般采用如下轉(zhuǎn)換形式：其中，其中，cmin既可以是當(dāng)前代中目標(biāo)函數(shù)既可以是當(dāng)前代中目標(biāo)函數(shù) J(x) 的最小值，也可以根的最小值，也可以根據(jù)經(jīng)驗人為設(shè)定。據(jù)經(jīng)驗人為設(shè)定。 采用如下的指數(shù)函數(shù)形式：采用如下的指數(shù)函數(shù)形式： 在最大化問題時，在最大化問題時，c一般取一般取1.618或或2；而在最小化問題時，；而在最小化問題時，c可取為可取為0.618。這樣，既保證了適應(yīng)度值非負(fù)，又使適應(yīng)度值。這樣，既保證了適應(yīng)度值非負(fù)，又使適應(yīng)度值增大方向和目標(biāo)函數(shù)優(yōu)化方向一致。增大方向和目標(biāo)函數(shù)優(yōu)化方向一致。( )( )J

18、 xf xcminmin( )( )0( )0J xcJ xcf x當(dāng)當(dāng)其它其它3/7/2022.15（4）復(fù)制（選擇）（）復(fù)制（選擇）（Reproduction or Selection） 復(fù)制是基于適者生存理論而提出的，是指種群中每一個體復(fù)制是基于適者生存理論而提出的，是指種群中每一個體按照適應(yīng)度函數(shù)進(jìn)入到匹配池中的過程。適應(yīng)度值高于種群平按照適應(yīng)度函數(shù)進(jìn)入到匹配池中的過程。適應(yīng)度值高于種群平均適應(yīng)度的個體在下一代中將有更多的機(jī)會繁殖一個或多個后均適應(yīng)度的個體在下一代中將有更多的機(jī)會繁殖一個或多個后代，而低于平均適應(yīng)度的個體則有可能被淘汰掉。復(fù)制的目的代，而低于平均適應(yīng)度的個體則有可能被淘

19、汰掉。復(fù)制的目的在于保證那些適應(yīng)度高的優(yōu)良個體在進(jìn)化中生存下去，在于保證那些適應(yīng)度高的優(yōu)良個體在進(jìn)化中生存下去，復(fù)制不復(fù)制不會產(chǎn)生新的個體會產(chǎn)生新的個體。常用的復(fù)制方法有：。常用的復(fù)制方法有：賭輪法賭輪法兩兩競爭法兩兩競爭法 從種群中隨機(jī)地選擇兩個個體，將其中適應(yīng)度較大的個體從種群中隨機(jī)地選擇兩個個體，將其中適應(yīng)度較大的個體作為被復(fù)制的個體；若兩個體適應(yīng)度相同，則任意選擇一個。作為被復(fù)制的個體；若兩個體適應(yīng)度相同，則任意選擇一個。排序法排序法 首先根據(jù)目標(biāo)函數(shù)值的大小將個體排序，根據(jù)具體問題應(yīng)首先根據(jù)目標(biāo)函數(shù)值的大小將個體排序，根據(jù)具體問題應(yīng)用各個體的排序序號分配各自進(jìn)入匹配池的概率。適應(yīng)度可

20、以用各個體的排序序號分配各自進(jìn)入匹配池的概率。適應(yīng)度可以按序號線性變化，也可以按某種非線性關(guān)系變化。按序號線性變化，也可以按某種非線性關(guān)系變化。3/7/2022.16（5）交叉（）交叉（Crossover） 交叉是指對從匹配池中隨機(jī)選出的兩個個體按一定的交叉交叉是指對從匹配池中隨機(jī)選出的兩個個體按一定的交叉概率概率 pc 部分地交換某些基因的過程。一般分兩步實現(xiàn)：第一步部分地交換某些基因的過程。一般分兩步實現(xiàn)：第一步是將新復(fù)制產(chǎn)生的匹配池中的個體隨機(jī)兩兩配對；第二步是進(jìn)是將新復(fù)制產(chǎn)生的匹配池中的個體隨機(jī)兩兩配對；第二步是進(jìn)行交叉繁殖，產(chǎn)生一對新的個體。行交叉繁殖，產(chǎn)生一對新的個體。交叉的目的是

21、為了生成新的交叉的目的是為了生成新的個體個體，產(chǎn)生新的基因組合，避免每代種群中個體的重復(fù)。，產(chǎn)生新的基因組合，避免每代種群中個體的重復(fù)。單點交叉（單點交叉（One-Point Crossover） 對每一對相互配對的個體，依設(shè)定的交叉概率對每一對相互配對的個體，依設(shè)定的交叉概率p pc c在其交叉在其交叉點處相互交換兩個父代個體的部分染色體，從而產(chǎn)生出兩個新點處相互交換兩個父代個體的部分染色體，從而產(chǎn)生出兩個新的個體，如下圖所示。的個體，如下圖所示。交叉前交叉前individual 111001 11001individual 201010 00110圖圖2 單點交叉單點交叉交叉后交叉后110

22、01 0011001010 110013/7/2022.17兩點交叉（兩點交叉（Two-Point Crossover） 按交叉概率隨機(jī)設(shè)置兩個交叉點，然后交換兩個父代個體按交叉概率隨機(jī)設(shè)置兩個交叉點，然后交換兩個父代個體在兩個交叉點之間的基因。在兩個交叉點之間的基因。均勻交叉（均勻交叉（Uniform Crossover） 其操作過程是：先選出兩個父代個體，之后依據(jù)交叉概率其操作過程是：先選出兩個父代個體，之后依據(jù)交叉概率 pc 產(chǎn)生一個與父代個體同樣長度的二進(jìn)制串，這里稱其為產(chǎn)生一個與父代個體同樣長度的二進(jìn)制串，這里稱其為模板模板（template）。若模板中的某位為）。若模板中的某位為0

23、，則兩個父代個體對應(yīng)位不，則兩個父代個體對應(yīng)位不進(jìn)行交換；反之，模板中的某位為進(jìn)行交換；反之，模板中的某位為1時，則交換兩個父代個體時，則交換兩個父代個體對應(yīng)位的基因。對應(yīng)位的基因。交叉前交叉前individual 111 01011 000individual 210 10110 101圖圖3 兩點交叉兩點交叉交叉后交叉后11 10110 00010 01011 1013/7/2022.18算數(shù)交叉（算數(shù)交叉（Arithmetic Crossover） 算數(shù)交叉的操作對象一般是由算數(shù)交叉的操作對象一般是由浮點數(shù)編碼浮點數(shù)編碼所表示的個體，所表示的個體，它通過兩個父代個體的線性組合而產(chǎn)生出兩個

24、新的個體。它通過兩個父代個體的線性組合而產(chǎn)生出兩個新的個體。 假設(shè)在兩個父代個體假設(shè)在兩個父代個體 ， 之間進(jìn)行算數(shù)交叉，則交叉運之間進(jìn)行算數(shù)交叉，則交叉運算后所產(chǎn)生出的兩個新個體是算后所產(chǎn)生出的兩個新個體是tAXtBX11(1)(1)tttAABtttBBAXXXXXX式中式中 為一參數(shù)，它若是一個常數(shù)，此時所進(jìn)行的交叉運算稱為一參數(shù)，它若是一個常數(shù)，此時所進(jìn)行的交叉運算稱為為均勻算數(shù)交叉均勻算數(shù)交叉；它也可以是一個由進(jìn)化代數(shù)所決定的變量，；它也可以是一個由進(jìn)化代數(shù)所決定的變量，此時所進(jìn)行的交叉運算稱為此時所進(jìn)行的交叉運算稱為非均勻算數(shù)交叉非均勻算數(shù)交叉。交叉前交叉前individual 1

25、0101100110template1001010101圖圖4 均勻交叉均勻交叉individual 20110010001交叉后交叉后010011001101110001003/7/2022.19（6）變異（）變異（Mutation） 一般的變異操作只作用于采用二進(jìn)制編碼的某單個個體，一般的變異操作只作用于采用二進(jìn)制編碼的某單個個體，它以一定的變異概率它以一定的變異概率pm對個體的某些位進(jìn)行取反操作。如同自對個體的某些位進(jìn)行取反操作。如同自然界很少發(fā)生基因突變一樣，變異概率然界很少發(fā)生基因突變一樣，變異概率pm一般都取得比較小。一般都取得比較小。變異的目的是為了增加種群個體的多樣性，防止丟失

26、一些有用變異的目的是為了增加種群個體的多樣性，防止丟失一些有用的遺傳模式。的遺傳模式。 在簡單遺傳算法中，變異就是將某個體中某一位的值作取在簡單遺傳算法中，變異就是將某個體中某一位的值作取反運算。反運算。變異前變異前1100110111圖圖5 變異操作示意圖變異操作示意圖變異后變異后11000101113/7/2022.20（7）收斂判據(jù)）收斂判據(jù) 常規(guī)的優(yōu)化方法有數(shù)學(xué)上比較嚴(yán)格的收斂判據(jù)，而遺傳算常規(guī)的優(yōu)化方法有數(shù)學(xué)上比較嚴(yán)格的收斂判據(jù)，而遺傳算法的收斂判據(jù)通常是啟發(fā)式的。由于遺傳算法沒有利用梯度信法的收斂判據(jù)通常是啟發(fā)式的。由于遺傳算法沒有利用梯度信息，因此要從數(shù)學(xué)上構(gòu)造比較嚴(yán)格的收斂判據(jù)

27、相當(dāng)困難。常用息，因此要從數(shù)學(xué)上構(gòu)造比較嚴(yán)格的收斂判據(jù)相當(dāng)困難。常用的收斂判據(jù)有：的收斂判據(jù)有： 根據(jù)計算時間和所采用計算機(jī)的性能確定收斂判據(jù)：一根據(jù)計算時間和所采用計算機(jī)的性能確定收斂判據(jù)：一般采用指定最大迭代次數(shù)的方法；般采用指定最大迭代次數(shù)的方法； 從解的質(zhì)量方面確定判據(jù)：如果連續(xù)幾代（或幾十代）從解的質(zhì)量方面確定判據(jù)：如果連續(xù)幾代（或幾十代）種群中的最優(yōu)解沒有變化，則認(rèn)為算法收斂；或種群中最優(yōu)個種群中的最優(yōu)解沒有變化，則認(rèn)為算法收斂；或種群中最優(yōu)個體的適應(yīng)度與平均適應(yīng)度之差和平均適應(yīng)度的比值小于某一給體的適應(yīng)度與平均適應(yīng)度之差和平均適應(yīng)度的比值小于某一給定值時，也可以認(rèn)為算法已經(jīng)收斂。

28、定值時，也可以認(rèn)為算法已經(jīng)收斂。3/7/2022.21（8）約束條件的處理）約束條件的處理 遺傳算法在求解有約束的優(yōu)化問題時，需對約束條件進(jìn)行遺傳算法在求解有約束的優(yōu)化問題時，需對約束條件進(jìn)行必要的處理。處理方式有：必要的處理。處理方式有：直接體現(xiàn)在字符串的編碼中直接體現(xiàn)在字符串的編碼中 對于優(yōu)化問題中變量的上、下限約束，可以讓字符串表示對于優(yōu)化問題中變量的上、下限約束，可以讓字符串表示的最大值和最小值分別對應(yīng)于實際約束變量的上、下限值。設(shè)的最大值和最小值分別對應(yīng)于實際約束變量的上、下限值。設(shè)待優(yōu)化變量待優(yōu)化變量x的變化范圍為的變化范圍為xmin, xmax，如用，如用l 位的二進(jìn)制字符位的二

29、進(jìn)制字符串串y來表示，則來表示，則 x、y之間有如下關(guān)系：之間有如下關(guān)系：)(12minmaxminxxyxxl判斷舍棄法判斷舍棄法 在遺傳算法的運算過程中，檢查得到字符串所對應(yīng)的解是在遺傳算法的運算過程中，檢查得到字符串所對應(yīng)的解是否為可行解。若是，則加入到下一代種群中；否則將其舍棄。否為可行解。若是，則加入到下一代種群中；否則將其舍棄。懲罰函數(shù)法懲罰函數(shù)法 如果一個解違反了某個約束，則視其違反程度給予一定的如果一個解違反了某個約束，則視其違反程度給予一定的懲罰，使其具有較小的適應(yīng)度。越限越嚴(yán)重，適應(yīng)度就越小。懲罰，使其具有較小的適應(yīng)度。越限越嚴(yán)重，適應(yīng)度就越小。3/7/2022.221.3

30、 遺傳算法的特點遺傳算法的特點 目前常規(guī)的優(yōu)化方法主要有目前常規(guī)的優(yōu)化方法主要有3種類型：解析法、枚舉法和種類型：解析法、枚舉法和隨機(jī)法。隨機(jī)法。 解析法是優(yōu)化方法中研究最多的一種，它又分為直接法和解析法是優(yōu)化方法中研究最多的一種，它又分為直接法和間接法。間接法。直接法直接法是一種通過沿著梯度信息最陡的方向逐漸運動是一種通過沿著梯度信息最陡的方向逐漸運動來尋找局部極值的方法；來尋找局部極值的方法；間接法間接法則是一種通過使目標(biāo)函數(shù)梯度則是一種通過使目標(biāo)函數(shù)梯度為零，進(jìn)而通過求解一組非線性方程來尋找局部極值的方法。為零，進(jìn)而通過求解一組非線性方程來尋找局部極值的方法。（1）解析法）解析法 解析法

31、的主要問題在于：解析法的主要問題在于： （1）要求目標(biāo)函數(shù)連續(xù)光滑且可微；）要求目標(biāo)函數(shù)連續(xù)光滑且可微； （2）一般只能找到局部極值而非全局極值，故對于存在）一般只能找到局部極值而非全局極值，故對于存在多峰極值的優(yōu)化問題有時顯得無能為力。多峰極值的優(yōu)化問題有時顯得無能為力。3/7/2022.23 隨機(jī)法能夠克服上述兩種方法的缺陷，它在搜索空間中隨隨機(jī)法能夠克服上述兩種方法的缺陷，它在搜索空間中隨機(jī)地漫游并記錄下所找到的最優(yōu)結(jié)果，當(dāng)搜索到一定程度后便機(jī)地漫游并記錄下所找到的最優(yōu)結(jié)果，當(dāng)搜索到一定程度后便終止。當(dāng)然，它所找到的結(jié)果往往也不是最優(yōu)解。實際上，隨終止。當(dāng)然，它所找到的結(jié)果往往也不是最優(yōu)

32、解。實際上，隨機(jī)法也是枚舉法中的一種。機(jī)法也是枚舉法中的一種。（2）枚舉法）枚舉法 枚舉法能夠克服解析法的兩點不足，它可以找到全局極值枚舉法能夠克服解析法的兩點不足，它可以找到全局極值且不要求目標(biāo)函數(shù)連續(xù)光滑。但其致命缺點是計算效率太低，且不要求目標(biāo)函數(shù)連續(xù)光滑。但其致命缺點是計算效率太低，對于許多實際問題往往會因為搜索空間太大而不可能將所有的對于許多實際問題往往會因為搜索空間太大而不可能將所有的情況一一搜索到。情況一一搜索到。（3）隨機(jī)法）隨機(jī)法3/7/2022.24 遺傳算法是基于自然選擇和基因遺傳學(xué)原理的搜索方法，遺傳算法是基于自然選擇和基因遺傳學(xué)原理的搜索方法，它將它將“優(yōu)勝劣汰、適者

33、生存優(yōu)勝劣汰、適者生存”的生物進(jìn)化原理引入到由待優(yōu)化的生物進(jìn)化原理引入到由待優(yōu)化參數(shù)形成的編碼串種群中，按照一定的適應(yīng)度函數(shù)及一系列遺參數(shù)形成的編碼串種群中，按照一定的適應(yīng)度函數(shù)及一系列遺傳操作對各個個體進(jìn)行篩選，使適應(yīng)度值較高的個體被保留下傳操作對各個個體進(jìn)行篩選，使適應(yīng)度值較高的個體被保留下來，從而組成新的種群，新種群中包含了上一代的大量信息，來，從而組成新的種群，新種群中包含了上一代的大量信息，并且引入了新的優(yōu)于上一代的個體。如此周而復(fù)始，種群中各并且引入了新的優(yōu)于上一代的個體。如此周而復(fù)始，種群中各個體的適應(yīng)度不斷提高，直至滿足一定的收斂條件。最后，以個體的適應(yīng)度不斷提高，直至滿足一定

34、的收斂條件。最后，以種群中適應(yīng)度值最高的個體作為待優(yōu)化參數(shù)的最優(yōu)解。種群中適應(yīng)度值最高的個體作為待優(yōu)化參數(shù)的最優(yōu)解。（4）遺傳算法）遺傳算法 遺傳算法也用到了隨機(jī)搜索技術(shù)，但它通過對參數(shù)空間的遺傳算法也用到了隨機(jī)搜索技術(shù)，但它通過對參數(shù)空間的隨機(jī)編碼并用適應(yīng)度函數(shù)作為工具來引導(dǎo)搜索過程向著更有效隨機(jī)編碼并用適應(yīng)度函數(shù)作為工具來引導(dǎo)搜索過程向著更有效的方向發(fā)展，因而它不同于常規(guī)的隨機(jī)法。的方向發(fā)展，因而它不同于常規(guī)的隨機(jī)法。3/7/2022.25 與常規(guī)優(yōu)化方法相比，遺傳算法的魯棒性較好，其主要與常規(guī)優(yōu)化方法相比，遺傳算法的魯棒性較好，其主要特點在于：特點在于： 遺傳算法對參數(shù)的編碼進(jìn)行操作，而

35、不是對參數(shù)本身；遺傳算法對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身； 遺傳算法從多個初始點開始操作，而不是從某一個點開遺傳算法從多個初始點開始操作，而不是從某一個點開始，這在很大程度上避免了搜索過程過早地收斂于局部極值，始，這在很大程度上避免了搜索過程過早地收斂于局部極值，因此更有可能求得全局極值；因此更有可能求得全局極值； 遺傳算法通過目標(biāo)函數(shù)計算適應(yīng)度，它不需要其它的推遺傳算法通過目標(biāo)函數(shù)計算適應(yīng)度，它不需要其它的推導(dǎo)運算和附加信息，因而對問題的依賴性??；導(dǎo)運算和附加信息，因而對問題的依賴性??； 遺傳算法使用概率的操作規(guī)則，而不是確定性的規(guī)則；遺傳算法使用概率的操作規(guī)則，而不是確定性的規(guī)則；

36、遺傳算法在解空間中采用啟發(fā)式搜索，而不是盲目的枚遺傳算法在解空間中采用啟發(fā)式搜索，而不是盲目的枚舉或完全隨機(jī)的搜索，因而搜索的效率高；舉或完全隨機(jī)的搜索，因而搜索的效率高； 遺傳算法對于待尋優(yōu)的問題基本沒有限制，既可以是數(shù)遺傳算法對于待尋優(yōu)的問題基本沒有限制，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，也可以是映射矩陣或神經(jīng)網(wǎng)絡(luò)表示學(xué)解析式所表示的顯函數(shù)，也可以是映射矩陣或神經(jīng)網(wǎng)絡(luò)表示的隱函數(shù)，同時也不要求待優(yōu)化函數(shù)連續(xù)、可微；的隱函數(shù)，同時也不要求待優(yōu)化函數(shù)連續(xù)、可微；3/7/2022.26 遺傳算法所具有的隱含并行性的特點，使其可以通過遺傳算法所具有的隱含并行性的特點，使其可以通過大規(guī)模并行搜索來提

37、高計算速度；大規(guī)模并行搜索來提高計算速度； 遺傳算法適合復(fù)雜的、高度非線性問題的優(yōu)化。遺傳算法適合復(fù)雜的、高度非線性問題的優(yōu)化。1.4 遺傳算法的研究熱點遺傳算法的研究熱點（1）編碼方式的確定；）編碼方式的確定；（2）專用遺傳算子的設(shè)計；）專用遺傳算子的設(shè)計；（3）控制參數(shù)的選擇；）控制參數(shù)的選擇；種群規(guī)模：種群規(guī)模：N = 20100；交叉概率：交叉概率：pc = 0.600.95；變異概率：變異概率：pm = 0.0010.01。李擎李擎、張偉、尹怡欣、王志良一種新的調(diào)節(jié)交叉和變異概率、張偉、尹怡欣、王志良一種新的調(diào)節(jié)交叉和變異概率的自適應(yīng)算法的自適應(yīng)算法控制與決策，控制與決策，2008年

38、年1月第月第23卷第卷第1期：期：7983 3/7/2022.272 遺傳算法的應(yīng)用實例遺傳算法的應(yīng)用實例車載導(dǎo)航系統(tǒng)路徑規(guī)劃算法的設(shè)計車載導(dǎo)航系統(tǒng)路徑規(guī)劃算法的設(shè)計2.1 問題簡介問題簡介 所謂車載導(dǎo)航系統(tǒng)路徑規(guī)劃，就是在電子地圖中找到一條所謂車載導(dǎo)航系統(tǒng)路徑規(guī)劃，就是在電子地圖中找到一條從起點到終點在距離（或時間）上最短的路徑。從起點到終點在距離（或時間）上最短的路徑。 下圖為一個路徑規(guī)劃用仿真地圖，其上共有下圖為一個路徑規(guī)劃用仿真地圖，其上共有15個節(jié)點，個節(jié)點，24條弧?；∠碌臄?shù)據(jù)表示路徑的長度（單位：公里），弧上的數(shù)條弧?；∠碌臄?shù)據(jù)表示路徑的長度（單位：公里），弧上的數(shù)據(jù)則表示該路段

39、車輛行駛的速度（單位：米據(jù)則表示該路段車輛行駛的速度（單位：米/秒）。秒）。 在實際電子地圖中，節(jié)點相當(dāng)于道路的交叉點，弧相當(dāng)于在實際電子地圖中，節(jié)點相當(dāng)于道路的交叉點，弧相當(dāng)于實際道路。實際道路。3/7/2022.281.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.4DPNLOMFCBGKH

40、IJAE圖圖6 路徑規(guī)劃用仿真地圖路徑規(guī)劃用仿真地圖3/7/2022.292.2 遺傳算法的具體應(yīng)用遺傳算法的具體應(yīng)用（1）路徑的表示方法）路徑的表示方法 這里采用這里采用符號編碼方式符號編碼方式表示實際路網(wǎng)中的路徑。表示實際路網(wǎng)中的路徑。 對于圖對于圖6中一條從中一條從A點到點到P點的路徑，采用符號編碼方式得點的路徑，采用符號編碼方式得到的個體為到的個體為A、B、E、H、L、O、P。圖圖7 仿真地圖中的一條路徑仿真地圖中的一條路徑ABEHLOP3/7/2022.30（2）初始路徑的產(chǎn)生）初始路徑的產(chǎn)生傳統(tǒng)遺傳算法傳統(tǒng)遺傳算法 隨機(jī)生成初始路徑，會產(chǎn)生斷路或環(huán)路。隨機(jī)生成初始路徑，會產(chǎn)生斷路或

41、環(huán)路。改進(jìn)遺傳算法改進(jìn)遺傳算法（a）克服斷路的思路）克服斷路的思路 從起始點出發(fā)，隨機(jī)選取與起始點直接相連的一個點作為從起始點出發(fā)，隨機(jī)選取與起始點直接相連的一個點作為下一個節(jié)點，如此反復(fù)直到找到終點為止。下一個節(jié)點，如此反復(fù)直到找到終點為止。 在路徑的產(chǎn)生過程中為了避免出現(xiàn)環(huán)路，規(guī)定在一條路徑在路徑的產(chǎn)生過程中為了避免出現(xiàn)環(huán)路，規(guī)定在一條路徑中當(dāng)一個路徑節(jié)點被選中以后，則給該節(jié)點一個標(biāo)記，只有沒中當(dāng)一個路徑節(jié)點被選中以后，則給該節(jié)點一個標(biāo)記，只有沒有標(biāo)記的節(jié)點才能被選作新的路徑節(jié)點，每條初始路徑選擇完有標(biāo)記的節(jié)點才能被選作新的路徑節(jié)點，每條初始路徑選擇完畢后標(biāo)記全部刷新。畢后標(biāo)記全部刷新。

42、（b）克服環(huán)路的思路）克服環(huán)路的思路3/7/2022.31（3）適應(yīng)度函數(shù)的確定）適應(yīng)度函數(shù)的確定距離最短優(yōu)化原則下的適應(yīng)度函數(shù)距離最短優(yōu)化原則下的適應(yīng)度函數(shù)時間最優(yōu)優(yōu)化原則下的適應(yīng)度函數(shù)時間最優(yōu)優(yōu)化原則下的適應(yīng)度函數(shù)1( )iijF xx1( )iijijF xxvix其中，其中， 為第為第i個染色體（路徑）；個染色體（路徑）； 為第為第i條路徑第條路徑第j段的路徑段的路徑長度。長度。ijxijv其中，其中， 仍為第仍為第i條路徑第條路徑第j段的路徑長度；段的路徑長度； 為第為第i條路徑第條路徑第j段的行駛速度。段的行駛速度。ijx3/7/2022.32 不能象傳統(tǒng)遺傳算法那樣隨機(jī)進(jìn)行一點、

43、兩點或多點交叉不能象傳統(tǒng)遺傳算法那樣隨機(jī)進(jìn)行一點、兩點或多點交叉操作，因為這樣很容易產(chǎn)生斷路或環(huán)路。操作，因為這樣很容易產(chǎn)生斷路或環(huán)路。 這里只允許使用在重復(fù)節(jié)點位置交叉且只進(jìn)行一點交叉的這里只允許使用在重復(fù)節(jié)點位置交叉且只進(jìn)行一點交叉的操作方式，具體實現(xiàn)步驟如下：操作方式，具體實現(xiàn)步驟如下：（5）交叉操作）交叉操作（4）復(fù)制（選擇）操作）復(fù)制（選擇）操作 采用賭輪法進(jìn)行復(fù)制操作。采用賭輪法進(jìn)行復(fù)制操作。 隨機(jī)選取兩個個體作為待交叉?zhèn)€體；隨機(jī)選取兩個個體作為待交叉?zhèn)€體； 找出兩個待交叉?zhèn)€體的共同節(jié)點（起點和終點除外）的找出兩個待交叉?zhèn)€體的共同節(jié)點（起點和終點除外）的集合；集合； 從共同節(jié)點的集

44、合中隨機(jī)選擇一個節(jié)點作為交叉節(jié)點；從共同節(jié)點的集合中隨機(jī)選擇一個節(jié)點作為交叉節(jié)點； 檢查兩個待交叉?zhèn)€體在交叉節(jié)點之前或之后的內(nèi)容是否檢查兩個待交叉?zhèn)€體在交叉節(jié)點之前或之后的內(nèi)容是否相同。如相同，則取消本次交叉操作；否則，兩者交換交叉點相同。如相同，則取消本次交叉操作；否則，兩者交換交叉點之前（或之后）的內(nèi)容形成兩個新個體。之前（或之后）的內(nèi)容形成兩個新個體。3/7/2022.33 下面將結(jié)合仿真地圖舉例說明交叉操作是如何實現(xiàn)的。下面將結(jié)合仿真地圖舉例說明交叉操作是如何實現(xiàn)的。 設(shè)選取的兩個待交叉樣本為設(shè)選取的兩個待交叉樣本為A、B、E、I、L、O、P和和A、C、E、H、L、N、P； 兩者重復(fù)節(jié)

45、點的集合為兩者重復(fù)節(jié)點的集合為 E、L ； 隨機(jī)選擇隨機(jī)選擇E作為交叉節(jié)點；作為交叉節(jié)點； 檢查發(fā)現(xiàn)兩者待交叉樣本在檢查發(fā)現(xiàn)兩者待交叉樣本在E點之前和之后的內(nèi)容均不點之前和之后的內(nèi)容均不相同，因此可以進(jìn)行此次交叉操作，交叉后的新個體為：相同，因此可以進(jìn)行此次交叉操作，交叉后的新個體為：A、B、E、 H、L、N、PA、C、E、 I、L、O、P和和3/7/2022.34圖8 交叉操作示意圖PLOCBHIAEN3/7/2022.35（6）變異操作）變異操作 不能采用傳統(tǒng)遺傳算法中隨機(jī)選擇變異點的做法，因為這不能采用傳統(tǒng)遺傳算法中隨機(jī)選擇變異點的做法，因為這樣同樣容易產(chǎn)生斷路或環(huán)路。樣同樣容易產(chǎn)生斷路

46、或環(huán)路。 這里采用的變異操作，其基本步驟如下：這里采用的變異操作，其基本步驟如下： 隨機(jī)選取一個個體作為待變異個體；隨機(jī)選取一個個體作為待變異個體； 在待變異個體中隨機(jī)選擇一個節(jié)點（起點和終點除外）在待變異個體中隨機(jī)選擇一個節(jié)點（起點和終點除外）作為待變異節(jié)點；作為待變異節(jié)點； 找到和該待變異節(jié)點直接相連的節(jié)點集合（該集合中不找到和該待變異節(jié)點直接相連的節(jié)點集合（該集合中不包括起點、終點以及待變異個體中的節(jié)點）；包括起點、終點以及待變異個體中的節(jié)點）； 從節(jié)點集合中隨機(jī)選取一個節(jié)點作為變異后節(jié)點；從節(jié)點集合中隨機(jī)選取一個節(jié)點作為變異后節(jié)點； 檢查待變異節(jié)點之前和之后的節(jié)點是否與變異后節(jié)點直檢查

47、待變異節(jié)點之前和之后的節(jié)點是否與變異后節(jié)點直接相連。若直接相連，則用變異后節(jié)點替代待變異節(jié)點完成變接相連。若直接相連，則用變異后節(jié)點替代待變異節(jié)點完成變異過程；否則，放棄此次操作，回到第異過程；否則，放棄此次操作，回到第步，直至將節(jié)點集合步，直至將節(jié)點集合中的所有節(jié)點全部選遍。中的所有節(jié)點全部選遍。3/7/2022.36 現(xiàn)結(jié)合仿真地圖舉例說明變異操作的具體實現(xiàn)方法?，F(xiàn)結(jié)合仿真地圖舉例說明變異操作的具體實現(xiàn)方法。 選擇待變異個體為選擇待變異個體為A、C、E、I、L、O、P； 經(jīng)過檢查發(fā)現(xiàn)經(jīng)過檢查發(fā)現(xiàn)C和和B不直接相連，所以取消此次變異操不直接相連，所以取消此次變異操作；接著選取作；接著選取F作

48、為變異后節(jié)點，檢查發(fā)現(xiàn)作為變異后節(jié)點，檢查發(fā)現(xiàn)C和和F、F和和I直接相直接相連，故可進(jìn)行此次變異操作，變異后的新個體為連，故可進(jìn)行此次變異操作，變異后的新個體為 隨機(jī)選取隨機(jī)選取E作為待變異節(jié)點；作為待變異節(jié)點； 與與E直接相連的節(jié)點集合為直接相連的節(jié)點集合為B、F、H； 隨機(jī)選取隨機(jī)選取B作為變異后節(jié)點；作為變異后節(jié)點；A、C、F、I、L、O、P3/7/2022.37PLOFCBHIAE圖圖9 變異操作示意圖變異操作示意圖3/7/2022.38（7）刪除操作）刪除操作 刪除操作的具體步驟如下：刪除操作的具體步驟如下： 隨機(jī)選擇一個個體；隨機(jī)選擇一個個體； 檢查該個體中任意兩個不相鄰節(jié)點（包括

49、起點和終點）檢查該個體中任意兩個不相鄰節(jié)點（包括起點和終點）之間是否直接相連。如果直接相連，則刪除兩個節(jié)點之間的所之間是否直接相連。如果直接相連，則刪除兩個節(jié)點之間的所有節(jié)點，結(jié)束此次刪除操作；否則，取消本次刪除操作。有節(jié)點，結(jié)束此次刪除操作；否則，取消本次刪除操作。 下面也結(jié)合仿真地圖舉例說明刪除操作的具體實現(xiàn)方法。下面也結(jié)合仿真地圖舉例說明刪除操作的具體實現(xiàn)方法。 設(shè)隨機(jī)選擇的個體為設(shè)隨機(jī)選擇的個體為A、C、E、F、I、L、O、P； 檢查發(fā)現(xiàn)檢查發(fā)現(xiàn)E、I直接相連，則刪除兩者之間的節(jié)點直接相連，則刪除兩者之間的節(jié)點F，從，從而得到新個體而得到新個體A、C、E、I、L、O、P3/7/2022.39PLOFCIAE圖圖10 刪除操作示意圖刪除操作示意圖3/7/2022.40（8）仿真結(jié)果）仿真結(jié)果初始種群初始種群33.5A、B、D、