基于两阶段搜索算法的多峰函数优化

doi:10.3969/j.issn.0372-2112.2016.06.032

电子学报 ›› 2016, Vol. 44 ›› Issue (6): 1481-1489.DOI: 10.3969/j.issn.0372-2112.2016.06.032

基于两阶段搜索算法的多峰函数优化

李焕哲^1,2, 吴志健¹, 郭肇禄³, 刘会超¹, 汪慎文²

1. 武汉大学计算机学院软件工程国家重点实验室, 湖北武汉 430072;
2. 河北地质大学信息工程学院, 河北石家庄 050031;
3. 江西理工大学理学院, 江西赣州 341000

收稿日期:2015-07-27 修回日期:2015-09-20 出版日期:2016-06-25
- 作者简介:
- 李焕哲 男,1975年生,河北唐山人,武汉大学计算机学院博士研究生,研究方向:智能计算、机器学习.E-mail:lihuanzhe@whu.edu.cn;吴志健 男,1963年生,教授,博士生导师,武汉大学软件工程国家重点实验室副主任,研究方向:智能计算、并行计算和智能信息处理.E-mail:zhijianwu@whu.edu.cn;郭肇禄 男,1984年生,江西南康人,博士,研究方向为智能计算、并行计算和机器学习.E-mail:gzl@whu.edu.cn;刘会超 男,1982年生,河南驻马店人,博士生,研究方向为智能计算.E-mail:huichaoliu@whu.edu.cn;汪慎文 男,1979年生,副教授,博士后,研究方向为智能计算与机器学习等.E-mail:wangshenwen@whu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61364025,No.61402481); 江西省自然科学基金 (No.20151BAB217010); 河北省自然科学基金 (No.F2015403046); 武汉大学软件工程国家重点实验室开放基金 (No.SKLSE2014-10-04); 河北省科学技术支撑项目 (No.12210319)

Multimodal Function Optimization Based on Two-Stage Search Algorithm

LI Huan-zhe^1,2, WU Zhi-jian¹, GUO Zhao-lu³, LIU Hui-chao¹, WANG Shen-wen²

1. State Key Lab of Software Engineering, Computer School, Wuhan University, Wuhan, Hubei 430072, China;
2. School of Information Engineering, Hebei GEO University, Shijiazhuang, Hebei 050031, China;
3. School of Science, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China

Received:2015-07-27 Revised:2015-09-20 Online:2016-06-25 Published:2016-06-25

摘要/Abstract

摘要：

多峰优化问题需要搜索多个最优值(全局最优/局部最优),这给传统的优化算法带来很大程度上的挑战.本文提出了一种两阶段算法求解多峰优化问题.第一阶段采用带有邻域变异策略的排挤差分演化算法进行粗粒度搜索,在适应度景观上尽可能多的找到最优解的大概位置.搜索一定代数之后,调用DMC聚类方法把搜索种群划分成多个聚类,然后在每个聚类上调用协方差矩阵自适应演化策略算法进行精细搜索.另外,本文还提出搜索点补充策略用于平衡每个聚类的大小及增加算法初期的搜索能力.我们提出的方法和9个较新的经典算法在两个基准测试集上进行了大量对比测试,结果表明新算法是有效的,在大多数测试函数上都优于其它算法.

关键词: 排挤差分演化, 协方差矩阵自适应演化策略, 多峰优化, 小生境, 邻域变异

Abstract:

Multimodal optimization aims to search multiple optima (global and/or local optima) simultaneously, which gives rise to a challenging task for traditional optimization algorithms.This paper proposes a two-stage algorithm to solve multimodal optimization problems.In the first stage, NCDE with neighborhood mutation strategy tries its best to find as many approximate positions of optimal solutions as possible on the fitness landscape.After NCDE runs a certain number of iterations, DMC method is employed to divide the entire population into multiple clusters, and then CMA-ES algorithm is used to perform fine search on each cluster which is found by NCDE.Additionally, search point replenishment strategy is put forward to balance cluster size and to increase search capability of our algorithm in the beginning of the running.Extensive comparative experiments is made between our proposed approach and 9 state-of-the-art algorithms on two benchmark sets, the results show that the new algorithm is effective and superior to the other algorithms on the majority of test functions.

Key words: crowding differential evolution, covariance matrix adaptation evolution strategy, multimodal optimization, niching, neighborhood mutation

中图分类号:

TP18

李焕哲, 吴志健, 郭肇禄, 刘会超, 汪慎文. 基于两阶段搜索算法的多峰函数优化[J]. 电子学报, 2016, 44(6): 1481-1489.

LI Huan-zhe, WU Zhi-jian, GUO Zhao-lu, LIU Hui-chao, WANG Shen-wen. Multimodal Function Optimization Based on Two-Stage Search Algorithm[J]. Acta Electronica Sinica, 2016, 44(6): 1481-1489.

参考文献

[1] 周新宇,吴志健,等.一种精英反向学习的粒子群优化算法[J].电子学报,2013,41(8):1647-1652. Zhou Xin-yu,Wu Zhi-jian,et al.Elite opposition-based particle swarm optimization[J].Acta Electronica Sinica,2013,41(8):1647-1652.(in Chinese)
[2] 彭虎,吴志健,等.基于精英区域学习的动态差分进化算法[J].电子学报,2014,42(8):1522-1530. Peng Hu,Wu Zhi-jian,et al.Dynamic differential evolution algorithm based on elite local learning[J].Acta Electronica Sinica,2014,42(8):1522-1530.(in Chinese)
[3] 李康顺,韦蕴珊,等.小生境演化算法下的WDCT图像压缩方法[J].电子学报,2014,(4):809-814. Li Kang-shun,Wei Yun-shan,et al.WDCT image compre-ssion based on niching evolutionary algorithm[J].Acta Electronica Sinica,2014,42(4):809-814.(in Chinese)
[4] 郑金华,刘磊,等.一种自适应小生境分布性保持策略[J].电子学报,2012,40(11):2330-2335. Zheng Jin-hua,Liu Lei,et al.An adaptive niche for keeping the diversity of solutions in multi-objective evolutionary algorithm[J].Acta Electronica Sinica,2012,40(11):2330-2335.(in Chinese)
[5] Qu B Y,Suganthan P N,Liang J J.Differential evolution with neighborhood mutation for multimodal optimization[J].IEEE Transactions on Evolutionary Computation,2012,16(5):601-614.
[6] Hansen N,Ostermeier A.Completely derandomized self-adaptation in evolution strategies[J].Evolutionary Computation,2001,9(2):159-195.
[7] Hansen N.The CMA Evolution Strategy:A Comparing Review[M].Berlin:Springer,2006.75-102.
[8] Preuss M.Niching the CMA-ES via nearest-better clustering[A].Proceedings of the 12th Annual Conference Companion On Genetic and Evolutionary Computation[C].Portland:ACM,2010.1711-1718.
[9] Stoean C,Preuss M,Stoean R,et al.Multimodal optimization by means of a topological species conservation algorithm[J].IEEE Transactions on Evolutionary Computation,2010,14(6):842-864.
[10] Li X D,et al.Benchmark Functions for CEC'2013 Special Session and Competition on Niching Methods for Multim-odal Function Optimization[R].Melbourne:RMIT University,Evolutionary Computation and Machine Learning Group,2013.1-10.
[11] Vitela J E,Castaños O.A sequential niching memetic algorithm for continuous multimodal function optimization[J].Applied Mathematics and Computation,2012,218(17):8242-8259.
[12] Pereira M W,et al.A topological niching covariance matrix adaptation for multimodal optimization[A].Proc of IEEE Congress on Evolutionary Computation[C].Betjing:IEEE,2014.2562-2569.
[13] Shir O M,Emmerich M,Back T.Adaptive niche radii and niche shapes approaches for niching with the CMA-ES[J].Evolutionary Computation,2010,18(1):97-126.
[14] Auger A,Hansen N.A restart CMA evolution strategy with increasing population size[A].Proc of IEEE Congress on Evolutionary Computation[C].Edinburgh,Scotland:IEEE,2005.1769-1776.
[15] Gao W,Yen G G,Liu S.A cluster-based differential evolution with self-adaptive strategy for multimodal optimization[J].IEEE Transactions on Cybernetics,2014,44(8):1314-1327.
[16] Qu B Y,Suganthan P N.A distance-based locally informed particle swarm model for multimodal optimization[J].IEEE Transactions on Evolutionary Computation,2013,17(3):387-402.
[17] Li X D.A Multimodal particle swarm optimizer based on fitness euclidean-distance ratio[A].Proc of The 9th Annual Conference on Genetic and Evolutionary Computation[C].London:ACM,2007.78-85.
[18] Bandaru S,Deb K.A parameterless-niching-assisted bi-objective approach to multimodal optimization[A].Proc of IEEE Congress on Evolutionary Computation[C].Cancun:IEEE,2013.95-102.

基于两阶段搜索算法的多峰函数优化

Multimodal Function Optimization Based on Two-Stage Search Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

[1]	张松海, 施心陵, 李鹏, 董易, 李孙寸. 多峰函数优化的黄金分割斐波那契树优化算法[J]. 电子学报, 2017, 45(4): 791-798.
[2]	徐雪松, 陈荣元. 融合粗糙集与小生境免疫优化的属性约简方法[J]. 电子学报, 2014, 42(8): 1545-1550.
[3]	李康顺, 韦蕴珊, 张文生. 小生境演化算法下的WDCT图像压缩方法[J]. 电子学报, 2014, 42(4): 809-814.
[4]	郑金华, 刘磊, 刘文盼, 邹娟. 一种自适应小生境分布性保持策略[J]. 电子学报, 2012, 40(11): 2330-2335.
[5]	王兴伟;郭磊;李雪娇;黄敏. 一种智能ABC支持型QoS切换决策机制[J]. 电子学报, 2011, 39(4): 748-756.
[6]	严宣辉. 应用疫苗接种策略的免疫入侵检测模型[J]. 电子学报, 2009, 37(4): 780-785.
[7]	林琳;王树勋. 基于自适应小生境混合遗传算法的说话人识别[J]. 电子学报, 2007, 35(1): 8-12.
[8]	凌军;曹阳;尹建华;徐国雄;黄天锡. 基于小生境技术的多样性抗体生成算法[J]. 电子学报, 2003, 31(8): 1130-1132.