Gaussian process assisted coevolutionary estimation of distribution algorithm for computationally expensive problems

Abstract

In order to reduce the computation of complex problems, a new surrogate-assisted estimation of distribution algorithm with Gaussian process was proposed. Coevolution was used in dual populations which evolved in parallel. The search space was projected into multiple subspaces and searched by sub-populations. Also, the whole space was exploited by the other population which exchanges information with the sub-populations. In order to make the evolutionary course efficient, multivariate Gaussian model and Gaussian mixture model were used in both populations separately to estimate the distribution of individuals and reproduce new generations. For the surrogate model, Gaussian process was combined with the algorithm which predicted variance of the predictions. The results on six benchmark functions show that the new algorithm performs better than other surrogate-model based algorithms and the computation complexity is only 10% of the original estimation of distribution algorithm.

Keywords

estimation of distribution algorithm / fitness function modeling / Gaussian process / surrogate approach

References

[1] JinY.-c., OlhoferM., SendhoffB.. A framework for evolutionary optimization with approximate fitness functions [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(5): 481-494

[2] SchmidtM. D., LipsonH.. Coevolution of fitness predictors [J]. IEEE Transactions on Evolutionary Computation, 2008, 12(6): 736-749

[3] VO C, PANAIT L, LUKE S, Cooperative coevolution and univariate estimation of distribution algorithms [C]// Proceedings of the 10th ACM SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery. Orlando, Florida, USA: 2009: 141–150.

[4] PotterM. A., DejongK. A.DavidorY., SchwefelH., MännerR.. A cooperative coevolutionary approach to function optimization [C]. The Third Parallel Problem Solving from Nature, 1994, Berlin/Heidelberg, Springer: 249-257

[5] PanaitL.. Theoretical convergence guarantees for cooperative coevolutionary algorithms [J]. Evolutionary Computation, 2010, 18(4): 581-615

[6] JansenT., WiegandR. P.. The cooperative coevolutionary (1+1) EA[J]. Evolutionary Computation, 2004, 12(4): 405-434

[7] BerghF. V. D., EngelbrechtA. P.. A cooperative approach to particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 225-239

[8] YangZ. Y., TangaK., YaoX.. Large scale evolutionary optimization using cooperative coevolution [J]. Information Sciences, 2008, 178(15): 2985-2999

[9] El-BeltagyM. A., KeaneA. J.. Evolutionary optimization for computationally expensive problems using gaussian processes [C]. Proceedings of the International Conference on Artificial Intelligence, 2001, Las Vegas, CSREA Press: 708-714

[10] SuS.-guo.QiL., TianX. Z.. Accelerating particle swarm optimization algorithms using gaussian process machine learning [C]. Proceedings of the 2009 International Conference on Computational Intelligence and Natural Computing, 2009, Wuhan, IEEE Computer Society: 174-177

[11] BucheD., SchraudolphN. N., KoumoutsakosP.. Accelerating evolutionary algorithms with gaussian process fitness function models [J]. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 2005, 35(2): 183-194

[12] LiB., ZhongR.-t., WangX.-j., ZhuangZ.-quan.TangY. Y., WangS. P., LoretteG., YeungD. S., YanH.. Continuous optimization based-on boosting gaussian mixture model [C]. Proceedings of the 18th International Conference on Pattern Recognition (ICPR 2006), 2006, Hong Kong, China, IEEE Computer Society: 1192-1195

[13] DingN., ZhouS., SunZ.. Histogram-based estimation of distribution algorithm: A competent method for continuous optimization [J]. Journal of computer science and technology, 2008, 23(1): 35-43

[14] KrohlingR. A., CoelhoL. D.. Coevolutionary particle swarm optimization using gaussian distribution for solving constrained optimization problems [J]. IEEE Transactions on Systems Man and Cybernetics Part B-Cybernetics, 2006, 36(6): 1407-1416

[15] ZhaoL., YangY.-p., ZengY.. Eliciting compact t-s fuzzy models using subtractive clustering and coevolutionary particle swarm optimization [J]. Neurocomputing, 2009, 72(10/11/12): 2569-2575

[16] XiongZ.-hua.. Soft sensor modeling based on gaussian processes [J]. Journal of Central South University of Technology, 2005, 12(4): 469-471

[17] JinY.-chu.. A comprehensive survey of fitness approximation in evolutionary computation [J]. Soft Computing, 2005, 9(1): 3-12