We introduce a novel first-order stochastic swarm intelligence (SI) model in the spirit of consensus formation models, namely a consensus-based optimization (CBO) algorithm, which may be used for the global optimization of a function in multiple dimensions. The CBO algorithm allows for passage to the mean-field limit, which results in a nonstandard, nonlocal, degenerate parabolic partial differential equation (PDE). Exploiting tools from PDE analysis we provide convergence results that help to understand the asymptotic behavior of the SI model. We further present numerical investigations underlining the feasibility of our approach.

Communicated by N. Bellomo, F. Brezzi and M. Pulvirenti

Keywords:

AMSC: 34F05, 35B40, 90C26

References

1. D. Acemoglu and A. Ozdaglar, Opinion dynamics and learning in social networks, Dynam. Games Appl. 1 (2011) 3–49. Crossref, Web of Science, Google Scholar
2. G. Ajmone Marsan, N. Bellomo and L. Gibelli, Stochastic evolutionary differential games toward a systems theory of behavioral social dynamics, Math. Models Methods Appl. Sci. 26 (2016) 1051–1093. Link, Web of Science, Google Scholar
3. G. Albi, M. Herty and L. Pareschi, Kinetic description of optimal control problems and applications to opinion consensus, Commun. Math. Sci. 13 (2015) 1407–1429. Crossref, Web of Science, Google Scholar
4. G. Aletti, G. Naldi and G. Toscani, First-order continuous models of opinion formation, SIAM J. Appl. Math. 67 (2007) 837–853. Crossref, Web of Science, Google Scholar
5. O. Askari-Sichani and M. Jalili, Large-scale global optimization through consensus of opinions over complex networks, Complex Adapt. Syst. Model. 1 (2013) 11. Crossref, Google Scholar
6. N. Bellomo and F. Brezzi, Mathematics, complexity and multiscale features of large systems of self-propelled particles, Math. Models Methods Appl. Sci. 26 (2016) 207–214. Link, Web of Science, Google Scholar
7. N. Bellomo and C. Dogbe, On the modeling of traffic and crowds: A survey of models, speculations, and perspectives, SIAM Rev. 53 (2011) 409–463. Crossref, Web of Science, Google Scholar
8. N. Bellomo and L. Gibelli, Behavioral crowds: Modeling and Monte Carlo simulations toward validation, Comput. Fluids 141 (2016) 13–21. Crossref, Web of Science, Google Scholar
9. N. Bellomo, B. Piccoli and A. Tosin, Modeling crowd dynamics from a complex system viewpoint, Math. Models Methods Appl. Sci. 22 (2012) 1230004. Link, Web of Science, Google Scholar
10. F. Bolley, J. A. Cañizo and J. A. Carrillo, Stochastic mean-field limit: Non-Lipschitz forces and swarming, Math. Models Methods Appl. Sci. 21 (2011) 2179–2210. Link, Web of Science, Google Scholar
11. L. Boudin and F. Salvarani, A kinetic approach to the study of opinion formation, ESAIM: Math. Model. Numer. Anal. 43 (2009) 507–522. Crossref, Web of Science, Google Scholar
12. D. Burini, S. De Lillo and L. Gibelli, Collective learning modeling based on the kinetic theory of active particles, Phys. Life Rev. 16 (2016) 123–139. Crossref, Web of Science, Google Scholar
13. J. A. Carrillo, Y.-P. Choi, C. Totzeck and O. Tse, An analytical framework for a consensus-based global optimization method, preprint (2016), arXiv:1602.00220. Google Scholar
14. J. A. Carrillo, M. Fornasier, J. Rosado and G. Toscani, Asymptotic flocking dynamics for the kinetic Cucker–Smale model, SIAM J. Math. Anal. 42 (2010) 218–236. Crossref, Web of Science, Google Scholar
15. V. Cerny, A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm, J. Optim. Theory Appl. 45 (1985) 41–51. Crossref, Web of Science, Google Scholar
16. S. Chatterjee and E. Seneta, Towards consensus: Some convergence theorems on repeated averaging, J. Appl. Probab. 14 (1977) 89–97. Crossref, Web of Science, Google Scholar
17. B. Cockburn, Discontinuous Galerkin methods, ZAMM Z. Angew. Math. Mech. 83 (2003) 731–754. Crossref, Web of Science, Google Scholar
18. F. Cucker and S. Smale, Emergent behavior in flocks, IEEE Trans. Autom. Control 52 (2007) 852–862. Crossref, Web of Science, Google Scholar
19. F. Cucker and S. Smale, On the mathematics of emergence, Japan J. Math. 2 (2007) 197–227. Crossref, Web of Science, Google Scholar
20. M. H. DeGroot, Reaching a consensus, J. Amer. Statist. Assoc. 69 (1974) 118–121. Crossref, Web of Science, Google Scholar
21. A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Vol. 38 (Springer Science and Business Media, 2009). Google Scholar
22. R. L. Dobrushin, Ya. G. Sinai and Yu. M. Sukhov, Dynamical systems of statistical mechanics, in Dynamical Systems II (Springer, 1989), pp. 208–254. Crossref, Google Scholar
23. M. Dolfin and M. Lachowicz, Modeling opinion dynamics: How the network enhances consensus, Netw. Heterog. Media 10 (2015) 421–441. Crossref, Web of Science, Google Scholar
24. R. C. Eberhart and J. Kennedy, A new optimizer using particle swarm theory, in Proc. Sixth Int. Symp. Micro Machine and Human Science, Vol. 1 (IEEE, 1995), pp. 39–43. Google Scholar
25. L. Festinger, A Theory of Cognitive Dissonance, Vol. 2 (Stanford Univ. Press, 1962). Google Scholar
26. J. R. P. French, Jr., A formal theory of social power, Psychol. Rev. 63 (1956) 181. Crossref, Web of Science, Google Scholar
27. S. Galam, Sociophysics: A Physicist’s Modeling of Psycho-Political Phenomena (Springer Science and Business Media, 2012). Crossref, Google Scholar
28. S. Galam and S. Moscovici, Towards a theory of collective phenomena: Consensus and attitude changes in groups, European J. Social Psychol. 21 (1991) 49–74. Crossref, Web of Science, Google Scholar
29. S.-Y. Ha and E. Tadmor, From particle to kinetic and hydrodynamic descriptions of flocking, Kinet. Relat. Models 1 (2008) 415–435. Crossref, Web of Science, Google Scholar
30. R. Hegselmann and U. Krause, Opinion dynamics and bounded confidence models, analysis, and simulation, J. Artif. Soc. Social Simulat. 5 (2002) 1–33. Web of Science, Google Scholar
31. D. Helbing, Quantitative Sociodynamics: Stochastic Methods and Models of Social Interaction Processes (Springer Science and Business Media, 2010). Crossref, Google Scholar
32. D. J. Higham, An algorithmic introduction to numerical simulation of stochastic differential equations, SIAM Rev. 43 (2001) 525–546. Crossref, Web of Science, Google Scholar
33. M. Jamil and X.-S. Yang, A literature survey of benchmark functions for global optimisation problems, Int. J. Math. Model. Numer. Optim. 4 (2013) 150–194. Crossref, Google Scholar
34. P. Jia, A. MirTabatabaei, N. E. Friedkin and F. Bullo, Opinion dynamics and the evolution of social power in influence networks, SIAM Rev. 57 (2015) 367–397. Crossref, Web of Science, Google Scholar
35. D. Karaboga, B. Gorkemli, C. Ozturk and N. Karaboga, A comprehensive survey: Artificial bee colony (ABC) algorithm and applications, Artif. Intell. Rev. 42 (2014) 21–57. Crossref, Web of Science, Google Scholar
36. J. Kennedy, Particle swarm optimization, in Encyclopedia of Machine Learning (Springer, 2010), pp. 760–766. Google Scholar
37. S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, Optimization by simulated annealing, Science 220 (1983) 671–680. Crossref, Web of Science, Google Scholar
38. D. Knopoff, On a mathematical theory of complex systems on networks with application to opinion formation, Math. Models Methods Appl. Sci. 24 (2014) 405–426. Link, Web of Science, Google Scholar
39. U. Krause, A discrete nonlinear and non-autonomous model of consensus formation, in Communications in Difference Equations, Proc. of the Fourth Int. Conf. on Difference Equations, eds. S. Elaydi, G. Ladas, J. Popenda and J. Rakowski (CRC Press, 2000), pp. 227–236. Google Scholar
40. D. V. Kulkarni, D. V. Rovas and D. A. Tortorelli, A discontinuous Galerkin formulation for solution of parabolic equations on nonconforming meshes, in Domain Decomposition Methods in Science and Engineering XVI (Springer, 2007), pp. 651–658. Google Scholar
41. L. Marco and S. Fabio, Global Optimization. Theory, Algorithms, and Applications (Society for Industrial and Applied Mathematics (SIAM), 2013). Google Scholar
42. M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Trans. Model. Comput. Simulat. 8 (1998) 3–30. Crossref, Google Scholar
43. B. C. Mohan and R. Baskaran, A survey: Ant colony optimization-based recent research and implementation on several engineering domain, Expert Syst. Appl. 39 (2012) 4618–4627. Crossref, Web of Science, Google Scholar
44. G. Naldi, L. Pareschi and G. Toscani, Mathematical Modeling of Collective Behavior in Socio-Economic and Life Sciences (Springer Science and Business Media, 2010). Crossref, Google Scholar
45. C. E. Osgood and P. H. Tannenbaum, The principle of congruity in the prediction of attitude change, Psychol. Rev. 62 (1955) 42. Crossref, Web of Science, Google Scholar
46. L. Pareschi and G. Toscani, Interacting Multiagent Systems: Kinetic Equations and Monte Carlo Methods (Oxford Univ. Press, 2013). Google Scholar
47. K. E. Parsopoulos and M. N. Vrahatis, Recent approaches to global optimization problems through particle swarm optimization, Nat. Comput. 1 (2002) 235–306. Crossref, Google Scholar
48. R. Poli, J. Kennedy and T. Blackwell, Particle swarm optimization, Swarm Intell. 1 (2007) 33–57. Crossref, Google Scholar
49. M. Sebastien and T. Eitan, Heterophilious dynamics enhances consensus, SIAM Rev. 56 (2014) 577–621. Crossref, Web of Science, Google Scholar
50. G. Strang, On the construction and comparison of difference schemes, SIAM J. Numer. Anal. 5 (1968) 506–517. Crossref, Web of Science, Google Scholar
51. A.-S. Sznitman, Topics in propagation of chaos, in Ecole d’Et de Probabilits de Saint-Flour XIX 1989, ed. P.-L. Hennequin, Lecture Notes in Mathematics, Vol. 1464, (Springer, 1991), pp. 165–251. Crossref, Google Scholar
52. T. Vicsek, A. Czirók, E. Ben-Jacob, I. Cohen and O. Shochet, Novel type of phase transition in a system of self-driven particles, Phys. Rev. Lett. 75 (1995) 1226. Crossref, Web of Science, Google Scholar
53. C. Villani, Topics in Optimal Transportation (Amer. Math. Soc., 2003). Crossref, Google Scholar