﻿ 基于搜索空间大小的动态变异算子差分进化算法
 计算机系统应用  2019, Vol. 28 Issue (6): 209-212 PDF

1. 榆林职业技术学院神木校区 信息中心, 神木 719300;
2. 西北工业大学 信息中心, 西安 710072

Differential Evolution with Dynamic Mutation Based on Search Space
MIAO Xiao-Feng1, LIU Zhi-Wei2
1. Information Center, Yulin Vocational and Technical College at Shenmu, Shenmu 719300, China;
2. Information Center, Northwestern Polytechnical University, Xi’an 710072, China
Foundation item: National Natural Science Foundation of China (61672433); Year 2018, Major Educational and Scientific Research Project of Yulin Vocational and Technical College at Shenmu (ZK-201801)
Abstract: Differential Evolution (DE) is a novel evolutionary computation technique, which has attracted much attention and wide applications for its simple concept, easy implementation and quick convergence. In order to tackle much overhead, problem-dependent parameters, etc and enhance the precision of classical DE, an Improved DE(IDE) algorithm is proposed by using an dynamical mutation operator adjusting the step size based on search space with evolution. Experiments of solving well-known benchmark functions in MATLAB show the improved approach outperforms existing algorithms, and dynamic mutation is a effective improvement ideas.
Key words: genetic algorithm     optimization     dynamic mutation     differential evolution (DE)     simulation     MATLAB

1 差分进化算法

DE有多种最基本的形式[1], 最著名的一种是标准DE即“DE/rand/1/bin”. 该算法工作时首先随机生成一组初始解, 然后通过变异和杂交操作产生一组对应的试验解, 再根据最优适应值函数判断哪些试验解能作为下一代解种群成员, 然后迭代进行以上操作, 直至所得到当前解种群的精度达到要求时即停止求解循环.

 ${V_{i,G}} = {X_{r{\rm{1}},G}} + F({X_{r2,G}} - {X_{r3,G}})$ (1)

 ${U_{i,G}} = \left( {{U_{1i,G,}}{U_{2i,G,}}\cdots,{U_{Di,G,}}} \right)$

 ${U_{ji,G}} = \left\{ \begin{array}{l} {V_{ji,G}},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{if}}{\kern 1pt} {\kern 1pt} ran{d_j}(0,1) \le CR{\kern 1pt} {\kern 1pt} \vee {\kern 1pt} j = k\\ {X_{ji,G}},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{otherwise}} \end{array} \right.$ (2)

2 根据搜索空间大小动态调整变异算子的算法

 ${x_j}(t + 1) = {x_j}(t) + [{b_j}(t) - {a_j}(t)]*rand()$ (3)
 $\begin{array}{l} {a_j}(t) = {\mathop{\rm Min}\nolimits} \left( {{x_{ij}}(t)} \right),\;\;{b_j}(t) = {\mathop{\rm Max}\nolimits} \left( {{x_{ij}}(t)} \right) \end{array}$ (4)
 $i = 1,2,\cdots,ps,\;\;j = 1,2,\cdots,n$

Begin

While NE < MAXNE do

For i = 1 to PS do

Xi和试验向量中选择具有更好适应度的一个进入下一代种群;

End For

if best(t+1)的适应值优于best的适应值

best = best(t+1);

if end

End While

End

 图 1 b(t)–a(t)值的收敛过程

3 基准函数测试试验

4 结论与展望

 图 2 改进DE求解f1时的收敛过程

 图 3 改进DE求解f3时的收敛过程

 [1] Storn R, Price K. Differential evolution–A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11(4): 341-359. DOI:10.1023/A:1008202821328 [2] Vesterstrom J, Thomsen R. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems. Proceedings of the 2004 Congress on Evolutionary Computation. Portland, OR, USA. 2014. 1980–1987. [3] Liu JH, Lampinen J. A fuzzy adaptive differential evolution algorithm. Soft Computing-A Fusion of Foundations, Methodologies and Applications, 2005, 9(6): 448-462. [4] Qin AK, Suganthan PN. Self-adaptive differential evolution algorithm for numerical optimization. Proceedings of 2005 IEEE Congress on Evolutionary Computation. Edinburgh, Scotland, UK. 2005. 1785–1791. [5] Brest J, Greiner S, Boskovic B, et al. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-657. DOI:10.1109/TEVC.2006.872133 [6] Yang ZY, Yao X, He JS. Making a difference to differential evolution. Siarry P, Michalewicz Z. Advances in Metaheuristics for Hard Optimization. Berlin, Heidelberg: Springer, 2018. 397–414. [7] Ali MM, Törn A. Population set-based global optimization algorithms: Some modifications and numerical studies. Computers and Operations Research, 2004, 31(10): 1703-1725. DOI:10.1016/S0305-0548(03)00116-3 [8] Sun JY, Zhang QF, Tsang EPK. DE/EDA: A new evolutionary algorithm for global optimization. Information Sciences, 2005, 169(3–4): 249-262. [9] Yao X, Liu Y, Lin GM. Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-102. DOI:10.1109/4235.771163 [10] He YC, Kou YZ, Shen CP. An improved differential evolution based on triple evolutionary strategy. Proceedings of the 3rd International Symposium on Intelligence Computation and Applications. Wuhan, China. 2008. 89–97. [11] Shi Y, Lan ZZ, Feng XH. Differential evolution based on improved learning strategy. Proceedings of the 10th Pacific Rim International Conference on Artificial Intelligence. Hanoi, Vietnam. 2008. 880–889. [12] 苗晓锋, 刘志伟. 一种基于混合策略的差分进化算法研究. 计算机应用与软件, 2019, 36(3): 260-265.