Skip to main content
Erschienen in: Natural Computing 3/2020

03.04.2018

A pattern-driven solution for designing multi-objective evolutionary algorithms

verfasst von: Giovani Guizzo, Silvia R. Vergilio

Erschienen in: Natural Computing | Ausgabe 3/2020

Einloggen

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

search-config
loading …

Abstract

Multi-objective evolutionary algorithms (MOEAs) have been widely studied in the literature, which led to the development of several frameworks and techniques to implement them. Consequently, the reusability, scalability and maintainability became fundamental concerns in the development of such algorithms. To this end, the use of design patterns (DPs) can benefit, ease and improve the design of MOEAs. DPs are reusable solutions for common design problems, which can be applied to almost any context. Despite their advantages to decrease coupling, increase flexibility, and allow an easier design extension, DPs have been underexplored for MOEA design. In order to contribute to this research topic, we propose a pattern-driven solution for the design of MOEAs. The MOEA designed with our solution is compared to another MOEA designed without it. The comparison considered: the Integration and Test Order (ITO) problem and the Traveling Salesman problem (TSP). Obtained results show that the use of this DP-driven solution allows the reuse of MOEA components, without decreasing the quality, in terms of hypervolume. This means that the developer can extend the algorithms to include other components using only object-oriented mechanisms in an easier way, while maintaining the expected results.

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!

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!

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!

Literatur
Zurück zum Zitat Alba E, Luque G, Nieto JG, Ordonez G, Leguizamon G (2007) MALLBA: a software library to design efficient optimisation algorithms. Int J Innov Comput Appl 1(1):74–85CrossRef Alba E, Luque G, Nieto JG, Ordonez G, Leguizamon G (2007) MALLBA: a software library to design efficient optimisation algorithms. Int J Innov Comput Appl 1(1):74–85CrossRef
Zurück zum Zitat Assunção WKG, Colanzi TE, Vergilio SR, Pozo A (2014) A multi-objective optimization approach for the integration and test order problem. Inf Sci 267:119–139MathSciNetCrossRef Assunção WKG, Colanzi TE, Vergilio SR, Pozo A (2014) A multi-objective optimization approach for the integration and test order problem. Inf Sci 267:119–139MathSciNetCrossRef
Zurück zum Zitat Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, Qu R (2013) Hyper-heuristics: a survey of the state of the art. J Oper Res Soc 64(12):1695–1724CrossRef Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, Qu R (2013) Hyper-heuristics: a survey of the state of the art. J Oper Res Soc 64(12):1695–1724CrossRef
Zurück zum Zitat Cahon S, Melab N, Talbi EG (2004) Paradiseo: A framework for the reusable design of parallel and distributed metaheuristics. J Heuristics 10(3):357–380MATHCrossRef Cahon S, Melab N, Talbi EG (2004) Paradiseo: A framework for the reusable design of parallel and distributed metaheuristics. J Heuristics 10(3):357–380MATHCrossRef
Zurück zum Zitat Coello CAC, Lamont GB, Veldhuizen DAV (2007) Evolutionary algorithms for solving multi-objective problems, 2nd edn. Springer, BerlinMATH Coello CAC, Lamont GB, Veldhuizen DAV (2007) Evolutionary algorithms for solving multi-objective problems, 2nd edn. Springer, BerlinMATH
Zurück zum Zitat Corder GW, Foreman DI (2009) Nonparametric statistics for non-statisticians: a step-by-step approach. Wiley, HobokenMATHCrossRef Corder GW, Foreman DI (2009) Nonparametric statistics for non-statisticians: a step-by-step approach. Wiley, HobokenMATHCrossRef
Zurück zum Zitat Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197 Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197
Zurück zum Zitat Eiben AE, Smit SK (2011) Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol Comput 1(1):19–31CrossRef Eiben AE, Smit SK (2011) Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol Comput 1(1):19–31CrossRef
Zurück zum Zitat Fernandez-Marquez JL, Di Marzo Serugendo G, Montagna S, Viroli M, Arcos JL (2013) Description and composition of bio-inspired design patterns: a complete overview. Nat Comput 12(1):43–67MathSciNetCrossRef Fernandez-Marquez JL, Di Marzo Serugendo G, Montagna S, Viroli M, Arcos JL (2013) Description and composition of bio-inspired design patterns: a complete overview. Nat Comput 12(1):43–67MathSciNetCrossRef
Zurück zum Zitat Fortin FA, De Rainville FM, Gardner MAG, Parizeau M, Gagné C (2012) DEAP: evolutionary algorithms made easy. J Mach Learn Res 13(1):2171–2175MathSciNet Fortin FA, De Rainville FM, Gardner MAG, Parizeau M, Gagné C (2012) DEAP: evolutionary algorithms made easy. J Mach Learn Res 13(1):2171–2175MathSciNet
Zurück zum Zitat Gamma E, Helm R, Johnson R, Vlissides J (1995) Design patterns: elements of reusable object-oriented software. Addison-Wesley Longman Publishing Co. Inc, BostanMATH Gamma E, Helm R, Johnson R, Vlissides J (1995) Design patterns: elements of reusable object-oriented software. Addison-Wesley Longman Publishing Co. Inc, BostanMATH
Zurück zum Zitat Garlan D, Shaw M (1994) An introduction to software architecture. In: Advances in software engineering and knowledge engineering. Publishing Company, pp 1–39 Garlan D, Shaw M (1994) An introduction to software architecture. In: Advances in software engineering and knowledge engineering. Publishing Company, pp 1–39
Zurück zum Zitat Guizzo G, Vergilio SR (2016) Metaheuristic design pattern: visitor for genetic operators. In: Brazilian conference on intelligent systems Guizzo G, Vergilio SR (2016) Metaheuristic design pattern: visitor for genetic operators. In: Brazilian conference on intelligent systems
Zurück zum Zitat Guizzo G, Fritsche GM, Vergilio SR, Pozo ATR (2015) A hyper-heuristic for the multi-objective integration and test order problem. In: Genetic and evolutionary computation conference. ACM, pp 1343–1350 Guizzo G, Fritsche GM, Vergilio SR, Pozo ATR (2015) A hyper-heuristic for the multi-objective integration and test order problem. In: Genetic and evolutionary computation conference. ACM, pp 1343–1350
Zurück zum Zitat Harman M, Mansouri SA, Zhang Y (2012) Search-based software engineering: trends. Tech Appl ACM Comput Surv 45(1):11–61 Harman M, Mansouri SA, Zhang Y (2012) Search-based software engineering: trends. Tech Appl ACM Comput Surv 45(1):11–61
Zurück zum Zitat Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press, CambridgeMATH Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press, CambridgeMATH
Zurück zum Zitat Krasnogor N (2012) Memetic algorithms. Springer, Berlin, pp 905–935 Krasnogor N (2012) Memetic algorithms. Springer, Berlin, pp 905–935
Zurück zum Zitat Lones MA (2014) Metaheuristics in nature-inspired algorithms. In: Genetic and evolutionary computation conference. ACM Press, pp 1419–1422 Lones MA (2014) Metaheuristics in nature-inspired algorithms. In: Genetic and evolutionary computation conference. ACM Press, pp 1419–1422
Zurück zum Zitat Mannava V, Ramesh T (2012) Load distribution design pattern for genetic algorithm based autonomic systems. Procedia Eng 38:1905–1915CrossRef Mannava V, Ramesh T (2012) Load distribution design pattern for genetic algorithm based autonomic systems. Procedia Eng 38:1905–1915CrossRef
Zurück zum Zitat Mariani T, Guizzo G, Vergilio SR, Pozo ATR (2016) A grammatical evolution hyper-heuristic for the integration and test order problem. In: Genetic and evolutionary computation conference. ACM, pp 1069–1076 Mariani T, Guizzo G, Vergilio SR, Pozo ATR (2016) A grammatical evolution hyper-heuristic for the integration and test order problem. In: Genetic and evolutionary computation conference. ACM, pp 1069–1076
Zurück zum Zitat Nebro AJ, Durillo JJ, Vergne M (2015) Redesigning the jMetal multi-objective optimization framework. In: Genetic and evolutionary computation conference. pp 1093–1100 Nebro AJ, Durillo JJ, Vergne M (2015) Redesigning the jMetal multi-objective optimization framework. In: Genetic and evolutionary computation conference. pp 1093–1100
Zurück zum Zitat Ochoa G, Hyde M, Curtois T, Vazquez-Rodriguez JA, Walker J, Gendreau M, Kendall G, Parkes AJ, Petrovic S, Burke EK (2012) HyFlex: A benchmark framework for cross-domain heuristic search. In: European conference on evolutionary computation in combinatorial optimization, Springer, pp 136–147 Ochoa G, Hyde M, Curtois T, Vazquez-Rodriguez JA, Walker J, Gendreau M, Kendall G, Parkes AJ, Petrovic S, Burke EK (2012) HyFlex: A benchmark framework for cross-domain heuristic search. In: European conference on evolutionary computation in combinatorial optimization, Springer, pp 136–147
Zurück zum Zitat Paquete L, Chiarandini M, Stützle T (2004) Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. Springer, Berlin, pp 177–199MATH Paquete L, Chiarandini M, Stützle T (2004) Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. Springer, Berlin, pp 177–199MATH
Zurück zum Zitat Patelli A, Bencomo N, Ekárt A, Goldingay H, Lewis P (2015) Two-B or not Two-B? Design patterns for hybrid metaheuristics. In: Genetic and evolutionary computation conference. ACM Press, pp 1269–1274 Patelli A, Bencomo N, Ekárt A, Goldingay H, Lewis P (2015) Two-B or not Two-B? Design patterns for hybrid metaheuristics. In: Genetic and evolutionary computation conference. ACM Press, pp 1269–1274
Zurück zum Zitat Ryan C, Collins JJ, Neill M (1998) Grammatical evolution: evolving programs for an arbitrary language. In: Genetic programming, vol 1391. Springer, pp 83–96 Ryan C, Collins JJ, Neill M (1998) Grammatical evolution: evolving programs for an arbitrary language. In: Genetic programming, vol 1391. Springer, pp 83–96
Zurück zum Zitat Tsyganov AV, Bulychov OI (2012) Implementing parallel metaheuristic optimization framework using metaprogramming and design patterns. Appl Mech Mater 263–266:1864–1873CrossRef Tsyganov AV, Bulychov OI (2012) Implementing parallel metaheuristic optimization framework using metaprogramming and design patterns. Appl Mech Mater 263–266:1864–1873CrossRef
Zurück zum Zitat Ventura S, Romero C, Zafra A, Delgado JA, Hervás C (2007) JCLEC: a Java framework for evolutionary computation. Soft Comput 12(4):381–392CrossRef Ventura S, Romero C, Zafra A, Delgado JA, Hervás C (2007) JCLEC: a Java framework for evolutionary computation. Soft Comput 12(4):381–392CrossRef
Zurück zum Zitat Wick MR, Phillips AT (2002) Comparing the template method and strategy design patterns in a genetic algorithm application. ACM SIGCSE Bull 34(4):76–80CrossRef Wick MR, Phillips AT (2002) Comparing the template method and strategy design patterns in a genetic algorithm application. ACM SIGCSE Bull 34(4):76–80CrossRef
Zurück zum Zitat Woodward J, Swan J, Martin S (2014) The ‘composite’ design pattern in metaheuristics. In: Genetic and evolutionary computation conference. ACM Press, pp 1439–1444 Woodward J, Swan J, Martin S (2014) The ‘composite’ design pattern in metaheuristics. In: Genetic and evolutionary computation conference. ACM Press, pp 1439–1444
Zurück zum Zitat Woodward JR, Swan J (2014) Template method hyper-heuristics. In: Genetic and evolutionary computation conference. ACM, pp 1437–1438 Woodward JR, Swan J (2014) Template method hyper-heuristics. In: Genetic and evolutionary computation conference. ACM, pp 1437–1438
Zurück zum Zitat Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength Pareto evolutionary algorithm. Technical report, Department of Electrical Engineering, Swiss Federal Institute of Technology Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength Pareto evolutionary algorithm. Technical report, Department of Electrical Engineering, Swiss Federal Institute of Technology
Zurück zum Zitat Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2):117–132CrossRef Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2):117–132CrossRef
Metadaten
Titel
A pattern-driven solution for designing multi-objective evolutionary algorithms
verfasst von
Giovani Guizzo
Silvia R. Vergilio
Publikationsdatum
03.04.2018
Verlag
Springer Netherlands
Erschienen in
Natural Computing / Ausgabe 3/2020
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-018-9677-y

Weitere Artikel der Ausgabe 3/2020

Natural Computing 3/2020 Zur Ausgabe

EditorialNotes

Preface