基于分布式蟻群算法的TSP問(wèn)題研究.pdf

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

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