Chromosome (evolutionary algorithm): Difference between revisions

Revision as of 09:33, 10 April 2006

Revision as of 02:08, 16 May 2006

Line 1:

:''forFor information onabout the chromosomechromosomes in biology, see [[Chromosome]].''

In [[genetic algorithm]]s, a '''chromosome''' (also sometimes called a '''genome''') is a set of parameters which define a proposed solution to the problem that the genetic algorithm is trying to solve. The chromosome is often represented as a simple [[string (computer science)|string]], although a wide variety of other [[data structure]]s are also in use as chromosomesused.

== Chromosome design ==

A genetic algorithm creates many chromosomes, either randomly or by design, as an initial population. These chromosomes are each evaluated by the [[fitness function]], which ranks them according to how good their solution is. The chromosomes which produced the best solutions, relatively speaking within the population, are allowed to breed, called [[crossover (genetic algorithm)|crossover]]. The best chromosomes' data is mixed, hopefully producing a better next generation.

The design of the chromosome and its parameters is by necessity specific to the problem to be solved. To give a trivial example, suppose the problem is to find the integer value of <math>x</math> between 0 and 255 that provides the maximal result for <math>f(x) = x^2</math>. (This isn't the type of problem that is normally solved by a genetic algorithm, since it can be trivially solved using numeric methods. It is only used to serve as a simple example.) Our possible solutions are the integers from 0 to 255, which can all be represented as 8-digit binary strings. Thus, we might use an 8-digit binary string as our chromosome. If a given chromosome in the population represents the value 155, its chromosome would be <code>10011011</code>.

A more realistic problem we might wish to solve is the [[travelling salesman problem]]. In this problem, we seek an ordered list of cities that results in the shortest trip for the salesman to travel. Suppose there are six cities, which we'll call A, B, C, D, E, and F. A good design for our chromosome might be the ordered list we want to try. An example chromosome we might encounter in the population might be <code>DFABEC</code>.

2006

The [[mutation (genetic algorithm)|mutation]] operator and [[crossover (genetic algorithm)|crossover]] operator employed by the genetic algorithm must take into account the chromosome's design.

[[Category:Genetic algorithms]]