Genetic Algorithms (GAs)

Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.

GAs were developed by John Holland and his students and colleagues at the University of Michigan, most notably David E. Goldberg. It has since been tried on various optimization problems with a high degree of success.

In GAs, we have a pool of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), produces new children, and the process is repeated for various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield fitter individuals. This is in line with the Darwinian Theory of Survival of the Fittest.

Thus, it keeps evolving better individuals or solutions over generations, till it reaches a stopping criterion.

Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (where we just try random solutions, keeping track of the best so far), as they exploit historical information as well.

GA for Optimization Problems

Optimization is an action of making design, situation, resource and system, as effective as possible. The following block diagram shows the optimization process:

Stages of GA mechanism for optimization process

The following is a sequence of steps of GA mechanism when used for optimization of problems:

•  Step 1: Generate the initial population randomly.
•  Step 2: Select the initial solution with best fitness values.
•  Step 3: Recombine the selected solutions using mutation and crossover operators.
•  Step 4: Insert an offspring into the population.
•  Step 5: Now, if the stop condition is met, return the solution with their best fitness value. Else go to step 2.

Necessary Packages

For solving the problem by using Genetic Algorithms in Python, we are going to use a powerful package for GA called DEAP. It is a library of novel evolutionary computation framework for rapid prototyping and testing of ideas. We can install this package with the help of the following command on command prompt:

pip install deap

If you are using anaconda environment, then following command can be used to install deap:
conda install -c conda-forge deap

The next post will focus on implementation of solutions using Genetic Algorithms