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

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

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