evolutionary-intelligence/pypop

PyPop7: A Pure-Python Library for POPulation-based Black-Box Optimization (BBO), especially their *Large-Scale* versions/variants. https://pypop.rtfd.io/

PyPop7 (a Pure-PYthon library of POPulation-based black-box OPtimization)

PyPop7 is a Pure-PYthon library of POPulation-based OPtimization for single-objective, real-parameter, black-box problems (currently actively maintained). Its goal is to provide a unified interface and elegant implementations for Black-Box Optimization (BBO), particularly population-based optimizers, in order to facilitate research repeatability, benchmarking of BBO, and real-world applications.

More specifically, for alleviating their curse of dimensionality, the primary focus of PyPop7 is to cover their State Of The Art for Large-Scale Optimization (LSO), though many of their small/medium-scaled versions and variants are also included here (mainly for theoretical or benchmarking purposes).

How to Quickly Use

The following three steps are enough to utilize the optimization power of this library PyPop7:

1. Use pip to install pypop7 on the Python3-based virtual environment via venv or conda (a strong suggestion):

$ pip install pypop7

For simplicity, all required library dependencies (except special cases) are automatically installed according to setup.cfg.

2. Define the objective/cost function (called fitness function in this library) for the optimization problem at hand,

3. Run one or more black-box optimizers on this optimization problem:

import numpy as np  # for numerical computation, which is also the computing engine of pypop7

# 2. Define your own objective/cost function for the optimization problem at hand:
#   the below example is Rosenbrock, the notorious test function from the optimization community
def rosenbrock(x):
    return 100.0*np.sum(np.power(x[1:] - np.power(x[:-1], 2), 2)) + np.sum(np.power(x[:-1] - 1, 2))

# define the fitness (cost) function and also its settings
ndim_problem = 1000
problem = {'fitness_function': rosenbrock,  # cost function
           'ndim_problem': ndim_problem,  # dimension
           'lower_boundary': -5.0*np.ones((ndim_problem,)),  # search boundary
           'upper_boundary': 5.0*np.ones((ndim_problem,))}

# 3. Run one or more black-box optimizers on the given optimization problem:
#   here we choose LM-MA-ES owing to its low complexity and metric-learning ability for LSO
#   https://pypop.readthedocs.io/en/latest/es/lmmaes.html
from pypop7.optimizers.es.lmmaes import LMMAES
# define all the necessary algorithm options (which differ among different optimizers)
options = {'fitness_threshold': 1e-10,  # terminate when the best-so-far fitness is lower than this threshold
           'max_runtime': 3600,  # 1 hours (terminate when the actual runtime exceeds it)
           'seed_rng': 0,  # seed of random number generation (which must be explicitly set for repeatability)
           'x': 4.0*np.ones((ndim_problem,)),  # initial mean of search (mutation/sampling) distribution
           'sigma': 3.0,  # initial global step-size of search distribution (not necessarily optimal)
           'verbose': 500}
lmmaes = LMMAES(problem, options)  # initialize the optimizer
results = lmmaes.optimize()  # run its (time-consuming) search process
print(results)

Note that for PyPop7, the number 7 is added just because pypop has been registered by other in PyPI. The icon butterfly for PyPop7 is used to respect to the book (a complete variorum edition) of Fisher, "the greatest of Darwin's successors": The Genetical Theory of Natural Selection (where four butterflies were drawn in its cover), which inspired the proposal of Genetic Algorithms (GA).

For a list of public use cases of PyPop7, see this online document for more details. For new/missed black-box optimizers, we provide a unified API interface to freely add them if they satisfy the following design philosophy (see development-guide for details).

A Large Number of Black-Box Optimizers (BBO)

Note that Ant Colony Optimization (ACO) and Tabu Search (TS) are not covered in this open-source library, since they work mainly in discrete/combinatorial search spaces. Furthermore, brute-force search (exhaustive/grid search) is also excluded here, since it works only for very low (typically < 10) dimensions. In the near future version, we will consider adding Simultaneous Perturbation Stochastic Approximation (SPSA) into this open-source library.

---

• : indicates the specific BBO version for LSO (dimension >= 1000).
• : indicates the competitive (or de facto) BBO version for small/medium-dimensional problems (though it may work well under certain LSO circumstances).
• : indicates the baseline BBO version mainly for theoretical interest, owing to its simplicity (relatively ease to mathematical analysis).

Note that this classification based on only the dimension of objective function is just a rough estimation for algorithm selection. In practice, perhaps the simplest way to algorithm selection is trial-and-error or to try more advanced Automated Algorithm Selection techniques.

---

• Evolution Strategies (ES) [e.g., Ollivier et al., 2017, JMLR; Hansen et al., 2015; Bäck et al., 2013; Rudolph, 2012; Beyer&Schwefel, 2002; Rechenberg, 1989; Schwefel, 1984]
  • Mixture Model-based Evolution Strategy (MMES) [He et al., 2021, TEVC]
  • Fast Covariance Matrix Adaptation Evolution Strategy (FCMAES) [Li et al., 2020, TCYB; Li&Zhang, 2016, PPSN]
  • Limited-Memory Matrix Adaptation Evolution Strategy (LMMAES) [Loshchilov et al., 2019, TEVC]
  • Limited Memory Covariance Matrix Adaptation (LMCMA) [Loshchilov, 2017, ECJ]
    • Limited Memory Covariance Matrix Adaptation Evolution Strategy (LMCMAES) [Loshchilov, 2014, GECCO]
  • Rank-M Evolution Strategy (RMES) [Li&Zhang, 2018, TEVC]
    • Rank-One Evolution Strategy (R1ES) [Li&Zhang, 2018, TEVC]
  • Projection-based Covariance Matrix Adaptation (VKDCMA) [Akimoto&Hansen, 2016, PPSN; Akimoto&Hansen, 2016, GECCO]
    • Linear Covariance Matrix Adaptation (VDCMA) [Akimoto et al., 2014, GECCO]
  • Cholesky-CMA-ES-2016 (CCMAES2016) [Krause et al., 2016, NeurIPS]
    • (1+1)-Active-Cholesky-CMA-ES-2015 (OPOA2015) [Krause&Igel, 2015, FOGA]
    • (1+1)-Active-Cholesky-CMA-ES (OPOA2010) [Arnold&Hansen, 2010, GECCO]
  • Cholesky-CMA-ES (CCMAES2009) [Suttorp et al., 2009, MLJ]
    • (1+1)-Cholesky-CMA-ES-2009 (OPOC2009) [Suttorp et al., 2009, MLJ]
    • (1+1)-Cholesky-CMA-ES (OPOC2006) [Igel et al., 2006, GECCO]
  • Separable Covariance Matrix Adaptation Evolution Strategy (SEPCMAES) [Bäck et al., 2013; Ros&Hansen, 2008, PPSN]
  • Diagonal Decoding Covariance Matrix Adaptation (DDCMA) [Akimoto&Hansen, 2020, ECJ]
  • Matrix Adaptation Evolution Strategy (MAES) [Beyer&Sendhoff, 2017, TEVC]
    • Fast Matrix Adaptation Evolution Strategy (FMAES) [Beyer, 2020, GECCO; Loshchilov et al., 2019, TEVC]
  • Covariance Matrix Adaptation Evolution Strategy (CMAES) [e.g. Hansen, 2016; Hansen et al., 2003, ECJ; Hansen et al., 2001, ECJ; Hansen&Ostermeier, 1996, CEC]
  • Self-Adaptation Matrix Adaptation Evolution Strategy (SAMAES) [Beyer, 2020, GECCO]
    • Self-Adaptation Evolution Strategy (SAES) [e.g. Beyer, 2020, GECCO; Beyer, 2007, Scholarpedia]
    • Cumulative Step-size Adaptation Evolution Strategy (CSAES) [e.g. Hansen et al., 2015; Ostermeier et al., 1994, PPSN]
    • Derandomized Self-Adaptation Evolution Strategy (DSAES) [e.g. Hansen et al., 2015; Ostermeier et al., 1994, ECJ]
    • Schwefel's Self-Adaptation Evolution Strategy (SSAES) [e.g. Hansen et al., 2015; Beyer&Schwefel, 2002; Schwefel, 1988; Schwefel, 1984, AOR]
    • Rechenberg's (1+1)-Evolution Strategy with 1/5th success rule (RES) [e.g. Hansen et al., 2015; Kern et al., 2004; Rechenberg, 1989; Rechenberg, 1984; Schumer&Steiglitz, 1968, TAC]
• Natural Evolution Strategies (NES) [e.g. Wierstra et al., 2014, JMLR; Yi et al., 2009, ICML; Wierstra et al., 2008, CEC]
  • Rank-One Natural Evolution Strategy (R1NES) [Sun et al., 2013, GECCO]
  • Separable Natural Evolution Strategy (SNES) [Schaul et al., 2011, GECCO]
  • Exponential Natural Evolution Strategies (XNES) [e.g. Glasmachers et al., 2010, GECCO]
  • Exact Natural Evolution Strategy (ENES) [e.g. Sun et al., 2009, ICML]
  • Original Natural Evolution Strategy (ONES) [e.g. Wierstra et al., 2008, CEC]
  • Search Gradient-based Evolution Strategy (SGES) [e.g. Wierstra et al., 2008, CEC]
• Estimation of Distribution Algorithms (EDA) [e.g. Brookes et al., 2020, GECCO; Larrañaga&Lozano, 2002; Pelikan et al., 2002; Mühlenbein&Paaß, 1996, PPSN; Baluja&Caruana, 1995, ICML]
  • Random-Projection Estimation of Distribution Algorithm (RPEDA) [Kabán et al., 2016, ECJ]
  • Univariate Marginal Distribution Algorithm (UMDA) [e.g. Larrañaga&Lozano, 2002; Mühlenbein, 1997, ECJ]
  • Adaptive Estimation of Multivariate Normal Algorithm (AEMNA)[Larrañaga&Lozano, 2002]
  • Estimation of Multivariate Normal Algorithm (EMNA) [e.g. Larrañaga&Lozano, 2002]
• Cross-Entropy Method (CEM) [e.g. Rubinstein&Kroese, 2016; Hu et al., 2007, OR; Kroese et al., 2006, MCAP; De Boer et al., 2005, AOR; Rubinstein&Kroese, 2004]
  • Differentiable Cross-Entropy Method (DCEM) [Amos&Yarats, 2020, ICML]
  • Dynamic-Smoothing Cross-Entropy Method (DSCEM) [e.g. Kroese et al., 2006, MCAP]
  • Model Reference Adaptive Search (MRAS) [e.g. Hu et al., 2007, OR]
  • Standard Cross-Entropy Method (SCEM) [e.g. Kroese et al., 2006, MCAP]
• Differential Evolution (DE) [e.g. Price, 2013; Price et al., 2005; Storn&Price, 1997, JGO]
  • Success-History based Adaptive Differential Evolution (SHADE) [Tanabe&Fukunaga, 2013, CEC]
  • Adaptive Differential Evolution (JADE) [Zhang&Sanderson, 2009, TEVC]
  • Composite Differential Evolution (CODE) [Wang et al., 2011, TEVC]
  • Trigonometric-mutation Differential Evolution (TDE) [Fan&Lampinen, 2003, JGO]
  • Classic Differential Evolution (CDE) [e.g. Storn&Price, 1997, JGO]
• Particle Swarm Optimizer (PSO) [e.g. Fornasier et al., 2021, JMLR; Bonyadi&Michalewicz, 2017, ECJ; Rahmat-Samii et al., 2012, PIEEE; Escalante et al., 2009, JMLR; Dorigo et al., 2008; Poli et al., 2007, SI; Shi&Eberhart, 1998, CEC; Kennedy&Eberhart, 1995, ICNN]
  • Cooperative Coevolving Particle Swarm Optimizer (CCPSO2) [Li&Yao, 2012, TEVC]
  • Incremental Particle Swarm Optimizer (IPSO) [de Oca et al., 2011, TSMCB]
  • Comprehensive Learning Particle Swarm Optimizer (CLPSO) [Liang et al., 2006, TEVC]
  • Cooperative Particle Swarm Optimizer (CPSO) [Van den Bergh&Engelbrecht, 2004, TEVC]
  • Standard Particle Swarm Optimizer with a Local (ring) topology (SPSOL) [e.g. Shi&Eberhart, 1998, CEC; Kennedy&Eberhart, 1995, ICNN]
  • Standard Particle Swarm Optimizer with a global topology (SPSO) [e.g. Shi&Eberhart, 1998, CEC; Kennedy&Eberhart, 1995, ICNN]
• Cooperative Co-evolution (CC) [e.g. Gomez et al., 2008, JMLR; Panait et al., 2008, JMLR; Moriarty&Miikkulainen, 1995, ICML; Potter&De Jong, 1994, PPSN]
  • Hierarchical Cooperative Co-evolution (HCC) [Mei et al., 2016, ACM-TOMS; Gomez&Schmidhuber, 2005, ACM-GECCO]
  • CoOperative CO-evolutionary Covariance Matrix Adaptation (COCMA) [Mei et al., 2016, ACM-TOMS; Potter&De Jong, 1994, PPSN]
  • CoOperative co-Evolutionary Algorithm (COEA) [e.g. Panait et al., 2008, JMLR; Potter&De Jong, 1994, PPSN]
  • CoOperative SYnapse NeuroEvolution (COSYNE) [Gomez et al., 2008, JMLR; Moriarty&Miikkulainen, 1995, ICML]
• Simulated Annealing (SA) [see e.g. Bertsimas&Tsitsiklis, 1993, Statistical Science; Kirkpatrick et al., 1983, Science; Hastings, 1970, Biometrika; Metropolis et al., 1953, JCP]
  • Enhanced Simulated Annealing (ESA) [Siarry et al., 1997, ACM-TOMS]
  • Corana et al.' Simulated Annealing (CSA) [Corana et al., 1987, ACM-TOMS]
  • Noisy Simulated Annealing (NSA) [Bouttier&Gavra, 2019, JMLR]
• Genetic Algorithms (GA) [e.g. Forrest, 1993, Science; Holland, 1973, SICOMP; Holland, 1962, JACM]
  • Active Subspace Genetic Algorithm (ASGA) [Demo et al., 2021, SISC]
  • Global and Local genetic algorithm (GL25) [García-Martínez et al., 2008, EJOR]
  • Generalized Generation Gap with Parent-Centric Recombination (G3PCX) [Deb et al., 2002, ECJ]
  • GENetic ImplemenTOR (GENITOR) [e.g. Whitley et al., 1993, MLJ]
• Evolutionary Programming (EP) [e.g. Yao et al., 1999, TEVC; Fogel, 1994, Statistics and Computing]
  • Lévy distribution based Evolutionary Programming (LEP) [Lee&Yao, 2004, TEVC]
  • Fast Evolutionary Programming (FEP) [Yao et al., 1999, TEVC]
  • Classical Evolutionary Programming (CEP) [e.g. Yao et al., 1999, TEVC; Bäck&Schwefel, 1993, ECJ]
• Direct Search (DS) [e.g. Powell, 1998, Acta-Numerica; Wright, 1996; Hooke&Jeeves, 1961, JACM]
  • Powell's search method (POWELL) [SciPy; Powell, 1964, Computer]
  • Generalized Pattern Search (GPS) [Kochenderfer&Wheeler, 2019; Torczon, 1997, SIAM-JO]
  • Nelder-Mead simplex method (NM) [Dean et al., 1975, Science; Nelder&Mead, 1965, Computer]
  • Hooke-Jeeves direct search method (HJ) [Kochenderfer&Wheeler, 2019; Kaupe, 1963, CACM; Hooke&Jeeves, 1961, JACM]
  • Coordinate Search (CS) [Torczon, 1997, SIAM-JO; Fermi&Metropolis, 1952]
• Random (stochastic) Search (RS) [e.g. Murphy, 2023; Gao&Sener, 2022, ICML; Russell&Norvig, 2021; Nesterov&Spokoiny, 2017, FoCM; Bergstra&Bengio, 2012, JMLR; Schmidhuber et al., 2001; Cvijović&Klinowski, 1995, Science; Rastrigin, 1986; Solis&Wets, 1981, MOOR; Brooks, 1958, OR]
  • BErnoulli Smoothing (BES) [Gao&Sener, 2022, ICML]
  • Gaussian Smoothing (GS) [Nesterov&Spokoiny, 2017, FoCM]
  • Simple Random Search (SRS) [Rosenstein&Barto, 2001, IJCAI]
  • Annealed Random Hill Climber (ARHC) [e.g. Russell&Norvig, 2021; Schaul et al., 2010, JMLR]
  • Random Hill Climber (RHC) [e.g. Russell&Norvig, 2021; Schaul et al., 2010, JMLR]
  • Pure Random Search (PRS) [e.g. Bergstra&Bengio, 2012, JMLR; Schmidhuber et al., 2001; Brooks, 1958, OR]

Design Philosophy

Given a large number of (black-box) optimizers which keep increasing almost every day, we need some (possibly) widely acceptable criteria to select from them, as presented below in details:

• Respect for Beauty (Elegance)

  From the problem-solving perspective, we empirically prefer to choose the best optimizer for the black-box optimization problem at hand. For the new problem, however, the best optimizer is often unknown in advance (when without a prior knowledge). As a rule of thumb, we need to compare a (often small) set of available/well-known optimizers and finally choose the best one according to some predefined performance criteria. From the academic research perspective, however, we prefer so-called beautiful optimizers, though always keeping the No Free Lunch Theorems in mind. Typically, the beauty of one optimizer comes from the following attractive features: model novelty, competitive performance on at least one class of real-world problems, theoretical insights (e.g., convergence), clarity/simplicity for understanding and implementation, and repeatability.

  If you find any to meet the above standard, welcome to launch issues or pulls or discussions. We will consider it to be included in the pypop7 library as soon as possible, if possible. Note that any superficial imitation to well-established optimizers (i.e. Old Wine in a New Bottle) will be NOT considered here. Sometimes, several very complex optimizers could obtain the top rank on some competitions consisting of only artificially-constructed benchmark functions. However, these optimizers may become over-skilled on these artifacts. In our opinions, a good optimizer should be elegant and generalizable. If there is no persuasive real-world application reported for it, we will not consider any very complex optimizer in this library, in order to avoid the possible repeatability and overfitting issues.

• Respect for Diversity

  Given the universality of black-box optimization (BBO) in science and engineering, different research communities have designed different optimizers/methods. The type and number of optimizers are continuing to increase as the more powerful optimizers are always desirable for new and more challenging applications. On the one hand, some of these methods may share more or less similarities. On the other hand, they may also show significant differences (w.r.t. motivations / objectives / implementations / communities / practitioners). Therefore, we hope to cover such a diversity from different research communities such as artificial intelligence (particularly machine learning evolutionary computation and zeroth-order optimization), mathematical optimization/programming (particularly global optimization), operations research / management science, automatic control, electronic engineering, open-source software, physics, chemistry, and others.

• Respect for Originality

  For each optimizer included in PyPop7, we expect to give its original/representative reference (sometimes also including its good implementations/improvements). If you find some important references missed, please do NOT hesitate to contact us (and we will be happy to add it if necessary).

• Respect for Repeatability

  For randomized search, properly controlling randomness is very crucial to repeat numerical experiments. Here we follow the Random Sampling suggestions from NumPy. In other worlds, you must explicitly set the random seed for each optimizer. For more discussions about repeatability from machine learning, evolutionary computation, and metaheuristics communities, refer to the following papers, to name a few:

  • Swan, J., Adriaensen, S., Brownlee, A.E., Hammond, K., Johnson, C.G., Kheiri, A., Krawiec, F., Merelo, J.J., Minku, L.L., Özcan, E., Pappa, G.L., et al., 2022. Metaheuristics “in the large”. European Journal of Operational Research, 297(2), pp.393-406.
  • López-Ibáñez, M., Branke, J. and Paquete, L., 2021. Reproducibility in evolutionary computation. ACM Transactions on Evolutionary Learning and Optimization, 1(4), pp.1-21.
  • Sonnenburg, S., Braun, M.L., Ong, C.S., Bengio, S., Bottou, L., Holmes, G., LeCunn, Y., Muller, K.R., Pereira, F., Rasmussen, C.E., Ratsch, G., et al., 2007. The need for open source software in machine learning. Journal of Machine Learning Research, 8, pp.2443-2466.

Computational Efficiency

For LSO, computational efficiency is an indispensable performance criterion of DFO in the post-Moore era. To obtain high-performance computation as much as possible, NumPy is heavily used in this library as the base of numerical computation along with SciPy. Sometimes, Numba is also utilized, in order to further accelerate the wall-clock time.

References

For each algorithm family, we provide several representative applications published on some top-tier journals and conferences (such as, Nature, Science, PNAS, PRL, JACS, PIEEE, etc.).

• Derivative-Free Optimization (DFO)
  • Berahas, A.S., Cao, L., Choromanski, K. and Scheinberg, K., 2022. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, 22(2), pp.507-560.
  • Porcelli, M. and Toint, P.L., 2022. Exploiting problem structure in derivative free optimization. ACM Transactions on Mathematical Software, 48(1), pp.1-25.
  • Gao, K. and Sener, O., 2022, June. Generalizing Gaussian smoothing for random search. In International Conference on Machine Learning (pp. 7077-7101). PMLR.
  • Kochenderfer, M.J. and Wheeler, T.A., 2019. Algorithms for optimization. MIT Press.
  • Larson, J., Menickelly, M. and Wild, S.M., 2019. Derivative-free optimization methods. Acta Numerica, 28, pp.287-404.
  • Nesterov, Y., 2018. Lectures on convex optimization. Berlin: Springer International Publishing.
  • Nesterov, Y. and Spokoiny, V., 2017. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2), pp.527-566.
  • Conn, A.R., Scheinberg, K. and Vicente, L.N., 2009. Introduction to derivative-free optimization. Society for Industrial and Applied Mathematics.
• Evolutionary Computation (EC) [ [Box, 1957] ]
  • Eiben, A.E. and Smith, J., 2015. From evolutionary computation to the evolution of things. Nature, 521(7553), pp.476-482. [ http://www.evolutionarycomputation.org/ ]
  • Miikkulainen, R. and Forrest, S., 2021. A biological perspective on evolutionary computation. Nature Machine Intelligence, 3(1), pp.9-15.
  • Hansen, N. and Auger, A., 2014. Principled design of continuous stochastic search: From theory to practice. Theory and Principled Methods for the Design of Metaheuristics, pp.145-180.
  • De Jong, K.A., 2006. Evolutionary computation: A unified approach. MIT Press.
  • Beyer, H.G. and Deb, K., 2001. On self-adaptive features in real-parameter evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 5(3), pp.250-270.
  • Salomon, R., 1998. Evolutionary algorithms and gradient search: Similarities and differences. IEEE Transactions on Evolutionary Computation, 2(2), pp.45-55.
  • Fogel, D.B., 1998. Evolutionary computation: The fossil record. IEEE Press.
  • Wolpert, D.H. and Macready, W.G., 1997. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), pp.67-82.
  • Bäck, T. and Schwefel, H.P., 1993. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1), pp.1-23.
  • Forrest, S., 1993. Genetic algorithms: Principles of natural selection applied to computation. Science, 261(5123), pp.872-878.
  • Taxonomy
• Benchmarking [ benchmarking-network + iohprofiler ]
  • Kudela, J., 2022. A critical problem in benchmarking and analysis of evolutionary computation methods. Nature Machine Intelligence, 4(12), pp.1238-1245.
  • Meunier, L., Rakotoarison, H., Wong, P.K., Roziere, B., Rapin, J., Teytaud, O., Moreau, A. and Doerr, C., 2022. Black-box optimization revisited: Improving algorithm selection wizards through massive benchmarking. IEEE Transactions on Evolutionary Computation, 26(3), pp.490-500.
  • Hansen, N., Auger, A., Ros, R., Mersmann, O., Tušar, T. and Brockhoff, D., 2021. COCO: A platform for comparing continuous optimizers in a black-box setting. Optimization Methods and Software, 36(1), pp.114-144.
  • Auger, A. and Hansen, N., 2021, July. Benchmarking: State-of-the-art and beyond. In Proceedings of Genetic and Evolutionary Computation Conference Companion (pp. 339-340). ACM.
  • Varelas, K., El Hara, O.A., Brockhoff, D., Hansen, N., Nguyen, D.M., Tušar, T. and Auger, A., 2020. Benchmarking large-scale continuous optimizers: The bbob-largescale testbed, a COCO software guide and beyond. Applied Soft Computing, 97, p.106737.
  • Hansen, N., Ros, R., Mauny, N., Schoenauer, M. and Auger, A., 2011. Impacts of invariance in search: When CMA-ES and PSO face ill-conditioned and non-separable problems. Applied Soft Computing, 11(8), pp.5755-5769.
  • Moré, J.J. and Wild, S.M., 2009. Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1), pp.172-191.
  • Whitley, D., Rana, S., Dzubera, J. and Mathias, K.E., 1996. Evaluating evolutionary algorithms. Artificial Intelligence, 85(1-2), pp.245-276.
  • Salomon, R., 1996. Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms. BioSystems, 39(3), pp.263-278.
  • Fogel, D.B. and Beyer, H.G., 1995. A note on the empirical evaluation of intermediate recombination. Evolutionary Computation, 3(4), pp.491-495.
  • Moré, J.J., Garbow, B.S. and Hillstrom, K.E., 1981. Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 7(1), pp.17-41.
• Evolution Strategy (ES) [ A visual guide to ES + [Li et al., 2020] + [Akimoto&Hansen, 2022, GECCO-Companion] ]
  • Akimoto, Y., Auger, A., Glasmachers, T. and Morinaga, D., 2022. Global linear convergence of evolution strategies on more than smooth strongly convex functions. SIAM Journal on Optimization, 32(2), pp.1402-1429.
  • Glasmachers, T. and Krause, O., 2022. Convergence analysis of the Hessian estimation evolution strategy. ECJ, 30(1), pp.27-50.
  • He, X., Zheng, Z. and Zhou, Y., 2021. MMES: Mixture model-based evolution strategy for large-scale optimization. IEEE-TEVC, 25(2), pp.320-333.
  • Akimoto, Y. and Hansen, N., 2020. Diagonal acceleration for covariance matrix adaptation evolution strategies. ECJ, 28(3), pp.405-435.
  • Beyer, H.G., 2020, July. Design principles for matrix adaptation evolution strategies. In ACM-GECCO Companion (pp. 682-700). ACM.
  • Choromanski, K., Pacchiano, A., Parker-Holder, J. and Tang, Y., 2019. From complexity to simplicity: Adaptive es-active subspaces for blackbox optimization. In NeurIPS.
  • Varelas, K., Auger, A., Brockhoff, D., Hansen, N., ElHara, O.A., Semet, Y., Kassab, R. and Barbaresco, F., 2018, September. A comparative study of large-scale variants of CMA-ES. In PPSN (pp. 3-15). Springer, Cham.
  • Li, Z. and Zhang, Q., 2018. A simple yet efficient evolution strategy for large-scale black-box optimization. IEEE-TEVC, 22(5), pp.637-646.
  • Lehman, J., Chen, J., Clune, J. and Stanley, K.O., 2018, July. ES is more than just a traditional finite-difference approximator. In ACM-GECCO (pp. 450-457). ACM.
  • Ollivier, Y., Arnold, L., Auger, A. and Hansen, N., 2017. Information-geometric optimization algorithms: A unifying picture via invariance principles. Journal of Machine Learning Research, 18(18), pp.1-65.
  • Loshchilov, I., 2017. LM-CMA: An alternative to L-BFGS for large-scale black box optimization. ECJ, 25(1), pp.143-171. [ Loshchilov, I., 2014, July. A computationally efficient limited memory CMA-ES for large scale optimization. In ACM-GECCO (pp. 397-404). ACM. ] + [ Loshchilov, I., Glasmachers, T. and Beyer, H.G., 2019. Large scale black-box optimization by limited-memory matrix adaptation. IEEE-TEVC, 23(2), pp.353-358. ]
  • Beyer, H.G. and Sendhoff, B., 2017. Simplify your covariance matrix adaptation evolution strategy. IEEE Transactions on Evolutionary Computation, 21(5), pp.746-759.
  • Krause, O., Arbonès, D.R. and Igel, C., 2016. CMA-ES with optimal covariance update and storage complexity. In Advances in Neural Information Processing Systems, 29, pp.370-378.
  • Akimoto, Y. and Hansen, N., 2016, July. Projection-based restricted covariance matrix adaptation for high dimension. In Proceedings of Annual Conference on Genetic and Evolutionary Computation (pp. 197-204). ACM.
  • Auger, A. and Hansen, N., 2016. Linear convergence of comparison-based step-size adaptive randomized search via stability of Markov chains. SIAM Journal on Optimization, 26(3), pp.1589-1624.
  • Krause, O. and Igel, C., 2015, January. A more efficient rank-one covariance matrix update for evolution strategies. In Proceedings of ACM Conference on Foundations of Genetic Algorithms (pp. 129-136). ACM.
  • Hansen, N., Arnold, D.V. and Auger, A., 2015. Evolution strategies. In Springer Handbook of Computational Intelligence (pp. 871-898). Springer, Berlin, Heidelberg.
  • Diouane, Y., Gratton, S. and Vicente, L.N., 2015. Globally convergent evolution strategies. Mathematical Programming, 152(1), pp.467-490.
  • Hansen, N., Atamna, A. and Auger, A., 2014, September. How to assess step-size adaptation mechanisms in randomised search. In International Conference on Parallel Problem Solving from Nature (pp. 60-69). Springer, Cham.
  • Akimoto, Y., Auger, A. and Hansen, N., 2014, July. Comparison-based natural gradient optimization in high dimension. In Proceedings of Annual Conference on Genetic and Evolutionary Computation (pp. 373-380). ACM.
  • Hansen, N. and Auger, A., 2014. Principled design of continuous stochastic search: From theory to practice. In Theory and Principled Methods for the Design of Metaheuristics (pp. 145-180). Springer, Berlin, Heidelberg.
  • Bäck, T., Foussette, C. and Krause, P., 2013. Contemporary evolution strategies. Berlin: Springer.
  • Rudolph, G., 2012. Evolutionary strategies. In Handbook of Natural Computing (pp. 673-698). Springer Berlin, Heidelberg.
  • Akimoto, Y., Nagata, Y., Ono, I. and Kobayashi, S., 2012. Theoretical foundation for CMA-ES from information geometry perspective. Algorithmica, 64(4), pp.698-716.
  • Akimoto, Y., 2011. Design of evolutionary computation for continuous optimization. Doctoral Dissertation, Tokyo Institute of Technology.
  • Akimoto, Y., Nagata, Y., Ono, I. and Kobayashi, S., 2010, September. Bidirectional relation between CMA evolution strategies and natural evolution strategies. In International Conference on Parallel Problem Solving from Nature (pp. 154-163). Springer, Berlin, Heidelberg.
  • Arnold, D.V. and Hansen, N., 2010, July. Active covariance matrix adaptation for the (1+1)-CMA-ES. In Proceedings of Annual Conference on Genetic and Evolutionary Computation (pp. 385-392). ACM.
  • Suttorp, T., Hansen, N. and Igel, C., 2009. Efficient covariance matrix update for variable metric evolution strategies. Machine Learning, 75(2), pp.167-197.
  • Arnold, D.V. and MacLeod, A., 2006, July. Hierarchically organised evolution strategies on the parabolic ridge. In Proceedings of Annual Conference on Genetic and Evolutionary Computation (pp. 437-444). ACM.
  • Igel, C., Suttorp, T. and Hansen, N., 2006, July. A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies. In Proceedings of Annual Conference on Genetic and Evolutionary Computation (pp. 453-460). ACM.
  • Auger, A. and Hansen, N., 2005, September. A restart CMA evolution strategy with increasing population size. In IEEE Congress on Evolutionary Computation (pp. 1769-1776). IEEE.
  • Beyer, H.G. and Schwefel, H.P., 2002. Evolution strategies–A comprehensive introduction. Natural Computing, 1(1), pp.3-52.
  • Hansen, N. and Ostermeier, A., 1996, May. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Proceedings of IEEE International Conference on Evolutionary Computation (pp. 312-317). IEEE. [ Hansen, N. and Ostermeier, A., 2001. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2), pp.159-195. ] + [ Hansen, N., Müller, S.D. and Koumoutsakos, P., 2003. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1), pp.1-18. ]
  • Rudolph, G., 1992. On correlated mutations in evolution strategies. In International Conference on Parallel Problem Solving from Nature (pp. 105-114).
  • Schwefel, H.P., 1984. Evolution strategies: A family of non-linear optimization techniques based on imitating some principles of organic evolution. Annals of Operations Research, 1(2), pp.165-167. [ Schwefel, H.P., 1988. Collective intelligence in evolving systems. In Ecodynamics (pp. 95-100). Springer, Berlin, Heidelberg. ]
  • Rechenberg, I., 1984. The evolution strategy. A mathematical model of darwinian evolution. In Synergetics—from Microscopic to Macroscopic Order (pp. 122-132). Springer, Berlin, Heidelberg. [ Rechenberg, I., 1989. Evolution strategy: Nature’s way of optimization. In Optimization: Methods and Applications, Possibilities and Limitations (pp. 106-126). Springer, Berlin, Heidelberg. ]
  • Applications: e.g., Lee et al., 2023, Science Robotics; Koginov et al., 2023, IEEE-TMRB; Sun et al., 2023, ACL; Deng et al., 2023; Zhang et al., 2023, NeurIPS; Tjanaka et al., 2023, IEEE-LRA; Yu et al., 2023, IJCAI; Zhu et al., 2023, IEEE/ASME-TMECH; Fadini et al., 2023; Ma et al., 2023; Kim et al., 2023, Science Robotics; Slade et al., 2022, Nature; Sun et al., 2022, ICML; Tjanaka et al., 2022, GECCO; Wang&Ponce, 2022, GECCO, Tian&Ha, 2022, EvoStar; Hansel et al., 2021; Anand et al., 2021, MLST; Nomura et al., 2021, AAAI; Zheng et al., 2021, IEEE-ASRU; Liu et al., 2019, AAAI; Dong et al., 2019, CVPR; Ha&Schmidhuber, 2018, NeurIPS; Müller&Glasmachers, 2018, PPSN; Chrabąszcz et al., 2018, IJCAI; OpenAI, 2017; Zhang et al., 2017, Science; Agrawal et al., 2014, TVCG; Heidrich-Meisner&Igel, 2009, ICML; Lipson&Pollack, 2000, Nature; Wiesmann et al., 1998, IEEE-TEVC.
• Natural Evolution Strategies (NES)
  • Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J. and Schmidhuber, J., 2014. Natural evolution strategies. Journal of Machine Learning Research, 15(1), pp.949-980.
  • Schaul, T., 2011. Studies in continuous black-box optimization. Doctoral Dissertation, Technische Universität München.
  • Yi, S., Wierstra, D., Schaul, T. and Schmidhuber, J., 2009, June. Stochastic search using the natural gradient. In Proceedings of International Conference on Machine Learning (pp. 1161-1168).
  • Wierstra, D., Schaul, T., Peters, J. and Schmidhuber, J., 2008, June. Natural evolution strategies. In IEEE Congress on Evolutionary Computation (pp. 3381-3387). IEEE.
  • Applications: e.g., Yu et al., USENIX Security; Flageat et al., 2023; Yan et al., 2023; Feng et al., 2023; Wei et al., 2022, IJCV; Agarwal et al., 2022, ICRA; Farid et al., 2022, CoRL; Feng et al., 2022, CVPR; Berliner et al., 2022, ICLR; Kirsch et al., 2022, AAAI; Jain et al., 2022, USENIX Security; Ilyas et al., 2018, ICML.
• Estimation of Distribution Algorithm (EDA) [ MIMIC [NeurIPS-1996] + BOA [GECCO-1999] + [ECJ-2005] ]
  • Brookes, D., Busia, A., Fannjiang, C., Murphy, K. and Listgarten, J., 2020, July. A view of estimation of distribution algorithms through the lens of expectation-maximization. In Proceedings of Genetic and Evolutionary Computation Conference Companion (pp. 189-190). ACM.
  • Kabán, A., Bootkrajang, J. and Durrant, R.J., 2016. Toward large-scale continuous EDA: A random matrix theory perspective. Evolutionary Computation, 24(2), pp.255-291.
  • Pelikan, M., Hauschild, M.W. and Lobo, F.G., 2015. Estimation of distribution algorithms. In Springer Handbook of Computational Intelligence (pp. 899-928). Springer, Berlin, Heidelberg.
  • Dong, W., Chen, T., Tiňo, P. and Yao, X., 2013. Scaling up estimation of distribution algorithms for continuous optimization. IEEE Transactions on Evolutionary Computation, 17(6), pp.797-822.
  • Hauschild, M. and Pelikan, M., 2011. An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation, 1(3), pp.111-128.
  • Teytaud, F. and Teytaud, O., 2009, July. Why one must use reweighting in estimation of distribution algorithms. In Proceedings of ACM Annual Conference on Genetic and Evolutionary Computation (pp. 453-460).
  • Larrañaga, P. and Lozano, J.A. eds., 2001. Estimation of distribution algorithms: A new tool for evolutionary computation. Springer Science & Business Media.
  • Mühlenbein, H., 1997. The equation for response to selection and its use for prediction. Evolutionary Computation, 5(3), pp.303-346.
  • Baluja, S. and Caruana, R., 1995. Removing the genetics from the standard genetic algorithm. In International Conference on Machine Learning (pp. 38-46). Morgan Kaufmann.
• Cross-Entropy Method (CEM)
  • Pinneri, C., Sawant, S., Blaes, S., Achterhold, J., Stueckler, J., Rolinek, M. and Martius, G., 2021, October. Sample-efficient cross-entropy method for real-time planning. In Conference on Robot Learning (pp. 1049-1065). PMLR.
  • Amos, B. and Yarats, D., 2020, November. The differentiable cross-entropy method. In International Conference on Machine Learning (pp. 291-302). PMLR.
  • Rubinstein, R.Y. and Kroese, D.P., 2016. Simulation and the Monte Carlo method (Third Edition). John Wiley & Sons.
  • Hu, J., Fu, M.C. and Marcus, S.I., 2007. A model reference adaptive search method for global optimization. Operations Research, 55(3), pp.549-568.
  • De Boer, P.T., Kroese, D.P., Mannor, S. and Rubinstein, R.Y., 2005. A tutorial on the cross-entropy method. Annals of Operations Research, 134(1), pp.19-67.
  • Rubinstein, R.Y. and Kroese, D.P., 2004. The cross-entropy method: A unified approach to combinatorial optimization, Monte-Carlo simulation, and machine learning. New York: Springer.
  • Mannor, S., Rubinstein, R.Y. and Gat, Y., 2003. The cross entropy method for fast policy search. In Proceedings of International Conference on Machine Learning (pp. 512-519).
  • Applications: e.g., Wang&Ba,2020, ICLR; Hafner et al., 2019, ICML; Pourchot&Sigaud, 2019, ICLR; Simmons-Edler et al., 2019, ICML-RL4RealLife; Chua et al., 2018, NeurIPS; Duan et al., 2016, ICML; Kobilarov, 2012, IJRR.
• Differential Evolution (DE)
  • Price, K.V., 2013. Differential evolution. In Handbook of Optimization (pp. 187-214). Springer, Berlin, Heidelberg.
  • Tanabe, R. and Fukunaga, A., 2013, June. Success-history based parameter adaptation for differential evolution. In IEEE Congress on Evolutionary Computation (pp. 71-78). IEEE.
  • Wang, Y., Cai, Z., and Zhang, Q. 2011. Differential evolution with composite trial vector generation strategies and control parameters. IEEE Transactions on Evolutionary Computation, 15(1), pp.55–66.
  • Zhang, J., and Sanderson, A. C. 2009. JADE: Adaptive differential evolution with optional external archive. IEEE Transactions on Evolutionary Computation, 13(5), pp.945–958.
  • Price, K.V., Storn, R.M. and Lampinen, J.A., 2005. Differential evolution: A practical approach to global optimization. Springer Science & Business Media.
  • Fan, H.Y. and Lampinen, J., 2003. A trigonometric mutation operation to differential evolution. Journal of Global Optimization, 27(1), pp.105-129.
  • Storn, R.M. and Price, K.V. 1997. Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), pp.341–359.
  • Applications: e.g., Higgins et al., 2023, Science; McNulty et al., 2023, PRL; Koob et al., 2023, Psychological Review; Colombo et al., 2023, Sci. Adv.; Lichtinger&Biggin, 2023, JCTC; Liang et al., 2023, NSDI; Shinn et al., 2023, Nature Neuroscience; Schad et al., 2023, ApJ; Hoyer et al., 2023, MNRAS; Hoyer et al., 2023, ApJL; Abdelnabi&Fritz, 2023,USENIX Security; Kotov et al., 2023, Cell Reports; Sidhartha et al., 2023, CVPR; Hardy et al., 2023, MNRAS; Boucher et al., 2023; Michel et al., 2023, PRA; Woo et al., 2023, iScience; Bozkurt et al., 2023; Ma et al., 2023, KDD; Zhou et al., 2023; Czarnik et al., 2023; Katic et al., 2023, iScience; Khajehnejad et al., 2023, RSIF; Digman&Cornish, 2023, PRD; Rommel et al., 2023; Li et al., 2022, Science; Schlegelmilch et al., 2022, Psychological Review; Mackin et al., 2022, Nature Communications; Liu&Wang, 2022, JSAC; Zhou et al., 2022, Nature Computational Science; Fischer et al., 2022, TOCHI; Ido et al., 2022, npj Quantum Materials; Clark et al., 2022, NECO; Powell et al., 2022, ApJ; Vo et al., 2022, ICLR; Andersson et al., 2022, ApJ; Naudin et al., 2022, NECO; Perini et al., 2022, AAAI; Sterbentz et al., 2022, Physics of Fluids; Mishra et al., 2021, Science; Tiwari et al., 2021, PRB; Mok et al., 2021, Communications Physics; Vinker et al., 2021, CVPR; Mehta et al., 2021, JCAP; Trueblood et al., 2021, Psychological Review; Verdonck et al., 2021, Psychological Review; Robert et al., 2021, npj Quantum Information; Canton et al., 2021, ApJ; Leslie et al., 2021, PRD; Fengler et al., 2021, eLife; Li et al., 2021, TQE; Chen et al., 2021, ACS Photonics; Menczel et al., 2021, J. Phys. A: Math. Theor.; Feng et al., 2021, JSAC; DES Collaboration, 2021, A&A; An et al., 2020, PNAS; Su et al., 2019, TEVC; Laganowsky et al., 2014, Nature.
• Particle Swarm Optimizer (PSO) [ swarm intelligence | scholarpedia ]
  • Sünnen, P., 2023. Analysis of a consensus-based optimization method on hypersurfaces and applications. Doctoral dissertation, Technische Universität München.
  • Fornasier, M., Huang, H., Pareschi, L. and Sünnen, P., 2021. Consensus-based optimization on the sphere: Convergence to global minimizers and machine learning. Journal of Machine Learning Research, 22(1), pp.10722-10776.
  • Carrillo, J.A., Choi, Y.P., Totzeck, C. and Tse, O., 2018. An analytical framework for consensus-based global optimization method. Mathematical Models and Methods in Applied Sciences, 28(06), pp.1037-1066.
  • Blackwell, T. and Kennedy, J., 2018. Impact of communication topology in particle swarm optimization. IEEE Transactions on Evolutionary Computation, 23(4), pp.689-702.
  • Pinnau, R., Totzeck, C., Tse, O. and Martin, S., 2017. A consensus-based model for global optimization and its mean-field limit. Mathematical Models and Methods in Applied Sciences, 27(01), pp.183-204.
  • Bonyadi, M.R. and Michalewicz, Z., 2017. Particle swarm optimization for single objective continuous space problems: A review. Evolutionary Computation, 25(1), pp.1-54.
  • Escalante, H.J., Montes, M. and Sucar, L.E., 2009. Particle swarm model selection. Journal of Machine Learning Research, 10(15), pp.405−440.
  • Floreano, D. and Mattiussi, C., 2008. Bio-inspired artificial intelligence: Theories, methods, and technologies. MIT Press.
  • Poli, R., Kennedy, J. and Blackwell, T., 2007. Particle swarm optimization. Swarm Intelligence, 1(1), pp.33-57.
  • Venter, G. and Sobieszczanski-Sobieski, J., 2003. Particle swarm optimization. AIAA Journal, 41(8), pp.1583-1589.
  • Parsopoulos, K.E. and Vrahatis, M.N., 2002. Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, 1(2), pp.235-306.
  • Clerc, M. and Kennedy, J., 2002. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), pp.58-73.
  • Eberhart, R.C., Shi, Y. and Kennedy, J., 2001. Swarm intelligence. Elsevier.
  • Shi, Y. and Eberhart, R., 1998, May. A modified particle swarm optimizer. In IEEE World Congress on Computational Intelligence (pp. 69-73). IEEE.
  • Kennedy, J. and Eberhart, R., 1995, November. Particle swarm optimization. In Proceedings of International Conference on Neural Networks (pp. 1942-1948). IEEE.
  • Eberhart, R. and Kennedy, J., 1995, October. A new optimizer using particle swarm theory. In Proceedings of International Symposium on Micro Machine and Human Science (pp. 39-43). IEEE.
  • Interest Applications: e.g., Melis et al., 2024, Nature; Grabner et al., 2023, Nature Communications; Morselli et al., 2023, IEEE-TWC; Reddy et al., 2023, IEEE-TC; Zhang et al., 2022, CVPR; Yang et al., PRL, 2022; Guan et al., 2022, PRL; Zhong et al., 2022, CVPR; Singh&Hecke, 2021, PRL; Weiel, et al., 2021, Nature Mach. Intell; Wintermantel et al., 2020, PRL; Tang et al., 2019, TPAMI; Sheng et al., 2019, TPAMI; CMS Collaboration, 2019, JHEP; Wang et al., 2019, TVCG; Zhang et al., 2018, PRL; Leditzky et al., 2018, PRL; Pham et al., 2018, TPAMI; Villeneuve et al., 2017, Science; Choi et al., 2017, PRL; González-Echevarría, et al., 2017, TCAD; Zhu et al., 2017, PRL; Choi et al., 2017, ICCV; Pickup et al., 2016, IJCV; Li et al., 2015, PRL; Sharp et al., 2015, CHI; Taneja et al., 2015, TPAMI; Zhang et al., 2015, IJCV; Meyer et al., 2015, ICCV; Tompson et al., 2014, TOG; Baca et al., 2013, Cell; Li et al., PRL, 2013; Kawakami et al., 2013, IJCV; Kim et al., 2012, Nature; Rahmat-Samii et al., 2012, PIEEE; Oikonomidis et al., 2012, CVPR; Li et al., 2011, TPAMI; Zhao et al., 2011, PRL; Zhu et al., 2011, PRL; Lv et al., 2011, PRL; Hentschel&Sanders, 2010, PRL; Pontani&Conway, 2010, JGCD; Zhang et al., 2008, CVPR; Liebelt&Schertler, 2007, CVPR; Hassan et al., 2005, AIAA].
• Cooperative Coevolution (CC)
  • Gomez, F., Schmidhuber, J. and Miikkulainen, R., 2008. Accelerated neural evolution through cooperatively coevolved synapses. Journal of Machine Learning Research, 9(31), pp.937-965.
  • Panait, L., Tuyls, K. and Luke, S., 2008. Theoretical advantages of lenient learners: An evolutionary game theoretic perspective. Journal of Machine Learning Research, 9, pp.423-457.
  • Schmidhuber, J., Wierstra, D., Gagliolo, M. and Gomez, F., 2007. Training recurrent networks by evolino. Neural Computation, 19(3), pp.757-779.
  • Gomez, F.J. and Schmidhuber, J., 2005, June. Co-evolving recurrent neurons learn deep memory POMDPs. In Proceedings of Annual Conference on Genetic and Evolutionary Computation (pp. 491-498).
  • Fan, J., Lau, R. and Miikkulainen, R., 2003. Utilizing domain knowledge in neuroevolution. In International Conference on Machine Learning (pp. 170-177).
  • Potter, M.A. and De Jong, K.A., 2000. Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1), pp.1-29.
  • Gomez, F.J. and Miikkulainen, R., 1999, July. Solving non-Markovian control tasks with neuroevolution. In Proceedings of International Joint Conference on Artificial Intelligence (pp. 1356-1361).
  • Moriarty, D.E. and Mikkulainen, R., 1996. Efficient reinforcement learning through symbiotic evolution. Machine Learning, 22(1), pp.11-32.
  • Moriarty, D.E. and Miikkulainen, R., 1995. Efficient learning from delayed rewards through symbiotic evolution. In International Conference on Machine Learning (pp. 396-404). Morgan Kaufmann.
  • Potter, M.A. and De Jong, K.A., 1994, October. A cooperative coevolutionary approach to function optimization. In International Conference on Parallel Problem Solving from Nature (pp. 249-257). Springer, Berlin, Heidelberg.
• Simultaneous Perturbation Stochastic Approximation (SPSA) [ https://www.jhuapl.edu/SPSA/ ]
• Simulated Annealing (SA)
  • Bouttier, C. and Gavra, I., 2019. Convergence rate of a simulated annealing algorithm with noisy observations. Journal of Machine Learning Research, 20(1), pp.127-171.
  • Gerber, M. and Bornn, L., 2017. Improving simulated annealing through derandomization. Journal of Global Optimization, 68(1), pp.189-217.
  • Siarry, P., Berthiau, G., Durdin, F. and Haussy, J., 1997. Enhanced simulated annealing for globally minimizing functions of many-continuous variables. ACM Transactions on Mathematical Software, 23(2), pp.209-228.
  • Bertsimas, D. and Tsitsiklis, J., 1993. Simulated annealing. Statistical Science, 8(1), pp.10-15.
  • Corana, A., Marchesi, M., Martini, C. and Ridella, S., 1987. Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm. ACM Transactions on Mathematical Software, 13(3), pp.262-280. [ Corrigenda ]
  • Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P., 1983. Optimization by simulated annealing. Science, 220(4598), pp.671-680.
  • Hastings, W.K., 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), pp.97-109.
  • Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E., 1953. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6), pp.1087-1092.
  • Applications: e.g., Young et al., 2023, Nature; Kim et al., 2023, Nature; Passalacqua et al., 2023, Nature; Pronker et al., 2023, Nature; Sullivan&Seljak, 2023; Holm et al., 2023, Nature; Snyder et al., 2023, Nature; Samyak&Palacios, 2023, Biometrika; Bouchet et al., 2023, PNAS; Li&Yu, 2023, ACM-TOG; Zhao et al., 2023, VLDBJ; Zhong et al., 2023, IEEE/ACM-TASLP; Wang et al., 2023, IEEE-TMC; Filippo et al., 2023, IJCAI; Barnes et al., 2023, ApJ; Melo et al., 2023; Bruna et al., 2023; Holm et al., 2023; Jenson et al., 2023, Nature; Kolesov et al., 2016, IEEE-TPAMI
• Genetic Algorithm (GA)
  • Whitley, D., 2019. Next generation genetic algorithms: A user’s guide and tutorial. In Handbook of Metaheuristics (pp. 245-274). Springer, Cham.
  • Levine, D., 1997. Commentary—Genetic algorithms: A practitioner's view. INFORMS Journal on Computing, 9(3), pp.256-259.
  • Goldberg, D.E., 1994. Genetic and evolutionary algorithms come of age. Communications of the ACM, 37(3), pp.113-120.
  • Forrest, S., 1993. Genetic algorithms: Principles of natural selection applied to computation. Science, 261(5123), pp.872-878.
  • De Jong, K.A., 1993. Are genetic algorithms function optimizer?. Foundations of Genetic Algorithms, pp.5-17.
  • Mitchell, M., Holland, J. and Forrest, S., 1993. When will a genetic algorithm outperform hill climbing. Advances in Neural Information Processing Systems (pp. 51-58).
  • Holland, J.H., 1992. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. MIT Press.
  • Holland, J.H., 1992. Genetic algorithms. Scientific American, 267(1), pp.66-73.
  • Whitley, D., 1989, December. The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In Proceedings of International Conference on Genetic Algorithms (pp. 116-121).
  • Goldberg, D.E. and Holland, J.H., 1988. Genetic algorithms and machine learning. Machine Learning, 3(2), pp.95-99.
  • Holland, J.H., 1973. Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing, 2(2), pp.88-105.
  • Holland, J.H., 1962. Outline for a logical theory of adaptive systems. Journal of the ACM, 9(3), pp.297-314.
  • Applications: e.g., Wang, 2023, Harvard Ph.D. Dissertation; Lee et al., 2022, Science Robotics; Whitelam&Tamblyn, 2021, PRL; Walker et al., 2021, Nature Chemistry; Chen et al., 2020, Nature; Whitley et al., 1993, MLJ.
• Evolutionary Programming (EP)
  • Yao, X., Liu, Y. and Lin, G., 1999. Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation, 3(2), pp.82-102.
  • Fogel, D.B., 1999. An overview of evolutionary programming. In Evolutionary Algorithms (pp. 89-109). Springer, New York, NY.
  • Fogel, D.B. and Fogel, L.J., 1995, September. An introduction to evolutionary programming. In European Conference on Artificial Evolution (pp. 21-33). Springer, Berlin, Heidelberg.
  • Fogel, D.B., 1994. Evolutionary programming: An introduction and some current directions. Statistics and Computing, 4(2), pp.113-129.
  • Bäck, T. and Schwefel, H.P., 1993. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1), pp.1-23.
  • Applications: e.g., Hoorfar, 2007, IEEE-TAP; Cui et al., 2006, MS; Damavandi&Safavi-Naeini, 2005, IEEE-TCSI.
• Pattern Search
  • Audet, C., Le Digabel, S., Rochon Montplaisir, V. and Tribes, C., 2022. Algorithm XXXX: NOMAD version 4: Nonlinear optimization with the MADS algorithm. ACM Transactions on Mathematical Software.
  • Brent, R.P., 2013. Algorithms for minimization without derivatives. Courier Corporation.
  • Singer, S. and Nelder, J., 2009. Nelder-mead algorithm. Scholarpedia, 4(7), p.2928.
  • Kolda, T.G., Lewis, R.M. and Torczon, V., 2003. Optimization by direct search: New perspectives on some classical and modern methods. SIAM Review, 45(3), pp.385-482.
  • Lagarias, J.C., Reeds, J.A., Wright, M.H. and Wright, P.E., 1998. Convergence properties of the Nelder--Mead simplex method in low dimensions. SIAM Journal on Optimization, 9(1), pp.112-147.
  • Powell, M.J., 1998. Direct search algorithms for optimization calculations. Acta Numerica, 7, pp.287-336.
  • Torczon, V., 1997. On the convergence of pattern search algorithms. SIAM Journal on Optimization, 7(1), pp.1-25.
  • Barton, R.R. and Ivey Jr, J.S., 1996. Nelder-Mead simplex modifications for simulation optimization. Management Science, 42(7), pp.954-973.
  • Wright, M.H., 1996. Direct search methods: Once scorned, now respectable. Pitman Research Notes in Mathematics Series, pp.191-208.
  • Jones, D.R., Perttunen, C.D. and Stuckman, B.E., 1993. Lipschitzian optimization without the Lipschitz constant. Journal of Optimization Theory and Applications, 79(1), pp.157-181.
  • Nelder, J.A. and Mead, R., 1965. A simplex method for function minimization. The Computer Journal, 7(4), pp.308-313.
  • Powell, M.J., 1964. An efficient method for finding the minimum of a function of several variables without calculating derivatives. The Computer Journal, 7(2), pp.155-162.
  • Kaupe Jr, A.F., 1963. Algorithm 178: Direct search. Communications of the ACM, 6(6), pp.313-314.
  • Spang, III, H.A., 1962. A review of minimization techniques for nonlinear functions. SIAM Review, 4(4), pp.343-365.
  • Hooke, R. and Jeeves, T.A., 1961. “Direct search” solution of numerical and statistical problems. Journal of the ACM, 8(2), pp.212-229. [ Python - pymoo | This Week's Citation Classic ]
  • Box, G.E., 1957. Evolutionary operation: A method for increasing industrial productivity. Journal of the Royal Statistical Society: Series C (Applied Statistics), 6(2), pp.81-101.
  • Fermi, E. and Metropolis N., 1952. Numerical solution of a minimum problem. Los Alamos Scientific Lab., Los Alamos, NM.
    • Anderson, H.L., Davidon, W.C., Glicksman, M. and Kruse, U.E., 1955. Scattering of positive pions by hydrogen at 189 MeV. Physical Review, 100(1), p.279.
  • Applications: e.g., [NM: Gokhale et al., 2023, PNAS; Hayashi, 2022, Bernoulli; Vanunu et al., 2021, PNAS; Williams et al., 2021, PNAS; Fleishman et al., Science, 2020; Nanni et al., 2020, PNAS; Steinrücken et al., 2019, PNAS; Omran et al., 2019, Science; Sparrow et al., 2018, Nature; Prochazka&Vogl, 2017, PNAS; Murphy&Brincke, 2017, MS; Gillon et al., 2017, Nature; Aghaeepour et al., 2017, Science Immunol.; Sayegh et al., 2017, TS; Landis&Schraiber, 2017, PNAS; Kim et al., 2016, PNAS; Chan et al., 2014, MS; Chan et al., 2014, MKSC; Bajikar et al., 2014, PNAS; Lee et al., 2014, PNAS; Wang et al., 2012, PRL; Lau&Rubinstein, Nature, 2012; Brown et al., 2012, MS; Contreras et al., 2012, PNAS; Morlon et al., 2011, PNAS; Forstmann et al., 2010, PNAS; Balachander et al., 2009, MS; Jayanthi et al., 2009, MS; Farrell et al., 2009, PNAS; Forstmann et al., 2008, PNAS; Rouder et al., 2008, PNAS; Sapir et al., 2005, PNAS; Amonlirdviman et al., 2005, Science; Cowan et al., 2004, PS; Zhou et al., 2004, PS; Draganska&Jain, 2004, MS; Fain&Levitt, 2003, PNAS; Dennis et al., 2002, PNAS; Sudhir, 2001, MKSC; Rouder, 2001, PS; Wolszczan, 1994, Science; Polvani et al., 1990, Science; Lee et al., 1987, PNAS; Sabath et al., 1986, PNAS; Burch et al., 1985, PNAS; Regoeczi et al., 1982, PNAS; Brasseur et al., 1982, PNAS; Korn et al., 1981, Science; Dean et al., 1975, Science]; [HJ: Kalita et al., 2023, Nature; Washington et al, 2023; Huynh et al., 2023; Kucher et al., 2022, SPLC; Pepe et al., 2021, IEEE-TASLP; Khaledian et al., 2018, IEEE-TMTT; Luhar et al., 2015, JFM; Paxton et al., 2013, ApJS; Schneider&Excoffier, 1999, Genetics; Ditchfield et al., 1971, JCP].
• Random Search (RS)
  • Bergstra, J. and Bengio, Y., 2012. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13(2).
  • Nemirovski, A., Juditsky, A., Lan, G. and Shapiro, A., 2009. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4), pp.1574-1609.
  • Schmidhuber, J., Hochreiter, S. and Bengio, Y., 2001. Evaluating benchmark problems by random guessing. A Field Guide to Dynamical Recurrent Networks, pp.231-235.
  • Rosenstein, M.T. and Barto, A.G., 2001, August. Robot weightlifting by direct policy search. In International Joint Conference on Artificial Intelligence (pp. 839-846).
  • Cvijović, D. and Klinowski, J., 1995. Taboo search: An approach to the multiple minima problem. Science, 267(5198), pp.664-666.
  • Polyak, B.T., 1987. Introduction to optimization. Optimization Software. New York.
  • Dorea, C.C.Y., 1983. Expected number of steps of a random optimization method. Journal of Optimization Theory and Applications, 39(2), pp.165-171. [ Sarma, M.S., 1990. On the convergence of the Baba and Dorea random optimization methods. Journal of Optimization Theory and Applications, 66, pp.337-343. ] + [ Appel, M.J., Labarre, R. and Radulovic, D., 2004. On accelerated random search. SIAM Journal on Optimization, 14(3), pp.708-731. ]
  • Solis, F.J. and Wets, R.J.B., 1981. Minimization by random search techniques. Mathematics of Operations Research, 6(1), pp.19-30.
  • Schumer, M.A. and Steiglitz, K., 1968. Adaptive step size random search. IEEE Transactions on Automatic Control, 13(3), pp.270-276.
  • Rastrigin, L.A., 1963. The convergence of the random search method in the extremal control of a many parameter system. Automaton & Remote Control, 24, pp.1337-1342. [ Rastrigin, L.A., 1986. Random search as a method for optimization and adaptation. In Stochastic Optimization. ]
  • Brooks, S.H., 1958. A discussion of random methods for seeking maxima. Operations Research, 6(2), pp.244-251.
  • Some interesting applications of RS: e.g., [Moon et al., 2023, Nature Medicine]; [Wang et al., 2023, Nature Mental Health]; [Xie et al., 2023, Nature Communications]; [Mathis et al., 2023, Nature Biotechnology]; [Tian et al., 2023, KDD]; [Schuch et al., 2023, JAMA]; [Flam-Shepherd et al., 2022, Nature Communications]; [Beucler et al., 2021, PRL]; [Roman et al., 2021, Nature Machine Intelligence]; [Shen et al., 2021, Nature Communications]; [Gonatopoulos-Pournatzis et al., 2020, Nature Biotechnology]; [Valeri et al., 2020, Nature Communications]; [Chen et al., 2020, Science Robotics]; [Pickard&Needs, 2006, PRL].
• Bayesian Optimization (BO)
  • https://bayesoptbook.com/
  • https://bayesopt-tutorial.github.io/
  • Wang, L., Fonseca, R. and Tian, Y., 2020. Learning search space partition for black-box optimization using monte carlo tree search. Advances in Neural Information Processing Systems, 33, pp.19511-19522. [ Python ]
  • Jones, D.R., Schonlau, M. and Welch, W.J., 1998. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4), pp.455-492.
• Automated Machine Learning (AutoML)
  • Hutter, F., Kotthoff, L. and Vanschoren, J., 2019. Automated machine learning: Methods, systems, challenges. Springer Nature.
  • Hoos, H.H., 2011. Automated algorithm configuration and parameter tuning. In Autonomous Search (pp. 37-71). Springer, Berlin, Heidelberg.
• Software
  • Custódio, A.L., Scheinberg, K. and Nunes Vicente, L., 2017. Methodologies and software for derivative-free optimization. Advances and Trends in Optimization with Engineering Applications, pp.495-506.
  • Rios, L.M. and Sahinidis, N.V., 2013. Derivative-free optimization: A review of algorithms and comparison of software implementations. Journal of Global Optimization, 56, pp.1247-1293.
  • Schaul, T., Bayer, J., Wierstra, D., Sun, Y., Felder, M., Sehnke, F., Rückstieß, T. and Schmidhuber, J., 2010. PyBrain. Journal of Machine Learning Research, 11(24), pp.743-746.
  • Press, W.H., Teukolsky, S.A., Vetterling, W.T. and Flannery, B.P., 2007. Numerical recipes: The art of scientific computing. Cambridge University Press. (See Chapter 10. Minimization or maximization of functions.)

Sponsor

From 2021 to 2023, this open-source library was supported by Shenzhen Fundamental Research Program under Grant No. JCYJ20200109141235597 (￥2,000,000).

Citation

If this open-source library is used in your paper/project, it is highly welcomed to cite the following arXiv preprint paper: Duan, Q., Zhou, G., Shao, C., Wang, Z., Feng, M., Yang, Y., Zhao, Q. and Shi, Y., 2022. PyPop7: A pure-Python library for population-based black-box optimization. arXiv preprint arXiv:2212.05652.

pypop's Issues

Add Arxiv article resource link to readme

Perhaps the following link can be added to the readme (if it isn't present already):

https://arxiv.org/abs/2212.05652

Parllelization

Hello,

is it somehow possible to run the algorithms on multiple CPUS, since most Laptops these days have multiple core.

How to get candidate solutions from each iteration?

Thanks for the excellent work 🥳

1. I'm looking for black-box optimization algorithms to perform prompt tuning on my neural network, which requires candidate solutions from each iteration.
2. Following the “ask-tell” form of pycma, the pseudo-code is shown as below:

while not es.stop():
    solutions = es.ask()
    fitness = [cma.ff.rosen(s) for s in solutions]
    es.tell(solutions, fitness)

3. Question: How can I obtain the solutions from each iteration to calculate new fitness (e.g. loss functions)?

Optimizers don't take into account lower and upper boundaries

As a test: I want to find min of function sum(x) for x between 0 and 1. I tryed to check it for all optimizers

The code which checks it:

import os
import pkgutil
import numpy
import importlib


def discover_optimizers(package_name):
    package = importlib.import_module(package_name)
    all_optimizers = []
    for _, module_name, is_pkg in pkgutil.iter_modules(package.__path__):
        if not is_pkg:
            continue
        full_module_name = f"{package_name}.{module_name}"
        subpackage = importlib.import_module(full_module_name)
        for _, class_name, _ in pkgutil.iter_modules(subpackage.__path__):
            try:
                if not class_name.startswith('_'):
                    full_class_name = f"{full_module_name}.{class_name}"
                    class_module = importlib.import_module(full_class_name)
                    class_obj = getattr(class_module, class_name.upper())
                    all_optimizers.append(class_obj)
            except:
                pass
    return all_optimizers

all_optimizers = discover_optimizers('pypop7.optimizers')
print(len(all_optimizers))

optim_func = lambda x: x.sum()
n_dim = 4

lower_boundary = numpy.array([0] * n_dim)
upper_boundary = numpy.array([1] * n_dim)

options = {
    'fitness_threshold': 1e-3,  # terminate when the best-so-far fitness is lower than this threshold
    'max_runtime': 300,  # 300 seconds (terminate when the actual runtime exceeds it)
    'seed_rng': 0,  # seed of random number generation (which must be explicitly set for repeatability)
    'verbose': 0,
    'max_function_evaluations': 100000,
    'sigma': 0.3
}
problem = {'fitness_function': optim_func,  # cost function
           'ndim_problem': n_dim,  # dimension
           'lower_boundary': lower_boundary,  # search boundary
           'upper_boundary': upper_boundary,
           'k': n_dim - 1}

for opt in all_optimizers:
    try:
        optimizer = opt(problem.copy(), options.copy())
        result = optimizer.optimize()
        if result:
            print(opt, result['best_so_far_x'])
    except:
        pass

The result:

<class 'pypop7.optimizers.bo.lamcts.LAMCTS'> [-0.6760339   0.3618667  -0.16212286 -0.02880972]
<class 'pypop7.optimizers.cc.cocma.COCMA'> [-0.47686997  0.53185109 -0.07582775 -0.0714384 ]
<class 'pypop7.optimizers.cc.coea.COEA'> [0.00231813 0.00659672 0.02236841 0.01236731]
<class 'pypop7.optimizers.cc.cosyne.COSYNE'> [0. 0. 0. 0.]
<class 'pypop7.optimizers.cc.hcc.HCC'> [-0.51623094 -0.14621922 -0.20562318  0.36384467]
<class 'pypop7.optimizers.cem.dscem.DSCEM'> [-0.39263308  0.25119954 -0.37545458  0.10072805]
<class 'pypop7.optimizers.cem.mras.MRAS'> [-0.07683651 -0.04483756 -0.06484939  0.10204932]
<class 'pypop7.optimizers.cem.scem.SCEM'> [-0.39263308  0.25119954 -0.37545458  0.10072805]
<class 'pypop7.optimizers.de.cde.CDE'> [ 0.16445318 -0.42179586 -0.09557912  0.04130309]
<class 'pypop7.optimizers.de.code.CODE'> [ 0.32137146 -0.99359753 -0.10802254  0.69684811]
<class 'pypop7.optimizers.de.jade.JADE'> [-0.17073779  0.15351694  0.27778093 -0.44524287]
<class 'pypop7.optimizers.de.shade.SHADE'> [ 0.13695033  0.07221861 -0.04688718 -0.39555022]
<class 'pypop7.optimizers.de.tde.TDE'> [ 0.46981607 -0.54584549 -0.20370663 -0.16033081]
<class 'pypop7.optimizers.ds.cs.CS'> [-0.1459572   0.10163917  0.00670629  0.16155334]
<class 'pypop7.optimizers.ds.gps.GPS'> [-0.88697404  0.79292833 -0.14605473  0.13879303]
<class 'pypop7.optimizers.ds.hj.HJ'> [-1.40047131  0.34461043  0.50683001  0.44171118]
<class 'pypop7.optimizers.ds.nm.NM'> [-0.83975216  0.06450609 -0.03964336  0.76778177]
<class 'pypop7.optimizers.ds.powell.POWELL'> [6.61069614e-05 6.61069614e-05 6.61069614e-05 4.53103854e-04]
<class 'pypop7.optimizers.eda.aemna.AEMNA'> [ 0.11252365 -0.18191406 -0.07250522  0.13927807]
<class 'pypop7.optimizers.eda.emna.EMNA'> [-0.01052653 -0.03288489  0.33220645  0.10134024]
<class 'pypop7.optimizers.eda.rpeda.RPEDA'> [0. 0. 0. 0.]
<class 'pypop7.optimizers.eda.umda.UMDA'> [-0.35342327  0.27947705 -0.37516572  0.10423779]
<class 'pypop7.optimizers.ep.cep.CEP'> [-1.52930751  0.46344768  0.14693299  0.63753879]
<class 'pypop7.optimizers.ep.fep.FEP'> [ 0.20749682  0.18527865  0.79435323 -2.94729542]
<class 'pypop7.optimizers.ep.lep.LEP'> [ 1.10558115  0.24239287 -4.9921671   0.69668987]
<class 'pypop7.optimizers.es.ccmaes2009.CCMAES2009'> [ 0.20749043 -0.8293654   0.24668735  0.23266953]
<class 'pypop7.optimizers.es.ccmaes2016.CCMAES2016'> [ 0.13678102 -0.69954803  0.32041095  0.13767426]
<class 'pypop7.optimizers.es.cmaes.CMAES'> [-0.28272347 -1.41480348  0.95616745 -0.40147134]
<class 'pypop7.optimizers.es.csaes.CSAES'> [-0.05864292 -0.19553882  0.29017808 -0.19070991]
<class 'pypop7.optimizers.es.ddcma.DDCMA'> [-0.02227496 -1.06207523  0.7854238   0.16832468]
<class 'pypop7.optimizers.es.dsaes.DSAES'> [ 0.30795104 -0.47174714 -0.784923    0.19072515]
<class 'pypop7.optimizers.es.fcmaes.FCMAES'> [ 0.24055367 -0.43308581  0.24361855 -0.28491516]
<class 'pypop7.optimizers.es.fmaes.FMAES'> [ 0.24110199 -0.82529545  0.27054464  0.21301834]
<class 'pypop7.optimizers.es.lmcma.LMCMA'> [-0.21275055 -0.66336508 -0.39555834  0.0026348 ]
<class 'pypop7.optimizers.es.lmcmaes.LMCMAES'> [ 0.63591624 -0.06963237 -0.70116549 -0.23170578]
<class 'pypop7.optimizers.es.lmmaes.LMMAES'> [-0.7468732   0.54044971 -0.83124089  0.28553827]
<class 'pypop7.optimizers.es.maes.MAES'> [ 0.24110199 -0.82529545  0.27054464  0.21301834]
<class 'pypop7.optimizers.es.mmes.MMES'> [ 0.18658459 -0.21728094 -0.22269701  0.1241464 ]
<class 'pypop7.optimizers.es.opoa2010.OPOA2010'> [ 0.78447352 -1.64450233  0.65211289 -0.41848015]
<class 'pypop7.optimizers.es.opoa2015.OPOA2015'> [ 0.64382685 -1.52102046  0.6747694  -0.45705725]
<class 'pypop7.optimizers.es.opoc2006.OPOC2006'> [ 1.09949707 -1.95056972  0.80188148 -0.50072606]
<class 'pypop7.optimizers.es.opoc2009.OPOC2009'> [ 0.78447352 -1.64450233  0.65211289 -0.41848015]
<class 'pypop7.optimizers.es.r1es.R1ES'> [ 0.01613307 -0.2390732  -0.1692492   0.0223703 ]
<class 'pypop7.optimizers.es.res.RES'> [ 1.18489362 -1.14707295  0.31712093 -0.39674864]
<class 'pypop7.optimizers.es.rmes.RMES'> [-0.52414836  0.35839744 -0.43697971 -0.25157316]
<class 'pypop7.optimizers.es.saes.SAES'> [ 0.37349651 -0.55888947  0.50092362 -0.50894695]
<class 'pypop7.optimizers.es.samaes.SAMAES'> [ 0.53545301 -0.73719703  0.65899345 -0.60428368]
<class 'pypop7.optimizers.es.sepcmaes.SEPCMAES'> [ 0.11559861 -1.04378521  0.23793796  0.2807491 ]
<class 'pypop7.optimizers.es.ssaes.SSAES'> [-0.43675648 -0.47365778 -0.01960891  0.48671414]
<class 'pypop7.optimizers.es.vdcma.VDCMA'> [ 1.36058364 -0.71217782 -0.44076356 -0.2856638 ]
<class 'pypop7.optimizers.es.vkdcma.VKDCMA'> [ 0.21444881 -0.88568877  0.32169121  0.25377752]
<class 'pypop7.optimizers.ga.g3pcx.G3PCX'> [-0.15269955  0.6733837  -0.18691776 -0.36552076]
<class 'pypop7.optimizers.ga.genitor.GENITOR'> [0.16925372 0.57813239 0.09181329 0.0330481 ]
<class 'pypop7.optimizers.ga.gl25.GL25'> [3.69095500e-04 4.19647735e-06 1.50494419e-04 2.18297760e-04]
<class 'pypop7.optimizers.nes.enes.ENES'> [ 1.81492    -2.57232933  1.48505313 -1.07211646]
<class 'pypop7.optimizers.nes.ones.ONES'> [ 1.81492    -2.57232933  1.48505313 -1.07211646]
<class 'pypop7.optimizers.nes.r1nes.R1NES'> [-3.70034242  0.60952904 -0.9282294   2.74587766]
<class 'pypop7.optimizers.nes.sges.SGES'> [ 1.81492    -2.57232933  1.48505313 -1.07211646]
<class 'pypop7.optimizers.nes.snes.SNES'> [-0.03319505 -0.71717639  0.48269242  0.10121638]
<class 'pypop7.optimizers.nes.xnes.XNES'> [ 1.81492    -2.57232933  1.48505313 -1.07211646]
<class 'pypop7.optimizers.pso.clpso.CLPSO'> [ 0.09216473  0.17694329 -0.15585932 -0.12475649]
<class 'pypop7.optimizers.pso.cpso.CPSO'> [-0.23658014 -0.07414678  0.1004639   0.20766364]
<class 'pypop7.optimizers.pso.ipso.IPSO'> [0. 0. 0. 0.]
<class 'pypop7.optimizers.pso.spso.SPSO'> [-0.41952165  0.17352028 -0.12113851  0.32384185]
<class 'pypop7.optimizers.pso.spsol.SPSOL'> [-0.22547512 -0.17689092 -0.01380493  0.38978217]
<class 'pypop7.optimizers.rs.bes.BES'> [-0.02723131 -0.08054957  0.08467001  0.02035118]
<class 'pypop7.optimizers.rs.gs.GS'> [ 0.01553554 -0.2359458   0.03920435  0.07267143]
<class 'pypop7.optimizers.rs.prs.PRS'> [0.01161162 0.06071727 0.00665576 0.02123513]
<class 'pypop7.optimizers.rs.rhc.RHC'> [ 0.66297826 -1.36597693  0.58673108 -0.29628104]
<class 'pypop7.optimizers.rs.srs.SRS'> [-0.283229    0.44578372 -0.47789181 -0.04463705]
<class 'pypop7.optimizers.sa.esa.ESA'> [0. 0. 0. 0.]

n_parents issue

In ES.init exists the bug with n_parents parameter.

The code:

import numpy
from pypop7.benchmarks.base_functions import rosenbrock  # function to be minimized
from pypop7.optimizers.es.ccmaes2016 import CCMAES2016
problem = {'fitness_function': rosenbrock,  # define problem arguments
           'ndim_problem': 2,
           'lower_boundary': -5*numpy.ones((2,)),
           'upper_boundary': 5*numpy.ones((2,))}
options = {'max_function_evaluations': 5000,  # set optimizer options
           'seed_rng': 2022,
           'mean': 3*numpy.ones((2,)),
           'sigma': 0.1,
           'n_parents': 10}  # the global step-size may need to be tuned for better performance
ccmaes2016 = CCMAES2016(problem, options)  # initialize the optimizer class
results = ccmaes2016.optimize()  # run the optimization process

Fails with AttributeError: 'CCMAES2016' object has no attribute '_mu_eff'

This is because the _mu_eff initialization never reached:

pypop/pypop7/optimizers/es/es.py

Lines 121 to 126 in 302d5e0

	if self.n_parents is None: # number of parents (μ: mu), parental population size
	self.n_parents = int(self.n_individuals/2)
	if self.n_parents > 1:
	self._w, self._mu_eff = self._compute_weights()
	self._e_chi = np.sqrt(self.ndim_problem)*( # E[||N(0,I)||]: expectation of chi distribution
	1.0 - 1.0/(4.0*self.ndim_problem) + 1.0/(21.0*np.square(self.ndim_problem)))

.

I suspect there is a wrong tabulation at line 123.

Tips to improve the results

I am trying to solve the optimization problem, I have selected 12 algorithms [VKDCMA, VDCMA, R1ES, RMES, CCMAES2016, FMAES, HCC, LMCMA, LMCMAES, OPOA2015, SAMAES, XNES], run them with 100 different seeds, but I realize that they are not doing well. The most effective one is "multi-start local optimization" (when I many times randomly choose the initial point for a local-search optimization, like BFGS). Maybe I'm doing something wrong?
Below I will only provide a "sandbox" that only runs FMAES. Sorry for numba (but, it's 10 times faster than numpy) and tdqm.

import math
import warnings

import numpy
import scipy
from numba import njit
from pypop7.optimizers.es.fmaes import FMAES
from scipy import optimize
from tqdm import tqdm

warnings.simplefilter(action='ignore', category=FutureWarning)


@njit(fastmath=True)
def power_function(x, k):
    N0 = len(x) // 3
    N_sphere = N0 // 2

    coords = numpy.zeros((N0, 3), dtype=float)
    ampl = numpy.zeros(N0, dtype=float)
    R_sources = numpy.zeros(N0, dtype=float)

    for i in range(N0):
        r = 1 if i < N_sphere else 1.1
        R_sources[i] = r
        ampl[i] = x[2 * N0 + i]

        theta = x[i]
        phi = x[N0 + i]

        sin_theta = math.sin(theta)

        coords[i, 0] = r * sin_theta * numpy.cos(phi)
        coords[i, 1] = r * numpy.sin(theta) * numpy.sin(phi)
        coords[i, 2] = r * numpy.cos(theta)

    distances = numpy.zeros((N0, N0), dtype=float)
    for i in range(N0):
        for j in range(i + 1, N0):
            d = math.sqrt(
                (coords[i, 0] - coords[j, 0]) ** 2 + (coords[i, 1] - coords[j, 1]) ** 2 + (
                            coords[i, 2] - coords[j, 2]) ** 2
            )
            distances[i, j] = distances[j, i] = d

    power = 1.0

    for i in range(N0):
        power += 2 * ampl[i] * numpy.sinc(k * R_sources[i] / numpy.pi)

    for i in range(N0):
        for j in range(N0):
            power += ampl[i] * ampl[j] * numpy.sinc(k * distances[i, j] / numpy.pi)

    return power


def multi_start_optimization(func, bounds, n_starts=10, method='BFGS', callback=None, seed=None, verbose=True,
                             **kwargs):
    best_result = None
    numpy.random.seed(seed)

    for _ in (pbar := tqdm(range(n_starts), disable=not verbose)):
        x0 = numpy.random.rand(*bounds[0].shape) * (bounds[1] - bounds[0]) + bounds[0]

        result = scipy.optimize.minimize(func, x0, method=method, callback=callback, **kwargs)

        if best_result is None or result.fun < best_result.fun:
            best_result = result
            pbar.set_postfix({'best_result_so_far': best_result.fun})

    return best_result

n_sources = 20

lower_boundary = numpy.array([0] * n_sources + [0] * n_sources + [-2] * n_sources)
upper_boundary = numpy.array([numpy.pi] * n_sources + [2 * numpy.pi] * n_sources + [2] * n_sources)
function_to_minimize = lambda x: power_function(x, k=7.5)

ms_result = multi_start_optimization(function_to_minimize, (lower_boundary, upper_boundary), n_starts=300, seed=23,
                                     tol=1e-4, verbose=True)

print(ms_result)

options = {
    'fitness_threshold': 1e-4,
    'max_runtime': 30_000,
    'seed_rng': 500,
    'max_function_evaluations': 100_000_000,
    'sigma': 0.3,
    'verbose': 500
}

problem = {'fitness_function': function_to_minimize,  # cost function
           'ndim_problem':  3 * n_sources,  # dimension
           'lower_boundary': lower_boundary,  # search boundary
           'upper_boundary': upper_boundary
          }

solver = FMAES(problem, options)  # initialize the optimizer
results = solver.optimize()

print(results['best_so_far_y'])

Output:

100%|██████████| 300/300 [03:18<00:00,  1.51it/s, best_result_so_far=0.162]
  message: Optimization terminated successfully.
  success: True
   status: 0
      fun: 0.16172215956324537
        x: [ 6.341e-01  1.739e+00 ... -4.215e-01 -2.126e-01]
      nit: 249
      jac: [-1.187e-05  3.090e-05 ...  2.599e-05  1.672e-05]
 hess_inv: [[ 3.054e+00 -8.579e-02 ...  2.756e-01  1.871e-01]
            [-8.579e-02  1.408e+00 ...  2.143e-02 -9.474e-02]
            ...
            [ 2.756e-01  2.143e-02 ...  5.659e-01  1.020e-01]
            [ 1.871e-01 -9.474e-02 ...  1.020e-01  6.574e-01]]
     nfev: 15799
     njev: 259
  * Generation 0: best_so_far_y 1.65875e+01, min(y) 1.65875e+01 & Evaluations 16
  * Generation 500: best_so_far_y 4.43191e-01, min(y) 4.44579e-01 & Evaluations 8016
  * Generation 1000: best_so_far_y 3.63186e-01, min(y) 3.63186e-01 & Evaluations 16016
  * Generation 1500: best_so_far_y 3.53268e-01, min(y) 3.53329e-01 & Evaluations 24016
  * Generation 2000: best_so_far_y 3.05547e-01, min(y) 3.05707e-01 & Evaluations 32016
  * Generation 2500: best_so_far_y 2.95432e-01, min(y) 2.95478e-01 & Evaluations 40016
  * Generation 3000: best_so_far_y 2.79785e-01, min(y) 2.79901e-01 & Evaluations 48016
  * Generation 3500: best_so_far_y 2.69350e-01, min(y) 2.69350e-01 & Evaluations 56016
  * Generation 4000: best_so_far_y 2.65173e-01, min(y) 2.65265e-01 & Evaluations 64016
  * Generation 4500: best_so_far_y 2.62260e-01, min(y) 2.62262e-01 & Evaluations 72016
  * Generation 5000: best_so_far_y 2.61340e-01, min(y) 2.61340e-01 & Evaluations 80016
  ...............................
....... *** restart *** .......
  * Generation 0: best_so_far_y 1.95928e-01, min(y) 9.80403e+00 & Evaluations 3197296
  * Generation 500: best_so_far_y 1.95928e-01, min(y) 2.09076e-01 & Evaluations 3709296
  * Generation 1000: best_so_far_y 1.84766e-01, min(y) 1.84766e-01 & Evaluations 4221296
  * Generation 1003: best_so_far_y 1.84766e-01, min(y) 1.84766e-01 & Evaluations 4223344
 ....... *** restart *** .......
  * Generation 0: best_so_far_y 1.84766e-01, min(y) 1.28830e+01 & Evaluations 4225392
  * Generation 500: best_so_far_y 1.84766e-01, min(y) 4.66329e-01 & Evaluations 5249392
  * Generation 1000: best_so_far_y 1.72185e-01, min(y) 1.74094e-01 & Evaluations 6273392
  * Generation 1087: best_so_far_y 1.72185e-01, min(y) 1.72500e-01 & Evaluations 6449520
 ....... *** restart *** .......
  * Generation 0: best_so_far_y 1.72185e-01, min(y) 1.31143e+01 & Evaluations 6453616
  * Generation 500: best_so_far_y 1.72185e-01, min(y) 3.64424e-01 & Evaluations 8501616
  * Generation 780: best_so_far_y 1.72185e-01, min(y) 2.91337e-01 & Evaluations 9644400
 ....... *** restart *** .......
  * Generation 0: best_so_far_y 1.72185e-01, min(y) 1.11503e+01 & Evaluations 9652592
  * Generation 500: best_so_far_y 1.72185e-01, min(y) 3.37978e-01 & Evaluations 13748592
  * Generation 685: best_so_far_y 1.72185e-01, min(y) 2.82461e-01 & Evaluations 15255920
 ....... *** restart *** .......
  * Generation 0: best_so_far_y 1.72185e-01, min(y) 9.21559e+00 & Evaluations 15272304
  * Generation 500: best_so_far_y 1.72185e-01, min(y) 4.49968e-01 & Evaluations 23464304
  * Generation 717: best_so_far_y 1.72185e-01, min(y) 4.29491e-01 & Evaluations 27003248
 ....... *** restart *** .......
  * Generation 0: best_so_far_y 1.72185e-01, min(y) 1.20239e+01 & Evaluations 27036016
  * Generation 215: best_so_far_y 1.72185e-01, min(y) 6.52917e-01 & Evaluations 34048368
 ....... *** restart *** .......
  * Generation 0: best_so_far_y 1.72185e-01, min(y) 8.29719e+00 & Evaluations 34113904
  * Generation 500: best_so_far_y 1.72185e-01, min(y) 6.05617e-01 & Evaluations 66881904
  * Generation 802: best_so_far_y 1.72185e-01, min(y) 5.39836e-01 & Evaluations 86608240
 ....... *** restart *** .......
  * Generation 0: best_so_far_y 1.72185e-01, min(y) 1.50296e+01 & Evaluations 86739312
  * Generation 102: best_so_far_y 1.72185e-01, min(y) 6.62570e-01 & Evaluations 100000000

So, the result of multi-start optimization is 0.161725642456162, at the same time FMAES gives 0.172185 after 100 mlns attempts. Moreover, the last 94 mlns attempts did not improve the result. What can I do??? Changing sigma and individuals did not allow me to get results better than 0.1617.

Feature request. Early stopping

Good day. If it possible to add 'early_stopping' feature? Sometimes I want to stop the process if it's stuck.
I can add it.

No module named 'pypop7.optimizers.bo'

Thank you for providing such an invaluable collection. I have checked the "setup.cfg" and found that Bayesian Optimization (BO) is not included yet (No module named 'pypop7.optimizers.bo' and LAMCTS is not available). Please add BO so that we can try this method using pypop7.

Possible bug after restart of RMES

Hi there,

I think there may be a bug in the handling of the delay factor in RMES.py after a restart - but I could be mistaken. After achieving convergence of an optimisation run, the implementation restarted the run;

 ....... *** restart *** .......

Then after one generation, resulted in an error. See following code output after restart 1;

* Generation 1: best_so_far_y -8.09000e-01, min(y) 2.19336e+01 & Evaluations 9352
Traceback (most recent call last):
  File "code.py", line 878, in <module>
    results = lmmaes.optimize()
  File "Python\Python39\lib\site-packages\pypop7\optimizers\es\rmes.py", line 154, in optimize       
    mean, p, s, mp, t_hat = self._update_distribution(x, mean, p, s, mp, t_hat, y, y_bak)
  File "Python\Python39\lib\site-packages\pypop7\optimizers\es\rmes.py", line 124, in _update_distribution
    mean, p, s = R1ES._update_distribution(self, x, mean, p, s, y, y_bak)
  File "Python\Python39\lib\site-packages\pypop7\optimizers\es\r1es.py", line 144, in _update_distribution
    self.sigma *= np.exp(s/self.d_sigma)
numpy.core._exceptions._UFuncOutputCastingError: Cannot cast ufunc 'multiply' output from dtype('float64') to dtype('int32') with casting rule 'same_kind'

The inputs were as follows;

  'max_runtime': (17*60*60),  
  'seed_rng': 16, 
  'x': x,  
  'sigma': 1, 
  'verbose': 1,
  'saving_fitness': 100,
  'd_sigma': 10}

The problem had 100 dimensions. Any help would be greatly appreciated!