一種求解TSP問(wèn)題的粒子群算法設(shè)計(jì)-科技論文

變異的目的是防止種群中的解跑到局部極值去。變異是對(duì)子代的隨機(jī)的改變。我在算法中采用了以下變異策略：
1．變異策略A：在第1－n個(gè)訪問(wèn)的城市中隨機(jī)地選取第J1次和第J2次訪問(wèn)的城市，在路徑C0中交換第J1次和第J2次訪問(wèn)的城市，其余不變，此時(shí)的路徑為C1。
2．變異策略B：在第1－n個(gè)訪問(wèn)的城市中隨機(jī)地選取第J1次訪問(wèn)的城市，在路徑C0中交換第J1次和第J1＋1次訪問(wèn)的城市，其余不變，此時(shí)的路徑為C1。
3．變異策略C：也稱(chēng)逆轉(zhuǎn)策略，在第1－n個(gè)訪問(wèn)的城市中隨機(jī)地選取第J1次和第J2次訪問(wèn)的城市，在路徑C0中第J1次和第J2次訪問(wèn)的城市之間的子路徑以反方向插入，其余不變，此時(shí)的路徑為C1。
4．變異策略D：在第1－n個(gè)訪問(wèn)的城市中隨機(jī)地選取第J1次和第J2次訪問(wèn)的城市，假設(shè)J15．變異策略E：在第1－n個(gè)訪問(wèn)的城市中隨機(jī)地選取第J1次訪問(wèn)的城市，選取離J1距離最近的城市J2，在路徑中將城市J2安排到城市J1之后，其余不變。
6．變異策略F：計(jì)算路徑中相鄰城市之間距離最大的兩個(gè)城市J1和J2，然后選取選取離J1距離最近的城市J3，在路徑中將城市J3安排到城市J1和J2之間，其余不變。
二、算法步驟
1.初始化，設(shè)定粒子數(shù)n，設(shè)定迭代次數(shù)m，隨機(jī)排列城市順序產(chǎn)生n條初始路徑。
2.根據(jù)當(dāng)前位置計(jì)算適應(yīng)值ltsp0，設(shè)置當(dāng)前適應(yīng)值為個(gè)體極值plbest，當(dāng)前位置為個(gè)體極值位置pcbest，根據(jù)各個(gè)粒子的個(gè)體極值找出全局極值glbest和全局極值位置gcbest。
while（迭代次數(shù)<規(guī)定迭代次數(shù)m）do
Forj＝1：n
3.第j個(gè)粒子的路徑C（j）與個(gè)體極值作交叉操作，產(chǎn)生新的路徑C’(j),若新的路徑長(zhǎng)度變短,則保存結(jié)果。C’(j)與全局極值作交叉操作,產(chǎn)生新的路徑C”(j),若新的路徑長(zhǎng)度變短,則保存結(jié)果。C”(j)變異得到新的位置C”’(j)，若新的路徑長(zhǎng)度變短,則保存結(jié)果。最后產(chǎn)生的路徑為C1(j),若△E<0，則C1(j)覆蓋原始路徑C(j)
Endfor
根據(jù)各個(gè)粒子的個(gè)體極值找出全局極值glbest和全局極值位置gcbest。
EndWhile
4.輸出全局極值glbest和全局極值位置gcbest。
三、算法結(jié)論
本文在深入分析和研究了粒子群算法基本理論與方法的基礎(chǔ)上，嘗試用新的方法將粒子群概念應(yīng)用到TSP這一離散領(lǐng)域優(yōu)化的問(wèn)題之中，取得了突破。同時(shí)針對(duì)PSO的弱點(diǎn)提出了交叉變異的方法，進(jìn)一步提升了粒子群算法在尋找TSP最優(yōu)解領(lǐng)域的能力，在求解旅行商問(wèn)題上有較高的搜索效率，能在較短時(shí)間內(nèi)獲得較好解，而且簡(jiǎn)單有效。算法的分析和測(cè)試表明，該粒子群算法是有效的。雖然該算法沒(méi)有專(zhuān)門(mén)針對(duì)TSP問(wèn)題的經(jīng)典算法那么高效，但是仍然是粒子群算法求解旅行商問(wèn)題的嶄新嘗試。
粒子群算法求解TSP問(wèn)題的研究處于初期，還有許多問(wèn)題值得研究，如算法的收斂性、理論依據(jù)等。但從當(dāng)前的應(yīng)用效果看，這種模仿自然生物的尋優(yōu)思想具有光明的前景，更多深入細(xì)致的工作還有待于進(jìn)一步展開(kāi)。