局部抽象凸区域剖分差分进化算法

周晓根; 张贵军; 郝小虎

doi:10.16383/j.aas.2015.c140680

局部抽象凸区域剖分差分进化算法

doi: 10.16383/j.aas.2015.c140680

1.
浙江工业大学信息工程学院杭州 310023

基金项目:

国家自然科学基金 (61075062), 浙江省自然科学基金 (LY13F0300 08), 浙江省科技厅公益项目 (2014C33088), 浙江省重中之重学科开放基金 (20120811), 杭州市产学研合作项目 (20131631E31) 资助

详细信息

作者简介:
周晓根浙江工业大学信息工程学院博士研究生. 主要研究方向为智能信息处理, 优化理论及算法设计.E-mail: zhouxiaogen53@126.com

计量
- 文章访问数: 1527
- HTML全文浏览量: 84
- PDF下载量: 947
- 被引次数: 0
出版历程
- 收稿日期: 2014-12-03
- 修回日期: 2015-02-27
- 刊出日期: 2015-07-20

Differential Evolution Algorithm with Local Abstract Convex Region Partition

1.
College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023

Funds:

Supported by National Natural Science Foundation of China (61075062), Natural Science Foundation of Zhejiang Province (LY13F030008), Public Welfare Project of Science Technology Department of Zhejiang Province (2014C33088), Open Fund for Key-Key Discipline of Zhejiang Province (20120811), and Cooperation Project of Industry-Academia-Research Institute of Hangzhou (20131631E31)

摘要

摘要: 在差分进化算法框架下, 结合抽象凸理论, 提出一种局部抽象凸区域剖分差分进化算法(Local partition based differential evolution, LPDE). 首先, 通过对新个体的邻近个体构建分段线性下界支撑面, 实现搜索区域的动态剖分; 然后, 利用区域剖分特性逐步缩小搜索空间, 同时根据下界估计信息指导种群更新, 并筛选出较差个体; 其次, 借助下界支撑面的广义下降方向作局部增强, 并根据进化信息对搜索区域进行二次剖分; 最后, 根据个体的局部邻域下降方向对部分较差个体作增强处理. 数值实验结果表明了所提算法的有效性.
- 差分进化 /
- 区域剖分 /
- 全局优化 /
- 下界估计 /
- 抽象凸
Abstract: Within the framework of differential evolution algorithm, a differential evolution algorithm with local abstract convex region partition is proposed in this paper incorporating the abstract convexity theory. Firstly, the partition of the search domain is performed dynamically by building piecewise linear abstract convex lower supporting hyperplanes for the neighboring individuals of new individuals. Secondly, the search domain narrows gradually by using properties of the region partition. Meanwhile, the process of population updating is guided according to the information of underestimate, and poor individuals are identified effectively. Additionally, the generalized descent directions of the lower supporting hyperpalens are used for local enhancement, and the search domain is partitioned again according to the evolutionary information. Finally, some poor individuals get enhanced according to descent directions of their local neighbourhood. Numerical experiment results have verified the effectiveness of the proposed algorithm.
- Differential evolution /
- region partition /
- global optimization /
- underestimate /
- abstract convex

HTML全文

参考文献(28)

[1]	Chen Bao-Lin. Theory and Methods of Optimization (2nd Edition). Beijing: Tsinghua University Press, 2005. (陈宝林. 最优化理论与算法. 第2版. 北京: 清华大学出版社, 2005.)
[2]	Walsh G R. Methods of Optimization. London: Wiley Press, 1975.
[3]	Nelder J A, Mead R. A simplex method for function minimization. The Computer Journal, 1965, 7(4): 308-313
[4]	Adjiman C S, Dallwig S, Floudas C A, Neumaier A. A global optimization method, αBB, for general twice-differentiable constrained NLPs: I. Theoretical advances. Computers & Chemistry Engineering, 1998, 22(9): 1137-1158
[5]	Adjiman C S, Androulakis I P, Floudas C A. A global optimization method, αBB, for general twice-differentiable constrained NLPs: II. Implementation and computational results. Computers & Chemistry Engineering, 1998, 22(9): 1159-1179
[6]	Skjäl A, Westerlund T, Misener R, Floudas C A. A generalization of the classical αBB convex underestimation via diagonal and nondiagonal quadratic terms. Journal of Optimization Theory and Applications, 2012, 154(2): 462-490
[7]	Beliakov G. Cutting angle method ---a tool for constrained global optimization. Optimization Methods and Software, 2004, 19(2): 137-151
[8]	Bagirov A M, Rubinov A M. Cutting angle method and a local search. Journal of Global Optimization, 2003, 27(2-3): 193-213
[9]	Beliakov G. Geometry and combinatorics of the cutting angle method. Optimization, 2003, 52(4-5): 379-394
[10]	Floudas C A, Gounaris C E. A review of recent advances in global optimization. Journal of Global Optimization, 2009, 45(1): 3-38
[11]	Das S, Suganthan P N. Differential evolution: a survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 4-31
[12]	Wang Da-Zhi, Liu Shi-Xin, Guo Xi-Wang. A multi-agent evolutionary algorithm for solving total tardiness permutation flow-shop scheduling problem. Acta Automatica Sinica, 2014, 40(3): 548-555 (王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法. 自动化学报, 2014, 40(3): 548-555
[13]	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
[14]	Islam S M, Das S, Ghosh S, Roy S, Suganthan P N. An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2012, 42(2): 482-500
[15]	Hu Rong, Qian Bin. A hybrid differential evolution algorithm for stochastic flow shop scheduling with limited buffers. Acta Automatica Sinica, 2009, 35(12): 1580-1586 (胡蓉, 钱斌. 一种求解随机有限缓冲区流水线调度的混合差分进化算法. 自动化学报, 2009, 35(12): 1580-1586)
[16]	Stoean C, Preuss M, Stoean R, Dumitrescu D. Multimodal optimization by means of a topological species conservation algorithm. IEEE Transactions on Evolutionary Computation, 2010, 14(6): 842-864
[17]	Kaelo P, Ali M M. A numerical study of some modified differential evolution algorithm. European Journal of Operational Research, 2006, 169(3): 1176-1184
[18]	Cai Y Q, Wang J H. Differential evolution with neighborhood and direction information for numerical optimization. IEEE Transactions on Cybernetics, 2013, 43(6): 2202-2215
[19]	Bhattacharya A, Chattopadhyay P K. Hybrid differential evolution with biogeography-based optimization for solution of economic load dispatch. IEEE Transactions on Power Systems, 2010, 25(4): 1955-1964
[20]	Wang Y, Cai Z X, Zhang Q F. Differential evolution with composite trial vector generation strategies and control parameters. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 55-66
[21]	Gong W Y, Cai Z H. Differential evolution with ranking-based mutation operators. IEEE Transactions on Cybernetics, 2013, 43(6): 2066-2081
[22]	Zhang Gui-Jun, He Yang-Jun, Guo Hai-Feng, Feng Yuan-Jing, Xu Jian-Ming. Differential evolution algorithm for multimodal optimization based on abstract convex underestimation. Journal of Software, 2013, 24(6): 1177-1195 (张贵军, 何洋军, 郭海锋, 冯远静, 徐建明. 基于广义凸下界估计的多模态差分进化算法. 软件学报, 2013, 24(6): 1177-1195)
[23]	Deng Yong-Yue, Zhang Gui-Jun. Multimodal optimization based on local abstract convexity support hyperplanes. Control Theory & Applications, 2014, 31(4): 458-466 (邓勇跃, 张贵军. 基于局部抽象凸支撑面的多模态优化算法. 控制理论与应用, 2014, 31(4): 458-466)
[24]	Rubinov A M. Abstract convexity and global optimization. Nonconvex Optimization and Its Applications. Dordrecht: Kluwer Academic Publishers, 2000.
[25]	Bagirov A M, Rubinov A M. Global minimization of increasing positively homogeneous functions over the unit simplex. Annals of Operations Research, 2000, 98(1-4): 171-187
[26]	Zhang Gui-Jun, Zhou Xiao-Gen. Population-based global optimization algorithm using abstract convex underestimate. Control and Decision, 2015, 30(6): 1116-1120(张贵军, 周晓根. 基于抽象凸下界估计的群体全局优化算法. 控制与决策, 2015, 30(6): 1116-1120)
[27]	Qin A K, Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398-417
[28]	Corder G W, Foreman D I. Nonparametric Statistics for Non-statisticians: a Step-by-step Approach. Hoboken, NJ: Wiley Press, 2009.