求解k最短路徑問題的混合遺傳算法

趙禮峰，于汶雨

(南京郵電大學 理學院，江蘇 南京 210023)

求解k最短路徑問題的混合遺傳算法

趙禮峰，于汶雨

(南京郵電大學 理學院，江蘇 南京 210023)

遺傳算法求解問題的關鍵在于對問題的解進行編碼,同時需要構造出適應度函數。結合k最短路徑實際問題，重新定義了一種染色體編碼方式，并且新構造了符合該問題的適應度函數。標準遺傳算法采用固定的交叉率和變異率,在應用過程中存在收斂過慢、早熟及穩定性差的缺點。因此，提出了一種改進的自適應遺傳算法,對交叉率和變異率采用自適應方式,構造了確定交叉率和變異率的公式，加快了算法收斂速度。同時結合模擬退火的Metropolis準則對子代個體的接收做出選擇，克服了算法容易早熟的問題。仿真結果表明，改進后的混合遺傳算法可以求解k最短路問題，并且在尋優精確度、時間效率、穩定性上均優于標準遺傳算法。

混合遺傳算法；染色體編碼；Metropolis準則；k最短路徑

0 引 言

k最短路問題[1]是圖論中研究的一個重要課題，同時在現代計算機網絡以及交通系統中扮演著重要的角色。該問題最早由Hoffman和Pavley在20世紀50年代提出[2]，多年來也一直受到學術界的廣泛關注，并且先后提出了多種求解k最短路徑問題的算法。因此，如何快速求解k最短路徑問題成為了研究的重點。文獻[3]主要的研究成果是基于Dijkstra算法的前N條最短路徑算法；文獻[4-6]利用“偏離路徑”的性質給出計算k條最短路徑的遞推公式,但在求解第k條最短路徑時采用了不同的方法。

遺傳算法(Genetic Algorithm)[7]是由美國J.Holland教授在1975年首先提出的、模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程演化而來的隨機化搜索方法。近年來在世界范圍內形成進化計算熱潮，計算智能已成為人工智能研究的一個重要方向，加上后來興起的人工生命研究，使得遺傳算法受到了極大的關注。

遺傳算法雖然具有良好的全局搜索能力，可以快速地搜索出解空間中的全體解，但算法存在收斂速度慢或易出現“早熟”現象等缺陷。文中針對遺傳算法不足之處進行改進。為克服遺傳算法中pc和pm不好確定的缺點，對pc和pm采用自適應過程。結合模擬退火算法的Metropolis準則，提高局部搜索能力，克服遺傳算法早熟問題。同時為使遺傳算法使用于k最短路問題，構造一種新的染色體編碼方式和染色體的交叉操作。仿真結果表明，該算法可以提高運行效率，具有較高的精確度并且結構簡明。

1 預備知識

2 遺傳算法和模擬退火算法

2.1 遺傳算法基本步驟

遺傳算法尋優過程其實是一個迭代的過程。把搜索的解空間映射為遺傳的空間,將解映射成為染色體,向量中的每個元素稱為基因,將所有的染色體組成種群,并按目標函數對每個染色體的優劣進行評價,并根據結果給出一個適應度值(fitness)。在這種情況下,每一代中各個體的特征可通過染色體遺傳到一下代中。在下一代中,一個群體中合體相互之間可以復制(reproduction)和交叉(crossover),并會以一定的概率發生變異(mutation)。交叉傾向于選擇群體中最為優秀的個體,這些交叉個體的最優特性相結合后產生的后代比父代具有更優良的特性,從而產生較好的解。遺傳算法基本流程[9]如圖1所示。

2.2 模擬退火基本原理與Metropolis準則

模擬退火算法(Simulated Annealing,SA)是模擬熱力學中經典粒子系統的降溫過程來求解規劃問題的極值。當孤立粒子系統的溫度以足夠慢的速度下降時,系統近似處于熱力學平衡狀態,最后系統將達到本身的最低能量狀態,即基態,這相當于能量函數的全局極小點。

模擬退火算法的基本原理如下：

(3)若Δf≤0，則接受新點，作為下一次模擬的初始點。

以上步驟稱為Metropolis準則[10]。按照一定的退火方案逐漸降低溫度,重復Metropolis過程,就構成了模擬退火優化算法。

圖1 遺傳算法流程圖

3 算法改進

3.1 染色體編碼

結合k最短路徑問題實際情況，文中定義了一種新的染色體編碼方式。

假設在無向賦權圖G=(V，E)中，初始節點Vs到目的節點Vt的路徑為： 1→5→9→13→17→20。其中，每個數字代表的是節點編號，在遺傳算法中可以作為每個染色體的基因，不同的路徑包含有不同的基因點，所以設計染色體的編碼方式為根據節點編號編碼，上述路徑的染色體編碼為：[1-5-9-13-17-20]。

3.2 適應度函數和選擇概率

(1)

選擇概率與其適應度呈比例，假設群體大小為N，第i個染色體的適應度為fi，第i個染色體被選中的概率為Pi，那么

(2)

顯然個體適應度越大被選擇的概率越高。

3.3 交叉操作與變異操作

交叉操作為兩個父代個體的部分結構替換重組從而生成新個體的操作。文中采用兩點交叉的方式，根據k最短路徑問題定義一種新的交叉方式，如下所示：

父代1：

父代2：

子代1：

子代2：

變異操作的基本內容是對群體中的染色體個體上的某些基因點的基因值進行變更。其目的是可以使遺傳算法具備局部隨機搜索能力和保持群體的多樣性，避免出現未成熟就收斂的情況。在最短路問題中，選擇要變異的路徑，假設為Y：

若變異后產生環路，按照交叉操作中所述進行處理。

3.4 交叉率(pc)與變異率(pm)的確定

遺傳算法在進化過程中，進化程度與交叉率和變異率[11]的取值有很大關系，pc取值越大,新個體產生的速度越快，但當pc過大時又會使高適應度的個體結構快速被破壞，當pc取值過小時會使搜索過程緩慢,甚至停滯不前。當變異概率pm取值過小時,不易產生新的結構;當pm取值過大時,遺傳算法就會變成純粹的隨機搜索算法。

所以文中采取自適應的遺傳算法。根據交叉率和變異率對遺傳算法群體進化過程中的影響，設計如下公式進行自適應調整：

pc1=0.9,pc2=0.2

(3)

pm1=0.01,pm2=0.05

(4)

其中，pc為兩個交叉父代個體中適應度值較大的個體；favg為每一代群體的平均適應度值；fmax為群體中適應度值最大的個體。

當個體的適應度值小于平均值時，采用較高的pc和pm，使個體進化成為優秀個體的概率增大；當個體的適應度值大于平均適應度值時，采用較低的pc和pm，這樣可以確保優秀個體的結構不容易被改變。

3.5 對最優個體進行模擬退火操作

模擬退火算法[12]的優點之一就是能以一定的概率接收較差解.也就是說算法即使陷入局部最優,理論上經過足夠長的時間也可跳出來，從而收斂到全局最優解。新解是否被接受,判斷的依據為Metropolis準則：

(5)

經過交叉操作后，若子代個體適應度變優,完全接收新解為當前解；若子代個體惡化,則以概率p接受惡化解為新的當前解。同時為了使每一代中優良個體結構不被破壞,采用精英保留策略[13],如果下一代群體中的最優個體適應度值小于當前群體最優個體適應度值,那么用當前群體中最優個體或者適應度值大于下一代最優個體適應度值的多個個體隨機替代下一代群體中適應度差的相應數量的個體，確保了當前的最優個體不會因為交叉、變異等操作而被破壞。

3.6 算法流程

Step1:群體初始化，隨機選取n條路徑構成群體；

Step2:對群體中的每一個個體，根據式(1)和式(2)分別計算適應度值和選擇概率；

Step3:按照Step2中得到的選擇概率選擇需要交叉操作的個體；

Step4:根據式(3)確定交叉率，根據3.3中所述的交叉方式進行交叉操作；

Step5:根據式(4)確定變異率，根據3.3中所述的變異方式進行變異操作；

Step6:按照模擬退火Metropolis準則對交叉后的個體是否接收進行操作；

Step7:根據精英保留策略對子代群體進行操作；

Step8:判斷是否達到終止條件，若達到終止條件則輸出前k個優秀解，否則轉Step2。

4 仿真實驗

仿真實驗環境：處理器為Intel COREi5，操作系統為Windows7,應用MATLAB[14]編寫。以圖2為算例，其中共有30個網絡節點，對算法的可行性及精確度進行實驗。

圖2 網絡拓撲圖

當k=10時，標準遺傳算法(GA)與改進后遺傳算法(GAM)所求v1到v30路徑權值對比如圖3所示。

圖3 求解結果精度對比

其中，初始種群個體數量n=100，迭代次數定為5 000，pc與pm由自適應公式得出，初始溫度T0=200。

從圖中可以看出，改進后的算法具有更高的精確度。

圖4為兩種算法在不同規模網絡中求解時間的比較。起始求解網絡規模為20個節點，150條邊，每次求得結果后，網絡拓撲圖的節點個數和邊的條數以5,50的數量遞增，直到增加到50個節點、450條邊為止。

圖4 兩種算法求解時間對比

從圖中可以看出，GAM平均時間效率高于GA，同時曲線更加平緩，說明穩定性也高于GA。

5 結束語

通過把遺傳算法與模擬退火算法相結合，文中提出了一種求解k最短路徑問題的新算法。通過對交叉率與變異率采用自適應的方式，構造了新的染色體編碼方式及適應度函數，實現了對k最短路問題的求解。仿真結果表明，該算法能夠較快較準確地找到多條最短路徑，具有較高穩定性的同時克服了遺傳算法易早熟的缺點。對求解一般復雜網絡中k最短路問題，具有廣泛的應用價值。

[1]PalmgrenM,YuanD.AshortsummaryonKshortestpath:algorithmsandapplications[EB/OL].1999.http://www.esc.auckland.ac.nz/Mason/Courses/LinkopingColCen99/kth.pdf.

[2]HoffmanW，PavleyR．AmethodofsolutionoftheNthbestpathproblem[J]．JournaloftheACM，1959，6(4):506-514．

[3] 柴登峰,張登榮.前N條最短路徑問題的算法及應用[J].浙江大學學報:工學版,2002,36(5):531-534.

[4] 袁紅濤,朱美正.K優路徑的一種求解算法與實現[J].計算機工程與應用,2004,40(6):51-53.

[5]KangT，ZhangX，WangZ，etal．Algorithmforshortestpathofmulti-objectivesbasedonkshortpathalgorithm[J]．JournalofChangzhouInstituteofTechnology，2011，24(3):25-28．

[6]WangZ，HanW，LiY．Shortestpathproblemwithmultipleshortestpaths[J]．JournalofHarbinInstituteofTechnology，2010，42(9):1428-1431．

[7] 周 明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業出版社,2001.

[8] 謝 政,李建平.網絡算法與復雜性理論[M].長沙：國防科技大學出版社，2003.

[9]AlsultannyYA,AqelMM.Patternrecognitionusingmultilayerneural-geneticalgorithm[J].Neurocomputing,2003,51:237-247.

[10] 康立山.非數值并行算法(第一冊)：模擬退火算法[M].北京:科學出版社,2000:22-38.

[11] 趙禮峰，王小龍.圖的Steiner最小樹問題的混合遺傳算法[J].計算機技術與發展,2014,24(10):110-114.

[12] 魯建業,李 琦,董蘊華,等.采用混合遺傳-模擬退火算法對DOE的直接設計[J].光電子·激光,2001,12(4):365-367.

[13]GaoErbao,LaiM.Animprovedgeneticalgorithmforthevehicleroutingproblemwithsimultaneousdeliveryandpickup[C]//Procofthe6thWuhaninternationalconferenceone-business-innovationmanagementtrack.Wuhan:[s.n.],2007:2100-2106.

[14] 王海英.MATLAB遺傳算法工具箱及應用[M].北京:北京航空航天大學出版社,2010.

A Hybrid Genetic Algorithm for SolvingkShortest Path Problem

ZHAO Li-feng,YU Wen-yu

(College of Sciences,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

The key for the genetic algorithm is coding and the need to construct the fitness function.Combined with actualkshortestpathproblem,anewchromosomecodingmethodisredefinedandanewfitnessfunctionisconstructed.Thestandardgeneticalgorithmadoptsfixedcrossoverrateandmutationrate,andexiststhedefectsoflowconvergence,prematurityandpoorstability.Therefore,animprovedadaptivegeneticalgorithmisproposed,usingtheadaptivewayforthecrossoverrateandmutationrate,theformulafordeterminingthemisconstructtoacceleratetheconvergencespeed.Atthesametime,combinedwiththeMetropolisprincipleofsimulatedannealingtochoosethereceiveroftheoffspring,thealgorithmovercomestheproblemofpremature.Thesimulationshowsthattheimprovedhybridgeneticalgorithmcansolvethekshortestpathproblem,anditissuperiortothestandardgeneticalgorithminoptimizationaccuracy,timeefficiencyandstability.

hybrid genetic algorithm;chromosome code;Metropolis principle;kshortestpath

2015-10-25

2016-03-03

時間：2016-09-18

國家自然科學基金資助項目(61070234,61071167)

趙禮峰(1959-)，男，教授，碩士研究生導師，研究方向為圖論及其在通信中的應用；于汶雨(1989-)，女，碩士研究生，研究方向為圖論及其在通信中的應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160918.1707.020.html

TP

A

1673-629X(2016)10-0032-04

10.3969/j.issn.1673-629X.2016.10.007