World Library  
Flag as Inappropriate
Email this Article

Chromosome (genetic algorithm)

Article Id: WHEBN0000555480
Reproduction Date:

Title: Chromosome (genetic algorithm)  
Author: World Heritage Encyclopedia
Language: English
Subject: Crossover (genetic algorithm), Mutation (genetic algorithm), Fitness function, Genetic operator, Genome (disambiguation)
Collection: Genetic Algorithms
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Chromosome (genetic algorithm)

In genetic algorithms, 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.[1] The chromosome is often represented as a binary string, although a wide variety of other data structures are also used.

Contents

  • Chromosome design 1
    • Example 1: binary representation 1.1
    • Example 2: string representation 1.2
  • Selection, crossover and mutation 2
  • References 3

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;[2] almost any representation which allows the solution to be represented as a finite-length string can be used.[3] 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.[4] The mutation operator and crossover 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 x between 0 and 255 that provides the maximal result for f(x) = x^2. 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. 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 and mutation

In each generation of the genetic algorithm, two parent chromosomes are selected based on their fitness values; these chromosomes are used by the mutation and crossover operators to produce two offspring chromosomes for the new population.[3]

References

  1. ^ "Introduction to genetic algorithms: IV. Genetic Algorithm". Retrieved 12 August 2015. 
  2. ^ Whitley, Darrell (June 1994). "A genetic algorithm tutorial". Statistics and Computing 4 (2).  
  3. ^ a b "What are Genetic Algorithms?". Retrieved 12 August 2015. 
  4. ^ "Genetic algorithms". Retrieved 12 August 2015. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.