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

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

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

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

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