求解旅行商問(wèn)題的蟻群遺傳混合算法

求解旅行商問(wèn)題的蟻群遺傳混合算法

1離散系統(tǒng)的優(yōu)化設(shè)計(jì)遺傳算法和螞蟻算法具有適應(yīng)性強(qiáng)、應(yīng)用范圍廣、效率高等特點(diǎn)。廣泛應(yīng)用于離散系統(tǒng)的項(xiàng)目?jī)?yōu)化。這兩者都有各自的優(yōu)缺點(diǎn)。在這項(xiàng)工作中，我們將集成這兩種算法，進(jìn)行互補(bǔ)，提高優(yōu)化性能，并解決離散空間和連續(xù)空間的優(yōu)化問(wèn)題。2在旅行商業(yè)中，提出了基于螞蟻的遺傳混合算法2.1tsp優(yōu)化算法旅行商問(wèn)題是個(gè)典型的離散空間的優(yōu)化問(wèn)題.旅行商問(wèn)題(TSP:TravelingSalesmanProblem)是一個(gè)NP完全問(wèn)題,TSP問(wèn)題是組合優(yōu)化領(lǐng)域中的一個(gè)典型的問(wèn)題,解決此問(wèn)題有較大的現(xiàn)實(shí)意義,如印刷電路板的鉆空路線方案,連鎖店送貨路線問(wèn)題等都可簡(jiǎn)化為T(mén)SP問(wèn)題.并且此問(wèn)題也可作為測(cè)試新的算法的標(biāo)準(zhǔn)問(wèn)題,因此該問(wèn)題一直是研究的熱點(diǎn).目前求解TSP問(wèn)題的主要方法有模擬退火算法,遺傳算法,啟發(fā)式搜索法,Hopfield神經(jīng)網(wǎng)絡(luò)算法,蟻群算法等,各種算法各有千秋.文將是將遺傳算法與螞蟻算法的融合,采用遺傳算法生成信息素分布,利用螞蟻算法求精確解,優(yōu)勢(shì)互補(bǔ),期望獲得優(yōu)化性能和時(shí)間性能的雙贏.本文提出蟻群算法與遺傳算法混合的算法來(lái)解決旅行商問(wèn)題,利用遺傳算法的優(yōu)點(diǎn),進(jìn)行對(duì)整個(gè)解空間的搜索,然后利用利用蟻群算法信息素信息進(jìn)行交叉操作,并且使用局部最優(yōu)化的方式以加速求解的速度.2.2城市與城市s之間的信息素—全局信息素更新利用蟻群算法中計(jì)算信息素的方式,在初始化時(shí),每一條邊的初始信息素值為τ0,在每一代的解產(chǎn)生之后,我們會(huì)根據(jù)這個(gè)代中的最好解來(lái)更新信息素.令τ(r,s)為城市r與城市s之間的邊上的信息素,其更新規(guī)則如下式(1):τ(r,s)=ρτ(r,s)+Δτ(r,s)(1)τ(r,s)=ρτ(r,s)+Δτ(r,s)(1)其中:Δτ(r,s)={Q/Lgbif(r,s)∈besttour0其他Δτ(r,s)={Q/Lgbif0(r,s)∈besttour其他,而ρ(0<ρ<1)表示軌跡的持久性,Lgb為最好解的長(zhǎng)度.2.3城市聚合酶5.2—交叉操作在交叉操作的操作上,混合算法主要是以每個(gè)邊上面的信息素信息為基礎(chǔ),為敘述方便,假設(shè)只有8個(gè)城市,假設(shè)兩個(gè)父代個(gè)體P1=12345678,P2=12834576(如圖1,圖中較粗的連線表示信息素較高的邊).對(duì)兩個(gè)父代個(gè)體的8條邊的信息素從大到小進(jìn)行排序,每個(gè)個(gè)體取前k個(gè)(如k=5)邊,如P1中e12、e23、e34、e45和e67信息較多,而P2中e12、e34、e45、e16和e67信息較多,先由這些邊組成部分解,每個(gè)城市最多有兩條邊與其它城市相連,如沖突時(shí)選擇較大的兩條,部分解如圖2所示.剩下的孤立城市采取接近原則與其他城市相連,得到后代解.2.4城市c0由路徑C0變異產(chǎn)生另一條路徑C1,常用的有以下4種策略,這里假設(shè)有n=9個(gè)城市.策略A在第1～n個(gè)訪問(wèn)的城市中隨機(jī)地選取第j1次和第j2次訪問(wèn)的城市,在路徑C0中交換第j1次和第j2次訪問(wèn)的城市,其余不變,此時(shí)的路徑為C1.比如C0=234157986,j1=2(第2次訪問(wèn)的城市是城市3),j2=7(第7次訪問(wèn)的城市是城市9),則C1=294157386.策略B在第1～n個(gè)訪問(wèn)的城市中隨機(jī)地選取第j1次訪問(wèn)的城市,在路徑C0中交換第j1次和第j1+1次訪問(wèn)的城市,其余不變,此時(shí)的路徑為C1.比如C0=234157986,j1=2,則C1=243157986.策略C在第1～n個(gè)訪問(wèn)的城市中隨機(jī)地選取第j1次和第j2次訪問(wèn)的城市,假設(shè)j1<j2,在路徑C0中將第j1次訪問(wèn)的城市安排到第j2次訪問(wèn)的城市之后,其余不變,此時(shí)的路徑為C1.比如C0=234157986,j1=2,j2=7,則C1=241579386.策略D也稱逆轉(zhuǎn)策略,在第1～n個(gè)訪問(wèn)的城市中隨機(jī)地選取第j1次和第j2次訪問(wèn)的城市,在路徑C0中第j1次到第j2次訪問(wèn)的城市之間的子路徑以反方向插入,其余不變,此時(shí)的路徑為C1.比如C0=234157986,j1=2,j2=7,則C1=297514386.2.52-opt局部搜尋利用TSP問(wèn)題本身的特性所發(fā)展出來(lái)的局部最優(yōu)化算法,例如2-Opt,3-Opt,及Lin-Kernighan等算法,則在解決TSP的問(wèn)題上展現(xiàn)了很好的效率.這里討論最簡(jiǎn)單的2-Opt局部搜索的算法.2-Opt局部搜尋方法是以邊為基礎(chǔ),先由解當(dāng)中任意拿掉兩條邊,此時(shí)會(huì)將解拆成兩部份,如圖3(a)中去掉邊e34和e58,然后再將其中一部份的路徑反接回另一路徑,如圖3(b)所示.如果新路徑比原來(lái)的路徑短,則我們將保留這個(gè)更好的解,并且針對(duì)不同的邊重復(fù)進(jìn)行以上的步驟直到找不到更好的解為止,最后則得到局部最優(yōu)化的解.2.6局部操作模擬混合算法是基于遺傳算法和蟻群算法所發(fā)展而來(lái)的,它是以遺傳算法為整個(gè)算法的架構(gòu),并結(jié)合蟻群算法的優(yōu)點(diǎn).因此混合算法的基本過(guò)程為,一開(kāi)始隨機(jī)產(chǎn)生m個(gè)解為起始解,更新此代的累積信息素,根據(jù)交叉概率接著由此代中選取成對(duì)的解,由交叉操作的方式產(chǎn)生下一代的解,在此交叉操作的過(guò)程中會(huì)利用到每個(gè)邊的信息素累積量,并對(duì)此新產(chǎn)生的解隨機(jī)選取某些解以產(chǎn)生變異,最后進(jìn)行局部最優(yōu)化的操作,基本步驟如下:步驟1隨機(jī)產(chǎn)生m個(gè)解為起始解;While(不滿足停止條件)步驟2更新此代的累積信息素;步驟3計(jì)算每個(gè)個(gè)體適應(yīng)值(路徑長(zhǎng)度),依據(jù)適應(yīng)值進(jìn)行選擇復(fù)制;步驟4按交叉概率選擇父代,依據(jù)信息素大小進(jìn)行交叉,根據(jù)子代更新累積信息素;步驟5進(jìn)行變異操作;步驟6進(jìn)行2-Opt局部?jī)?yōu)化;步驟7記錄當(dāng)前代解的最好解;Endwhile為了檢驗(yàn)算法的有效性,選用att48(TSPLIB提供的最好解為33522)作為實(shí)驗(yàn)例子來(lái)研究.并于基本蟻群算法、基本遺傳算法、模擬退火算法進(jìn)行比較.模擬退火算法采用文獻(xiàn)的算法,起始溫度T=100000,終止溫度T0=1,退火速度α=0.99;遺傳算法程序采用MATLAB的遺傳算法工具箱,參數(shù)如下:染色體個(gè)數(shù)N=30,交叉概率Pc=0.2,變異概率Pm=0.5,迭代次數(shù)100;混合算法參數(shù):m=30,ρ=0.9,混合算法分別采用4種變異策略進(jìn)行比較.對(duì)各種算法測(cè)試20次,結(jié)果如表1所示.從表1可以看出,混合的4種組合大都比較好,特別變異策略D的混合算法的效果最好.3基于連續(xù)設(shè)置的工業(yè)性能開(kāi)發(fā)對(duì)于連續(xù)優(yōu)化問(wèn)題,目前還沒(méi)有適合各種問(wèn)題的一種解法,各個(gè)方法都有自己特定的適用范圍.求解連續(xù)優(yōu)化問(wèn)題的蟻群算法思路為:首先可根據(jù)問(wèn)題的性質(zhì)估計(jì)一下最優(yōu)解的范圍,估計(jì)出各變量的取值范圍:xjl≤xj≤xju(j=1,2,…,n).在變量區(qū)域內(nèi)打網(wǎng)格,空間的網(wǎng)格點(diǎn)上對(duì)應(yīng)于一個(gè)狀態(tài),人工螞蟻在各個(gè)空間網(wǎng)格點(diǎn)之間移動(dòng),根據(jù)各網(wǎng)格點(diǎn)的目標(biāo)函數(shù)值,留下不同的信息量,以此影響下一批人工螞蟻的移動(dòng)方向.循環(huán)一段時(shí)間后,目標(biāo)函數(shù)值小的網(wǎng)格點(diǎn)信息量比較大.根據(jù)信息量,找出信息量大的空間網(wǎng)格點(diǎn),縮小變量范圍,在此點(diǎn)附近進(jìn)行人工蟻群移動(dòng),重復(fù)前述過(guò)程,直到網(wǎng)格的間距小于預(yù)先給定的精度,算法終止.假設(shè)各變量分成N等份,n個(gè)變量變成n級(jí)決策問(wèn)題,每一級(jí)有N+1個(gè)節(jié)點(diǎn),如圖4所示.共有(N+1)×n個(gè)節(jié)點(diǎn).從第1級(jí)到第n級(jí)之間的連接在一起,組成空間一個(gè)解,如圖4狀態(tài)為(3,2,1,…,1),其對(duì)應(yīng)的解為(x1,x2,?,xn)=(x1l+x1u-x1lΝ×3,x2l+x2u-x2lΝ×2,x3l+x3u-x31lΝ×1,?,xnl+xnu-xnlΝ×1)(x1,x2,?,xn)=(x1l+x1u?x1lN×3,x2l+x2u?x2lN×2,x3l+x3u?x31lN×1,?,xnl+xnu?xnlN×1)對(duì)每一級(jí)設(shè)置1個(gè)螞蟻(也可多于1個(gè)),每個(gè)螞蟻只在本級(jí)節(jié)點(diǎn)之間轉(zhuǎn)移,螞蟻在本級(jí)中第j節(jié)轉(zhuǎn)移到本級(jí)中第i個(gè)節(jié)點(diǎn)的概率pij為:pij=τijΝ∑i=1τij(2)pij=τij∑i=1Nτij(2)更新方程為:τnewij=ρτoldij+Q/f(3)其中:τij理解為第j級(jí)第i個(gè)節(jié)點(diǎn)的吸引強(qiáng)度;ρ表示強(qiáng)度的持久性系數(shù),一般取0.5～0.9左右;Q為一正常數(shù);f為目標(biāo)函數(shù)值,為保證f>0,在原目標(biāo)函數(shù)的基礎(chǔ)上加上一個(gè)大的常數(shù).蟻群遺傳混合算法的思路:在蟻群算法基礎(chǔ)上加上遺傳算法交叉操作和變異操作,交叉操作就是對(duì)τij矩陣隨機(jī)挑選兩個(gè)元素進(jìn)行交換;變異操作就是在τij矩陣隨機(jī)挑選某個(gè)元素,然后對(duì)其加上或減去一定增量.解連續(xù)優(yōu)化問(wèn)題的蟻群遺傳算法如下:步驟1估計(jì)出各變量的取值范圍:xjl≤xj≤xju(j=1,2,…,n);步驟2對(duì)各變量分N等份,hj=xju-xjlΝ(j=1,2,?,n);步驟3若max(h1,h2,…,hn)<ε,算法停止,最優(yōu)解為x*j=xjl+xju2(j=1,2,?,n);否則轉(zhuǎn)步驟4;步驟4nc←0(nc為循環(huán)次數(shù)),給τij矩陣賦相同的數(shù)值,給出Q、ρ的值;步驟5對(duì)每個(gè)螞蟻按轉(zhuǎn)移概率pij選擇下一個(gè)節(jié)點(diǎn);步驟6按更新方程修改吸引強(qiáng)度;步驟7遺傳交叉操作;步驟8遺傳編譯操作;步驟9nc←nc+1,若迭代次數(shù)nc<規(guī)定的最大循環(huán)次數(shù),轉(zhuǎn)步驟5;否則,找出τij矩陣中每列最大的元素對(duì)應(yīng)的行(m1,m2,…,mn);步驟10縮小變量的取值范圍:xjl←xjl+(mj-Δ)hj,xju←xjl+(mj+Δ)hj,(j=1,2,…,n),轉(zhuǎn)步驟2;為了更一步驗(yàn)證方法的有效性,考慮下面優(yōu)化問(wèn)題F=1100100∑i=1x4i-16x2i+5xi?-10≤xi≤100?i=1,2,?,100(4)當(dāng)x*i=-2.904時(shí),該函數(shù)的最小目標(biāo)值為-78.3323,與前人的方法進(jìn)行比較,每種算法均運(yùn)行10次,結(jié)果如2所示,從中看出本文的混合算法的有效性.4局部性侵加2-opt本文提出混合算法結(jié)合了遺傳和蟻群算法兩者的優(yōu)點(diǎn),解