周柯雯，姚愛祥 （軍事交通學院，天津 300161）

基于遺傳算法和啟發(fā)策略的軍用物資飛機裝載優(yōu)化

周柯雯，姚愛祥 （軍事交通學院，天津 300161）

以軍用物資飛機裝載為研究對象，在考慮實際應用中的一些約束條件下，構造了軍用物資的裝載優(yōu)化模型，提出了一種基于啟發(fā)策略的遺傳算法。該算法考慮了裝載容積、裝載質量及裝載密度等約束條件。最后對一個案例進行了計算，驗證了該模型的有效性。

軍用物資；遺傳算法；啟發(fā)策略

0 引 言

航空軍事運輸，是軍隊利用運輸機和直升機等航空器，通過空中航線輸送人員、物資和裝備的一種運輸方式[1]。裝載，是航空軍事運輸實施的重要階段和環(huán)節(jié)。搞好飛機的裝載，對保證飛行安全，防止貨損貨差，充分利用飛機的載貨能力，提高裝卸效率和運輸經濟性，具有重要的意義。根據物資和載運工具的數量，裝載問題可以分為兩大類：一是載運工具足夠多，而待裝物資有限，要求使用的載運工具數目最少；二是載運工具有限，而待裝的物資遠遠超過現有裝載能力，要求充分利用容積和載重，使載運工具利用率最高。本文選取第二類問題為研究對象，建立相應的數學模型，設計實現高效的求解算法。

1 軍用物資飛機裝載問題的描述與建模

1.1 問題的描述

有若干件待運軍用物資，要求合理安排物資的組合，包括物資的裝載順序、裝載方向和裝載位置，使貨艙能裝入更多的物資。

在建立模型之前，作出如下規(guī)定： （1）軍用物資簡化為長方體，且?guī)缀沃行臑槠渲匦模?（2）物資及其包裝良好，可以支撐承重和多層裝載，且都運往同一個目的地； （3）不考慮前后貨艙重量對飛機平衡的影響，以及油重、溫度等對貨艙重量的制約； （4）必須橫裝火箭彈和已經安裝引信的炮彈，而其他軍用物資可以橫、順混裝。

軍用物資在飛機裝運時應保證：物資的頂部或四周與飛機內部結構之間的最小間隙不得小于150mm；對于貨艙中沒有過道的飛機，應設置應急通道，要求保持有一個最小凈空間，這個空間設置在順航向左側，其尺寸寬×高為355mm×1 830mm或762mm×1 220mm；對于有過道的飛機，在該通道上不能放置任何物資。

考慮到飛機的配重，實際擺放物資的順序是先擺放靠近空機重心的區(qū)域，后擺放靠近機頭或機尾的區(qū)域。

1.2 模型建立

設V為貨艙的最大可用容積，G為飛機的最大業(yè)載量，vi為待裝軍用物資i的體積，gi為待裝軍用物資i的重量，n為待裝軍用物資總數，m為裝入貨艙的軍用物資數量。

建立如下優(yōu)化模型：

式中：k1,k2,k3為權重系數，根據部隊執(zhí)行任務的具體情況，由經驗確定，且滿足k1,k2,k3＞0，k1+k2+k3=1。式 （6）為貨艙容積約束，即裝入貨艙的物資所占用的體積不能超過貨艙的最大可用容積；式 （7）為飛機業(yè)載量能力約束，即裝入貨艙的物資總質量不能超過飛機的最大業(yè)載量。

為了使所裝貨物的體積重量達到最優(yōu)，一方面，應該找出使貨物的平均密度最接近標準密度 （貨艙限重/貨艙體積）的組合；另一方面，要避免最接近標準密度的貨物組合的體積和重量遠低于貨艙的裝載能力的情況，即：貨物還沒有裝滿，它們的平均密度已經是最優(yōu)的了[2]。

2 基于遺傳算法和啟發(fā)策略的算法設計

遺傳算法是一種以自然選擇和遺傳理論為基礎，將生物進化過程中適者生存規(guī)則與同一群染色體的隨機信息變換機制相結合的搜索算法。通過給解向量編碼、形成初始群，然后用變異、交叉重組、自然選擇等算子，進行并行迭代，進而求得最優(yōu)解。

2.1 編碼與解碼

通常采用二進制編碼，把待裝軍用物資按一定的順序排列并編號，取串S={W1,W2,W3,W4,…,Wn}，其中Wi的取值是0或1，若Wi為1，則編號為i的軍用物資被裝載。若Wi為0，則不被裝載。例如，對一組貨物數為8的裝載問題，若某一裝載方案的編碼方式為S={1,0,1,1,0,0,1,1 } ，則解碼后對應的解碼方案：編號1、3、4、7、8的物資被順序裝載。

2.2 適應度函數

遺傳算法對一個解的好壞用適應度函數值的大小來評價，適應度的值越大，解的質量越好。為滿足實際應用需要，縮短算法的搜索時間，選擇適應度函數應遵循盡可能快的得到最優(yōu)解的原則。因此，本文采用適應度函數等于目標函數。

2.3 遺傳操作過程

2.3.1 初始種群的選取

一般的遺傳算法隨機選取多條染色體，然后依據適應度大小排序，取出適應度較大的作為初始種群。為了提高初始種群的質量，可以將幾種由啟發(fā)策略生成的染色體加入初始種群中。這些啟發(fā)策略包括：

（1）設ci為待裝的第i個軍用物資的價值，其價值密度為將所有待運物資價值密度的值按降序排列，然后依次將物資裝載，直至違反約束條件為止。

（2）從部隊所擔負的具體任務出發(fā)，根據對物資的需求程度不同，將物資按特需、急需、一般排序，然后依次裝載。（3）定義物資的價值空間密度為，將價值空間密度的值按降序排列，然后依次將物資裝載。這種策略兼顧了價值密度和承重約束[3]。

（5）除此之外，將一些已有的運輸方案作為優(yōu)勝染色體也加入初始種群。

其他初始種群的染色體則采取在不違反約束的條件下隨機生成。

2.3.2 選擇操作

一般采用輪盤賭、隨機遍歷抽樣、局部選擇法等進行選擇。這里同時使用比例選擇法和最優(yōu)保存策略[4]。按照輪盤賭方法選擇中間種群中適應度高的個體復制到下一代中，使用最優(yōu)保存策略進化模型 （Elitist Model），使當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來替換掉本代群體中經過交叉變異等遺傳操作后所產生的適應度最低的個體。這既能保證適應度較高的個體遺傳到下一代，又能保證有較高的全局收斂性。

2.3.3 交叉、變異操作以及倒位操作

交叉操作：本文采用雙點交叉的方式。雙點交叉是指在個體編碼串中隨機設置了兩個交叉點，然后再進行部分基因交換。

變異操作：為了在遺傳操作過程中保持群體的多樣性，避免算法早熟收斂甚至無法尋到全局最優(yōu)解，對個體采取變異操作。在 [ 1,n ] 之間按均勻分布隨機產生一個整數作為基因W1～Wn間的變異位，并將該位置基因值替換為相對應的整數0或1。

倒位操作：所謂倒位操作是指顛倒個體編碼串中隨機指定的二個基因座之間的基因排列順序，從而形成一個新的染色體。其目的主要是為了能夠使遺傳算法更有利于生成較好的模式。

2.4 算法步驟描述

（1）初始化進化計數代數t=0，最大進化代數為T

（2）按一定啟發(fā)策略產生初始種群

（3）以概率P1進行個體間的交叉操作

（4）以概率P2進行個體變異操作

（5）以概率P3進行個體倒位操作

（6）計算種群中個體適應值，并更新最優(yōu)個體

（7）按比例大小將適應度高的個體選擇到下一代

（8）進化T次后，停止計算，輸出此時的最好解作為所求得的最優(yōu)解

表1 軍用物資尺寸

應用本文提出的遺傳算法計算，各項初始參數取值分別為：群體規(guī)模n=80，最大進化代數T=200，交叉概率P1=0.9，變異概率P2=0.1，倒位概率P3=0.01。優(yōu)化裝載的結果為：A物資100箱，B物資130箱，C物資42箱，D物資5箱，共裝載277箱。飛機的總裝載質量為49 830kg，占最大業(yè)載量的99.7%；總裝載容積為169.68m3，空間利用率為99.8%；偏離標準密度值0.27，物資裝載后，其密度占標準密度的99.9%。為了防止軍用物資破損，在實際裝載過程中需要用木板、覆蓋物之類的材料來填補貨物之間的空隙。

3 應用舉例

設有如下軍用物資 （見表1）要裝入某型運輸機中 （見表2）。試確定充分利用運輸機運輸能力的合理裝載方案。

表2 某型運輸機主要參數

4 結束語

飛機貨艙的利用率，是貨物重量和體積共同作用的結果。貨艙的限重除以體積為貨艙標準密度，所裝貨物的平均密度越接近這個標準密度，效果越佳。

要搞好軍用物資飛機裝載作業(yè)，充分發(fā)揮航空運輸的優(yōu)勢，除了要有良好的運輸設備和裝載設備外，還應該提高飛機的利用率。采用基于啟發(fā)策略的遺傳算法對這類問題進行求解，方法簡單易行，其結果可為從事航空軍事運輸工作的單位和個人提供科學的決策依據，從而大大提高航空軍事運輸裝載工作的效率。

[1] 葛同民.航空軍事運輸[M].天津：軍事交通學院，2004.

[2] 張劼，衡紅軍，楊曉雪.航空貨運裝載問題算法設計與研究[J].計算機工程，2005(7):28-30.

[3] 徐賢勝，王帥.基于遺傳算法和啟發(fā)策略的艦船裝載方案[J].軍事運籌與系統工程，2008(6):40-44.

[4] 周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業(yè)出版社，1999.

Cargo-transport Plane Packing Optimization of Military Material Based on Genetic Algorithm and Developmental Strategy

ZHOU Ke-wen,YAO Ai-xiang (Academy of Military Transportation,Tianjin 300161,China)

This paper studies the problem of military material packing by cargo-transport plane.Considering multi-constraints in applications,an optimizing stowage model is set up,and a genetic algorithm based on developmental strategy is presented in this paper.The genetic algorithm takes account of loading capacity,loading mass,loading density and other constraints.Finally,the practical calculation shows the method is effective.

military material;genetic algorithm;developmental strategy

E234

A

1002-3100(2010)09-0122-03

2010-06-13

周柯雯（1985-），男，山東安丘人，軍事交通學院碩士研究生，研究方向：軍事運輸；姚愛祥（1983-），男，江蘇鹽城人，軍事交通學院軍事碩士研究生，研究方向：作戰(zhàn)后勤保障。