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

趙禮峰，于汶雨

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

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

趙禮峰，于汶雨

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

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

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

0 引 言

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

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

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

1 預(yù)備知識

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

2.1 遺傳算法基本步驟

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

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

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

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

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

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

圖1 遺傳算法流程圖

3 算法改進

3.1 染色體編碼

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

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

3.2 適應(yīng)度函數(shù)和選擇概率

(1)

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

(2)

顯然個體適應(yīng)度越大被選擇的概率越高。

3.3 交叉操作與變異操作

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

父代1：

父代2：

子代1：

子代2：

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

若變異后產(chǎn)生環(huán)路，按照交叉操作中所述進行處理。

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

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

所以文中采取自適應(yīng)的遺傳算法。根據(jù)交叉率和變異率對遺傳算法群體進化過程中的影響，設(shè)計如下公式進行自適應(yīng)調(diào)整：

pc1=0.9,pc2=0.2

(3)

pm1=0.01,pm2=0.05

(4)

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

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

3.5 對最優(yōu)個體進行模擬退火操作

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

(5)

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

3.6 算法流程

Step1:群體初始化，隨機選取n條路徑構(gòu)成群體；

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

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

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

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

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

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

Step8:判斷是否達到終止條件，若達到終止條件則輸出前k個優(yōu)秀解，否則轉(zhuǎn)Step2。

4 仿真實驗

仿真實驗環(huán)境：處理器為Intel COREi5，操作系統(tǒng)為Windows7,應(yīng)用MATLAB[14]編寫。以圖2為算例，其中共有30個網(wǎng)絡(luò)節(jié)點，對算法的可行性及精確度進行實驗。

圖2 網(wǎng)絡(luò)拓撲圖

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

圖3 求解結(jié)果精度對比

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

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

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

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

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

5 結(jié)束語

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

[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條最短路徑問題的算法及應(yīng)用[J].浙江大學學報:工學版,2002,36(5):531-534.

[4] 袁紅濤,朱美正.K優(yōu)路徑的一種求解算法與實現(xiàn)[J].計算機工程與應(yīng)用,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] 周 明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社,2001.

[8] 謝 政,李建平.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].長沙：國防科技大學出版社，2003.

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

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

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

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

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

[14] 王海英.MATLAB遺傳算法工具箱及應(yīng)用[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-)，男，教授，碩士研究生導(dǎo)師，研究方向為圖論及其在通信中的應(yīng)用；于汶雨(1989-)，女，碩士研究生，研究方向為圖論及其在通信中的應(yīng)用。

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