On Evolutionary Computation
Roman V. Yampolskiy
Editor’s note: Dr. Yampolskiy is Associate Professor in the department of Computer Engineering and Computer Science at the Speed School of Engineering, University of Louisville. In this series, he asks: “What Can and Can’t Darwin’s Algorithm Compute?” See also yesterday’s post, the first in the series, “What Can and Can’t Darwin’s Algorithm Compute?“
Inspired by Darwin’s theory1 of biological evolution, evolutionary computation attempts to automate the process of optimization and problem solving by simulating differential survival and reproduction of individual solutions. From the early 1950s, multiple well-documented attempts to make Darwin’s algorithm work on a computer have been published under such names as Evolutionary Programming12, Evolutionary Strategies13, Genetic Algorithms14, Genetic Programming15, Genetic Improvement16, Gene Expression Programming17, Differential Evolution18, Neuroevolution19, and Artificial Embryogeny20. While numerous variants different in their problem representation and metaheuristics exist21-24, all can be reduced to just two main approaches — Genetic Algorithm (GA) and Genetic Programming (GP).
GAs are used to evolve optimized solutions to a particular instance of a problem such as Shortest Total Path25, Maximum Clique26, Battleship27, Sudoku28, Mastermind23, Light Up29, Graph Coloring30, integer factorization31, 32, or efficient halftone patterns for printers33, and so are not the primary focus of this paper. GPs’ purpose, from their inception, was to automate programming by evolving an algorithm or a program for solving a particular class of problems, for example an efficient34 search algorithm. Software design is the type of application most frequently associated with GPs35, but work in automated programming is also sometimes referred to as “real programing,” “object-oriented GP,” “algorithmic programming,” “program synthesis,” “traditional programming,” “Turing Equivalent (TE) programming” or “Turing-complete GP”36-38.
Tremendous Growth
The sub-field of computation, inspired by evolution in general, and the Genetic Programing paradigm, established by John Koza in 1990s, in particular are thriving and growing exponentially. This is evidenced both by the number of practitioners and of scientific publications. Petke et al. observe “…enormous expansion of number of publications with the Genetic Programming Bibliography passing 10,000 entries … By 2016 there were nineteen GP books including several intended for students …”16. Such tremendous growth has been fueled, since the early days, by belief in the capabilities of evolutionary algorithms, and our ability to overcome obstacles of limited computational power or data as illustrated by the following comments:
“We will (before long) be able to run genetic algorithms on computers that are sufficiently fast to recreate on a human timescale the same amount of cumulative optimization power that the relevant processes of natural selection instantiated throughout our evolutionary past … ”39
“As computational devices improve in speed, larger problem spaces can be searched.”40
“Evolution is a slow learner, but the steady increase in computing power, and the fact that the algorithm is inherently suited to parallelization, mean that more and more generations can be executed within practically acceptable timescales.”41
“We believe that in about fifty years’ time it will be possible to program computers by means of evolution. Not merely possible but indeed prevalent.”42
“The relentless iteration of Moore’s law promises increased availability of computational resources in future years. If available computer capacity continues to double approximately every 18 months over the next decade or so, a computation requiring 80 h will require only about 1% as much computer time (i.e., about 48 min) a decade from now. That same computation will require only about 0.01% as much computer time (i.e., about 48 seconds) in two decades. Thus, looking forward, we believe that genetic programming can be expected to be increasingly used to automatically generate ever-more complex human-competitive results.”43
“The production of human-competitive results as well as the increased intricacy of the results are broadly correlated to increased availability of computing power tracked by Moore’s law. The production of human-competitive results using genetic programming has been greatly facilitated by the fact that genetic algorithms and other methods of evolutionary computation can be readily and efficiently parallelized. … Additionally, the production of human-competitive results using genetic programming has facilitated to an even greater degree by the increased availability of computing power, over a period of time, as tracked by Moore’s law. Indeed, over the past two decades, the number and level of intricacy of the human-competitive results has progressively grown. … [T]here is, nonetheless, data indicating that the production of human-competitive results using genetic programming is broadly correlated with the increased availability of computer power, from year to year, as tracked by Moore’s Law.”43
“[P]owerful test data generation techniques, an abundance of source code publicly available, and importance of nonfunctional properties have combined to create a technical and scientific environment ripe for the exploitation of genetic improvement.”40
Tomorrow, “State-of-the-Art in Evolutionary Computation.”
References:
Back, T., Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. 1996: Oxford university press.
Mayr, E., Behavior Programs and Evolutionary Strategies: Natural selection sometimes favors a genetically” closed” behavior program, sometimes an” open” one. American scientist, 1974. 62(6): p. 650-659.
Davis, L., Handbook of genetic algorithms. 1991: Van Nostrand Reinhold.
Koza, J.R., Genetic programming as a means for programming computers by natural selection. Statistics and computing, 1994. 4(2): p. 87-112.
Petke, J., et al., Genetic improvement of software: a comprehensive survey. IEEE Transactions on Evolutionary Computation, 2017.
Ferreira, C., Gene expression programming: mathematical modeling by an artificial intelligence. Vol. 21. 2006: Springer.
Storn, R. and K. Price, Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 1997. 11(4): p. 341-359.
Such, F.P., et al., Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning. arXiv preprint arXiv:1712.06567, 2017.
Stanley, K.O. and R. Miikkulainen, A taxonomy for artificial embryogeny. Artificial Life, 2003. 9(2): p. 93-130.
Yampolskiy, R.V., L. Ashby, and L. Hassan, Wisdom of Artificial Crowds—A Metaheuristic Algorithm for Optimization. Journal of Intelligent Learning Systems and Applications, 2012. 4(2): p. 98-107.
Yampolskiy, R.V. and A. El-Barkouky, Wisdom of artificial crowds algorithm for solving NP-hard problems. International Journal of Bio-inspired computation, 2011. 3(6): p. 358-369.
Khalifa, A.B. and R.V. Yampolskiy, GA with Wisdom of Artificial Crowds for Solving Mastermind Satisfiability Problem. Int. J. Intell. Games & Simulation, 2011. 6(2): p. 12-17.
Lowrance, C.J., O. Abdelwahab, and R.V. Yampolskiy. Evolution of a Metaheuristic for Aggregating Wisdom from Artificial Crowds. in Portuguese Conference on Artificial Intelligence. 2015. Springer.
Hundley, M.V. and R.V. Yampolskiy, Shortest Total Path Length Spanning Tree via Wisdom of Artificial Crowds Algorithm, in The 28th Modern Artificial Intelligence and Cognitive Science Conference (MAICS2017). April 28-29, 2017: Fort Wayne, IN, USA.
Ouch, R., K. Reese, and R.V. Yampolskiy. Hybrid Genetic Algorithm for the Maximum Clique Problem Combining Sharing and Migration. in MAICS. 2013.
Port, A.C. and R.V. Yampolskiy. Using a GA and Wisdom of Artificial Crowds to solve solitaire battleship puzzles. in Computer Games (CGAMES), 2012 17th International Conference on. 2012. IEEE.
Hughes, R. and R.V. Yampolskiy, Solving Sudoku Puzzles with Wisdom of Artificial Crowds. Int. J. Intell. Games & Simulation, 2012. 7(1): p. 24-29.
Ashby, L.H. and R.V. Yampolskiy. Genetic algorithm and Wisdom of Artificial Crowds algorithm applied to Light up. in Computer Games (CGAMES), 2011 16th International Conference on. 2011. IEEE.
Hindi, M. and R.V. Yampolskiy. Genetic Algorithm Applied to the Graph Coloring Problem. in MAICS. 2012.
Yampolskiy, R.V., Application of bio-inspired algorithm to the problem of integer factorisation. International Journal of Bio-Inspired Computation, 2010. 2(2): p. 115-123.
Mishra, M., S. Pal, and R. Yampolskiy, Nature-Inspired Computing Techniques for Integer Factorization. Evolutionary Computation: Techniques and Applications, 2016: p. 401.
Yampolskiy, R., et al. Printer model integrating genetic algorithm for improvement of halftone patterns. in Western New York Image Processing Workshop (WNYIPW). 2004. Citeseer.
Yampolskiy, R.V., Efficiency Theory: a Unifying Theory for Information, Computation and Intelligence. Journal of Discrete Mathematical Sciences and Cryptography, 2013. 16(4-5): p. 259-277.
Rylander, B., T. Soule, and J. Foster. Computational complexity, genetic programming, and implications. in European Conference on Genetic Programming. 2001. Springer.
White, D.R., et al., Better GP benchmarks: community survey results and proposals. Genetic Programming and Evolvable Machines, 2013. 14(1): p. 3-29.
Woodward, J.R. and R. Bai. Why evolution is not a good paradigm for program induction: a critique of genetic programming. in Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation. 2009. ACM.
Helmuth, T. and L. Spector. General program synthesis benchmark suite. in Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. 2015. ACM.
Shulman, C. and N. Bostrom, How hard is artificial intelligence? Evolutionary arguments and selection effects. Journal of Consciousness Studies, 2012. 19(7-8): p. 103-130.
Becker, K. and J. Gottschlich, AI Programmer: Autonomously Creating Software Programs Using Genetic Algorithms. arXiv preprint arXiv:1709.05703, 2017.
Eiben, A.E. and J. Smith, From evolutionary computation to the evolution of things. Nature, 2015. 521(7553): p. 476.
Orlov, M. and M. Sipper, FINCH: A system for evolving Java (bytecode), in Genetic Programming Theory and Practice VIII. 2011, Springer. p. 1-16.
Koza, J.R., Human-competitive results produced by genetic programming. Genetic Programming and Evolvable Machines, 2010. 11(3-4): p. 251-284.
No comments:
Post a Comment