改進(jìn)的遺傳算法求解TSP問題.pdf

1、本文由三個(gè)部分組成，第一部分是對研究背景的介紹，給出了最優(yōu)化問題的描述，概括了求解最優(yōu)化問題的數(shù)學(xué)方法和演化計(jì)算方法。第二部分是對遺傳算法的研究：對傳統(tǒng)的遺傳算法進(jìn)行了簡要的分析，介紹了一些改進(jìn)的遺傳算法，在此基礎(chǔ)上，提出了一種基于相似性的遺傳算法。第三部分是遺傳算法的應(yīng)用實(shí)踐：將所設(shè)計(jì)的算法應(yīng)用到代表性的旅行商問題(TravelingSalesmanProblem，簡稱TSP)和車間調(diào)度問題，并將結(jié)果與傳統(tǒng)的方法進(jìn)行比較，結(jié)果顯示本文

2、設(shè)計(jì)的算法表現(xiàn)出了良好的性能。本文的主要工作和創(chuàng)新點(diǎn)： 1、定義了距離、相似性和鄰域等概念，用距離反映個(gè)體間的差異程度，用相似性描述個(gè)體間的類似程度，用鄰域?qū)崿F(xiàn)對種群的劃分。 2、在新解的產(chǎn)生過程中引入了分級策略，對種群按照適應(yīng)值進(jìn)行劃分，對處于不同級別的個(gè)體采用不同的遺傳操作，使得個(gè)體在相似性的指導(dǎo)下產(chǎn)生新解，避免了新解產(chǎn)生的盲目性，從而使得子代較好繼承了父代的優(yōu)勢特征。此外，用一定概率保留較差個(gè)體和對于重復(fù)個(gè)體用隨機(jī)

3、產(chǎn)生的個(gè)體替換保證了種群的多樣性。從而使算法的效果和效率達(dá)到較好的平衡。為了使算法更快地搜索到最優(yōu)解，還設(shè)計(jì)了加速算子。 3、提出了一種基于相似性的遺傳算法。將該算法運(yùn)用到TSP問題中，其中結(jié)合了TSP問題的特點(diǎn)，定義了TSP問題的距離、相似性和鄰域等并設(shè)計(jì)了符合TSP問題的加速算子。數(shù)值實(shí)驗(yàn)表明該算法收斂速度快，結(jié)果也較好。 4、對TSP問題進(jìn)行了綜述。介紹了TSP問題的歷史和研究現(xiàn)狀、數(shù)學(xué)模型、時(shí)間復(fù)雜度、評價(jià)標(biāo)準(zhǔn)。