【摘要】：旅行商問題是一個經典組合優(yōu)化方面的問題。隨著城市集群的規(guī)模迅猛增長,旅行商問題在搜索空間里變得越來越難尋找最優(yōu)解。同時,過于冗余的改進算法給程序帶來更多的負面影響。因此,尋找一個高效和便捷的遺傳算法計算框架成了眾多學者的研究重點。對于旅行商問題這類完全問題,遺傳算法具有全局搜索的優(yōu)勢,而它的局部搜索能力不足以及收斂速度緩慢。在傳統(tǒng)精確算法中,它們多為局部搜索算法,一般得到局部較優(yōu)解,即對小范圍的城市群能夠準確求出近似解。因此,近年來不斷改進的遺傳算法有通過和傳統(tǒng)算法相結合成混合算法來改進,以便達到優(yōu)勢互補。除此之外,它也有借助相關策略的改進來提高遺傳算法的性能。在改進算法中,鮮有人突出提出對于城市信息預處理來克服那些不足,有的是基于數(shù)據(jù)挖掘算法中的k均值聚類算法與遺傳算法的混合算法的提出。聚類算法是以迭代時間的巨大代價來換取遺傳算法處理能力的提高。本文出發(fā)點依然是圍繞傳統(tǒng)遺傳算法解決旅行商問題所遇到的兩大問題,采取一種直接劃分地圖而形成區(qū)域網格的簡單方式,通過劃分處理城市信息數(shù)據(jù)進而改進路徑編碼。改進的遺傳算法是將原來城市群的坐標數(shù)據(jù)根據(jù)地圖區(qū)域網格單位的劃分進行數(shù)據(jù)信息預處理而達到地圖壓縮和提煉有用信息的目的。改進的遺傳算法基于對于原始數(shù)據(jù)進行域規(guī)則的數(shù)據(jù)預處理,提出了一種對傳統(tǒng)路徑編碼,以及諸算子改進的遺傳算法。改進的遺傳算法的數(shù)據(jù)預處理將根據(jù)地圖區(qū)域化特點進行網格區(qū)域劃分處理,且采用提前培育的局部優(yōu)秀基因塊,再與整體相結合完成分階段初始化。同時,區(qū)域劃分必然存在鄰近區(qū)域,進而有了對于諸算子的發(fā)生位置的指導以及發(fā)生概率的影響。后續(xù)依托數(shù)據(jù)預處理階段處理得到的結果信息對初始種群算子,以及選擇、交叉和變異等算子進行相應的改進。正因為它運用類似聚類的算法劃分,與數(shù)據(jù)挖掘算法的混合算法相比較而言,前期處理變得簡單。研究實現(xiàn)結果表明,通過對城市數(shù)據(jù)進行域規(guī)則的預處理以及配套的策略相結合,可提高遺傳算法的收斂速度和精確度。
[Abstract]:The traveling salesman problem is a classical combinatorial optimization problem. With the rapid growth of urban clusters, the traveling salesman problem becomes more and more difficult to find the optimal solution in the search space. At the same time, the redundant improved algorithm brings more negative effects to the program. Therefore, the search for an efficient and convenient genetic algorithm computing framework has become the focus of many scholars. For the complete problem such as traveling salesman problem, genetic algorithm has the advantage of global search, but its local search ability is insufficient and the convergence speed is slow. In the traditional exact algorithms, most of them are local search algorithms. Generally, the local optimal solution is obtained, that is, the approximate solution can be accurately obtained for the small urban agglomeration. Therefore, the genetic algorithm which has been improved in recent years has been improved by combining the traditional algorithm with the hybrid algorithm in order to achieve complementary advantages. In addition, it also improves the performance of genetic algorithm by the improvement of related strategies. In the improved algorithm, few people put forward to the city information preprocessing to overcome those shortcomings, some of the data mining algorithm based on the k-means clustering algorithm and genetic algorithm hybrid algorithm proposed. Clustering algorithm is a huge cost of iterative time in exchange for the improvement of genetic algorithm processing capacity. The starting point of this paper is still around the traditional genetic algorithm to solve the two major problems encountered in the traveling salesman problem, using a direct map to form a simple way to form a regional grid, by dividing the processing of urban information data and improve the path coding. The improved genetic algorithm is to preprocess the coordinate data of the original urban agglomeration according to the division of the grid units of the map area to achieve the purpose of map compression and extraction of useful information. Based on the data preprocessing of domain rules for raw data, the improved genetic algorithm (GA) is proposed to encode the traditional path and improve the operators. The data preprocessing of the improved genetic algorithm will be processed according to the characteristics of map regionalization. The improved genetic algorithm will adopt the local excellent gene blocks which are cultivated in advance and complete the initialization by stages in combination with the whole. At the same time, there must be adjacent regions in the division of regions, which will have the influence on the location of the operators and the probability of occurrence. The initial population operator, selection operator, crossover operator and mutation operator are improved based on the result information of the data preprocessing stage. Because it uses clustering-like algorithm partitioning, compared with the mixed algorithm of data mining algorithm, the preprocessing becomes simple. The results show that the convergence speed and accuracy of the genetic algorithm can be improved by preprocessing the urban data with domain rules and combining the corresponding strategies.
【學位授予單位】：江西理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

1 吳瑞鏞,徐大紋;具有年齡結構的遺傳算法[J];桂林電子工業(yè)學院學報;2001年04期

2 楊艷麗,史維祥;一種新的優(yōu)化算法—遺傳算法的設計[J];液壓氣動與密封;2001年02期

3 楊宜康,李雪,彭勤科,黃永宣;具有年齡結構的遺傳算法[J];計算機工程與應用;2002年11期

4 谷峰,吳勇,唐俊;遺傳算法的改進[J];微機發(fā)展;2003年06期

5 ;遺傳算法[J];計算機教育;2004年10期

6 趙義紅,李正文,何其四;生物信息處理系統(tǒng)遺傳算法探討[J];成都理工大學學報(自然科學版);2004年05期

7 劉坤,劉偉波,吳忠強;基于模糊遺傳算法的電液位置伺服系統(tǒng)控制[J];黑龍江科技學院學報;2005年04期

8 張英俐,劉弘 ,馬金剛;遺傳算法作曲系統(tǒng)研究[J];信息技術與信息化;2005年05期

9 丁發(fā)智;;淺談遺傳算法[J];烏魯木齊成人教育學院學報;2005年04期

10 李冰潔;;遺傳算法及其應用實例[J];吉林工程技術師范學院學報;2005年12期

相關會議論文 前10條

1 陳家照;廖海濤;張中位;羅寅生;;一種改進的遺傳算法及其在路徑規(guī)劃中的應用[A];2009系統(tǒng)仿真技術及其應用學術會議論文集[C];2009年

2 李國云;劉穎;薛梅;鄔志敏;;遺傳算法在高溫空冷冷凝器優(yōu)化設計中的應用[A];第五屆全國制冷空調新技術研討會論文集[C];2008年

3 王志軍;李守春;張爽;;改進的遺傳算法在反演問題中的應用[A];新世紀 新機遇 新挑戰(zhàn)——知識創(chuàng)新和高新技術產業(yè)發(fā)展（上冊）[C];2001年

4 任燕翔;姜立;劉連民;從滋慶;;改進遺傳算法在三維日照方案優(yōu)化中的應用[A];工程三維模型與虛擬現(xiàn)實表現(xiàn)——第二屆工程建設計算機應用創(chuàng)新論壇論文集[C];2009年

5 韓娟;;遺傳算法概述[A];第三屆河南省汽車工程科技學術研討會論文集[C];2006年

6 龐國仲;王元西;;基于遺傳算法控制步長的定性仿真方法[A];'2000系統(tǒng)仿真技術及其應用學術交流會論文集[C];2000年

7 張忠華;楊淑瑩;;基于遺傳算法的聚類設計[A];全國第二屆信號處理與應用學術會議�？痆C];2008年

8 何翠紅;區(qū)益善;;遺傳算法及其在計算機編程中的應用[A];1995年中國智能自動化學術會議暨智能自動化專業(yè)委員會成立大會論文集（下冊）[C];1995年

9 靳開巖;張乃堯;;幾種實用遺傳算法及其比較[A];1996年中國智能自動化學術會議論文集（下冊）[C];1996年

10 王宏剛;曾建潮;李志宏;;攝動遺傳算法[A];1996年中國智能自動化學術會議論文集（下冊）[C];1996年

相關重要報紙文章 前1條

1 林京;《神經網絡和遺傳算法在水科學領域的應用》將面市[N];中國水利報;2002年

相關博士學位論文 前10條

1 蔡美菊;交互式遺傳算法及其在隱性目標決策問題中的應用研究[D];合肥工業(yè)大學;2015年

2 張士偉;三維聲學快速多極基本解法在機械噪聲預測中的應用研究[D];沈陽工業(yè)大學;2016年

3 高軍;無鉛焊料本構模型及其參數(shù)識別方法研究[D];南京航空航天大學;2015年

4 Amjad Mahmood;半監(jiān)督進化集成及其在網絡視頻分類中的應用[D];西南交通大學;2015年

5 周輝仁;遞階遺傳算法理論及其應用研究[D];天津大學;2008年

6 郝國生;交互式遺傳算法中用戶的認知規(guī)律及其應用[D];中國礦業(yè)大學;2009年

7 侯格賢;遺傳算法及其在跟蹤系統(tǒng)中的應用研究[D];西安電子科技大學;1998年

8 馬國田;遺傳算法及其在電磁工程中的應用[D];西安電子科技大學;1998年

9 唐文艷;結構優(yōu)化中的遺傳算法研究和應用[D];大連理工大學;2002年

10 周激流;遺傳算法理論及其在水問題中應用的研究[D];四川大學;2000年

相關碩士學位論文 前10條

1 張英俐;基于遺傳算法的作曲系統(tǒng)研究[D];山東師范大學;2006年

2 鐘海萍;原對偶遺傳算法與蟻群算法的一種融合算法[D];暨南大學;2013年

3 李志添;模糊遺傳算法與資源優(yōu)化配置的預測控制[D];華南理工大學;2015年

4 王琳琳;新型雙層液壓轎運車車廂的設計研究[D];上海工程技術大學;2015年

5 李海全;基于遺傳算法的建筑體形系數(shù)及迎風面積比優(yōu)化方法研究[D];華南理工大學;2015年

6 彭騫;基于遺傳算法的山區(qū)高等級公路縱斷面智能優(yōu)化方法研究[D];昆明理工大學;2015年

7 周玉林;基于小波分析和遺傳算法的配電網故障檢測[D];昆明理工大學;2015年

8 郭頌;基于粗糙集和遺傳算法的數(shù)字管道生產管理系統(tǒng)研究[D];昆明理工大學;2015年

9 吳南;數(shù)值逼近遺傳算法的研究應用[D];華南理工大學;2015年

10 于光帥;一類優(yōu)化算法的改進研究與應用[D];渤海大學;2015年

，

本文編號：2215751