車輛路徑問(wèn)題的混合遺傳粒子群算法

-.z.車輛路徑問(wèn)題的混合遺傳—粒子群算法——HFUT論文翻譯作業(yè)摘要：通常的遺傳算法，具體的解并不在他們的生命周期內(nèi)進(jìn)化：它們被創(chuàng)立，評(píng)估，可能被選作為新解決方案的父代，然后被銷毀。然而對(duì)Memetic算法和基因局部搜索的研究說(shuō)明，如果解能夠被允許在其生命周期內(nèi)進(jìn)展演化，性能可能會(huì)提高。我們建議，解的提高可以通過(guò)對(duì)父代解的知識(shí)存儲(chǔ)來(lái)獲取幫助，以有效地讓父代教他們的后代如何改善適應(yīng)性。本文中，具體解通過(guò)應(yīng)用粒子群算法來(lái)進(jìn)化，即每個(gè)解都要按照PSO的根本原則進(jìn)展物理運(yùn)動(dòng)，直到被要求去作為一個(gè)父代。因此，每個(gè)父代的知識(shí)，特別是一個(gè)非常適合父代，就有可能被轉(zhuǎn)移到其后代以及整個(gè)群體的子代中去，通過(guò)這種方式提出的算法有可能更有效的搜索解空間。這種想法被應(yīng)用到一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，即車輛路徑問(wèn)題，當(dāng)應(yīng)用于兩個(gè)經(jīng)典的基準(zhǔn)實(shí)例集合時(shí)具有很好的效果。1.簡(jiǎn)介在過(guò)去的十幾年中，由于先進(jìn)的信息系統(tǒng)設(shè)計(jì)智能范例利用，自然啟發(fā)智力變得越來(lái)越流行。其中最流行的自然啟發(fā)方法是對(duì)動(dòng)物和微生物的團(tuán)隊(duì)行為的表示，如群智能〔鳥(niǎo)群或魚(yú)群?jiǎn)l(fā)粒子群優(yōu)化〕、人工免疫系統(tǒng)、蜂群的性能優(yōu)化、蟻群等等。但自然啟發(fā)方法最流行的是遺傳算法，它的應(yīng)用十分廣泛，在遺傳算法和更普遍的進(jìn)化計(jì)算的背景下，也實(shí)現(xiàn)了許多新的思想。通常的遺傳算法，我們有一些離散的階段，即群的初始化，父代的選擇，穿插算子，變異算子和每一代的更換。但兩代之間又發(fā)生什么呢？如果我們想有一個(gè)完整的進(jìn)化算法，我們將要觀察每個(gè)個(gè)體在其生命周期內(nèi)的行為。在父代試圖幫助他們的子女來(lái)學(xué)習(xí)和開(kāi)展，而使其變得更具有競(jìng)爭(zhēng)性，并有更多的可能性生存，來(lái)成為下一代的父代。有許多不同的方法可以用來(lái)完成一個(gè)進(jìn)化算法，一種方法是獨(dú)立的觀察每個(gè)個(gè)體，個(gè)體間無(wú)任何交流與影響。在遺傳算法的情況下，其實(shí)現(xiàn)是使用單一或更復(fù)雜的局部搜索策略。另一種方法是讓個(gè)體之間有一個(gè)相互作用。在本文中，這種互動(dòng)利用粒子群優(yōu)化算法來(lái)實(shí)現(xiàn)。在每一代中，所有的個(gè)體〔父代和子女〕被視為一個(gè)單一的群體，他們通過(guò)向群的最優(yōu)局部運(yùn)動(dòng)來(lái)努力提高自己的解決方案〔即后代學(xué)習(xí)他們的父代〕。因此，在本文中我們著重于每個(gè)個(gè)體如何利用粒子群來(lái)進(jìn)化。在每次的粒子群優(yōu)化階段完畢時(shí)，整個(gè)群適者生存，并轉(zhuǎn)移到下一階段的遺傳算法，即遺傳算法的父代選擇階段。在算法的進(jìn)化局部應(yīng)用PSO算法的優(yōu)勢(shì)是，與其他超啟發(fā)式算法相比，對(duì)于群體中的每個(gè)個(gè)體只有兩種變量在迭代中需要計(jì)算，即位置和速度。經(jīng)常用Memetic算法〔帶有局部搜索階段的遺傳算法〕來(lái)代替典型的遺傳算法使用的原因是，純粹的遺傳算法很難有效的探索解空間。全局優(yōu)化算法與局部?jī)?yōu)化算法的結(jié)合往往能夠提高算法的性能。在本文中，我們用了一個(gè)全局搜索算法即PSO代替局部搜索算法來(lái)分別改進(jìn)每個(gè)個(gè)體。因此每個(gè)個(gè)體并不通過(guò)自身來(lái)改善解，而是利用整個(gè)群體的解的知識(shí)。我們的另一個(gè)目標(biāo)是在較短的計(jì)算時(shí)間內(nèi)得到進(jìn)可能好的結(jié)果。這個(gè)目標(biāo)使我們使用兩個(gè)不同的程序，一是加速技術(shù)〔擴(kuò)張鄰域搜索-ENS〕，另一個(gè)用于產(chǎn)生盡可能好的初始解〔MPNS-GRASP〕。因此，遺傳算法和一個(gè)非?？斓木植克阉鞑呗缘腜SO算法相結(jié)合，如擴(kuò)大鄰域搜索策略〔[Marinakis等，2005]和[Marinakis等，2005年〕，將產(chǎn)生非常快速和有效的算法，并將減少解決大規(guī)模的車輛路徑算法的計(jì)算時(shí)間，以及更多的困難的組合優(yōu)化問(wèn)題。本文下面的組織構(gòu)造為：下一節(jié)將具體描述車輛路徑問(wèn)題，第三局部中，算法hybridgenetic–PSO–GRASP–ENS(HybGENPSO)被提出并詳細(xì)描述。實(shí)驗(yàn)結(jié)果將在第四局部展示和分析，最后一局部得出結(jié)論以及對(duì)未來(lái)的展望。2.車輛路徑問(wèn)題VRP和CVRP問(wèn)題經(jīng)常被描述為，車輛基于中心倉(cāng)庫(kù)，要求到達(dá)地理位置不同客戶以滿足客戶的需求。令G=(V,E)表示一個(gè)圖，其中V={i1,i2,…in}表示定點(diǎn)集合，(i1代表倉(cāng)庫(kù)客戶位置表示為i2,…,in)，E={(il,im):il,imV}表示邊的集合。每個(gè)客戶必須被分配一個(gè)確切的車輛，每輛車分配的載量不能超過(guò)其容量〔Qk〕，如果每輛車都是同質(zhì)的則容量相等記為Q。需求ql以及效勞時(shí)間stl分配給每個(gè)客戶節(jié)點(diǎn)il。倉(cāng)庫(kù)節(jié)點(diǎn)的需求量q1和效勞時(shí)間st1設(shè)置為0，il和im之間的運(yùn)輸費(fèi)用記為Clm。Tk表示車輛k被允許的路線上的最大時(shí)間。該問(wèn)題是建立一個(gè)低本錢(qián)的，對(duì)每一輛車都可行的路線。一條路線是一個(gè)地點(diǎn)的序列，車輛必須根據(jù)它提供的效勞來(lái)訪問(wèn)路線，如果邊(il,im)被車輛k經(jīng)過(guò)則置變量為1，否則為0。車輛必須在倉(cāng)庫(kù)處完畢其行程。下面我們用數(shù)學(xué)公式來(lái)描述VRP問(wèn)題。目標(biāo)函數(shù)〔1〕指出，總距離要盡量減少。等式〔2〕和〔3〕確保每個(gè)有需求的節(jié)點(diǎn)會(huì)得到一個(gè)車輛的效勞。〔4〕表示路線的連續(xù)性，即一輛車進(jìn)入需求節(jié)點(diǎn)后必須從該節(jié)點(diǎn)出來(lái)。公式〔5〕表示車輛的容量約束，式子〔6〕表示總共的時(shí)間約束。式子〔7〕和〔8〕保證了車輛的供應(yīng)能力沒(méi)被超出。VRP問(wèn)題首先由丹捷格和拉姆瑟〔1959〕提出。由于這是一個(gè)NP-難問(wèn)題，提出了大批近似技術(shù)。這些技術(shù)大體可分為兩大類：一是經(jīng)典啟發(fā)式算法，主要開(kāi)展于1960年至1990年，以及最近15年才開(kāi)展的超啟發(fā)式算法，該算法可以根據(jù)使用的策略不同來(lái)分類。禁忌搜索策略是比較常用的技術(shù)，很多研究人員提出了很多有效的禁忌搜索算法的變種。一些有趣的高效的算法也被提出，基于自適應(yīng)記憶的概念，將高質(zhì)量的VRP解存在里面，并在解得過(guò)程中用更好的解來(lái)代替它。模擬退火，貪婪隨機(jī)自適應(yīng)搜索過(guò)程和閾值接收算法也有效地應(yīng)用于VRP求解。在過(guò)去10多年中，自然啟發(fā)超啟發(fā)式算法已用于VRP問(wèn)題的求解過(guò)程。最常用的自然啟發(fā)算法是遺傳算法，蟻群優(yōu)化，蜜蜂交配優(yōu)化，以及其他進(jìn)化技術(shù)。讀者可以很容易從現(xiàn)存的論文書(shū)籍中找到對(duì)這些算法的詳細(xì)描述。3.應(yīng)用于VRP問(wèn)題一種混合算法〔Hybridgenetic–PSO–GRASP–ENS〕3.1Hybridgenetic–PSO–GRASP–ENS〔HybGENPSO〕的整體描述該算法結(jié)合了遺傳算法，MPNS-GRASP算法，鄰域擴(kuò)張搜索策略和粒子群優(yōu)化算法。接下來(lái)，將列出算法的提綱。初始化〔1〕創(chuàng)立初始種群的P個(gè)個(gè)體，使用的多階段鄰域搜索-GRASP〔MPNS-GRASP〕?！?〕評(píng)價(jià)每個(gè)個(gè)體的適應(yīng)性?！?〕運(yùn)用粒子群優(yōu)化策略改善每個(gè)個(gè)體的適應(yīng)性。主算法〔1〕設(shè)置generations為0.〔2〕如果不滿足終止條件，繼續(xù)循環(huán)2.1如果父代仍在選擇和交配，繼續(xù)循環(huán)通過(guò)輪盤(pán)賭的方式從群體中選擇兩個(gè)作為父代對(duì)兩個(gè)父代進(jìn)展穿插操作，首先將兩個(gè)父代的共同特征克隆到后代，然后使用ENS的算法完成后代。通過(guò)突變操作〔擴(kuò)張鄰域搜索〕改進(jìn)后代，并將其結(jié)果插入到群體中。2.2ENDDO2.3通過(guò)粒子群優(yōu)化策略，提高新群體中每個(gè)個(gè)體〔父代和后代〕的適應(yīng)性。2.4根據(jù)適應(yīng)性函數(shù)對(duì)子代和父代進(jìn)展排序，然后選擇與初始群體數(shù)目相等的個(gè)體作為新群體。2.5代的數(shù)目加一?！?〕ENDDO〔4〕返回最好的個(gè)體3.2路徑表示在為*一問(wèn)題設(shè)計(jì)遺傳算法時(shí)，第一步就是設(shè)計(jì)適宜的候選解的表示。例如Vrp情況下，每個(gè)個(gè)體〔旅行〕通過(guò)旅行的路徑來(lái)表示，即通過(guò)一個(gè)特殊的點(diǎn)序列。有了這種表示，有2n種方式來(lái)表示一樣的旅行，其取決于哪個(gè)節(jié)點(diǎn)被放置在位置1和旅行走向哪個(gè)方向，其中n是節(jié)點(diǎn)數(shù)。該算法，與1號(hào)節(jié)點(diǎn)固定在了每一個(gè)人，總是抑制代表性位置1，因此，同一旅游多種編碼的障礙，抑制了很多冗余的解決方案的代表性。在提出的算法中，表示每個(gè)個(gè)體時(shí)，1號(hào)節(jié)點(diǎn)就被固定于位置1，這樣就可以抑制一樣旅行有多個(gè)編碼的障礙，抑制解表示的冗余。3.3群初始化-MPNS-GRASP通常的遺傳算法，隨機(jī)產(chǎn)生初始化群，其中不能確保包含好的候選解，為防止這種情況，一種貪心隨機(jī)自適應(yīng)搜索算法的修改版本，多階段鄰域搜索-GRASP被用于初始化群體。GRASP是一種迭代的兩階段搜索算法。每次迭代由兩個(gè)階段構(gòu)成，構(gòu)建階段和局部搜索階段，在構(gòu)建階段中，用一個(gè)隨機(jī)貪心函數(shù)來(lái)構(gòu)建一個(gè)初始解。該隨機(jī)技術(shù)每次迭代中都產(chǎn)生一個(gè)可行的解，該解通過(guò)經(jīng)過(guò)局部搜索階段來(lái)提高。最后的結(jié)果就是所有迭代過(guò)程中最優(yōu)的解。構(gòu)建過(guò)程可被描述為一個(gè)逐步的過(guò)程，它一次增加一個(gè)元素到一個(gè)非完整解。下一個(gè)要被參加的元素通過(guò)排序所有元素來(lái)選擇，根據(jù)貪心函數(shù)，將一個(gè)最好的元素放于有限候選列表RCL中，然后從表中隨機(jī)選擇。這個(gè)RCL由可能最好的D元素構(gòu)成。最后RCL每次迭代都通過(guò)用不屬于RCL中的邊替換掉包含在巡回中的邊來(lái)調(diào)整，命名為第〔D+m〕條邊，其中m表示目前迭代的次數(shù)。用于解決VRP問(wèn)題的貪心算法是一個(gè)簡(jiǎn)單的過(guò)程。在第二階段，局部搜索從這些點(diǎn)初始化，最終結(jié)果是整個(gè)搜索過(guò)程的最優(yōu)解。MPNS-GRASP介紹了應(yīng)用多目標(biāo)函數(shù)來(lái)替代經(jīng)典方法中的簡(jiǎn)單貪心函數(shù)的靈活性，而且組合貪心算法也是可行的。算法開(kāi)場(chǎng)于一個(gè)貪心算法，如果結(jié)果沒(méi)有改善，則利用一個(gè)多目標(biāo)貪心函數(shù)來(lái)替代?；谶@些貪心函數(shù)忽略VRP問(wèn)題的邊約束，可解決一個(gè)TSP問(wèn)題。因此可以通過(guò)增加邊約束來(lái)講一個(gè)TSP問(wèn)題轉(zhuǎn)化為VRP問(wèn)題。更準(zhǔn)確一點(diǎn)，第一輛車從代表倉(cāng)庫(kù)的節(jié)點(diǎn)出發(fā)，并基于TSP的解來(lái)移到下一個(gè)節(jié)點(diǎn)，檢查車輛的容量或最大路線長(zhǎng)度是否滿足約束。不滿足任一約束則車輛返回倉(cāng)庫(kù)節(jié)點(diǎn)，開(kāi)場(chǎng)一個(gè)新的路線。經(jīng)典算法的第二階段，簡(jiǎn)單局部搜索局受限于獲得好解的時(shí)機(jī)，因此MPNS-GRASP經(jīng)常用擴(kuò)張鄰域搜索來(lái)代替，這是一種很靈活的局部搜索策略。3.4適應(yīng)度函數(shù)的計(jì)算在VRP中，每個(gè)個(gè)體初始適應(yīng)度與每個(gè)旅行的路線長(zhǎng)度有關(guān)。每個(gè)個(gè)體S的適應(yīng)值由下式計(jì)算：Fitnesss=Jma*-Js+1其中Jma*是群體中最大花費(fèi)的個(gè)體的目標(biāo)函數(shù)值，Js是當(dāng)前個(gè)體的函數(shù)值。注意，選擇個(gè)體去交配的可能性依賴于其適應(yīng)值，并且花費(fèi)最高的個(gè)體的適應(yīng)值為0，它永遠(yuǎn)不會(huì)被選擇，因此，加1來(lái)保證最壞的解不會(huì)完全剔除。3.5選擇概率選擇機(jī)制用于選擇父代的染色體，并構(gòu)建雜交池。在以后的進(jìn)化中更適應(yīng)的染色體有較高的幾率存活。本文中，我們使用簡(jiǎn)單常用的輪盤(pán)賭方式來(lái)作為選擇機(jī)制。3.6穿插算子我們提出一個(gè)穿插操作來(lái)首先標(biāo)示父代個(gè)體的共同特征，然后將其復(fù)制到后代。穿插操作是一種自適應(yīng)記憶過(guò)程。開(kāi)場(chǎng)時(shí)，自適應(yīng)記憶被作為解決VRP問(wèn)題禁忌搜索超啟發(fā)算法的一局部提出來(lái)的。該過(guò)程存儲(chǔ)了好解的特征。每發(fā)現(xiàn)一個(gè)新的好解，自適應(yīng)記憶就會(huì)更新。對(duì)于我們來(lái)說(shuō)，第一代的自適應(yīng)記憶為空。為了向其中參加一個(gè)或局部解，有幾種更可能行：〔1〕參加其中的候選解是前面最好的解，但它的花費(fèi)至少比目前最好的解壞10%?！?〕參加其中的候選解是群體中的一員，其花費(fèi)同樣至少比最優(yōu)解壞10%?！?〕一條路徑與最優(yōu)解及很多個(gè)體的一樣詳加分析，在穿插操作中，點(diǎn)是由自適應(yīng)記憶各個(gè)個(gè)體以及最優(yōu)解中隨機(jī)選擇的。因此首先選擇兩個(gè)穿插算子〔Cr1，Cr2〕來(lái)控制用于自適應(yīng)記憶、個(gè)體和最優(yōu)解的局部參數(shù)。如果解之間有一樣的局部則一樣的局部遺傳與下一代，否則Cr1、Cr2的值與一個(gè)隨機(jī)數(shù)產(chǎn)生器的輸出比較，randi(0,1)。如果隨機(jī)數(shù)不大與Cr1，則相應(yīng)的值從最好的解中遺傳，假設(shè)介于兩者之間，遺傳的值為自適應(yīng)記憶中的隨機(jī)的一個(gè)解，否則從其他個(gè)體的解中隨機(jī)選擇。因此如果子代解表示為Oi(t)，最優(yōu)個(gè)體解bii(t)，自適應(yīng)記憶解adi(t)，一個(gè)其他個(gè)體的解pi(t)：每次迭代自適應(yīng)記憶基于最優(yōu)解來(lái)更新，穿插操作后，計(jì)算子代的適應(yīng)度函數(shù)，如果比父代好，變量被選擇為下一代，否則父代至少多存活一代。3.7擴(kuò)張鄰域搜索本文用的局部搜索方法為擴(kuò)張鄰域搜索，ENS是一種超啟發(fā)式算法，可以用來(lái)解決很多組合優(yōu)化問(wèn)題。該算法的主要特征：〔a〕運(yùn)用圈限制局部搜索移動(dòng)策略?！瞓〕有在不同局部搜索策略間變動(dòng)的能力?！瞔〕運(yùn)用擴(kuò)張策略。這些特征將在下面祥加介紹。圈受限局部搜索移動(dòng)〔CRLSM〕策略中，計(jì)算時(shí)間比其他啟發(fā)算法或超啟發(fā)算法要少，因?yàn)樗胁荒芨纳平獾眠叾荚谒阉鬟^(guò)程中剔除了。它將搜索空間約束到候選刪除邊的周圍。在2-opt局部搜索算法中，只有一種可能性來(lái)減少解得花費(fèi)。即至少一條邊花費(fèi)比兩邊中的一個(gè)少，并且另一邊的花費(fèi)比兩個(gè)舊邊的總花費(fèi)少。因此CRLSM策略中，對(duì)所有的局部搜索策略，圈在候選刪除邊的終節(jié)點(diǎn)周圍產(chǎn)生，只有圈內(nèi)的節(jié)點(diǎn)才被用于尋找更好解的過(guò)程中。為了減少更多的計(jì)算時(shí)間，并且在候選刪除邊終結(jié)點(diǎn)附近很可能找到一個(gè)更好的解，我們開(kāi)場(chǎng)不用最大的可行圈，而是用較小的圈來(lái)尋找更優(yōu)解。例如，在2-opt算法中，如果候選刪除邊的長(zhǎng)度為A，則圈初始半徑為A/2，然后，局部搜索策略按如下描述應(yīng)用，并且如果解在圈內(nèi)無(wú)法改善，圈按a%擴(kuò)展后，該算法繼續(xù)。直到圈到達(dá)最大可能直徑，A+B，其中B是另一個(gè)候選刪除邊的長(zhǎng)度。ENS算法有能力在不同局部搜索策略間變動(dòng)。Gar?nkel和Nemhauser首先提出一種非常簡(jiǎn)單的方式來(lái)使用一個(gè)更大的鄰域。通常來(lái)說(shuō)，局部?jī)?yōu)化發(fā)現(xiàn)中使用一個(gè)鄰域，然后一個(gè)更大的鄰域在試圖掙脫局部?jī)?yōu)化時(shí)使用。有人提出一個(gè)系統(tǒng)的方法來(lái)在不同的鄰域間變換，叫做變種鄰域搜索。在擴(kuò)張鄰域搜索中一些局部搜索策略被應(yīng)用于圈內(nèi)。工作過(guò)程如下：首先當(dāng)前解的一條邊被選中〔例如最差長(zhǎng)度的邊〕并且應(yīng)用第一種局部搜索策略。如果用這種策略沒(méi)有發(fā)現(xiàn)一個(gè)更好的解，對(duì)同一條邊就會(huì)選用另一種局部搜索策略。該過(guò)程一直持續(xù)到有一個(gè)更好的解被找到，或者所有的局部搜索策略都已經(jīng)用到了。第一種情況中，解得到更新，選出一個(gè)新的邊，然后開(kāi)場(chǎng)新一輪的擴(kuò)張鄰域搜索策略，第二種情況中，將圈擴(kuò)大后再使用局部搜索策略，直到找到一個(gè)更好的解或者圈已經(jīng)到達(dá)最大可能直徑。如果已經(jīng)到達(dá)最大可能直徑，則選擇一個(gè)新的候選刪除邊。用于VRP的擴(kuò)張鄰域搜索的局部搜索策略分為單一路線和多重路線的局部搜索策略。屬于第一類的局部搜索算法是解決TSP的常用算法，2-opt和3-opt步操作。在單一路線交換中所有的路線在算法的初始階段生成。單一路線交換的局部搜索策略試圖提高路由決策。多路由交換試圖提高委派決策。這樣自然會(huì)增加算法的復(fù)雜性，但能夠更好的改善解。多重路由交互策略允許上坡下坡動(dòng)作，單路線交互局部搜索策略只允許下坡動(dòng)作。所用的多重路由交換局部搜索策略是1–0重新部署,2–0重新部署,1–1交換,2–2交換。3.8群演化-粒子群優(yōu)化粒子群優(yōu)化〔PSO〕是一種基于群的群體智能算法。它最初是作為社會(huì)有機(jī)體的社會(huì)行為由肯尼迪和埃伯哈特提出的。利用粒子群中個(gè)體的物理運(yùn)動(dòng)，具有靈活的平衡機(jī)制，以提高全局適應(yīng)性和局部探測(cè)能力。由于其易于實(shí)現(xiàn)和廉價(jià)的計(jì)算，編碼性能的一致性和簡(jiǎn)單性，粒子群已被證明是一個(gè)為在連續(xù)空間優(yōu)化問(wèn)題的有效、有競(jìng)爭(zhēng)力的算法。PSO算法的大多數(shù)應(yīng)用程序都集中于連續(xù)空間的優(yōu)化，同時(shí)，最近對(duì)于離散優(yōu)化問(wèn)題也有所研究。自推出以來(lái)，PSO算法已得到迅速普及，通過(guò)與其他超啟發(fā)式演算法比較，被證明是有競(jìng)爭(zhēng)力和有效的優(yōu)化算法。粒子群優(yōu)化算法首先隨機(jī)初始化粒子群。在問(wèn)題空間sjd〔j=1,2，..N；N為人口數(shù)目〕中每個(gè)個(gè)體〔叫做粒子〕用一個(gè)d維的變量表示，并且通過(guò)預(yù)定義的適應(yīng)度函數(shù)來(lái)進(jìn)展評(píng)價(jià)。因此，每個(gè)粒子隨機(jī)的分布在d維空間中作為一個(gè)候選解。第j個(gè)粒子的速度vjd定義為其位置的變化。每個(gè)粒子的飛行方向，通過(guò)個(gè)體和整體的飛行經(jīng)歷來(lái)動(dòng)態(tài)交互確定。該算法通過(guò)個(gè)體最優(yōu)解和全局最優(yōu)解完成優(yōu)化。每個(gè)粒子的運(yùn)動(dòng)軌跡根據(jù)自己先前的最好位置和全局的最好位置來(lái)調(diào)整，分別記為pjd和pgd，每次迭代中群通過(guò)下式來(lái)更新。vjd(t+1)=vjd(t)+c1rand1(pjd-sjd(t))+c2rand2(Pgd-sjd(t))(13)sjd(t+1)=sjd(t)+vjd(t+1)(14)其中t表示迭代次數(shù)，c1和c2加速系數(shù)，rand1和rand2是【0,1】之間產(chǎn)生的隨機(jī)數(shù)。加速系數(shù)c1和c2決定了粒子一次迭代移動(dòng)的距離。低值允許粒子在被拽回來(lái)之前能夠在遠(yuǎn)離目標(biāo)區(qū)域的地方漫游，反之則要求迅速移向過(guò)去最好位置或目標(biāo)位置。典型的值為2.0，雖然分配不同的值給加速系數(shù)有時(shí)會(huì)提高性能。根底PSO算法及其變種已經(jīng)成功運(yùn)用于連續(xù)優(yōu)化函數(shù)。為了將應(yīng)用擴(kuò)展到離散空間，肯尼迪和埃伯哈特提出了離散二進(jìn)制版本的PSO，其中粒子群的狀態(tài)空間每個(gè)維局限于1和0，vjd表示速度變?yōu)?的概率。粒子的軌跡定義為可能性的變化，vjd度量目前個(gè)體置為1的可能性。速度越大，越可能選擇1，越低越可能選擇0。應(yīng)用一個(gè)sig函數(shù)將速度從實(shí)數(shù)空間轉(zhuǎn)化到概率空間。(15)在二進(jìn)制版本的pso中，粒子的速度和位置根據(jù)下式更新：(16)(17)其中sjd屬于{0，1}，vjd表示速度，sig(vjd)根據(jù)15式計(jì)算，rand3是0到1間隨機(jī)分配的一個(gè)數(shù)。在根本的PSO，一個(gè)參數(shù)Uma*用來(lái)限制vjd，這樣sig(vjd)就不會(huì)過(guò)于靠近0或1。這種機(jī)制可以保證二進(jìn)制數(shù)積極地在0和1之間轉(zhuǎn)換，Uma*經(jīng)常設(shè)置為4。本文提出的算法是基于標(biāo)準(zhǔn)PSO的，名為帶慣性權(quán)重的根本PSO，其中w為慣性權(quán)重。慣性權(quán)重用以控制先前的速度對(duì)目前速度的影響，通常作為一個(gè)控制平衡的參數(shù)。粒子根據(jù)其歷史最優(yōu)和其他粒子的最優(yōu)信息來(lái)調(diào)整其運(yùn)動(dòng)軌跡。慣性權(quán)重w也被用來(lái)控制PSO的收斂行為。為了隨著迭代而改變權(quán)重w，以允許算法探索細(xì)節(jié)區(qū)域，權(quán)重w可按下式更新：(18)其中Wma*，Wmin是慣性權(quán)重可以取的最大最小值，t是目前迭代的次數(shù)，iterma*是最大的迭代的次數(shù)。其中一個(gè)要處理的主要問(wèn)題是如何將粒子從目前的解，移動(dòng)到全局最優(yōu)〔整個(gè)群的最優(yōu)解〕或局部最正確〔每個(gè)粒子的最正確解〕。通常在一個(gè)離散粒子群中使用〔17〕式?；旌线z傳粒子群算法，使用路徑重新鏈接策略代替這個(gè)公式。路徑重新連接是加強(qiáng)戰(zhàn)略，作為一個(gè)在優(yōu)秀解之間探索軌跡的方式使用。因此，每個(gè)粒子當(dāng)前解使用這一戰(zhàn)略與全球或局部最優(yōu)解結(jié)合。這種方法通過(guò)連接高品質(zhì)解來(lái)探索軌跡，并生成新的解。從一個(gè)初始解出發(fā)，在鄰域空間生成路徑得到另一個(gè)解，稱為目標(biāo)解。初始解和目標(biāo)解的角色可以交換。首先，選兩個(gè)解最差的為初始解，另一個(gè)為目標(biāo)解。其次，角色發(fā)生變化。有兩個(gè)途徑同時(shí)探索的可能性。以粒子群優(yōu)化粒子可以繼續(xù)自己的方式，或返回到其以前的最正確解，或靠近全局最優(yōu)解〔到在群最好的粒子〕。因此，在混合遺傳粒子群中，粒子無(wú)論跟隨以往的最優(yōu)解或全局最優(yōu)解的路徑，當(dāng)當(dāng)前解作為初始解，最優(yōu)解作為目標(biāo)解時(shí)，應(yīng)用了路徑重新連接的策略。兩個(gè)解之間的軌跡探測(cè)通過(guò)簡(jiǎn)單的交換初始解得兩個(gè)節(jié)點(diǎn)，直到與目標(biāo)解一樣。如果一些重新連接中產(chǎn)生一個(gè)新的最優(yōu)解，無(wú)論是粒子或全體群，則目前最優(yōu)解被代替，算法繼續(xù)。3.9群體替換和進(jìn)程終止就如上一節(jié)提到的，所有粒子在穿插變異后，并通過(guò)PSO算法來(lái)演化。然后更適應(yīng)環(huán)境的個(gè)體將有更大的生存和繁殖時(shí)機(jī)，否則就會(huì)被淘汰。開(kāi)場(chǎng)所有個(gè)體按照適應(yīng)值排序，然后選p個(gè)最好的個(gè)體替代舊的群體。當(dāng)?shù)竭_(dá)預(yù)定的最大迭代次數(shù)或收斂時(shí)，算法中止。4．計(jì)算結(jié)果整個(gè)算法用Fortran90語(yǔ)言執(zhí)行，并使用處理器為1.86GHz的運(yùn)行SUSELinu*9.1的雷希f95編譯器來(lái)編譯。該算法的參數(shù)選擇經(jīng)過(guò)充分的測(cè)試。對(duì)一組不同值的數(shù)據(jù)進(jìn)展了測(cè)試，并選擇那些解質(zhì)量較好和計(jì)算所需的時(shí)間較少的計(jì)算結(jié)果。因此，所選的參數(shù)見(jiàn)表1。最終參數(shù)選定后，根據(jù)不同的參數(shù)運(yùn)行50次。該算法在兩類基準(zhǔn)問(wèn)題上進(jìn)展了測(cè)試。赫里斯托菲等人提出的14個(gè)基準(zhǔn)問(wèn)題，金等人提出20個(gè)大型車輛路由問(wèn)題。第一組的每個(gè)實(shí)例包含51到200個(gè)節(jié)點(diǎn)，包括倉(cāng)庫(kù)節(jié)點(diǎn)。每個(gè)問(wèn)題包括能力限制的問(wèn)題，同時(shí)問(wèn)題6-10、13、14有最大路線約束以及非零效勞次數(shù)。第二組的實(shí)例包含200到483個(gè)節(jié)點(diǎn)，每個(gè)問(wèn)題實(shí)例包括容量約束，同時(shí)前8個(gè)有最長(zhǎng)路線約束，以及0效勞次數(shù)。產(chǎn)生的解得質(zhì)量為，其中cHybGENPSO表示由HybGENPSO算法找到的解的本錢(qián)，cBKS表示知道的最優(yōu)解的本錢(qián)。在表2和表3的第一列表示每個(gè)實(shí)例節(jié)點(diǎn)數(shù)，而在第二，第三和第四列是重要的特征，即車輛最大容量、最大長(zhǎng)度以及每輛車的效勞時(shí)間。后面的6個(gè)欄目，對(duì)算法〔第5欄〕的50次運(yùn)行的平均結(jié)果，算法的最好結(jié)果〔第6欄〕，最好解〔BKS-第7欄〕，平均運(yùn)行質(zhì)量〔ωav-8欄〕最好的質(zhì)量〔ω-9欄〕和最好運(yùn)行時(shí)間〔列10〕。從表2可以看出，該算法，在第一組的情況下的14個(gè)中10個(gè)已到達(dá)最優(yōu)解。至于其他四個(gè)實(shí)例的最正確解，運(yùn)行質(zhì)量介于0.07％和0.23％，而14個(gè)實(shí)例的平均質(zhì)量是0.046％。對(duì)于20個(gè)大型路由問(wèn)題〔表3〕，該算法的車輛已經(jīng)找到了其中一個(gè)最知名的解，為其余的質(zhì)量介于0.26％和1.04％，而為20情況下的平均運(yùn)行質(zhì)量是0.60％。此外，在這些表中也需要計(jì)算所需的時(shí)間。所需的CPU時(shí)間是很少的，只有第一組的兩個(gè)實(shí)例5和10有點(diǎn)增加，但仍然是非常有效的。在第二組的情況下，問(wèn)題更復(fù)雜，因此，計(jì)算時(shí)間有所增加，但所有的實(shí)例仍低于10分鐘。這些結(jié)果說(shuō)明了該算法的有效性。在9個(gè)在所有50個(gè)運(yùn)行實(shí)例都設(shè)置算法找到了最有效的解。在大量實(shí)例情況下算法只在一個(gè)或兩個(gè)上沒(méi)有找到最正確解。然而，即使是最好的解并非在所有運(yùn)行中發(fā)現(xiàn)，但找到的解與最正確解時(shí)非常接近的。應(yīng)當(dāng)指出，我們想提出一個(gè)非?？焖俸陀行У乃惴?，因而，參數(shù)的選擇要在得到盡可能好的結(jié)果下，結(jié)合考慮收斂速度。這個(gè)問(wèn)題有時(shí)會(huì)導(dǎo)致該算法找不到最正確解。如果我們?cè)黾恿肆Ｗ訑?shù)和迭代數(shù)提高了算法的解，但隨后會(huì)發(fā)現(xiàn)找到這些解需要更多的計(jì)算時(shí)間。為了證明HybGENPSO的奉獻(xiàn)，我們分別執(zhí)行主要階段并與HybGENPSO的結(jié)果進(jìn)展比較。有兩個(gè)非進(jìn)化算法，擴(kuò)展鄰域搜索〔ENS〕〔表4和表5的第1列和第2列〕和多階段鄰域搜索-GRASP(MPNS-GRASP)〔表4和表5的3、4列〕和3個(gè)進(jìn)化算法，混合遺傳巨猿-ENS的〔HybGEN〕〔第5和第6列〕，遺傳--粒子群優(yōu)化-算法〔第7、8列〕和GEN-PSO-ENS算法〔第9、10列〕。HybGEN和HybGENPSO之間的唯一的區(qū)別是在于群是否通過(guò)粒子群優(yōu)化算法實(shí)現(xiàn)進(jìn)化，而GEN-PSO和HybGENPSO不同的是，在GEN-PSO中MPNS-GRASP和ENS根本沒(méi)用到。最后，GEN-PSO-ENS和HybGENPSO不同的是，GEN-PSO-ENS中初始化階段的MPNS-GRASP根本沒(méi)有使用。在所有的實(shí)現(xiàn)中，這些參數(shù)都以這樣一種方式選擇，即在所有算法作出一樣數(shù)目的評(píng)估函數(shù)。該參數(shù)不影響評(píng)價(jià)函數(shù)的數(shù)目，如RCL等。設(shè)置參數(shù)和局部搜索策略與HybGENPSO一樣。為了使HybGEN和HybGENPSO的評(píng)價(jià)函數(shù)肅穆一樣，我們?cè)贖ybGEN中增加了個(gè)體和迭代數(shù)目。在表4和表5給出了本錢(qián)以及解的質(zhì)量。因?yàn)樗梢詮谋?和表5觀察到，使用該算法使得結(jié)果改善。更確切地說(shuō)，在對(duì)從ENS的算法提出方法的結(jié)果質(zhì)量的改善，對(duì)于赫里斯托菲基準(zhǔn)實(shí)例介于0.00％和1.68％之間，平均為0.524％；金基準(zhǔn)的情況改善0.38％和3.32％之間，平均等于1.35％在對(duì)從MPNS–GRASP提出方法的結(jié)果質(zhì)量的改善，對(duì)于赫里斯托菲情況介于0.00％和