Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Natural Computing 3/2021

18-11-2020

An Island Model based on Stigmergy to solve optimization problems

Authors: Grasiele Regina Duarte, Afonso Celso de Castro Lemonge, Leonardo Goliatt da Fonseca, Beatriz Souza Leite Pires de Lima

Published in: Natural Computing | Issue 3/2021

Login to get access
share
SHARE

Abstract

Island Model (IM) is an alternative often used to parallel Evolutionary Algorithms (EA). In IM, the population is distributed between islands that evolve their solutions in parallel, connected by a topology. Periodically, solutions migrate between islands according to a migration policy. The IM can be seen as an ideal structure to combine different algorithms to be used in an organized and cooperative way to solve a problem. Motivated by the number and distinction of EAs proposed in the last decades, in terms of performance and evolutionary behavior, this work proposes a hybrid configuration for IM, called Stigmergy Island Model (Stgm-IM), inspired by the natural phenomenon of stigmergy. Stigmergy is present in groups of some social species, and, by it, their agents organize themselves and maintain a level of cooperation through indirect communication. The Stgm-IM was evaluated regarding its evolutionary behavior and its performance on a benchmark suite of fifteen optimization problems, showing expected results.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 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

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Appendix
Available only for authorised users
Literature
go back to reference Alba E (2005) Parallel metaheuristics: a new class of algorithms. Wiley, Hoboken CrossRef Alba E (2005) Parallel metaheuristics: a new class of algorithms. Wiley, Hoboken CrossRef
go back to reference Bessaou M, Pétrowski A, Siarry P (2000) Island model cooperating with speciation for multimodal optimization. In: Schoenauer M, Deb K, Rudolph G, Yao X, Lutton E, Merelo JJ, Schwefel HP (eds) Parallel problem solving from nature PPSN VI. Springer, Berlin, pp 437–446 CrossRef Bessaou M, Pétrowski A, Siarry P (2000) Island model cooperating with speciation for multimodal optimization. In: Schoenauer M, Deb K, Rudolph G, Yao X, Lutton E, Merelo JJ, Schwefel HP (eds) Parallel problem solving from nature PPSN VI. Springer, Berlin, pp 437–446 CrossRef
go back to reference Bilal PM, Zaheer H, Garcia-Hernandez L, Abraham A (2020) Differential evolution: a review of more than two decades of research. Eng Appl Artif Intell 90:103479 CrossRef Bilal PM, Zaheer H, Garcia-Hernandez L, Abraham A (2020) Differential evolution: a review of more than two decades of research. Eng Appl Artif Intell 90:103479 CrossRef
go back to reference Bodenhofer U (2002) Genetic algorithms: theory and applications. Fuzzy Logic Laboratorium Linz, Hagenberg Bodenhofer U (2002) Genetic algorithms: theory and applications. Fuzzy Logic Laboratorium Linz, Hagenberg
go back to reference Bonabeau E (1998) Social insect colonies as complex adaptive systems. Ecosystems 1(5):437–443 CrossRef Bonabeau E (1998) Social insect colonies as complex adaptive systems. Ecosystems 1(5):437–443 CrossRef
go back to reference Candan C, Goeffon A, Lardeux F, Saubion F (2012) A dynamic island model for adaptive operator selection. In: Proceedings of the 14th annual conference on genetic and evolutionary computation, GECCO’12, pp. 1253–1260. Association for Computing Machinery, New York, NY, USA Candan C, Goeffon A, Lardeux F, Saubion F (2012) A dynamic island model for adaptive operator selection. In: Proceedings of the 14th annual conference on genetic and evolutionary computation, GECCO’12, pp. 1253–1260. Association for Computing Machinery, New York, NY, USA
go back to reference Cantú-Paz E (1998) A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et systems repartis 10(2):141–171 Cantú-Paz E (1998) A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et systems repartis 10(2):141–171
go back to reference Cantú-Paz E (2001) Migration policies, selection pressure, and parallel evolutionary algorithms. J Heuristics 7(4):311–334 CrossRef Cantú-Paz E (2001) Migration policies, selection pressure, and parallel evolutionary algorithms. J Heuristics 7(4):311–334 CrossRef
go back to reference Capriles PVSZ, Fonseca LG, Barbosa HJC, Lemonge ACC (2007) Rank-based ant colony algorithms for truss weight minimization with discrete variables. Commun Numer Methods Eng 23(6):553–575 MathSciNetCrossRef Capriles PVSZ, Fonseca LG, Barbosa HJC, Lemonge ACC (2007) Rank-based ant colony algorithms for truss weight minimization with discrete variables. Commun Numer Methods Eng 23(6):553–575 MathSciNetCrossRef
go back to reference Cheong PY, Aggarwal D, Hanne T, Dornberger R (2017) Variation of ant colony optimization parameters for solving the travelling salesman problem. In: 2017 IEEE 4th international conference on soft computing machine intelligence (ISCMI), pp 60–65 Cheong PY, Aggarwal D, Hanne T, Dornberger R (2017) Variation of ant colony optimization parameters for solving the travelling salesman problem. In: 2017 IEEE 4th international conference on soft computing machine intelligence (ISCMI), pp 60–65
go back to reference Crainic TG, Toulouse M (2003) Parallel strategies for meta-heuristics. Springer, Boston, pp 475–513 MATH Crainic TG, Toulouse M (2003) Parallel strategies for meta-heuristics. Springer, Boston, pp 475–513 MATH
go back to reference Dorigo M, Bonabeau E, Theraulaz G (2000) Ant algorithms and stigmergy. Fut Gen Comput Syst 16(8):851–871 CrossRef Dorigo M, Bonabeau E, Theraulaz G (2000) Ant algorithms and stigmergy. Fut Gen Comput Syst 16(8):851–871 CrossRef
go back to reference Dorigo M, Stützle T (2010) Ant colony optimization: overview and recent advances. Springer, Boston, pp 227–263 Dorigo M, Stützle T (2010) Ant colony optimization: overview and recent advances. Springer, Boston, pp 227–263
go back to reference Duarte G, Lemonge A, Goliatt L (2017) A dynamic migration policy to the island model. In: 2017 IEEE congress on evolutionary computation (CEC), pp 1135–1142 Duarte G, Lemonge A, Goliatt L (2017) A dynamic migration policy to the island model. In: 2017 IEEE congress on evolutionary computation (CEC), pp 1135–1142
go back to reference Duarte G, Lemonge A, Goliatt L (2018) A new strategy to evaluate the attractiveness in a dynamic island model. In: 2018 IEEE congress on evolutionary computation (CEC), pp 1–8 Duarte G, Lemonge A, Goliatt L (2018) A new strategy to evaluate the attractiveness in a dynamic island model. In: 2018 IEEE congress on evolutionary computation (CEC), pp 1–8
go back to reference Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the sixth international symposium on micro machine and human science, MHS’95. IEEE, pp 39–43 Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the sixth international symposium on micro machine and human science, MHS’95. IEEE, pp 39–43
go back to reference Gaertner D, Clark K (2005) On optimal parameters for ant colony optimization algorithms. In: Proceedings of the international conference on artificial intelligence 2005. CSREA Press, pp 83–89 Gaertner D, Clark K (2005) On optimal parameters for ant colony optimization algorithms. In: Proceedings of the international conference on artificial intelligence 2005. CSREA Press, pp 83–89
go back to reference Guan W, Szeto KY (2013) Topological effects on the performance of island model of parallel genetic algorithm. In: Proceedings of the 12th international conference on artificial neural networks: advances in computational intelligence—volume part II, IWANN’13. Springer, Heidelberg, pp 11–19 Guan W, Szeto KY (2013) Topological effects on the performance of island model of parallel genetic algorithm. In: Proceedings of the 12th international conference on artificial neural networks: advances in computational intelligence—volume part II, IWANN’13. Springer, Heidelberg, pp 11–19
go back to reference Gustafson S, Burke EK (2006) The speciating island model: an alternative parallel evolutionary algorithm. J Parall Distrib Comput 66(8):1025–1036 (special issue: parallel bioinspired algorithms) CrossRef Gustafson S, Burke EK (2006) The speciating island model: an alternative parallel evolutionary algorithm. J Parall Distrib Comput 66(8):1025–1036 (special issue: parallel bioinspired algorithms) CrossRef
go back to reference Izzo D, Rucinski M, Ampatzis C (2009) Parallel global optimisation meta-heuristics using an asynchronous island-model. In: 2009 IEEE congress on evolutionary computation, pp 2301–2308 Izzo D, Rucinski M, Ampatzis C (2009) Parallel global optimisation meta-heuristics using an asynchronous island-model. In: 2009 IEEE congress on evolutionary computation, pp 2301–2308
go back to reference Jadaan OA, Rajamani L, Rao CR (2005) Improved selection operator for ga. J Theor Appl Inf Technol 4:269–277 Jadaan OA, Rajamani L, Rao CR (2005) Improved selection operator for ga. J Theor Appl Inf Technol 4:269–277
go back to reference Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical report TR06, Erciyes University, Engineering Faculty, Kayseri, Turkiye Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical report TR06, Erciyes University, Engineering Faculty, Kayseri, Turkiye
go back to reference Karaboga D, Basturk B (2007) Artificial bee colony (abc) optimization algorithm for solving constrained optimization problems. In: Foundations of fuzzy logic and soft computing, vol 4529, pp 789–798. Springer, Berlin Karaboga D, Basturk B (2007) Artificial bee colony (abc) optimization algorithm for solving constrained optimization problems. In: Foundations of fuzzy logic and soft computing, vol 4529, pp 789–798. Springer, Berlin
go back to reference Kurdi M (2015) A new hybrid island model genetic algorithm for job shop scheduling problem. Comput Ind Eng 88(Supplement C):273–283 CrossRef Kurdi M (2015) A new hybrid island model genetic algorithm for job shop scheduling problem. Comput Ind Eng 88(Supplement C):273–283 CrossRef
go back to reference Li C, Yang S (2008) An island based hybrid evolutionary algorithm for optimization. Springer, Berlin, pp 180–189 Li C, Yang S (2008) An island based hybrid evolutionary algorithm for optimization. Springer, Berlin, pp 180–189
go back to reference Liang JJ, Qu BY, Suganthan PN, Chen Q (2014) Problem definitions and evaluation criteria for the cec 2015 competition on learning-based real-parameter single objective optimization. Technical report, Nanyang Technological University Liang JJ, Qu BY, Suganthan PN, Chen Q (2014) Problem definitions and evaluation criteria for the cec 2015 competition on learning-based real-parameter single objective optimization. Technical report, Nanyang Technological University
go back to reference Lynn N, Ali MZ, Suganthan PN (2018) Population topologies for particle swarm optimization and differential evolution. Swarm Evol Comput 39:24–35 CrossRef Lynn N, Ali MZ, Suganthan PN (2018) Population topologies for particle swarm optimization and differential evolution. Swarm Evol Comput 39:24–35 CrossRef
go back to reference Ma H, Shen S, Yu M, Yang Z, Fei M, Zhou H (2019) Multi-population techniques in nature inspired optimization algorithms: a comprehensive survey. Swarm Evol Comput 44:365–387 CrossRef Ma H, Shen S, Yu M, Yang Z, Fei M, Zhou H (2019) Multi-population techniques in nature inspired optimization algorithms: a comprehensive survey. Swarm Evol Comput 44:365–387 CrossRef
go back to reference Magalhaes TT, Krempser E, Barbosa HJC (2015) Migration policies to improve exploration in parallel island models for optimization via metaheuristics. In: Proceedings of the XXXVII Ibero-Latin American congress on computational methods in engineering, CILAMCE 2015 Magalhaes TT, Krempser E, Barbosa HJC (2015) Migration policies to improve exploration in parallel island models for optimization via metaheuristics. In: Proceedings of the XXXVII Ibero-Latin American congress on computational methods in engineering, CILAMCE 2015
go back to reference Meng Q, Wu J, Ellis J, Kennedy PJ (2017) Dynamic island model based on spectral clustering in genetic algorithm. In: 2017 international joint conference on neural networks (IJCNN), pp 1724–1731 Meng Q, Wu J, Ellis J, Kennedy PJ (2017) Dynamic island model based on spectral clustering in genetic algorithm. In: 2017 international joint conference on neural networks (IJCNN), pp 1724–1731
go back to reference Mezura-Montes E, Velázquez-Reyes J, Coello Coello CA (2006) A comparative study of differential evolution variants for global optimization. In: Proceedings of the 8th annual conference on genetic and evolutionary computation, GECCO’06, pp 485–492. ACM, New York Mezura-Montes E, Velázquez-Reyes J, Coello Coello CA (2006) A comparative study of differential evolution variants for global optimization. In: Proceedings of the 8th annual conference on genetic and evolutionary computation, GECCO’06, pp 485–492. ACM, New York
go back to reference Parpinelli RS, Lopes HS (2012) An ecology-based heterogeneous approach for cooperative search. In: Barros LN, Finger M, Pozo AT, Gimenénez-Lugo GA, Castilho M (eds) Advances in artificial intelligence—SBIA 2012. Springer, Berlin, pp 212–221 CrossRef Parpinelli RS, Lopes HS (2012) An ecology-based heterogeneous approach for cooperative search. In: Barros LN, Finger M, Pozo AT, Gimenénez-Lugo GA, Castilho M (eds) Advances in artificial intelligence—SBIA 2012. Springer, Berlin, pp 212–221 CrossRef
go back to reference Poli R, Kennedy J, Blackwell T (2007) Particle swarm optimization. Swarm Intell 1(1):33–57 CrossRef Poli R, Kennedy J, Blackwell T (2007) Particle swarm optimization. Swarm Intell 1(1):33–57 CrossRef
go back to reference Ruciński M, Izzo D, Biscani F (2010) On the impact of the migration topology on the island model. Parallel Comput 36(10–11):555–571 (parallel architectures and bioinspired algorithms) CrossRef Ruciński M, Izzo D, Biscani F (2010) On the impact of the migration topology on the island model. Parallel Comput 36(10–11):555–571 (parallel architectures and bioinspired algorithms) CrossRef
go back to reference Skolicki ZM (2007) An analysis of island models in evolutionary computation. Ph.D. thesis, Fairfax, VA, USA Skolicki ZM (2007) An analysis of island models in evolutionary computation. Ph.D. thesis, Fairfax, VA, USA
go back to reference Storn R, Price K (1997) Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359 MathSciNetCrossRef Storn R, Price K (1997) Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359 MathSciNetCrossRef
go back to reference Ursem RK (2000) Multinational gas: multimodal optimization techniques in dynamic environments. In: Proceedings of the 2nd annual conference on genetic and evolutionary computation, GECCO’00, pp 19–26. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA Ursem RK (2000) Multinational gas: multimodal optimization techniques in dynamic environments. In: Proceedings of the 2nd annual conference on genetic and evolutionary computation, GECCO’00, pp 19–26. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA
go back to reference Yu JJ, Li VO (2015) A social spider algorithm for global optimization. Appl Soft Comput 30:614–627 CrossRef Yu JJ, Li VO (2015) A social spider algorithm for global optimization. Appl Soft Comput 30:614–627 CrossRef
go back to reference Zhang Y, Wang S, Ji G (2015) A comprehensive survey on particle swarm optimization algorithm and its applications. Math Probl Eng 2015:1–38 Zhang Y, Wang S, Ji G (2015) A comprehensive survey on particle swarm optimization algorithm and its applications. Math Probl Eng 2015:1–38
Metadata
Title
An Island Model based on Stigmergy to solve optimization problems
Authors
Grasiele Regina Duarte
Afonso Celso de Castro Lemonge
Leonardo Goliatt da Fonseca
Beatriz Souza Leite Pires de Lima
Publication date
18-11-2020
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 3/2021
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-020-09819-x

Other articles of this Issue 3/2021

Natural Computing 3/2021 Go to the issue

EditorialNotes

Preface

Premium Partner