﻿ Chapter 2 - What are Genetic Algorithms > Solving Optimization Problems

# Solving Optimization Problems

Navigation:  Chapter 2 - What are Genetic Algorithms >

# Solving Optimization Problems

GeneHunter solves optimization problems the same way.  It will create a population of possible solutions to the problem.  The individuals in this population will carry chromosomes which are the values of variables of the problem.  In our tin can example, the possible solutions of the problem are height/radius pairs.  We could rank each pair by how well it solves the problem, i.e., the less metal involved, the better the solution.  In Figure 2.2, we show a population of 20 individuals in the can population.  Beside each possible solution, we also show the amount of metal in the can with the dimensions specified in the chromosomes of the individuals.  Just as the ability of an animal to swim in a swamp is a measure of that animal's fitness to survive, the amount of metal in the can is a measure of the fitness of the dimensions of the cans.  The formula for the area of the can is called a "fitness function,” which we want to minimize.

 Height Radius Volume Area 7.08 1.5 50.04552 80.86457 6 1.63 50.08134 78.14333 3.8 2.04 49.68135 74.85534 5.6 1.69 50.24709 77.40945 7.2 1.49 50.21743 81.35529 4.82 1.82 50.15789 75.93102 3.6 2.1 49.87588 75.20971 6.5 1.56 49.69492 79.00224 4 2 50.26544 75.39820 6.75 1.54 50.29151 80.21489 4.93 1.79 49.62522 75.57916 5.63 1.68 49.92021 77.16252 5.35 1.72 49.72332 76.40603 4.15 1.96 50.08523 75.24489 5.63 1.68 49.92021 77.16252 2.9 2.35 50.31334 77.51878 7.1 1.5 50.18690 81.05307 3.43 2.16 50.27488 75.86567 6.1 1.62 50.29321 78.58001 4.25 1.94 50.25067 75.45224

Figure 2.2  Possible solutions for Tin Can example

GeneHunter actually solves the can problem by allowing the less fit individuals in the population to die (peacefully) and selectively breeding the most fit individuals (the ones that solve the problem best because the cans they describe have the least metal).  This process is called selection, as in selection of the fittest. GeneHunter will take two fit individuals and mate them (a process called crossover).  The offspring of the mated pair will receive some of the characteristics of the mother, and some of the father. (In reality there are no sexes in the population, and all reproduction is asexual in GeneHunter).

In nature, offspring often have some slight abnormalities, called mutations. Usually these mutations are disabling and inhibit the ability of the children to survive, but once in a while they improve the fitness of the individual (like toes stuck together in a web-like fashion).  GeneHunter similarly occasionally causes mutations in its populations.

After GeneHunter mates fit individuals and mutates some, the population undergoes a generation change. The population will then consist of offspring plus a few of the older individuals which GeneHunter allows to survive to the next generation because they are the most fit in the population, and we will want to keep them breeding.  These most fit individuals are called elite individuals.

After dozens or even hundreds of "generations", a population eventually emerges wherein the individuals will solve the problem very well.  In fact, the most fit (elite) individual will be an optimum or close to optimum solution.

The processes of selection, crossover, and mutation are called genetic operators. GeneHunter actually has a couple of other genetic operators that may be applied.  One is called diversity and it allows additional but very slight mutations of the population.  Another is called extinction, and it is similar to a plague destroying most of the population (all but the elite individuals) and refreshing it with a large set of new individuals.  Extinction is sometimes made to occur when so much inbreeding takes place that no offspring are more fit than their parents for many generations.  (Note: extinction is only available in the DLL form of GeneHunter, not in the Excel interface.)