【摘要】：旅行商問題作為組合優(yōu)化問題的典型代表,很多問題都可以轉(zhuǎn)化為該問題求解。隨著優(yōu)化理論在各行各業(yè)的廣泛應(yīng)用,尋找旅行商問題的最優(yōu)解成為研究重點(diǎn)。論文以求解旅行商問題的最短巡回路徑為主要研究對象,首先介紹了求解旅行商問題的背景和研究現(xiàn)狀,闡述了蟻群算法和遺傳算法以及二者融合后的原理,并建立了它們的數(shù)學(xué)模型和求解旅行商問題的步驟。在此基礎(chǔ)上,對三種算法在TSP中的應(yīng)用進(jìn)行了如下研究:1、對蟻群算法、遺傳算法以及二者融合后最優(yōu)的參數(shù)選取進(jìn)行了分析;2、在參數(shù)選取最優(yōu)的情況下改變TSP的規(guī)模用三種算法分別對最短路徑距離的尋優(yōu)進(jìn)行仿真實(shí)驗(yàn);3、對三種算法在不同規(guī)模上的尋優(yōu)結(jié)果進(jìn)行對比分析。實(shí)驗(yàn)結(jié)果表明,求解TSP的最短巡回路徑,當(dāng)TSP規(guī)模較小時(shí),三種算法的尋優(yōu)效果沒有明顯的優(yōu)劣之分;隨著TSP規(guī)模的擴(kuò)大,將蟻群算法與遺傳算法融合后,尋優(yōu)效果明顯好于兩種算法單獨(dú)運(yùn)算時(shí)的求解效果。
[Abstract]:As a typical representative of combinatorial optimization problems, many problems can be transformed into solving them. With the wide application of optimization theory in various industries, finding the optimal solution of traveling salesman problem becomes the focus of research. In this paper, the shortest itinerant path of traveling salesman problem is taken as the main research object. Firstly, the background and research status of solving traveling salesman problem are introduced, and the ant colony algorithm and genetic algorithm and the principle of merging them are expounded. Their mathematical models and the steps to solve the traveling salesman problem are established. On this basis, the application of the three algorithms in TSP are studied as follows: 1. The ant colony algorithm, genetic algorithm and the optimal selection of parameters after the fusion of the ant colony algorithm and genetic algorithm are analyzed. 2. Under the condition of optimal parameter selection, three algorithms are used to simulate the optimization of the shortest path distance by changing the scale of TSP; 3, the optimization results of the three algorithms on different scales are compared and analyzed. The experimental results show that there is no obvious difference between the three algorithms when the scale of TSP is small for solving the shortest circuit path of TSP. With the expansion of the TSP scale, the combination of ant colony algorithm and genetic algorithm is better than the solution of the two algorithms alone.
【學(xué)位授予單位】：山西師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陳亞云;韓文濤;崔鶴平;;遺傳算法與蟻群算法的改進(jìn)融合[J];中國農(nóng)機(jī)化學(xué)報(bào);2014年04期

2 于瑩瑩;陳燕;李桃迎;;改進(jìn)的遺傳算法求解旅行商問題[J];控制與決策;2014年08期

3 任海艷;陳飛翔;;自適應(yīng)遺傳算法的改進(jìn)及在曲線化簡中的應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2012年11期

4 代桂平;王勇;侯亞榮;;基于遺傳算法的TSP問題求解算法及其系統(tǒng)[J];微計(jì)算機(jī)信息;2010年04期

5 劉青鳳;李敏;;基于遺傳算法的TSP問題優(yōu)化求解[J];計(jì)算機(jī)與現(xiàn)代化;2008年02期

6 徐紅梅;陳義保;劉加光;王燕濤;;蟻群算法中參數(shù)設(shè)置的研究[J];山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年01期

7 田貴超;黎明;韋雪潔;;旅行商問題(TSP)的幾種求解方法[J];計(jì)算機(jī)仿真;2006年08期

8 陳文蘭;戴樹貴;;旅行商問題算法研究綜述[J];滁州學(xué)院學(xué)報(bào);2006年03期

9 高海昌;馮博琴;朱利b;;智能優(yōu)化算法求解TSP問題[J];控制與決策;2006年03期

10 徐精明,曹先彬,王煦法;多態(tài)蟻群算法[J];中國科學(xué)技術(shù)大學(xué)學(xué)報(bào);2005年01期

相關(guān)博士學(xué)位論文 前1條

1 王超學(xué);遺傳算法和蟻群算法及其在TSP問題和配電網(wǎng)重構(gòu)問題中的應(yīng)用研究[D];西安理工大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 孫晶;改進(jìn)的混合型蟻群算法及其應(yīng)用[D];中北大學(xué);2014年

2 劉錦;混合遺傳算法和模擬退火算法在TSP中的應(yīng)用研究[D];華南理工大學(xué);2014年

3 楊溪;改進(jìn)遺傳算法和蟻群算法在電力系統(tǒng)問題中的應(yīng)用研究[D];太原理工大學(xué);2013年

4 初雪寧;自適應(yīng)記憶遺傳算法研究及在TSP問題中的應(yīng)用[D];東北大學(xué);2012年

5 王娜;一種改進(jìn)的遺傳算法求解TSP問題[D];東北師范大學(xué);2010年

6 汪松泉;遺傳算法在組合優(yōu)化中的應(yīng)用研究[D];安徽大學(xué);2010年

7 蔣榮;遺傳算法在TSP問題上的應(yīng)用[D];合肥工業(yè)大學(xué);2009年

8 李薇;遺傳算法及其在TSP問題中的應(yīng)用研究[D];貴州大學(xué);2008年

9 孫海雷;改進(jìn)的遺傳算法求解TSP問題[D];重慶大學(xué);2007年

10 林志毅;改進(jìn)的遺傳算法求解TSP問題[D];武漢理工大學(xué);2006年

，

本文編號(hào)：2392840