基于智能優(yōu)化算法的TSP問題研究及應用.pdf

1、TSP(旅行商問題)是指給定n個城市和各城市間的距離，要求確定一條經過各個城市當且僅當一次的最短路線。它是一種典型的組合優(yōu)化問題，其最優(yōu)解的求解代價是指數級的。已經證明TSP問題是一個NP-hard問題。 基于智能優(yōu)化算法求解TSP問題，是近年來剛剛興起的熱門課題。本文主要對粒子群算法和遺傳算法求解TSP問題進行了研究。 1．在分析基本粒子群算法機理的基礎上，引入了粒子個體極值的平均值，將其與粒子個體極值和全局極值一起用

2、于粒子速度更新中，提出了一種改進的粒子群算法。仿真結果表明改進后的粒子群算法在收斂率和收斂速度等方面有明顯的提高。 2．引入交叉算子和變異算子，對求解TSP問題的粒子群算法提出了一種改進，并用14-TSP和30-TSP問題對算法了測試，驗證了改進算法的有效性。 3．利用遺傳算法求解了旅行商問題，并實驗分析了適應度函數、交叉概率和變異概率在求解旅行商問題時，對算法性能的影響。 4．設計了山西省旅游線路優(yōu)化決策系統(tǒng)，