改進的遺傳算法在TSP問題上的研究.pdf

1、組合優(yōu)化中的許多問題是NP完全問題，也是科學(xué)和工程計算中重要和基本的問題，這類問題的求解一直是算法研究領(lǐng)域的熱點問題。旅行商(TSP)問題是經(jīng)典的組合優(yōu)化問題，目前TSP問題的求解方法主要是啟發(fā)式算法，尤其是仿生、智能優(yōu)化算法。遺傳算法(Genetic Algorithm)是一種新的智能優(yōu)化算法，通過模擬自然界生物進化過程，利用簡單的編碼技術(shù)和遺傳操作高效地解決復(fù)雜的組合優(yōu)化問題。其特點就是其不同于傳統(tǒng)的搜索尋優(yōu)方式而是模擬自然界生物進

2、化過程，通過基因的交叉、變異重組產(chǎn)生新的個體，實現(xiàn)“物競天擇，適者生存”進化規(guī)則，使種群得到進化，最終得到最優(yōu)個體，即最優(yōu)解。
　　 遺傳算法以決策變量的編碼作為運算對象，直接以適應(yīng)度函數(shù)值作為搜索信息，因此具有較強的魯棒性；它是使用多個點的搜索信息，具有全局優(yōu)化能力，還具有很強的可并行性等優(yōu)點；但也容易產(chǎn)生早熟現(xiàn)象以及局部尋優(yōu)能力較差等問題。本文針對遺傳算法的這一缺點，就遺傳操作進行改進，并應(yīng)用于求解旅行商問題。
　　

3、 本文的主要工作包括：
　　 1、簡要介紹了組合優(yōu)化中的TSP問題的研究現(xiàn)狀，對現(xiàn)有一些求解TSP方法進行了分析，詳細介紹了遺傳算法、并闡述了遺傳算法求解TSP問題的一般步驟，建立了遺傳算法求解TSP問題模型；
　　 2、就遺傳算法中交叉算子進行改進：傳統(tǒng)的交叉算子操作方法尋優(yōu)效率低，并易陷入局部最優(yōu)，就順序交叉方法進行改進。改進后的交叉算子是在隨機選擇交叉區(qū)域和交叉片斷長度后，對重復(fù)節(jié)點和前后節(jié)點的路徑長度進行比較后，

4、再刪除路徑長的重復(fù)節(jié)點，有效地提高了算法的尋優(yōu)效率。
　　 3、對變異算子進行了改進：主要是將蟻群算法的正反饋思想引入到遺傳算法中。為了彌補變異算子變異過程中的盲目無原則性，引入蟻群算法信息素更新指導(dǎo)變異規(guī)則，確保交換后的變異位置前后路徑的信息素比交換前的高，有效地提高了算法的尋優(yōu)效率。
　　 4、將改進的遺傳算法應(yīng)用到TSP問題求解中，用TSPLIB庫中的兩個公共數(shù)據(jù)eil51和gr202和安徽省17個城市的TSP數(shù)據(jù)