Chromosome (genetic algorithm)
Encyclopedia
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
, although a wide variety of other data structure
s are also used.
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
between 0 and 255 that provides the maximal result for 
. (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
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
The mutation
operator
and crossover
operator employed by the genetic algorithm must take into account the chromosome's design.
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
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
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
, although a wide variety of other data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s are also used.
Chromosome design
The article would also benefit from more relevant and clearer examples.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
between 0 and 255 that provides the maximal result for . (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 10011011.A more realistic problem we might wish to solve is the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
. 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
DFABEC.The mutation
Mutation (genetic algorithm)
In genetic algorithms of computing, mutation is a genetic operator used to maintain genetic diversity from one generation of a population of algorithm chromosomes to the next...
operator
Genetic operator
A genetic operator is an operator used in genetic algorithms to maintain genetic diversity, known as Mutation and to combine existing solutions into others, Crossover...
and crossover
Crossover (genetic algorithm)
In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based...
operator employed by the genetic algorithm must take into account the chromosome's design.