機群環(huán)境下用螞蟻算法求解旅行商問題的研究.pdf

1、旅行商問題(Travelling Salesman Problem)是典型的組合優(yōu)化問題，可以應用在諸多領域，它的特點是問題容易描述卻難于求解。隨著問題規(guī)模的擴大，該問題對求解質量和求解速度都提出了更高的要求，因此尋求一種適合大規(guī)模并行且具有智能優(yōu)化特征的算法具有重大的現(xiàn)實意義。目前，隨著并行計算技術的發(fā)展，利用高速網(wǎng)絡將幾臺普通的PC機或工作站連接起來，搭建高性價比的機群系統(tǒng)，求解大規(guī)模問題提供了一種途徑。
　　 螞蟻算法具有

2、正反饋和隱并行性等特點，是求解旅行商問題的理想算法。論文首先利用基本螞蟻算法求解旅行商問題，針對算法在求解過程中，存在搜索時間長、容易陷入局部最優(yōu)解等缺陷，對螞蟻算法進行了改進。針對螞蟻算法搜索時間長的缺陷，引入了局部搜索的模擬退火算法，生成初始信息素分布，加快算法的收斂速度；針對早熟停滯現(xiàn)象，采用信息量動態(tài)加權的方法，控制信息素對算法的引導作用，增加解空間的多樣性。接下來，論文重點分析了螞蟻算法并行實現(xiàn)的可行性，在機群環(huán)境下，基于消息

3、傳遞機制的MPI(Message Passing Interface)并行編程，實現(xiàn)了用并行螞蟻算法求解大規(guī)模旅行商問題。
　　 論文最后在機群環(huán)境下，對用并行螞蟻算法求解旅行商問題進行了測試，分析比較了用螞蟻算法和改進螞蟻算法串行和并行實現(xiàn)對求解大規(guī)模旅行商問題的求解質量和求解速度的差異。并對兩種算法的并行實現(xiàn)進行了橫向比較。根據(jù)理論研究和實驗測試結果證明，利用機群系統(tǒng)實現(xiàn)并行算法求解旅行商問題是可行的，并且可以取得相對串行計