基于改進(jìn)遺傳算法的最短路徑問題的研究

肖文海，劉貴平，符安君

?

基于改進(jìn)遺傳算法的最短路徑問題的研究

肖文海1，劉貴平1，符安君2

（1.華南理工大學(xué)，廣州 510091；2.廣州天越電子科技有限公司，廣州 510091）

遺傳算法解決最短路徑問題，易出現(xiàn)早熟現(xiàn)象，對此論文提出了隔代交叉的自適應(yīng)遺傳算法。本文首先闡述了標(biāo)準(zhǔn)遺傳算法過程，并對其出現(xiàn)的早熟現(xiàn)象進(jìn)行了分析；其次，調(diào)整自適應(yīng)遺傳算法的適應(yīng)度函數(shù)，提出了隔代交叉的自適應(yīng)遺傳算法；最終，算法在多峰值問題和不同最短路徑問題進(jìn)行了驗證，分析了算法的優(yōu)劣。實驗表明，本文提出的算法可以有效的避免早熟、收斂速度快、穩(wěn)定性高。

自適應(yīng)；隔代交叉；遺傳算法；最短路徑

0 引言

遺傳算法采用生物進(jìn)化論的思想，以自然選擇、遺傳變異等生物機制為主要特征進(jìn)行全局概率搜索的算法。該算法具有較強的搜索能力，但是陷入局部最優(yōu)問題。

最短路徑是圖論中典型的研究問題。該圖研究的方面是在圖上尋找兩個結(jié)點間的最短長度。目前，最短路徑的含義已經(jīng)推廣到時間、容量、費用等方面，實際中的車載導(dǎo)航系統(tǒng)等也有應(yīng)用。姚明海[1]等人把遺傳算法與模擬退火算法相結(jié)合進(jìn)行了算法的改進(jìn)，并將其應(yīng)用于求解TSP問題；薛冰冰[2]研究當(dāng)前算法的不足，對目前研究的自適應(yīng)遺傳算法進(jìn)行改進(jìn)，不僅把改進(jìn)算法在MATLAB上進(jìn)行了仿真，而且還把改進(jìn)算法應(yīng)用到足球機器人的實踐中。

目前，遺傳算法在解決最短路徑達(dá)到較好的效果，但是解決過程中存在一定問題。論文基于此，結(jié)合實際來研究遺傳算法。

1 標(biāo)準(zhǔn)遺傳算法

遺傳算法中，把問題解的轉(zhuǎn)化為染色體，每個染色體的基因排列順序的不同則代表了問題的不同解，采用適應(yīng)度函數(shù)對群體中個體的性能的評價，對環(huán)境適應(yīng)能力強的個體實現(xiàn)交叉的機會大，部分個體會產(chǎn)生變異，完成一代的進(jìn)化。標(biāo)準(zhǔn)遺傳算法的基本結(jié)構(gòu)，如圖1所示。

圖1 標(biāo)準(zhǔn)遺傳算法的基本結(jié)構(gòu)

1）參數(shù)編碼

遺傳算法中，把解決目標(biāo)問題的表示域和算法中的染色體空間位串建立關(guān)系，即確定相應(yīng)的編碼或解碼運算。論文采用二進(jìn)制編碼方式來實現(xiàn)對最短路徑的解空間的編碼。

2）初始種群

遺傳算法操作對象是種群，首先需要生成由若干個體組成的初始種群。實際工程問題求解中，并不具有問題解的先驗知識，無法確定最優(yōu)解的數(shù)量及相應(yīng)解的分布情況。

3）適應(yīng)度函數(shù)

遺傳算法將問題空間表示為染色位串空間，為了執(zhí)行適者生存的原則必須對個體位串的適應(yīng)性進(jìn)行評價。計算個體的在這個環(huán)境下的適應(yīng)度，用該值高低定量的衡量其生存能力。一般情況，具有較高的適應(yīng)函數(shù)值的染色體，在遺傳迭代中就能獲得較高的評價，其生存能力也較強。

4）遺傳算子

經(jīng)典的遺傳算子包含選擇（selection）、雜交（crossover）和變異（mutation）算子三種基本的形式。在基本算子中，雜交算子是最為主要關(guān)鍵的，是整個算法中應(yīng)用最多、最廣的操作。論文的選擇算子選取輪盤賭選擇法。

交叉一般是單點交叉、兩點、多點交叉方法。變異算子個體串某些基因位置基因值的變化。

遺傳算法中，交叉算子是全局搜索能力的主要算子。遺傳算法是通過選擇、交叉和變異算子實現(xiàn)全局的搜索能力。

2 遺傳算法的改進(jìn)

標(biāo)準(zhǔn)遺傳算法在解決現(xiàn)實問題時，容易出現(xiàn)早熟收斂和后期搜索遲鈍等現(xiàn)象，為此深入研究表明：交叉概率的高低決定著種群的更新速度和搜索速度的快慢，交叉概率越大，算法的探測能力越強，越易得到新的優(yōu)良個體。增加算法的收斂速度；若交叉概率很小，種群的進(jìn)化就會停止不前。Srinivas[4]等提出了自適應(yīng)遺傳算法（AGA）。

（3）

遺傳算法大多是同代的染色體才進(jìn)行交叉操作。該交叉機制在實際應(yīng)用中容易使算法過早收斂。因此，本文提出自適應(yīng)遺傳算法基礎(chǔ)上隔代交叉。

具體實現(xiàn)過程如下：

Step1.在新一代的染色體中，選擇最優(yōu)的一部分染色體Ti，同時選取平均值以上的染色體進(jìn)入染色體池。

Step2.把最優(yōu)的一部分染色體與父代中的染色進(jìn)行交叉與變異；

Step3.用適應(yīng)度評價函數(shù)選取大于平均值得染色體進(jìn)入進(jìn)入染色體池

Step4.在染色體池中進(jìn)行下輪的交叉變異，并跳入step1。

3 算法的實驗對比

上述算法在自適應(yīng)遺傳算法的基礎(chǔ)上進(jìn)行調(diào)整改進(jìn)，具體實施，如圖2、圖3所示。

圖2 簡單圖

圖3 較為復(fù)雜圖

圖2、圖3中進(jìn)行試驗，分別從簡單與復(fù)雜兩個方面來設(shè)計。

3.1 簡單圖形算法的對比

算法的實現(xiàn)首先在圖2對比算法的優(yōu)劣。在圖2的基礎(chǔ)上，進(jìn)行了經(jīng)典遺傳算法、自適應(yīng)遺傳算法、論文提出的改進(jìn)方法。在變異概率pm=0.04時運行時間，如表1所示。

表1 三種算法運行時間比較

從表中可知論文提出的改進(jìn)算法用時最少。

染色體在算法運行前后的變化情況，如圖4所示。

a 隨機生成的染色體信息

b 經(jīng)典算法的染色體信息

c 改進(jìn)交叉算子的染色體信息

d 改進(jìn)算法的染色體信息

圖4 染色體的變化

圖4.a是隨機生成的染色的位置信息，圖4.b是經(jīng)典算法運行之后的染色體分布情況，圖4.c是改進(jìn)交叉算子的運行之后的染色體的分布情況，圖4.d是本論文的改進(jìn)算法得到的染色體的分布情況。三種算法的時間分析上，只改進(jìn)交叉算子的算法具有較高的優(yōu)勢。

從整體來看，論文提出的改進(jìn)算法具有較高的優(yōu)勢。本問題提出的算法充分考慮種群多樣性，運行時間比交叉算子算法慢了一點點，但本文提出的算法的收斂性遠(yuǎn)高其算法的收斂性。

3種算法的最優(yōu)、平均適應(yīng)度函數(shù)變化曲線，如圖5所示。

a 經(jīng)典算法

b 改進(jìn)交叉算則算法

c 改進(jìn)交叉概率算法

經(jīng)典的算法的劣勢在3個圖明顯顯現(xiàn)出現(xiàn)。改進(jìn)算法的收斂性上明顯優(yōu)勢；增加種群多樣性的也可保證算法的收斂性。

3.2 較為復(fù)雜的圖形算法對比

論文主要從算法的執(zhí)行時間、收斂性方面來分析算法的優(yōu)劣。遺傳代數(shù)選擇200次，其余參數(shù)不變。

經(jīng)典遺傳算法與論文提出的改進(jìn)算法運行時間分別為3.3975、3.3584，而自適應(yīng)遺傳算法計算出現(xiàn)了局部最優(yōu)的現(xiàn)象，計算結(jié)果與預(yù)期不匹配，所以不予以參考。改進(jìn)算法的收斂時間明顯短于經(jīng)典算法的時間。

圖6.a、b為運行染色體分布情況，如圖6所示。

圖6 a 改進(jìn)算法的染色體分布圖

圖6 b經(jīng)典算法的染色體分布圖

由圖可知改進(jìn)算法較經(jīng)典算法收斂性好。經(jīng)典算法的染色體分布較為分散，而改進(jìn)算法則相對集中。

改進(jìn)算法的適應(yīng)度值變化曲線，如圖7所示。

圖7 改進(jìn)算法的適應(yīng)度值變化曲線

經(jīng)典遺傳算法的適應(yīng)度值變化曲線圖，如圖8所示。

圖8 經(jīng)典算法的適應(yīng)度值變化曲線

改進(jìn)算法的最優(yōu)適應(yīng)度函數(shù)變化曲線的趨勢較為平緩、穩(wěn)定。由平均適應(yīng)度值變化曲線可知，改進(jìn)算法的平均適應(yīng)度值平緩的、逐步地收斂，而經(jīng)典算法收斂性較差；最終收斂值高于本文提出的改進(jìn)算法，這是因固定的交叉變異概率引起的，出現(xiàn)局部收斂。

4結(jié)論

最短路徑研究有助于解決生活的很多問題，論文進(jìn)一步地研究遺傳算法。本文結(jié)合最短路徑問題的實際，對自適應(yīng)遺傳算法進(jìn)行改進(jìn)。從上述實驗可以看出：改進(jìn)遺傳算法更能有效的解決最短路徑問題，有效的避免局部最優(yōu)，提高算法的運行速率及算法的收斂性。

[1] 姚明海,王娜,趙連朋. 改進(jìn)的模擬退火和遺傳算法求解TSP問題[J]. 計算機工程與應(yīng)用,2013,14:60-65.

[2] 薛冰冰. 基于改進(jìn)型遺傳算法的足球機器人路徑規(guī)劃研究[D].長春工業(yè)大學(xué),2012.

[3] De Jong K.A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems[D]. USA: University of Michigan, 1975.

[4] Chen Lin.An Adaptive Genetic Algorithm based on Population Diversity Stratety // Third International Conference on Genetic and EvolutionaryComputing[C].New York:IEEE,2009:93-96.

[5] 李延梅. 一種改進(jìn)的遺傳算法及應(yīng)用[D].華南理工大學(xué),2012.

[6] 梁芳. 遺傳算法的改進(jìn)及其應(yīng)用[D].武漢理工大學(xué),2008.

Research on Shortest Path Problem Based on Improved Genetic Algorethm

Xiao Wenhai1, Liu Guiping1, Fu Anjun2

(1. South china University of Technology, Guangzhou 510091, China;2. Guangzhou Tian Yue Electronic Technology Co.,Ltd, Guangzhou 510091, China;)

This paper describes the standard genetic algorithm process, the precocious phenomenon is analyzed. The adaptiue function of adaptive genetic algorithm is improued, the generational cross is presented in this article. The pros and cons of three algorithms are compared and analyzed. Experimental results show that the proposed algorithm can effectively avoid prematurity, fast convergence and high stability.

Adaptive algorithm; Generational cross; GA; The shortest path

1007-757X(2016)12-0064-04

TP311

A

肖文海（1984-），湖南新邵人，華南理工大學(xué)，碩士研究生，研究方向：遺傳算法，廣州 510091

劉貴平（1983-），男，工程師，服務(wù)計算機工程，華南理工大學(xué)，碩士研究生，廣州 510091

符安君（1984-），男，岳陽，工程師，通信工程廣州天越電子科技有限公司，廣州 510091

（2015.05.30）