基于差分進(jìn)化算法的運(yùn)輸直升機(jī)人員裝載問題

田 野，田衛(wèi)萍，李文龍，范文超

（北方自動(dòng)控制技術(shù)研究所，太原 030006；2.駐太原地區(qū)第二軍代室，太原 030006）

0 引言

直升機(jī)因其具有靈活的機(jī)動(dòng)性、低空隱蔽性等特點(diǎn)，逐漸成為現(xiàn)代戰(zhàn)爭(zhēng)中不可缺少的作戰(zhàn)力量，空中機(jī)降作戰(zhàn)隨之成為一種重要作戰(zhàn)方式。因此，依據(jù)作戰(zhàn)任務(wù)和作戰(zhàn)人員乘載原則，快速地生成合理有效的運(yùn)輸直升機(jī)乘載人員分配方案，對(duì)于提高作戰(zhàn)效率、減少直升機(jī)資源浪費(fèi)、節(jié)省時(shí)間成本具有重要作用。

運(yùn)輸直升機(jī)人員裝載問題實(shí)質(zhì)是一個(gè)離散空間的多約束組合優(yōu)化問題，同時(shí)也是典型的NP 問題［1］。當(dāng)前，對(duì)此類問題的求解方法可分為以線性規(guī)劃為代表的傳統(tǒng)算法，和以遺傳算法為代表的智能優(yōu)化算法［2-5］兩類。傳統(tǒng)算法求解效果精確，但大規(guī)模的組合優(yōu)化問題受限于計(jì)算量，求解速度較慢，效率較低。相較之下，智能優(yōu)化算法通過不同的搜索策略和優(yōu)化搜索機(jī)制，可以較快地處理大規(guī)模數(shù)據(jù)并得到較優(yōu)的解。智能優(yōu)化算法已逐漸成為求解復(fù)雜組合優(yōu)化問題主要的有效方式。

為了實(shí)現(xiàn)對(duì)直升機(jī)資源高效的使用，減少資源浪費(fèi)，本文在滿足裝載原則的前提下，建立了以直升機(jī)空間利用率最大化為目標(biāo)的人員裝載模型，并提出一種動(dòng)態(tài)的差分進(jìn)化算法對(duì)該模型進(jìn)行求解。

1 運(yùn)輸直升機(jī)人員裝載問題

1.1 問題描述

運(yùn)輸直升機(jī)人員裝載問題的核心是在現(xiàn)有運(yùn)輸直升機(jī)資源有限的情況下，滿足作戰(zhàn)人員直升機(jī)裝載原則的前提下，以盡可能高的空間利用率和盡可能少的直升機(jī)完成作戰(zhàn)人員的分配裝載。

其中，裝載原則如下：作戰(zhàn)人員直升機(jī)裝載分配過程中，應(yīng)盡量保持戰(zhàn)斗編組和建制的完整性，保證乘機(jī)人員機(jī)降后保持一定戰(zhàn)斗力；多位指揮員不搭乘同一架直升機(jī)，避免指揮員傷亡造成部隊(duì)?wèi)?zhàn)斗力大幅下降。

同時(shí)，作戰(zhàn)人員裝載分配過程中受到可用直升機(jī)的機(jī)型、數(shù)量、不同機(jī)型直升機(jī)的容量（座次）和可承載重量等約束的限制，而直升機(jī)的容量和可承載人員重量又與實(shí)際作戰(zhàn)半徑（是否需掛載副油箱）等因素有關(guān)。如何處理約束條件和裝載原則是求解直升機(jī)人員裝載問題的重要部分。

1.2 數(shù)學(xué)模型

設(shè)有k 種不同機(jī)型的運(yùn)輸直升機(jī)，第i 種機(jī)型直升機(jī)最大可用數(shù)量為ni（i=1，2，…，k），該型直升機(jī)在作戰(zhàn)距離為s 時(shí)，最大人員容量為，可承載人員重量為。

設(shè)有t 個(gè)待乘機(jī)建制班，為保證乘機(jī)人員戰(zhàn)斗力，以作戰(zhàn)小組為基本登機(jī)單位，將t 個(gè)建制班分為m 個(gè)具有獨(dú)立作戰(zhàn)能力的作戰(zhàn)小組（指揮員單人成組），第h（h=1，2，…，m）個(gè)作戰(zhàn)小組的人數(shù)為Nh，人員及攜帶裝備重量為wh。

假設(shè)直升機(jī)作戰(zhàn)距離一定，針對(duì)單波次運(yùn)輸直升機(jī)人員裝載問題，基于最大的直升機(jī)空間利用率建立如下數(shù)學(xué)模型：

1）目標(biāo)函數(shù)

該式表示所使用直升機(jī)的空間利用率。其中，numi表示最終裝載方案所使用的第i 型直升機(jī)數(shù)量。

2）約束條件

直升機(jī)數(shù)量約束：

容量約束：

載重量約束：

裝載原則約束：

其中，xijh= {0，1}，xijh=1 時(shí)，表示第h 個(gè)小組乘坐第i型機(jī)中的第j（j=1，2，…，ni）架直升機(jī)，ph為指揮員標(biāo)志，取值范圍為{0，1}，ph=1 時(shí)，表示第h 個(gè)小組為指揮員。

2 差分進(jìn)化算法

2.1 算法描述

本文求解直升機(jī)人員裝載問題采用的差分進(jìn)化算法主要思想如下：隨機(jī)生成初始種群，將種群中任意兩個(gè)個(gè)體的向量差與第3 個(gè)個(gè)體求和產(chǎn)生變異個(gè)體；變異個(gè)體與父代個(gè)體交叉重組產(chǎn)生子代個(gè)體；對(duì)子代個(gè)體與父代個(gè)體間進(jìn)行選擇操作，將適應(yīng)度更高的個(gè)體保留下來(lái)；不斷進(jìn)化迭代保留優(yōu)良個(gè)體，逐漸逼近最優(yōu)解。

本文提出的動(dòng)態(tài)差分進(jìn)化算法具體流程如下頁(yè)算法1 所示。

2.2 編碼設(shè)計(jì)

首先，對(duì)可用的k 種機(jī)型直升機(jī)依據(jù)型號(hào)數(shù)量按順序編號(hào)。其次，采用整數(shù)編碼方式對(duì)解方案進(jìn)行描述：染色體上的每一位基因代表一個(gè)作戰(zhàn)小組，該基因位的數(shù)值代表該作戰(zhàn)小組搭乘的直升機(jī)編號(hào)，如圖1 所示。這種編碼方式與實(shí)際問題比較切合，直觀易懂，同時(shí)滿足直升機(jī)數(shù)量約束，見式（2）。

圖1 編碼方案

算法1 差分法進(jìn)化算法Input：Population：pop；Dimension：n；Generation：T Output：The best solution：Δ 1.t←1（initialization）2.while（t≤T）or（f（Δ）is not same in l generation continuously）do 3. if f（Δ）is the same in h generatiaon continuously and f（Δ）≤fo then 4.F=F+rand（0，1）5. Cr=Cr-rand（0，Cr）6.end 7. （Mutation and Crossover）8.for i=1 to pop do 9.for j=1 to n do 10. vi，j t+1=Mutation（xi，j t ）11.ui，j t+1=Crossover（vi，j t+1，xi，j t ）12.end 13.（One to One Survival Selection）14.if f（ui t+1）＞f（xi t）then 15.Δ ←ui t+1 16.else 17.Δ ←xi t 18.end 19.end 20. t←t+1 21. end 22. return the best solution Δ；

2.3 約束處理

現(xiàn)有的啟發(fā)式算法多用懲罰策略、競(jìng)賽選擇機(jī)制、基因修復(fù)策略［2］等方法對(duì)約束進(jìn)行處理。其中，懲罰策略和基因修復(fù)策略對(duì)可行域大小要求較高，當(dāng)初始種群中可行解較少甚至毫無(wú)可行解時(shí)，這兩種策略作用都不明顯。

相較來(lái)說，競(jìng)賽選擇機(jī)制對(duì)初始種群個(gè)體是否可行要求較低，更適合處理人員分配問題求解時(shí)隨機(jī)生成的初始種群可行解較少的情況。因此，本文采用競(jìng)賽選擇機(jī)制處理約束：

1）如式（6）所示創(chuàng)建違反約束程度矩陣CV。

該矩陣中，列表示直升機(jī)裝載狀態(tài)，行表示該行所對(duì)應(yīng)的種群個(gè)體違反約束程度，若CV 中存在元素cvij≥0，則表示該種群第i 個(gè)個(gè)體對(duì)應(yīng)的解方案違反約束，為不可行解。若CV 第i 行元素皆小于0，表明該行對(duì)應(yīng)個(gè)體為可行解，且CV 中的元素越接近于0，該方案對(duì)直升機(jī)利用率越高。

2）依據(jù)違反約束程度矩陣和種群目標(biāo)函數(shù)矩陣（ObjV）來(lái)計(jì)算種群適應(yīng)度（fitness），具體處理原則如下：滿足約束個(gè)體的適應(yīng)度高于違反約束個(gè)體的適應(yīng)度；對(duì)于滿足約束的個(gè)體，目標(biāo)函數(shù)值越大，適應(yīng)度越高；對(duì)于不滿足約束的個(gè)體，違反約束程度越低，適應(yīng)度越高。

這種約束處理方法保證了可行解對(duì)于非可行解的絕對(duì)優(yōu)勢(shì)，引導(dǎo)進(jìn)化向可行方向進(jìn)行，對(duì)不可行解的溫和處理在一定程度上保持了種群的多樣性。

2.4 參數(shù)處理

差分進(jìn)化算法（DE）的控制參數(shù)包括種群規(guī)模（NP）、交叉概率（Cr，Cr∈［0，1］）和差分權(quán)重（F）［8］。NP 反映種群信息量大??；Cr反映父代個(gè)體與實(shí)驗(yàn)個(gè)體交叉重組過程中信息交換程度，通常取值范圍為Cr∈［0，1］：F 決定差分向量的放大比例，反映算法的全局尋優(yōu)能力，通常取值范圍為F∈（0，2）。F和Cr兩個(gè)參數(shù)決定著整個(gè)算法的搜索效率。

為保證較少的計(jì)算量和較低算法時(shí)間代價(jià)，本文提出的算法在較小的種群規(guī)?；A(chǔ)上調(diào)整參數(shù)Cr和F 來(lái)改進(jìn)算法性能。同時(shí)，為保證實(shí)際工程中的求解質(zhì)量，本文在算法中加入預(yù)設(shè)個(gè)體適應(yīng)度f(wàn)0，通過對(duì)待乘機(jī)人員和直升機(jī)數(shù)量性能的初步估算，給出預(yù)設(shè)個(gè)體適應(yīng)度f(wàn)0（即預(yù)設(shè)目標(biāo)函數(shù)）。具體處理方式如下：在給定初始參數(shù)Crinit和Finit的情況下，當(dāng)進(jìn)化過程中連續(xù)h 代種群最優(yōu)個(gè)體適應(yīng)度停滯在某一值不變時(shí)，且種群最優(yōu)個(gè)體適應(yīng)度小于預(yù)設(shè)個(gè)體適應(yīng)度f(wàn)0時(shí)，認(rèn)為算法陷入局部最優(yōu)解，此時(shí)應(yīng)調(diào)整參數(shù)提高種群多樣性，即增大差分權(quán)重F 的值（F=F+rand（0，1）），提高全局尋優(yōu)能力，促使算法跳出局部最優(yōu)解；同時(shí)，為避免差分權(quán)重F 增大導(dǎo)致算法局部搜索能力變差的風(fēng)險(xiǎn)，減小交叉概率Cr的值進(jìn)行平衡（Cr=Cr-rand（0，Cr）），保證一定的局部搜索能力。

這種控制參數(shù)隨進(jìn)化代數(shù)和種群最優(yōu)適應(yīng)度變化的動(dòng)態(tài)參數(shù)處理方式，可以有效地改善傳統(tǒng)差分進(jìn)化算法進(jìn)化過程中易產(chǎn)生的陷入局部最優(yōu)、早熟等缺點(diǎn)，有效平衡了算法的全局搜索能力和局部搜索能力。

2.5 迭代過程

2.5.1 變異策略

本文采用的動(dòng)態(tài)精英變異策略如下頁(yè)圖2 所示。變異的基礎(chǔ)是差分向量，即個(gè)體通過與種群中個(gè)體間的差異作矢量和進(jìn)行變異。種群初始進(jìn)化時(shí)，個(gè)體間差異較大，變異范圍更廣泛，全局搜索能力更強(qiáng)。隨著進(jìn)化代數(shù)增加，種群趨向某個(gè)極值進(jìn)化，個(gè)體間差異變小變異被局限在某個(gè)范圍，種群多樣性銳減，搜索將陷入停滯進(jìn)入早熟狀態(tài)。此時(shí)由圖2 可以看出，上調(diào)參數(shù)F 可以擴(kuò)展個(gè)體的變異范圍，算法搜索范圍變大，跳出局部極值。

圖2 差分變異策略

這種變異策略選取精英個(gè)體作為基向量，在可行精英解附近域進(jìn)行變異，有利于進(jìn)化向最優(yōu)解方向發(fā)展。而動(dòng)態(tài)的差分權(quán)重參數(shù)使得種群多樣性不隨進(jìn)化過程銳減，始終保持一定的種群多樣性，保證算法不陷入早熟。

2.5.2 交叉策略

圖3 交叉策略

差分進(jìn)化算法常用的交叉方式分為兩種（如圖3）：二項(xiàng)式交叉和指數(shù)交叉［10］。其中，二項(xiàng)式交叉是針對(duì)父代染色體和變異個(gè)體的每一位進(jìn)行交叉互換，指數(shù)交叉則對(duì)變異個(gè)體和父代個(gè)體上某一段基因進(jìn)行交叉操作。2.4.1 節(jié)所述的變異策略很大程度上拓展了算法全局搜索能力，二項(xiàng)式交叉策略精確到基因的操作更容易保證局部搜索能力（當(dāng)Cr取較小值時(shí)，交叉基因位數(shù)變少，可以充分對(duì)變異個(gè)體領(lǐng)域進(jìn)行搜索）可以抵消變異策略，導(dǎo)致算法的局部搜索能力較差的后果。

根據(jù)2.3 節(jié)所述，在進(jìn)化過程中，當(dāng)參數(shù)F 增加時(shí)，減小交叉概率Cr=Cr-rand（0，Cr），提高局部搜索能力，對(duì)進(jìn)化過程進(jìn)行微調(diào)，平衡差分權(quán)重F 增加帶來(lái)的算法局部搜索能力變?nèi)蹂e(cuò)失更優(yōu)解的弊端。

2.5.3 選擇策略

本文采用一對(duì)一生存選擇策略生成新一代種群：將交叉生成的子代染色體與其父代基向量染色體進(jìn)行比較，排除適應(yīng)度低的個(gè)體，選擇適應(yīng)度高的個(gè)體作為新一代種群個(gè)體。該策略保留父代精英個(gè)體，規(guī)避了因變異交叉操作丟失最優(yōu)解的風(fēng)險(xiǎn)。

2.5.4 終止條件

本文同時(shí)使用兩種終止條件結(jié)束進(jìn)化過程：當(dāng)?shù)^程達(dá)到最大進(jìn)化代數(shù)時(shí)，進(jìn)化終止；連續(xù)l（l＞h）代種群最優(yōu)個(gè)體適應(yīng)度或目標(biāo)函數(shù)值保持不變時(shí)，進(jìn)化終止。兩個(gè)終止條件相互制約，保證算法收斂同時(shí)盡可能縮減時(shí)間代價(jià)。

3 仿真測(cè)試

3.1 實(shí)例測(cè)試

為驗(yàn)證模型及算法可用性，本文采用如下用例進(jìn)行測(cè)試：假設(shè)現(xiàn)有待乘機(jī)人員可分為22 個(gè)作戰(zhàn)小組，參數(shù)如下頁(yè)表1 所示，可用直升機(jī)參數(shù)如表2所示。設(shè)差分進(jìn)化算法初始差分權(quán)重F=0.5，交叉概率Cr=0.5，預(yù)設(shè)個(gè)體適應(yīng)度f(wàn)0=90%，基于Python 語(yǔ)言編寫代碼對(duì)運(yùn)輸直升機(jī)人員裝載問題進(jìn)行求解。

運(yùn)行差分進(jìn)化算法求解得到的作戰(zhàn)小組分配方案如表3 所示，共使用6 架直升機(jī)（3 架I 型，3 架II 型），總空間利用率為96.97%。實(shí)驗(yàn)結(jié)果表明，本文提出的差分進(jìn)化算法可以較好地解決運(yùn)輸直升機(jī)人員裝載問題，分配方案滿足裝載原則，直升機(jī)空間利用率很高。

表1 待乘機(jī)人員參數(shù)

表2 可用直升機(jī)參數(shù)

表3 運(yùn)輸直升機(jī)人員裝載方案

3.2 算法分析

以3.1 節(jié)測(cè)試用例為例，采用遺傳算法（GA）、傳統(tǒng)差進(jìn)化算法（DE）和本文提出的動(dòng)態(tài)差分進(jìn)化算法（動(dòng)態(tài)DE）分別對(duì)該用例進(jìn)行測(cè)試。

圖4 各類算法迭代圖

圖4 所示為3 種算法對(duì)于該用例分別迭代500代的結(jié)果，可以看到相較DE 和GA，本文提出的動(dòng)態(tài)差分進(jìn)化算法具有更快的收斂速度和較好的求解質(zhì)量，動(dòng)態(tài)變異算子和交叉算子使得算法進(jìn)行快速搜索，可以較快地得到高空間利用率的直升機(jī)人員裝載方案。

表4 所示為3 種算法對(duì)測(cè)試用例進(jìn)行120 次測(cè)試的結(jié)果。測(cè)試過程中，遺傳算法多次出現(xiàn)無(wú)可行解的情況，而傳統(tǒng)差進(jìn)化算法求解質(zhì)量較為一般?？梢钥闯?，針對(duì)運(yùn)輸直升機(jī)人員裝載問題，本文提出的動(dòng)態(tài)差分進(jìn)化算法求解效果更穩(wěn)定，可以大概率地獲得優(yōu)質(zhì)的人員裝載方案。

表4 各類算法結(jié)果比較

4 結(jié)論

本文針對(duì)運(yùn)輸直升機(jī)人員裝載問題這一多約束組合優(yōu)化問題，提出了一種動(dòng)態(tài)的差分進(jìn)化算法，該算法在傳統(tǒng)差分進(jìn)化算法的基礎(chǔ)上，對(duì)控制參數(shù)差分權(quán)重和交叉概率進(jìn)行了調(diào)整，使其隨迭代效果進(jìn)行變化，平衡了算法全局搜索能力和局部搜索能力，改善了傳統(tǒng)差分進(jìn)化算法進(jìn)化后期種群多樣性銳減、易早熟等缺點(diǎn)。第3 章實(shí)驗(yàn)測(cè)試對(duì)該算法的求解效果進(jìn)行了驗(yàn)證，表明該算法可以在滿足裝載原則的條件下，更快地得到高空間利用率的直升機(jī)人員分配方案。