動態(tài)TSP遺傳算法研究.pdf

1、TSP問題(Traveling Salesman Problem，TSP)是一個典型的組合優(yōu)化問題，己經(jīng)成為并仍將繼續(xù)成為測試組合優(yōu)化新算法的熱點問題。在傳統(tǒng)的TSP問題中，城市的規(guī)模以及城市之間的距離是固定不變的，但在實際應用中，問題的規(guī)模及費用向量矩陣常常是隨著時間而動態(tài)變化的，稱這類問題為動態(tài)TSP問題。為了給管理者提供正確的決策方案，算法必須根據(jù)實時信息在較短時間內(nèi)給出滿意解。對這類問題的研究，不僅可為各類動態(tài)組合優(yōu)化問題提供一

2、種理論上的參考，而且還具有廣泛的實際應用價值。
　　 遺傳算法作為一種自適應的全局優(yōu)化概率搜索算法，具有簡單通用、魯棒性強、智能性及并行性等優(yōu)點，已成功地應用于求解組合優(yōu)化問題。本文采用改進的遺傳算法對TSP問題進行求解，主要的研究工作和創(chuàng)新如下：
　　 1)對TSP問題進行了分析，建立了數(shù)學模型。融合當前的研究成果，對動態(tài)TSP提出了三種模型，分別從不同層面表現(xiàn)問題的動態(tài)性，并提出一種可以適應所有情形的統(tǒng)一的動態(tài)TSP

3、問題模型；
　　 2)針對靜態(tài)TSP問題，提出了一種雙倍體編碼方案，該方案集近鄰關(guān)系和訪問序列于一體，使得個體評價表現(xiàn)出多種性能，即增加了種群的多樣性，同時又加快了種群的收斂速度，使遺傳算法更具使用價值；
　　 3)在遺傳算法理論方面，提出了“二八”種群控制策略，對種群的少部分個體進行控制，實現(xiàn)了種群的整體收斂，同時較好地保持了種群的多樣性，減少了運行時間；提出了判官算子，提高了種群的收斂速度，達到了提高求解速度同時又保

4、持種群多樣性的雙重功效。
　　 4)提出了一種兩階段反轉(zhuǎn)映射遺傳算法。該算法分為兩階段，在第一階段主要使用反轉(zhuǎn)交叉算法和個體競爭策略，運行到種群“穩(wěn)定”態(tài)，以保證最優(yōu)解的子串基本包含在當前的種群的個體之間，甚至是最優(yōu)解本身，第二階段主要運用映射算法，通過對種群中個體的映射修改，構(gòu)造出最優(yōu)解，從而完成遺傳算法的求解。實驗表明改進后的遺傳算法，有較快的求解速度，具有一定的實用價值。
　　 5)針對動態(tài)TSP問題設計了嵌入式遺