To use all functions of this page, please activate cookies in your browser.
my.bionity.com
With an accout for my.bionity.com you can always see everything at a glance – and you can configure your own website and individual newsletter.
- My watch list
- My saved searches
- My saved topics
- My newsletter
Holland's schema theoremHolland's schema theorem is widely taken to be the foundation for explanations of the power of genetic algorithms. Additional recommended knowledgeA schema is a template that identifies a subset of strings with similarities at certain string positions. DescriptionFor example, consider binary strings of length 6. The schema 1**0*1 describes the set of all strings of length 6 with 1's at positions 1 and 6 and a 0 at position 4. The * is a "don't care" symbol, which means that positions 2, 3 and 5 can have a value of either 1 or 0. The order of a schema is defined as the number of fixed positions in the template, while the defining length δ(H) is the distance between the first and last specific positions. The order of 1**0*1 is 3 and its defining length is 5. The fitness of a schema is the average fitness of all strings matching the schema. The fitness of a string is a measure of the value of the encoded problem solution, as computed by a problem-specific evaluation function. With the genetic operators as defined above, the schema theorem states that short, low-order, schemata with above-average fitness increase exponentially in successive generations. Expressed as an equation: Here m(h,t) is the number of strings belonging to schema h at generation t, f(h) is the observed fitness of schema h and at is the observed average fitness at generation t. The probability of disruption p is the probability that crossover or mutation will destroy the schema h. It can be expressed as where o(H) is the number of fixed positions, l is the length of the code, pm is the probability of mutation and pc is the probability of crossover. So a schema with a shorter defining length δ(H) is less likely to be disrupted. References
|
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Holland's_schema_theorem". A list of authors is available in Wikipedia. |