Implementation Details

<< Click to Display Table of Contents >>

Navigation:  Chapter 2 - What are Genetic Algorithms >

Implementation Details

Previous pageReturn to chapter overviewNext page

It was previously mentioned that populations are composed of individuals, and individuals are composed of chromosomes, which are equivalent to variables.  Chromosomes are composed of smaller units (hidden from the user) called genes.

 

There are several types of chromosomes, but the type we have been discussing so far are called continuous chromosomes.  A continuous chromosome in GeneHunter is composed of either 8, 16, or 32 genes, which are implemented in the computer as binary bits.  The two distinct values of a gene, 0 and 1, are called alleles. The three sizes of chromosomes are chromosome precisions.

 

 

_bm2

 

Figure 2.3  Continuous chromosomes.  Multiple chromosomes make up the individual.  Each partition is one chromosome, each binary bit is a gene, and the value of each bit (1, 0, 1, 1, 1, 0) is an allele.

 

The genes in a chromosome can take on a wide range of values between the minimum and maximum values of the associated variables.  If the variable is limited to between 1 and 3 inches, as our can radii were, then the chromosomes are made to take on values in these limits also.  There are only a finite number of values that the chromosomes can take on, however, and the number depends upon the precision.  If the precision is 8 bits, then there are 2 to the eighth power or 256 possible values for the chromosome, which will be evenly spread out between 1 and 3.  The exact values of the chromosome, for the mathematically inclined only, are 1.0, 1.0078125, 1.015625, 1.0234375, ... in increments of 2/256 ... 2.9921875, 3.0.  So you see that not all of the infinite number of values between 1 and 3 can be realized.  But if the precision is increased to 16 bits, the increments will be 2/65536, and with a precision of 32 bits the increments are quite small at 2/4294967296 =  0.0000000004656612873077.

There are other types of problems than those we have discussed so far, and they require another type of chromosomes and genes.  For example, many variables can take on integer values (like the number of widgets produced per month).  GeneHunter therefore provides a type of continuous chromosome called an integer chromosome.  It will only take integer values. If, in the tin can example, the height must be in integer values, then the height chromosome can only be 2, 3, 4, 5, 6, 7, or 8 inches.

 

Integer chromosomes use only 16-bit resolution and their values can range from -32,768 to 32,767.

 

There is another type of problem, usually called a combinatorial problem, of which the Traveling Salesman Problem (TSP) is the most famous example.  In the TSP, a salesman must visit some number of cities, say 8, and he only wants to visit each city once.  In these days of high gas prices, however, he wants the shortest route through all cities in order to minimize his gasoline costs.  There are two examples of the TSP implemented in GeneHunter described in later chapters.  For this type of problem we use a type of chromosome called "Enumerated".  This chromosome consists of genes which can have more allele values than just 0 and 1, and these values are visible to the GeneHunter user.  The values range from a minimum to a maximum value, and the order of their genes in the chromosome is important.  In the TSP example with 8 cities, there will be 8 genes, each with values ranging from 1 to 8.  The entire chromosome represents the path through the cities.  For example, suppose a particular chromosome in the population is 4,5,2,1,7,8,6,3.  This would represent the solution where the salesman went first to city 4, thence to city 5, etc.

 

_bm3

 

Figure 2.4  Enumerated chromosome.  In the TSP problem, each individual has only one chromosome, comprised of the entire list of cities.  Each partition (city) is a gene, and each value (4, 5, 2, 1, 7, 8, 6, 3) is an allele.

 

Note that our chromosomes for the TSP should not contain duplicate genes, i.e., genes with the same allele values, or else the salesman may travel to the same city more than once.  GeneHunter provides two different types of enumerated chromosomes:  "repeating genes" and "unique genes". For the TSP we will have to use unique genes, but some other problems may require repeating genes where we could get chromosomes like 2,3,2,4,5,2,3,8 or even 3,3,3,3,3,3,3,3.