Artificial Darwinism: an Overview
Darwinisme Artificiel: une Vue d’Ensemble
OPEN ACCESS
Genetic algorithms,genetic programming,evolution strategies,and what is now called evolutionary algorithms,are stochastic optimisation techniques inspired by Darwin’s theory.We present here an overview of these techniques,while stressing on the extreme versatility of the artificial evolution concept.Their applicative framework is very large and is not limited to pure optimisation.Artifical evolution implementations are however computationally expensive:an efficient tuning of the components and parameter of these algorithms should be based on a clear comprehension of the evolutionary mechanisms.Moreover,it is noticeable that the killer-applications of the domain are for the most part based on hybridisation with other optimisation techniques.As a consequence,evolutionary algorithms are not to be considered in competition but rather in complement to the “classical”optimisation techniques.
Résumé
Les algorithmes génétiques,la programmation génétique,les stratégies d’évolution,et ce que l’on appelle maintenant en général les algorithmes évolutionnaires,sont des techniques d’optimisation stochastiques inspirées de la théorie de l’évolution selon Darwin. Nous donnons ici une vision globale de ces techniques, en insistant sur l’extrême flexibilité du concept d’évolution artificielle. Cet outil a un champ très vaste d’applications,qui ne se limite pas à l’optimisation pure. Leur mise en œuvre se fait cependant au prix d’un coût calculatoire important,d’où la nécessité de bien comprendre ces mécanismes d’évolution pour adapter et régler efficacement les différentes composantes de ces algorithmes. Par ailleurs,on note que les applications-phares de ce domaine sont assez souvent fondées sur une hybridation avec d’autres techniques d’optimisation. Les algorithmes évolutionnaires ne sont donc pas à considérer comme une méthode d’optimisation concurrente des méthodes d’optimisation classiques,mais plutôt comme une approche complémentaire.
Genetic Algorithms,genetic programing,evolution stategies,evolutionary algorithms,artificial evolution,artificial Darwinism,stochastic optimisation.
Mots clés
Algorithmes génétiques,programmation génétique,stratégies d’évolution,algorithmes évolutionnaires,évolution artificielle,Darwinisme artificiel,optimisation stochastique.
[1] ALBERT J., FERRI F., DOMINGO J., VINCENS M., An Approach to Natural Scene Segmentation by Means of Genetic Algoritms with Fuzzy Data. In Pattern Recognition and Image Analysis, 97-113, 1992. Selected papers of the 4th Spanish Symposium (Sept 90), Perez de la Blanca Ed.
[2] ALTENBERG L., Evolutionary computation models from population genetics. part 2: An historical toolbox. In Congress on Evolutionary Computation, 2000. Tutorial.
[3] ANGELINE P. J., Evolving fractal movies. In Genetic Programming 1996: Proceedings of the First Annual Conference, John R. Koza and David E. Goldberg and David B. Fogel and Rick L. Riolo (Eds), 503511, 1996.
[4] ANGELINE P. J., POLLACK J. B., Competitive environments evolve better solutions for complex tasks. In Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993. Morgan Kaufmann.
[5] BAECK T., HOFFMEISTER F., SCHWEFEL H.P.,A survey of evolution strategies. In International Conference on Genetic Algorithms, 2-10, 1991. 13-16 July.
[6] BAECK T., SCHWEFEL H. P., An overview of evolutionnary algorithms for parameter optimisation. Technical report, University of Dortmund, 1992.
[7] BAGLEY J. D., The Behaviour of adaptative systems which employ genetic and correlation algorithms. PhD thesis, University of Michigan, 1967. 5106B.
[8] BANZHAF W., Handbook of Evolutionary Computation, chapter Interactive Evolution. Oxford University Press, 1997.
[9] BEN HAMIDA S., Algorithmes évolutionnaires: prise en compte des contraintes et applications réelles. PhD thesis, Université Paris-Sud XI, spécialité informatique, 2001. 29 Mars 2001.
[10] BOUMAZA A., LOUCHET J., Dynamic flies: Using real-time evolution in robotics. In EVO-IASP 2001 Workshop, Artificial Evolution in Image Analysis and Signal Processing, 2001.
[11] BULL L., FOGARTY T. C., Co-evolving communicating classifier systems for tracking. p. 522-527, Innsbruck, Austria, 13-16. April 1993. Springer-Verlag, Wien.
[12] CAVICCIO D. J., Adaptative search using simulated evolution. PhD thesis, University of Michigan Press,Ann Arbor, 1970.
[13] CHAPUIS J., LUTTON E., Artie-fract: Interactive evolution of fractals. In 4th International Conference on Generative Art, Milano, Italy, December 12-14 2001.
[14] COHOON J. P., MARTIN W. N., RICHARDS D. S., Genetic algorithms punctuated equilibria in VLSI. In H. P. Schwefel and R.Männer, editors, Parallel Problem Solving from Nature Proceedings of 1st Workshop, PPSN 1, volume 496 of Lecture Notesin Computer Science, 134-144, Dortmund, Germany, 1-3 Oct 1991. Springer-Verlag, Berlin, Germany.
[15] COLLET P., LUTTON E., RAYNAL F., SCHŒNAUER M., Polar ifs + parisian Genetic Programming = efficient IFS inverse problem solving, Genetic Programming and Evolvable Machines Journal, 1(4):339-361, 2000. October.
[16] DAVIDOR Y., Robot programming with a genetic algorithm. In Proceedings of the 1990 IEEE International Conference on Computer Systems and Software Engineering, number Cat. No. 90CH2867-0, 186-191, Tel-Aviv, Israel, May, 8-10 1990. IEEE Computer Society Press, Los Alamitos, CA.
[17] DAVIDOR Y., Genetic Algorithms Robotics. A heuristic Strategy for Optimization. World Scientific Series in Robotics and Automated Systems - vol 1. World Scientific, Teaneck, NJ, 1991.
[18] DAVIS L., Genetic Algorithms Simulated Annealing. Pittman, London, 1987.
[19] DAVIS T. E., PRINCIPE J. C., A Simulated Annealing Like Convergence Theory for the Simple Genetic Algorithm. In Proceedings of the Fourth International Conference on Genetic Algorithm, 174-182, 1991. 13-16 July.
[20] DORIGO M., DI CARO G., The ant colony optimization meta-heuristic. New Ideas in Optimization, 11-32, 1999. D. Corne, M. Dorigo and F. Glover, editors, McGraw-Hill.
[21] DORIGO M., DI CARO G., GAMBARDELLA L. M., Ant algorithms for discrete optimization. Artificial Life, 5(2):137-172, 1999.
[22] FOGEL D. B.,An analysis of evolutionary programming. In D.B. Fogel and W. Atmar, editors, Proceedings of the First Annual Conference on Evolutionary Programming, 43-51, La Jolla, California, 1992.
[23] FOGEL D. B., Asymptotic convergence properties of genetic algorithms evolutionary programming:Analysis experiments. In Journal of Mathematical Biology, 1992.
[24] GOLDBERG D. E., Zen and the art of genetic algorithms. In Third International Conference on Genetic Algorithms, 1989.
[25] GOLDBERGD. E.,Genetic Algorithms in Search,Optimization, and Machine Learning. Addison-Wesley Publishing Company, inc., Reading, MA, January 1989.
[26] GOLDBERG D. E., Genetic algorithms and rule learning in dynamic system control. In ICGA85, 8-15, 1985.
[27] GOLDBERG D. E., KORB B., DEB K., Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems, 3(5):493530, October 1989.
[28] GOLDBERG D. E., RICHARDSON J., Genetic algorithms with sharing for multimodal function optimization. In J. J. Grefenstette, editor, Genetic Algorithms and their Applications, 41-49, Hillsdale, New Jersey, 1987. Lawrence Erlbaum Associates.
[29] GOLDBERG D. E., SMITH R. E., Nonstationary function optimization using genetic algorithms with dominance and diploidy. In J. J. Grefenstette, editor, Proceedings of the second international conference on genetic algorithms and their applications, 59-68, Hillsdale, New Jersey, 1987. Lawrence Erlbaum Associates.
[30] HAMDA H., JOUVE F., LUTTON E., SCHŒNAUER M., SEBAG M., Compact unstructured representations in evolutionary topological optimum design. Applied Intelligence, 16, 2002.
[31] HILL A., TAYLOR C. J., Model-Based Image Interpretation using Genetic Algorithms. Image and Vision Computing, 10(5):295-301, June 1992.
[32] HILLIS W. D., Co-evolving parasites improve simulated evolution as an optimization procedure. 228-234, Cambridge, MA, 1990. MIT Press / North-Holl. (also as Physica D, Vol. 42).
[33] HOFFMEISTER F., BÄCK T., Genetic algorithms evolution strategies: similarities and differences. In H. P. Schwefel and R. Männer, editors, Parallel Problem Solving from Nature - Proceedings of 1st Workshop, PPSN 1, volume 496 of Lecture Notes in Computer Science, 455-469, Dortmund, Germany, 1-3 Oct 1991. SpringerVerlag, Berlin, Germany.
[34] HOFFMEISTER F., BAECK T., Genetic algorithms and evolution strategies: Similarities and differences. Technical Report SYS-1/92, University of Dortmund, February 1992.
[35] HOLLAND J. H.,. Outline for a logical theory of adaptative systems. Journal of the association for the Computing Machinery, (3):297314, 1962.
[36] HOLLAND J. H, Adaptation in Natural and Artificial System. Ann Arbor, University of Michigan Press, 1975.
[37] HOLLSTIEN R. B., Artificial genetic adaptation in computer control systems. PhD thesis, University of Michigan, 1971. 1510B.
[38] HORN J., Finite Markov Chain Analysis of Genetic Algorithms with Niching. IlliGAL Report 93002, University of Illinois at Urbana Champaign, Department of General Engineering, 117 Transportation Building, 104 South Mathews Avenue, Urbana, IL 61801-2996, February 1993.
[39] HUSBANDS P., MILL F., Simulated co-evolution as the mechanism for emergent planning scheduling. 264-270, San Diego, 13.-16. July 1991. Morgan Kaufmann Publishers.
[40] DE JONG K. A., Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan, 1975. 5140B.
[41] KAMOHARA S.,TAKAGI H.,TAKEDA T., Control rule acquisition for an arm wrestling robot. In IEEE Int. Conf. on System, Man Cybernetics (SMC’97), volume 5, Orlo, FL, USA, 1997.
[42] KAUFFMANS. A.,JOHNSENS.,Co-evolution to the edge of chaos: Coupled fitness landscapes, poised states, co-evolutionary avalanches. In ALifeII conference, 1992.
[43] KOJIMA K.-I., editor. Mathematical Topics in Population Genetics, volume 1. Springer-Verlag, Berlin, 1970. Biomathematics.
[44] KOZA J. R., Genetic Programming. MIT Press, 1992.
[45] KOZA J. R.,Evolution and cœvolution of computer programs to control independently acting agents. In Proceedings SAB90, 366-375, 1990.
[46] KOZA J. R.,. Genetic evolution and co-evolution of computer programs. In ALifeII conference, 603-629, 1991.
[47] LANDRIN-SCHWEITZER Y., COLLET P., LUTTON E., Interactive gp for data retrieval in medical databases. In EUROGP’03. LNCS, Springer Verlag, 2003.
[48] LANDRIN-SCHWEITZER Y., COLLET P., LUTTON E., PROST T., Introducing lateral thinking in search engines with interactiveevolutionary algorithms. In Annual ACM Symposium on Applied Computing (SAC 2003), Special Track on "Computer Applications in Health Care" (COMPAHEC 2003), 2003. March 9 to 12, Melbourne, Florida, U.S.A.
[49] LANGDON W. B., Quadratic bloat in genetic programming. In Darrell Whitley, David Goldberg, Erick Cantu-Paz, Lee Spector, Ian Parmee, and Hans-Georg Beyer, editors, Proceedings of the Genetic Evolutionary Computation Conference (GECCO-2000),451-458,Las Vegas, Nevada, USA, 10-12 2000. Morgan Kaufmann.
[50] LANGDON W. B., BANZHAF W., Genetic programming bloat without semantics. In M. Schœnauer, K. Deb, G. Rudolf, X. Yao, E. Lutton, Merelo. J.J., H.-P. Schwefel, editors, Parallel Problem Solving from Nature - PPSN VI 6th International Conference, Paris, France, September 16-20 2000. Springer Verlag. LNCS 1917.
[51] LARRANAGA P., LOZANO J. A., Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.
[52] LERICHE R., HAFTKA R.T., Optimization of laminate stacking sequence for buckling load maximization by genetic algorithm. AIAA Journal, 31(5):951-969, May 1993.
[53] LOUCHET J., GUYON M., LESOT M.-J., BOUMAZA A., Dynamic flies: a new pattern recognition tool applied to stereo sequence processing. Pattern Recognition Letters, 2002. No. 23, 335-345, Elsevier Science B.V.
[54] LUTTON E., COLLET P., LOUCHET J., Easea comparisons on test functions: Galib versus eo. In EA01 Conference on Artificial Evolution, Le Creusot, octobre 2001.
[55] LÉVY VÉHEL J., LUTTON E., Evolutionary signal enhancement based on hölder regularity analysis. In EVO-IASP 2001 Workshop, Artificial Evolution in Image Analysis and Signal Processing, 2001.
[56] MAULDIN M. L., Maintening diversity in genetic search. In Proceedings of the National Conference on Artificial Intelligence, 1984.
[57] MICHALEWICZ Z., Genetic Algorithms + Data Structures = Evolution Programs. Artificial Intelligence. Springer Verlag, New York, 1992.
[58] MONMARCHE N., NOCENT G.,. VENTURINI G,. SANTINI P., Artificial Evolution, European Conference, AE 99, Dunkerque, France, November 1999, Selected papers, volume Lecture Notes in Computer Science 1829, chapter On Generating HTML Style Sheets with an Interactive Genetic Algorithm Based on Gene Frequencies. Springer Verlag, 1999.
[59] MUHLENBEIN H., PAASS G., From recombination of genes to the estimation of distributions. i. binary parameters. In Parallel Problem Solving from Nature, 1996.
[60] NIX A..E., VOSE M. D., Modeling genetic algorithms with markov chains. Annals of Mathematics and Artificial Intelligence, 5(1):79-88, April 1992.
[61] O’NEILL M., RYAN C., Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4),August 2001.
[62] O’NEILL M., RYAN C., Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language (Genetic Programming, 4) Kluwer Academic Publishers, May 2003.
[63] PELIKAN M., GOLDBERG D. G., LOBO F,. A survey of optimization by building using probabilistic models. Computational Optimization Applications, (21):5-20, 2002. also as IlliGAL Report No 99018.
[64] POLI R., CAGNONI S., Genetic programming with user-driven selection: Experiments on the evolution of algorithms for image enhancement. In 2nd Annual Conf. on Genetic Programming, 1997.
[65] PRÜGEL-BENNETT A., ROGERS A., chapter Modelling GA Dynamics., p.59-86. Theoretical Aspects of Evolutionary Computing: proceedings of the Second EvoNet Summer School, Antwerp, 1999, Springer, 2001.
[66] RECHENBERG I., Evolutionsstrategie: Optimierung Technicher System nach Prinzipien der Biologischen Evolution. Fromman Holzboog, Stuttgart, 1973.
[67] ROOKE S., The evolutionary art of steven rooke. http://www.azstarnet.com/~srooke/.
[68] ROSENBERG R. S., Simulation of genetic populations with biochemical properties. PhD thesis, University of Michigan, 1967. 2732B.
[69] ROTH G., LEVINE M. D., Geometric Primitive Extraction Using a Genetic Algorithm. In IEEE Computer Society Conference on CV PR, 640-644, 1992.
[70] RYAN C., NICOLAU M., O’NEILL M., Genetic algorithms using grammatical evolution. In Springer Verlag, editor, Proceedings of EuroGP 2002, 2002.
[71] SCHWEFEL H-P., Evolutionsstrategie und numerische Optimierung. PhD thesis, Technische Universitat, Berlin, may 1975.
[72] SCHWEFEL H-P., Numerical Optimization of Computer Models. John Wiley & sons, New-York, 1981, 1995 2nd edition.
[73] SHAPIRO J. L., PRÜGEL-BENNETT A., Maximum entropy analysis of genetic algorithm operators. Lecture Notes in Computer Science, 993:14-24, 1995.
[74] SHAPIRO J. L., RATTRAY M., PRÜGEL-BENNETT A., The statistical mechanics theory of genetic algorithm dynamics. In First International Conference on Evolutionary Computation and Its Applications, Moscow, 1996. Plenary Lecture.
[75] SIEGEL E., Competively evolving decision trees against fixed training cases for natural language processing. In Advances in Genetic Programming, 1994. ed. Kim Kinnear. Cambridge, MA: MIT Press.
[76] SIMS K., Interactive evolution of dynamical systems. In First European Conference on Artificial Life, 171-178, 1991. Paris, December.
[77] SIMS K., Artificial evolution for computer graphics. Computer Graphics, 25(4):319-328, July 1991.
[78] SMITH R. E., GOLDBERG D. E., Diploidy and dominance in artificial genetic search. Complex Systems, 6:251-285, 1992.
[79] SOULE T., FOSTER J. A., DICKINSON J., Code growth in genetic programming. In John R. Koza, David E. Goldberg, David B. Fogel, and Rick L. Riolo, editors, Genetic Programming 1996: Proceedingsof the First Annual Conference, 215-223, Stanford University, CA, USA, 28-31 1996. MIT Press.
[80] TAKAGI H., Interactive evolutionary computation: System optimisation based on human subjective evaluation. In IEEE Int. Conf. on Intelligent Engineering Systems (INES’98),Vienna,Austria, Sept 1719 1998.
[81] TAKAGI H.,OHSAKI M.,Iec-based hearing aids fitting. In IEEE Int. Conf. on System, Man and Cybernetics (SMC’99), volume 3, Tokyo, Japan, Oct. 12-15 1999.
[82] TODD S. J. P., LATHAM W., Evolutionary Art and Computers. Academic Press, 1992.
[83] TROMPETTE P., MARCELIN J. L., SCHMELDING C., Optimal damping of viscœlastic constrained beams or plates by use of a genetic algotithm. In IUTAM, 1993. Zakopane Pologne.
[84] TRUVÉ S., Using a Genetic Algorithm to solve Constraint Satisfation Problems Generated by an Image Interpreter. In Theory and Applications of Image Analysis: 7th Scandinavian Conference on Image Analysis, 378-386,August 1991. Aalborg (DK).
[85] LÉVY VÉHEL J., LUTTON E., Optimization of fractal functions using genetic algorithms. In Fractal 93, 1993. London.
[86] VOSE M., Modeling simple genetic algorithms. In FOGA-92, Foundations of Genetic Algorithms, Vail, Colorado, 24-29 July 1992. Email: vose@cs.utk.edu.
[87] ZITZLER E., DEB K., THIELE L., Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2):173-195, 2000.