Solving Optimization Problems

<< Click to Display Table of Contents >>

Navigation:  Chapter 2 - What are Genetic Algorithms >

Solving Optimization Problems

Previous pageReturn to chapter overviewNext page

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.)