nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Convergence Analysis of Swarm Intelligence Metaheuristic Methods

verfasst von : Tatjana Davidović, Tatjana Jakšić Krüger

Erschienen in: Optimization Problems and Their Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Intensive applications and success of metaheuristics in practice have initiated research on their theoretical analysis. Due to the unknown quality of reported solution(s) and the inherently stochastic nature of metaheuristics, the theoretical analysis of their asymptotic convergence towards a global optimum is mainly conducted by means of probability theory. In this paper, we show that principles developed for the theoretical analysis of Bee Colony Optimization metaheuristic hold for swarm intelligence based metaheuristics: they need to implement learning mechanisms in order to properly adapt the probability rule for modification of a candidate solution. We propose selection schemes that a swarm intelligence based metaheuristic needs to incorporate in order to assure the so-called model convergence.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Fuzzy Core Allocations in a Mixed Economy of Arrow-Debreu Type

Nächstes Kapitel An Optimization Model for Empty Tank Cars Movement at Railway Petroleum Logistics Market

Nur mit Berechtigung zugänglich

In [10] the author mistakenly reported that the sequence \(\{B(t)\}_{t=1}^{\infty }\) is non-decreasing.

Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York (1999)MATH

Chen, J., Ni, J., Hua, M.: Convergence analysis of a class of computational intelligence approaches. Math. Probl. Eng. 2013, 1–10 (2013)MathSciNetMATH

Davidović, T., Teodorović, D., Šelmić, M.: Bee Colony Optimization- Part I: the algorithm overview. Yugoslav J. Oper. Res. 25(1), 33–56 (2015)MathSciNetCrossRef

Dorigo, M., Birattari, M.: Swarm intelligence. Scholarpedia 2(9), 1462 (2007). http://www.scholarpedia.org/Swarm_intelligenceCrossRef

Dorigo, M., Blum, C.: Ant Colony Optimization theory: a survey. Theor. Comput. Sci. 344, 243–278 (2005)MathSciNetCrossRef

Dorigo, M., Stützle, T.: Ant Colony Optimization: overview and recent advances. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. ISOR, vol. 146, pp. 227–263. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5_8CrossRef

Garcia-Gonzalo, E., Fernandez-Martinez, J.L.: A brief historical review of Particle Swarm Optimization (PSO). J. Bioinform. Intell. Contr. 1(1), 3–16 (2012)CrossRef

Gutjahr, W.J.: A graph-based ant system and its convergence. Future Gener. Comput. Syst. 16(8), 873–888 (2000)CrossRef

Gutjahr, W.J.: ACO algorithms with guaranteed convergence to the optimal solution. Inf. Process. Lett. 82(3), 145–153 (2002)MathSciNetCrossRef

10.

Gutjahr, W.J.: Convergence analysis of metaheuristics. In: Maniezzo, V., Stützle, T., Voß, S. (eds.) Matheuristics: Hybridizing Metaheuristics and Mathematical Programming. AOIS, vol. 10, pp. 159–187. Springer, Boston (2009). https://doi.org/10.1007/978-1-4419-1306-7_6CrossRef

11.

Gutjahr, W.J.: Stochastic search in metaheuristics. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. ISOR, vol. 146, pp. 573–597. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5_19CrossRef

12.

Gutjahr, W.J.: Ant colony optimization: recent developments in theoretical analysis. In: Auger, A., Doerr, B. (eds.) Theory of Randomized Search Heuristics: Foundations and Recent Developments, pp. 225–254. World Scientific (2011). https://www.worldscientific.com/worldscibooks/10.1142/7438MATH

13.

Jacobson, S.H., Yücesan, E.: Global optimization performance measures for generalized hill climbing algorithms. J. Global Optim. 29(2), 173–190 (2004)MathSciNetCrossRef

14.

Jakšic Krüger, T.: Development, implementation and theoretical analysis of the Bee Colony Optimization metaheuristic method. Ph.D. thesis, University of Novi Sad (2017)

15.

Jakšić Krüger, T., Davidović, T.: Model convergence properties of the constructive Bee Colony Optimization algorithm. In: Proceedings of 41th Symposium on Operational Research, SYM-OP-IS 2014, pp. 340–345 (2014)

16.

Jakšić Krüger, T., Davidović, T., Teodorović, D., Šelmić, M.: The Bee Colony Optimization algorithm and its convergence. Int. J. Bio-Inspired Comput. 8(5), 340–354 (2016)CrossRef

17.

Jiang, M., Luo, Y., Yang, S.: Stochastic convergence analysis and parameter selection of the standard Particle Swarm Optimization algorithm. Inf. Process. Lett. 102(1), 8–16 (2007)MathSciNetCrossRef

18.

Karaboga, D., Gorkemli, B., Ozturk, C., Karaboga, N.: A comprehensive survey: Artificial Bee Colony (ABC) algorithm and applications. Artif. Intell. Rev. 42, 21–57 (2014)CrossRef

19.

Kötzing, T., Neumann, F., Röglin, H., Witt, C.: Theoretical analysis of two ACO approaches for the Traveling Salesman Problem. Swarm Intell. 6(1), 1–21 (2012)CrossRef

20.

Liu, H., Abraham, A., Snásel, V.: Convergence analysis of swarm algorithm. In: NaBIC, pp. 1714–1719 (2009)

21.

Parpinelli, R.S., Lopes, H.S.: New inspirations in swarm intelligence: a survey. Int. J. Bio-Inspired Comput. 3(1), 1–16 (2011)CrossRef

22.

Pintér, J.: Convergence properties of stochastic optimization procedures. Optimization 15(3), 405–427 (1984)MathSciNetMATH

23.

Solis, F.J., Wets, R.J.B.: Minimization by random search techniques. Math. Oper. Res. 6(1), 19–30 (1981)MathSciNetCrossRef

24.

Stützle, T., Dorigo, M.: A short convergence proof for a class of Ant Colony Optimization algorithms. IEEE Trans. Evol. Comput. 6(4), 358–365 (2002)CrossRef

25.

Talbi, E.G.: Metaheuristics: From Design to Implementation. Wiley, New York (2009)CrossRef

26.

Trelea, I.C.: The Particle Swarm Optimization algorithm: convergence analysis and parameter selection. Inf. Process. Lett. 85(6), 317–325 (2003)MathSciNetCrossRef

27.

Van Den Bergh, F.: An analysis of Particle Swarm Optimizers. Ph.D. thesis, University of Pretoria (2006)

28.

Yang, X.-S.: Metaheuristic optimization: algorithm analysis and open problems. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 21–32. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20662-7_2CrossRef

29.

Zeng, J.C., Cui, Z.H.: A guaranteed global convergence Particle Swarm Optimizer. J. Comput. Res. Dev. 8, 1333–1338 (2004)MATH

30.

Zlochin, M., Birattari, M., Meuleau, N., Dorigo, M.: Model-based search for combinatorial optimization: a critical survey. Ann. Oper. Res. 131(1–4), 373–395 (2004)MathSciNetCrossRef

31.

Zlochin, M., Dorigo, M.: Model-based search for combinatorial optimization: a comparative study. In: Guervós, J.J.M., Adamidis, P., Beyer, H.-G., Schwefel, H.-P., Fernández-Villacañas, J.-L. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 651–661. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45712-7_63CrossRef

Titel: Convergence Analysis of Swarm Intelligence Metaheuristic Methods
verfasst von: Tatjana Davidović
Tatjana Jakšić Krüger
Verlag: Springer International Publishing
Buch: Optimization Problems and Their Applications
Print ISBN: 978-3-319-93799-1

Electronic ISBN: 978-3-319-93800-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93800-4_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"