粒子群算法在旅行商問題中的應(yīng)用研究.pdf

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

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

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

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