Defining length

Last updated

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:

References

  1. Baeck, Thomas (3 October 2018). Evolutionary Computation 1: Basic Algorithms and Operators. CRC Press. ISBN   978-1-351-98942-8.
  2. Poli, Riccardo; Langdon, William B. (1 September 1998). "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.
  3. "Foundations of Genetic Programming". UCL UK. Retrieved 13 July 2010.
  4. Langdon, William B.; Poli, Riccardo (9 March 2013). Foundations of Genetic Programming. Springer Science & Business Media. ISBN   978-3-662-04726-2.