基于遺傳算法艦船裝載碼頭配置方案優(yōu)化

徐清華，季大琴，英戈

（海軍陸戰(zhàn)學(xué)院，廣州510430）

基于遺傳算法艦船裝載碼頭配置方案優(yōu)化

徐清華，季大琴，英戈

（海軍陸戰(zhàn)學(xué)院，廣州510430）

兩棲輸送艦船碼頭裝載過(guò)程中，如何科學(xué)配置裝載碼頭，使得整個(gè)裝載任務(wù)完成時(shí)間最短是部隊(duì)制定裝載方案需要解決的重要難題。依據(jù)碼頭裝載配置特點(diǎn)和要求，運(yùn)用軍事運(yùn)籌學(xué)多目標(biāo)規(guī)劃理論構(gòu)建裝載碼頭配置規(guī)劃模型，并運(yùn)用遺傳算法理論和計(jì)算機(jī)編程工具實(shí)現(xiàn)碼頭配置規(guī)劃模型的優(yōu)化解算。從而提高了部隊(duì)兩棲輸送艦船碼頭裝載方案制定的科學(xué)性和時(shí)效性。

遺傳算法，裝載，碼頭配置，方案

0 引言

兩棲輸送艦船裝載是兩棲作戰(zhàn)準(zhǔn)備的關(guān)鍵環(huán)節(jié)，是完成兩棲作戰(zhàn)任務(wù)的首要。碼頭裝載依靠其健全的港口裝載設(shè)施成為兩棲輸送艦船裝載方式的首選。兩棲輸送艦船碼頭裝載過(guò)程中，如何科學(xué)配置裝載碼頭，使得整個(gè)裝載任務(wù)完成時(shí)間最短是部隊(duì)制定裝載方案需要解決的重要難題。

1 兩棲輸送艦船裝載碼頭配置方案優(yōu)化模型構(gòu)建

在組織較大規(guī)模兩棲作戰(zhàn)裝載任務(wù)時(shí)，通常涉及的兩棲艦船類(lèi)型、數(shù)量較多，選擇的裝載碼頭類(lèi)型、數(shù)量較多，裝載裝備的類(lèi)型、數(shù)量較多。而這些涉及因素都直接影響兩棲作戰(zhàn)裝載任務(wù)完成的效率。通過(guò)構(gòu)建碼頭配置方案優(yōu)化模型，使得整個(gè)裝載任務(wù)完成時(shí)間最短，是提高部隊(duì)兩棲作戰(zhàn)裝載任務(wù)效率的有力方法。

1.1 兩棲輸送艦船及裝載碼頭分類(lèi)

為了提高模型構(gòu)建的通用性，現(xiàn)將兩棲輸送艦船和裝載碼頭進(jìn)行分類(lèi)。兩棲輸送艦船按照排水量和功能特點(diǎn)可劃分為大型登陸艦艇、中型登陸艦艇、小型登陸艦艇及特種兩棲輸送艦艇等4種類(lèi)型；裝載碼頭按照其使用功能劃分為大、中、小型登陸碼頭（指能夠?yàn)殛憫?zhàn)裝備通過(guò)斜坡、跳板直接機(jī)動(dòng)上落艦的碼頭），大、中、小型普通碼頭（指能夠提供吊裝功能的普通民用碼頭）和大、中、小型可供兩棲裝備泛水裝載碼頭［1］。

1.2 兩棲輸送艦船裝載碼頭配置條件

兩棲輸送艦船配置裝載碼頭時(shí)應(yīng)遵循以下條件:大型登陸艦艇只能配置在大型碼頭裝載，不適合在中、小型碼頭裝載；中型登陸艦艇只能配置在大型碼頭或中型碼頭裝載，不適合在小型碼頭裝載；小型登陸艦艇可以配置在大、中、小型碼頭裝載。另外，規(guī)定一座碼頭同一時(shí)間內(nèi)只能容納1艘艦船進(jìn)行裝載。

1.3 兩棲輸送艦船裝載碼頭配置方案需求描述

設(shè)完成某兩棲作戰(zhàn)任務(wù)所需兩棲輸送艦艇的類(lèi)型和數(shù)量如表1所示，所需兩棲艦船總數(shù)為A= {A1，A2，A3}，其中A1，A2，A3分別為大型、中型、小型登陸艦艇數(shù)量，某港可用于兩棲輸送艦船裝載的碼頭總數(shù)為X={X1，X2，X3，X4，X5，X6，X7，X8，X9}，如表2所示，其中X1，X2，X3分別為大、中、小型登陸碼頭（M1、M2、M3）的數(shù)量，X4，X5，X6分別為大、中、小型普通碼頭（M4、M5、M6）的數(shù)量，X7，X8，X9為大、中、小型可供兩棲裝備泛水裝載碼頭（M1、M2、M3）的數(shù)量。各型登陸艦艇配置給相應(yīng)碼頭數(shù)量為{X11，X12，X13，X21，X22，X23，X24，X25，X26，X31，X32，X33，X34，X35，X36，X37，X38，X39}，如圖1所示，其中，大型登陸艦艇配置給大型碼頭數(shù)量分別為X11，X12，X13，中型登陸艦艇配置給大、中型碼頭數(shù)量分別為X21，X22，X23，X24，X25，X26，小型登陸艦艇配置給大、中、小型碼頭數(shù)量分別為X31，X32，X33，X34，X35，X36，X37，X38，X39。每艘艦艇分配相應(yīng)碼頭裝載時(shí)間為t11，t12，t13，t21，t22，t23，t24，t25，t26，t31，t32，t33，t34，t35，t36，t37，t38，t39，各型碼頭完成裝載任務(wù)所需要的時(shí)間為T(mén)X1，TX2，TX3，TX4，TX5，TX6，TX7，TX8，TX9。合理規(guī)劃碼頭配置方案{X11，X12，X13，X21，X22，X23，X24，X25，X26，X31，X32，X33，X34，X35，X36，X37，X38，X39}，并計(jì)算完成整個(gè)兩棲輸送艦船裝載任務(wù)最短時(shí)間。

表1 兩棲輸送艦船兵力投送需求數(shù)量

1.4 裝載碼頭配置方案模型構(gòu)建

依據(jù)兩棲輸送艦船裝載碼頭配置條件，運(yùn)用軍事運(yùn)籌學(xué)多目標(biāo)規(guī)劃理論構(gòu)建裝載碼頭配置方案模型。

表2 某港裝載碼頭建設(shè)配置情況

圖1 艦艇裝載碼頭配置方案示意圖

①已知

2 基于遺傳算法裝載碼頭配置方案優(yōu)化模型解算

兩棲輸送艦船裝載碼頭配置優(yōu)化所要解決的是配置方案能夠?qū)崿F(xiàn)整體裝載時(shí)間最短問(wèn)題，屬于多目標(biāo)規(guī)劃問(wèn)題。由于遺傳算法（GA）在解算多目標(biāo)規(guī)劃問(wèn)題過(guò)程中，不受問(wèn)題求解空間的限制，不必對(duì)求解問(wèn)題作出連續(xù)性、導(dǎo)數(shù)存在和單峰等假設(shè)，在裝載碼頭配置方案搜索進(jìn)化過(guò)程中基本上不需要外部信息，僅用評(píng)估函數(shù)即適應(yīng)值函數(shù)來(lái)評(píng)價(jià)種群中個(gè)體的優(yōu)劣，并作為優(yōu)勝劣汰遺傳操作的依據(jù)，加上遺傳算法本身固有的并行性，使得遺傳算法在裝載碼頭配置方案優(yōu)化求解方面具有較強(qiáng)的優(yōu)越性［2-3］。因此，本文采用遺傳算法求解裝載碼頭配置方案優(yōu)化問(wèn)題。

2.1 問(wèn)題編碼（構(gòu)造染色體）

根據(jù)裝載碼頭配置方案規(guī)劃約束條件，配置給各個(gè)碼頭的艦艇數(shù)量為正整數(shù)，且一種方案中的配置數(shù)為18種，因此，采用非負(fù)整數(shù)進(jìn)行編碼比較合適，一個(gè)個(gè)體代表一種配置方案，其個(gè)體編碼為xijk（i=1，2，3，…，18，j=1，2，3，…，M）。xijk表示第k代種群第j個(gè)個(gè)體中的第i段基因編碼值，M為種群數(shù)。

2.2 初始種群設(shè)定

在裝載碼頭配置方案中，配置最少為0艘艦艇，最多A1，A2，A3為艘艦艇，因此，可初始化種群如圖3所示。即，大中小型艦艇在編碼過(guò)程是相對(duì)獨(dú)立，每段染色體第1至n-2為0，第n-1個(gè)染色體為1，最后一個(gè)染色體為Ai-1。

圖2 裝載碼頭配置方案問(wèn)題編碼

圖3 裝載碼頭配置方案種群初始化

2.3 適應(yīng)值函數(shù)設(shè)計(jì)

遺傳算法在搜索進(jìn)化過(guò)程中一般不需要其他外部信息，僅用評(píng)估函數(shù)來(lái)評(píng)估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。評(píng)估函數(shù)又稱(chēng)適應(yīng)值（fitness）。適應(yīng)值函數(shù)是根據(jù)目標(biāo)函數(shù)確定的，其值總是非負(fù)數(shù)，且越大越好［4］。

2.4 遺傳操作設(shè)計(jì)

遺傳算法的執(zhí)行過(guò)程中，每一代有許多不同的染色體（個(gè)體）同時(shí)存在，這些染色體中哪個(gè)保留（生存），哪個(gè)淘汰（死亡）是根據(jù)它們對(duì)環(huán)境的適應(yīng)能力決定的，適應(yīng)性強(qiáng)的有更多的機(jī)會(huì)保留下來(lái)，主要的遺傳操作有選擇、交叉和變異。

2.4.1 選擇操作

選擇又稱(chēng)復(fù)制、繁殖。選擇是從種群中選擇生命力強(qiáng)的染色體產(chǎn)生新種群的過(guò)程。依據(jù)每個(gè)染色體的適應(yīng)值大小，適應(yīng)值越大，被選擇的概率就越大，其子孫在下一代產(chǎn)生的個(gè)數(shù)就越多［5］。

根據(jù)裝載碼頭配置方案規(guī)劃的需要，采取排序選擇方法比較適合研究的需要，排序選擇方法是指在計(jì)算每個(gè)個(gè)體的適應(yīng)值后，根據(jù)適應(yīng)值的大小順序?qū)θ后w中個(gè)體排序，按線(xiàn)性排序計(jì)算個(gè)體的適應(yīng)度，再采用輪盤(pán)賭選擇方式選擇復(fù)制個(gè)體，同時(shí)為了保存優(yōu)良個(gè)體加快算法的收斂，采用精英保存策略，將當(dāng)代種群中的最優(yōu)個(gè)體直接復(fù)制至下一代。

設(shè)種群大小為M，個(gè)體j的適應(yīng)值為fj，則j個(gè)體被選擇的概率psj為:

2.4.2 交叉操作

交叉又稱(chēng)重組、配對(duì)。當(dāng)許多染色體相同或者后代的染色體與上一代沒(méi)有多大差別時(shí)，可通過(guò)染色體重組來(lái)產(chǎn)生新一代染色體。染色體重組分兩步進(jìn)行，首先在新復(fù)制的群體中隨機(jī)選取兩個(gè)個(gè)體，交叉算子采用擴(kuò)展整體算術(shù)雜交算子。如對(duì)個(gè)體Xijk和Xγjk執(zhí)行擴(kuò)展整體算術(shù)雜交操作。課題中的個(gè)體要求同一段染色體總和為定值A(chǔ)1，A2，A3，因此，采用同一個(gè)體同一段染色體之間的編碼值進(jìn)行交叉，保證產(chǎn)生新染色體依然滿(mǎn)足約束條件，如圖4所示。

圖4 裝載碼頭配置方案基因交叉操作

2.4.3 變異操作

選擇和交叉操作基本完成了遺傳算法的大部分搜索功能，而變異則增加了遺傳算法找到接近最優(yōu)解的能力。變異就是以很小的概率，隨機(jī)地改變基因值，變異發(fā)生的概率pm一般都取很?。ㄒ话阍?.001～0.1之間）。當(dāng)選定某個(gè)染色體變異操作時(shí)，即這個(gè)染色體基因加1操作，同時(shí)在同一段染色體中另一基因作減1操作，如果另一基因值小于1，則終止此次變異操作。對(duì)個(gè)體xijk執(zhí)行變異操作，如圖5所示。

圖5 裝載碼頭配置方案基因變異操作

2.5 控制參數(shù)的設(shè)定

控制參數(shù)的設(shè)定主要指群體的大小和使用遺傳算法操作的概率，針對(duì)裝載配置方案可取交叉概率為0.9，變異概率為0.1，種群規(guī)模為N=100。利用計(jì)算機(jī)編程即可實(shí)現(xiàn)解算最優(yōu)結(jié)果。

2.6 遺傳算法解算流程圖

根據(jù)以上遺傳算法求解步驟，可制定遺傳算法解算流程圖，如圖6所示。

圖6 遺傳算法解算流程圖

3 算例分析

3.1 基本想定

為實(shí)現(xiàn)某兩棲作戰(zhàn)任務(wù)需要兩棲艦船數(shù)量為A型艦8艘、C型艦6艘、E型艦3艘?，F(xiàn)要求最短時(shí)間內(nèi)在某港2座M1登陸碼頭、2座M4普通碼頭、1座可供兩棲裝備泛水裝載的M8碼頭完成以上裝載任務(wù)，計(jì)算此次裝載任務(wù)的碼頭配置方案。兩棲艦艇裝載數(shù)量及碼頭裝載參數(shù)如表3、表4所示。

表3 兩棲艦船裝載數(shù)量

3.2 碼頭配置模型構(gòu)建

如圖7所示，實(shí)線(xiàn)表示可裝載的碼頭和艦艇，虛線(xiàn)表示不存在裝載的碼頭和艦艇。

表4 某港碼頭裝載能力性能參數(shù)表

圖7 艦艇裝載碼頭配置方案圖

3.2.1 已知

3.2.2 設(shè)定

即

3.2.3 求解

圖8 裝載碼頭配置方案種群初始化

3.3 運(yùn)用遺傳算法解優(yōu)化模型

3.3.1 初始種群設(shè)定

3.3.2 適應(yīng)值函數(shù)設(shè)計(jì)

3.3.3 遺傳操作實(shí)現(xiàn)

①利用計(jì)算機(jī)編程將以上模型進(jìn)行解算可得優(yōu)化方案為:

圖9 兩棲艦船裝載碼頭配置方案優(yōu)化解算界面

4 結(jié)論

裝載碼頭配置是部隊(duì)制定裝載方案的一項(xiàng)重要工作，本文運(yùn)用軍事運(yùn)籌學(xué)多目標(biāo)規(guī)劃和遺傳算法理論構(gòu)建裝載碼頭配置方案優(yōu)化模型，有效解決了碼頭配置優(yōu)化問(wèn)題，提高了部隊(duì)裝載方案制定的科學(xué)性和時(shí)效性。該模型算法可以擴(kuò)展運(yùn)用到大規(guī)模登陸作戰(zhàn)中兩棲輸送艦船同時(shí)采用碼頭裝載、抵灘裝載、泛水裝載時(shí)，多種上船點(diǎn)的優(yōu)化配置問(wèn)題。但裝載配置問(wèn)題是典型的NP問(wèn)題，隨著裝載艦船、上船點(diǎn)種類(lèi)及數(shù)量的增加，優(yōu)化搜索的計(jì)算量迅速增長(zhǎng)，算法效率必然會(huì)下降。因此，必須進(jìn)一步改進(jìn)算法，提高算法的效率。

表5 兩棲艦船裝載碼頭配置優(yōu)化方案

［1］冷畫(huà)屏，徐清華.大型兩棲艦艇編隊(duì)陸戰(zhàn)兵力裝卸載方案及流程研究［M］.廣州:海軍陸戰(zhàn)學(xué)院，2015:20-21.

［2］周智超，劉鋼，徐清華.反艦導(dǎo)彈航路規(guī)劃理論與應(yīng)用［M］.北京:國(guó)防工業(yè)出版社，2015:132-133.

［3］陳文偉，周智超.海軍軍事數(shù)據(jù)挖掘技術(shù)［M］.北京:海潮出版社，2002.

［4］徐清華，李中良.基于遺傳算法反艦導(dǎo)彈航路規(guī)劃研究［J］.火力與指揮控制，2008，33（增刊）:60-61.

［5］王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2003.

Research on Project Optimization of Ship Loading Berth Allocation Based on Genetic Algorithm

XU Qing-hua，JI Da-qin，YING Ge
（Naval Marine Academy，Guangzhou 510430，China）

It is a key problem for the navy to make a plan during the ship loading phase，taking advantages of scientific berth allocation to make the ship loading as quickly as possible.In accordance with the characteristics and requirements of berth allocation during ship loading，the thesis applies the multi-objective programming theory of operational research to construct a loading berth allocation model，genetic algorithm theory and computer programming to work out the optimal solution to berth allocation plan model，to improve the scientificity and timeliness of the plan on berth allocation for the navy amphibious transport forces.

genetic algorithm，ship loading，berth allocation，project

E917

A

1002-0640（2017）04-0171-06

2016-02-18

2016-04-24

徐清華（1980-）男，江西鄱陽(yáng)人，碩士，副教授。研究方向：兵種戰(zhàn)術(shù)。