旅行商問題（Traveling Salesman Problem,TSP）是一類經(jīng)典的組合優(yōu)化問題,許多科學研究和工程計算中的實際問題都可以描述為TSP問題,對該問題求解算法的研究具有重要意義.本文對求解TSP問題的差分進化算法（Differential Evolution,DE）和進化多目標優(yōu)化方法進行了研究.主要工作如下:首先,差分進化算法在求解連續(xù)優(yōu)化問題上表現(xiàn)突出,但在TSP這類組合優(yōu)化問題中的應用較少.為了較好的模擬差分進化算法的進化機制,本文提出了求解TSP問題的離散差分進化算法（Discrete Differential Evolution,DDE）.與傳統(tǒng)DE中使用的算術運算符不同,DDE利用個體中城市所在的位置序數(shù)來指導個體進行變異和交叉,并采用簡化的2-opt局部搜索策略來改善種群中解的質量.同時,運用馬爾可夫理論證明了DDE以概率1收斂到全局最優(yōu)解.其次,考慮到多目標進化算法（Multi-objective Evolutionary Algorithm,MOEA）的種群進化過程蘊含了隱式的自適應多樣性保持機制,本文建立了求解TSP問題的雙目標優(yōu)化模型,并針對該模型... 

【文章來源】：武漢理工大學湖北省 211工程院校 教育部直屬院校

【文章頁數(shù)】：59 頁

【學位級別】：碩士

【部分圖文】：

不同參數(shù)下的結果對比

圖 3-9 Eil51 最優(yōu)路徑圖 3-10 St70 最優(yōu)路徑0 10 20 30 40 50 60 70 80 90 100橫坐標0102030405060708090100軌跡圖12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849515052535455565758596061626364656667686970

Eil51的最優(yōu)路徑1

【參考文獻】：
期刊論文
[1]一種求解旅行商問題的新型帝國競爭算法[J]. 張鑫龍,陳秀萬,肖漢,李偉.  控制與決策. 2016(04)
[2]新型蟻群算法在TSP問題中的應用[J]. 張弛,涂立,王加陽.  中南大學學報(自然科學版). 2015(08)
[3]一種簡單有效的求解TSP的混合差分進化算法[J]. 曾宇容,王林,頓彩霞.  計算機應用研究. 2012(12)
[4]一種求解TSP初始化種群問題的鄰域法[J]. 羅辭勇,盧斌,劉飛.  重慶大學學報. 2009(11)
[5]進化多目標優(yōu)化算法研究[J]. 公茂果,焦李成,楊咚咚,馬文萍.  軟件學報. 2009(02)
[6]一種求解TSP的混合遺傳蟻群算法[J]. 徐金榮,李允,劉海濤,劉攀.  計算機應用. 2008(08)
[7]求解旅行商問題的位置—次序編碼差分演化算法[J]. 賀毅朝,寇應展,陳致明.  計算機應用. 2007(03)
[8]旅行推銷員問題的算法綜述[J]. 馬良.  數(shù)學的實踐與認識. 2000(02)



本文編號：3024642