本文關(guān)鍵詞：基于淘汰機(jī)制的果蠅優(yōu)化算法求解車(chē)輛路徑問(wèn)題

  更多相關(guān)文章： 車(chē)輛路徑問(wèn)題 群智能 果蠅優(yōu)化算法 旅行商問(wèn)題 淘汰機(jī)制 算子

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

【相似文獻(xiàn)】

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

1 任慶生,葉中行,曾進(jìn);進(jìn)化算法的收斂速度[J];上海交通大學(xué)學(xué)報(bào);1999年06期

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

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

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

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

6 _5文龍 ,黃，

本文編號(hào)：1280497