Content deleted Content added
m section heads could be a bit more concise but otherwise I see no reason not to accept |
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed access-date with no URL. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 512/1032 |
||
| (6 intermediate revisions by 5 users not shown) | |||
Line 1:
{{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>
[[File:CBORastrigin.gif|thumb|Behavior of CBO on the [[Rastrigin function]]. '''Blue:''' Particles, '''Pink:''' drift vectors and consensus point.]]
where <math>f:\mathcal{X}\to\R</math> denotes the objective function acting on the state space <math>\cal{X}</math>, which is assumed to be a [[normed vector space]]. 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
== 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,
Line 21 ⟶ 16:
</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<ref>{{cite arXiv |last1=Carrillo |first1=José A. |title=A consensus-based global optimization method for high dimensional machine learning problems |date=2020-03-04 |eprint=1909.09249 |last2=Jin |first2=Shi |last3=Li |first3=Lei |last4=Zhu |first4=Yuhua|class=math.OC }}</ref>'', <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.
Line 53 ⟶ 48:
</math> determines the communication radius of particles. This choice corresponds to a local convex regularization of the objective function <math>f
</math>.
* '''[[Mean-shift algorithm]]''':<ref>{{Cite journal |last1=Fukunaga |first1=K. |last2=Hostetler |first2=L. |date=January 1975 |title=The estimation of the gradient of a density function, with applications in pattern recognition
</math>, together with no noise (i.e. <math>\sigma = 0
</math>) and an Euler–Maruyama discretization with step size <math>dt=1
</math>, corresponds to the mean-shift algorithm.
* '''Bounded confidence model''': When choosing a constant objective function, no noise model, but also the special kernel function <math>k(x,\tilde x) = 1_{\|x-\tilde x\| \leq \kappa}
</math>, the SDE in transforms to a ODE known as the bounded confidence model,<ref>{{Cite journal |last1=Deffuant |first1=Guillaume |last2=Neau |first2=David |last3=Amblard |first3=Frederic |last4=Weisbuch |first4=Gérard |date=January 2000 |title=Mixing beliefs among interacting agents |url=https://www.worldscientific.com/doi/abs/10.1142/S0219525900000078 |journal=Advances in Complex Systems |language=en |volume=03 |issue=1n04 |pages=87–98 |doi=10.1142/S0219525900000078 |s2cid=15604530 |issn=0219-5259|url-access=subscription }}</ref>
== See also ==
* [[Particle Swarm Optimization]]
* [[Simulated annealing]]
▲* [[Ant colony optimization algorithms]]<br />
== References ==
{{reflist}}
[[Category:Optimization algorithms and methods]]
[[Category:Metaheuristics]]
| |||