What exactly are genetic algorithms and what sort of problems are they good for?

Question

I've noticed that a few questions on this site mention genetic algorithms and it made me realize that I don't really know much about those.

I have heard the term before, but it's not something I've ever used, so I don't have much idea about how they work and what they are good for. All I know is that they involve some sort of evolution and randomly changing values.

Can you give me a short explanation, preferably including some sort of practical example that illustrates the basic principles?

Answer 1

Evolutionary algorithms are a family of optimization algorithms based on the principle of Darwinian natural selection. As part of natural selection, a given environment has a population of individuals that compete for survival and reproduction. The ability of each individual to achieve these goals determines their chance to have children, in other words, to pass on their genes to the next generation of individuals, who, for genetic reasons, will have an increased chance of doing well, even better, in realizing these two objectives.

This principle of continuous improvement over the generations is taken by evolutionary algorithms to optimize solutions to a problem. In the initial generation, a population composed of different individuals is generated randomly or by other methods. An individual is a solution to the problem, more or less good: the quality of the individual in regards to the problem is called fitness, which reflects the adequacy of the solution to the problem to be solved. The higher the fitness of an individual, the higher it is likely to pass some or all of its genotype to the individuals of the next generation.

An individual is coded as a genotype, which can have any shape, such as a bit vector (genetic algorithms) or a vector of real (evolution strategies). Each genotype is transformed into a phenotype when assessing the individual, i.e. when its fitness is calculated. In some cases, the phenotype is identical to the genotype: it is called direct coding. Otherwise, the coding is called indirect. For example, suppose you want to optimize the size of a rectangular parallelepiped defined by its length, height and width. To simplify the example, assume that these three quantities are integers between 0 and 15. We can then describe each of them using a 4-bit binary number. An example of a potential solution may be to genotype 0001 0111 1010. The corresponding phenotype is a parallelepiped of length 1, height 7 and width 10.

During the transition from the old to the new generation, the variation operators, whose purpose is to manipulate individuals, are applied. There are two distinct types of variation operators:

• the mutation operators, which are used to introduce variations within the same individual, as genetic mutations;
• the crossover operators, which are used to cross at least two different genotypes, as genetic crosses from breeding.

Evolutionary algorithms have proven themselves in various fields such as operations research, robotics, biology, nuance, or cryptography. In addition, they can optimize multiple objectives simultaneously and can be used as black boxes because they do not assume any properties in the mathematical model to optimize. Their only real limitation is the computational complexity.

Answer 2

A genetic algorithm is an algorithm that randomly generates a number of attempted solutions for a problem. This set of attempted solutions is called the "population".

It then tries to see how well these solutions solve the problem, using a given fitness function. The attempted solutions with the best fitness value are used to generate a new population. This can be done by making small changes to the attempted solutions (mutation) or by combining existing attempted solutions (crossover).

The idea is that, over time, an attempted solution emerges that has a high enough fitness value to solve the problem.

The inspiration for this came from the theory of evolution; the fittest solutions survive and procreate.

Example 1

Suppose you were looking for the most efficient way to cut a number of shapes out of a piece of wood. You want to waste as little wood as possible.

Your attempted solutions would be random arrangements of these shapes on your piece of wood. Fitness would be determined by how little wood would be left after cutting the shapes following this arrangement.
The less wood is left, the better the attempted solution.

Example 2

Suppose you were trying to find a polynomial that passes through a number of points. Your attempted solutions would be random polynomials.
To determine the fitness of these polynomials, you determine how well they fit the given points. (In this particular case, you would probably use the least squares method to determine how well the polynomial fit the points). Over a number of trials, you would get polynomials that fit the points better, until you had a polynomial that fit the points closely enough.

Answer 3

There are a number of good answers here explaining what genetic algorithms are, and giving example applications. I'm adding some general purpose advice on what they are good for, but also cases where you should NOT use them.

If my tone seems harsh, it is because using GAs in any of the cases in the inappropriate section below will lead to your paper being instantly rejected from any top-tier journal.

First, your problem MUST be an optimization problem. You need to define a "fitness function" that you are trying to optimize and you need to have a way to measure it.

Good

• Crossover functions are easy to define and natural: When dealing with certain kinds of data, crossover/mutation functions might be easy to define. For example strings (eg. DNA or gene sequences) can be mutated easily by splicing two candidate strings to obtain a new one (this is why nature uses genetic algorithms!). Trees (like phylogenetic trees or parse trees) can be spliced too, by replacing a branch of one tree with a branch from another. Shapes (like airplane wings or boat shapes) can be mutated easily by drawing a grid on the shape and combining different grid sections from the parents to obtain a child. Usually this means your problem is composed of different parts and putting together parts from distinct solutions is a valid candidate solution.
• This means that if your problem is defined in a vector space where the coordinates don't have any special meaning, GAs are not a good choice. If it is hard to formulate your problem as a GA, it is not worth it.
• Black Box evaluation: If for a candidate, your fitness function is evaluated outside the computer, GAs are a good idea. For example, if you are testing a wing shape in an air tunnel, genetic algorithms will help you generate good candidate shapes to try.
• Exception: Simulations. If your fitness function is measuring how well a nozzle design performs and requires simulating the fluid dynamics for each nozzle shape, GAs may work well for you. They may also work if you are simulating a physical system through time and are interested in how well your design performs over the course of the operation eg. modelling locomotion patterns. However, methods that use partial differential equations as constraints are being developed in the literature, eg. PDE constrained optimization, so this may change in the future.

Inappropriate

• You can calculate a gradient for your function: If you have access to the gradient of your function, you can do gradient descent, which is in general much more efficient than GAs. Gradient descent may have issues with local minima (as will GAs) but many methods have been studied to mitigate this.
• You know the fitness function in closed form: Then, you can probably calculate the gradient. Many languages have libraries supporting automatic differentiation, so you don't even need to do it manually. If your function is not differentiable, then you can use subgradient descent.
• Your optimization problem is of a known form, like a linear program or a quadratic program: GAs (and black box optimization methods in general) are very inefficient in terms of the number of candidates they need to evaluate, and are best avoided if possible.
• Your solution space is small: If you can grid your search space efficiently, you can guarantee that you have found the best solution, and can make contour plots of the solution space to see if there is a region you need to explore further.

Finally, if you are considering a GA, consider more recent work in Evolutionary Strategies. I am biased towards CMA-ES, which I think is a good simple algorithm that captures the notion of a gradient in the fitness landscape in a way that traditional GAs do not.

Answer 4

This answer requests a practical example of how one might be used, which I will attempt to provide in addition to the other answers. They seem to due a very good job of explaining what a genetic algorithm is. So, this will give an example.

Let's say you have a neural network (although they are not the only application of it), which, from some given inputs, will yield some outputs. A genetic algorithm can create a population of these, and by seeing which output is the best, breed and kill off members of the population. Eventually, this should optimise the neural network if it is complicated enough.

Here is a demonstration I've made, which despite being badly coded, might help you understand. http://khrabanas.github.io/projects/evo/evo.html Hit the evolve button and mess around with the goals.

It uses a simple genetic algorithm to breed, mutate, and decide which individuals of the population survive. Depending on how the input variables are set, the network will be able to get to some level of closeness to them. In this fashion, the population will likely eventually become a homogeneous group, whose outputs resemble the goals.

The genetic algorithm is trying to create a "neural network" of sorts, that by taking in RGB, will yield an output color. First, it generates a random population. It then by taking 3 random members from the population, selecting the one with the lowest fitness and removing it from the population. The fitness is equal to the difference in the top goal squared + the difference in the bottom goal squared. It then breeds the two remaining ones together and adds the child to the same place in the population as the dead member. When mating occurs, there is a chance a mutation will occur. This mutation will change one of the values randomly.

As a side note, due to how it is set up, it is impossible for it to be totally correct in many cases, though it will reach relative closeness.

Answer 5

As observed in another answer, all you need to apply Genetic Algorithms (GAs) is to represent a potential solution to your problem in a form that is subject to crossover and mutation. Ideally, the fitness function will provide some kind of smooth feedback about the quality of a solution, rather than simply being a 'Needle in a Haystack'.

Here are some characteristics of problems that Genetic Algorithms (and indeed Metaheuristics in general) are good for:

• NP-complete - The number of possible solutions to the problem is exponential, but checking the fitness of a solution is relatively cheap (technically, with time polynomial in the input size).
• Black box - GAs work reasonably well even if you don't have a particularly informed model of the problem to be solved. This means that these approaches are also useful as a 'rapid prototyping' approach to solving problems.

However, despite their widespread use for the purpose, note that GAs are actually not function optimizers - GA mechanisms tend not to explore 'outlying' regions of the search space in the hope of finding some distant high quality solution, but rather to cluster around more easily attainable peaks in the 'fitness landscape'.

More detail on the applicability of GAs is given in a famous early paper "What makes a problem hard for a Genetic Algorithm?"