Consensus based optimization

Consensus-based optimization (CBO) is a multi-agent derivative-free optimization method, designed to obtain solutions for global optimization problems of the form $$\min _{x\in {\cal {X}}}f(x),$$

Behavior of CBO on the Rastrigin function. Blue: Particles, Pink: drift vectors and consensus point.

where $f:{\mathcal {X}}\to \mathbb {R}$ denotes the objective function acting on the state space ${\cal {X}}$, which we assume to be a normed vector space in the following. The function $f$ can potentially be nonconvex and nonsmooth. The algorithm employs particles or agents to explore the state space, which communicate with each other to update their positions. Their dynamics follows the paradigm of metaheuristics, which blend exporation with exploitation. In this sense, CBO is comparable to ant colony optimization, wind driven optimization, particle swarm optimization or Simulated annealing.

The algorithm

Consider an ensemble of points $x_{t}=(x_{t}^{1},\dots ,x_{t}^{N})\in {\cal {X}}^{N}$, dependent of the time $t\in [0,\infty )$. Then the update for the $i$th particle is formulated as a stochastic differential equation,

$dx_{t}^{i}=-\lambda \,\underbrace {(x_{t}^{i}-c_{\alpha }(x_{t}))\,dt} _{\text{consensus drift}}+\sigma \underbrace {D(x_{t}^{i}-c_{\alpha }(x_{t}))\,dB_{t}^{i}} _{\text{scaled diffusion}}$ 1

with the following components:

• The consensus point $c_{\alpha }(x)$: The key idea of CBO is that in each step the particles “agree” on a common consensus point, by computing an average of their positions, weighted by their current objective function value $$c_{\alpha }(x_{t})={\frac {1}{\sum _{i=1}^{N}\omega _{\alpha }(x_{t}^{i})}}\sum _{i=1}^{N}x_{t}^{i}\ \omega _{\alpha }(x_{t}^{i}),\quad {\text{ with }}\quad \omega _{\alpha }(\,\cdot \,)=\mathrm {exp} (-\alpha f(\,\cdot \,)).$$This point is then used in the drift term $x_{t}^{i}-c_{\alpha }(x_{t})$, which moves each particle into the direction of the consensus point.
• Scaled noise: For each $t\geq 0$ and $i=1,\dots ,N$, we denote by $B_{t}^{i}$ independent standard Brownian motions. The function $D:{\cal {X}}\to \mathbb {R} ^{s}$ incorporates the drift of the $i$th particle and determines the noise model. The most common choices are:
  • Isotropic noise, $D(\cdot )=\|\cdot \|$: In this case $s=1$ and every component of the noise vector is scaled equally. This was used in the original version of the algorithm.
  • Anisotropic noise, $D(\cdot )=|\cdot |$: In the special case, where ${\cal {X}}\subset \mathbb {R} ^{d}$, this means that $s=d$ and $D$ applies the absolute value function component-wise. Here, every component of the noise vector is scaled, dependent on the corresponding entry of the drift vector.
• Hyperparameters: The parameter $\sigma \geq 0$ scales the influence of the noise term. The parameter $\alpha \geq 0$ determines the separation effect of the particles:
  • in the limit $\alpha \to 0$ every particle is assigned the same weight and the consensus point is a regular mean.
  • In the limit $\alpha \to \infty$ the consensus point corresponds to the particle with the best objective value, completely ignoring the position of other points in the ensemble.

Notes on Implementation

In practice, the SDE in [[#math_{{{1}}}|{{{1}}}]] is discretized via the Euler–Maruyama method such that the following explicit update formula for the ensemble $x=(x^{1},\dots ,x^{N})$ is obtained,$$x^{i}\gets x^{i}-\lambda \,(x^{i}-c_{\alpha }(x))\,dt+\sigma D(x^{i}-c_{\alpha }(x))\,B^{i}.$$If one can employ an efficient implementation of the LogSumExp functions, this can be beneficial for numerical stability of the consensus point computation. We refer to existing implementation in Python [1] and Julia [2].

See also

Particle Swarm Optimization

Simulated annealing

Ant colony optimization algorithms