張宏勇

摘 要：通過建立實(shí)例模型，利用MATLAB進(jìn)行系統(tǒng)仿真，對傳統(tǒng)的DP算法和改進(jìn)后的DE算法進(jìn)行對比分析。仿真結(jié)果表明，經(jīng)過改進(jìn)的DE算法可以很好地解決問題，并具有收斂快、效率高等優(yōu)勢。

關(guān)鍵詞：DE求解方法；動態(tài)規(guī)劃；數(shù)據(jù)模型；仿真模型

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識碼：A DOI：10.15913/j.cnki.kjycx.2015.11.013

動態(tài)規(guī)劃（DP）是運(yùn)籌學(xué)的一個分支，是求解多階段決策問題的最優(yōu)化方法。在軍事、科學(xué)管理、工程技術(shù)和工農(nóng)業(yè)生產(chǎn)等多個領(lǐng)域中得到了廣泛的應(yīng)用，但在求解某些問題時，求解效率較低，而且計算復(fù)雜、步驟煩瑣。

差分進(jìn)化算法是一種并行的直接搜索算法，由Storn R和Price K于20世紀(jì)90年代在其所作的技術(shù)報告中提出。它本質(zhì)上是一種基于實(shí)數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法，具有易用性、穩(wěn)健性和強(qiáng)大的全局尋優(yōu)能力等優(yōu)勢，可對非線性不可微連續(xù)空間函數(shù)進(jìn)行最小化，因而在多個領(lǐng)域取得了成功。

如今，計算機(jī)技術(shù)飛速發(fā)展，特別是內(nèi)存容量和計算速度的迅猛增加，使以上兩種求解方法在實(shí)際中的應(yīng)用范圍迅速擴(kuò)大。本文從實(shí)際出發(fā)，通過建立實(shí)例數(shù)據(jù)模型，在計算機(jī)上利用MATLAB進(jìn)行仿真，對比分析兩種求解算法的效率和優(yōu)缺點(diǎn)，以此來檢測DE算法的優(yōu)越程度。

1 DE算法

微分進(jìn)化算法的基本思想是：從種群中隨機(jī)選擇三個點(diǎn)，以其中一點(diǎn)為基礎(chǔ)，另外兩點(diǎn)作為參照，做一個擾動，所得點(diǎn)與種群中的個體i交叉后進(jìn)行選擇，保留較優(yōu)者，實(shí)現(xiàn)種群的優(yōu)化。

設(shè)待求問題為 ，則DE算法描述如下。

第一步，初始化種群，輸入種群各項(xiàng)參數(shù)，種群規(guī)模N，交叉概率Pc，交叉因子F∈（0，1），進(jìn)化代數(shù)t=0，隨機(jī)生成初始種 （0）={X1（0），L，XN（0）}，其中，Xi（0）={X1i（0），L，Xni（0）}。

第二步，對種群中的每個個體進(jìn)行評價，計算每個個體Xi（t）的目標(biāo)值f（Xi（t））。

第三步，繁殖種群中的每個個體Xi（t），隨機(jī)生成三個互不相同的隨機(jī)整數(shù)r1，r2，r3∈{1，2，L，N}和隨機(jī)整數(shù)jrand∈﹛1，2，L，n﹜，

，

.

第四步，如果種群Xi（t+1）滿足終止準(zhǔn)則，則將具有最小目標(biāo)值的個體作為最優(yōu)解輸出；否則轉(zhuǎn)第二步。

2 MATLAB仿真實(shí)現(xiàn)

MATLAB是Matrix Laboratory矩陣實(shí)驗(yàn)室的簡稱，是一種用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析和數(shù)值計算的高級技術(shù)計算語言和交互式環(huán)境。它包括MATLAB桌面、命令窗口、M文件編輯調(diào)試器、MATLAB工作空間和在線幫助文檔等，允許用戶輸入輸出數(shù)據(jù)，并為用戶提供了M文件的集成編譯和調(diào)試環(huán)境。

MATLAB語言是一種高級的基于矩陣數(shù)組的語言，與其他語言具有通信接口，具有豐富的庫函數(shù)，用這種語言能夠方便、快捷地建立起簡單、運(yùn)行快的程序，也能建立起復(fù)雜的程序。

本設(shè)計中采用MATLAB語言進(jìn)行仿真，仿真的模型為兩種武器對應(yīng)三種目標(biāo)，同時兼容不同目標(biāo)威脅系數(shù)不同的情況，可根據(jù)實(shí)際需要進(jìn)行適當(dāng)修改。

定義攻擊概率矩陣P為2×3矩陣，定義目標(biāo)威脅系數(shù)A為1×3向量，定義兩種武器的數(shù)目M為1×2向量。

應(yīng)用實(shí)例：有3架敵機(jī)，價值分別為A1=3，A2=2，A3=5，

用兩種導(dǎo)彈射擊，第一種導(dǎo)彈有6枚（M1=6），第二種導(dǎo)彈有8枚（M1=8），其單發(fā)擊毀概率如表1所示，求最優(yōu)分配方案。

表1 單發(fā)擊毀概率表

1 2 3

1 0.4 0.1 0.5

2 0.2 0.4 0.2

對應(yīng)的數(shù)據(jù)量為P=[0.4，0.1，0.5，0.2，0.4，0.2]，A=[3，2，5]，M=[6，8]。

本實(shí)例為多目標(biāo)優(yōu)化問題。傳統(tǒng)的微分進(jìn)化算法適用于無約束連續(xù)變量的全局優(yōu)化問題，卻并不適合用來求解多目標(biāo)優(yōu)化問題。主要原因有兩個：①個體評價問題。無約束單目標(biāo)優(yōu)化問題要求個體對應(yīng)的函數(shù)值越小越好，但多目標(biāo)優(yōu)化問題則要復(fù)雜得多；②標(biāo)準(zhǔn)的微分進(jìn)化算法（DE）一般會收斂到一個最優(yōu)點(diǎn)，但多目標(biāo)優(yōu)化問題的解通常是一個點(diǎn)集，因而，本設(shè)計對DE算法和結(jié)構(gòu)進(jìn)行了優(yōu)化，采用改進(jìn)后的DE算法求解問題，并將其與DP算法的性能進(jìn)行對比驗(yàn)證，程序流程如圖1所示。

圖1 DP算法和DE算法性能對比程序流程圖

3 仿真結(jié)果

隨機(jī)生成N組概率矩陣，每組迭代loop_max次進(jìn)行性能統(tǒng)計，然后按照性能大小對應(yīng)順序排序進(jìn)行效益性能和時間復(fù)雜度的對比。每組矩陣迭代一次大約要2 s多，可以根據(jù)要求修改生成概率矩陣組數(shù)N和迭代次數(shù)loop_max。

迭代loop_max=10次。仿真結(jié)果如圖2所示。

迭代loop_max=1 500次

（a）效益性能對比

（b）時間復(fù)雜度對比

圖2 仿真結(jié)果圖

這里提供兩個子文件分別獨(dú)立進(jìn)行求分配方案（DP_DE_ Campare. m）和性能分析（DP_DE_Campare_two.m）。

DP_DE_Campare.m運(yùn)行結(jié)果如圖3所示。

從圖2中可以看出兩種算法在性能和時間復(fù)雜度上的對比

結(jié)果：①攻擊效益最大值為性能的直接體現(xiàn)，當(dāng)性能損失相對量數(shù)值為正時，表示惡化量；為負(fù)時，表示優(yōu)化量；為零時，表示性能相同。②占用時間為時間復(fù)雜度的直接體現(xiàn)，當(dāng)計算時間優(yōu)化相對量數(shù)值為正時，表示優(yōu)化量；為負(fù)時，表示惡化量；為零時，表示時間復(fù)雜度相同。③具體的分配方案表示每種武器分別攻擊對應(yīng)目標(biāo)的數(shù)目。

需要說明的情況：①當(dāng)DP算法找不到最優(yōu)解時，攻擊效益最大值會顯示為0，相對應(yīng)的性能相對惡化量為-Inf，此時的分配方案均為0；②對算法的衡量需要對多次循環(huán)迭代進(jìn)行統(tǒng)計才可以最終確定算法的優(yōu)越性，在單次運(yùn)行時，可能出現(xiàn)DE算法性能差于DP算法的情況，但并不能因此否認(rèn)DE算法的優(yōu)越性。

DP_DE_Campare_two.m運(yùn)行結(jié)果如圖4所示。

圖3 DP_DE_Campare.m運(yùn)行結(jié)果圖

圖4 DP_DE_Campare_two.m運(yùn)行結(jié)果

通過MATLAB仿真結(jié)果可以看出，對DP算法和DE算法進(jìn)行比較，DE算法完全可以解決火力分配問題，并具有較大的優(yōu)越性。

指導(dǎo)教師：曹迎槐教授。

參考文獻(xiàn)

[1]康英軍，李為民，李續(xù)武.H opfield神經(jīng)網(wǎng)絡(luò)的防空火力最優(yōu)分配問題[J].火力與指揮控制，2003，28（6）：35-37.

[2]樓順天，施陽.基于MATLAB的系統(tǒng)分析與設(shè)計[M].西安：西安電子科技大學(xué)出版社，1998.

[3]尹澤明，丁春利.精通Matlab7[M].北京：清華大學(xué)出版社，2008.

[4]海天翼.DE算法在matlab中的應(yīng)用[M].北京：清華大學(xué)出版社，2007.

[5]黃文梅，楊勇，熊桂林.系統(tǒng)分析與仿真——MATLAB語言及應(yīng)用[M].長沙：國防科技大學(xué)出版社，1999.

〔編輯：王霞〕