一種改進的蟻群算法——RBFACO算法求解TSP問題.pdf

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

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

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