發(fā)布時間：2018-06-19 08:18

  本文選題：群智能 + 三角形TSP法�。� 參考：《寧波大學(xué)》2017年碩士論文

【摘要】：旅行商(traveling salesman problem,TSP)問題是優(yōu)化組合問題中一類經(jīng)典的NP問題,這類問題的目標(biāo)是求得一個最優(yōu)哈密頓回路,對于該類問題的求解方法源遠流長,求解算法眾多,其中群智能算法表現(xiàn)較優(yōu),這也成為人們研究的重點。群智能算法首先會分析數(shù)據(jù)集內(nèi)部對象連接,由于聚類算法k-means在劃分?jǐn)?shù)據(jù)集中較為常見,并且效果較優(yōu),本文結(jié)合群智能算法和聚類算法k-means求解TSP。本文提出幾種求解TSP的方法,包括三角形TSP法、改進的蟻群算法、受限邊集空間優(yōu)化改進的蟻群算法、優(yōu)化基于GA(Genetic Algorithm)的EAX(Edge Assembly Crossover)法(文中將基于GA的EAX,簡稱為EAX)、結(jié)合改進的蟻群算法與改進的EAX。由于三角形TSP法能夠快速求解TSP,本文首先以三角形TSP法為基礎(chǔ),針對蟻群算法中初始螞蟻具有盲目選擇的特點,提出優(yōu)化蟻群算法的初始矩陣,然后研究數(shù)據(jù)集內(nèi)部對象之間距離和分布,結(jié)合不同算法對數(shù)據(jù)集求解的分析,提出運用聚類算法k-means劃分?jǐn)?shù)據(jù)集,將該劃分結(jié)果作為蟻群算法迭代中的影響因子,以此求解并得到較好的解。其次,通過對數(shù)據(jù)集本身最優(yōu)解與MST(Minimum Spanning Tree)和利用三角形TSP法形成的初始矩陣相比對,發(fā)現(xiàn)所有數(shù)據(jù)集的解都分布在狹小的空間,以此提出受限解空間。優(yōu)化初始矩陣中包含的邊集,構(gòu)成受限的邊空間,將廣泛的邊空間限制在狹小范圍,用這部分邊集實施k-opt優(yōu)化,從而可以減小時間復(fù)雜度和空間復(fù)雜度。另外,本文又通過研究發(fā)現(xiàn)EAX算法在形成新的TSP過程中有信息遺漏,并且用MST連接回路效率較低,進而提出以受限的邊集空間替代原來的MST,并用三角形TSP法生成解替代EAX算法的初始種群。最后,本文綜合分析改進的蟻群算法和優(yōu)化的EAX的不足之處,以及對解空間中解的分布,提出結(jié)合改進的蟻群算法和優(yōu)化的EAX求解TSP。本文用20個數(shù)據(jù)集測試以上5種算法,給出測試結(jié)果,并在文章最后列出所有算法的比對,通過實驗表明,本文所提出的算法對TSPLIB中數(shù)據(jù)集求解TSP均有較優(yōu)效果。
[Abstract]:Traveling salesman problem (TP) problem is a classical NP problem in optimal combinatorial problem. The goal of this kind of problem is to find an optimal Hamiltonian loop. The method of solving this kind of problem has a long history and many algorithms. Among them, swarm intelligence algorithm is better, which has become the focus of research. Firstly, the cluster intelligence algorithm will analyze the object connection in the data set. Because the clustering algorithm k-means is more common in the partition data set, and the effect is better, this paper combines the swarm intelligence algorithm and the clustering algorithm k-means to solve the k-means. This paper presents several methods for solving tsp, including triangle tsp, improved ant colony algorithm, constrained edge set space optimization, and improved ant colony algorithm. The method of optimizing EAXT Edge Assembly Crossoverbased on GA genetic algorithm (EAX) based on GA is proposed in this paper, which combines the improved ant colony algorithm with the improved EAX. Because the triangular tsp method can solve tsp quickly, this paper, based on the triangular tsp method, puts forward the initial matrix of the optimization ant colony algorithm, aiming at the blind selection of the initial ant in the ant colony algorithm. Then the distance and distribution of objects in the data set are studied. Combining with the analysis of different algorithms to solve the data set, the clustering algorithm k-means is proposed to partition the data set, and the partition result is regarded as the influence factor in ant colony algorithm iteration. By this method, a better solution is obtained. Secondly, by comparing the optimal solution of the data set itself with the initial matrix formed by the triangular tsp method, it is found that the solutions of all the data sets are distributed in a narrow space, so that the constrained solution space is proposed. The edge set contained in the initial matrix is optimized to form a restricted edge space, and the extensive edge space is confined to a narrow range. The k-opt optimization is implemented with this part of edge set, which can reduce the time complexity and space complexity. In addition, we also find that the EAX algorithm has information omission in the process of forming new tsp, and the efficiency of using MST to connect the loop is low. Then it is proposed that the original MSTs be replaced by the restricted edge-set space and the initial population of the EAX algorithm be replaced by the triangular tsp method. Finally, this paper comprehensively analyzes the shortcomings of the improved ant colony algorithm and the optimized EAX, as well as the distribution of the solution in the solution space, and proposes a combination of the improved ant colony algorithm and the optimized EAX to solve the TSPs. In this paper, 20 datasets are used to test the above five algorithms, and the test results are given. At the end of the paper, the comparison of all the algorithms is given. The experiments show that the algorithm proposed in this paper has a better effect on solving tsp in the data set of TSPLIB.
【學(xué)位授予單位】：寧波大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18

【參考文獻】

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

1 吳華鋒;陳信強;毛奇凰;張倩楠;張壽春;;基于自然選擇策略的蟻群算法求解TSP問題[J];通信學(xué)報;2013年04期

2 周永權(quán);黃正新;劉洪霞;;求解TSP問題的離散型螢火蟲群優(yōu)化算法[J];電子學(xué)報;2012年06期

3 陳慶芳;吳小俊;;基于分塊互信息和量子粒子群算法的圖像配準(zhǔn)[J];數(shù)據(jù)采集與處理;2011年04期

4 冀俊忠;黃振;劉椿年;;一種快速求解旅行商問題的蟻群算法[J];計算機研究與發(fā)展;2009年06期

5 田瑩;苑瑋琦;;遺傳算法在圖像處理中的應(yīng)用[J];中國圖象圖形學(xué)報;2007年03期

6 王萬良,宋毅,吳啟迪;求解作業(yè)車間調(diào)度問題的雙倍體遺傳算法與軟件實現(xiàn)[J];計算機集成制造系統(tǒng)-CIMS;2004年01期

7 丁建立,陳增強,袁著祉;遺傳算法與螞蟻算法的融合[J];計算機研究與發(fā)展;2003年09期

8 ;Hybrid ant colony algorithm for traveling salesman problem[J];Progress in Natural Science;2003年04期

9 吳斌,史忠植;一種基于蟻群算法的TSP問題分段求解算法[J];計算機學(xué)報;2001年12期

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

1 陳玲;基于PSO-GA混合算法的時間優(yōu)化的旅行商問題的研究[D];合肥工業(yè)大學(xué);2015年

2 宋志飛;基于蟻群算法的TSP問題研究[D];江西理工大學(xué);2013年

3 翟艷鵬;智能算法優(yōu)化Normalized Cut的圖像分割[D];陜西師范大學(xué);2011年

4 楊學(xué)峰;蟻群算法求解TSP問題的研究[D];吉林大學(xué);2010年

5 司馬義買買提;蟻群算法在組合優(yōu)化問題中的若干應(yīng)用及其收斂性研究[D];上海交通大學(xué);2008年

6 蘇晉榮;基于智能優(yōu)化算法的TSP問題研究及應(yīng)用[D];山西大學(xué);2007年

，

本文編號：2039230