Defining length: Difference between revisions
imported>Geysirhead removed Category:Genetic algorithms; added Category:Evolutionary algorithms using HotCat |
imported>OAbot m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| Line 1: | Line 1: | ||
{{Technical|date=August 2011}} | {{Technical|date=August 2011}} | ||
{{short description|Concept in genetic algorithm theory}} | |||
{{Use dmy dates|date=July 2023}} | {{Use dmy dates|date=July 2023}} | ||
In the field of [[genetic algorithms]], a '''[[Schema (genetic algorithms)|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 (genetic algorithm)|crossover]].<ref>{{Cite book |last=Baeck |first=Thomas |url=https://books.google.com/books?id=PgJ-DwAAQBAJ |title=Evolutionary Computation 1: Basic Algorithms and Operators |date=2018-10-03 |publisher=CRC Press |isbn=978-1-351-98942-8 |language=en}}</ref><ref>{{Cite journal |last=Poli |first=Riccardo |last2=Langdon |first2=William B. |date=1998-09-01 |title=Schema Theory for Genetic Programming with One-Point Crossover and Point Mutation |url=https://doi.org/10.1162/evco.1998.6.3.231 |journal=Evolutionary Computation |volume=6 |issue=3 |pages=231–252 |doi=10.1162/evco.1998.6.3.231 |issn=1063-6560|url-access=subscription }}</ref> As a result, short schemata are considered more robust and are more likely to be propagated to the next generation.<ref name="UCL12">{{cite web |title=Foundations of Genetic Programming |url=http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP/ |accessdate=13 July 2010 |publisher=UCL UK}}</ref> | |||
In [[genetic | 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.<ref>{{Cite book |last=Langdon |first=William B. |url=https://books.google.com/books?id=zsaqCAAAQBAJ |title=Foundations of Genetic Programming |last2=Poli |first2=Riccardo |date=2013-03-09 |publisher=Springer Science & Business Media |isbn=978-3-662-04726-2 |language=en}}</ref> | ||
== 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 == | == References == | ||
| Line 13: | Line 19: | ||
[[Category:Evolutionary algorithms]] | [[Category:Evolutionary algorithms]] | ||
[[Category:Genetic algorithms]] | |||
{{comp-sci-stub}} | {{comp-sci-stub}} | ||
Latest revision as of 02:31, 4 August 2025
Script error: No such module "Unsubst". Template:Short description Template:Use dmy dates
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
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".