fcmaes - a Python 3 gradient-free optimization library

fcmaes complements scipy optimize by providing additional optimization methods, faster C++/Eigen based implementations and a coordinated parallel retry mechanism. It supports the multi threaded application of different gradient free optimization algorithms. There are 35 real world tutorials showing in detail how to use fcmaes. See performance for detailed fcmaes performance figures.

fcmaes started as a fast CMA-ES implementation combined with a new smart parallel retry mechanism aimed to solve hard optimization problems from the space flight planning domain. It evolved to a general library of state-of-the-art gradient free optimization algorithms applicable to all kind of real world problems covering multi-objective and constrained problems. Its main algorithms are implemented both in Python and C++ and support both parallel fitness function evaluation and a parallel retry mechanism.

Update: New example shows the interaction between AI code generation and optimization

LLMs can help to generate code implementing a trading strategy. It can even propose ways to optimize the final return. prophet_opt.py shows:

• The o1-preview prompts used to generate the strategy back-testing code.

• How to identify the parameters to optimize using the AI.

• How the parameter optimization process can be automated efficiently utilizing trading simulations executed in parallel.

This idea can be applied everywhere when parameters of time consuming simulations have to be optimized. If you aim to optimize multiple objectives, you may find many other examples in:

Tutorials

Performance

Features

• Focused on optimization problems hard to solve utilizing modern many-core CPUs.

• Parallel fitness function evaluation and different parallel retry mechanisms.

• Excellent scaling with the number of available CPU-cores.

• Minimized algorithm overhead - relative to the objective function evaluation time - even for high dimensions.

• Multi-objective/constrained optimization algorithm MODE combining features from Differential evolution and NSGA-II, supporting parallel function evaluation. Features enhanced multiple constraint ranking improving its performance in handling constraints for engineering design optimization.

• QD support: CVT-map-elites including a CMA-ES emitter and a new "diversifier" meta algorithm utilizing CVT-map-elites archives.

• Selection of highly efficient single-objective algorithms to choose from.

• Ask-tell interface for CMA-ES, CR-FM-NES, DE, MODE and PGPE.

• Large collection of 35 tutorials related to real world problems: tutorials.

Changes from version 1.6.3:

• Logging now based on loguru. All examples are adapted.

• New dependencies: loguru + numba.

• New tutorial related to the GECCO 2023 Space Optimization Competition: ESAChallenge.

• You can define an initial population as guess for multi objective optimization.

Changes from version 1.4.0:

• Pure Python versions of the algorithms are now usable also for parallel retry. Pure Python features: Algorithms: CMA-ES, CR-FM-NES, DE, MODE (multiple objective), Map-Elites+Diversifier (quality diversity). All Python algorithms support an ask-tell interface and parallel function evaluation. Additionally parallel retry / advanced retry (smart boundary management) are supported for these algorithms.

• Python version > 3.7 required, 3.6 is no longer supported.

• PEP 0484 compatible type hints useful for IDEs like PyCharm.

• Most algorithms now support an unified ask/tell interface: cmaes, cmaescpp, crfmnes, crfmnescpp, de, decpp, mode, modecpp, pgpecpp. This is useful for monitoring and parallel fitness evaluation.

• Added support for Quality Diversity [QD]: MAP-Elites with additional CMA-ES emitter, new meta-algorithm Diversifier, a generalized variant of CMA-ME, "drill down" for specified niches and bidirectional archive <→ store transfer between the QD-archive and the smart boundary management meta algorithm (advretry). All QD algorithms support parallel optimization utilizing all CPU-cores and statistics for solutions associated to a specific niche: mean, stdev, maximum, minimum and count.

Derivative free optimization of machine learning models often have several thousand decision variables and require GPU/TPU based parallelization both of the fitness evaluation and the optimization algorithm. CR-FM-NES, PGPE and the QD-Diversifier applied to CR-FM-NES (CR-FM-NES-ME) are excellent choices in this domain. Since fcmaes has a different focus (parallel optimizations and parallel fitness evaluations) we contributed these algorithms to EvoJax which utilizes JAX for GPU/TPU execution.

Optimization algorithms

To utilize modern many-core processors all single-objective algorithms should be used with the parallel retry for cheap fitness functions, otherwise use parallel function evaluation.

• MO-DE: A new multi-objective optimization algorithm merging concepts from differential evolution and NSGA. Implemented both in Python and in C++. Provides an ask/tell interface and supports constraints and parallel function evaluation. Can also be applied to single-objective problems with constraints. Supports mixed integer problems (see CFD for details)

• CVT-map-elites/CMA: A new Python implementation of CVT-map-elites including a CMA-ES emitter providing low algorithm overhead and excellent multi-core scaling even for fast fitness functions. Enables "drill down" for specific selected niches. See mapelites.py and Map-Elites.

• Diversifier: A new Python meta-algorithm based on CVT-map-elites archives generalizing ideas from CMA-ME to other wrapped algorithms. See diversifier.py and Quality Diversity.

• BiteOpt algorithm from Aleksey Vaneev BiteOpt. Only a C++ version is provided. If your problem is single objective and if you have no clue what algorithm to apply, try this first. Works well with almost all problems. For constraints you have to use weighted penalties.

• Differential Evolution: Implemented both in Python and in C++. Additional concepts implemented are temporal locality, stochastic reinitialization of individuals based on their age and oscillating CR/F parameters. Provides an ask/tell interface and supports parallel function evaluation. Supports mixed integer problems (see CFD for details)

• CMA-ES: Implemented both in Python and in C++. Provides an ask/tell interface and supports parallel function evaluation. Good option for low number of decision variables (< 500).

• CR-FM-NES: Fast Moving Natural Evolution Strategy for High-Dimensional Problems, see https://arxiv.org/abs/2201.11422. Derived from https://github.com/nomuramasahir0/crfmnes . Implemented both in Python and in C++. Both implementations provide parallel function evaluation and an ask/tell interface. Good option for high number of decision variables (> 100).

• PGPE Parameter Exploring Policy Gradients, see http://mediatum.ub.tum.de/doc/1099128/631352.pdf . Implemented in C++. Provides parallel function evaluation and an ask/tell interface. Good option for very high number of decision variables (> 1000) and for machine learning tasks. An equivalent Python implementation can be found at pgpe.py, use this on GPUs/TPUs.

• Wrapper for cmaes which provides different CMA-ES variants implemented in Python like separable CMA-ES and CMA-ES with Margin (see https://arxiv.org/abs/2205.13482) which improves support for mixed integer problems. The wrapper additionally supports parallel function evaluation.

• Dual Annealing: Eigen based implementation in C++. Use the scipy implementation if you prefer a pure Python variant or need more configuration options.

• GCL-DE: Eigen based implementation in C++. See "A case learning-based differential evolution algorithm for global optimization of interplanetary trajectory design, Mingcheng Zuo, Guangming Dai, Lei Peng, Maocai Wang, Zhengquan Liu", doi.

• Expressions: There are two operators for constructing expressions over optimization algorithms: Sequence and random choice. Not only the single objective algorithms above, but also scipy and NLopt optimization methods and custom algorithms can be used for defining algorithm expressions.

Installation

Linux

• pip install fcmaes.

To use the C++ optimizers a gcc-9.3 (or newer) runtime is required. This is the default on newer Linux versions. If you are on an old Linux distribution you need to install gcc-9 or a newer version. On ubuntu this is:

• sudo add-apt-repository ppa:ubuntu-toolchain-r/test

• sudo apt update

• sudo apt install gcc-9

Alternatively if you use Anaconda:

• conda install -c conda-forge gxx_linux-64==9.5.0

  • Recommended Python environment: Anaconda3-2022.05 or newer. At least Python 3.7 is required.

Windows

• pip install fcmaes

• Install C++ runtime libraries https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads

• Recommended Python environment: Anaconda3-2022.05 or newer.

For parallel fitness function evaluation use the native Python optimizers or the ask/tell interface of the C++ ones. Python multiprocessing works better on Linux. To get optimal scaling from parallel retry and parallel function evaluation use:

• Linux subsystem for Windows WSL.

The Linux subsystem can read/write NTFS, so you can do your development on a NTFS partition. Just the Python call is routed to Linux. If performance of the fitness function is an issue and you don’t want to use the Linux subsystem for Windows, think about using the fcmaes java port: fcmaes-java.

MacOS

• pip install fcmaes

The C++ shared library is outdated, use the native Python optimizers.

Usage

Usage is similar to scipy.optimize.minimize.

For parallel retry use:

from fcmaes.optimizer import logger
from fcmaes import retry
ret = retry.minimize(fun, bounds, logger=logger())

The retry logs mean and standard deviation of the results, so it can be used to test and compare optimization algorithms: You may choose different algorithms for the retry:

from fcmaes.optimizer import logger, Bite_cpp, De_cpp, Cma_cpp, Sequence
ret = retry.minimize(fun, bounds, logger=logger(), optimizer=Bite_cpp(100000))
ret = retry.minimize(fun, bounds, logger=logger(), optimizer=De_cpp(100000))
ret = retry.minimize(fun, bounds, logger=logger(), optimizer=Cma_cpp(100000))
ret = retry.minimize(fun, bounds, logger=logger(), optimizer=Sequence([De_cpp(50000), Cma_cpp(50000)]))

Here https://github.com/dietmarwo/fast-cma-es/blob/master/examples you find more examples. Check the tutorials for more details.

Dependencies

Runtime:

• numpy: https://github.com/numpy/numpy, version >= 1.20

• scipy: https://github.com/scipy/scipy, version >= 1.8

• scikit-learn: https://github.com/scikit-learn/scikit-learn (for CVT-Map-Elites), version >= 1.1

Compile time (binaries for Linux and Windows are included):

• Eigen https://gitlab.com/libeigen/eigen (version >= 3.4.0 is required for CMA).

• EigenRand: https://github.com/bab2min/EigenRand - used in all C++ optimization algorithms.

• LBFGSpp: https://github.com/yixuan/LBFGSpp/tree/master/include - used for dual annealing local optimization.

Optional dependencies:

• matplotlib for the optional plot output.

• NLopt: NLopt. Install with 'pip install nlopt'.

• pygmo2: pygmo. Install with 'pip install pygmo'.

Example dependencies:

• pykep: pykep. Install with 'pip install pykep'.

Citing

@misc{fcmaes2022,
    author = {Dietmar Wolz},
    title = {fcmaes - A Python-3 derivative-free optimization library},
    note = {Python/C++ source code, with description and examples},
    year = {2022},
    publisher = {GitHub},
    journal = {GitHub repository},
    howpublished = {Available at \url{https://github.com/dietmarwo/fast-cma-es}},
}