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.

Constraint programming

Constraint programming is an exiting modeling technique that states the relations between the variables in the form of constraints. There is a variety of constraints used in the constraint satisfaction problems , e.g. boolean "R" is true and "M" is false, inequalities like "Y"<=10, equations "X"=5 and etc. The variables can take real or integer values and etc.

To be ammended...