發(fā)布時間：2020-06-16 21:05

【摘要】：我們的社會豐富多彩,包羅萬象,生活在大數(shù)據(jù)時代,車輛運輸連接著我們生活的方方面面。車輛路由問題是一個在物流運輸和資源分配等方面都有著非常廣泛的應(yīng)用的組合優(yōu)化問題,是旅行商問題的進(jìn)一步擴展,主要研究的問題是如何對車輛運輸?shù)穆窂竭M(jìn)行優(yōu)化以及如何合理的調(diào)配車輛。隨著工業(yè)設(shè)計以及科學(xué)研究領(lǐng)域的各類復(fù)雜優(yōu)化問題的不斷深入,使用傳統(tǒng)的優(yōu)化算法在解決復(fù)雜優(yōu)化問題時遇到了很多的困難,在這種背景下,群體智能優(yōu)化算法的產(chǎn)生為解決復(fù)雜優(yōu)化問題提供了新的思路。在眾多群體智能算法中,遺傳算法因其強大的全局搜索功能、魯棒性高、適應(yīng)性強、計算過程簡單、便于與其他算法結(jié)合等特征,已廣泛應(yīng)用于工程優(yōu)化、系統(tǒng)識別、自動控制等領(lǐng)域,是解決NP難問題的更有效的全局方法。本文使用遺傳算法,旨在從理論和實驗兩方面多角度的分析和驗證染色體編碼方案的設(shè)計對于遺傳算法解決多旅行商問題的至關(guān)重要的地位,綜合全局搜索和局部搜索的平衡機制解決問題�；谙鄬饪臻g概念,首先分析三種染色體編碼方案對應(yīng)的解空間在極限意義下的相對大小關(guān)系,接下來分析旅行商數(shù)與城市數(shù)在不同情形下解空間的近似相對大小關(guān)系。本文對搜索空間定量分析的理論結(jié)果對工程問題的求解可以提供科學(xué)的指導(dǎo)意義。從而將其應(yīng)用于目前較為流行的車輛路由優(yōu)化問題中,創(chuàng)造性地提出了一種基于兩段式編碼方案的遺傳算法。同時,本文在研究過程中重點關(guān)注遺傳算法中染色體編碼方式對解空間大小的影響,以及這種影響對群體尋求最優(yōu)位置的指導(dǎo)。提出了一種基于兩段式編碼的遺傳算法,采用先路由后集群的方法改進(jìn)初始解的構(gòu)造過程,并使用C-W-saving算法優(yōu)化車輛的路線,優(yōu)化選擇操作中的選擇策略,優(yōu)化解的選擇方法,并調(diào)整插入算子,對所選父代染色體進(jìn)行特定的交叉變異操作,使用最大重疊交叉對子代進(jìn)行交叉操作。最后在小數(shù)據(jù)集上進(jìn)行仿真測試算法的收斂速度,并在大數(shù)據(jù)集上,通過與原始算法作對比來表明該算法的有效性。
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：U116.2;TP18
【圖文】：

圖２＿１解２間編碼解碼逡逑編碼是實際問題和遺傳算法之間的橋梁，遺傳算法中的遺傳算法不能直接實際問題的實際解空間，所以需要將要處理的實際優(yōu)化問題的解空間轉(zhuǎn)化為空間。使用遺傳算法解決實際的優(yōu)化問題時，首先要處理的問題就是染色體方式的選取。好的染色體編碼策略可以大大提高算法效率，避免算法做一些功，不好的編碼方法會帶來算法的不適應(yīng)，帶來大量冗余解，而使算法無法。編碼方法不斷發(fā)展，常用的編碼主要有以下幾種：逡逑（１）二進(jìn)制編碼：二進(jìn)制編碼方式是遺傳算法中最常用的一種編碼方法。二編碼是由０、１構(gòu)成的，首先將實際優(yōu)化問題的解空間變?yōu)橛桑�、１�?gòu)成的編間，然后在編碼空間上進(jìn)行下續(xù)的選擇、交叉、變異等操作，在問題得到最后再將后代解碼成實際優(yōu)化問題適應(yīng)的解空間。它的簡單易行是它成為最案的重要原因，但在一些優(yōu)化問題中，二進(jìn)制編碼因為只能表示幾種狀態(tài)不太適用。逡逑（２）實數(shù)編碼：對于染色體ＸＭｘｐ邋ｘ２，…，ｘｆ，…，ｘｎ），Ｋ／分，ｘｔ．ｅＲ

邐Ｖ邐．／逡逑圖２＿１解２間編碼解碼逡逑編碼是實際問題和遺傳算法之間的橋梁，遺傳算法中的遺傳算法不能直接處逡逑理實際問題的實際解空間，所以需要將要處理的實際優(yōu)化問題的解空間轉(zhuǎn)化為編逡逑碼空間。使用遺傳算法解決實際的優(yōu)化問題時，首先要處理的問題就是染色體編逡逑碼方式的選取。好的染色體編碼策略可以大大提高算法效率，避免算法做一些無逡逑用功，不好的編碼方法會帶來算法的不適應(yīng)，帶來大量冗余解，而使算法無法進(jìn)逡逑行。編碼方法不斷發(fā)展，常用的編碼主要有以下幾種：逡逑（１）

【相似文獻(xiàn)】

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

1 俞慶生;林冬梅;王東;;多旅行商問題研究綜述[J];價值工程;2012年02期

2 吳云;姜麟;劉強;;基于并行遺傳算法多旅行商問題的求解[J];微型電腦應(yīng)用;2011年07期

3 牟廉明;;子旅行商問題及其蟻群求解算法[J];計算機應(yīng)用與軟件;2011年11期

4 李天龍;呂勇哉;;基于自組織優(yōu)化算法的一類多旅行商問題[J];計算機應(yīng)用;2010年02期

5 崔鵬;;多源點的旅行商問題的一種求解方法[J];科協(xié)論壇(下半月);2010年09期

6 王海龍;周輝仁;魏穎輝;;基于遺傳算法的一類多旅行商問題研究[J];計算機應(yīng)用;2009年01期

7 李鋒;魏瑩;;基于仿真的遺傳算法求解動態(tài)旅行商問題[J];系統(tǒng)管理學(xué)報;2009年05期

8 李飛;白艷萍;;用遺傳算法求解旅行商問題[J];中北大學(xué)學(xué)報(自然科學(xué)版);2007年01期

9 趙曦;;廣義旅行商問題與旅行商問題的轉(zhuǎn)化[J];電腦知識與技術(shù)(學(xué)術(shù)交流);2007年05期

10 江賀;張憲超;陳國良;;有向黑白旅行商問題[J];計算機學(xué)報;2007年03期

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

1 馮純伯;;旅行商問題的一種解法[A];1991年控制理論及其應(yīng)用年會論文集（下）[C];1991年

2 李大衛(wèi);王夢光;;熱軋調(diào)度與多旅行商問題[A];1996年中國控制會議論文集[C];1996年

3 張雷;鄭維敏;;廣義旅行商問題、放映員問題和一類調(diào)度模型[A];1996年中國控制會議論文集[C];1996年

4 熊翠;吳慧萍;李波;;多旅行商問題遺傳算法求解及其改進(jìn)[A];第四屆中國智能計算大會論文集[C];2010年

5 劉春波;潘豐;楊丹;;基于改進(jìn)的蟻群算法在中國旅行商問題中的求解[A];2007中國控制與決策學(xué)術(shù)年會論文集[C];2007年

6 賈亞軍;叢爽;;粒子群與模擬退火的混合算法求解旅行商問題[A];'2010系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會議論文集[C];2010年

7 李麗;程玉榮;牛奔;;離散人工蜂群算法求解旅行商問題[A];第十三屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2011年

8 韓愛麗;朱大銘;;旅行商問題的一種新DNA編碼方案[A];2006年全國理論計算機科學(xué)學(xué)術(shù)年會論文集[C];2006年

9 張煒;李勇剛;周曉君;;一種求解有城市訪問順序約束旅行商問題的狀態(tài)轉(zhuǎn)移算法[A];2018中國自動化大會(CAC2018)論文集[C];2018年

10 董亞非;譚剛軍;張社民;;基于粘貼系統(tǒng)求解TSP問題[A];提高全民科學(xué)素質(zhì)、建設(shè)創(chuàng)新型國家——2006中國科協(xié)年會論文集（下冊）[C];2006年

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

1 孟祥虎;著色旅行商問題及其動態(tài)化研究[D];東南大學(xué);2017年

2 譚陽;求解廣義旅行商問題的若干進(jìn)化算法研究[D];華南理工大學(xué);2013年

3 張夢穎;不確定因素下路徑規(guī)劃問題研究[D];中國科學(xué)技術(shù)大學(xué);2016年

4 魏航;基于鄰接實數(shù)矩陣編碼的路徑優(yōu)化進(jìn)化算法的研究[D];華南理工大學(xué);2017年

5 王剛;兩類圈問題的算法研究[D];國防科學(xué)技術(shù)大學(xué);2013年

6 包曉光;一些路線問題的算法設(shè)計與分析[D];華東理工大學(xué);2012年

7 李茂軍;單親遺傳算法理論及應(yīng)用[D];湖南大學(xué);2002年

8 曾華;隨機顧客和需求的配送優(yōu)化[D];山東大學(xué);2012年

9 李娜娜;仿生算法及其在專家分配問題中的應(yīng)用[D];天津大學(xué);2008年

10 費威;最小調(diào)整法的改進(jìn)及其在經(jīng)濟優(yōu)化中的應(yīng)用[D];東北財經(jīng)大學(xué);2010年

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

1 郭賽;多旅行商問題的解空間分析及其車輛路由優(yōu)化的應(yīng)用研究[D];北京郵電大學(xué);2019年

2 束東來;基于遺傳算法的多旅行商問題的優(yōu)化[D];安慶師范大學(xué);2018年

3 謝曾慧;求解多目標(biāo)旅行商問題的改進(jìn)蟻群優(yōu)化算法研究[D];東北大學(xué);2017年

4 師喜婷;狼群算法的改進(jìn)及其在復(fù)雜函數(shù)優(yōu)化問題中的應(yīng)用[D];西安理工大學(xué);2018年

5 鄧昶博;改進(jìn)蟻群算法解決電商快遞場景下的多目標(biāo)多旅行商問題[D];華南理工大學(xué);2018年

6 鄭碩;新型啟發(fā)式算法求解旅行商問題及其衍生問題[D];天津大學(xué);2017年

7 趙麗娜;帶油耗的單商品取送貨旅行商問題研究[D];沈陽師范大學(xué);2016年

8 徐東鎮(zhèn);蟻群算法及其在廣義旅行商問題求解中的應(yīng)用[D];合肥工業(yè)大學(xué);2007年

9 胡平;群集智能算法在不確定旅行商問題中的應(yīng)用研究[D];吉林大學(xué);2007年

10 袁豪;旅行商問題的研究與應(yīng)用[D];南京郵電大學(xué);2017年

本文編號：2716585