解旅行商問(wèn)題的混沌蟻群算法

1、2005年9月系統(tǒng)工程理論與實(shí)踐第9期文章編號(hào):100026788(20050920100205解旅行商問(wèn)題的混沌蟻群算法高尚(江蘇科技大學(xué)電子信息學(xué)院,江蘇鎮(zhèn)江212003摘要:利用混沌運(yùn)動(dòng)的遍歷性、隨機(jī)性和規(guī)律性等特點(diǎn),提出了一種求解旅行商問(wèn)題的混沌蟻群S olving T raveling Salesman Problem by Chaos AntC olony Optimization Alg orithmG AO Shang(School of electronics and in formation ,Jiangsu University of Science and T echn

2、ology ,Zhenjiang 212003,China Abstract :By use of the properties of erg odicity ,randomicity ,and regularity of chaos ,a chaos ant colonyoptimization (C AC O alg orithm is proposed to s olve traveling salesman problem.The basic principle of CPS O alg orithm is that chaos initialization is adopted to

3、 im prove individual quality and chaos perturbation is utilized to av oid the search being trapped in local optimum.C om pared with the standard G A and simulated annealing alg orithm ,simulation results show that chaos ant colony optimization is a sim ple and effective alg orithm.K ey w ords :ant c

4、olony alg orithm ;chaos ;chaos perturbation ,chaos ant colony optimization alg orithm ,traveling salesman problem收稿日期:2004209216作者簡(jiǎn)介:高尚(1972-,男,江蘇人,副教授,主要從事系統(tǒng)理論等方面的研究.1引言本世紀(jì)50年代中期創(chuàng)立了仿生學(xué),人們從生物進(jìn)化的機(jī)理中受到啟發(fā),提出了許多用以解決復(fù)雜優(yōu)化問(wèn)題的新方法,如遺傳算法、進(jìn)化規(guī)劃、進(jìn)化策略等,蟻群優(yōu)化(Ant C olony optimization 算法是最近幾年才提出的一種新型的模擬進(jìn)化算法,由意大利學(xué)者M(jìn).

5、D orig o 等人首先提出來(lái)1,用蟻群在搜索食物源的過(guò)程中所體現(xiàn)出來(lái)的尋優(yōu)能力來(lái)解決一些離散系統(tǒng)優(yōu)化中困難問(wèn)題.已經(jīng)用該方法求解了旅行商問(wèn)題、指派問(wèn)題、調(diào)度問(wèn)題等,取得了一系列較好的實(shí)驗(yàn)結(jié)果2,3.蟻群算法在電信路由優(yōu)化4、數(shù)據(jù)聚類分析5、數(shù)據(jù)分類規(guī)則提取6等方面效果也很好.混沌是自然界廣泛存在的一種非線性現(xiàn)象,它看似混沌,卻有著精致的內(nèi)在結(jié)構(gòu),具有“隨機(jī)性”、“遍歷性”及“規(guī)律性”等特點(diǎn),對(duì)初始條件極度敏感,能在一定范圍內(nèi)按其自身規(guī)律不重復(fù)地遍歷所有狀態(tài),利用混沌運(yùn)動(dòng)的這些性質(zhì)可以進(jìn)行優(yōu)化搜索7,8.根據(jù)混沌特性,融入到其它算法中,提出了一系列新的優(yōu)化方法,如混沌遺傳算法9.本文將混沌融

6、入蟻群算法中,提出混沌蟻群(Chaos Ant C olony Optimization ,簡(jiǎn)稱C AC O 算法,利用混沌初始化進(jìn)行改善個(gè)體質(zhì)量和利用混沌擾動(dòng)避免搜索過(guò)程陷入局部極值.解旅行商問(wèn)題的仿真結(jié)果表明,C AC O 算法較與其他算法比較,效果比較好.2解旅行商問(wèn)題的基本蟻群算法旅行商問(wèn)題(T raveling Salesman Problem ,簡(jiǎn)稱TSP 是運(yùn)籌學(xué)、組合優(yōu)化等領(lǐng)域中一個(gè)著名的難題,由于其N(xiāo)P 難題性質(zhì),迄今尚未能徹底解決.目前求解TSP 問(wèn)題的主要方法有模擬退火算法1012,遺傳算法13,14,啟發(fā)式搜索法,H opfield 神經(jīng)網(wǎng)絡(luò)算法15,蟻群算法1,2等.

7、設(shè)有m 個(gè)螞蟻,每個(gè)簡(jiǎn)單螞蟻有以下特征:它根據(jù)以城市距離和連接邊上外激素的數(shù)量為變量的概率函數(shù)選擇下一個(gè)城(設(shè)ij (t 為t 時(shí)刻邊e (i ,j 上外激素的強(qiáng)度.規(guī)定螞蟻?zhàn)吆戏肪€,除非周游完成,不允許轉(zhuǎn)到已訪問(wèn)城市,有禁忌表控制(設(shè)tabu k 表示第k 個(gè)螞蟻的禁忌表,tabu k (s 表示禁忌表中第s 個(gè)元素.它完成周游后,螞蟻在它每一條訪問(wèn)的邊上留下外激素.初始時(shí)刻,各條路徑上的信息量相等,設(shè)ij (0=C (C 為常數(shù).螞蟻k (k =1,2,m 在運(yùn)動(dòng)過(guò)程中,根據(jù)各條路徑上信息量決定轉(zhuǎn)移方向,p kij (t 表示在t 時(shí)刻螞蟻k 由位置i 轉(zhuǎn)移到位置j 的概率,p kij=

8、ij (t ij (t s allowedkis (t is (t if j allowed kotherwise(1其中,allowed k =0,1,n -1-tabu k 表示螞蟻k 下一步允許選擇的城市,與實(shí)際蟻群不同,人工蟻群系統(tǒng)具有記憶功能,tabu k (k =1,2,m 用以記錄螞蟻k 當(dāng)前所走過(guò)的城市,集合tabu k 隨著進(jìn)化過(guò)程做動(dòng)態(tài)調(diào)整.ij 表示邊弧(i ,j 的能見(jiàn)度,用某種啟發(fā)式算法算出,一般取ij =1d ij,d ij 表示城市i 與城市j 之間的距離.表示軌跡的相對(duì)重要性,表示能見(jiàn)度的相對(duì)重要性,表示軌跡的持久性,1-理解為軌跡衰減度.隨著時(shí)間的推移,以前留

9、下的信息逐漸消失,用參數(shù)1-表示信息消逝程度,經(jīng)過(guò)n 個(gè)時(shí)刻,螞蟻完成一次循環(huán),各路徑上信息量要根據(jù)以下式做調(diào)整:ij (t +n =ij (t +ij ,(2ij =mk =1kij .(3kij 表示第k 只螞蟻在本次循環(huán)中留在路徑上ij 的信息量,ij 表示本次循環(huán)中路徑ij 上的信息量增量,L k表示第k 只螞蟻環(huán)游一周的路徑長(zhǎng)度,Q 常數(shù).kij=Q L k若第k 只螞蟻在本次循環(huán)經(jīng)過(guò)ij 0否則(4解TSP 的基本蟻群算法的基本步驟:步驟1nc 0,(nc 為迭代步數(shù)或搜索次數(shù)各ij 和ij 的初始化,將m 個(gè)螞蟻置于n 個(gè)頂點(diǎn)上;步驟2將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集中,對(duì)每個(gè)螞

10、蟻k (k =1,2,m ,按概率p kij 移至下一頂點(diǎn)j ,將頂點(diǎn)j 置于當(dāng)前解集;步驟3計(jì)算各螞蟻的路徑長(zhǎng)度L k (k =1,2,m ,記錄當(dāng)前的最好解;步驟4按更新方程修改軌跡強(qiáng)度;步驟5nc nc +1;步驟6若nc <預(yù)定的迭代次數(shù)且無(wú)退化行為(即找到的都是相同解則轉(zhuǎn)步驟2;步驟7輸出目前最好解.3混沌蟻群算法311混沌及運(yùn)動(dòng)特性101第9期解旅行商問(wèn)題的混沌蟻群算法目前對(duì)混沌尚無(wú)嚴(yán)格的定義,一般將由確定性方程得到的具有隨機(jī)性的運(yùn)動(dòng)狀態(tài)稱為混沌.Logistic 映射就是一個(gè)典型的混沌系統(tǒng),迭代公式如下:z i+1=z i(1-z i,i=0,1,2,(2,4,(5式中為控

11、制參量,當(dāng)=4,0z01,Logistic完全處于混沌狀態(tài).利用混沌運(yùn)動(dòng)特性可以進(jìn)行優(yōu)化搜索,其基本思想是首先產(chǎn)生一組與優(yōu)化變量相同數(shù)目的混沌變量,用類似載波的方式將混沌引入優(yōu)化變量使其呈現(xiàn)混沌狀態(tài),同時(shí)把混沌運(yùn)動(dòng)的遍歷范圍放大到優(yōu)化變量的取值范圍,然后直接利用混沌變量搜索7,8.由于混沌運(yùn)動(dòng)具有隨機(jī)性、遍歷性、對(duì)初始條件的敏感性等特點(diǎn),基于混沌的搜索技術(shù)無(wú)疑會(huì)比其它隨機(jī)搜索更具優(yōu)越性.本文將利用=4時(shí)的混沌特性,取(5式的Logistic映射為混沌信號(hào)發(fā)生器. 312基本蟻群算法改進(jìn)31211混沌初始化表114排列的DVC表蟻群算法初始化時(shí),各路徑的信息素取相同值,讓螞蟻以等概率選擇路徑,這

12、樣使螞蟻很難在短時(shí)間內(nèi)從大量的雜亂無(wú)章的路徑中,找出一條較好的路徑,所以收斂速度較慢.假如初始化時(shí)就給出啟發(fā)性的信息量,可以加快收斂速度.改進(jìn)的方法是利用混沌運(yùn)動(dòng)的遍歷性,進(jìn)行混沌初始化,每個(gè)混沌量對(duì)應(yīng)于一條路徑,產(chǎn)生大量的路徑(如100條,從中選擇比較優(yōu)的(如30條,使這些路徑留下信息素(與路徑長(zhǎng)度和成反比,各路徑的信息量就不同,以此引導(dǎo)螞蟻進(jìn)行選擇路徑. 每個(gè)混沌量對(duì)應(yīng)于一條路徑是利用全排列構(gòu)造的理論16.首先以(1,2,3,4的全排列為例,討論其構(gòu)造,給出轉(zhuǎn)換算法.所有不同排列的總計(jì)數(shù)為4!=24,其構(gòu)造按詞典序,則構(gòu)造的第一位元素取最小標(biāo)號(hào),以后各位依次增大,1234是首構(gòu)造,首向量是

13、111,含義為每次都是取剩下物件的最小標(biāo)號(hào).按詞典序構(gòu)造,末構(gòu)造為4321,末向量為432.序號(hào)D、向量V和構(gòu)造C就構(gòu)成了DVC表,如表1所示.由DVC表可知,D、V和C之間是有關(guān)系等,它們之間有DV、VD、VC、CV,DC,CD六種轉(zhuǎn)換,我們關(guān)心的DC轉(zhuǎn)換,目前無(wú)法直接寫(xiě)出轉(zhuǎn)換公式,需要通過(guò)DV轉(zhuǎn)換,再經(jīng)過(guò)VC來(lái)完成.DV轉(zhuǎn)換公式如下:D0=Dv i=D i-1(n-i!D i=D i-1-(v i-1(n-i!i=1,2,n-1(6VC轉(zhuǎn)換是通過(guò)向量V的指針功能來(lái)確定構(gòu)造C.如V=v1v2v3=231,則有v1=21234C1=2v2=3134C2=4v1=113C3=1C4=3C=C1C

14、2C3C4=2413由公式(5產(chǎn)生混沌量zi(0zi1,則D0=n!zi,代入公式(6,令d1=nz i得到:201系統(tǒng)工程理論與實(shí)踐2005年9月v 1=d 1d i =(n -i +1(d i -1-v i -1+1i =2,3,n -1v i =d i (7再由V 的指針功能來(lái)確定構(gòu)造C ,這樣z i 與C 一一對(duì)應(yīng).31212選擇較優(yōu)解螞蟻每次周游結(jié)束后,不論螞蟻搜索到的解如何,都將賦予相應(yīng)的信息增量,比較差的解也將留下信息素,這樣就干擾后續(xù)的螞蟻進(jìn)行尋優(yōu),造成大量的無(wú)效的搜索.改進(jìn)的方法是,只有比較好的解才留下信息素,即只有當(dāng)路徑長(zhǎng)度小于給定的值才留下信息素.31213混沌擾動(dòng)蟻群利

15、用了正反饋原理,在一定程度上加快了進(jìn)化進(jìn)程,但也存在一些缺陷,如出現(xiàn)停滯現(xiàn)象,陷入局部最優(yōu)解.改進(jìn)的措施加入混沌擾動(dòng),在調(diào)整信息量,在加入混沌擾量,以使解跳出局部極值區(qū)間.公式(2修改為:ij (t +n =ij (t +ij +qZ ij ,(8其中,Z ij 為混沌變量,由公式(5迭代得到;q 為系數(shù).313混沌蟻群算法改進(jìn)后的解TSP 問(wèn)題的混沌蟻群算法如下:步驟1nc 0,(nc 為迭代步數(shù)或搜索次數(shù),混沌初始化,調(diào)整各路徑信息素,將m 個(gè)螞蟻置于n 個(gè)頂點(diǎn)上;步驟2將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集中,對(duì)每個(gè)螞蟻k (k =1,2,m ,按概率p kij 移至下一頂點(diǎn)j ,將頂點(diǎn)j 置

16、于當(dāng)前解集;步驟3計(jì)算各螞蟻的路徑長(zhǎng)度L k (k =1,2,m ,記錄當(dāng)前的最好解;步驟4對(duì)路徑長(zhǎng)度L k 小于給定值的路徑,按更新方程(8修改軌跡強(qiáng)度;步驟5nc nc +1;步驟6若nc <預(yù)定的迭代次數(shù)且無(wú)退化行為(即找到的都是相同解則轉(zhuǎn)步驟2;步驟7輸出目前最好解.4算法測(cè)試圖1用混沌蟻群算法解CTSP 最好的解為了檢驗(yàn)算法的有效性,來(lái)解決中國(guó)31個(gè)直轄市和省會(huì)城市的CTSP 問(wèn)題,數(shù)據(jù)來(lái)源于文獻(xiàn)12和pr76.tsp (TSP LI B 提供的最好解為108159.模擬退火算法采用文獻(xiàn)12的算法,起始溫度T =100000,終止溫度T 0=1,退火速度=0199;遺傳算法程序

17、采用MAT LAB 的遺傳算法工具箱17,參數(shù)如下:染色體個(gè)數(shù)N =30,交叉概率P c =012,變異概率P m =015,迭代次數(shù)100;混沌蟻群算法參數(shù):=115,m =30,=2,=019,為了說(shuō)明混沌初始化的優(yōu)點(diǎn),與隨機(jī)初始化也作了比較,每種算法運(yùn)行50次,結(jié)果如表2所示.從中可以看出基本蟻群算法上加入混沌初始化或混沌擾動(dòng)后,效果比較好,同時(shí)加入混沌初始化或混沌擾動(dòng)的混沌蟻群算法的效果更好.混沌蟻群算法解CTSP 最好的解如圖1所示,總路程為15383km.301第9期解旅行商問(wèn)題的混沌蟻群算法401系統(tǒng)工程理論與實(shí)踐2005年9月表2結(jié)果比較CTSP pr76.tsp優(yōu)化方法AC

18、O+混沌初始化+混沌擾5結(jié)束語(yǔ)計(jì)算結(jié)果表明,利用混沌的隨機(jī)性、遍歷性及規(guī)律性等特點(diǎn)提出的混沌蟻群算法可以顯著提高計(jì)算效率,具有較大的實(shí)用價(jià)值.混沌信號(hào)產(chǎn)生機(jī)理簡(jiǎn)單,具有內(nèi)在并行性,本文混沌信號(hào)取自Logistic映射,實(shí)際上混沌信號(hào)可取自其它混沌系統(tǒng),至于哪個(gè)更好,有待進(jìn)一步研究.蟻群算法研究處于初期,還有許多問(wèn)題值得研究,如算法的收斂性、理論依據(jù)等.但從當(dāng)前的應(yīng)用效果來(lái)看這種模仿自然生物的新型系統(tǒng)尋優(yōu)思想無(wú)疑具有十分光明的前景,更多深入細(xì)致的工作還有待于進(jìn)一步展開(kāi).參考文獻(xiàn):1C olorni A,D orig o M,Maniezzo V.An investigation of s ome

19、 properties of an ant alg orithmA.Proc.of the Parallel ProblemS olving from Nature C on ference(PPS N92C.Brussels,Belgium:E lsevier Publishing,1992,509-520.2吳慶洪,張紀(jì)會(huì),徐心和.具有變異特征的蟻群算法J.計(jì)算機(jī)研究與發(fā)展,1999,36(10:1240-1245.W U Qinghong,ZH ANG Jihui,X U X inhe.Ant colony alg orithm with mutation featuresJ.Journ

20、al of C om puter Research& Development,1999,36(10:1240-1245.3馬良,項(xiàng)培軍.螞蟻算法在組合優(yōu)化中的應(yīng)用J.管理科學(xué)學(xué)報(bào),2001,4(2:32-37.M A Liang,XI ANG Peijun.Applications of the ant alg orithm to combinatorial optimizationJ.Journal of Management Sciences in China,2001,4(2:32-37.4G unes M,S orges U,Bouazizi I.ARA the ant col

21、ony based routing alg orithm for M ANETsA.Proceedings International C on ferenceon Parallel Processing W orkshopsC.Uuncouver,B C,Canada,2002:79-85.5Lumer E,Faieta B.Diversity and adaptation in populations of clustering antsA.Proc of the3C on f On S imulation of AdaptiveBehaviorC.MIT Press,1994:499-5

22、08.6Parpinelli R S,Lopes H S,Freitas.Data M ining with an ant colony optimization alg orithmJ.IEEE T ransactions on Ev olutionaryC om putation,2002,6(4:321-332.7李兵,蔣慰孫.混沌優(yōu)化方法及其應(yīng)用J.控制理論與應(yīng)用,1997,14(4:613-615.LI Bing,J I ANG Weisun.Chaos optimization method and its applicationJ.C ontrol Theory and Appl

23、ications,1997,14(4:613-615.8張國(guó)平,王正歐,袁國(guó)林.求解一類組合優(yōu)化問(wèn)題的混沌搜索法J.系統(tǒng)工程理論與實(shí)踐,2001,21(5:102-105.ZH ANG G uoping,W ANG Zheng ou,Y UAN G uolin.A chaotic search method for a class of combinatorial optimization problemsJ.Systems Engineering Theory and Practice,2001,21(5:102-105.9唐巍,郭鎮(zhèn)明,唐嘉亨等.復(fù)雜函數(shù)優(yōu)化的混沌遺傳算法J.哈爾濱工程大學(xué)

24、學(xué)報(bào),2000,21(5:1-5.T ANG Wei,G UO Zhenming,T ANG Jiaheng,et al.Optimization com plex functions by chaos genetic alg orithmJ.Journal of Harbin Engineering University,2000,21(5:1-5.(下轉(zhuǎn)第125頁(yè)第9期 航班離場(chǎng)排序問(wèn)題的遺傳算法設(shè)計(jì) 125 大尾渦間隔的出現(xiàn) ,比如緊隨重型航班之后不安排小型航班 ; 全局最優(yōu)并不意味著航班序列固定 ,比如 , 在不影響各個(gè)分隊(duì)航班相對(duì)順序得前提下 ,隨意調(diào)整相鄰兩同類型航班的順序 ,并不

25、影響總的離場(chǎng)耗時(shí) ; 隨機(jī)排序下 ,某序號(hào)航班離場(chǎng)時(shí)間有可能早于優(yōu)化排序中該序號(hào)航班的離場(chǎng)時(shí)間 ,這說(shuō)明了全局最優(yōu)并 不要求步步最優(yōu) . 5 結(jié)語(yǔ) 本文針對(duì)航班的離場(chǎng)排序問(wèn)題 ,建立了優(yōu)化排序的數(shù)學(xué)模型 ,并設(shè)計(jì)了求解模型的雙碼自適應(yīng)遺傳算 法 . 仿真結(jié)果表明 ,通過(guò)本文設(shè)計(jì)的算法求解相應(yīng)最小化問(wèn)題 ,可有效縮減總的離場(chǎng)耗時(shí) ,并能得到離場(chǎng)排 序問(wèn)題的全局最優(yōu)解 . 參考文獻(xiàn) : 1 Bolender M A. Scheduling and Control Strategies for the Departure Problem in Air Traffic Control D . Amer

26、ica : University of Cincinnati , 2000. 2 盧開(kāi)澄 . 單目標(biāo) , 多目標(biāo)與整數(shù)規(guī)劃 M . 北京 : 清華大學(xué)出版社 , 1999. 3 Srinivas L ,Patnaik M. Adaptive probabilities of crossover and mutation in genetic algorithmJ . IEEE Trans. on SMC , 1994 ,24 (4 :656 - 667. 4 周明 ,孫樹(shù)棟 . 遺傳算法原理及應(yīng)用 M . 北京 : 國(guó)防工業(yè)出版社 , 2002. Lu Kaicheng. Single2obj

27、ective , Multi2objective and Integer Programming M . Beijing : Tsinghua University Press , 1999. Zhou Ming ,Sun Shudong. Genetic Algorithms Theory and Applications M . Beijing : Defence Industry Press , 2002. traveling salesman problemJ . Acta Automatica Sinica , 1999 ,25 (3 :425 - 428. Applications

28、 , 2002 ,38 (8 :58 - 60. 17 (9 :52 - 55. HUA Shan. Computer Science MathM . Harbin : Harbin Shipbuilding Institute Press , 1994 :97 - 101. 2002 ,18 (8 :52 - 54. ( 上接第 104 頁(yè) 10 王凌 . 智能優(yōu)化算法及其應(yīng)用 M . 北京 : 清華大學(xué)出版社 ,2001 :195 - 211. WANGLing. Intelligent Optimization Algorithms with ApplicationsM . Beijing : Tsinghua University Press , 2001 :195 - 211. G AO Guohua , SHEN Lincheng , CHANG Wensen. Using simulated annealing algorithm with search space sharpening to solve 11 高國(guó)華 ,沈林成 ,常文森 . 求解 TSP 問(wèn)題的空間銳化模擬退火算法 J . 自動(dòng)化學(xué)報(bào) ,1999 ,25 (3 :425 - 428. 12 康立山 ,謝云 ,尤矢勇 ,等 . 模擬退