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

1、分類號密級UDC編號桂林電子科技大學(xué)碩士學(xué)位論文題目:求解TSP問題的遺傳算法研究(英文)ResearchonGeicAlgithmsfTravelingSalesmanProblems研究生姓名：符一平指導(dǎo)教師姓名、職務(wù)：陳光喜副教授申請學(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)勢在于可以高效的處理傳統(tǒng)搜索方法難以求解決的非線性問題.遺傳算法具有全局優(yōu)化性和易操作性由于其不受搜索空間的限制性假設(shè)的約束具有廣泛的適應(yīng)性、并行性等特點(diǎn)，目前被廣泛應(yīng)用于函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、模式識別等眾多領(lǐng)域并逐漸成為人工智能領(lǐng)域的一個研究熱點(diǎn).TSP問題是一個經(jīng)典的組合優(yōu)化問題中的NP難問題有效地解決TSP問題在可計(jì)算理論上有著重要的理論價(jià)值同時(shí)也有著極高的實(shí)際應(yīng)用價(jià)值.而且遺傳算法在TSP問題求解問題的應(yīng)用研究對于構(gòu)造合適

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

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