差分优化算法及其应用_免费论文全文下载

申明:本网站内容仅用于学术交流，如有侵犯您的权益，请及时告知我们，本站将立即删除有关内容。

【摘 要】差分进化算法是一类基于群体的全局优化结果的算法。本文对差分进化算法的三个算子进行研究，并将此算法与旅行商问题结合，针对旅行商问题进行最短路径优化测试与研究。实验结果表明差分进化算法对于最短路径问题有较好的效果。

【关键词】差分进化算法；旅行商；算子
1 差分进化算法
差分进化算法（differential evolution，DE）作为演化算法的一种，其主要流程具有与其他演化算法类似的特点，是一种模拟生物进化的算法模型，通过分别差分算子的操作，对种群进行不断进化的迭代操作，将适应性最高的个体保存下来，即选取出符合条件的最优解。其主要包含了对群体的初始化、对种群个体进行差分操作、将变异操作取得的结果与原始种群进行交叉、通过适应性函数进行对比来选择最优解个体四部分操作。
差分变异算法通过差分变异策略来对不同个体之前进行随机操作，从而实现个体变异。其具体操作是将从种群中随机选取的两个不相同的个体Xvb、Xvc，对这两个不相同的个体进行向量差的缩放操作之后，将缩放操作的结果和另外一个待变异个体X0a进行合成。得到一个差分变异后的个体Xv（a+1）。
通过对待变异的种群个体Xva及其对应的变异的中间体Xv（a+1）之间的进行个体间的杂交操作，得到一个新的种群个体，交叉操作表示如下：
其中，CR代表交叉概率，rand（0，1）产生一个在0～1区间内的一个随机实数，将其与交叉概率CR比较，如果此时随机数小于等于交叉概率CR，将选择变异操作中产生的变异个体的一个解作为此时交叉的结果，这里的是取值范围在[1，2，3…，D]之间的整数，j=jrand是为了保证变异操作的有效性，来保证交叉结果中存在一个变异个体的一个解。
DE算法通过交叉操作可以得到一组经过进化之后的解，现在为了确定这组交叉之后的解是否能够作为下一代的解，就要将原本最初的那一组解和这一组变异解进行适应性的比较，如果变异过后的解优于原解，则将原解替换掉，否则，就保留原来的解。
差分进化算法作为演化算法的一种，其主要流程具有与其他演化算法类似的特点，例如主要包含了对群体的初始化、对种群个体进行差分操作、将变异操作取得的结果与原始种群进行交叉、通过适应性函数进行对比来从所有的结果当中选择最优解个体等。差分进化算法的关键流程步骤与部分操作如下：
1）对差分进化算法中所有相关的参数进行初始化，初始设为当前代数G=0，最大迭代次数Gmax、种群规模大小Np、交叉概率CR、差分缩放因子F和每一个种群所涉及的解的维度D。
2）随机生成初始种群。将进化的代数G进行+1操作，即G=G+1。
3）将目标种群个体设置索引号a=1。
4）对目标个体进行差分变异操作，生成变异个体。
5）将目标个体与变异个体进行交叉，生成试验个体。
6）计算初始个体和试验个体的适应度值，进行对比，作出选择。
7）目标个体索引号a=a+1，跳转到步骤5，一直循环到a=Np，否则跳转到步骤8.
8）算法运行循环到G=Gmax，表示差分进化算法迭代完毕，输出结果，否则跳转运行到步骤3。
2 差分进化算法解决旅行商问题
通过Matlab编程语言，实现基于差分进化算法的对路径优化，分别带入不同数目的样本数据进行仿真数据测试。增加数据的多样性和可靠性，以下进行的数据样本优化均进行了300次的迭代操作，并具有原始路径与经过算法优化过后的路径对比，能够简单直接的看出原始路径和最优路径的差别。
3 以City10为数据样本进行仿真测试
City10数据坐标的初始状态如下所示：
以City10数据坐标为样本，通过算法优化，得出最短路径长度是：276.6526，得出的最优路径如下所示：
通过Matlab绘图工具，可以得出以City10数据坐标为样本的原始路径和进过差分进化算法优化过后的路径对比如下图1所示：
从图1可以看出，对以City10数据坐标为样本进行城市路径模拟，使用差分进化算法进行原始路径优化后，优化路径的顺序变为：9、7、3、2、10、6、1、路径优化过后具有优点：完成了所选取的路径长度是所有可行性路径的最小值，即最优解的任务目标。对于City10问题，原始路径的总距离是665.1982，而差分进化算法的总距离为276.6526，很明显差分进化算法求得的距�x比原始路径小很多，达到了路径优化的目的。
4 总结
本文主要实现了差分进化算法中的定义参数与编码初始化、种群初始化、差分变异操作、交叉操作和选择操作，并用差分算法解决旅行商问题，分别带入不同的数据来验证差分进化算法在旅行商问题中的实用性和有效性。
【参考文献】
[1]郁磊，史峰，王辉，胡斐.MATLAB智能算法30个案例分析（2版）[M].北京：北京航空航天大学出版社，2015：10-52.
[2]张春美.差分进化算法理论与应用 [M].北京：北京理工大学出版社，2014：22-45.
[3]N. Hansen， A. Auger， S. Finck， and R.Ros，“Real-parameter black-box optimization benchmarking 2012： Experimental setup，” Dept. Comput.Sci. Contr.， INRIA， France， Tech. Rep.， Mar. 2012.
[4] J. J. Liang， B. Y. Qu， P. N. Suganthan， and A. G. Hernandez-Diaz，“Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization，” Zhengzhou Univ.， China， and Nanyang Technol. Univ.， Singapore， Tech. Rep. 201212， Jan. 2013.
[责任编辑：朱丽娜]

本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。QQ:522-52-5970