nach oben

Soft Computing

Erschienen in:

01.08.2010 | Original Paper

Algorithm::Evolutionary, a flexible Perl module for evolutionary computation

verfasst von: Juan Julián Merelo Guervós, Pedro A. Castillo, Enrique Alba

Erschienen in: Soft Computing | Ausgabe 10/2010

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper describes Algorithm::Evolutionary ( A::E ), a Perl module released under an open source license and designed for the exploration and exploitation of evolutionary algorithms. We describe the design decisions taken to enhance flexibility, how performance was improved by using several implementation tweaks, and what kind of design patterns were applied for its development. This work also tries to dispel the myth of low performance of scripting languages by comparing it with a state-of-the-art library (ECJ) written in Java. Besides, we are interested in assessing its efficiency in several possible evolutionary settings, finding out what kind of behavior we can expect, and what can be done to improve it. Applications already written using A::E are also described, along with how it can be used to create new operators. Finally, some conclusions are drawn from the design experience.

Vorheriger Artikel A goal programming approach to group decision-making with three formats of incomplete preference relations

Nächster Artikel 0-homogeneous effect algebras

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

Tree::DAG_Node and Bit::Vector classes, and many more, can be found in the helpful CPAN, or Comprehensive Perl Archive Network.

Adam K (2008) Microsoft partners with Strawberry Perl to improve the CPAN. http://use.perl.org/∼Alias/journal/38036

Alba E, Dorronsoro B (2008) Cellular genetic algorithms. Springer, Berlin

Alba E, Troya J (2001) Gaining new fields of application for OOP: the parallel evolutionary algorithm case. J Object Orient Prog. Web-only version. Available from http://adtmag.com/articles/2001/12/01/gaining-new-fields-of-application-for-oop-the-parallel-evolutionary-algorithm-case.aspx

Alba E, Almeida F, Blesa M, Cotta C, Díaz M, Dorta I, Gabarró J, León C, Luque G, Petit J, et al (2006) Efficient parallel LAN/WAN algorithms for optimization. The MALLBA project. Parallel Comput 32(5–6):415–440CrossRef

Alcalá-Fdez J, Sánchez L, García S, del Jesus MJ, Ventura S, Garrell JM, Otero J, Romero C, Bacardit J, Rivas VM, Fernández JC, Herrera F (2009) KEEL: A software tool to assess evolutionary algorithms for data mining problems. Soft Comput 13(3):307–318CrossRef

Araujo L, Merelo-Guervós J, Cotta C, de Vega F (2008) MultiKulti algorithm: migrating the most different genotypes in an Island model. Arxiv preprint arXiv:0806.2843

Ashton E, Hietaniemi J (2006) CPAN frequently asked questions. Tech. rep., Cited 6/10/2006. http://www.cpan.org/misc/cpan-faq.html#What_is_CPAN

Back EC (2008) Ruby vs PHP performance revisited http://elliottback.com/wp/archives/2008/01/17/ruby-vs-php-performance-revisited/

Bäck T, Fogel D, Michalewicz Z (1997) Handbook of evolutionary computation. IOP Publishing Ltd, BristolMATHCrossRef

Baiocchi G (2004) Using Perl for statistics: data processing and statistical computing. J Stat Softw 11(1):1–81

Baldi M, Corno F, Rebaudengo M, Reorda MS, Squillero G (2000) Telecommunications optimization: heuristic and adaptive techniques. In: Corne D, Smith G, Oates MJ. chap. GA-based verification of network protocols performance. Wiley, Great Britain, pp 185–198

Bates D (1993) Data manipulation in Perl. Comput Sci Stat Tech. Rep., Available from http://www.ftp.wu-wien.ac.at/pub/lib/info/Data_in_perl.ps.gz

Blansit B (2006) Perl: the duct tape of the internet. J Electron Resour Med Librar 3(2):91CrossRef

blokhead : A beginning guide to evolutionary algorithms. Available from http://perlmonks.org/index.pl?node_id=298877 (2003)

Box D, Ehnebuske D, Kakivaya G, Layman A, Mendelsohn N, Nielsen H, Thatte S, Winer D (2000) Simple object access protocol (SOAP) 1.1. Available from http://www.w3.org/TR/soap/

Cahon S, Melab N, Talbi E (2004) ParadisEO: a framework for the reusable design of parallel and distributed metaheuristics. J Heuristics 10(3):357–380CrossRef

Castillo P, Arenas M, Castellano J, Merelo-Guervós JJ, Rivas V, Romero G (2002) Optimisation of multilayer perceptrons using a distributed evolutionary algorithm with SOAP. In: Guervós JJM, Adamidis P, Beyer HG, nas JLFV, Schwefel HP (eds) Parallel problem solving from nature—PPSN VII, 7th international conference, Granada, September 7–11, 2002. Proceedings, no. 2439 in Lecture Notes in Computer Science, LNCS. Springer, pp 676–688

Castillo P, Merelo J, Arenas M, Romero G (2007) Comparing evolutionary hybrid systems for design and optimization of multilayer perceptron structure along training parameters. Inform Sci 177:2884–2905. doi: 10.1016/j.ins.2007.02.021

Castillo P, Fernández G, Mora A, Merelo J, Bernier J, Prieto A (2008) Evolving machine microprograms. In: Genetic and evolutionary computation conference, GECCO2008. ACM Press, New York, pp 1103–1104

Dyer D (2008) Watchmaker framework for evolutionary computation - version 0.5.0. Available from http://blog.uncommons.org/2008/12/10/watchmaker-framework-for-evolutionary-computation-version-050/

Eiben AE, Smith JE (2003) Introduction to evolutionary computing. Springer, Berlin

Eiben A, Van Kemenade C, Kok J (1995) Orgy in the computer: multi-parent reproduction in genetic algorithms. In: Proceedings of the 3rd european conference on artificial life, no. 929 in LNAI. Springer, pp 934–945

Fallside DC (2004) XML Schema Part 0: Primer. Available from http://www.w3.org/TR/xmlschema-0/

Fourment M, Gillings M (2008) A comparison of common programming languages used in bioinformatics. BMC Bioinform 9(1):82CrossRef

Gagné C, Parizeau M (2006) Genericity in evolutionary computation software tools: principles and case-study. Int J Artif Intell Tools 15(2):173–194CrossRef

Gamma E, Helm R, Johnson R, Vlissides J (1993) Design patterns: abstraction and reuse of object-oriented design. In: ECOOP’93, object-oriented programming, 7th european conference, Kaiserslautern, July 26–30, 1993: Proceedings, Lecture Notes in Computer Science, vol 707. Springer, pp 406–431

García-Nieto J, Alba E, Chicano F (2007) Using metaheuristic algorithms remotely via ROS. In: GECCO ’07: Proceedings of the 9th annual conference on genetic and evolutionary computation. ACM, New York, pp 1510–1510. doi: http://doi.acm.org/10.1145/1276958.1277239

Giacobini M, Preuss M, Tomassini M (2006a) Effects of scale-free and small-world topologies on binary coded self-adaptive CEA. In: Evolutionary computation in combinatorial optimization: 6th european conference, EvoCOP 2006, Budapest, April 10–12, Proceedings. Springer

Giacobini M, Preuss M, Tomassini M (2006b) Effects of scale-free and small-world topologies on binary coded self-adaptive CEA. In: Gottlieb J, Raidl GR (eds) Evolutionary computation in combinatorial optimization—EvoCOP 2006, LNCS, vol 3906. Springer, Budapest, pp 85–96

gumpu : Genetic Programming or breeding Perls. Available from http://perlmonks.org/index.pl?node_id=31147 (2001)

Harold ER (2001) XML Bible. IDG Books worldwide

Hugman J (2003) mybeasties: an object ecosystem. Available from http://sourceforge.net/projects/mybeasties

Igel C, Heidrich-Meisner V, Glasmachers T (2008) Shark. J Mach Learn Res 9:993–996. http://www.scopus.com

Ingerson B, Evans C, Ben-Kiki O (2001) YAML 1.2 specification. Available from http://yaml.org/spec/1.2/

jweed : improving evolutionary algorithm. Available from http://perlmonks.org/index.pl?node_id=330315 (2004)

Keijzer M, Merelo-Guervós JJ, Romero G, Schoenauer M (2002) Evolving objects: a general purpose evolutionary computation library. In: Collet P, Fonlupt C, Hao JK, Lutton E, Schoenauer M (eds) Artificial evolution, 5th international conference, evolution artificielle, EA 2001, Le Creusot, France, October 29–31, 2001, Selected Papers, Lecture Notes in Computer Science, vol 2310. Springer, pp 231–244

Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220(4598):671–680CrossRefMathSciNet

Klein J, Spector L (2007) Unwitting distributed genetic programming via asynchronous JavaScript and XML. In: Proceedings of the 9th annual conference on genetic and evolutionary computation. ACM, New York, pp 1628–1635

Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press, CambridgeMATH

Kunken J (2001) The application of genetic algorithms in English vocabulary generation. In: Proceedings of the twelfth midwest artificial intelligence and cognitive science conference 2001. Miami University Press. Available also from http://www.ocf.berkeley.edu/∼jkunken/glot-bot/

Laredo JLJ, Eiben AE, Steen MV, Castillo PA, Mora AM, Merelo JJ (2008a) P2P evolutionary algorithms: a suitable approach for tackling large instances in hard optimization problems. In: 14th international euro-par conference, Las Palmas de Gran Canaria, Spain, August 26–29, 2008. Proceedings, pp 622–631. doi:10.1007/978-3-540-85451-7. http://dx.doi.org/10.1007/978-3-540-85451-7_66

Laredo JLJ, Eiben AE, Steen MV, Merelo JJ (2008b) On the run-time dynamics of a peer-to-peer evolutionary algorithm. In: Rudolph G, Jansen T, Lucas S, Poloni C, Beume N (eds) Parallel problem solving from nature - PPSN X, LNCS, vol 5199. Springer, Dortmund, pp 236–245. doi: 10.1007/978-3-540-87700-4_24

Lee W, Kim H (2005) Genetic algorithm implementation in python. In: Proceedings—fourth annual ACIS international conference on computer and information science, ICIS 2005, vol 2005, pp 8–12

Lenaerts T, Manderick B (1998) Building a genetic programming framework: the added-value of design patterns. In: Genetic programming: first european workshop, EuroGP’98: Paris, April 14–15, 1998: Proceedings. Springer, pp 196–208

Loui RP (2008) In praise of scripting: real programming pragmatism. IEEE Comput 41(7):22–26

Lukasz S (2009) AI::Genetic::Pro-efficient genetic algorithms for professional purpose. Available from http://search.cpan.org/∼strzelec/AI-Genetic-Pro-0.34/lib/AI/Genetic/Pro.pm

Luke S, et al (2009) ECJ: a java-based evolutionary computation and genetic programming research system. Available at http://www.cs.umd.edu/projects/plus/ec/ecj

MacCallum R (2003) Introducing a Perl genetic programming system–and can meta-evolution solve the bloat problem. In: Genetic programming, 6th european conference, EuroGP. Springer, pp 364–373

McPhee NF, Hopper NJ, Reierson ML (1998) Sutherland: an extensible object-oriented software framework for evolutionary computation. In: Koza JR, Banzhaf W, Chellapilla K, Deb K, Dorigo M, Fogel DB, Garzon MH, Goldberg DE, Iba H, Riolo R (eds) Genetic programming 1998: proceedings of the third annual conference, pp 22–25 Jul. Morgan Kaufmann, University of Wisconsin, Madison. http://www.mrs.umn.edu/∼mcphee/Research/Sutherland/sutherland_gp98_announcement.ps.gz

Merelo JJ, Castillo PA, Arenas MG, Romero G (2003) Specifying evolutionary algorithms in XML. In: Mira J, Álvarez (eds) 7th international work-conference on artificial and natural neural networks, IWANN 2003, number 2686–2687 in Lecture Notes in Computer Science, LNCS. pp 503–509. Springer. http://www.springerlink.com/link.asp?id=v6j34778lx0y43m0

Merelo JJ, García AM, Laredo JLJ, Lupión J, Tricas F (2007) Browser-based distributed evolutionary computation: performance and scaling behavior. In: GECCO ’07: proceedings of the 2007 GECCO conference companion on genetic and evolutionary computation, pp 2851–2858. ACM Press, New York. doi: http://doi.acm.org/10.1145/1274000.1274083

Merelo JJ, Castillo PA, Laredo JLJ, Mora A, Prieto A (2008a) Asynchronous distributed genetic algorithms with Javascript and JSON. In: WCCI 2008 Proceedings, pp 1372–1379. IEEE Press. http://atc.ugr.es/I+D+i/congresos/2008/CEC_2008_1372.pdf

Merelo JJ, Mora AM, Castillo PA, Laredo JLJ, Araujo L, Sharman KC, Esparcia-Alcázar AI, Alfaro-Cid E, Cotta C (2008b) Testing the intermediate disturbance hypothesis: effect of asynchronous population incorporation on multi-deme evolutionary algorithms. In: Rudolph G, Jansen T, Lucas S, Poloni C, Beume N (eds) Parallel problem solving from nature-PPSN X, LNCS, vol 5199, pp 266–275. Springer, Dortmund. doi: 10.1007/978-3-540-87700-4_27

Merelo-Guervós JJ (2002) Evolutionary computation in Perl. In: Perl Mongers M (ed) YAPC::Europe::2002, pp 2–22

Merelo-Guervós JJ, Castillo-Valdivieso P (2004) Conference paper assignment using a combined greedy/evolutionary algorithm. In: Yao X, Burke E, Lozano JA, Smith J, Guervós JJM, Bullinaria JA, Rowe J, Tino P, Kabán A, Schwefel HP (eds) Parallel problem solving from nature—PPSN VIII, no. 3242 in Lecture Notes in Computer Science,LNCS, pp 602–611. Springer

Merelo-Guervós JJ, Arenas MG, Carpio J, Castillo P, Rivas VM, Romero G, Schoenauer M (2000) Evolving objects. In: Wang PP (ed) Proc. JCIS 2000 (joint conference on information sciences), vol I, pp 1083–1086. ISBN: 0-9643456-9-2

Merelo-Guervós JJ, Prieto A (1996) gags, a flexible object-oriented library for evolutionary computation. In: Borrajo D, Isasi P (eds) MALFO96, Procs. of the first international workshop on machine learning, forecasting and optimization, pp 99–105. Available from http://neo.lcc.uma.es/EAWebSite/SKELETON/GPROG/gags-paper.ps.gz

Michalewicz Z (1996) Genetic Algorithms + Data Structures = Evolution programs, 3rd edn. Springer, Berlin

Mitchell M, Forrest S, Holland J (1992) The royal road for genetic algorithms: fitness landscapes and GA performance. In: Towards a practice of autonomous systems: proceedings of the first european conference on artificial life, pp 245–254

Murray B, Williams K (1999) Genetic algorithms with Perl. The Perl Journal 5(1). Also available from http://mathforum.org/∼ken/genetic/article.html

Networks O (2009) XML.com: XML from the inside out. Web site at http://www.xml.com

Neylon MK (2001) Algorithm :: Genetic. Available from http://perlmonks.org/index.pl?node_id=81678

Ousterhout JK (1998) Scripting: higher level programming for the 21st century. Computer 31(3):23–30

Pedersen T, Patwardhan S, Michelizzi J (2004) WordNet:: similarity-measuring the relatedness of concepts. In: Proceedings of the nineteenth national conference on artificial intelligence (AAAI-04) pp 1024–1025

Prechelt L (2000) An empirical comparison of seven programming languages. IEEE Comput 33(10):23–29. doi: http://doi.ieeecomputersociety.org/10.1109/2.876288

Ray ET (2001) Learning XML: creating self-describing data. O ’Reilly, Beijing

Raymond E (1998) Book review: the essential Perl books. Linux Journal 46es. Available from http://www.linuxjournal.com/article/2523

regeya : Why YAML? Why not? http://www.kuro5hin.org/story/2004/10/29/14225/062 (2004)

Schwartz RL, Phoenix T Foy BD (2008) Learning Perl, 5th edn. O ’Reilly & Associates, Sebastopol, CA, USA

Smith MA (1998) Building software frameworks for evolutionary computation. In: Porto VW, Saravanan N, Waagen DE, Eiben AE (eds) Evolutionary programming, Lecture Notes in Computer Science, vol 1447. Springer, pp 557–567

Stajich J, Block D, Boulez K, Brenner S, Chervitz S, Dagdigian C, Fuellen G, Gilbert J, Korf I, Lapp H, et al (2002) The bioperl toolkit: Perl modules for the life sciences. Genome Res 12(10):1611–1618. doi: 10.1101/gr.361602

Veenhuis C, Franke K, Kōppen M (2000) A semantic model for evolutionary computation. In: Proceedings IIZUKA ’00, pp 68–73

Ventura S, Romero C, Zafra A, Delgado J, Hervás C (2008) JCLEC: a java framework for evolutionary computation. Soft Comput 12(4):381–392

Wagner S, Winkler S, Pitzer E, Kronberger G, Beham A, Braune R, Affenzeller M (2007) Benefits of plugin-based heuristic optimization software systems. In: Proceedings computer aided systems theory EUROCAST 2007, Lecture Notes in Computer Science, vol 4739. Springer, p 747

Wainwright P, Calpini A, Corliss A, Cozens S, Powers S, Merelo-Guervós J, Saraf A, Nandor C (2001) Professional Perl programming. Wrox Press Inc. Available from http://www.amazon.com/exec/obidos/ASIN/1861004494 or http://www.amazon.co.uk/exec/obidos/ASIN/1861004494

Walker J (2005) Floating point benchmark: Comparing languages. http://www.fourmilab.ch/fourmilog/archives/2005-08/000567.html

Wall L, Christiansen T, Orwant J (2000) Programming Perl, 3rd edn. O ’Reilly & Associates

Whitley L (1993) Cellular genetic algorithms. In: Proceedings of the 5th international conference on genetic algorithms table of contents. Morgan Kaufmann Publishers Inc. San Francisco

Whitley D (1994) A genetic algorithm tutorial. Stat Comput 4(2):65–85CrossRef

Wilson GC, McIntyre A, Heywood MI (2004) Resource review: three open source systems for evolving programs—Lilgp, ECJ and grammatical evolution. Genetic Program Evol Mach 5(1):103–105CrossRef

Zlatanov T (2001) Cultured Perl:genetic algorithms applied with Perl create your own darwinian breeding grounds. Available from http://www106.ibm.com/developerworks/linux/library/lgenperl/

Titel: Algorithm::Evolutionary, a flexible Perl module for evolutionary computation
verfasst von: Juan Julián Merelo Guervós
Pedro A. Castillo
Enrique Alba
Publikationsdatum: 01.08.2010
Verlag: Springer-Verlag
Erschienen in: Soft Computing / Ausgabe 10/2010
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-009-0504-3

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 10/2010

Properties of $$\text{max-}*$$ fuzzy relation equations

Maps on a quantum logic

Variable-basis topological systems versus variable-basis topological spaces

Erratum to: Conditional states and independence in D-posets

Conditional states and independence in D-posets

On another view of an inverse of an interval matrix