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

周柯雯，姚愛(ài)祥 （軍事交通學(xué)院，天津 300161）

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

周柯雯，姚愛(ài)祥 （軍事交通學(xué)院，天津 300161）

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

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

0 引 言

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

1 軍用物資飛機(jī)裝載問(wèn)題的描述與建模

1.1 問(wèn)題的描述

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

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

軍用物資在飛機(jī)裝運(yùn)時(shí)應(yīng)保證：物資的頂部或四周與飛機(jī)內(nèi)部結(jié)構(gòu)之間的最小間隙不得小于150mm；對(duì)于貨艙中沒(méi)有過(guò)道的飛機(jī)，應(yīng)設(shè)置應(yīng)急通道，要求保持有一個(gè)最小凈空間，這個(gè)空間設(shè)置在順航向左側(cè)，其尺寸寬×高為355mm×1 830mm或762mm×1 220mm；對(duì)于有過(guò)道的飛機(jī)，在該通道上不能放置任何物資。

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

1.2 模型建立

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

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

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

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

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

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

2.1 編碼與解碼

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

2.2 適應(yīng)度函數(shù)

遺傳算法對(duì)一個(gè)解的好壞用適應(yīng)度函數(shù)值的大小來(lái)評(píng)價(jià)，適應(yīng)度的值越大，解的質(zhì)量越好。為滿足實(shí)際應(yīng)用需要，縮短算法的搜索時(shí)間，選擇適應(yīng)度函數(shù)應(yīng)遵循盡可能快的得到最優(yōu)解的原則。因此，本文采用適應(yīng)度函數(shù)等于目標(biāo)函數(shù)。

2.3 遺傳操作過(guò)程

2.3.1 初始種群的選取

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

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

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

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

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

2.3.2 選擇操作

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

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

交叉操作：本文采用雙點(diǎn)交叉的方式。雙點(diǎn)交叉是指在個(gè)體編碼串中隨機(jī)設(shè)置了兩個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換。

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

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

2.4 算法步驟描述

（1）初始化進(jìn)化計(jì)數(shù)代數(shù)t=0，最大進(jìn)化代數(shù)為T(mén)

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

（3）以概率P1進(jìn)行個(gè)體間的交叉操作

（4）以概率P2進(jìn)行個(gè)體變異操作

（5）以概率P3進(jìn)行個(gè)體倒位操作

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

（7）按比例大小將適應(yīng)度高的個(gè)體選擇到下一代

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

表1 軍用物資尺寸

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

3 應(yīng)用舉例

設(shè)有如下軍用物資 （見(jiàn)表1）要裝入某型運(yùn)輸機(jī)中 （見(jiàn)表2）。試確定充分利用運(yùn)輸機(jī)運(yùn)輸能力的合理裝載方案。

表2 某型運(yùn)輸機(jī)主要參數(shù)

4 結(jié)束語(yǔ)

飛機(jī)貨艙的利用率，是貨物重量和體積共同作用的結(jié)果。貨艙的限重除以體積為貨艙標(biāo)準(zhǔn)密度，所裝貨物的平均密度越接近這個(gè)標(biāo)準(zhǔn)密度，效果越佳。

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

[1] 葛同民.航空軍事運(yùn)輸[M].天津：軍事交通學(xué)院，2004.

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

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

[4] 周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(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-），男，山東安丘人，軍事交通學(xué)院碩士研究生，研究方向：軍事運(yùn)輸；姚愛(ài)祥（1983-），男，江蘇鹽城人，軍事交通學(xué)院軍事碩士研究生，研究方向：作戰(zhàn)后勤保障。