本文關鍵詞：基于淘汰機制的果蠅優(yōu)化算法求解車輛路徑問題

  更多相關文章： 車輛路徑問題 群智能 果蠅優(yōu)化算法 旅行商問題 淘汰機制 算子

【摘要】：近些年來,隨著社會節(jié)奏的加速、電子商務的蓬勃發(fā)展以及各大O2O平臺的異軍突起,越來越多的人開始選擇網(wǎng)上購物、網(wǎng)上訂餐,作為這些活動中的重要環(huán)節(jié),物流開始在現(xiàn)實社會中扮演越來越重要的角色,但與之而來的則是物流代價的不斷增加,因此,如何有效的減少物流代價,越來越成為人們關注的熱點問題。在現(xiàn)實生活中,整個物流活動包括運輸、儲存、裝卸、包裝、流通加工、配送、信息處理等基本過程。根據(jù)相關統(tǒng)計,在整個物流成本中,配送成本所占比例約為53%,占比超過一半,因此,減少物流代價的關鍵在于減少配送代價。車輛路徑問題(VRP)正是對物流配送活動的抽象,該問題是一個組合優(yōu)化問題,也是一個典型的NP難問題,由Dantzing和Ramser兩位科學家于1959年首次提出。目前求解VRP問題主要有兩類方法:一類是可以求得確切解的精確算法,例如動態(tài)規(guī)劃法、分支限定法、線性規(guī)劃法等;另一類是可以在較短時間內(nèi)求得近似最優(yōu)解的啟發(fā)式算法,例如禁忌搜索算法、遺傳算法、蟻群算法等。果蠅優(yōu)化算法是臺灣學者潘文超根據(jù)果蠅覓食行為于2011年提出的一種新的群智能算法,該算法易于理解、實現(xiàn)簡單,而且果蠅的嗅覺搜索過程對于解空間具有很好的擴展能力,但是果蠅的視覺搜索過程很容易使算法陷入局部最優(yōu)。在充分研究了果蠅算法的優(yōu)缺點之后,本文提出了一種改進的果蠅優(yōu)化算法,并將其用于求解旅行商問題(TSP)和VRP問題,最后在相關數(shù)據(jù)集上進行了仿真實驗,證明了算法的可行性和有效性。本文的主要工作有以下幾點:(1)介紹了VRP問題的研究背景與意義,VRP問題的描述、數(shù)學模型及其分類,以及該問題的國內(nèi)外研究現(xiàn)狀。(2)充分研究了果蠅優(yōu)化算法的基本原理,并基于該算法提出了一種改進的果蠅優(yōu)化算法。改進后的算法加強了果蠅的視覺搜索能力,在其他果蠅向最優(yōu)果蠅靠近的過程中,是緩慢的向最優(yōu)果蠅靠近,而不是立刻到達最優(yōu)果蠅所在的位置,這樣就有效的減小了算法陷入局部最優(yōu)的可能性。同時,改進后的算法還引入了淘汰機制,在算法的每次迭代過程中,會淘汰掉一部分表現(xiàn)較差的個體,并隨機的加入相同數(shù)量的新的個體,這樣就有效的增加了種群的多樣性,增強了算法對于解空間的擴展能力。(3)利用改進的果蠅優(yōu)化算法求解TSP問題。在求解過程中,定義了兩個算子:逆序算子和乘法算子,分別用于模擬果蠅在嗅覺搜索過程中對于解空間的拓展和在視覺定位過程中向最優(yōu)解的靠近。并且用TSPLIB中的10個基準數(shù)據(jù)集對于改進后的果蠅優(yōu)化算法進行了仿真實驗,實驗結(jié)果證明了算法的可行性和有效性。(4)利用改進后的果蠅優(yōu)化算法求解VRP問題。詳細介紹了求解過程中的種群初始化、嗅覺搜索以及視覺搜索過程,并且在兩組標準數(shù)據(jù)集上進行了仿真實驗,實驗結(jié)果證明了算法的可行性和有效性。
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：F724.6;TP18

【相似文獻】

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

1 任慶生,葉中行,曾進;進化算法的收斂速度[J];上海交通大學學報;1999年06期

2 唐浩;;蟻群算法的研究與展望[J];牡丹江教育學院學報;2009年06期

3 鄧小波;曹聰聰;龍倫海;康耀紅;;蟻群算法搜索熵研究[J];海南大學學報(自然科學版);2007年04期

4 張康;顧幸生;;全局組搜索優(yōu)化算法及其應用研究[J];青島科技大學學報(自然科學版);2012年05期

5 李東曉;蔣珉;柴干;;蟻群算法優(yōu)化及其在高速公路緊急救援中的應用[J];計算機技術與發(fā)展;2010年11期

6 _5文龍 ,黃，

本文編號：1280497