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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

不同參數(shù)下的結(jié)果對(duì)比

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

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

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



本文編號(hào)：3024642