求解武器—目標分配問題的混合編碼差異演化算法
2009-01-01 00:00:00鄧長壽梁昌勇
計算機應用研究 2009年1期
(1.九江學院 信息科學與技術學院， 江西 九江 332005; 2.合肥工業大學 網絡系統研究所， 合肥 230009)
摘 要：提出一種混合編碼差異演化求解武器—目標分配優化問題。在差異演化算法中增加違反邊界約束處理操作，確保由變異和交叉操作生成的每個新個體滿足邊界約束條件；對差異演化算法中的選擇操作重新定義，使其可以直接處理約束條件。基于編碼映射的方法構建一種新的混合編碼差異演化算法。利用武器—目標分配問題對該算法進行了仿真實驗，結果表明該算法的有效性與適用性?；旌暇幋a差異演化算法是求解離散約束優化問題的一種有效方法。
關鍵詞：武器—目標分配問題; 混合編碼; 編碼映射; 差異演化
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)01007403
Hybrid coding differential evolution algorithm for
weapontarget assignment problem
DENG Changshou1，2， LIANG Changyong2
(1.School of Information Science Technology， Jiujiang University， Jiujiang Jiangxi 332005， China; 2.Institute of Computer Network System， Hefei University of Technology， Hefei 230009， China)
Abstract:Firstly， added a new operation， boundaryhandling operation to the original differential evolution to ensure each population generated by the mutation and crossover operation comply with the boundary constraints. Employed a new selection operation to deal with constraints directly. Then put forward a new hybrid coding differential evolution algorithm with mapping methodto deal with the discrete optimization problem. The simulation result of practical weapontarget assignment shows it is effective and useful. Hybrid coding differential evolution algorithm is a new effective way for solving the discrete optimization problem.
Key words：weapontarget assignment(WTA) problem; hybrid coding; code mapping; differential evolution
0 引言
武器—目標分配(WTA)問題是現代戰爭中一個十分重要的問題，其解空間隨著武器數目和目標總數的增加而呈指數級增加，是多參數多約束的離散NP完全問題。此外，WTA問題的目標函數往往帶有大量的局部極值點，且常常是不可微、不連續和高度非線性的。為了解決這一問題，人們提出了許多算法。例如，Llyod[1]提出了序列算法，該算法假定分配問題按順序逐個地進行，用迎擊失敗概率最小的方式選擇目標與迎擊武器組合，收斂速度較慢；Wacholker[2]利用Hopfield和Tank神經網絡模型，提出一種解WTA問題的神經網絡方法，但懲罰值難以確定，有時得不到穩定解；文獻[3，4]利用遺傳算法求解WTA問題，獲得了較好的結果，但是求解速度有待進一步提高；文獻[5]提出了具有不同交叉策略的粒子群優化算法求解WTA問題，各種交叉策略得到不同的結果，然而每種策略得到的解均不穩定，成功率在12%~82%。本文研究利用混合編碼差異演化(hybrid coding differential evolution，HCDE)算法求解WTA問題。
差異演化算法(differential evolution，DE)是一種基于群體差異的演化算法，采用浮點數編碼，由Storn[6]于1996年在IEEE首屆演化計算大賽中為求解切比雪夫多項式而提出的。DE算法在此次比賽中表現超群，隨后在連續問題的優化中獲得了廣泛的應用[7，8]。雖然DE算法已成功用于連續域上的最優化問題，但對于離散域上的最優化問題，特別是在NP完全問題中的應用研究，現有學術文獻鮮有報道。本文研究利用混合編碼的方法，將DE算法引入離散域優化問題求解WTA問題。
1 WTA問題模型
在一個戰斗編隊中迎擊武器分布于M個武器平臺W1，W2，…，WM，有N個目標T1，T2，…，TN。設pij為武器平臺Wi迎擊目標Tj的命中概率，Ri為武器平臺Wi最多可使用的武器個數，Sj為對目標Tj最多可使用的武器個數。武器—目標分配的最佳解是分配迎擊全部目標的失敗概率和最小。若分配武器平臺Wi迎擊目標Tj，則yij=1，否則yij=0。WTA問題的數學模型如下：
min totalp=∑nj=1∏mi=1(1-pijyij)
s.t. ∑nj=1yij≤Ri； i=1，2，…，M
∑mi=1yij≤Sj； j=1，2，…，N
yij=0，1(1)
式(1)中，當Ri=1(i=1，2，…，M)且Sj=1(j=1，2，…，N)時，WTA問題轉換為指派問題，可以用匈牙利法求解。其他情況下，WTA問題實質是非線性0—1整數規劃問題，屬于NP—難題，用單純形法、梯度法和動態規劃法求解比較困難，尤其是目標數和武器數較多時，也不適宜用枚舉法。
2 DE算法
DE算法首先在搜索空間內隨機產生初始群體，然后通過群體中兩個成員間的差向量增加到第三個成員的方法來生產新的個體。如果新個體的適應度更好，那么新個體將代替原個體。
DE算法偽代碼如下：
生成初始種群
repeat
變異操作
交叉操作
選擇操作
until 滿足循環結束條件
DE算法根據變異和交叉操作的不同形成了不同的模式。其中，常見的是DE/rand/1/bin和DE/best/1/bin[9]。DE/rand/1/bin的具體內容如下。
2.1 生成初始種群
在n維空間中，隨機產生滿足上下界約束，具有m個個體的種群X=(xij)m×n。方法如下：
xij(0)=xlj+rand (0，1)(xuj-xlj)(2)
其中：i=1，2，…，m；j=1，2，…，n；xlj和xuj分別表示第j個變量的上界和下界。
2.2 變異操作
對種群中的每個向量xi(i=1，2，…，m)實施變異時，從種群中隨機選擇三個體xr1，xr2，xr3，要求彼此互不相同，即要求(i≠r1≠r2≠r3)。設當前種群位于第t代，則變異操作的計算式為
ci(t+1)=xr1+η(xr2-xr3)(3)
其中：η為縮放因子；(xr2-xr3)為差異向量；i=1，2，…，m；j=1，2，…，n。
2.3 交叉操作
對種群中的每個向量，利用交叉操作來增加群體的多樣性。交叉操作的公式如下：
ui(t+1)=ci(t+1)rand≤CR or j=R(i)
xi(t)otherwise(4)
其中：i=1，2，…，m;j=1，2，…，n；rand∈[0，1]的隨機小數；CR∈[0，1]為交叉概率；R(i)∈[1，n]的隨機整數。采用這種交叉策略可以保證xi(t+1)至少有一分量由ci(t+1)的相應分量貢獻。
2.4 選擇操作
為了決定xi(t)能否成為下一代種群中的成員，基于優勝劣汰的原則，利用式(5)所示的選擇操作進行選擇。
xi(t+1)=ui(t+1) f(ui(t+1))≤f(xi(t))xi(t) otherwise(5)
由以上描述可以看出，DE算法涉及的數據結構和運算簡單，易于編程實現。
3 解WTA問題的HCDE算法
DE算法雖然成功應用于實數域的數值優化問題， 但從式(1)所示的數學模型可知，WTA問題屬于帶約束的離散優化問題。由于變異操作計算式(3)是基于實數域的四則運算，而離散域的最優化問題的編碼通常對應一個二進制向量，計算式(3)對二進制的計算往往不封閉，不能直接利用DE求解WTA問題。為此，本文提出混合編碼的方法解決DE算法中變異操作對二進制運算的不封閉問題。此外，對DE算法中選擇操作重新定義，使其可以直接處于約束條件。
3.1 編碼映射
由于基本DE算法適合處理連續變量優化問題，求解WTA問題時，需要將連續變量映射轉換為離散變量。HCDE算法中選擇初始種群的取值在區間[0，1]，為了便于HCDE算法處理離散約束優化問題，將區間[0，1]分成兩個子區間[0，0.5）和[0.5，1]。當連續變量的取值屬于區間[0，0.5）時，其映射值為0；當連續變量的取值屬于區間[0.5，1]時，其映射值為1。映射函數f(x)定義如下：
f(x)=0 x∈[0，0.5）1 x∈[0.5，1](6)
3.2 違反邊界約束的處理操作
DE算法中，通過變異操作與交叉操作所產生的新個體中的某分量可能違反了邊界約束條件，即不屬于區間[0，1]。HCDE算法中采用重新生成新的分量方法解決違反邊界約束條件問題，即利用式(7)所定義的邊界約束處理操作生成一個新的分量來代替因變異和交叉操作所產生的不良分量。
uij(t+1)=uij(t+1) if uij(t+1)∈[0，1]rand(0，1) else(7)
在HCDE算法中，利用式(7)所表示的增加違反邊界約束處理操作，不僅可以解決邊界約束問題，而且適當增加了個體的多樣性。
3.3 混合編碼
HCDE算法中，每個個體的編碼由維數相同的兩個子向量構成，第一子向量為實數向量X，第二個子向量為二進制向量B。其中，子向量X為DE算法中的向量；二進制向量B是由實數向量X利用式(6)所表示的函數映射而得到的離散向量。個體混合編碼向量Y如式(8)所示。
Y=(X，B)(8)
其中：B=f(X)。將由實數域的編碼X和由離散域的編碼B所共同構成的混合向量編碼Y稱為混合編碼。
采用上述混合編碼的HCDE算法不僅保留了DE算法的優點，而且可以求解離散域的優化問題。在變異和交叉運算時，利用實數域編碼子向量X；在選擇操作和計算目標函數時，利用離散域編碼子向量B。因此，混合編碼的DE算法可以有效地解決離散優化計算中的不封閉問題。
3.4 選擇操作的改進
DE算法中的選擇操作是基于函數的適應值。當含有約束條件時，需要在函數的適應值與約束條件之間進行平衡。本文采用以下的原則進行選擇操作：
a)如果都是可行解，則選擇函數適應值較小的個體進入下一代。
b)可行解優于不可行解。
c)如果都是不可行解，則違反約束程度小的個體進入下一代。
將式(1)所示的WTA問題的約束條件記為
g(x)=∑nj=1yij-Ri i=1，2，…，M
∑mi=1yij-Sjj=1，2，…，N(9)
基于上述三個原則，HCDE算法中選擇操作定義如下：
popi(t+1)=ui(t+1)ifg(ui(t+1))≤0∧g(popi(t))≤0∧f(ui(t+1))≤f(popi(t))g(ui(t+1))≤0∧g(popi(t))＞0g(ui(t+1))＞0∧max(g(ui(t+1))，0)≤max(g(popi(t))，0)
popi(t)otherwise(10)
3.5 算法描述
求解WTA問題的HCDE算法流程如下：
a)初始化，包括設置最大迭代代數、種群中個體數目、變異概率、交叉概率和生成具有混合編碼的初始種群；
b)不滿足結束條件時，執行c)~f)，否則轉h);
c)對子向量X進行變異操作；
d)對子向量X進行交叉操作；
e)對子向量X進行違反邊界約束處理操作；
f)利用子向量B，按照式(10)所表示的選擇操作確定下一代個體；
g)利用子向量B計算最優值；
h)輸出最優值，算法結束。
4 實例仿真
有六個目標T1，T2，…，T6，武器分布于四個武器平臺W1，W2，W3，W4，每個武器平臺最多可使用武器為(2，1，2，1)。對每個目標最多可使用一個武器，武器平臺Wi迎擊目標Tj的概率為pij(i=1，2，3，4；j=1，2，…，6)，如表1所示[5]。
表1 迎擊概率表
武器平臺T1T2T3T4T5T6
W10.50.70.70.80.40.8
W20.40.80.50.70.60.9
W30.80.70.70.70.60.5
W40.50.70.60.80.70.9
利用MATLAB實現HCDE算法對上述WTA問題進行求解。實驗時種群數目NP=120，縮放因子η=0.5，交叉概率CR=0.3，最大迭代次數為300，懲罰因子M=10，N=10。獨立測試100次，每次都能求出最優解。其中一個最優解為“武器1迎擊目標4和目標6，武器2迎擊目標2，武器3迎擊目標1和目標3，武器4迎擊目標5”；另外一個最優解為“武器1迎擊目標2和目標3，武器2迎擊目標2，武器3迎擊目標1和目標5，武器4迎擊目標6”。迎擊全部目標的失敗概率均為1.4。HCDE算法獨立運行100次的統計結果與粒子群算法[5]的最好策略求解結果的對比情況如表2所示。
表2 結果比較
算法最優結果平均結果最差結果最好解的次數
HCDE算法1.41.41.4100
粒子群算法1.41.421.682
為了描述HCDE算法的收斂性，圖1給出了100次仿真實驗的平均最優適應度的進化曲線。
從表2可以看出，求解WTA問題時，HCDE算法在求解精度與魯棒性方面均優于粒子群算法。此外，圖1所示的HCDE算法100次仿真實驗的平均最優適應度進化曲線表明，HCDE算法求解WTA問題時收斂速度快。
5 結束語
WTA問題是離散域上有約束的NP完全問題。本文利用混合編碼的方法提出了HCDE算法以成功求解WTA問題。HCDE算法保留了DE算法的優點，同時成功地解決了DE算法求解離散優化問題時的計算不封閉問題；此外，HCDE算法利用新的原則定義了選擇操作，直接處理約束條件。仿真實驗表明，HCDE算法求解WTA問題精度高、收斂速度快、魯棒性好。HCDE算法適合處理與WTA問題類似的帶約束條件的NP離散優化問題，具有廣闊的應用前景。此外，對于算法收斂性的理論分析是進一步的研究方向。
參考文獻：
［1］LLYOD S P. An algorithm for the weapontarget assignment problem[J]. Defence Techique， 1991(1): 4556.
[2]WACHOLKER E. A neural networkbased optimization algorithm for the static weapontarget assignment problem[J]. ORSA Journal on Computing， 1989，1(4): 232246.
[3]曹奇英，何張兵.WTA問題的遺傳算法研究[J].控制理論與應用，2001，18(1):7679.
[4]陶英歌，郭乃林，羅紅英.基于遺傳算法的目標分配優化模型研究[J].系統工程與電子技術，2003，25(7):817819.
[5]高尚，楊靜宇.武器—目標分配問題的粒子群優化算法[J].系統工程與電子技術，2005，27(7)：12501252，1259.
[6]STORN R. Differential evolution design of an IIRfilter[C]//Proc ofIEEE International Conference on Evolutionary Computation. Nagoya: IEEE Press，1996:268273.
[7]PAHNER U， HAMEYER K. Adaptive coupling of differential evolution and multiquadrics approximation for the tuning of the optimization process[J]. IEEE Trans on Magnetic， 2000，36(4):10471051.
[8]CHENG S L， HWANG C. Optimal approximation of linear system by a differential evolution algorithm[J]. IEEE Trans on Systems， Man and Cybernecics: Part A，2001，31(6):698707.
[9]STORN R， PRICE K. Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization， 1997，11(4):341359.
