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

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

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

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

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