Genetics in Action: Evolutionary Algorithms
ABSTRACT
Evolutionary algorithms help us solve optimization problems where we know what the answer is, but don't know how to get that answer. In this talk, we will look at how different evolutionary algorithms apply the concepts of genetics to discover formulas and patterns. Specifically, we will look at genetic algorithms and genetic programming, digging into how they work and solving a number of problems with each. We will also include a crash course on basic genetics, just in case high school biology isn't fresh in your mind.ADDITIONAL MEDIA
No recordings or additional media are available for this talk.SLIDES
Click here to access the slides for this presentation.
The slides are licensed under Creative Commons Attribution-ShareAlike.
DEMO CODE
Click here to access demo code for this presentation. This includes all of the R code used in demos. The demos are a set of notebooks running the R programming language. I used R version 4.4.1 and RStudio Desktop to run these.
The source code is licensed under the terms offered by the GPL.
LINKS & FURTHER INFO
I have a multi-part blog series covering this topic in further detail. This is for a prior variant of the talk.Creative Commons Attribution
The following is a Creative Commons attribution of each of the images used in this presentation.- Darwin's Finches by Gould. Author: John Gould.
- Human chromosome 18 with ASD genes. Author: Merlin G. Butler, et al.
- Gene. Courtesy: National Human Genome Research Institute.
- Punnett Square with Mendel Flowers. Author: Madeline Price Ball.
- Biogeographical Regions of Europe. Author: Julio Reis.
Books
- John Holland's Adaptation in Natural and Artificial Systems is a classic in the field. It is more math-heavy and doesn't really touch on the computer science aspects much, but is vital if you want to understand in detail the mathematics behind genetic algorithms.
- Melanie Mitchell followed up with An Introduction to Genetic Algorithms. I have not read this book, but Mitchell's reputation in the community is strong enough that I can recommend it on that alone.
- John Koza popularized genetic programming with his series of titles, starting with Genetic Programming. It's a long book and Koza's preferred language of Lisp can make it tough to follow if you don't know the language, but it is extremely helpful at explaining the topic. Koza had three follow-on books named Genetic Programming II-IV, but I have not looked at any of them.
Articles
- Melanie Mitchell provides an overview of genetic algorithms. This is an excerpt from her book, linked above.
- John Holland introduces genetic algorithms.
- Genetic Algorithms in Plain English. This provides a gentler introduction to the concept, skipping the math in favor of an explanatory example.
- Marek Obitko provides an interactive introduction to genetic algorithms. The page is old enough that it requires in-browser Java, but the concepts are good.
- Gail Shaw explains what genetic algorithms are.
- Genetic Algorithm enhanced by Deep Reinforcement Learning in parent selection mechanism and mutation by Irmouli, et al
- How is reinforcement learning related to genetic algorithms?
- Genetic Algorithms vs Neural Networks
- Genetic Algorithms + Neural Networks = Best of Both Worlds
- Using Genetic Algorithms to Evolve Artificial Neural Networks
- MarI/O - Machine Learning for Video Games (YouTube video)
Packages
- If you want to develop genetic algorithms in R, my favorite package is GA. They have a helpful vignette, as well as a paper describing extensions to the library.
- The most common Python library for genetic algorithms is PyGAD. It also ties in well with neural network libraries like Keras and PyTorch.
- Oliver Flasch wrote rgp as part of his dissertation. It is now defunct, having been removed from CRAN in 2018.
- An alternative package for symbolic regression is gramEvol. This is a grammatical evolution (GE) library rather than genetic programming, but there is some overlap in specific cases and it is still active.
- The R library I prefer for conditional genetic programs is evtree. The authors have a relatively short vignette showing how to use it.
- The most mature genetic algorithm/genetic programming library I have seen is ECJ. This is a Java library.
- In Python, gplearn is a neat library for symbolic regression in Python. It doesn't cover all genetic programming use cases but does cover one important one.
- On the .NET side, the Accord.NET Framework included the genetic libraries that used to be in AForge.NET. AForge included a few evolutionary algorithm samples but no source code. I recommend using a tool like Telerik JustDecompile to read the code and learn what's going on. Also, Accord.NET has been rendered defunct, so I can't really recommend it anymore.
Genetic Algorithms In T-SQL
- Gail Shaw has "a completely inappropriate use of SQL Server". As Gail notes, the things she had to do to get this to work are somewhat scary in a production environment, but as a fun challenge, it is quite informative.
- William Taleda builds a genetic algorithm to solve a room cleaning problem. His code is linked on the page, and also serves as an interesting exercise, but not something that I'd put into production.