改進(jìn)的遺傳算法在TSP問(wèn)題上的研究.pdf

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

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

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

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