In
genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
s, a chromosome (also sometimes called a genotype) is a set of parameters which define a proposed solution to the problem that the genetic algorithm is trying to solve. The set of all solutions is known as the ''population''.
The chromosome is often represented as a binary
string
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
, although a wide variety of other
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s are also used.
Chromosome design
The design of the chromosome and its parameters is by necessity specific to the problem to be solved. Traditionally, chromosomes are represented in binary as strings of 0s and 1s, however other encodings are also possible;
almost any representation which allows the solution to be represented as a finite-length string can be used.
Finding a suitable representation of the problem domain for a chromosome is an important consideration, as a good representation will make the search easier by limiting the search space; similarly, a poorer representation will allow a larger search space.
The
mutation
In biology, a mutation is an alteration in the nucleic acid sequence of the genome of an organism, virus, or extrachromosomal DNA. Viral genomes contain either DNA or RNA. Mutations result from errors during DNA or viral replication, mi ...
operator and
crossover
Crossover may refer to:
Entertainment
Albums and songs
* ''Cross Over'' (Dan Peek album)
* ''Crossover'' (Dirty Rotten Imbeciles album), 1987
* ''Crossover'' (Intrigue album)
* ''Crossover'' (Hitomi Shimatani album)
* ''Crossover'' (Yoshino ...
operator employed by the genetic algorithm must also take into account the chromosome's design.
Example 1: binary representation
Suppose the problem is to find the integer value of
between 0 and 255 that provides the maximal result for
. The possible solutions for this problem 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
.
Note that this is not 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.
Example 2: string representation
A more realistic problem we might wish to solve is the
travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
. 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
.
Selection, crossover, elitism and mutation
Fitness Function
Each generation in the genetic algorithm is the set of all current solutions. In each generation of the genetic algorithm, two parent chromosomes (encodings) are selected based on their fitness values which is determined by the
fitness function {{no footnotes, date=May 2015
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims. Fitness functions are used in genetic ...
; these chromosomes are used by the mutation and crossover operators to produce two offspring chromosomes for the new population.
Each encoding is an argument to the fitness function and outputs a score. In the real world you can imagine a fitness function being an organisms ability to survive and the score being the ease at which it does so. This determines how "good" a genetic encoding is with respect to the fitness function. Not all solutions pass the threshold and are therefore not considered for the next step.
Crossover
Two parent chromosomes are selected and using the single point
Crossover (genetic algorithm)
In genetic algorithms and evolutionary computation, crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring. It is one way to stochastically generate new soluti ...
they create two new solutions. One factor to consider is that because the selection and crossover functions are governed by randomness there is no way to ensure an improvement in solutions across evolutions.
Elitism
Elitism
Elitism is the belief or notion that individuals who form an elite—a select group of people perceived as having an intrinsic quality, high intellect, wealth, power, notability, special skills, or experience—are more likely to be constructi ...
remedies this however by selecting the nth top solutions in regard to the fitness function and copy them into the next generation. This ensures our best solutions are not lost while still utilizing the algorithm.
Mutation
The next step is the introduction of
mutation
In biology, a mutation is an alteration in the nucleic acid sequence of the genome of an organism, virus, or extrachromosomal DNA. Viral genomes contain either DNA or RNA. Mutations result from errors during DNA or viral replication, mi ...
. Mutation will change a random bit of the genome for example, To discover solutions that may otherwise be impossible by regular crossover of existing solutions. These new solutions are introduced to the algorithm and it runs on a loop until a satisfactory solution has been found. How genetic algorithms differ is by changing the functions(fitness function, crossover function, selection function, mutation function and function to generate new solutions) used in the algorithm. You may also change the genetic representation of a solution.
References
{{DEFAULTSORT:Chromosome (Genetic Algorithm)
Genetic algorithms
5. A. Lambora, K. Gupta and K. Chopra, "Genetic Algorithm- A Literature Review," 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon), 2019, pp. 380-384, doi: 10.1109/COMITCon.2019.8862255.v
6. Yang S. Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evol Comput. 2008 Fall;16(3):385-416. doi: 10.1162/evco.2008.16.3.385. PMID: 18811247.