發(fā)布時(shí)間：2017-03-19 10:03

  本文關(guān)鍵詞：基于模因演化算法的有限容量弧路徑問(wèn)題研究，由筆耕文化傳播整理發(fā)布。

【摘要】：有限容量弧路徑問(wèn)題(Capacitated Arc Routing Problem, CARP)是一個(gè)經(jīng)典的帶有約束條件的組合優(yōu)化問(wèn)題,在現(xiàn)實(shí)生活中有非常廣泛的應(yīng)用,如城市道路撒鹽與灑水路徑規(guī)劃,垃圾回收線路規(guī)劃,物流配送網(wǎng)絡(luò)優(yōu)化,輸氣、輸電線路檢修規(guī)劃等等,因此也得到了許多研究者的關(guān)注。由于該問(wèn)題是NP-hard問(wèn)題,對(duì)于精確算法,要在可接受的時(shí)間內(nèi)得到問(wèn)題的最優(yōu)解是非常困難的,并且計(jì)算成本非常之大。因此,本文旨在利用元啟發(fā)式方法在給定時(shí)間內(nèi)取得性能更優(yōu)的次優(yōu)解,為有限容量弧路徑問(wèn)題提供更加有效實(shí)用的解決方案。首先,本文以目前求解CARP較為領(lǐng)先的算法—基于擴(kuò)展鄰域搜索的模因演化算法(MAENS)為基礎(chǔ)算法,提出了三種改進(jìn)方法,即(1)使用錦標(biāo)賽選擇算子篩選父代(MAENS-T);(2)基于個(gè)體適應(yīng)度的自適應(yīng)搜索概率(MAENS-Pls);(3)基于動(dòng)態(tài)參數(shù)的隨機(jī)排序算法(MAENS-Pf)，結(jié)合三種改進(jìn)方法,形成了本文所提出的基于自適應(yīng)擴(kuò)展鄰域搜索的模因演化算法(MAENS-C)，，然后利用C語(yǔ)言編程實(shí)現(xiàn)算法,并采用研究領(lǐng)域內(nèi)的通用測(cè)試集—Egl數(shù)據(jù)集中的三個(gè)實(shí)例對(duì)三種改進(jìn)算法分別進(jìn)行測(cè)試,證明了本文所設(shè)計(jì)算法的有效性。其次,針對(duì)設(shè)計(jì)的各版本算法中包含的參數(shù),利用統(tǒng)計(jì)賽車技術(shù)(Racing Algorithm)與統(tǒng)計(jì)檢驗(yàn)中的非參數(shù)檢驗(yàn)方法對(duì)所有算法在全部的實(shí)驗(yàn)用例上(Egl數(shù)據(jù)集的八個(gè)實(shí)驗(yàn)用例)進(jìn)行了參數(shù)優(yōu)化,大大節(jié)省了參數(shù)優(yōu)化的計(jì)算成本,最終得到了各算法的優(yōu)化參數(shù)組合,為算法評(píng)價(jià)、應(yīng)用奠定了基礎(chǔ)。再次,基于改進(jìn)算法與其相應(yīng)的優(yōu)化參數(shù)組合,利用平均總成本,收斂可靠性,全局尋優(yōu)能力,魯棒穩(wěn)定性,以及時(shí)間復(fù)雜度五個(gè)評(píng)價(jià)指標(biāo),在Egl數(shù)據(jù)集的八個(gè)實(shí)例上進(jìn)行了定量與定性的算法評(píng)價(jià)。本文主要從相同演化代數(shù)和相同時(shí)間復(fù)雜度水平兩個(gè)角度進(jìn)行了比較總結(jié),得出了MAENS-Pls以及三種改進(jìn)方法的結(jié)合算法MAENS-C顯著的優(yōu)于基礎(chǔ)算法MAENS,并且發(fā)現(xiàn)了13個(gè)針對(duì)CARP問(wèn)題的新型最優(yōu)解,進(jìn)一步驗(yàn)證了本文提出的算法能有效地對(duì)局部搜索頻率與深度進(jìn)行雙重優(yōu)化,證明了算法的優(yōu)異性能。最后,將本文的理論研究成果應(yīng)用于路徑規(guī)劃實(shí)例中,利用英國(guó)蘭開(kāi)夏郡Egl數(shù)據(jù)集的路徑服務(wù)需求與地理信息,對(duì)蘭開(kāi)夏郡的路網(wǎng)進(jìn)行了實(shí)例驗(yàn)證,為路徑規(guī)劃與車輛分配提供了優(yōu)化的規(guī)劃方案,并進(jìn)行了優(yōu)化解的可視化呈現(xiàn),為交通領(lǐng)域內(nèi)的路徑規(guī)劃提供了有效的解決方案。
【關(guān)鍵詞】：有限容量弧路徑問(wèn)題 模因演化算法 擴(kuò)展鄰域搜索 自適應(yīng)局部搜索頻率與深度 動(dòng)態(tài)隨機(jī)排序算法 算法魯棒性優(yōu)化 解的可視化
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：U116
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-13
• 1 引言13-21
• 1.1 問(wèn)題概述14
• 1.2 研究現(xiàn)狀14-19
• 1.2.1 構(gòu)造型啟發(fā)式算法15-16
• 1.2.2 元啟發(fā)式算法16-17
• 1.2.3 模因演化算法17-18
• 1.2.4 算法評(píng)估18-19
• 1.3 研究思路與論文結(jié)構(gòu)19-21
• 2 有限容量弧路徑問(wèn)題模型與算法21-34
• 2.1 有限容量弧路徑問(wèn)題模型定義21-23
• 2.2 模因演化算法框架23-24
• 2.3 基于擴(kuò)展鄰域搜索的模因演化算法24-34
• 2.3.1 處理約束條件24-27
• 2.3.2 算法的搜索能力27-30
• 2.3.3 基于擴(kuò)展鄰域搜索的模因演化算法30-33
• 2.3.4 當(dāng)前算法缺陷分析33-34
• 3 基于自適應(yīng)擴(kuò)展鄰域搜索的模因演化算法設(shè)計(jì)34-43
• 3.1 基于錦標(biāo)賽選擇機(jī)制的父代選擇算子34
• 3.2 基于個(gè)體適應(yīng)度的自適應(yīng)局部搜索概率34-36
• 3.2.1 遞增式局部搜索概率34-35
• 3.2.2 遞減式局部搜索概率35-36
• 3.3 基于動(dòng)態(tài)參數(shù)的隨機(jī)排序算法36-37
• 3.4 算法實(shí)現(xiàn)與測(cè)試37-38
• 3.5 結(jié)果與討論38-43
• 4 基于統(tǒng)計(jì)賽車技術(shù)的參數(shù)優(yōu)化43-52
• 4.1 參數(shù)優(yōu)化方法論43-44
• 4.2 MAENS-PF的參數(shù)優(yōu)化44-46
• 4.2.1 參數(shù)設(shè)定44-45
• 4.2.2 實(shí)驗(yàn)及結(jié)果分析45-46
• 4.3 MAENS-PLS的參數(shù)優(yōu)化46-48
• 4.3.1 參數(shù)設(shè)定46-47
• 4.3.2 實(shí)驗(yàn)及結(jié)果分析47-48
• 4.4 MAENS-C的參數(shù)優(yōu)化48-49
• 4.4.1 參數(shù)設(shè)定48-49
• 4.4.2 實(shí)驗(yàn)及結(jié)果分析49
• 4.5 MAENS的參數(shù)優(yōu)化49-50
• 4.6 結(jié)果與討論50-52
• 5 算法評(píng)價(jià)與比較52-62
• 5.1 實(shí)驗(yàn)分析52-56
• 5.2 統(tǒng)計(jì)方法分析56-58
• 5.3 結(jié)果與討論58-62
• 6 算法求解路徑優(yōu)化方案實(shí)例62-68
• 6.1 英國(guó)蘭開(kāi)夏郡實(shí)例信息62-64
• 6.2 路徑優(yōu)化方案可視化64-67
• 6.3 分析與討論67-68
• 7 總結(jié)與展望68-73
• 7.1 研究結(jié)論68-69
• 7.2 研究創(chuàng)新點(diǎn)69-70
• 7.3 研究局限性70-71
• 7.4 未來(lái)展望71-73
• 參考文獻(xiàn)73-78
• 附錄A78-80
• 附錄B80-83
• 作者簡(jiǎn)歷及攻讀碩士學(xué)位期間取得的研究成果83-85
• 學(xué)位論文數(shù)據(jù)集85

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 郭振宇;程博;葉敏;康龍?jiān)?曹秉剛;;一種并行混沌差異演化算法[J];西安交通大學(xué)學(xué)報(bào);2007年03期

2 盧青波;張學(xué)良;溫淑花;蘭國(guó)生;劉麗琴;;多種群協(xié)作差異演化算法及其應(yīng)用[J];現(xiàn)代制造工程;2012年02期

3 熊銀鍵,嵇啟春;演化算法在非線性參數(shù)估計(jì)中的應(yīng)用[J];西安建筑科技大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年01期

4 劉明廣;李高揚(yáng);;差異演化算法在機(jī)械優(yōu)化設(shè)計(jì)中的應(yīng)用[J];機(jī)床與液壓;2006年05期

5 戴福祥;胡曉林;;基于鄰域探索的多目標(biāo)演化算法[J];武漢理工大學(xué)學(xué)報(bào);2009年09期

6 蘭國(guó)生;張學(xué)良;盧青波;溫淑花;劉麗琴;;簡(jiǎn)單差異演化算法及其在裝配公差優(yōu)化中的應(yīng)用[J];機(jī)械設(shè)計(jì)與制造;2011年05期

7 王志剛;夏慧明;;基于差異演化算法的化學(xué)方程式配平研究[J];哈爾濱商業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年04期

8 韓珂;楊俊鵬;;求解旅行商問(wèn)題的分布式演化算法[J];華北水利水電學(xué)院學(xué)報(bào);2013年04期

9 胡中波;蘇清華;;求解混合變量?jī)?yōu)化問(wèn)題的自適應(yīng)差分演化算法[J];武漢理工大學(xué)學(xué)報(bào);2010年03期

10 蘭國(guó)生;張學(xué)良;盧青波;溫淑花;;增強(qiáng)差異演化算法及其應(yīng)用[J];工程設(shè)計(jì)學(xué)報(bào);2010年04期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前3條

1 馮珊;李鋒;周凱波;;面向演化算法應(yīng)用的智能體系統(tǒng)建模與仿真研究[A];西部開(kāi)發(fā)與系統(tǒng)工程——中國(guó)系統(tǒng)工程學(xué)會(huì)第12屆年會(huì)論文集[C];2002年

2 張文俊;謝曉鋒;馬君;;并行演化算法在半導(dǎo)體器件綜合中的應(yīng)用[A];2006年全國(guó)開(kāi)放式分布與并行計(jì)算學(xué)術(shù)會(huì)議論文集（二）[C];2006年

3 謝柏橋;戴光明;鄭蔚;王劍文;;有指導(dǎo)的多目標(biāo)演化算法在區(qū)域星座設(shè)計(jì)中的應(yīng)用[A];中國(guó)宇航學(xué)會(huì)深空探測(cè)技術(shù)專業(yè)委員會(huì)第四屆學(xué)術(shù)年會(huì)論文集[C];2007年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 彭晟;演化算法的靜電場(chǎng)論模型[D];武漢大學(xué);2011年

2 陳明;演化算法漸近行為的若干問(wèn)題研究[D];武漢大學(xué);2012年

3 彭飛;實(shí)值演化算法投資組合研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

4 萬(wàn)書(shū)振;動(dòng)態(tài)環(huán)境下差分演化算法研究與應(yīng)用[D];武漢理工大學(xué);2012年

5 魏波;交互式與自適應(yīng)演化算法研究[D];武漢大學(xué);2013年

6 賴鑫生;演化算法與混合算法的性能研究[D];華南理工大學(xué);2014年

7 武志峰;差異演化算法及其應(yīng)用研究[D];北京交通大學(xué);2009年

8 陳天石;演化算法的計(jì)算復(fù)雜性研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

9 龔文引;差分演化算法的改進(jìn)及其在聚類分析中的應(yīng)用研究[D];中國(guó)地質(zhì)大學(xué);2010年

10 吳志健;演化優(yōu)化及其在微分方程反問(wèn)題中的應(yīng)用[D];武漢大學(xué);2004年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 楊穎;一種多差分向量的自適應(yīng)差分演化算法[D];浙江大學(xué);2015年

2 陳偉;隊(duì)伍演化算法及其在微波電路設(shè)計(jì)中的應(yīng)用[D];杭州電子科技大學(xué);2015年

3 吳昊;多群體并行演化算法的研究[D];南京郵電大學(xué);2015年

4 要婷婷;基于模因演化算法的有限容量弧路徑問(wèn)題研究[D];北京交通大學(xué);2016年

5 戴志晃;一種基于熵量守恒的改進(jìn)演化算法的研究[D];江西理工大學(xué);2010年

6 潘偉豐;一種基于平均矢量偏差的仿生演化算法[D];江西理工大學(xué);2008年

7 胡中波;差分演化算法及其在函數(shù)優(yōu)化中的應(yīng)用研究[D];武漢理工大學(xué);2006年

8 李程俊;組合優(yōu)化問(wèn)題的并行演化算法研究[D];武漢理工大學(xué);2003年

9 趙永翔;多目標(biāo)差分演化算法的構(gòu)造及其應(yīng)用[D];武漢理工大學(xué);2007年

10 張?chǎng)?協(xié)同演化算法及其在組合投資中的研究與應(yīng)用[D];哈爾濱工程大學(xué);2011年

  本文關(guān)鍵詞：基于模因演化算法的有限容量弧路徑問(wèn)題研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：255865