基于遺傳算法的遠(yuǎn)海島礁補(bǔ)給模型研究*

李 東 滕 哲 張煒靈

（海軍大連艦艇學(xué)院 大連 116018）

1 引言

我國島礁眾多，面積達(dá)500m2以上的島嶼為6500多個(gè)，島礁對于海洋主權(quán)意義重大。占領(lǐng)島礁意味著可以獲取所有權(quán)、使用權(quán)、收益權(quán)、控制權(quán)等，但是僅僅通過宣示的方式往往是不夠的，只有實(shí)際占領(lǐng)、控制和管轄才能更好地維護(hù)正當(dāng)權(quán)益。要進(jìn)行島礁的實(shí)際占領(lǐng)就必須派遣人員駐扎，而多數(shù)島礁自然資源匱乏，交通不便，駐扎所需的一切物資幾乎全需要依靠外部補(bǔ)給。很多礁距離大陸較遠(yuǎn)、位置相對分散、靠泊條件各異、物資需求量和儲(chǔ)存量各不相同，如何研究制定科學(xué)合理、安全高效的物資補(bǔ)給策略，一直是我軍后勤保障部門關(guān)注的重要課題。

通常情況下，由后勤保障中心根據(jù)實(shí)際需求，以一個(gè)月為一個(gè)補(bǔ)給周期，制定補(bǔ)給方案，分別由不同型號(hào)的補(bǔ)給船和運(yùn)輸機(jī)執(zhí)行物資補(bǔ)給任務(wù)。補(bǔ)給船和運(yùn)輸機(jī)都是從物資保障中心出發(fā)，為各島礁運(yùn)送所需物資，回程運(yùn)回垃圾及其他材料等。補(bǔ)給方案應(yīng)當(dāng)包括補(bǔ)給船（或運(yùn)輸機(jī)）種類、補(bǔ)給路線、補(bǔ)給數(shù)量、轉(zhuǎn)運(yùn)方式、物資裝卸與回收材料的數(shù)量等。

綜合考慮上述因素，本文建立了一個(gè)數(shù)學(xué)模型，嘗試給出一個(gè)補(bǔ)給周期的島礁物資補(bǔ)給方案。

2 模型基本假設(shè)

為了便于問題的研究，對題中某些條件進(jìn)行合理假設(shè)：

1）補(bǔ)給中心及島礁之間不存在障礙，可沿歐式幾何的平面最短路徑通行。

2）所有補(bǔ)給船只、飛機(jī)及補(bǔ)給設(shè)備工作穩(wěn)定，所有時(shí)間內(nèi)均保持相同航行速度、補(bǔ)給速度。

3）島礁上需回收的固體不計(jì)儲(chǔ)存成本。

4）所有補(bǔ)給船只在補(bǔ)給時(shí)可以同時(shí)補(bǔ)給固體和液體。

5）一個(gè)補(bǔ)給周期（一月）時(shí)長為30天。

對于模型中將要用到的物理量，定義如表1所示。

表1 模型中的物理量

3 方案建模

本文的課題是研究我補(bǔ)給艦船在某海域島礁之間的物資補(bǔ)給問題，目的是統(tǒng)籌補(bǔ)給時(shí)間、島礁現(xiàn)狀和經(jīng)濟(jì)性等多要素，設(shè)計(jì)一個(gè)詳實(shí)、合理的補(bǔ)給方案。這類問題可以歸類為非線性規(guī)劃問題，但由于數(shù)據(jù)要素較多，模型復(fù)雜，需要在現(xiàn)有理論上開展進(jìn)一步思考。因此，在廣泛查閱了相關(guān)參考文獻(xiàn)［1～3］基礎(chǔ)之上，對問題展開探索。

3.1 分塊處理，問題簡化

在進(jìn)行補(bǔ)給方案設(shè)計(jì)時(shí)，應(yīng)顧及島嶼之間的相對位置、最大儲(chǔ)存量、剩余物資量、日消耗量、固體回收量、補(bǔ)給時(shí)間、經(jīng)濟(jì)成本等，要素多，情況極為復(fù)雜，因此首先考慮將問題分塊解決。

首先，針對補(bǔ)給的經(jīng)濟(jì)情況進(jìn)行建模。補(bǔ)給開銷主要分為島礁物資儲(chǔ)存成本和補(bǔ)給艦船運(yùn)輸成本兩方面，設(shè)所有島礁的儲(chǔ)存成本總和為E儲(chǔ)，所有補(bǔ)給艦船的運(yùn)輸成本總和為E運(yùn)，補(bǔ)給方案的總開支為E總，則其關(guān)系可表示如下：

同樣地，可以對液體物資也列出類似公式、進(jìn)行類似變換，綜合起來，可以得到總的島礁儲(chǔ)存成本表達(dá)式和單個(gè)島礁的儲(chǔ)存成本表達(dá)式：

從中可以明顯地看出，無論對島礁補(bǔ)充量如何，只要當(dāng)補(bǔ)充量不為零時(shí)所對應(yīng)的j越大（即補(bǔ)充時(shí)間越遲）時(shí)，所得島礁儲(chǔ)存成本越小。

綜上，物資儲(chǔ)存模型和物資運(yùn)送模型已經(jīng)建立，并且對物資儲(chǔ)存成本同補(bǔ)給時(shí)間的關(guān)系進(jìn)行了探索，推導(dǎo)了補(bǔ)給時(shí)間點(diǎn)的一般通式，為下一步優(yōu)化處理打下了基礎(chǔ)。

3.2 問題變換，優(yōu)化參數(shù)

對于島礁而言，希望盡量能減少物資的儲(chǔ)存成本?；谘a(bǔ)給時(shí)間關(guān)于每次補(bǔ)給量之間的關(guān)系，將尋求最優(yōu)的存儲(chǔ)成本問題，轉(zhuǎn)變?yōu)閷で笞詈线m的補(bǔ)給量，將問題轉(zhuǎn)化成了一個(gè)非線性優(yōu)化問題。

在尋優(yōu)問題中，利用了格雷碼的遺傳算法［4～5］將每次補(bǔ)給量進(jìn)行優(yōu)化，在指定補(bǔ)給次數(shù)的前提下達(dá)到最低存儲(chǔ)成本。遺傳算法表述如下：

初始化種群數(shù)量為M，設(shè)定遺傳代數(shù)為D，各參數(shù)編碼長度為L。

編碼選擇。由于遺傳算法的隨機(jī)特性，使得二進(jìn)制編碼的搜索能力較差，又為了能方便交叉和變異操作，本文采用格雷碼的編碼方式。

假設(shè)有一個(gè)二進(jìn)制編碼為

其對應(yīng)的格雷碼為

格雷碼和二進(jìn)制碼轉(zhuǎn)換如下：

其中“⊕”表示異或運(yùn)算。

格雷碼中一個(gè)基因座的差別對應(yīng)的參數(shù)也只是微小的差別，這使得在最優(yōu)解附近，格雷碼能快速收斂到最優(yōu)解，從而提高遺傳算法的整體效率。采用隨機(jī)單點(diǎn)交叉［6］，交叉的概率 pc。格雷碼十分方便進(jìn)行基因變異，本文采用模擬生物基因變異過程中的單點(diǎn)變異［7］，變異概率為 pv。將儲(chǔ)存成本作為目標(biāo)函數(shù)。

優(yōu)化函數(shù)為儲(chǔ)存成本的倒數(shù)：

采用最為實(shí)用的輪盤賭比例選擇算子［8］，子代的數(shù)量仍為M。在每次選擇中，表現(xiàn)型越優(yōu)秀的父代被選擇成為子代的概率越大。

設(shè)定初始化種群數(shù)量為M=100，設(shè)定遺傳代數(shù)為D=500，各參數(shù)編碼長度為L=15，交叉概率 pc=0.3，變異概率 pv=0.03。程序流程圖如圖1所示。

圖1 程序流程圖

3.3 依據(jù)模型，給出方案

通過上述計(jì)算，各島礁的補(bǔ)給次數(shù)及每次物資補(bǔ)給量已經(jīng)通過遺傳算法尋優(yōu)得到，但所選用的艦船型號(hào)、艦船的補(bǔ)給路線還未確定，因而需要進(jìn)一步對模型進(jìn)行細(xì)化。通過分析島礁數(shù)據(jù)和艦船數(shù)據(jù)，一個(gè)較為初步的認(rèn)知可以很容易地建立［9～11］：

1）裝載量小的補(bǔ)給艦、燃油經(jīng)濟(jì)性適中，適合保障中遠(yuǎn)距離的中型規(guī)模島礁。

2）裝載量大的補(bǔ)給艦、燃油經(jīng)濟(jì)性差，適合保障近距離大型島嶼并為其它艦船提供物資保障。

3）拖船裝載量小、燃油經(jīng)濟(jì)性好，適合保障中小型島礁，但島礁區(qū)域的拖船數(shù)量會(huì)嚴(yán)重限制島礁的補(bǔ)給需求。

4）補(bǔ)給艦所擁有的補(bǔ)給小艇補(bǔ)給效率低，保障島礁時(shí)間長，同時(shí)需要補(bǔ)給艦開至距島礁1海里處，雖不考慮其燃油經(jīng)濟(jì)性，但需將補(bǔ)給艦的運(yùn)輸成本算入，隱含經(jīng)濟(jì)性差的涵義。

5）運(yùn)輸機(jī)效費(fèi)比極低，無特殊情況時(shí)無需使用。

接下來需要考慮的就是怎樣通過尋找最短路徑，挑選最經(jīng)濟(jì)適用的船進(jìn)行運(yùn)輸。最短路徑的選擇可以采用Dijkstra算法，比較容易實(shí)現(xiàn)，而運(yùn)輸工具的選擇上述推論可作參考，至此，便可形成一個(gè)完整的補(bǔ)給方案［12～13］。

4 結(jié)語

通過所建立的數(shù)學(xué)模型，一個(gè)較為嚴(yán)密的理論閉合已經(jīng)形成。首先，分析物資儲(chǔ)存模型，設(shè)計(jì)并實(shí)現(xiàn)遺傳算法進(jìn)行尋優(yōu)，得到了不同補(bǔ)給次數(shù)下的物資補(bǔ)給量；緊接著，綜合考慮不同補(bǔ)給次數(shù)下物資儲(chǔ)存成本與物資運(yùn)輸成本的總和，結(jié)合島礁自身儲(chǔ)存上限情況，得到了包含不同島礁之間補(bǔ)給次數(shù)、補(bǔ)給量在內(nèi)的補(bǔ)給方案；最后，考慮不同補(bǔ)給艦船的經(jīng)濟(jì)性和承載能力，通過最短路徑尋優(yōu)的方式，確定艦船補(bǔ)給路線，形成一個(gè)補(bǔ)給周期的島礁補(bǔ)給完整方案。