The Effects of CMA-ES Style Selection and Restart Criteria on DE

Mark Wineberg; Samuel Opawale

doi:10.13164/mendel.2018.1.017

Mark Wineberg
Samuel Opawale

DOI: https://doi.org/10.13164/mendel.2018.1.017

Keywords: CMA-ES, DE, selection, restart, IPOP, ES

Abstract

Over the years, a lot of research has gone into the creation of different mutation operators and adaptive parameters for differential evolution (DE). However, the literature is fairly quiet about automatically setting population size and completely silent about varying the selection operator used within DE. In this paper, we steal a page from CMA-ES/IPOP: using ES-style µ+λ selection, which selects across the entire population, in place of more individualistic DE selection with its use of local selection on the target and its child. We find that the most effective choice of selection can depend on the function being optimized, although for most of the functions we tested, the original DE selection was preferable. When adding IPOP style restarting, EqualFunValHist is the most applicable of the stagnation criteria, and it is used to trigger the doubling of the population size upon restart. The initial population size is set to the same as CMA-ES. Here we find, that the restartable DE behave as well and better as regular DE with population size set as lower than the default settings used.

References

Auger, A., Hansen, N.: Performance evaluation of an advanced local search evolutionary algorithm. In: Evolutionary Computation, 2005. The 2005 IEEE Congress on, vol. 2, pp. 1777–1784. IEEE (2005)

Auger, A., Hansen, N.: A restart cma evolution strategy with increasing population size. In: Evolutionary Computation, 2005. The 2005 IEEE Congress on, vol. 2, pp. 1769–1776. IEEE (2005)

Auger, A., Schoenauer, M., Vanhaecke, N.: Ls-cma-es: A second-order algorithm for covariance matrix adaptation. In: International Conference on Parallel Problem Solving from Nature, pp. 182–191. Springer (2004)

Hansen, N., Ostermeier, A.: Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In: Evolutionary Computation, 1996., Proceedings of IEEE International Conference on, pp. 312–317. IEEE (1996)

Igel, C., Suttorp, T., Hansen, N.: A computational efficient covariance matrix update and a (1+ 1)-cma for evolution strategies. In: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp. 453–460. ACM (2006)

Price, K.V.: Differential evolution: a fast and simple numerical optimizer. In: Fuzzy Information Processing Society, 1996. NAFIPS., 1996 Biennial Conference of the North American, pp. 524–527. IEEE (1996)

Price, K.V., Storn, R.M., Lampinen, J.A.: The differential evolution algorithm. Differential evolution: a practical approach to global optimization pp. 37–134 (2005)

van Rijn, S., Wang, H., van Stein, B., B¨ack, T.: Algorithm configuration data mining for cma evolution strategies. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 737–744. ACM (2017)

Sarma, J., De Jong, K.A.: An analysis of local selection algorithms in a spatially structured evolutionary algorithm. In: ICGA, pp. 181–187. Citeseer (1997)

Simon, D.: Evolutionary optimization algorithms. John Wiley & Sons (2013)

Storn, R., Price, K.: Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization 11(4), 341–359 (1997)

Wineberg, L.: Reexpressing problematic optimization data. In: Proceedings of the 2017 Annual Conference on Genetic and Evolutionary Computation, pp. 897–904. ACM (2017)