基于分布式蟻群算法的TSP問題研究.pdf

1、許多實際工程問題可以抽象為相應(yīng)的組合優(yōu)化問題，TSP問題是作為所有組合優(yōu)化問題的范例而存在的，它已成為并將一直做為測試組合優(yōu)化新算法的標(biāo)準(zhǔn)問題。從理論上講，使用窮舉法可以求解出TSP問題的最優(yōu)解；但是對現(xiàn)有的計算機(jī)來說，讓它在如此龐大的搜索空間中尋求最優(yōu)解，幾乎是不可能的。所以，各種求TSP問題近似解的算法應(yīng)運而生了，蟻群算法也是其中一種。 但面對規(guī)模較大的TSP問題，包括蟻群算法在內(nèi)的各種啟發(fā)算法都不能有效的求解。本論文提出了

2、利用分布式技術(shù)結(jié)合蟻群算法的思想來求解TSP問題。 首先，論文對分布式計算框架進(jìn)行了探討，基于RMI設(shè)計并實現(xiàn)了任務(wù)管理機(jī)制、任務(wù)池等。通過上述機(jī)制，提高了計算資源的利用率。 其次，論文比較了兩種不同的信息素更新策略：局部更新策略和全局更新策略之后，根據(jù)分布式計算的特點，提出了異步更新策略，并進(jìn)行了相應(yīng)的仿真實驗。實驗結(jié)果證明這種更新策略有效地降低了通信量提高計算效率。 接著，對蟻群算法參數(shù)的選取進(jìn)行了研究。蟻群