基于信息共享的组合演化算法框架

doi:10.3969/j.issn.0253-2778.2018.01.002

中国科学技术大学学报 ›› 2018, Vol. 48 ›› Issue (1): 7-19.DOI: 10.3969/j.issn.0253-2778.2018.01.002

基于信息共享的组合演化算法框架

许晗，刘伟明，李斌

中国科学技术大学信息科学技术学院，安徽合肥 230026

收稿日期:2017-04-14 修回日期:2017-08-05 出版日期:2018-01-01 发布日期:2018-01-01
通讯作者: 李斌
作者简介:许晗，女，1992年生，硕士生，研究方向：演化计算. E-mail: han0115@mail.ustc.edu.cn
基金资助:
国家自然科学基金（61473001，71071045，71131002）资助.

Evolutionary algorithm portfolios based on information sharing

XU Han, LIU Weiming, LI Bin

University of Science and Technology of China，School of Information Science and Technology，Hefei，230026）

Received:2017-04-14 Revised:2017-08-05 Online:2018-01-01 Published:2018-01-01

摘要/Abstract

摘要： 提出一种用于集成多种启发式算法的通用框架.该框架的每个组成算法各自拥有自属种群并独立演化，因而可以保持各算法的特性和演化过程的连续性.算法间的信息交互仅通过外设的archive结构完成，即每隔一定的迁移间隔，各算法和archive之间进行一定数量的个体迁移.私有种群和信息共享的组合框架可以方便地集成现有的启发式搜索算法，具有很高的普适性.实验选取了五种算法作为子算法，共组成26个组合算法实例，测试了26个组合算法的性能，验证了基于信息共享的组合演化算法框架（EAP_IS）的有效性，并进一步将EAP_IS与其他组合框架进行了对比，实验结果表明，所提出的框架可以有效提高组成算法的综合性能.

关键词: 演化算法, 多算法组合, 信息共享, 私有种群

Abstract: A general framework for combining multiple evolutionary algorithms EAP_IS is proposed. Each of the constituent algorithms in this framework has its own population to maintain its characteristic and the continuity of the evolution process. EAP_IS runs each constituent algorithm with a part of the given time budget and encourages information sharing among the constituent algorithms. The effectiveness of EAP_IS has been verified by investigating 26 instantiations of it on 25 benchmark functions, and further comparisons of EAP_IS with other combinatorial frameworks have been conducted. Experimental results show that the proposed framework can improve the performance of constituent algorithms effectively.

Key words: evolutionary algorithm, algorithm portfolios, information sharing, private population

中图分类号:

TP301

许晗，刘伟明，李斌. 基于信息共享的组合演化算法框架[J]. 中国科学技术大学学报, 2018, 48(1): 7-19.

XU Han, LIU Weiming, LI Bin. Evolutionary algorithm portfolios based on information sharing[J]. Journal of University of Science and Technology of China, 2018, 48(1): 7-19.

参考文献

［1］
HOLLAND J H. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence[J]. Quarterly Review of Biology, 1992, 6(2): 126-137.
[2] EBERHART R, KENNEDY J. A new optimizer using particle swarm theory[C]// International Symposium on MICRO Machine and Human Science. Nagoya: IEEE Press, 1995: 39-43.
[3] STORN R, PRICE K. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359.
[4] LARRAAGA, P, LOZANO J A Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation[M]. Springer Science & Business Media, 2001.
[5] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3): 459-471.
[6] TALBI E G. A taxonomy of hybrid metaheuristics [J]. Journal of Heuristics, 2002, 8(5): 541-564.
[7] VRUGT J A, ROBINSON B A, HYMAN J M. Self-adaptive multimethod search for global optimization in real-parameter spaces [J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 243-259.
[8] VRUGT J A, ROBINSON B A. Improved evolutionary optimization from genetically adaptive multimethod search[J]. Proceedings of the National Academy of Sciences, 2007, 104(3): 708-711.
[9] YUEN S Y, CHOW C K, ZHANG X. Which algorithm should I choose at any point of the search: An evolutionary portfolio approach[C] // Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. Amsterdam: ACM Press, 2013: 567-574.
[10] MOLINA D, LOZANO M, HERRERA F. MA-SW-Chains: Memetic algorithm based on local search chains for large scale continuous global optimization [C]// Proceedings of the IEEE Congress on Evolutionary Computation. Barcelona: ACM Press, 2010: 1-8.
[11] PENG F, TANG K, CHEN G, et al. Population-based algorithm portfolios for numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(5): 782-800.
[12] TANG K, PENG F, CHEN G, et al. Population-based algorithm portfolios with automated constituent algorithms selection[J]. Information Sciences, 2014, 27(1)9: 94-104.
[13] AKAY R, BASTURK A, KALINLI A, et al. Parallel population-based algorithm portfolios: An empirical study[J]. Neurocomputing, 2017, 247(C): 115-125.
[14] SOURAVLIAS D, PARSOPOULOS K E, ALBA E. Parallel algorithm portfolio with market trading-based time allocation[C]// Proceedings of the Operations Research. Springer, 2016: 567-574.
[15] GONG W, ZHOU A, CAI Z. A multioperator search strategy based on cheap surrogate models for evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(5): 746-758.
[16] Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal function optimization[C]// Proceedings of the 2nd International Conference on Genetic Algorithms. Cambridge, USA: Hillsdale, 1987: 41-49.
[17] HANSEN N. The CMA evolution strategy: A comparing review[A]// Study in Fuzziness & Soft Computing. Springe, 2006, 192: 75-102.
[18] ZAMBRANOBIGIARINI M, CLERC M, ROJAS R. Standard particle swarm optimisation 2011 at CEC-2013: A baseline for future PSO improvements[C]// IEEE Congress on Evolutionary Computation, 2013:2337-2344.
[19] QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2):398-417.
[20] WANG Y, CAI Z, ZHANG Q. Differential evolution with composite trial vector generation strategies and control parameters[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 55-66.
[21] SUGANTHAN P N, HANSEN N, LIANG J J, et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R]. KanGAL Report, NCL-TR-2005001, 2005.
[22] WILCOXON F. Individual comparisons by ranking methods[J]. Biometrics Bulletin, 1945, 1(6): 80-83.
[23] DE LA FUENTE A L T, SáNCHEZ J M P. A framework for hybrid dynamic evolutionary algorithms: Multiple offspring sampling (MOS)[D]. Universidad Politécnica de Madrid,2009.

()
(

[1]	王涛，张国桢，杨丽，江俊. 一种基于哈密顿矩阵的电子波函数演化算法[J]. 中国科学技术大学学报, 2020, 50(6): 811-818.
[2]	宦梅丽，陈鹏飞，张莉，侯云先. 突发事件下的乳制品供应链信息共享机制[J]. 中国科学技术大学学报, 2019, 49(6): 506-516.

基于信息共享的组合演化算法框架

Evolutionary algorithm portfolios based on information sharing

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价