文章快速检索 高级检索

A hybrid differential evolutionary algorithm based on the simulated annealing operation
YANG Yanxia
Department of Information Engineering, Wuhan University of Science and Technology City College, Wuhan 430083, China
Abstract: In order to improve the ability of the evolutionary algorithm for solving such complicated combination and optimization problems as the massive deceptive problems and hierarchical problems, this paper proposes an improved algorithm, which introduces the simulated annealing operation into the differential evolutionary algorithm. Using this method, the simulated annealing operation is carried out for a randomly generated initial individual and the temperature-reducing operation is carried out for a new individual. After several times of iterations, the optimal solution in the population is taken as the solution to the question. By utilizing the mutation search of the simulated annealing operator to improve the diversity of the population, the differential evolutionary algorithm can better utilize colony differences for an overall search. In the experiment, various types of deceptive functions and the hierarchical functions with a tree-shape structure are applied to simulation testing of the algorithm. In the initial stage, the algorithm keeps diversity of the population; in the later stage, a local optimal solution may be generated, the convergence scope nears to the overall optimal solution. The simulation results show that the algorithm has advantage for the aspect of searching the overall optimal solution.
Key words: differential evolutionary     evolutionary algorithm     simulated annealing     deceptive problem     hierarchical problem

1 差分进化算法与模拟退火算法 1.1 差分进化算法原理及操作

1)种群初始化。

Li=(l1i, l2i, …, lni)为一个n维向量，即种群中的一个个体，其中编码长度为n，种群大小为P，种群第1代个体按式(1)随机产生：

 (1)

2)变异操作。

 (2)

3)交叉操作。

 (3)

4)选择操作。

1.2 模拟退火算法原理及操作

1)方式1。

 (4)

2)方式2。

 (5)

2 混合差分进化算法

 图 1 混合差分进化算法 Fig. 1 Hybrid differential evolution algorithm
3 实验仿真与结果分析

3.1 欺骗函数问题

 函数 维数n 函数最优解 COMAEA SCDE DESA Goldberg3 30 300 298.42 300.00 300.00 60 600 564.85 572.68 586.69 90 900 796.84 842.75 889.36 Deceptive3 30 10 9.84 10.00 10.00 60 20 18.96 19.26 19.96 90 30 28.96 28.78 29.46 Trap5 30 30 29.63 29.65 29.89 60 60 58.36 49.45 59.68 90 90 78.95 82.68 88.61 Bipolar6 30 5 4.78 4.82 4.91 60 10 9.14 9.54 9.72 90 15 13.68 14.56 14.89

n=60的上述4个函数某一次优化计算的收敛曲线如图 2所示。

 图 2 60维函数收敛曲线对比图 Fig. 2 Comparison of 60-dimensional function convergence curve
3.2 等级问题

1)HIFF函数。

 (6)

 (7)

 (8)

2)HtrapI函数。

HtrapI函数和HIFF函数映射过程类似，将下一层的3个变量映射为上一层的1个变量，问题规模满足n=3L，映射函数如式(9)所示：

 (9)

 (10)

 (11)

 函数 维数n 函数最优解 COMAEA SCDE DESA HIFF 32 192 148.42 153.24 189.79 64 448 372.69 312.33 424.62 128 1 024 836.54 821.35 989.36 HtrapI 27 135 129.94 121.26 134.82 81 1 134 1 083.16 1 041.74 1 131.43 243 9 963 9 228.76 9 128.13 9 927.31

 图 3 HIFF函数和HtrapI函数收敛曲线对比 Fig. 3 Comparison of HIFF function and HtrapI function convergence curve

4 结束语

 [1] 刘建平. 基于混沌和差分进化的混合粒子群优化算法[J]. 计算机仿真 , 2012, 29 (2) : 208-212 LIU Jianping. Hybrid particle swarm optimization algorithm based on chaos and differential evolution[J]. Computer Simulation , 2012, 29 (2) : 208-212 [2] 刘波, 王凌, 金以慧. 差分进化算法研究进展[J]. 控制与决策 , 2007, 22 (7) : 721-729 LIU Bo, WANG Ling, JIN Yihui. Advances in differential evolution[J]. Control and Decision , 2007, 22 (7) : 721-729 [3] 徐斌, 祁荣宾, 钱锋. 基于混合差分进化和alpha约束支配处理的多目标优化算法[J]. 控制理论与应用 , 2012, 29 (3) : 353-360 XU Bin, QI Rongbin, QIAN Feng. Constrained multi-objective optimization with hybrid differential evolution and alpha constrained domination technique[J]. Control Theory & Applications , 2012, 29 (3) : 353-360 [4] 刘若辰, 焦李成, 雷七峰, 等. 一种新的差分进化约束优化算法[J]. 西安电子科技大学学报:自然科学版 , 2011, 38 (1) : 47-53 LIU Ruochen, JIAO Licheng, LEI Qifeng, et al. New differential evolution constrained optimization algorithm[J]. Journal of Xidian University: Natural Science , 2011, 38 (1) : 47-53 [5] 张伟丰. 引入模拟退火算子的差分进化算法性能研究[J]. 数值计算与计算机应用 , 2011, 32 (4) : 301-304 ZHANG Weifeng. The performance research of differential evolution algorithm which introduced the simulated and annealing operator[J]. Journal on Numerical Methods and Computer Applications , 2011, 32 (4) : 301-304 [6] 郑建国, 王翔, 刘荣辉. 求解约束优化问题的ε-DE算法[J]. 软件学报 , 2012, 23 (9) : 2374-2387 ZHENG Jianguo, WANG Xiang, LIU Ronghui. ε-differential evolution algorithm for constrained optimization problems[J]. Journal of Software , 2012, 23 (9) : 2374-2387 DOI:10.3724/SP.J.1001.2012.04149 [7] ZOU Dexuan, GAO Liqun. An efficient improved differential evolution algorithm[C]//The 31st Chinese Control Conference. Hefei, China, 2012: 2385-2390. [8] LI Yinghai. Optimal scheduling of cascade hydropower system using grouping differential evolution algorithm[C]//2012 International Conference on Computer Science and Electronic Engineering. Hangzhou, China, 2012: 625-629. [9] 陶新明, 徐鹏, 刘福荣, 等. 组合分布估计和差分进化的多目标优化算法[J]. 智能系统学报 , 2013, 8 (1) : 39-45 TAO Xinmin, XU Peng, LIU Furong, et al. Multi-objective optimization algorithm composed of estimation of distribution and differential evolution[J]. CAAI Transactions on Intelligent Systems , 2013, 8 (1) : 39-45 [10] 杨振宇, 唐珂. 差分进化算法参数控制与适应策略综述[J]. 智能系统学报 , 2011, 6 (5) : 415-423 YANG Zhengyu, TANG Ke. An overview of parameter control and adaptation strategies in differential evolution algorithm[J]. CAAI Transactions on Intelligent Systems , 2011, 6 (5) : 415-423 [11] 阳春华, 钱晓山, 桂卫华. 一种混沌差分进化和粒子群优化混合算法[J]. 计算机应用研究 , 2011, 28 (2) : 439-441 YANG Chunhua, QIAN Xiaoshan, GUI Weihua. Hybrid algorithm of chaotic differential evolution and particle swarm optimization[J]. Application Research of Computers , 2011, 28 (2) : 439-441 [12] GOLDBERG D E, DEB K, KORB B. Messy genetic algorithms revisited: studies in mixed size and scale[J]. Complex Systems , 1990, 4 (4) : 415-444 [13] 钟伟才, 刘静, 刘芳, 等. 组合优化多智能体进化算法[J]. 计算机学报 , 2004, 27 (10) : 1341-1353 ZHONG Weicai, LIU Jing, LIU Fang, et al. Combinatorial optimization using multi-agent evolutionary algorithm[J]. Chinese Journal of Computers , 2004, 27 (10) : 1341-1353 [14] 刘荣辉, 郑建国. 分区交叉差分进化算法及其约束优化[J]. 计算机科学 , 2012, 39 (2) : 283-287 LIU Ronghui, ZHENG Jianguo. Subarea crossover differential evolution algorithm and its constrained optimization[J]. Computer Science , 2012, 39 (2) : 283-287
DOI: 10.3969/j.issn.1673-4785.201305027

0

#### 文章信息

YANG Yanxia

A hybrid differential evolutionary algorithm based on the simulated annealing operation

CAAI Transactions on Intelligent Systems, 2014, 9(1): 109-114
http://dx.doi.org/10.3969/j.issn.1673-4785.201305027