基于遺傳算法的遠海島礁補給模型研究*

李 東 滕 哲 張煒靈

（海軍大連艦艇學院 大連 116018）

1 引言

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

通常情況下，由后勤保障中心根據實際需求，以一個月為一個補給周期，制定補給方案，分別由不同型號的補給船和運輸機執行物資補給任務。補給船和運輸機都是從物資保障中心出發，為各島礁運送所需物資，回程運回垃圾及其他材料等。補給方案應當包括補給船（或運輸機）種類、補給路線、補給數量、轉運方式、物資裝卸與回收材料的數量等。

綜合考慮上述因素，本文建立了一個數學模型，嘗試給出一個補給周期的島礁物資補給方案。

2 模型基本假設

為了便于問題的研究，對題中某些條件進行合理假設：

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

2）所有補給船只、飛機及補給設備工作穩定，所有時間內均保持相同航行速度、補給速度。

3）島礁上需回收的固體不計儲存成本。

4）所有補給船只在補給時可以同時補給固體和液體。

5）一個補給周期（一月）時長為30天。

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

表1 模型中的物理量

3 方案建模

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

3.1 分塊處理，問題簡化

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

首先，針對補給的經濟情況進行建模。補給開銷主要分為島礁物資儲存成本和補給艦船運輸成本兩方面，設所有島礁的儲存成本總和為E儲，所有補給艦船的運輸成本總和為E運，補給方案的總開支為E總，則其關系可表示如下：

同樣地，可以對液體物資也列出類似公式、進行類似變換，綜合起來，可以得到總的島礁儲存成本表達式和單個島礁的儲存成本表達式：

從中可以明顯地看出，無論對島礁補充量如何，只要當補充量不為零時所對應的j越大（即補充時間越遲）時，所得島礁儲存成本越小。

綜上，物資儲存模型和物資運送模型已經建立，并且對物資儲存成本同補給時間的關系進行了探索，推導了補給時間點的一般通式，為下一步優化處理打下了基礎。

3.2 問題變換，優化參數

對于島礁而言，希望盡量能減少物資的儲存成本。基于補給時間關于每次補給量之間的關系，將尋求最優的存儲成本問題，轉變為尋求最合適的補給量，將問題轉化成了一個非線性優化問題。

在尋優問題中，利用了格雷碼的遺傳算法［4～5］將每次補給量進行優化，在指定補給次數的前提下達到最低存儲成本。遺傳算法表述如下：

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

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

假設有一個二進制編碼為

其對應的格雷碼為

格雷碼和二進制碼轉換如下：

其中“⊕”表示異或運算。

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

優化函數為儲存成本的倒數：

采用最為實用的輪盤賭比例選擇算子［8］，子代的數量仍為M。在每次選擇中，表現型越優秀的父代被選擇成為子代的概率越大。

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

圖1 程序流程圖

3.3 依據模型，給出方案

通過上述計算，各島礁的補給次數及每次物資補給量已經通過遺傳算法尋優得到，但所選用的艦船型號、艦船的補給路線還未確定，因而需要進一步對模型進行細化。通過分析島礁數據和艦船數據，一個較為初步的認知可以很容易地建立［9～11］：

1）裝載量小的補給艦、燃油經濟性適中，適合保障中遠距離的中型規模島礁。

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

3）拖船裝載量小、燃油經濟性好，適合保障中小型島礁，但島礁區域的拖船數量會嚴重限制島礁的補給需求。

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

5）運輸機效費比極低，無特殊情況時無需使用。

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

4 結語

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