Defining length
 | This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (August 2011) (Learn how and when to remove this template message) |
In the field of genetic algorithms, a schema (plural: schemata) is a template that represents a subset of potential solutions. These templates use fixed symbols (e.g., `0` or `1`) for specific positions and a wildcard or "don't care" symbol (often `#` or `*`) for others.
The defining length of a schema, denoted as L(H), measures the distance between the outermost fixed positions in the template. According to the Schema theorem, a schema with a shorter defining length is less likely to be disrupted by the genetic operator of crossover.[1][2] As a result, short schemata are considered more robust and are more likely to be propagated to the next generation.[3]
In genetic programming, where solutions are often represented as trees, the defining length is the number of links in the minimum tree fragment that includes all the non-wildcard symbols within a schema H.[4]
Example
The defining length is calculated by subtracting the position of the first fixed symbol from the position of the last one. Using 1-based indexing for a string of length 5:
- The schema `1##0#` has its first fixed symbol (`1`) at position 1 and its last fixed symbol (`0`) at position 4. Its defining length is 4 − 1 = 3.
- The schema `00##0` has its first fixed symbol at position 1 and its last at position 5. Its defining length is 5 − 1 = 4.
- The schema `##0##` has only one fixed symbol at position 3. The first and last fixed positions are the same, so its defining length is 3 − 3 = 0.
References
- ↑ Baeck, Thomas (2018-10-03) (in en). Evolutionary Computation 1: Basic Algorithms and Operators. CRC Press. ISBN 978-1-351-98942-8. https://books.google.com/books?id=PgJ-DwAAQBAJ.
- ↑ Poli, Riccardo; Langdon, William B. (1998-09-01). "Schema Theory for Genetic Programming with One-Point Crossover and Point Mutation". Evolutionary Computation 6 (3): 231–252. doi:10.1162/evco.1998.6.3.231. ISSN 1063-6560. https://doi.org/10.1162/evco.1998.6.3.231.
- ↑ "Foundations of Genetic Programming". UCL UK. http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP/. Retrieved 13 July 2010.
- ↑ Langdon, William B.; Poli, Riccardo (2013-03-09) (in en). Foundations of Genetic Programming. Springer Science & Business Media. ISBN 978-3-662-04726-2. https://books.google.com/books?id=zsaqCAAAQBAJ.
 |  |
