趙禮峰，于汶雨

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

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

趙禮峰，于汶雨

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

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

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

0 引 言

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

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

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

1 預(yù)備知識

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

2.1 遺傳算法基本步驟

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

2.2 模擬退火基本原理與Metropolis準(zhǔn)則

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

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

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

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

圖1 遺傳算法流程圖

3 算法改進(jìn)

3.1 染色體編碼

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

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

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

(1)

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

(2)

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

3.3 交叉操作與變異操作

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

父代1：

父代2：

子代1：

子代2：

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

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

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

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

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

pc1=0.9,pc2=0.2

(3)

pm1=0.01,pm2=0.05

(4)

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

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

3.5 對最優(yōu)個(gè)體進(jìn)行模擬退火操作

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

(5)

經(jīng)過交叉操作后，若子代個(gè)體適應(yīng)度變優(yōu),完全接收新解為當(dāng)前解；若子代個(gè)體惡化,則以概率p接受惡化解為新的當(dāng)前解。同時(shí)為了使每一代中優(yōu)良個(gè)體結(jié)構(gòu)不被破壞,采用精英保留策略[13],如果下一代群體中的最優(yōu)個(gè)體適應(yīng)度值小于當(dāng)前群體最優(yōu)個(gè)體適應(yīng)度值,那么用當(dāng)前群體中最優(yōu)個(gè)體或者適應(yīng)度值大于下一代最優(yōu)個(gè)體適應(yīng)度值的多個(gè)個(gè)體隨機(jī)替代下一代群體中適應(yīng)度差的相應(yīng)數(shù)量的個(gè)體，確保了當(dāng)前的最優(yōu)個(gè)體不會(huì)因?yàn)榻徊妗⒆儺惖炔僮鞫黄茐摹?/p>

3.6 算法流程

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

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

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

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

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

Step6:按照模擬退火Metropolis準(zhǔn)則對交叉后的個(gè)體是否接收進(jìn)行操作；

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

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

4 仿真實(shí)驗(yàn)

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

圖2 網(wǎng)絡(luò)拓?fù)鋱D

當(dāng)k=10時(shí)，標(biāo)準(zhǔn)遺傳算法(GA)與改進(jìn)后遺傳算法(GAM)所求v1到v30路徑權(quán)值對比如圖3所示。

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

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

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

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

圖4 兩種算法求解時(shí)間對比

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

5 結(jié)束語

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

[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].浙江大學(xué)學(xué)報(bào):工學(xué)版,2002,36(5):531-534.

[4] 袁紅濤,朱美正.K優(yōu)路徑的一種求解算法與實(shí)現(xiàn)[J].計(jì)算機(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].長沙：國防科技大學(xué)出版社，2003.

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

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

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

[12] 魯建業(yè),李 琦,董蘊(yùn)華,等.采用混合遺傳-模擬退火算法對DOE的直接設(shè)計(jì)[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].北京:北京航空航天大學(xué)出版社,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

時(shí)間：2016-09-18

國家自然科學(xué)基金資助項(xiàng)目(61070234,61071167)

趙禮峰(1959-)，男，教授，碩士研究生導(dǎo)師，研究方向?yàn)閳D論及其在通信中的應(yīng)用；于汶雨(1989-)，女，碩士研究生，研究方向?yàn)閳D論及其在通信中的應(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