粒子群算法在旅行商問題中的應用研究.pdf

1、粒子群優(yōu)化算法(PSO)是一種立足于群智能方法的優(yōu)化技術，算法的優(yōu)勢在于它的較強的全局搜索能力，較少的參數設置，實現(xiàn)起來簡單容易又有深刻的智能背景，既適合科學研究，同時特別適合工程應用。但是，PSO算法存在一種明顯不足，即：在優(yōu)化過程中所有粒子都朝最優(yōu)解的方向飛去，粒子趨向同一化，致使群體的多樣性逐漸喪失，算法后期的收斂速度明顯變慢，甚至處于停滯狀態(tài)，因此也就難以獲得較好的優(yōu)化結果。本研究針對粒子群優(yōu)化算法應用于求解旅行商問題(TSP)

2、時易出現(xiàn)停滯早熟，陷入局部最優(yōu)等現(xiàn)象，對PSO算法進行了改進，主要工作如下：
　　 1．根據慣性權重和學習因子的特點，對ω和c1, c2重新設定；當粒子處于停滯狀態(tài)時，粒子本身沒有變異機制，為使得粒子能夠成功跳出局部最優(yōu)，對粒子進行主動變異；進化的后期，粒子陷入局部最優(yōu)，本研究引入了粒子的自探索行為，在公共知識庫的基礎上定義了擾動算子，以達到種群多樣化，提高求精能力的目的，并針對經典旅行商問題TSPLIB標準庫中的Burma14

3、城市和Ulysses22城市求解最短路徑問題進行了相應的實驗。實驗結果表明，使用擾動算子的確可以改善算法性能，使得求解14城市時的平均收斂能力明顯提高，求解22城市時，最優(yōu)解的精度比基本PSO算法明顯得到提高。
　　 2．結合捕食搜索策略的先在整個搜索空間進行全局搜索，直至找到一個較優(yōu)解，然后在較優(yōu)解的附近區(qū)域進行集中搜索的特性，提出了基于捕食搜索策略的粒子群算法來求解旅行商問題。用來解決上述Burma14城市問題，實驗結果表明

4、尋優(yōu)能力很強，每次都能找劍最優(yōu)解；解決上述Ulysses22城市問題時，實驗結果表明其最優(yōu)解，平均解和最差解都比改進自組織PSO(SOPSO)算法得到提高。
　　 3．結合蟻群算法和遺傳算法提出了一種混合粒子群算法來求解旅行商問題，為了驗證該方法的有效性和可行性，對上述的Ulysses22城市問題進行了測試，給出了實驗結果，并與標準PSO，SOPSO，標準蟻群等其他算法結果進行了比對，得出混合算法有效的結論。
　　 綜合