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

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

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

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

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

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

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

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

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

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