解旅行商問題的混沌蟻群算法

1、2005年9月系統(tǒng)工程理論與實踐第9期文章編號:100026788(20050920100205解旅行商問題的混沌蟻群算法高尚(江蘇科技大學電子信息學院,江蘇鎮(zhèn)江212003摘要:利用混沌運動的遍歷性、隨機性和規(guī)律性等特點,提出了一種求解旅行商問題的混沌蟻群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作者簡介:高尚(1972-,男,江蘇人,副教授,主要從事系統(tǒng)理論等方面的研究.1引言本世紀50年代中期創(chuàng)立了仿生學,人們從生物進化的機理中受到啟發(fā),提出了許多用以解決復雜優(yōu)化問題的新方法,如遺傳算法、進化規(guī)劃、進化策略等,蟻群優(yōu)化(Ant C olony optimization 算法是最近幾年才提出的一種新型的模擬進化算法,由意大利學者M.

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

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

7、設(shè)有m 個螞蟻,每個簡單螞蟻有以下特征:它根據(jù)以城市距離和連接邊上外激素的數(shù)量為變量的概率函數(shù)選擇下一個城(設(shè)ij (t 為t 時刻邊e (i ,j 上外激素的強度.規(guī)定螞蟻走合法路線,除非周游完成,不允許轉(zhuǎn)到已訪問城市,有禁忌表控制(設(shè)tabu k 表示第k 個螞蟻的禁忌表,tabu k (s 表示禁忌表中第s 個元素.它完成周游后,螞蟻在它每一條訪問的邊上留下外激素.初始時刻,各條路徑上的信息量相等,設(shè)ij (0=C (C 為常數(shù).螞蟻k (k =1,2,m 在運動過程中,根據(jù)各條路徑上信息量決定轉(zhuǎn)移方向,p kij (t 表示在t 時刻螞蟻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 下一步允許選擇的城市,與實際蟻群不同,人工蟻群系統(tǒng)具有記憶功能,tabu k (k =1,2,m 用以記錄螞蟻k 當前所走過的城市,集合tabu k 隨著進化過程做動態(tài)調(diào)整.ij 表示邊弧(i ,j 的能見度,用某種啟發(fā)式算法算出,一般取ij =1d ij,d ij 表示城市i 與城市j 之間的距離.表示軌跡的相對重要性,表示能見度的相對重要性,表示軌跡的持久性,1-理解為軌跡衰減度.隨著時間的推移,以前留

9、下的信息逐漸消失,用參數(shù)1-表示信息消逝程度,經(jīng)過n 個時刻,螞蟻完成一次循環(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)游一周的路徑長度,Q 常數(shù).kij=Q L k若第k 只螞蟻在本次循環(huán)經(jīng)過ij 0否則(4解TSP 的基本蟻群算法的基本步驟:步驟1nc 0,(nc 為迭代步數(shù)或搜索次數(shù)各ij 和ij 的初始化,將m 個螞蟻置于n 個頂點上;步驟2將各螞蟻的初始出發(fā)點置于當前解集中,對每個螞

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

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

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

13、111,含義為每次都是取剩下物件的最小標號.按詞典序構(gòu)造,末構(gòu)造為4321,末向量為432.序號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)換,目前無法直接寫出轉(zhuǎn)換公式,需要通過DV轉(zhuǎn)換,再經(jīng)過VC來完成.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)換是通過向量V的指針功能來確定構(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)工程理論與實踐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 的指針功能來確定構(gòu)造C ,這樣z i 與C 一一對應(yīng).31212選擇較優(yōu)解螞蟻每次周游結(jié)束后,不論螞蟻搜索到的解如何,都將賦予相應(yīng)的信息增量,比較差的解也將留下信息素,這樣就干擾后續(xù)的螞蟻進行尋優(yōu),造成大量的無效的搜索.改進的方法是,只有比較好的解才留下信息素,即只有當路徑長度小于給定的值才留下信息素.31213混沌擾動蟻群利

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

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

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

18、O+混沌初始化+混沌擾5結(jié)束語計算結(jié)果表明,利用混沌的隨機性、遍歷性及規(guī)律性等特點提出的混沌蟻群算法可以顯著提高計算效率,具有較大的實用價值.混沌信號產(chǎn)生機理簡單,具有內(nèi)在并行性,本文混沌信號取自Logistic映射,實際上混沌信號可取自其它混沌系統(tǒng),至于哪個更好,有待進一步研究.蟻群算法研究處于初期,還有許多問題值得研究,如算法的收斂性、理論依據(jù)等.但從當前的應(yīng)用效果來看這種模仿自然生物的新型系統(tǒng)尋優(yōu)思想無疑具有十分光明的前景,更多深入細致的工作還有待于進一步展開.參考文獻: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.計算機研究與發(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馬良,項培軍.螞蟻算法在組合優(yōu)化中的應(yīng)用J.管理科學學報,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張國平,王正歐,袁國林.求解一類組合優(yōu)化問題的混沌搜索法J.系統(tǒng)工程理論與實踐,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)明,唐嘉亨等.復雜函數(shù)優(yōu)化的混沌遺傳算法J.哈爾濱工程大學

24、學報,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頁第9期 航班離場排序問題的遺傳算法設(shè)計 125 大尾渦間隔的出現(xiàn) ,比如緊隨重型航班之后不安排小型航班 ; 全局最優(yōu)并不意味著航班序列固定 ,比如 , 在不影響各個分隊航班相對順序得前提下 ,隨意調(diào)整相鄰兩同類型航班的順序 ,并不

25、影響總的離場耗時 ; 隨機排序下 ,某序號航班離場時間有可能早于優(yōu)化排序中該序號航班的離場時間 ,這說明了全局最優(yōu)并 不要求步步最優(yōu) . 5 結(jié)語 本文針對航班的離場排序問題 ,建立了優(yōu)化排序的數(shù)學模型 ,并設(shè)計了求解模型的雙碼自適應(yīng)遺傳算 法 . 仿真結(jié)果表明 ,通過本文設(shè)計的算法求解相應(yīng)最小化問題 ,可有效縮減總的離場耗時 ,并能得到離場排 序問題的全局最優(yōu)解 . 參考文獻 : 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 盧開澄 . 單目標 , 多目標與整數(shù)規(guī)劃 M . 北京 : 清華大學出版社 , 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 周明 ,孫樹棟 . 遺傳算法原理及應(yīng)用 M . 北京 : 國防工業(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 頁 10 王凌 . 智能優(yōu)化算法及其應(yīng)用 M . 北京 : 清華大學出版社 ,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 高國華 ,沈林成 ,常文森 . 求解 TSP 問題的空間銳化模擬退火算法 J . 自動化學報 ,1999 ,25 (3 :425 - 428. 12 康立山 ,謝云 ,尤矢勇 ,等 . 模擬退