nach oben

Soft Computing

Erschienen in:

01.07.2013 | Focus

Design and analysis of migration in parallel evolutionary algorithms

verfasst von: Jörg Lässig, Dirk Sudholt

Erschienen in: Soft Computing | Ausgabe 7/2013

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Parallelization is becoming a more important issue for solving difficult optimization problems. Island models combine phases of independent evolution with migration where genetic information is spread out to neighbored islands. This can lead to an increased diversity within the population. Despite many successful applications, the reasons behind the success of island models are not well understood. We perform a first rigorous runtime analysis for island models and construct a function where phases of independent evolution as well as communication among the islands are essential. A simple island model with migration finds a global optimum in polynomial time, while panmictic populations as well as island models without migration need exponential time, with very high probability. Our results lead to new insights into the usefulness of migration, how information is propagated in island models, and how to set parameters such as the migration interval. This is a novel contribution to the theoretical foundation of parallel EAs. Further, we provide empirical results that complement the theoretical results, investigate the robustness with respect to the choice of the migration interval and compare various migration topologies using statistical tests.

Vorheriger Artikel Complex and dynamic population structures: synthesis, open questions, and future directions

Nächster Artikel Adaptive three-dimensional cellular genetic algorithm for balancing exploration and exploitation processes

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 "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

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

Recall that this is a provably good value for \(\tau =50{,}000\) by Theorem 3. For other migration intervals, there generally is no provably good value, so for \(\tau \ne 50{,}000\) the choice of 25,000 is somewhat arbitrary.

Abramowitz M, Stegun IA (1964) Handbook of mathematical functions with formulas, graphs, and mathematical tables. 9th Dover printing, 10th GPO printing edition. Dover, New York

Alba E (2002) Parallel evolutionary algorithms can achieve super-linear performance. Inf Process Lett 82(1):7–13MathSciNetMATHCrossRef

Alba E (2005) Parallel metaheuristics: a new class of algorithms. Wiley-Interscience, New York

Baswana S, Biswas S, Doerr B, Friedrich T, Kurur PP, Neumann F (2009) Computing single source shortest paths using single-objective fitness functions. In: Proceedings of the 10th international workshop on foundations of genetic algorithms (FOGA ’09). ACM Press, New York, pp 59–66

Böttcher S, Doerr B, Neumann F (2011) Optimal fixed and adaptive mutation rates for the leadingones problem. In: 11th international conference on parallel problem solving from nature (PPSN 2010). LNCS, vol 6238. Springer, Berlin, pp 1–10

Cantú-Paz E (1997) A survey of parallel genetic algorithms. Technical report, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana Champaign, Urbana

Cantú-Paz E, Goldberg DE (1999) On the scalability of parallel genetic algorithms. Evol Comput 7(4):429–449CrossRef

Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. The MIT Press, Massachusetts

Doerr B, Gnewuch M, Hebbinghaus N, Neumann F (2007) A rigorous view on neutrality. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2007). IEEE Press, New Jersey, pp 2591–2597

Droste S, Jansen T, Wegener I (2002) On the analysis of the (1+1) evolutionary algorithm. Theoret Comput Sci 276:51–81MathSciNetMATHCrossRef

Friedrich T, Oliveto PS, Sudholt D, Witt C (2009) Analysis of diversity-preserving mechanisms for global exploration. Evol Comput 17(4):455–476CrossRef

Giacobini M, Tomassini M, Tettamanzi A (2003) Modelling selection intensity for linear cellular evolutionary algorithms. In: Proceedings of the sixth international conference on artificial evolution, evolution artificielle. Springer, Berlin, pp 345–356

Giacobini M, Alba E, Tettamanzi A, Tomassini M (2005a) Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Trans Evol Comput 9:489–505CrossRef

Giacobini M, Tomassini M, Tettamanzi A (2005b) Takeover time curves in random and small-world structured populations. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2005). ACM Press, New York, pp 1333–1340

He J, Yao X (2006) Analysis of scalable parallel evolutionary algorithms. In: Proceedings of the IEEE congress on evolutionary computation (CEC 2006), July 2006, pp 120–127

Jägersküpper J, Storch T (2007) When the plus strategy outperforms the comma strategy and when not. In: Proceedings of the IEEE symposium on foundations of computational intelligence, FOCI 2007. IEEE, New Jersey, pp 25–32

Jansen T, Wegener I (2005) Real royal road functions: where crossover provably is essential. Discrete Appl Math 149(1–3):111–125MathSciNetMATHCrossRef

Jansen T, De Jong KA, Wegener I (2005) On the choice of the offspring population size in evolutionary algorithms. Evol Comput 13:413–440CrossRef

Kötzing T, Sudholt D, Theile M (2011) How crossover helps in pseudo-Boolean optimization. In: Proceedings of the 13th annual genetic and evolutionary computation conference (GECCO 2011). ACM Press, New York, pp 989–996

Lässig J, Sudholt D (2010a) The benefit of migration in parallel evolutionary algorithms. In: Proceedings of the annual genetic and evolutionary computation conference (GECCO 2010), pp 1105–1112

Lässig J, Sudholt D (2010b) Experimental supplements to the theoretical analysis of migration in the island model. In: 11th international conference on parallel problem solving from nature (PPSN 2010). LNCS, vol 6238. Springer, Berlin, pp 224–233

Lässig J, Sudholt D (2010c) General scheme for analyzing running times of parallel evolutionary algorithms. In: 11th international conference on parallel problem solving from nature (PPSN 2010). Springer, Berlin, pp 234–243

Lässig J, Sudholt D (2011) Adaptive population models for offspring populations and parallel evolutionary algorithms. In: Proceedings of the 11th workshop on foundations of genetic algorithms (FOGA 2011). ACM Press, New York, pp 181–192

Luque G, Alba E (2010) Selection pressure and takeover time of distributed evolutionary algorithms. In: Proceedings of the annual genetic and evolutionary computation conference (GECCO 2010). ACM, New York, pp 1083–1088

Luque G, Alba E (2011) Parallel genetic algorithms theory and real world applications. In: Studies in computational intelligence, vol 367. Springer, Berlin

McMinn P (2013) An identification of program factors that impact crossover performance in evolutionary test input generation for the branch coverage of C programs. Inf Softw Technol (to appear). http://philmcminn.staff.shef.ac.uk/papers/2012-ist.pdf.

Mitzenmacher M, Upfal E (2005) Probability and computing. Cambridge University Press, Oxford

Neumann F, Oliveto PS, Rudolph G, Sudholt D (2011) On the effectiveness of crossover for migration in parallel evolutionary algorithms. In: Proceedings of the 13th annual genetic and evolutionary computation conference (GECCO 2011). ACM Press, New York, pp 1587–1594

Rudolph G (2000) On takeover times in spatially structured populations: array and ring. In: Proceedings of the 2nd Asia-Pacific conference on genetic algorithms and applications. Global-Link Publishing Company, Hong Kong, pp 144–151

Rudolph G (2006) Takeover time in parallel populations with migration. In: Proceedings of the second international conference on bioinspired optimization methods and their applications (BIOMA 2006), pp 63–72

Skolicki Z, De Jong K (2005) The influence of migration sizes and intervals on island models. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2005). ACM Press, New York, pp 1295–1302

Sudholt D (2005) Crossover is provably essential for the Ising model on trees. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2005). ACM Press, New York, pp 1161–1167

Sudholt D (2010) General lower bounds for the running time of evolutionary algorithms. In: 11th international conference on parallel problem solving from nature (PPSN 2010). LNCS, vol 6238. Springer, Berlin, pp 124–133

Teytaud F, Teytaud O (2010) Log(lambda) modifications for optimal parallelism. In: 11th international conference on parallel problem solving from nature (PPSN 2010). LNCS, vol 6238, pp 254–263

Tomassini M (2005) Spatially structured evolutionary algorithms: artificial evolution in space and time. Springer, Berlin

Watson RA, Jansen T (2007) A building-block royal road where crossover is provably essential. In: Proceedings of the genetic and evolutionary computation conference (GECCO 2007). ACM Press, New York, pp 1452–1459

Wegener I (2002) Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Sarker R, Yao X, Mohammadian M (eds) Evolutionary optimization. Kluwer, Dordrecht, pp 349–369

Wineberg M, Christensen S (2009) Statistical analysis for evolutionary computation: introduction. In: Companion of GECCO 2009. ACM Press, New York, pp 2949–2976

Witt C (2006) Runtime analysis of the (μ+1) EA on simple pseudo-Boolean functions. Evol Comput 14(1):65–86MathSciNet

Titel: Design and analysis of migration in parallel evolutionary algorithms
verfasst von: Jörg Lässig
Dirk Sudholt
Publikationsdatum: 01.07.2013
Verlag: Springer-Verlag
Erschienen in: Soft Computing / Ausgabe 7/2013
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-013-0991-0

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 7/2013

Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal

Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms

Special issue: Bio-inspired algorithms with structured populations

Multi-granulation rough sets based on tolerance relations

Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem

Complex and dynamic population structures: synthesis, open questions, and future directions

Premium Partner