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

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