基于EP的MMAS在VRPTW中的應(yīng)用研究.pdf

1、螞蟻是群居性昆蟲，其行為的一個(gè)重要方面就是能在巢穴和食物源之間找到一條最短路的能力。當(dāng)螞蟻在巢穴和食物源之間行走時(shí)會(huì)釋放一種稱之為信息素的化學(xué)物質(zhì)。一些生物學(xué)家通過實(shí)驗(yàn)證實(shí)螞蟻喜歡用信息素的濃度來標(biāo)識(shí)路徑:路徑上信息素濃度越高該路徑被選中的概率就越大。然而，一些生物學(xué)上的研究表明這種信息素蹤跡是持久的(因螞蟻的種類和路面類型等因素不同，信息素可以保存幾小時(shí)到幾個(gè)月)，所以，在搜索行為中最短路徑上信息素蒸發(fā)率的影響就顯得不是那么重要了。即

2、使螞蟻已經(jīng)找到一條更短的路徑，它們也很難忘記信息素濃度高的那些路徑。因此，如果將螞蟻的這種行為直接轉(zhuǎn)化到計(jì)算機(jī)中來設(shè)計(jì)搜索算法，那么我們?cè)O(shè)計(jì)的算法往往會(huì)迅速陷入局部極值。
　　受螞蟻覓食行為的啟發(fā)，人們?cè)谶^去的二十年中提出了很多蟻群優(yōu)化算法(ACO)的變種，這些變種已經(jīng)成為一種新的解決組合優(yōu)化問題可行的算法。該模型的顯著特征是正反饋、分布式計(jì)算和富于建設(shè)性的貪婪啟發(fā)式搜索。目前，ACO算法的各種版本都是基于人工螞蟻的相互協(xié)作和人工

3、信息素的交流。當(dāng)人工螞蟻在圖的邊上游走時(shí)有兩種信息來指導(dǎo)螞蟻的移動(dòng):用來測(cè)量螞蟻由一點(diǎn)到另一點(diǎn)的啟發(fā)式信息和模擬真實(shí)螞蟻釋放信息素的人工信息素。
　　雖然ACO已成功應(yīng)用到很多組合優(yōu)化問題中，但是它的理論研究卻很滯后。到目前為止，只有少量的數(shù)學(xué)證明結(jié)果顯示了該算法可以在有限的時(shí)間內(nèi)獲得最優(yōu)解。然而，怎樣確定信息素蒸發(fā)率這個(gè)關(guān)鍵因素在ACO算法中的影響，怎樣證明算法運(yùn)行時(shí)間可由指數(shù)級(jí)變?yōu)槎囗?xiàng)式級(jí)，實(shí)在是一項(xiàng)復(fù)雜而艱巨的工作。

4、　　起源于二十世紀(jì)50年代后期的進(jìn)化算法，在過去的十年得到了很大關(guān)注。我們描述了進(jìn)化算法(EA)不同方法的結(jié)構(gòu)和工作原理，這些方法包括遺傳算法(GA)，遺傳規(guī)劃(GP)，進(jìn)化策略(ES)和進(jìn)化規(guī)劃(EP)，然后分析了算法的表達(dá)、變異算子、重組和選擇機(jī)制。進(jìn)化規(guī)劃是進(jìn)化算法的一個(gè)重要分支，它主要依靠選擇操作和變異算子來搜索優(yōu)化問題的解。為改進(jìn) EP的性能，人們近期提出了一系列新的變異算子。與常規(guī)進(jìn)化規(guī)劃使用Gaussian分布不同，使用基

5、于Cauchy分布的快速進(jìn)化規(guī)劃算法是一個(gè)很好的進(jìn)化規(guī)劃算法。一些研究表明，變異算子和選擇機(jī)制的相互影響在進(jìn)化規(guī)劃的性能中起著重要的作用，但這種相互影響卻難以琢磨。EP中的適應(yīng)性參數(shù)，即步長(zhǎng)控制，在進(jìn)化進(jìn)程中對(duì)目標(biāo)變量的控制也起著重要的作用。然而，這種步長(zhǎng)控制常因失控而使搜索陷入早熟。如果使用下界機(jī)制來維持步長(zhǎng)，這會(huì)限制對(duì)目標(biāo)變量進(jìn)行深層次的局部開發(fā)。所以，尋求進(jìn)化過程中探索和開發(fā)的平衡，這也是一項(xiàng)復(fù)雜而艱巨的工作。
　　有時(shí)間窗

6、車輛路徑問題(VRPTW)是一個(gè)雙目標(biāo)優(yōu)化問題，其目的首先是最小化所用路徑集合，即車輛數(shù)，然后最小化車輛走的總路程。由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值一直受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。在實(shí)踐中有時(shí)間窗車輛路徑問題的應(yīng)用包括:學(xué)校班車路線，報(bào)紙和郵件的分發(fā)，治安巡邏或維修服務(wù)，航空和鐵路時(shí)間表安排以及工業(yè)廢品收集等。
　　本文的主要工作和創(chuàng)新點(diǎn)如下:
　　1、描述了常見的各種蟻群優(yōu)化算法、進(jìn)化規(guī)劃算法和各種變異算子，如 Gaus

7、sian變異、Cauchy變異和Lévy變異。
　　2、分析了Lévy分布，它的兩個(gè)參數(shù)分別是?和?，0??，?是滿足0??的比例因2?子。參數(shù)?控制 Lévy分布的形狀，其尾部區(qū)域更依賴參數(shù)?。也就是說，參數(shù)?越小，尾部越長(zhǎng)。我們根據(jù)1.0，1.3，1.7，2.0??和使每個(gè)父代個(gè)體產(chǎn)生四個(gè)子代作為下一代好的候選解，然后在四個(gè)個(gè)體中選擇一個(gè)子代。這種基于環(huán)境來選擇子代的策略在某種意義上說是適應(yīng)性的。
　　3、提出一種新的最

8、大最小蟻群算法
　　EP和ACO的基本思想是很不同的:EP使用每一個(gè)個(gè)體的行為，其搜索策略不是期望去哪個(gè)區(qū)域，而是從局部點(diǎn)逃逸，但是ACO使用包含在種群中的預(yù)估信息，即螞蟻根據(jù)路徑上信息素的分布來產(chǎn)生新的解。本文的工作是將這兩種優(yōu)化方法結(jié)合起來會(huì)產(chǎn)生怎樣的結(jié)果。
　　基于上述觀點(diǎn)，本文提出了基于MMAS框架的混合算法，通過利用EP和ACO的優(yōu)點(diǎn)來解決 VRPTW問題。我們用兩個(gè)人工蟻群設(shè)計(jì)算法HMMAS-VRPTW來優(yōu)化 V

9、RPTW:第一個(gè)蟻群最小化車輛數(shù)目，第二個(gè)蟻群最小化旅行的距離。兩個(gè)蟻群通過信息素的更新來交換信息，從而相互協(xié)作。然后，使用Lévy隨機(jī)分布來提高新框架的性能，Lévy隨機(jī)分布可以產(chǎn)生介于Gaussian和Cauchy變異間的任意隨機(jī)數(shù)，Gaussian變異在全局最優(yōu)解的臨域能找到一個(gè)解更好的解，而 Cauchy變異在當(dāng)前搜索點(diǎn)和全局最優(yōu)點(diǎn)相對(duì)較遠(yuǎn)時(shí)會(huì)有較好的性能。通過分析有時(shí)間窗車輛路徑問題和旅行商問題的區(qū)別，改進(jìn)最大最小蟻群算法中狀