關(guān)于TSP問題的演化算法研究.pdf

1、TSP(Trayeling Salesman Problem)問題是組合優(yōu)化中最為著名的問題，它綜合了一大類組合優(yōu)化問題的典型特征。從理論上講，使用窮舉法不但可以求解TSP問題，而且還可以求出該問題的最優(yōu)解。但是對現(xiàn)有的計算機來說，使用常規(guī)的窮舉法在如此龐大的搜索空間中尋求最優(yōu)解，幾乎是不可能的。所以，各種求。TSP問題近似解的優(yōu)化算法應(yīng)運而生了，其中演化算法的運用為求解TSP問題帶來了新的希望。 演化算法是一種模擬自然界自適應(yīng)

2、演化過程而發(fā)展起來的通用問題求解方法。它采用簡單的編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu)，并通過對編碼進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導(dǎo)學(xué)習(xí)和確定搜索的方向。簡單的遺傳操作和優(yōu)勝劣汰的自然選擇機制使演化算法具有不受搜索條件的限制、不需要其它輔助信息的特點。它采用的種群搜索模式，有利于搜索到全局最優(yōu)解，能較好的解決解的局部性問題。因此，演化算法被廣泛的用來求解具有挑戰(zhàn)性的問題。 在求解TSP問題時，蟻群算法(ACO)和粒子群算法(

3、PSO)都顯示了有效的解決問題的能力。而郭濤算法在求解TSP問題時性能表現(xiàn)特別突出。本文分析和研究了改進的蟻群算法中的信息素的積累及信息的交換方式，通過實驗證明該算法避免了算法過早停滯的缺點，提高了解的質(zhì)量，同時算法的收斂速度得到保證。對微粒群優(yōu)化算法的速度位置算式的改進進行了分析研究，該算法符合組合優(yōu)化問題的特點，在求解TSP上有較高的搜索效率。在將原郭濤算法算子的線性逆轉(zhuǎn)改為環(huán)形逆轉(zhuǎn)以及引入映射算子、優(yōu)化算子以及增加一些控制策略基礎(chǔ)