遺傳模擬退火算法

——黑龍江TSP問題

Genetic Simulated Annealing Algorithm： Heilongjiang TSP Problem

姚君 YAO Jun

（黑龍江科技大學(xué)理學(xué)院，哈爾濱150022）

（College of Science，Heilongjiang University of Science and Technology，Harbin 150022，China）

摘要：以黑龍江省29個(gè)城市構(gòu)造TSP問題，通過對實(shí)驗(yàn)數(shù)據(jù)的分析，得出了遺傳模擬退火算法在求解精度上優(yōu)于遺傳算法或模擬退火算法。遺傳模擬退火算法利用了模擬退火算法局部精確的求解能力補(bǔ)充了遺傳算法在局部求解不夠精確的弊端，從而加快了求解TSP問題的效率，同時(shí)，又將蟻群算法和遺傳模擬退火算法做比較，從結(jié)果可以看出遺傳模擬退火算法求解效果較好。

Abstract： Based on the analysis of experimental data of the urban structure TSP problem of 29 cities in Heilongjiang Province， it is concluded that genetic simulated annealing algorithm is better than genetic algorithm or simulated annealing algorithm in solving the precision. Genetic Simulated Annealing Algorithm （GA）， which utilizes the local exact solution ability of the simulated annealing algorithm，complements the drawbacks of the genetic algorithm which is not accurate enough to solve the problem. The results show that the genetic simulated annealing algorithm is effective.

關(guān)鍵詞：遺傳模擬退火算法；TSP問題；蟻群算法

Key words： genetic simulated annealing algorithm；TSP problem；ant colony algorithm

中圖分類號：O1-0 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2016）36-0206-03

0 引言

傳統(tǒng)的遺傳算法容易過早收斂，而且在搜索過程中有可能搜索到最優(yōu)解然后又發(fā)散出去的現(xiàn)象。模擬退火算法在解的質(zhì)量與求解時(shí)間長之間存在矛盾，為得到一個(gè)好的近似最優(yōu)解，需要進(jìn)行反復(fù)迭代運(yùn)算，當(dāng)問題的規(guī)模不可避免地增大時(shí)，缺乏可行的解決途徑。遺傳算法和模擬退火算法的直接互補(bǔ)性體現(xiàn)在：遺傳算法雖把握總體的能力較強(qiáng)，但局部搜索能力較差；模擬退火算法具有較強(qiáng)的局部搜索能力，為了克服遺傳算法和模擬退火算法各自的缺點(diǎn)，將遺傳算法和模擬退火算法相互結(jié)合，取長補(bǔ)短，這就形成了模擬退火遺傳算法，簡稱GASA。

1 黑龍江旅行商問題

TSP問題是比較典型的組合優(yōu)化問題，因其應(yīng)用范圍廣，研究價(jià)值高，所以成為學(xué)者們研究重點(diǎn)，求解方法也有許多。但是一些常規(guī)的算法往往存在一些弊端，如后期計(jì)算不夠精確，容易造成過早收斂等。TSP問題是研究算法性能的經(jīng)典問題，具有廣泛的應(yīng)用背景。

選取黑龍江省29個(gè)城市構(gòu)造TSP問題，即求得一條將黑龍江省29個(gè)城市旅行一遍，且每個(gè)城市有且僅經(jīng)過一次的最短路線。表1是黑龍江省29個(gè)城市的坐標(biāo)。

2 算法比較

實(shí)驗(yàn)過程中，染色體的長度L等于城市個(gè)數(shù)，即：29。種群的規(guī)模pop-size定為100，各個(gè)參數(shù)確定如下：將退火過程參數(shù)a=0.9，交叉概率和變異概率Pc=0.5，Pm=0.1，迭代結(jié)束的依據(jù)是q=100。單個(gè)的遺傳算法和模擬退火法里用到的參數(shù)也這樣設(shè)定。

首先將黑龍江省29個(gè)城市的坐標(biāo)放入一個(gè)數(shù)組中，記為：citys=[1 544 636；2 532 658；3 624 518；4 815 631；5 636 501；6 715 202；7 435 912；8 728 657；9 720 1016；10 1014 729；11 647 1022；12 517 1057；13 532 1150；14 435 936；15 829 451；16 421 928；17 720 357；18 548 1049；19 522 615；20 514 755；21 638 1111；22 425 1111；23 638 659；24 659 801；25 739 1230；26 455 711；27 838 607；28 742 856；29 604 558]。

2.1 運(yùn)用遺傳算法

遺傳算法，簡稱GA，是以自然選擇理論和遺傳變異理論為基礎(chǔ)的仿生學(xué)的概率性搜索迭代算法。

遺傳算法求解TSP的算法描述如下：

步驟1 設(shè)定種群的規(guī)模、遺傳變異概率pm、遺傳交叉概率pc，初始化當(dāng)前代數(shù)g=0；

步驟2 使用算法，隨機(jī)產(chǎn)生一個(gè)初代種群，在將種群中所有個(gè)體的適應(yīng)度計(jì)算出來；

步驟3 根據(jù)輪盤賭策略選擇父代1和父代2；

步驟4 產(chǎn)生兩個(gè)0～1的隨機(jī)數(shù)p1和p2；

步驟5 若p1

步驟6 若p2

步驟7 若產(chǎn)生子代種群總數(shù)等于規(guī)定最大總?cè)簜€(gè)體量，就向下順序執(zhí)行步驟8，不然就跳到步驟3；

步驟8 計(jì)算新產(chǎn)生種群的適應(yīng)度（遍歷的距離），并用新產(chǎn)生的子代作為新的父代；

步驟9 check目前狀態(tài)是否達(dá)到結(jié)束條件，如果達(dá)到，則結(jié)束迭代計(jì)算并輸出得到的最優(yōu)解，并跳轉(zhuǎn)到步驟3；

最優(yōu)解為：R1=[1 19 2 26 20 16 7 14 22 12 18 13 25 21 11 9 28 24 8 4 10 27 15 6 17 5 3 29 23]；

程序求解結(jié)果如圖1。

即最佳路線為：哈爾濱—雙城—阿城—五?！兄尽獙幇病Ａ帧档そ椃液印u西—七臺河—密山—同江—雙鴨山—佳木斯—鶴崗—伊春—鐵力—海倫—北安—黑河—五大連池—訥河—富錦—齊齊哈爾—大慶—安達(dá)—肇東—綏化—哈爾濱；

最短路徑為：3408.6。

2.2 運(yùn)用模擬退火算法

模擬退火算法，簡稱SA，通常能夠求得局部的最優(yōu)解，它的根本思想源自固態(tài)物體降溫過程，將該過程引入到求解組合的優(yōu)化問題從而出現(xiàn)這個(gè)算法。

模擬退火算法的偽代碼如下：

①隨機(jī)生成一個(gè)初始解X0，令Xbest=X0，并計(jì)算目標(biāo)函數(shù)值E（X0）；

②設(shè)置初始的溫度T（0）=T0，迭代次數(shù) i=l：

Do whileT（i）>Tmin

for j=1 to k （k為循環(huán)次數(shù)和城市規(guī)模有關(guān)）

對當(dāng)前最優(yōu)解Xbest鄰域函數(shù)，產(chǎn)生一新的解Xnew，計(jì)算新得到的目標(biāo)函數(shù)值E（Xnew），并計(jì)算判定函數(shù)的增量ΔE=E（Xnew）-E（Xbest）。

如果ΔE<0，則Xbest=Xnew。

③輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束。

最優(yōu)解為：R2=[1 23 29 3 5 17 6 15 10 27 4 8 24 28 9 11 21 25 13 22 12 18 14 16 7 20 26 2 19]；

程序求解結(jié)果如圖2。

即最佳路線為：哈爾濱—綏化—肇東—安達(dá)—大慶—齊齊哈爾—富錦—訥河—黑河—五大連池—北安—海倫—鐵力—伊春—鶴崗—佳木斯—雙鴨山—同江—密山—綏芬河—雞西—七臺山—牡丹江—寧安—海林—尚志—五?！⒊恰p城—哈爾濱；

最短路程為：3365.3。

2.3 運(yùn)用遺傳模擬退火算法

遺傳算法雖把握總體的能力較強(qiáng)，但局部搜索能力較差；模擬退火算法具有較強(qiáng)的局部搜索能力，因此可以將遺傳算法和模擬退火算法相互結(jié)合，取長補(bǔ)短。為了克服遺傳算法和模擬退火算法各自的缺點(diǎn)，發(fā)揮它們的優(yōu)勢，將遺傳算法和模擬退火算法結(jié)合起來，形成了模擬退火遺傳算法，簡稱GASA。

GASA算法求解TSP問題流程：

Step1.給定算法參數(shù)：初始溫度t0，終止溫度tf，溫度衰減因子α，種群規(guī)模Nc，交叉概率Pc，變異概率p，并初始化種群S；

Step2.在當(dāng)前溫度tk下，執(zhí)行以下操作：

①對種群中各個(gè)個(gè)體進(jìn)行評價(jià)，即計(jì)算所有個(gè)體的適應(yīng)度vali；e（i，1：n）=s（i），e（i，n+1）=val（i）；

②執(zhí)行GA算法的選擇處理，采用淘汰算法判定是否淘汰惡性解，對當(dāng)前種群進(jìn)行選擇；

③運(yùn)行算法中的交叉流程，采用部分匹配交叉算子，附帶保優(yōu)操作，即執(zhí)行交叉操作后所有個(gè)體的適應(yīng)度val（i），如果val（i）>e（i，n+1），則令e（i，n+1）=val（i）；

④執(zhí)行算法中的變異流程，采用倒位變異算子，附帶保優(yōu)操作；

⑤由上一步得到初代群體，然后對群體中的個(gè)體使用模擬退火操作，獲得子代個(gè)體；

⑥利用SA算法的狀態(tài)產(chǎn)生函數(shù)獲取新的個(gè)體；

⑦依據(jù)概率exp（-Δf/tk）>random[0，1]接受新個(gè)體；重復(fù)⑥和⑦直至系統(tǒng)達(dá)到溫度的平衡狀態(tài)；

Step3.按一定方式降溫，tk=αtk-1；

Step4.若tk

最優(yōu)解為：R4 = [1 2 26 20 7 16 14 18 12 22 13 25 21 11 9 28 24 23 8 4 27 10 15 6 17 5 3 29 19]；

程序求解結(jié)果如圖3。

即最佳路線為：哈爾濱—阿城—五常—尚志—海林—安寧—牡丹江—七臺河—雞西—綏芬河—密山—同江—雙鴨山—佳木斯—鶴崗—阿城—鐵力—綏化—海倫—北安—五大連池—黑河—訥河—富錦—齊齊哈爾—大慶—安達(dá)—肇東—雙城—哈爾濱；

最短路程為：3316.6。

可以看出，將模擬退火算法優(yōu)良的局部求解能力和遺傳算法優(yōu)良的全局求解能力進(jìn)行有機(jī)結(jié)合的遺傳模擬退火算法的結(jié)果優(yōu)于單獨(dú)使用遺傳算法和模擬退火算法的結(jié)果。

3 蟻群算法與遺傳模擬退火算法對比

運(yùn)用蟻群算法求解此問題的結(jié)果如下：

最優(yōu)解為： R3= [1 19 29 3 5 17 6 15 10 27 4 8 23 24 28 9 25 21 11 18 12 13 22 14 16 7 20 26 2]；

程序求解結(jié)果如圖4。

即最優(yōu)路線為：哈爾濱—雙城—肇東—安達(dá)—大慶—齊齊哈爾—富錦—訥河—黑河—五大連池—北安—海倫—綏化—鐵力—伊春—鶴崗—同江—雙鴨山—佳木斯—七里河—雞西—密山—綏芬河—牡丹江—安寧—海林—尚志—五?！⒊恰枮I；

最短路程為：3341.9。

由實(shí)驗(yàn)結(jié)果可以看出，在該問題的求解過程中，蟻群算法的求解結(jié)果優(yōu)于遺傳算法和模擬退火算法的求解結(jié)果，但還是不如遺傳模擬退火算法的求解效果。

將四種算法結(jié)果進(jìn)行對比，如表2。

通過對比四種算法求解黑龍江省29城市的問題的結(jié)果可以看出：

雖然GA算法、SA算法，單獨(dú)求解已經(jīng)可以得到很好的結(jié)果。但從結(jié)果中可以看到，蟻群算法的求解結(jié)果卻優(yōu)于GA和SA，將遺傳算法和模擬退火算法兩種算法的結(jié)合而成的GASA算法，在求解該問題時(shí)，得到的結(jié)果又優(yōu)于蟻群算法，是最好的?？梢妼⑦z傳算法和模擬退火算法結(jié)合起來使用可以有效提高解的質(zhì)量，可以更有效的求解TSP問題。但是在求解過程中參數(shù)的給定，會(huì)很大程度上影響求解結(jié)果；遺傳算法的交叉、變異過程也有很大的改進(jìn)空間；所以，在接下來的主要研究中，應(yīng)該對這些問題進(jìn)行思考，從而進(jìn)一步提高遺傳模擬退火算法的性能。

參考文獻(xiàn)：

[1]劉錦.混合遺傳算法和模擬退火算法在TSP中的應(yīng)用研究[D].廣東省：華南理工大學(xué)，2014.

[2]朱成娟.遺傳算法的改進(jìn)及其若干應(yīng)用[D].河北省：燕山大學(xué)，2006.

[3]劉曉路.改進(jìn)的遺傳算法及其在TSP問題中的應(yīng)用與研究[D].黑龍江：哈爾濱理工大學(xué)，2011.

[4]龐峰.模擬退火算法的原理及算法在優(yōu)化問題上的應(yīng)用[D].吉林：吉林大學(xué)，2005.

[5]張文修.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安：西安交通大學(xué)出版社，2003：90-157.

[6]王凌著.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2001：66-120.