車輛路徑問題的混合遺傳粒子群算法

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