Defining length

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. As a result, short schemata are considered more robust and are more likely to be propagated to the next generation.

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.

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