Inheritance (genetic algorithm)

Last updated

In genetic algorithms, inheritance is the ability of modeled objects to mate, mutate (similar to biological mutation), and propagate their problem solving genes to the next generation, in order to produce an evolved solution to a particular problem. The selection of objects that will be inherited from in each successive generation is determined by a fitness function, which varies depending upon the problem being addressed. [1]

Contents

The traits of these objects are passed on through chromosomes by a means similar to biological reproduction. These chromosomes are generally represented by a series of genes, which in turn are usually represented using binary numbers. This propagation of traits between generations is similar to the inheritance of traits between generations of biological organisms. This process can also be viewed as a form of reinforcement learning, because the evolution of the objects is driven by the passing of traits from successful objects which can be viewed as a reward for their success, thereby promoting beneficial traits. [1]

Process

Once a new generation is ready to be created, all of the individuals that have been successful and have been chosen for reproduction are randomly paired together. Then the traits of these individuals are passed on through a combination of crossover and mutation. [1] This process follows these basic steps:

  1. Pair off successful objects for mating.
  2. Determine randomly a crossover point for each pair.
  3. Switch the genes after the crossover point in each pair.
  4. Determine randomly if any genes are mutated in the child objects.

After following these steps, two child objects will be produced for every pair of parent objects used. Then, after determining the success of the objects in the new generation, this process can be repeated using whichever new objects were most successful. This will usually be repeated until either a desired generation is reached or an object that meets a minimum desired result from the fitness function is found.

While crossover and mutation are the common genetic operators used in inheritance, there are also other operators such as regrouping and colonization-extinction.[ citation needed ]

Example

Assume these two strings of bits represent the traits being passed on by two parent objects:

Now, consider that the crossover point is randomly positioned after the fifth bit:

During crossover, the two objects will swap all of the bits after the crossover point, leading to:

Finally, mutation is simulated on the objects by there being zero or more bits flipped randomly. Assuming the tenth bit for object 1 is mutated, and the second and seventh bits are mutated for object 2, the final children produced by this inheritance would be:

See also

Related Research Articles

Genetics Science of genes, heredity, and variation in living organisms

Genetics is a branch of biology concerned with the study of genes, genetic variation, and heredity in organisms.

In artificial intelligence, genetic programming (GP) is a technique of evolving programs, starting from a population of unfit programs, fit for a particular task by applying operations analogous to natural genetic processes to the population of programs.

Genetic disorder Health problem caused by one or more abnormalities in the genome

A genetic disorder or genetic brain injury (GBI), is a health problem caused by one or more abnormalities in the genome. It can be caused by a mutation in a single gene (monogenic) or multiple genes (polygenic) or by a chromosomal abnormality. Although polygenic disorders are the most common, the term is mostly used when discussing disorders with a single genetic cause, either in a gene or chromosome. The mutation responsible can occur spontaneously before embryonic development, or it can be inherited from two parents who are carriers of a faulty gene or from a parent with the disorder. When the genetic disorder is inherited from one or both parents, it is also classified as a hereditary disease. Some disorders are caused by a mutation on the X chromosome and have X-linked inheritance. Very few disorders are inherited on the Y chromosome or mitochondrial DNA.

Heredity Passing of traits to offspring from the speciess parents or ancestor

Heredity, also called inheritance or biological inheritance, is the passing on of traits from parents to their offspring; either through asexual reproduction or sexual reproduction, the offspring cells or organisms acquire the genetic information of their parents. Through heredity, variations between individuals can accumulate and cause species to evolve by natural selection. The study of heredity in biology is genetics.

Mendelian inheritance Type of biological inheritance

Mendelian inheritance is a type of biological inheritance that follows the principles originally proposed by Gregor Mendel in 1865 and 1866, re-discovered in 1900 by Hugo de Vries and Carl Correns, and popularized by William Bateson. These principles were initially controversial. When Mendel's theories were integrated with the Boveri–Sutton chromosome theory of inheritance by Thomas Hunt Morgan in 1915, they became the core of classical genetics. Ronald Fisher combined these ideas with the theory of natural selection in his 1930 book The Genetical Theory of Natural Selection, putting evolution onto a mathematical footing and forming the basis for population genetics within the modern evolutionary synthesis.

Genetic algorithm Competitive algorithm for searching a problem space

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 generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection. Some examples of GA applications include optimizing decision trees for better performance, solving sudoku puzzles, hyperparameter optimization, etc.

Dominance (genetics) One gene variant masking the effect of another in the other copy of the gene

In genetics, dominance is the phenomenon of one variant (allele) of a gene on a chromosome masking or overriding the effect of a different variant of the same gene on the other copy of the chromosome. The first variant is termed dominant and the second recessive. This state of having two different variants of the same gene on each chromosome is originally caused by a mutation in one of the genes, either new or inherited. The terms autosomal dominant or autosomal recessive are used to describe gene variants on non-sex chromosomes (autosomes) and their associated traits, while those on sex chromosomes (allosomes) are termed X-linked dominant, X-linked recessive or Y-linked; these have an inheritance and presentation pattern that depends on the sex of both the parent and the child. Since there is only one copy of the Y chromosome, Y-linked traits cannot be dominant or recessive. Additionally, there are other forms of dominance such as incomplete dominance, in which a gene variant has a partial effect compared to when it is present on both chromosomes, and co-dominance, in which different variants on each chromosome both show their associated traits.

In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

Genetic linkage is the tendency of DNA sequences that are close together on a chromosome to be inherited together during the meiosis phase of sexual reproduction. Two genetic markers that are physically near to each other are unlikely to be separated onto different chromatids during chromosomal crossover, and are therefore said to be more linked than markers that are far apart. In other words, the nearer two genes are on a chromosome, the lower the chance of recombination between them, and the more likely they are to be inherited together. Markers on different chromosomes are perfectly unlinked.

A genetic operator is an operator used in genetic algorithms to guide the algorithm towards a solution to a given problem. There are three main types of operators, which must work in conjunction with one another in order for the algorithm to be successful. Genetic operators are used to create and maintain genetic diversity, combine existing solutions into new solutions (crossover) and select between solutions (selection). In his book discussing the use of genetic programming for the optimization of complex problems, computer scientist John Koza has also identified an 'inversion' or 'permutation' operator; however, the effectiveness of this operator has never been conclusively demonstrated and this operator is rarely discussed.

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 solutions from an existing population, and is analogous to the crossover that happens during sexual reproduction in biology. Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions are typically mutated before being added to the population.

Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next. It is analogous to biological mutation.

In biology and genetic genealogy, the most recent common ancestor (MRCA), also known as the last common ancestor (LCA) or concestor, of a set of organisms is the most recent individual from which all the organisms of the set are descended. The term is also used in reference to the ancestry of groups of genes (haplotypes) rather than organisms.

In computer programming, gene expression programming (GEP) is an evolutionary algorithm that creates computer programs or models. These computer programs are complex tree structures that learn and adapt by changing their sizes, shapes, and composition, much like a living organism. And like living organisms, the computer programs of GEP are also encoded in simple linear chromosomes of fixed length. Thus, GEP is a genotype–phenotype system, benefiting from a simple genome to keep and transmit the genetic information and a complex phenotype to explore the environment and adapt to it.

Mating pool

A mating pool is a concept used in evolutionary computation, which refers to a family of algorithms used to solve optimization and search problems.

Conservation genetics

Conservation genetics is an interdisciplinary subfield of population genetics that aims to understand the dynamics of genes in populations principally to avoid extinction. Therefore, it applies genetic methods to the conservation and restoration of biodiversity. Researchers involved in conservation genetics come from a variety of fields including population genetics, molecular ecology, biology, evolutionary biology, and systematics. Genetic diversity is one of the three fundamental levels of biodiversity, so it is directly important in conservation. Genetic variability influences both the health and long-term survival of populations because decreased genetic diversity has been associated with reduced fitness, such as high juvenile mortality, diminished population growth, reduced immunity, and ultimately, higher extinction risk.

Human genetics Study of inheritance as it occurs in human beings

Human genetics is the study of inheritance as it occurs in human beings. Human genetics encompasses a variety of overlapping fields including: classical genetics, cytogenetics, molecular genetics, biochemical genetics, genomics, population genetics, developmental genetics, clinical genetics, and genetic counseling.

Genetics, a discipline of biology, is the science of heredity and variation in living organisms.

This glossary of genetics is a list of definitions of terms and concepts commonly used in the study of genetics and related disciplines in biology, including molecular biology and evolutionary biology. It is intended as introductory material for novices; for more specific and technical detail, see the article corresponding to each term. For related terms, see Glossary of evolutionary biology.

This glossary of evolutionary biology is a list of definitions of terms and concepts used in the study of evolutionary biology, population biology, speciation, and phylogenetics, as well as sub-disciplines and related fields. For additional terms from related glossaries, see Glossary of genetics, Glossary of ecology, and Glossary of biology.

References

  1. 1 2 3 Russell, Stuart J.; Norvig, Peter (1995). Artificial Intelligence: A Modern Approach . Englewood Heights, NJ: Prentice-Hall.