What are good examples of genetic algorithms/genetic programming solutions?

Question

I'd like to know about specific problems you have solved using GA/GP and what libraries/frameworks you used if you didn't roll your own.

Questions:

• What problems have you used GA/GP to solve?

• What libraries/frameworks did you use?

I'm looking for first-hand experiences, so please do not answer unless you have that.

Answer 1

Genetic algorithms are used to generate high-quality solutions for optimization and search problems.

• It stimulates the natural selection(survival of the fittest), which means the species who can adapt to the changes in the environment are able to survive and reproduce and go to the next generation.

• Each generation has many individuals and each individual represents a point in search space and it’s possible solutions. Each individual is represented as a string of character/integer/float/bits.

GAs are not good for all kinds of problems. They’re best for problems where there is a clear way to evaluate fitness. If your search space is not well constrained or your evaluation process is computationally expensive, GAs may not find solutions in a sane amount of time.

The process of using genetic algorithms goes like this:

• Determine the problem and goal

• Break down the solution to bite-sized properties (genomes)

• Build a population by randomizing said properties

• Evaluate each unit in the population

• Selectively breed (pick genomes from each parent)

• Rinse and repeat

Some steps for performing GA/GP are:

1. Fitness – Giving a score to each solution, that represents how good it is

2. Selection – Selecting pairs of parent solutions according to their Fitness value

3. Crossover – Breeding the selected parents to produce an offspring

4. Mutation – Mutating the offspring solution with a very low probability                  

When choosing to use genetic algorithms, the first thing we need to understand is how to represent an individual solution in our population. In order to understand how to do that, we’ll use the Traveling Salesman Problem (TSP):

A solution to the problem can be represented as an ordered list of cities when each one describes the desired route. And it’s important to point out that every city should be listed exactly once.

In this example, our solution population consists of a collection of lists of cities. To form our first generation, we will randomly generate a collection of solutions, and we need to make sure that each generated solution is valid (and is a possible solution to the problem). We call these solutions chromosomes.

The next step will be taking these chromosomes into a process of evolution, and use the power of natural selection to obtain a better population.

In order to achieve this, we first need to evaluate each chromosome and give better ones higher probabilities to produce children. This is done by a function called the Fitness Function that receives a chromosome and returns a score that represents how good the chromosome is in terms of the problem. Going back to our example, the function could be the sum of the distances in the route.

At this point, we take the scores, and each chromosome will get a relative probability to be selected as a parent for the next generation. And as we mentioned earlier, better chromosomes will get higher probabilities. Or in other words, this is where we use natural selection and now it’s time to move to the process of evolution.