Article summary
Nature is truly marvelous. The brilliance and complexity of the systems and organisms found in the natural world are unmatched by anything humans have ever created. Take, for example, the human eye. Will any camera ever compare to the speed and quality in which it can process dynamic scenes in nearly any lighting condition? How impressive is the speed at which our brains can recall facts, identify patterns, and draw conclusions so intuitively? It’s no wonder scientists have looked to the natural world as a source of inspiration for their technical innovations. In this post, I will describe one such example found in the world of computer science — genetic algorithms.
Defining a Genetic Algorithm
A genetic algorithm is a computational process that attempts to mimic the natural phenomenon of biological evolution to solve a complex problem. Biological evolution is the process in which traits of an organism change over time through successive generations via reproduction. Through natural selection, the organisms that are best suited for survival in their environment thrive and pass on their traits to future generations. Meanwhile, the less resilient die off. Similarly, genetic algorithms combine evolution and selection mechanisms to optimize a solution with a given set of constraints.
Use Cases
Genetic algorithms are not appropriate for solving all types of problems. However, they can be the ideal approach to determining a highly optimal solution to a problem where a truly ideal solution is either not possible or prohibitively expensive, computationally, otherwise. They can be a great tool for optimizing parameters to mathematical models as discussed in this previous Spin post. Genetic algorithms are powerful because they can solve problems humans don’t otherwise know how to solve. The only criterion is that we can recognize a good solution from a bad one.
This Wikipedia page contains a large list of use cases for genetic algorithms.
How They Work
The first step to creating a genetic algorithm is to identify a list of inputs to feed into the system. These inputs correspond to genes in biology. Collectively, all of the genes (inputs parameters) identified for the application make up the chromosome.
The genetic algorithm begins by creating an initial population of randomly generated chromosomes (sets of random inputs). Each chromosome is fed into the fitness function , which quantitatively determines how good a solution they produce. The fitness function takes the set of input parameters (the genes) and uses them to produce an output design using a consistent, domain-specific model or equation. This output design is then evaluated for its fitness, i.e., how close it is to an ideal solution.
After evaluating the entire population, a set of select chromosomes become the “parents” of the next generation. There are many different approaches for carrying out this selection, but all involve prioritizing chromosomes that produce a higher fitness score.
Next, using the selected parents, we create a new generation of offspring through a combination of genetic operators: crossover and mutation. Crossover involves combining the genes of the two parents to create one or more offspring that contain genetic material from both parents. This mimics sexual reproduction. Mutation involves making random modifications to gene values to create genetic diversity in the population. Genetic diversity helps prevent the system from converging on local optima rather than the global optimum.
After the new generation is constructed, you feed it into the fitness function. Then, the process repeats over and over until an acceptable solution has been reached or a certain amount of time has passed.
Wrapping Up
In summary, the process looks like this:
- Generate initial population of chromosomes
- Loop until satisfied with solution
- Evaluate fitness of each chromosome in population
- Select chromosomes to be parents
- Generate new population through crossover and mutation
Demonstrations
Below are a couple of demonstrations with great visualizations of genetic algorithms in action.