A notion of schemata in the genetic algorithm (GA)

We address the issue mentioned above in this short review.. To understand why GA works, we will have to introduce a notion of schemata. The attributes of genetic algorithm usually include a binary string representation of a chromosome and the notion of schemata.

The cromosome is a string of a given length consisting of boolean values , e.g. (10010) or (11011) and etc.

The schemata is a template that allows to explore similarities between the chromosomes. A "don't care" symbol (*) represents either 0 or 1 and is considered as a part of the schemata. For example, consider the schemata of length 5 : (1*010). It matches two chromosomes: (10010) and (11010). The schemata (*****) represents all chromosomes of length 5. Clearly every schemata matches to 2^n chromosomes, where n is the number of "don't care" (*) symbols.

The number of fixed positions (the non don't care symbols) are referred to as the order of the schemata (denoted by o(S)). For example, the following four scemata, each of length 5 have the following orders.

S_1=(**1*0); o(S_1)=2;
S_2=(10*01); o(S_2)=4;
S_3=(**1**); o(S_3)=1;
S_4=(11001); o(S_4)=0;

The distance between the first and the last fixed string positions are referred to as the defining length of the schemata (denoted by delta(S)) . For example,

delta(S_1)=5-3=2; delta(S_2)=5-1=4; delta(S_3)=3-3=0; delta(S_4)=5-1=4.