Crossover (recombination). In a genetic algorithm

24 slides
0.39 MB
277 views

Similar Presentations

Presentation Transcript

1

COMP305. Part II.Genetic Algorithms.

2

Topic 3.Genetic Algorithms Terminology.

3

Genetic Algorithms. Historical Introduction.1960s – John Holland of Michigan University invented the Genetic Algorithms (GAs) and later developed the algorithms with his students and colleagues. In contrast with “evolutionary strategies” and “evolutionary programming”, Holland was not interested in finding solutions to particular problems, but rather formally studied the phenomenon of adaptation as it occurs in nature and how the algorithm might be used in the computer systems. 1975 – Holland’s book “Adaptation in Natural and Artificial Systems” presented the Genetic Algorithm as an abstraction of natural evolution and gave a theoretical framework for adaptation under GAs.

4

GAs by John Holland. Holland introduced a “population” of binary strings which he called “chromosomes”. The “population” evolves using kind of “natural selection” together with the genetics-inspired operators of crossover, mutation, and inversion. Bits in a “chromosome” represent genes, and each “gene” is an instance of a particular “allele”, 0 or 1. The selection operator chooses those chromosomes in the population that will be allowed to reproduce, and on average the fitter chromosomes produce more offspring than the less fit ones. Crossover exchange subparts of two chromosomes Mutation randomly changes the allele values of some locations in the chromosome. Inversion reverses the order of a contiguous section of the chromosome rearranging the genes order.

5

Coding for Genetic Algorithms. In contrast with Nature, there is no universal code in GAs, every coding is problem dependent. The art of coding, though left beyond the scope, is very important in Genetic Algorithms, as from the very beginning the approach depends on whether or not the problem can be coded as a string of characters at all. The above implies serious restrictions on the class of problems capable of solving by GAs.

6

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”, e.g. “ABCDE1FGHI2JKL”, coding a candidate solution for the problem in consideration.

7

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”, e.g. “ABCDE1FGHI2JKL”, coding a candidate solution for the problem in consideration. Often the GA chromosome is defined as a fixed length binary string, e.g. “1001111100001101”

8

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”. Often it is a fixed length binary string, e.g. “1001111100001101” The same as nature blindly operates on real chromosomes and does not know or care what information is actually coded in the chromosomes, Holland had left behind the question of what particular information and in what way was coded in the strings of the Genetic Algorithms chromosomes.

9

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”. Often it is a fixed length binary string, e.g. “1001111100001101” Usually, Haploid organisms, i.e. the organisms with non-paired chromosomes are considered in the Genetic Algorithms.

10

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”. Often it is a fixed length binary string, e.g. “1001111100001101” Usually, GAs chromosome coincides with genotype, i.e. the genotype consists of a single chromosome. For simplicity, there is no phenotype concept in Genetic Algorithms either, and therefore GAs chromosome = GAs genotype = GAs organism

11

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”. Often it is a fixed length binary string, e.g. “1001111100001101” Following that in Genetic Algorithms GAs chromosome = GAs genotype = GAs organism, GAs Population is a population of GAs chromosomes, e.g. “1001001100001101”, “1001111100001101”, “1001100000001101”, “1001101100001101” , ….

12

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”. Often it is a fixed length binary string, e.g. “1001111100001101” Following that in Genetic Algorithms GAs chromosome = GAs genotype = GAs organism, GAs Population is a population of GAs chromosomes, e.g. “1001001100001101”, “1001111100001101”, “1001100000001101”, “1001101100001101” , ….It is also called population of candidate solutions.

13

GAs by John Holland. Chromosomes. Definition: GAs Chromosome is a string of “characters”. Often it is a fixed length binary string, e.g. “1001111100001101” In a GAs chromosome, a character represents a gene Possible settings for a gene are called alleles, e.g. in the example above the alleles are 0s and 1s, and if a gene codes a trait then an allele is the trait instance. For binary chromosomes, the alleles “alphabet” consists of just two characters, 0 and 1; There might be bigger “alphabets” to represent bigger number of alleles. Position of a gene in the string is called locus of the gene.

14

GAs by John Holland. Mutations. Mutation is change of allele of a gene at randomly chosen location. For binary chromosomes that means a flip of a bit at randomly chosen locus. “00000000000000000” “00000100000000000” For chromosomes with larger alphabet, mutation means replacement of a character at randomly chosen location with randomly chosen new character. “0123456789” “0123856789”

15

Crossover (recombination). In nature, crossover occurs when two parents exchange parts of their corresponding chromosomes: In a genetic algorithm, crossover recombines parts of two parent chromosomes to make two “children”: Parent1 “111111” Child1 “111100” Parent2 “000000” Child2 “000011” Or Parent1 “ABCDEF” Child1 “GHJDEF” Parent2 “GHJKLN” Child2 “ABCKLN”

16

Crossover (recombination). In a genetic algorithm, crossover recombines parts of two parent chromosomes to make two “children”: Parent1 “111111” Child1 “111100” Parent2 “000000” Child2 “000011” Or Parent1 “ABCDEF” Child1 “GHJDEF” Parent2 “GHJKLN” Child2 “ABCKLN” The crossover cutting point is chosen randomly. One-point crossover is considered most often.

17

Inversion and Translocation. Inversion is a mutation when part of a chromosome is cut out, rotates by 180o and then fitted back into the same position: “0123456789” “0123654789” Translocation is a mutation when part of a chromosome is cut out and moved to a different location in the chromosome “0123456789” “0123786549” Both Inversion and Translocation need two break points in a chromosome. Inversion and Translocation are rarely used in modern Genetic Algorithms.

18

Fitness Function. To evaluate a chromosome fitness, i.e. how good the candidate solution solves the problem, a Genetic Algorithm uses fitness function. The fitness function takes a chromosome as an input and produces its quantitative fitness evaluation as an output.

19

Fitness Function. The same as a particular code to be used for coding a problem possible solutions in a form of GAs chromosomes depends on the problem itself, a particular form of the fitness function also depends on the problem to be solved. Example: Maximize the real-valued function here the candidate solutions are values of y.

20

Evolving unit. The same as in nature, in GAs Population of chromosomes is the evolving unit. The GAs population evolves from one generation of chromosomes to the next generation and so on. first generation second generation third generation ... “1001001100001101” “1001001100001101” “1001101100101101” …. “1001001100001101” “1001001100001101” “1001101100001101” …. “1001001100001101” “1001001100001111” “1001101100001111” …. “1001001100001101” “1001001100001101” “1001101100001101” …. “1001001100001101” “1001001100001101” “1001101100001101” ….

21

Selection Operator. To simulate natural evolution of population of chromosomes, there must be a rule how to choose which chromosome is more likely to produce offspring for the next generation. We shall call that rule a selection operator. Usually a selection operator is defined in a way that better fitted chromosome is selected for reproduction more often and therefore will produce more offspring.

22

Search Space. As Genetic Algorithms are to search for the best possible solution to a problem, it was natural to introduce the concept of a Search Space for the algorithms. Definition: Set of all possible solutions to a problem in consideration is called a Genetic Algorithm search space. Thus, we search through the search space of possible solutions for the best solution to the problem.

23

Fitness Landscape. A fitness landscape is a representation of all possible solutions along with their fitness. The candidate solutions are represented by points in the coordinate plane, i.e. the search space, and corresponding fitness is measured along an additional dimension.

24

Fitness Landscape. A fitness landscape is a representation of all possible solutions along with their fitness. There will be “peaks”, “hills”, and “valleys” resembling features of physical landscapes. Evolution causes populations move towards the peaks of the fitness landscape.

Browse More Presentations

Last Updated: 8th March 2018

Recommended PPTs