改進后的DE求解方法的MATLAB仿真實現及應用

張宏勇

摘 要：通過建立實例模型，利用MATLAB進行系統仿真，對傳統的DP算法和改進后的DE算法進行對比分析。仿真結果表明，經過改進的DE算法可以很好地解決問題，并具有收斂快、效率高等優勢。

關鍵詞：DE求解方法；動態規劃；數據模型；仿真模型

中圖分類號：TP391.41 文獻標識碼：A DOI：10.15913/j.cnki.kjycx.2015.11.013

動態規劃（DP）是運籌學的一個分支，是求解多階段決策問題的最優化方法。在軍事、科學管理、工程技術和工農業生產等多個領域中得到了廣泛的應用，但在求解某些問題時，求解效率較低，而且計算復雜、步驟煩瑣。

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

如今，計算機技術飛速發展，特別是內存容量和計算速度的迅猛增加，使以上兩種求解方法在實際中的應用范圍迅速擴大。本文從實際出發，通過建立實例數據模型，在計算機上利用MATLAB進行仿真，對比分析兩種求解算法的效率和優缺點，以此來檢測DE算法的優越程度。

1 DE算法

微分進化算法的基本思想是：從種群中隨機選擇三個點，以其中一點為基礎，另外兩點作為參照，做一個擾動，所得點與種群中的個體i交叉后進行選擇，保留較優者，實現種群的優化。

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

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

第二步，對種群中的每個個體進行評價，計算每個個體Xi（t）的目標值f（Xi（t））。

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

，

.

第四步，如果種群Xi（t+1）滿足終止準則，則將具有最小目標值的個體作為最優解輸出；否則轉第二步。

2 MATLAB仿真實現

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

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

本設計中采用MATLAB語言進行仿真，仿真的模型為兩種武器對應三種目標，同時兼容不同目標威脅系數不同的情況，可根據實際需要進行適當修改。

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

應用實例：有3架敵機，價值分別為A1=3，A2=2，A3=5，

用兩種導彈射擊，第一種導彈有6枚（M1=6），第二種導彈有8枚（M1=8），其單發擊毀概率如表1所示，求最優分配方案。

表1 單發擊毀概率表

1 2 3

1 0.4 0.1 0.5

2 0.2 0.4 0.2

對應的數據量為P=[0.4，0.1，0.5，0.2，0.4，0.2]，A=[3，2，5]，M=[6，8]。

本實例為多目標優化問題。傳統的微分進化算法適用于無約束連續變量的全局優化問題，卻并不適合用來求解多目標優化問題。主要原因有兩個：①個體評價問題。無約束單目標優化問題要求個體對應的函數值越小越好，但多目標優化問題則要復雜得多；②標準的微分進化算法（DE）一般會收斂到一個最優點，但多目標優化問題的解通常是一個點集，因而，本設計對DE算法和結構進行了優化，采用改進后的DE算法求解問題，并將其與DP算法的性能進行對比驗證，程序流程如圖1所示。

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

3 仿真結果

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

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

迭代loop_max=1 500次

（a）效益性能對比

（b）時間復雜度對比

圖2 仿真結果圖

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

DP_DE_Campare.m運行結果如圖3所示。

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

結果：①攻擊效益最大值為性能的直接體現，當性能損失相對量數值為正時，表示惡化量；為負時，表示優化量；為零時，表示性能相同。②占用時間為時間復雜度的直接體現，當計算時間優化相對量數值為正時，表示優化量；為負時，表示惡化量；為零時，表示時間復雜度相同。③具體的分配方案表示每種武器分別攻擊對應目標的數目。

需要說明的情況：①當DP算法找不到最優解時，攻擊效益最大值會顯示為0，相對應的性能相對惡化量為-Inf，此時的分配方案均為0；②對算法的衡量需要對多次循環迭代進行統計才可以最終確定算法的優越性，在單次運行時，可能出現DE算法性能差于DP算法的情況，但并不能因此否認DE算法的優越性。

DP_DE_Campare_two.m運行結果如圖4所示。

圖3 DP_DE_Campare.m運行結果圖

圖4 DP_DE_Campare_two.m運行結果

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

指導教師：曹迎槐教授。

參考文獻

[1]康英軍，李為民，李續武.H opfield神經網絡的防空火力最優分配問題[J].火力與指揮控制，2003，28（6）：35-37.

[2]樓順天，施陽.基于MATLAB的系統分析與設計[M].西安：西安電子科技大學出版社，1998.

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

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

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

〔編輯：王霞〕