Schema (genetic algorithms)

A schema is a template in computer science used in the field of genetic algorithms that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets; and so form a topological space. A schema is a template in computer science used in the field of genetic algorithms that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets; and so form a topological space. For example, consider binary strings of length 6. The schema 1**0*1 describes the set of all words of length 6 with 1's at the first and sixth positions and a 0 at the fourth position. The * is a wildcard 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 ) {displaystyle delta (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. The length of a schema H {displaystyle H} , called N ( H ) {displaystyle N(H)} , is defined as the total number of nodes in the schema. N ( H ) {displaystyle N(H)} is also equal to the number of nodes in the programs matching H {displaystyle H} . If the child of an individual that matches schema H does not itself match H, the schema is said to have been disrupted. In evolutionary computing such as genetic algorithms and genetic programming, propagation refers to the inheritance of characteristics of one generation by the next. For example, a schema is propagated if individuals in the current generation match it and so do those in the next generation. Those in the next generation may be (but don't have to be) children of parents who matched it. Recently schema have been studied using order theory.