軍用補(bǔ)給艦船路徑規(guī)劃改進(jìn)混合算法

孔垂超，田景文，高美娟

北京聯(lián)合大學(xué) 北京市信息服務(wù)工程重點(diǎn)實(shí)驗(yàn)室，北京 100101

1 引言

現(xiàn)代海戰(zhàn)消耗物資種類(lèi)較多，艦只設(shè)備損毀量較大，后勤補(bǔ)給負(fù)擔(dān)重，所需后勤物資傳送距離遠(yuǎn)，因此海上軍用補(bǔ)給艦船運(yùn)輸路徑的選擇是軍事后勤保障的一項(xiàng)重要任務(wù)。時(shí)間是決定戰(zhàn)爭(zhēng)勝負(fù)的關(guān)鍵因素之一，如何對(duì)軍用補(bǔ)給艦船運(yùn)輸路徑進(jìn)行規(guī)劃，使海戰(zhàn)中的軍用物資經(jīng)過(guò)軍事物流的必要環(huán)節(jié)高效、準(zhǔn)確、及時(shí)地運(yùn)抵戰(zhàn)斗艦只從而迅速轉(zhuǎn)化為戰(zhàn)斗力，是當(dāng)前需要研究的一項(xiàng)現(xiàn)實(shí)而又緊迫的課題[1]。

從本質(zhì)上來(lái)說(shuō)，該問(wèn)題屬于VRP（Vehicle Routing Problem）問(wèn)題，是VRP在軍事領(lǐng)域的典型應(yīng)用，所以軍用補(bǔ)給艦船路徑規(guī)劃問(wèn)題具備VRP的典型特征。

由于路徑規(guī)劃問(wèn)題是典型的組合優(yōu)化NP難題[2]，求解較為困難，而且具有廣泛的現(xiàn)實(shí)應(yīng)用背景，所以長(zhǎng)期以來(lái)有大量學(xué)者對(duì)其進(jìn)行不斷地研究探索，研究人員從最初的精確算法開(kāi)始，逐步轉(zhuǎn)向更廣闊的啟發(fā)式算法領(lǐng)域，如遺傳算法、禁忌搜索算法、蟻群算法等。鐘石泉等人提出通過(guò)禁忌搜索算法對(duì)軟、硬時(shí)間窗約束的VRP進(jìn)行求解[3]；Chao提出用禁忌搜索算法對(duì)多運(yùn)輸工具型VRP進(jìn)行求解[4]；Chen等人利用遺傳算法對(duì)鋼鐵領(lǐng)域物流配送中的車(chē)輛時(shí)間表制定及路徑選擇問(wèn)題進(jìn)行求解[5]；龔延成等人利用遺傳算法求解物流配送組織過(guò)程中的運(yùn)輸工具調(diào)度問(wèn)題[6]；唐爐亮等人針對(duì)GPS數(shù)據(jù)的公眾出行路徑優(yōu)化問(wèn)題提出了一種改進(jìn)蟻群算法[7]。這些算法在VRP的求解上取得了很大的成果，可以較好地運(yùn)用于海戰(zhàn)軍用物資配送的路徑規(guī)劃問(wèn)題中，但也存在著不少問(wèn)題和不足，如禁忌搜索算法存在對(duì)初始解有較高的依賴(lài)性的缺點(diǎn)；遺傳算法有局部搜索能力不強(qiáng)，易陷入早熟，總體上可行解的質(zhì)量不高等缺點(diǎn)，尤其是遺傳算法的變異操作是隨機(jī)的，且個(gè)體間無(wú)信息交流，導(dǎo)致收斂速度較慢的問(wèn)題，這在軍事應(yīng)用中是一個(gè)致命的缺陷。

遺傳算法自從被提出就受到了廣泛的關(guān)注，有很多研究人員將該算法應(yīng)用于解決路徑優(yōu)化、任務(wù)分配以及無(wú)線傳感器網(wǎng)絡(luò)（WSN）路由規(guī)劃等問(wèn)題。例如田景文等人提出將遺傳算法與蟻群算法相結(jié)合來(lái)解決無(wú)線傳感器網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題[8]；高美娟等人提出一種改進(jìn)遺傳算法并將其應(yīng)用于Web文本挖掘[9]；李成博等人提出了一種基于遺傳算法的WMSNs多路徑多目標(biāo)優(yōu)化路由算法[10]；雷霖等人提出了一種基于遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)路徑優(yōu)化算法[11]；楊開(kāi)兵等人提出了一種改進(jìn)的Pareto適應(yīng)度遺傳算法用于解決多目標(biāo)組合優(yōu)化的求解問(wèn)題[12]；孔垂超等人提出了一種將遺傳算法與BP算法相結(jié)合的改進(jìn)混合算法應(yīng)用于車(chē)輛路徑規(guī)劃。在這些領(lǐng)域的應(yīng)用中，遺傳算法都表現(xiàn)出了良好的性能，但是遺傳算法也存在一些缺陷，例如：由于遺傳算法不是采用確定性規(guī)則而是采用概率變遷規(guī)則來(lái)指導(dǎo)其搜索方向，所以其搜索方向的明確性在解決大規(guī)模問(wèn)題時(shí)遠(yuǎn)遠(yuǎn)達(dá)不到要求，導(dǎo)致其在運(yùn)算過(guò)程中收斂速度慢，運(yùn)算時(shí)間長(zhǎng)，容易陷入局部最優(yōu)解，這對(duì)于軍用補(bǔ)給艦船運(yùn)輸?shù)穆窂揭?guī)劃來(lái)說(shuō)是極為不利的。

粒子群算法是基于鳥(niǎo)類(lèi)覓食行為而提出的一種算法，其功能與遺傳算法非常相似，也是一種迭代優(yōu)化算法即系統(tǒng)初始化為一組隨機(jī)解，經(jīng)由迭代來(lái)尋找最優(yōu)解，與遺傳算法相比，具有收斂速度快，參數(shù)設(shè)置少，實(shí)現(xiàn)方便且不需要梯度信息等優(yōu)點(diǎn)，且其搜索過(guò)程是通過(guò)并行性從一組解迭代到另一組解，其粒子運(yùn)行可以搜索不確定的復(fù)雜區(qū)域，最重要的是其具有記憶特性，具有良好的搜索方向引導(dǎo)性能，這一特點(diǎn)可以用于彌補(bǔ)遺傳算法變異操作無(wú)方向性的缺陷。但粒子群算法也有一些缺點(diǎn)，如易陷入局部極值點(diǎn)，搜索精度不高以及數(shù)學(xué)基礎(chǔ)相對(duì)較為薄弱等。

本文針對(duì)上述遺傳算法與粒子群算法的優(yōu)缺點(diǎn)，對(duì)遺傳算法操作算子做出了很大改進(jìn)，然后將兩種算法進(jìn)行結(jié)合，將遺傳算子引入粒子群算法中，有效提高了算法收斂速度，得到了一種運(yùn)算效率更高，運(yùn)算結(jié)果更精確的改進(jìn)混合優(yōu)化算法。

2 軍用補(bǔ)給艦船路徑規(guī)劃數(shù)學(xué)模型

軍用補(bǔ)給艦船路徑規(guī)劃問(wèn)題實(shí)際上是VRP問(wèn)題在海洋環(huán)境中的一個(gè)特定實(shí)例。因此該問(wèn)題的數(shù)學(xué)建模規(guī)則跟VRP問(wèn)題的建模規(guī)則是一樣的，即明確規(guī)定符合約束條件時(shí)應(yīng)派出的艦船數(shù)量及各艦船的具體路徑，保證按時(shí)、按量完成運(yùn)輸任務(wù)，同時(shí)盡量做到使路徑總長(zhǎng)度最短。

根據(jù)上述數(shù)學(xué)建模規(guī)則，在本文中，軍用補(bǔ)給艦船路徑規(guī)劃的數(shù)學(xué)模型表述如下：某海軍基地向k艘艦船運(yùn)送軍用物資，設(shè)第i艘艦船的物資需求量為gi(i=1，2，…，k)，由海軍基地派出載重量為q的運(yùn)輸艦船承擔(dān)運(yùn)輸任務(wù)。設(shè)gi＜q，求滿足軍用物資運(yùn)輸需求的最短行程路線。

為了有效地進(jìn)行路線規(guī)劃，可以事先對(duì)需要使用的艦船數(shù)目進(jìn)行估算。在現(xiàn)實(shí)情況中，艦船數(shù)目的需求量取決于軍用物資裝卸的復(fù)雜程度，裝卸越復(fù)雜，約束條件就越多，艦船的實(shí)際載重量就越小。戰(zhàn)斗艦艇自主選擇的軍用物資運(yùn)送艦船數(shù)目可以由下列公式[13]求得：

其中，n表示所需的艦船數(shù)；［］表示取整，為保證艦船數(shù)目足夠，在取整后再加1；gi代表第i艘艦船的物資需求量；α是參數(shù)，且0＜α＜1；q代表運(yùn)輸艦船的載重量。約束條件越多的情況下，物資裝船、卸船越復(fù)雜，α值就越小，一般取α＝0.85。

用cij表示點(diǎn)i到點(diǎn)j的路程，海軍基地的編號(hào)為0，各戰(zhàn)斗艦船的編號(hào)為i(i＝1，2，…，k)，現(xiàn)定義如下變量：

可以建立下列目標(biāo)函數(shù)的數(shù)學(xué)模型：

限制條件如下：

式（4）是以補(bǔ)給艦船行駛路徑最短作為目標(biāo)函數(shù)的數(shù)學(xué)模型。式（5）、（6）、（7）、（8）為該目標(biāo)函數(shù)的約束條件，其中，式（5）表示每艘艦船裝載的軍用物資總重量不得超過(guò)其最大載重量；式（6）是為了保證針對(duì)每艘戰(zhàn)斗艦艇的配送任務(wù)在同一時(shí)刻僅由一艘艦船來(lái)完成，防止出現(xiàn)多艘補(bǔ)給艦船在同一時(shí)刻為同一艘戰(zhàn)斗艦艇服務(wù)的混亂狀況，而所有運(yùn)輸任務(wù)則由n艘艦船協(xié)同完成；式（7）、（8）保證了到達(dá)和離開(kāi)某一艦艇的貨船有且僅有一艘。

由上述數(shù)學(xué)模型可知該問(wèn)題是一個(gè)典型的多約束條件下的尋優(yōu)問(wèn)題，諸如遺傳算法等啟發(fā)式算法在解決該類(lèi)問(wèn)題方面具有很大優(yōu)勢(shì)，所以本文提出了一種將改進(jìn)遺傳算法與粒子群算法相結(jié)合的改進(jìn)混合算法來(lái)對(duì)該問(wèn)題進(jìn)行求解。

3 粒子群優(yōu)化算法

粒子群優(yōu)化算法概念簡(jiǎn)單，具有很強(qiáng)的較優(yōu)解搜尋能力，算法比較簡(jiǎn)潔，易于實(shí)現(xiàn)，沒(méi)有很多參數(shù)需要調(diào)整，且不需要梯度信息。Eberhart等人已經(jīng)成功將粒子群算法用于分析帕金森綜合癥等顫抖類(lèi)疾病[14]；He等人用改進(jìn)的速度更新方程訓(xùn)練模糊神經(jīng)網(wǎng)絡(luò)[15]。

在粒子群算法中，每個(gè)個(gè)體稱(chēng)為一個(gè)“粒子”，每個(gè)粒子對(duì)應(yīng)一個(gè)潛在的解。在一個(gè)D維的目標(biāo)搜索空間中，每個(gè)粒子被看成是空間內(nèi)的一個(gè)點(diǎn)。設(shè)群體由m個(gè)粒子構(gòu)成，zi=(zi1，zi2，…，ziD)為第i個(gè)粒子 (i=1，2，…，m)的D維位置矢量，根據(jù)事先設(shè)定的適應(yīng)度值函數(shù)計(jì)算zi當(dāng)前的適應(yīng)度值；vi=(vi1，vi2，…，vid，…，viD)為粒子i的飛行速度；pi=(pi1，pi2，…，pid，…，piD)為粒子迄今為止搜索到的最優(yōu)位置；pg=(pg1，pg2，…，pgd，…，pgD)代表整個(gè)粒子群迄今為止搜索到的最優(yōu)位置。在每次迭代中，粒子根據(jù)以下公式更新速度和位置：

其中，i=1，2，…，m，d=1，2，…，D，k是迭代次數(shù)，r1和r2為[0，1]之間的隨機(jī)數(shù)，這兩個(gè)參數(shù)用來(lái)保持群體的多樣性；c1和c2為學(xué)習(xí)因子，使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)點(diǎn)以及群體內(nèi)歷史最優(yōu)點(diǎn)靠近。粒子群算法的簡(jiǎn)化流程圖如圖1所示。

粒子群算法具有記憶性，較優(yōu)解的知識(shí)被所有粒子都保存，而對(duì)于遺傳算法，以前的知識(shí)隨著種群的改變被破壞。在粒子群算法中，信息只來(lái)自粒子自身找到的最優(yōu)位置和群體中的最好粒子，整個(gè)搜索更新過(guò)程是跟隨當(dāng)前最優(yōu)值的過(guò)程，其方向性較為明確，因此，與遺傳算法比較，所有的粒子在大多數(shù)情況下可以更快地收斂于最優(yōu)值。

圖1 粒子群算法流程圖

4 改進(jìn)遺傳算法

遺傳算法是一種全新的全局優(yōu)化搜索算法，以其簡(jiǎn)單通用，魯棒性強(qiáng)，適用于并行處理等特點(diǎn)，成為一種被廣泛應(yīng)用的重要啟發(fā)式算法[16]。但是遺傳算法也有較多的缺點(diǎn)，較明顯的是其采用概率的變遷規(guī)則來(lái)指導(dǎo)其搜索方向，導(dǎo)致搜索方向的明確性達(dá)不到要求，且其變異是隨機(jī)的，缺乏方向性，導(dǎo)致收斂速度不快，耗費(fèi)時(shí)間長(zhǎng)，這在軍用補(bǔ)給艦船運(yùn)輸路徑規(guī)劃中是極為不利的。

本文對(duì)傳統(tǒng)遺傳算法進(jìn)行改進(jìn)，在遺傳算法的操作中加入克隆操作算子，在選擇操作中采用截?cái)噙x擇策略。下面是在本文在改進(jìn)遺傳算法中所采用的操作算子：

（1）選擇。本文放棄常用的輪盤(pán)賭策略，采用截?cái)噙x擇法進(jìn)行參數(shù)選擇，截?cái)噙x擇法是一種人工選擇法，適用于規(guī)模較大的種群。在截?cái)噙x擇法中，個(gè)體按適應(yīng)度值排序，只有最優(yōu)秀的個(gè)體可以被選作父代個(gè)體，截?cái)噙x擇的參數(shù)叫做截?cái)嚅撝礣runc，指的是被選作父代個(gè)體的百分比，在本文中，Trunc的取值為10%。在該閾值之下的個(gè)體不能產(chǎn)生子個(gè)體。

顯然，這種選擇方式也使得適應(yīng)度值較高的個(gè)體具有較大的“生存”機(jī)會(huì)。同時(shí)，由于它只使用適應(yīng)度值的相對(duì)值作為選擇的標(biāo)準(zhǔn)，而與適應(yīng)度值的數(shù)值大小不成直接比例，從而它也能避免超級(jí)個(gè)體的影響，在一定程度上避免了過(guò)早收斂和停滯現(xiàn)象的發(fā)生。

在運(yùn)輸艦只路徑規(guī)劃中，染色體即為各種不同的路徑，種群即多條染色體的集合，適應(yīng)度值取路徑長(zhǎng)度l的倒數(shù)。在采用錦標(biāo)賽選擇策略時(shí)，路徑長(zhǎng)度l越短，染色體的適應(yīng)度值越高，適應(yīng)度值最高的染色體得以保留作為下一代種群的父代染色體。

選擇強(qiáng)度為：

多樣化損失為：

選擇方差為：

其中fc為下列高斯分布的積分下限：

（2）克隆?？寺〔僮骶褪菍?duì)適應(yīng)度值較高的個(gè)體進(jìn)行復(fù)制，產(chǎn)生一個(gè)新的子群體，從而擴(kuò)大解的搜索范圍。本算法中，將由第一步通過(guò)截?cái)噙x擇所產(chǎn)生的父代個(gè)體進(jìn)行克隆操作，產(chǎn)生一個(gè)新的子代群體，這樣便擴(kuò)大了解的搜索空間。

本算法中克隆算子的定義如下：

設(shè)Γc為一個(gè)Rn→Rn的映射，如果對(duì)任一X∈Rn有Γc(X)=[Γc(x1)，Γc(x2)，…，Γc(xn)]T成立，則稱(chēng) Γc為克隆算子。

其中 Γc(xi)=Ii×xi，Ii是NCi維行向量，NCi代表克隆的數(shù)量，其值可事先確定，也可在算法中動(dòng)態(tài)調(diào)整。在上述算法中，克隆的規(guī)模與適應(yīng)度值成正比，既適應(yīng)度越高，個(gè)體被克隆得越多，在這里克隆的數(shù)量NCi按下式計(jì)算NCi=[βN/i]，i=1，2，3，…，其中，β∈(0，1)是克隆常數(shù)，N是種群規(guī)模，將個(gè)體按適應(yīng)度度排序，i是其序號(hào)。

（3）變異。變異操作是遺傳算法中保持物種多樣性的一個(gè)重要途徑，不僅被視為找回因交叉操作而遺失優(yōu)良基因的手段，還是探索相鄰空間、優(yōu)化性能的有力工具。考慮到VRP問(wèn)題的實(shí)際情況，一般采用自然數(shù)形式編碼。本文對(duì)于新種群的個(gè)體采取用Logistic方程對(duì)應(yīng)的概率分布函數(shù)來(lái)進(jìn)行變異操作的方案。

Logistic方程對(duì)應(yīng)的概率密度函數(shù)如下：

利用該變異操作產(chǎn)生的種群多樣度較高，跳出局部極值的能力較強(qiáng)。本算法對(duì)適應(yīng)度值越低的個(gè)體所進(jìn)行的變異程度越高，對(duì)克隆所產(chǎn)生的個(gè)體進(jìn)行變異操作，保留原父代個(gè)體，從而保證了原有優(yōu)秀個(gè)體，又?jǐn)U大了解的搜尋范圍。

（4）交叉。由于在VRP問(wèn)題中一般采用自然數(shù)形式編碼，所以在交叉操作時(shí)一般采用離散交叉方式，即在個(gè)體之間變換變量的值，子個(gè)體的每個(gè)變量等概率地隨機(jī)挑選父?jìng)€(gè)體。

5 改進(jìn)遺傳粒子群混合算法的實(shí)現(xiàn)步驟

本文所提出的改進(jìn)遺傳-粒子群混合算法的基本思想是在粒子群算法中引進(jìn)遺傳算法的操作算子，即標(biāo)準(zhǔn)遺傳算法的選擇、交叉和變異算子，以及本文為改進(jìn)遺傳算法所引入的克隆算子，提高粒子群算法擺脫局部極值點(diǎn)的能力和提高搜索精度的能力，同時(shí)將粒子群優(yōu)化中粒子的飛行引入遺傳算法中去，用粒子群公式對(duì)每個(gè)個(gè)體的速度及位置進(jìn)行更新，并限制其不超過(guò)邊界，并更新全局最優(yōu)位置；用粒子群優(yōu)化公式指導(dǎo)遺傳變異，使得變異操作具有更加明確的方向性，按粒子群優(yōu)化公式對(duì)執(zhí)行變異操作后的個(gè)體進(jìn)一步更新其位置，直到找到達(dá)到評(píng)估要求的全局最優(yōu)解。該算法通過(guò)將粒子群算法與改進(jìn)的遺傳算法進(jìn)行結(jié)合，實(shí)現(xiàn)兩種算法的優(yōu)勢(shì)互補(bǔ)。

本文提出的改進(jìn)遺傳-粒子群混合算法的實(shí)現(xiàn)步驟如下：

（1）隨機(jī)初始化種群P，種群大小為n，確定每個(gè)個(gè)體的初始位置和速度；

（2）根據(jù)目標(biāo)函數(shù)計(jì)算所有個(gè)體的適應(yīng)度值；

（3）若達(dá)到結(jié)束條件，算法終止；

（4）選擇部分適應(yīng)度值高的個(gè)體組成集合Pm；

（5）在Pm中選擇適應(yīng)度值最高的k個(gè)個(gè)體進(jìn)行克隆操作得到Pc，克隆的數(shù)量與適應(yīng)度值成正比；

（6）用前文中所提到的改進(jìn)遺傳算法對(duì)Pc中的個(gè)體進(jìn)行交叉與變異操作，適應(yīng)度值越低的個(gè)體其變異程度越大；

（7）重新計(jì)算Pc中每個(gè)個(gè)體的適應(yīng)度值；

（8）按粒子群優(yōu)化進(jìn)化公式對(duì)Pc中每個(gè)個(gè)體的速度和位置進(jìn)行更新，同時(shí)限制其不超過(guò)邊界，并更新全局最優(yōu)位置；

（9）回到（2）。

在算法的第（8）步，針對(duì)變異后的種群，將粒子群優(yōu)化算法公式引入遺傳操作過(guò)程，使得個(gè)體具有社會(huì)性特征，可促進(jìn)不同個(gè)體之間信息的交流，其良好的最優(yōu)解搜索方向引導(dǎo)性能使得對(duì)最優(yōu)解的搜索具有更明確的方向性，可以彌補(bǔ)遺傳算法變異操作無(wú)方向性的缺陷，因此可以提高算法的性能；同時(shí)，因?yàn)榱Ｗ尤核惴ㄐ枰{(diào)整的參數(shù)較少，需要評(píng)估函數(shù)的次數(shù)少，不需要目標(biāo)函數(shù)的梯度信息，所以可以提高算法的收斂速度。

改進(jìn)遺傳-粒子群混合算法流程圖如圖2。

圖2 改進(jìn)混合算法流程圖

圖3 Sphere函數(shù)的尋優(yōu)曲線圖

6 仿真結(jié)果分析

6.1 仿真實(shí)驗(yàn)

本文所做的兩次仿真實(shí)驗(yàn)均是在MATLAB環(huán)境下進(jìn)行的。

為了驗(yàn)證所提出的改進(jìn)混合算法的尋優(yōu)性能，本文選用如下函數(shù)進(jìn)行實(shí)驗(yàn)。

（1）Sphere函數(shù)：

該函數(shù)為簡(jiǎn)單的單峰二次函數(shù)。

（2）Rastrgin函數(shù)：

該函數(shù)是具有大量局部極值點(diǎn)的多峰函數(shù)，非常難尋到全局最優(yōu)值，本次仿真實(shí)驗(yàn)的理論最優(yōu)值為0。

函數(shù)f1(x)和f2(x)的標(biāo)準(zhǔn)粒子群算法和改進(jìn)的粒子群優(yōu)化算法函數(shù)的運(yùn)算30次平均優(yōu)化結(jié)果，如表1所示；函數(shù)f1(x)和f2(x)函數(shù)優(yōu)化曲線分別如圖3和圖4所示（圖中曲線1、2和3分別代表自適應(yīng)遺傳算法、免疫遺傳算法和改進(jìn)混合算法的尋優(yōu)曲線）。

表1 三種算法分別對(duì)兩個(gè)函數(shù)進(jìn)行尋優(yōu)所得數(shù)據(jù)

由表1可知，對(duì)于Sphere和Rastrgin兩個(gè)函數(shù)來(lái)說(shuō)，本文所提出的改進(jìn)混合算法比自適應(yīng)遺傳算法和免疫遺傳算法具有更好的尋優(yōu)能力，可以找到更接近理論最優(yōu)值0的平均最小值，通過(guò)數(shù)值比較也能看出，改進(jìn)混合算法的收斂性能和搜索能力也比另外兩種算法好。同時(shí)，由圖3和圖4的尋優(yōu)曲線圖可以看出，相比另外兩種算法，本文所提出的改進(jìn)混合算法能達(dá)到更小的適應(yīng)度值，從而擴(kuò)大了搜索范圍和提高了收斂精度；對(duì)于較為復(fù)雜的Rastrgin函數(shù)來(lái)說(shuō)，改進(jìn)混合算法的尋優(yōu)曲線也比另外兩種算法要平滑，說(shuō)明改進(jìn)混合算法穩(wěn)定性更好，效果也更明顯。

圖4 Rastrgin函數(shù)的尋優(yōu)曲線圖

在本次仿真實(shí)驗(yàn)中，建立一個(gè)平面坐標(biāo)系，選取適當(dāng)大小的平面區(qū)域作為艦船活動(dòng)區(qū)域（為方便計(jì)算，本文選取橫縱坐標(biāo)均為100個(gè)單位長(zhǎng)度的區(qū)域作為仿真實(shí)驗(yàn)區(qū)域）。選擇一艘艦船需要遍歷的節(jié)點(diǎn)數(shù)為29，即k=29，加上海軍基地共30個(gè)節(jié)點(diǎn)。分別對(duì)自適應(yīng)遺傳算法、免疫遺傳算法和本文所提出的粒子群優(yōu)化遺傳算法進(jìn)行了仿真，以便更好地對(duì)本文提出的粒子群優(yōu)化遺傳算法的性能進(jìn)行對(duì)比分析。

在仿真實(shí)驗(yàn)中，隨機(jī)選取的30個(gè)節(jié)點(diǎn)的坐標(biāo)分別為（87，7），（91，38），（83，46），（71，44），（64，60），（68，58），（83，69），（87，76），（74，78），（71，71），（58，69），（54，62），（51，67），（37，84），（41，94），（2，99），（7，64），（22，60），（25，62），（18，54），（4，50），（13，40），（18，40），（24，42），（25，38），（41，26），（45，21），（44，35），（58，35），（62，32）。令（87，7）代表海軍基地，編號(hào)為0，后面依次編號(hào)為1，2，…，29。節(jié)點(diǎn)編號(hào)均在仿真實(shí)驗(yàn)所得路徑示意圖中標(biāo)出，見(jiàn)圖5、圖6、圖7。

圖5 利用自適應(yīng)遺傳算法得到的路徑示意圖

圖6 利用免疫遺傳算法得到的路徑示意圖

圖7 利用改進(jìn)混合算法得到的路徑示意圖

利用本文所提出的改進(jìn)遺傳-粒子群混合算法與免疫遺傳算法、自適應(yīng)遺傳算法尋找海上軍用物資路徑規(guī)劃的全局最優(yōu)解。本文的仿真實(shí)驗(yàn)以相鄰兩次優(yōu)化過(guò)程中均方誤差的差值的變化率小于等于0.01作為算法終止的條件，此時(shí)得到的解已經(jīng)充分接近最優(yōu)解，這時(shí)算法終止。下面比較三種算法求得的結(jié)果，分析其求解性能與效率。

圖5、圖6和圖7分別是三種算法所求得的仿真路徑示意圖（圖中坐標(biāo)系用于確定節(jié)點(diǎn)的位置，使得所求路徑便于觀察，便于參考路徑長(zhǎng)度比例關(guān)系，所以其坐標(biāo)值并不是帶單位的具體長(zhǎng)度）。

利用自適應(yīng)遺傳算法求得的路徑為：0→1→2→5→6→7→8→9→10→4→11→12→14→13→18→16→22→20→15→21→19→17→24→23→3→29→28→27→25→26→0。

利用免疫遺傳算法求得的路徑為：0→1→3→2→5→9→8→6→7→4→11→10→12→17→18→16→20→19→22→21→15→14→13→23→24→27→28→26→25→29→0。

利用改進(jìn)混合算法求得的路徑為：0→1→2→3→28→27→26→25→24→23→22→21→20→18→17→19→16→15→14→10→11→12→13→4→7→6→8→9→5→29→0。

按照以相鄰兩次優(yōu)化過(guò)程中均方誤差差值的變化率小于等于0.01作為算法終止條件的標(biāo)準(zhǔn)，所得實(shí)驗(yàn)結(jié)果為通過(guò)自適應(yīng)遺傳算法在57.1 s的時(shí)間內(nèi)得到長(zhǎng)度為523.013 3個(gè)單位長(zhǎng)度的路徑，通過(guò)免疫遺傳算法在61.8 s的時(shí)間內(nèi)得到長(zhǎng)度為492.363 3個(gè)單位長(zhǎng)度的路徑，通過(guò)改進(jìn)混合算法在55.3 s的時(shí)間內(nèi)得到長(zhǎng)度為476.384 2個(gè)單位長(zhǎng)度的路徑。

根據(jù)實(shí)驗(yàn)所得結(jié)果可以看出與自適應(yīng)遺傳算法和免疫遺傳算法相比，本文所提出的改進(jìn)混合算法的求解效率是最高的。仿真實(shí)驗(yàn)所得數(shù)據(jù)如表2所示。

表2 三種算法計(jì)算所得數(shù)據(jù)

6.2 實(shí)驗(yàn)結(jié)果分析與評(píng)價(jià)

從實(shí)例仿真可以看出，本文所提出的改進(jìn)混合算法相對(duì)于其他兩種算法能夠以更快的速度收斂到全局最優(yōu)解；求解方面，改進(jìn)混合算法比其他兩種算法找到的路徑長(zhǎng)度更短，其解的質(zhì)量有很大提高。說(shuō)明本文的改進(jìn)混合算法跟其他兩種算法相比，不僅操作簡(jiǎn)單，而且收斂效果好，收斂速度快，全局收斂率高。

7 總結(jié)

由研究車(chē)輛路徑規(guī)劃問(wèn)題（VBR）的算法開(kāi)始，通過(guò)分析遺傳算法與粒子群算法各自的優(yōu)缺點(diǎn)，研究出將兩種算法進(jìn)行結(jié)合的改進(jìn)混合算法，用于解決軍用補(bǔ)給艦船運(yùn)輸路徑規(guī)劃的問(wèn)題。該方法的特點(diǎn)是將粒子群優(yōu)化算法中加入改進(jìn)的遺傳操作算子，并將粒子群優(yōu)化公式對(duì)遺傳變異進(jìn)行引導(dǎo)，有效提高了遺傳算法的尋優(yōu)效率。本文改進(jìn)混合算法通過(guò)對(duì)遺傳算法與粒子群優(yōu)化算法的結(jié)合，比較有效地將兩種算法的優(yōu)缺點(diǎn)進(jìn)行了互補(bǔ)，提高了求解效率與質(zhì)量。通過(guò)在MATLAB環(huán)境下利用Sphere函數(shù)和Rastrgin函數(shù)對(duì)自適應(yīng)遺傳算法、免疫遺傳算法與改進(jìn)混合算法的尋優(yōu)性能進(jìn)行驗(yàn)證，并進(jìn)行30個(gè)節(jié)點(diǎn)的仿真實(shí)驗(yàn)，對(duì)仿真結(jié)果做對(duì)比分析，證明本文的改進(jìn)混合算法在尋優(yōu)能力和效率等方面要優(yōu)于其他兩種算法，在軍用補(bǔ)給艦船路徑規(guī)劃問(wèn)題的求解中具有求解速度快，所得解質(zhì)量高的優(yōu)點(diǎn)，因而本方法是有效且可行的。

[1]楊春周，滕克難.戰(zhàn)時(shí)艦載導(dǎo)彈配送路徑規(guī)劃模型構(gòu)建研究[J].艦船科學(xué)技術(shù)，2009，31（9）：136-140.

[2]宋留勇，王銳，周永旺，等.動(dòng)態(tài)城市交通網(wǎng)絡(luò)優(yōu)化模型研究及算法設(shè)計(jì)[J].測(cè)繪科學(xué)，2011，36（1）：134-136.

[3]鐘石泉，賀國(guó)光.有時(shí)間窗約束車(chē)輛調(diào)度優(yōu)化的一種禁忌算法[J].系統(tǒng)工程理論方法應(yīng)用，2005，14（6）：523-527.

[4]Chao Yiming.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：33-51.

[5]Chen Yaorong，Liang Bo，Zhou Meihua.Optimization for vehicle scheduling in iron and steel works based on semitrailer swap transport[J].Journal of Central South University of Technology：English Edition，2010，17（4）：873-879.

[6]龔延成，郭曉汾，尤曉鈴，等.基于遺傳算法的物流配送車(chē)輛調(diào)度問(wèn)題研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2004，34（6）：93-97.

[7]唐爐亮，常曉猛，李清泉，等.基于蟻群優(yōu)化算法與出租車(chē)GPS數(shù)據(jù)的公眾出行路徑優(yōu)化[J].中國(guó)公路學(xué)報(bào)，2011，24（2）：89-95.

[8]Tian Jingwen，Sun Yang.WSN path optimization based on fusion of improved ant colony algorithm and genetic algorithm[J].Journal of Computational Information Systems，2010，6（5）：1591-1599.

[9]Tian Jingwen，Gao Meijuan.Web text mining based on improved genetic algorithm and radialbasisfunction neural network[J].Journal of Computational Information Systems，2012，8（3）：1195-1202.

[10]李成博，王小明，柳強(qiáng).基于遺傳算法的WMSNs多路徑多目標(biāo)優(yōu)化路由算法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2277-2282.

[11]雷霖，李偉峰，王厚軍.基于遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)路徑優(yōu)化[J].電子科技大學(xué)學(xué)報(bào)，2009，38（2）：227-230.

[12]楊開(kāi)兵，劉曉冰.求解多目標(biāo)組合優(yōu)化的改進(jìn)Pareto適應(yīng)度遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（8）：44-46.

[13]陳迎新.基于改進(jìn)蟻群算法的車(chē)輛路徑優(yōu)化問(wèn)題研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2031-2034.

[14]Eberhart R C，Hu X.Human tremor analysis using particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway：IEEE Service Center，1999：1927-1930.

[15]He Z，Wei C，Yang L.Extracting rules from fuzzy neural network by particle swarm optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation，Anchorage，1998：74-77.

[16] 張鈴，張鈸.遺傳算法機(jī)理的研究[J].軟件學(xué)報(bào)，2000，11（7）：945-952.