Heuristics: Genetic Algorithm 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Protz (Diskussion | Beiträge) |
Protz (Diskussion | Beiträge) |
||
Zeile 5: | Zeile 5: | ||
The solution that you get from a genetic algorithm is the result of the iteratively application of different stochastic operators. | The solution that you get from a genetic algorithm is the result of the iteratively application of different stochastic operators. | ||
+ | |||
+ | |||
+ | individual a strucuture, that represents a solution, consisting of genes | ||
+ | |||
+ | chromosome equal to individuals | ||
+ | |||
+ | gene a bit of the binary representation of a solution | ||
+ | |||
+ | population quantity of individuals, that became considered by an GA | ||
+ | |||
+ | parents two chosen individuals of a population | ||
+ | |||
+ | crossing combination of two genes from two chromosomes | ||
+ | |||
+ | mutation modification of a chromosome | ||
+ | |||
+ | fitness qualtity of a solution | ||
+ | |||
+ | generation one iteration in the duration of the optimation | ||
+ | |||
+ | genotype coded solution of a problem | ||
+ | |||
+ | phenotype decoded solution of a problem | ||
+ | |||
Zeile 20: | Zeile 44: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Example== | ==Example== | ||
Zeile 109: | Zeile 124: | ||
Improvement of 9 percent | Improvement of 9 percent | ||
+ | |||
+ | ==References== |
Version vom 25. Juni 2013, 08:57 Uhr
Inhaltsverzeichnis
Introduction
Genetic Algorithm are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might otherwise find in a lifetime (Salvatore Mangano, Computer Design, May 1995)
The solution that you get from a genetic algorithm is the result of the iteratively application of different stochastic operators.
individual a strucuture, that represents a solution, consisting of genes
chromosome equal to individuals
gene a bit of the binary representation of a solution
population quantity of individuals, that became considered by an GA
parents two chosen individuals of a population
crossing combination of two genes from two chromosomes
mutation modification of a chromosome
fitness qualtity of a solution
generation one iteration in the duration of the optimation
genotype coded solution of a problem
phenotype decoded solution of a problem
Basically the strucure of Genetic Algorithm is always the same presented below
- produce an initial population of indivuals
- evaluate the fitness of all individuals
- WHILE termination condition not met DO
- select fitter individuals for reproduction
- recombine between individuals
- mutate individuals
- evaluate the fitness of the modified individuals
- generate a new population
- END WHILE
Example
We toss a fair coin 60 times and get the following initial population:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \color{red}\sum_{i=1}^{6}f(s_i)=34
The new population after performing selection:
We only perform a crossover for the pairs and
Crossover-points: 2 and 5
Before crossover:
After crossover:
Before applying mutation:
After applying mutation with updated fitness-values:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=1}^{6}f(s_i''')=37
Improvement of 9 percent