Genetic Algorithms

TL;DR

Genetic algorithms (metaheuristics algorithms family) help us solve problems which are impossible, very hard or take too long to solve by other solutions.

Genetic algorithms are algorithms that uses evolution inspired approaches to solve problems that are too hard to solve using other methods. Genetic algorithms are called meta-heuristic because they don't solve problems in traditional way. They are a part of big metaheuristic algorithms family (e.g., ant algorithm, swarm algorithm). They are used to search for solution by trying to guess the best solution. Guessing means that we don't know the actual algorithm that will give us a final solution, we can't be sure that we will find a solution at all. Let's image a following function:

We can see that the space range, here is defined as:

 \[ x \in \{ 0 \dots 8 \}, y \in \{ 0 \dots 8 \} \]

As we can see there is one global maximum in this space at \( (x,y) = (8, 8) \). We can also see that we have two close "local maximums" \( (x,y) = (8, 2) \) and \( (x,y) = (2, 8) \). This function shows that randomly guessing the solution around the space may give us not the right maximum but we can "jump" into one of local maximums. That's the problem with meta-heuristics, we never know if we will find a solution. The big pros for that kind of methods is possibility of find a solution in the spaces where other algorithms fails, are to hard to implement or finding solution takes too much time.

Multiobjective optimization

Let's image a following problem. We have to plan chemotherapy treatment in a way that we need to minimize the amount of toxic drugs that cause unwanted side effects in human body. From the other way we want to kill the cancer cells therefore we can't limit the efficiency of treatment too much. No classic algorithm will help here. We have a huge space of possibilities because planning of chemotherapy requires from us to consider many important aspects of human body. We can't make to big injections of toxic substance to not kill the patient, we have to bare in mind his suffer/pain and take under considerations all the side effects. Let's remember that chemotherapeutic drugs are poisons.

Because of such many limitations of such treatment we will have a lot of constraints for our solution and all of them are important. Searching a solution for many different objectives is called multiobjective optimization. This is one of the most important field where genetic algorithms can help.

Having a set of objectives make it impossible to find one solution. In multiobjective optimization we search of number of optimal solutions creating a front of good solutions. We call it Pareto-optimal front. 

   Andre A.Keller, Multi-Objective optimization in theory and practice II:
Metaheuristic algorithms (book cover)

Above picture shows an example of Pareto front in three-dimensional space of solutions for 3 objective functions \( (f_1, f_2, f_3) \). The optimal solutions create a something looking like a fragment of sphere.

That could be an example of many different solutions of treatment, each dot can denote one plan of chemotherapy treatment.

Why good, why not?

Some people says that metaheuristics is like a crystal ball, you never know what you see and what you get. Others will say, thanks to the mutation and crossover operators in genetic algorithms we can even accidentally, but still, jump into the best solution. Opinions are divided. First opinion is some way true. Because of that unpredictability I prefer to use non-heuristic algorithms for well known problems. Imagine to use genetic algorithms for sorting, not really :-) Same with e.g. backpack problem, nooo.

But when you see a very hard problem, with a number of objectives, constraints and models you doubt, that you can find a classical algorithm to solve it. In such cases I prefer metaheuristics. I personally really like the origin of genetic algorithms, the ideas drawn from genetics and evolution. This inspiration from nature may be sometimes closer to the real world. Of course we always model things, problems are explained in functions then functions are calculated. Anyway, using special operators known from genetics and well known in nature may be really fascinating. Discovering new ways to mutate genes in our virtual population, or crossing over chromosomes is really interesting thing, believe me!

That's all for the intro. I encourage you to read other posts in the series Genetic Algorithms.