改进后的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.

〔编辑：王霞〕