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

In the simple genetic algorithms, individuals are encoded as a binary vector (vector 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 bellow.

 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 how to implement the genetic operators, but the traditional ones are 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 creating by taking the remaining parts.


The bit flip mutation changes random bits in the individual to the other value.


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 positive).


Today's seminar


Our goal today is to implement the simple genetic algorithm in a programming language of your choice. I will share a Python implementation with all of you after the seminar. In the rest of the seminars this year, you can choose if you want to use Python or Java to solve the assignments. A description of the Java sources and implementation of a general evolutionary algorithm is available on a separate page.
Последнее изменение: вторник, 8 октября 2019, 12:38