【摘要】：旅行商問題是著名的路徑規(guī)劃問題,在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用。伴隨著城市數(shù)目的增多,傳統(tǒng)的算法在旅行商問題巨大搜索空間里的尋優(yōu)能力越來越差,很難達(dá)到精確地求出最優(yōu)解的目的。如何設(shè)計(jì)出一個性能高效的近似求解算法成了眾多學(xué)者的研究重點(diǎn)。遺傳算法以其優(yōu)良的性能,擅長全局搜索的優(yōu)點(diǎn),成為了研究組合優(yōu)化問題中常用的算法。但長期的實(shí)際應(yīng)用中,暴露了遺傳算法難以對局部空間進(jìn)行搜索,導(dǎo)致算法進(jìn)化后期搜索效率偏低,解質(zhì)量不高的缺點(diǎn)。因此,近年來學(xué)者通過結(jié)合局部搜索來提升算法的性能。目前,解旅行商問題局部尋優(yōu)較好的算子有opt的各種形式(2-opt,3-opt等)以及Lin-Kernighan(LK),然而因?yàn)長K的復(fù)雜性高,通常較少使用。另外,由于opt的固有特性,其各種形式的局部搜索算子都難較精細(xì)地對個體鄰域進(jìn)行搜索。綜上所述,本文將單點(diǎn)插入算子(Single Insertion,SI)、交換算子(Swap)引入TSP問題的局部搜索,并結(jié)合2-opt,組成一種特有的局部搜索算子集合。同時(shí),鑒于遺傳算法在全局搜索能力上的優(yōu)秀表現(xiàn),將上述算子集合嵌入遺傳算法,從而形成混合遺傳算法(HGA),并以其對TSP問題求解。通過國際通用的TSPLIB中不同城市規(guī)模的數(shù)據(jù)進(jìn)行測試,并對比5種算法的解質(zhì)量,結(jié)果證明了該混合遺傳算法的有效性。針對基于隨機(jī)機(jī)會約束規(guī)劃模型的旅行商問題,本文以基于TSPLIB測試算例生成的不確定旅行商問題測試數(shù)據(jù)對UHGA算法進(jìn)行性能衡量和算法驗(yàn)證,并給出相應(yīng)的實(shí)驗(yàn)結(jié)果分析。
【圖文】：

HGA算法得到的Att48最優(yōu)路徑軌跡圖

種算法最優(yōu)解質(zhì)量對比
【學(xué)位授予單位】：安慶師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：C81

【相似文獻(xiàn)】

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

1 袁群;左弈;;基于改進(jìn)混合遺傳算法的冷鏈物流配送中心選址優(yōu)化[J];上海交通大學(xué)學(xué)報(bào);2016年11期

2 劉蕊蕊;;基于多目標(biāo)混合遺傳算法認(rèn)知無線電頻譜分配[J];雞西大學(xué)學(xué)報(bào);2016年12期

3 楊書森;郭順生;;基于混合遺傳算法的生產(chǎn)調(diào)度研究[J];機(jī)械制造;2017年10期

4 楊亞輝;;基于混合遺傳算法的機(jī)床夾具夾緊力優(yōu)化[J];機(jī)械設(shè)計(jì)與制造工程;2016年10期

5 毛政濤;劉新文;;應(yīng)用雙層混合遺傳算法優(yōu)化大規(guī)模換熱網(wǎng)絡(luò)[J];寧波工程學(xué)院學(xué)報(bào);2014年01期

6 朱傳偉;童幼堂;董受全;;混合遺傳算法在艦空導(dǎo)彈武器系統(tǒng)火力分配中的應(yīng)用[J];艦船電子工程;2014年07期

7 王威;徐兵;岳曉峰;;基于機(jī)器加工時(shí)間最短的混合遺傳算法[J];長春工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年03期

8 高光敏;趙亮;何秋月;王凱;孫洪波;;改進(jìn)混合遺傳算法在無功優(yōu)化的應(yīng)用研究[J];長春工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2011年01期

9 朱小娟;高慶忠;宋福圣;;基于自適應(yīng)混合遺傳算法的協(xié)調(diào)控制系統(tǒng)[J];自動化與儀器儀表;2009年03期

10 顧曉芬;郝永平;唐健;;一種基于混合遺傳算法的車間調(diào)度算法[J];自動化技術(shù)與應(yīng)用;2008年11期

相關(guān)會議論文 前10條

1 劉瓊昕;陳嘉玉;宋曄;蘇思悅;;混合遺傳算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用[A];第十一屆全國信號和智能信息處理與應(yīng)用學(xué)術(shù)會議專刊[C];2017年

2 張海波;陳行行;;混合遺傳算法在智能天線波束成型中的應(yīng)用[A];重慶市電機(jī)工程學(xué)會2010年學(xué)術(shù)會議論文集[C];2010年

3 吳海兵;劉萍;;混合遺傳算法在物流配送路徑優(yōu)化問題中的應(yīng)用[A];'2006系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會論文集[C];2006年

4 王永生;曹貝;肖立伊;;基于混合遺傳算法的測試殼優(yōu)化[A];第四屆中國測試學(xué)術(shù)會議論文集[C];2006年

5 李平;;客戶成套訂單配送策略混合遺傳算法研究[A];第九屆中國青年信息與管理學(xué)者大會論文集[C];2007年

6 馬倩;左浩毅;;混合遺傳算法和高斯牛頓算法分析電荷交換復(fù)合譜的數(shù)據(jù)[A];第十八屆全國光散射學(xué)術(shù)會議摘要文集[C];2015年

7 何大闊;凌君;顧大為;王福利;;基于減聚類的混合遺傳算法[A];第三屆中國智能計(jì)算大會論文集[C];2009年

8 侯志祥;;基于混合遺傳算法的連續(xù)系統(tǒng)參數(shù)辨識[A];第二十六屆中國控制會議論文集[C];2007年

9 宋莉波;徐學(xué)軍;孫延明;查靚;;一種求解flexible job-shop調(diào)度問題的混合遺傳算法[A];系統(tǒng)工程與和諧管理——第十屆全國青年系統(tǒng)科學(xué)與管理科學(xué)學(xué)術(shù)會議論文集[C];2009年

10 劉轍;彭亮;崔廣才;吳學(xué)禮;;混合遺傳算法在車間調(diào)度中的應(yīng)用[A];中國自動化學(xué)會全國第九屆自動化新技術(shù)學(xué)術(shù)交流會論文集[C];2004年

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

1 陶澤;基于Petri網(wǎng)和混合遺傳算法的JSP優(yōu)化調(diào)度[D];東北大學(xué);2006年

2 程蓉;復(fù)雜生產(chǎn)環(huán)境下優(yōu)化調(diào)度方法研究與系統(tǒng)實(shí)現(xiàn)[D];華中科技大學(xué);2006年

3 仁慶道爾吉;車間作業(yè)調(diào)度問題的多目標(biāo)模型建立及其算法[D];西安電子科技大學(xué);2013年

4 霍紅衛(wèi);遺傳算法在圖論和優(yōu)化中的應(yīng)用[D];西安電子科技大學(xué);2000年

5 朱云飛;一種用進(jìn)化方法求解魯棒最優(yōu)問題的研究[D];中南大學(xué);2011年

6 彭北青;第三方物流配送車輛路徑問題模型及算法研究[D];華中科技大學(xué);2009年

7 張相賢;基于極值理論的金融資產(chǎn)配置研究[D];東華大學(xué);2011年

8 童孝忠;大地電磁測深有限單元法正演與混合遺傳算法正則化反演研究[D];中南大學(xué);2008年

9 鄭加駒;超磁致伸縮換能器滯回非線性模型的研究[D];天津大學(xué);2009年

10 劉曉霞;基于OCTPN和混合遺傳算法的JSP多目標(biāo)優(yōu)化調(diào)度[D];東北大學(xué);2008年

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

1 羅書敏;基于混合遺傳算法的可重入混合流水車間調(diào)度優(yōu)化研究[D];鄭州大學(xué);2018年

2 梅俊;基于混合遺傳算法的TSP優(yōu)化問題求解[D];安慶師范大學(xué);2018年

3 李文磊;基于混合遺傳算法的轉(zhuǎn)運(yùn)車調(diào)度優(yōu)化研究[D];東北大學(xué);2015年

4 于豐平;基于混合遺傳算法的快遞車輛路徑優(yōu)化問題的研究[D];青島科技大學(xué);2017年

5 李小寧;關(guān)于混合遺傳算法改進(jìn)的研究[D];西北大學(xué);2008年

6 王俊麗;基于改進(jìn)的混合遺傳算法的排課問題研究[D];大連海事大學(xué);2013年

7 任剛;多種群退火貪婪混合遺傳算法的研究與應(yīng)用[D];鄭州大學(xué);2005年

8 薛凌霄;基于共軛梯度法的混合遺傳算法研究[D];福建師范大學(xué);2009年

9 陳磊;基于混合遺傳算法的車輛調(diào)度優(yōu)化[D];重慶師范大學(xué);2015年

10 劉輝;基于混合遺傳算法的有限能力作業(yè)車間調(diào)度[D];河北工業(yè)大學(xué);2006年

，

本文編號：2659290