Simple Genetic Algorithm

The simple genetic algorithm is (as the name suggests) one of the simplest versions of a genetic algorithm.

In simple genetic algorithms, individuals are encoded as binary vectors (vectors of 0s and 1s). The algorithm works with these individuals and tries to simulate the Darwinian evolution.

In the beginning, a set of individuals (population) is randomly initialized. Afterwards, the algorithm runs iteratively (iterations are called generations). In each iteration, the quality (fitness) of each individual is evaluated and mating selection is performed. The mating selection creates a set of pairs of individuals that will create new offspring. Then, genetic operators (crossover and mutation) are applied to the individuals in the mating pool in order to create a set of offspring. Finally, the population is replaced by the new population of offspring.

The pseudo-code of the main loop of a simple EA is given below.

evolutionary_algorithm(fitness):
   pop = create_population(POP_SIZE)
   for G in 1..MAX_GEN:
       fits = map(fitness, pop)
       mating_pool = selection(pop, fits)
       offspring = operators(mating_pool)
       pop = offspring
   return pop

Genetic operators

There are various ways to implement the genetic operators, but the traditional ones are the so-called one-point crossover and bit-flip mutation. The one point crossover takes two parents and creates two offspring. It first selects a random crossover point in the parents, and one offspring is created by taking the initial part (before the crossover point) of one parent and the ending part of the other parent. The other offspring is created from the remaining parts.

The bit-flip mutation flips random bits in the individual.

Fitness function

The fitness function is problem specific and evaluates the quality of each individual. The evolutionary algorithm maximizes the fitness function. An example of a simple problem is so called OneMAX problem, where the goal is to find an individual which contains maximum number of 1s. In such a case, the fitness function can return the number of 1s in the individual.

Selection

The selection in evolutionary algorithms should favor individuals with better fitness, thus increasing their chance to create offspring. Again, there is a number of ways how to implement selection, the traditional one is the so called roulette wheel selection (or fitness-proportionate selection), where the probability of selecting an individual is proportionate to its fitness (this selection obviously requires the fitness to be non-negative).

Today’s seminar

Our goal today is to implement the simple genetic algorithm in Python. I will share my Python implementation with all of you after the seminar. We will use Python to solve the assignments this semester.