一種改進(jìn)的蟻群算法——RBFACO算法求解TSP問題.pdf

1、TSP問題(TravelingSalesmanProblem)即旅行商問題，是數(shù)學(xué)領(lǐng)域中著名問題之一，對(duì)于它的求解，不但有很高的學(xué)術(shù)價(jià)值，也有非常大的實(shí)用價(jià)值。而它的求解方法是多種多樣的。其中使用智能計(jì)算的方法是近年來新興的一種方法。而蟻群算法是智能計(jì)算中的一種比較新的方法，它從1991年被提出到現(xiàn)在，已經(jīng)經(jīng)過了很大的發(fā)展。蟻群算法最早成功應(yīng)用于解決著名的TSP問題，而后滲透到多個(gè)應(yīng)用領(lǐng)域，由解決一維靜態(tài)優(yōu)化問題到解決多維動(dòng)態(tài)組合優(yōu)化問

2、題，由離散范圍內(nèi)的研究逐漸拓展到連續(xù)范圍內(nèi)的研究，如在系統(tǒng)控制，人工智能，模式識(shí)別，生產(chǎn)調(diào)度等方面，都取得了驚人的進(jìn)展。 而圍繞TSP問題的求解而展開的對(duì)蟻群算法的改進(jìn)，好的算法可以說是層出不窮。從基本蟻群算法，到EAS(ElitistAntSystem)，再到RAS(Rank-basedAntSystem)，直到MMAS(MAX-MINAntSystem)，求解的城市規(guī)模越來越大，求得的最優(yōu)解也在不斷的接近已經(jīng)知道得最優(yōu)解，可

3、以說是蟻群算法的發(fā)展在求解TSP問題方面越來越成熟。 然而通過對(duì)各種蟻群算法的分析，會(huì)發(fā)現(xiàn)在求解TSP問題的過程中，存在著求解時(shí)間過長(zhǎng)和容易陷入停滯的情況，并且這些算法對(duì)這兩者是無(wú)法同時(shí)解決的。針對(duì)這種情況，根據(jù)對(duì)求解TSP問題的FDC(fitnessdistancecorrelation)分析，本文引入了一種機(jī)制--徑向基函數(shù)(RadialBasisFunction，RBF)，利用徑向基函數(shù)的良好的局部性，遴選一部分螞蟻對(duì)路徑