About Genetic Algorithms

What is a Genetic Algorithm good for?

Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints

Sometimes the constraints on the arguments of a problem are very generous in size. The number of permutations makes solving the optimization in a brute-force way impractical.

Using a generational genetic algorithm can drastically shorten the time needed to find a solution.

The genetic algorithm repeatedly modifies a population of individual solutions until an individual (or a set of individuals) with a fitness value above the threshold is found.

Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to next generation

The general procedure is shown here in python code:

def mainloop(): 
    # We start with a randomly created population
    population = create_population(NUM_INDIVIDUALS) 
    generation_count = 0 

    # evaluate population and return index and max score
    index,res = evaluate_population(population)

    # sort the population based on score
    population = sort_population(population)
 
    print(f"Generation: {generation_count}")
    while generation_count < MAX_GENERATIONS: 
        # remove part pf population with bad score
        population = killoff_deadbeats(population)

        # Let the winners re-create. Children inherits DNA from parents and sometimes mutate
        population = mate(population)

        # re-evaluate and sort
        index,res = evaluate_population(population)
        population = sort_population(population)
        generation_count = generation_count + 1
        print(f"Generation: {generation_count}")

Explanations

A genetic algorithms most important features are the 1) the fitness function, ie a function that evaluates the DNA of the individual and calculates a score, by which the individual can be compared to others and 2) the crossover, or mating, where new individuals are created from parents, and some DNA is passed on to the child, and possibly also mutated.

In each generation, the population is sorted according to its fitness score, and the individuals with poor scores are removed. The remaining population is then used as a gene pool to mate and create new individuals. This process is called crossover, but I use to think of it as mating. How the DNA is mixed from the parents is decided by the algorithm. It could be picked 50/50 (if there are two parents), or weighted depending on the score of the parents.

The re-generations occur until a max number of generations have passed, or a good enough score has been achieved.

The Individual and the Population

The size of the population will mainly decide the computation time it takes to finish, so it will have to be a compromise between accuracy (large population) and cputime (smaller population).

The DNA

The DNA can be designed any way you want it. Easiest is to just construct an array of values that are used by the fitness function.

The Fitness function

Should be a pure function and always calculate the same score for a DNA.

Crossover and Mutation

Lots of possibilities here, on how to generate new individuals in the crossover/mating process. The generation could involve any number of individuals, it doesnt even have to be one “father” and one “mother”. Whether the new DNA should be constructed with half the DNA from one parent and half from another is also up to you. Perhaps it could be weighed depending on the score oif the “parents”. A random component could also be introduced.

However it is important that the “childs” DNA has an element of mutation, maybe in 1% of the cases. This ensures that the population evolves and that new features that fit the environment are created.

Conclusion

A genetic algorithm is not an answer in itself, but an optimisation tool when “brute force” is too computationally intensive.

It is suitable when there are too many arguments to use other tools like linear regression etc.

It can be used to quickly find answers that suit the environment, but note that the answer is always just a “best fit” at the moment. There might be better answers that haven’t been found yet.

Genetic Algorithms might be used to control other algos, or neural networks, by generating the parameters, calculating a score and let the good ones live, and kill off the ones that doesnt lead to satisfactory results.

References

There are plenty of good resources out there. I like the videos by The Coding Train and The Nature of Code.

But there are also plenty of great books. Here are a few:

Genetic Algorithms with Python (Wirsansky)

Genetic Algorithms and Machine Learning for Programmers: Create AI Models and Evolve Solutions (Buontempo)

An Introduction to Genetic Algorithms (Mitchell)