Evolutionary algorithm portfolios based on information sharing

doi:10.3969/j.issn.0253-2778.2018.01.002

Abstract

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

CLC Number:

TP301

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.

References

［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]	WANG Tao, ZHANG Guozhen, YANG Li, JIANG Jun. A Hamiltonian matrix based algorithm for simulating evolution of electronic wave functions [J]. Journal of University of Science and Technology of China, 2020, 50(6): 811-818.
[2]	HUAN Meili, CHEN Pengfei, ZHANG Li, HOU Yunxian. Information sharing mechanism of dairy supply chain under emergencies [J]. Journal of University of Science and Technology of China, 2019, 49(6): 506-516.