求解TSP問題的遺傳算法研究.pdf

1、分類號(hào)密級(jí)UDC編號(hào)桂林電子科技大學(xué)碩士學(xué)位論文題目:求解TSP問題的遺傳算法研究(英文)ResearchonGeicAlgithmsfTravelingSalesmanProblems研究生姓名：符一平指導(dǎo)教師姓名、職務(wù)：陳光喜副教授申請(qǐng)學(xué)科門類：理學(xué)碩士學(xué)科、專業(yè)：應(yīng)用數(shù)學(xué)提交論文日期：2008年3月論文答辯時(shí)間：2008年6月2008年3月27日摘要摘要遺傳算法(GeicAlgithms)是一種模仿生物自然進(jìn)化過程的隨機(jī)搜索和優(yōu)化

2、算法其優(yōu)勢(shì)在于可以高效的處理傳統(tǒng)搜索方法難以求解決的非線性問題.遺傳算法具有全局優(yōu)化性和易操作性由于其不受搜索空間的限制性假設(shè)的約束具有廣泛的適應(yīng)性、并行性等特點(diǎn)，目前被廣泛應(yīng)用于函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、模式識(shí)別等眾多領(lǐng)域并逐漸成為人工智能領(lǐng)域的一個(gè)研究熱點(diǎn).TSP問題是一個(gè)經(jīng)典的組合優(yōu)化問題中的NP難問題有效地解決TSP問題在可計(jì)算理論上有著重要的理論價(jià)值同時(shí)也有著極高的實(shí)際應(yīng)用價(jià)值.而且遺傳算法在TSP問題求解問題的應(yīng)用研究對(duì)于構(gòu)造合適

3、的遺傳算法框架、建立有效的遺傳操作等都有重要意義.本文從求解TSP問題出發(fā)對(duì)遺傳算法作了細(xì)致地分析及研究.首先介紹了遺傳算法的理論及應(yīng)用領(lǐng)域然后針對(duì)TSP問題的求解進(jìn)一步指出遺傳算法求解TSP問題一大難題是如何快速收斂到最優(yōu)解并防止”早熟”現(xiàn)象發(fā)生.為了解決這一難題本文對(duì)群體、遺傳算子作了詳細(xì)地討論得出解決”早熟”現(xiàn)象的一些微觀策略對(duì)于遺傳算法在進(jìn)化后期局部搜索能力較差可以適當(dāng)?shù)募尤刖植克阉魉惴ㄌ岣咂溥\(yùn)行效率.根據(jù)這些策略對(duì)遺傳算法進(jìn)行

4、改進(jìn):結(jié)合TSP問題最優(yōu)路徑中一般包含城市與其最近城市相連的特點(diǎn)提出了兩點(diǎn)插入變異算子改進(jìn)了啟發(fā)式交叉算子并根據(jù)個(gè)體適應(yīng)度與群體平均適應(yīng)度的比較賦予不同的變異概率使得較好的個(gè)體探測(cè)路徑較差的個(gè)體開發(fā)新個(gè)體.另外對(duì)初始群體進(jìn)行局部?jī)?yōu)化提高其質(zhì)量加快算法的收斂速度若最優(yōu)個(gè)體連續(xù)幾代一直保留則采用局部微調(diào)對(duì)其進(jìn)行局部搜索從而使得子代中最優(yōu)個(gè)體跳離局部解.通過仿真實(shí)驗(yàn)改進(jìn)的算法能較快地收斂到TSP問題的已知最優(yōu)解其測(cè)試結(jié)果與國(guó)際標(biāo)準(zhǔn)測(cè)試庫(kù)TSP