在貨物配送路徑規(guī)劃問題中,為了保持基本布谷鳥算法中萊維飛行機(jī)制與偏好隨機(jī)游動(dòng)策略的特點(diǎn),文中提出了基于定向變異的布谷鳥算法和求解配送路徑問題的完整有效方法。首先采用快速排序法將實(shí)數(shù)編碼個(gè)體的每一維元素映射成問題的城市編號(hào),從而建立算法與問題模型之間的聯(lián)系;然后運(yùn)用鄰域搜索法決定城市訪問的次序,即通過各城市之間的距離尋找當(dāng)前城市的鄰近城市,以增強(qiáng)算法的收斂速度。同時(shí),在算法局部搜索機(jī)制中,通過平均適應(yīng)度函數(shù)將算法劃分為雙子群,然后針對(duì)不同的子群體采用相應(yīng)的定向變異機(jī)制,從而使算法搜索具有目的性,以增強(qiáng)算法的局部搜索能力。對(duì)標(biāo)準(zhǔn)TSP數(shù)據(jù)庫中測試算例的求解實(shí)驗(yàn)結(jié)果表明,所提算法在各個(gè)算例中的求解偏差率均有明顯降低,無論在最優(yōu)值還是平均值的偏差率上都小于其他幾種對(duì)比算法,對(duì)于路徑規(guī)劃問題的求解效果較優(yōu)。 

【文章來源】：計(jì)算機(jī)科學(xué). 2019,46(07)北大核心

【文章頁數(shù)】：7 頁

【部分圖文】：

圖５Ｃｈｉｎａ３１的適應(yīng)度對(duì)比曲線Ｆｉｇ．５ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＣｈｉｎａ３１

，本文也通過圖６－圖１０對(duì)ＤＶＣＳ算法在５個(gè)算例上求解的最優(yōu)路徑進(jìn)行了展示。圖６Ｂｕｒｍａ１４上的最優(yōu)路徑Ｆｉｇ．６ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＢｕｒｍａ１４圖７Ｕｌｙｓｓｅｓｓ１６上的最優(yōu)路徑Ｆｉｇ．７ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＵｌｙｓｓｅｓｓ１６圖８Ｕｌｙｓｓｅｓｓ２２上的最優(yōu)路徑Ｆｉｇ．８ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＵｌｙｓｓｅｓｓ２２圖９Ｅｉｌ５１上的最優(yōu)路徑Ｆｉｇ．９ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＥｉｌ５１圖１０Ｃｈｉｎａ３１上的最優(yōu)路徑Ｆｉｇ．１０ＯｐｔｉｍａｌｐａｔｈｍａｐｏｎＣｈｉｎａ３１由圖６－圖１０可知，本文算法所求最優(yōu)路徑的走勢清晰，并未出現(xiàn)任何路徑交叉現(xiàn)象，這說明ＤＶＣＳ算法在求解貨物配送路徑規(guī)劃問題時(shí)具有一定的優(yōu)勢，且此算法在實(shí)際問題的應(yīng)用中也具有較好的適應(yīng)性與可行性。結(jié)束語本文針對(duì)貨物配送路徑規(guī)劃問題，設(shè)計(jì)了一種映射關(guān)系，從而將離散型的問題轉(zhuǎn)化為連續(xù)型問題進(jìn)行求解，并提出了一種ＤＶＣＳ求解算法。首先運(yùn)用快速排序法將實(shí)數(shù)編碼的種群個(gè)體映射成問題中車輛團(tuán)隊(duì)需要訪問的城市編號(hào)，從而建立算法與實(shí)際問題模型之間的關(guān)系。然后運(yùn)用各城市之間的距離進(jìn)行鄰域搜索，決定各城市的訪問次序，此種方式通過對(duì)鄰近城市的搜索可以加快算法的收斂速度，提高算法搜索的效率。同時(shí)，采用定向變異的方式優(yōu)化布谷鳥算法的局部搜索機(jī)制，通過平均適應(yīng)度函數(shù)將種群個(gè)體分為優(yōu)質(zhì)子群體與劣質(zhì)子群體兩類，針對(duì)不同子群體，采用不同的變異機(jī)制，從而保持算法種群的靈活性與多樣性，增

圖１Ｂｕｒｍａ１４的適應(yīng)度對(duì)比曲線Ｆｉｇ．１ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＢｕｒｍａ１４圖２Ｕｌｙｓｓｅｓｓ１６的適應(yīng)度對(duì)比曲線Ｆｉｇ．２ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＵｌｙｓｓｅｓｓ１６圖３Ｕｌｙｓｓｅｓｓ２２的適應(yīng)度對(duì)比曲線Ｆｉｇ．３ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＵｌｙｓｓｅｓｓ２２圖４Ｅｉｌ５１的適應(yīng)度對(duì)比曲線Ｆｉｇ．４ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＥｉｌ５１圖５Ｃｈｉｎａ３１的適應(yīng)度對(duì)比曲線Ｆｉｇ．５ＦｉｔｎｅｓｓｃｕｒｖｅｏｆＣｈｉｎａ３１上述實(shí)驗(yàn)結(jié)果顯示：本文算法在５個(gè)算例上的收斂速度明顯快于其他３種算法，且在尋優(yōu)過程中出現(xiàn)拐點(diǎn)的次數(shù)較少，尤其是算例Ｕｌｙｓｓｅｓ１６上的收斂曲線在算法搜索前期收斂速度非常快，收斂曲線幾乎垂直向下并且曲線較為光滑。對(duì)于算例Ｂｕｒｍａ１４，雖然ＤＶＣＳ算法前期的收斂速度與其他３種算法相差無幾，但是該算法仍在進(jìn)行深度挖掘。對(duì)于算例Ｕｌｙｓｓｅｓ２２，４種算法均出現(xiàn)了多處拐點(diǎn)，但是本文算法的收斂速度仍快于其他３種算法，且跳離局部極值的速度也較快。對(duì)于算例Ｅｉｌ５１、Ｃｈｉｎａ３１（中國３１個(gè)城市），本文算法呈弧狀形態(tài)并不斷進(jìn)行深度搜索，而其他３種算法在搜索后期幾乎呈水平直線狀態(tài)，搜索能力減弱�；谏鲜龇治觯疚乃惴▽�(yōu)曲線的下降速度均快于其他算法，收斂速度得到了提升。這是因?yàn)楸疚乃惴ㄔ谟成溥^程中，通過鄰域搜索方式中鄰近表的決策使每次訪問的城市都以自身最近城市為出發(fā)點(diǎn)進(jìn)行訪問，從而縮短了路徑的距離，增強(qiáng)了算法的收斂速度。以

【參考文獻(xiàn)】：
期刊論文
[1]基因-表現(xiàn)型的布谷鳥算法求解旅行商問題[J]. 林敏,鐘一文,劉必雄,林曉宇.  計(jì)算機(jī)工程與應(yīng)用. 2017(24)
[2]混合模擬退火的布谷鳥算法研究[J]. 馬燦,劉堅(jiān),余方平.  小型微型計(jì)算機(jī)系統(tǒng). 2016(09)
[3]求解TSP問題的離散狼群算法[J]. 吳虎勝,張鳳鳴,李浩,梁曉龍.  控制與決策. 2015(10)
[4]新型元啟發(fā)式布谷鳥搜索算法[J]. 李煜,馬良.  系統(tǒng)工程. 2012(08)

碩士論文
[1]混合遺傳算法和模擬退火算法在TSP中的應(yīng)用研究[D]. 劉錦.華南理工大學(xué) 2014



本文編號(hào)：2980807