Top

Published in:

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

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article A framework for designing of genetic operators automatically based on gene expression programming and differential evolution

next article Absolute versus stochastic stability of the artificial bee colony in synchronous and sequential modes

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

Abdelhafez A, Alba E, Luque G (2019) Performance analysis of synchronous and asynchronous distributed genetic algorithms on multiprocessors. Swarm Evol Comput 49:147–157. https://doi.org/10.1016/j.swevo.2019.06.003CrossRef

Alba E (2005) Parallel metaheuristics: a new class of algorithms. Wiley, HobokenCrossRef

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–446CrossRef

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:103479CrossRef

Bodenhofer U (2002) Genetic algorithms: theory and applications. Fuzzy Logic Laboratorium Linz, Hagenberg

Bonabeau E (1998) Social insect colonies as complex adaptive systems. Ecosystems 1(5):437–443CrossRef

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

Cantú-Paz E (1998) A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et systems repartis 10(2):141–171

Cantú-Paz E (2001) Migration policies, selection pressure, and parallel evolutionary algorithms. J Heuristics 7(4):311–334CrossRef

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–575MathSciNetCrossRef

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

Crainic TG, Toulouse M (2003) Parallel strategies for meta-heuristics. Springer, Boston, pp 475–513MATH

Dolan ED, More JJ (2002) Benchmarking optimization software with performance profiles. Math Progr 91(2):201–213MathSciNetCrossRef

Dorigo M, Bonabeau E, Theraulaz G (2000) Ant algorithms and stigmergy. Fut Gen Comput Syst 16(8):851–871CrossRef

Dorigo M, Stützle T (2010) Ant colony optimization: overview and recent advances. Springer, Boston, pp 227–263

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 (2018) A new strategy to evaluate the attractiveness in a dynamic island model. In: 2018 IEEE congress on evolutionary computation (CEC), pp 1–8

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

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

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

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

Holland JH (1973) Genetic algorithms and the optimal allocation of trials. SIAM J Comput 2(2):88–105MathSciNetCrossRef

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

Jadaan OA, Rajamani L, Rao CR (2005) Improved selection operator for ga. J Theor Appl Inf Technol 4:269–277

Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Technical report TR06, Erciyes University, Engineering Faculty, Kayseri, Turkiye

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

Kurdi M (2015) A new hybrid island model genetic algorithm for job shop scheduling problem. Comput Ind Eng 88(Supplement C):273–283CrossRef

Lardeux F, Maturana J, Rodriguez-Tello E, Saubion F (2019) Migration policies in dynamic island models. Nat Comput Int J 18(1):163–179. https://doi.org/10.1007/s11047-017-9660-zMathSciNetCrossRef

Li C, Yang S (2008) An island based hybrid evolutionary algorithm for optimization. Springer, Berlin, pp 180–189

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

Lynn N, Ali MZ, Suganthan PN (2018) Population topologies for particle swarm optimization and differential evolution. Swarm Evol Comput 39:24–35CrossRef

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–387CrossRef

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

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

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

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–221CrossRef

Poli R, Kennedy J, Blackwell T (2007) Particle swarm optimization. Swarm Intell 1(1):33–57CrossRef

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

Skolicki ZM (2007) An analysis of island models in evolutionary computation. Ph.D. thesis, Fairfax, VA, USA

Storn R, Price K (1997) Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359MathSciNetCrossRef

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

Yu JJ, Li VO (2015) A social spider algorithm for global optimization. Appl Soft Comput 30:614–627CrossRef

Zhang Y, Wang S, Ji G (2015) A comprehensive survey on particle swarm optimization algorithm and its applications. Math Probl Eng 2015:1–38

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

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2021

On the use of -evolution strategy as efficient local search mechanism for discrete optimization: a behavioral analysis

Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations

An evaluation of k-means as a local search operator in hybrid memetic group search optimization for data clustering

Absolute versus stochastic stability of the artificial bee colony in synchronous and sequential modes

Improving convergence in swarm algorithms by controlling range of random movement

On the class of hybrid adaptive evolutionary algorithms (chavela)

Premium Partner