Content deleted Content added
Added information |
Added section on algorithm |
||
Line 3:
{{Short description|Iterative simulation method}}
'''Consensus-based optimization (CBO)''' <ref name=":0">{{Cite journal |last1=Pinnau |first1=René |last2=Totzeck |first2=Claudia |last3=Tse |first3=Oliver |last4=Martin |first4=Stephan |date=January 2017 |title=A consensus-based model for global optimization and its mean-field limit |url=https://www.worldscientific.com/doi/abs/10.1142/S0218202517400061 |journal=Mathematical Models and Methods in Applied Sciences |language=en |volume=27 |issue=1 |pages=183–204 |doi=10.1142/S0218202517400061 |arxiv=1604.05648 |s2cid=119296432 |issn=0218-2025}}</ref> is a multi-agent [[derivative-free optimization]] method, designed to obtain solutions for global optimization problems of the form <math display="block">\min_{x\in \cal{X}} f(x),</math>where <math>f:\mathcal{X}\to\R</math> denotes the objective function acting on the state space <math>\cal{X}</math>, which we assume to be a [[normed vector space]] in the following. The function <math>f</math> 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 [[Metaheuristic|metaheuristics]], which blend exporation with exploitation. In this sense, CBO is comparable to [[Ant colony optimization algorithms|ant colony optimization]], wind driven optimization<ref>{{Cite web |title=The Wind Driven Optimization Technique and its Application in Electromagnetics {{!}} IEEE Journals & Magazine {{!}} IEEE Xplore |url=https://ieeexplore.ieee.org/document/6407788 |access-date=2024-02-03 |website=ieeexplore.ieee.org}}</ref>, [[particle swarm optimization]] or [[Simulated annealing]]. However, compared to other heuristics, CBO was designed to have a well-posed mean-field limit
== The algorithm ==
Consider an ensemble of points <math>x_t = (x_t^1,\dots, x_t^N) \in {\cal{X}}^N</math>, dependent of the time <math>t\in[0,\infty)</math>. Then the update for the <math>i</math>th particle is formulated as a stochastic differential equation,<math display="block">dx^i_t = -\lambda\, \underbrace{(x^i_t-c_\alpha(x_t))\,dt}_{\text{consensus drift}} + \sigma \underbrace{D(x^i_t-c_{\alpha}(x_t))\,dB^i_t}_{\text{scaled diffusion}}</math>with the following components:
* '''The consensus point''' <math>c_{\alpha}(x)</math>: 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 <math display="block">c_\alpha(x_t) = \frac{1}{\sum_{i=1}^N \omega_\alpha(x^i_t)} \sum_{i=1}^N x^i_t\ \omega_\alpha(x^i_t), \quad\text{ with }\quad \omega_\alpha(\,\cdot\,) = \mathrm{exp}(-\alpha f(\,\cdot\,)).
</math>This point is then used in the '''drift''' term <math>x^i_t-c_\alpha(x_t)</math>, which moves each particle into the direction of the consensus point.
* '''Scaled noise:''' For each <math>t\geq 0</math> and <math>i=1,\dots,N</math>, we denote by <math>B^i_t</math> independent standard Brownian motions. The function <math>D:{\cal{X}}\to\R^s</math> incorporates the drift of the <math>i</math>th particle and determines the noise model. The most common choices are:
** ''Isotropic noise'', <math>D(\cdot) = \|\cdot \|</math>: In this case <math>s=1</math> and every component of the noise vector is scaled equally. This was used in the original version of the algorithm<ref name=":0" />.
** ''Anisotropic noise'', <math>D(\cdot) = |\cdot|</math>: In the special case, where <math>{\cal{X}}\subset \R^d</math>, this means that <math>s=d</math> and <math>D</math> 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 <math>\sigma \geq 0</math> scales the influence of the noise term. The parameter <math>\alpha \geq 0</math> determines the separation effect of the particles<ref name=":0" />:
** in the limit <math>\alpha\to 0</math> every particle is assigned the same weight and the consensus point is a regular mean.
** In the limit <math>\alpha\to\infty</math> the consensus point corresponds to the particle with the best objective value, completely ignoring the position of other points in the ensemble.
== Convergence ==
== Notes on Implementation ==
== Variants ==
Line 16 ⟶ 31:
[[Particle Swarm Optimization]]
[[Simulated annealing]]
[[Ant colony optimization algorithms]]
| |||