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

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

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

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

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