CODEWITHSUNDEEP
artificial-intelligencegenetic-algorithmevolutionary-algorithm
Anish Chandran
Anish Chandran

Reputation: 141

What exactly is the purpose of using schemata in genetic algorithm?

How exactly is the schemata going to help genetic algorithm to get the optimal solution? Schema means template does that mean that every individual in the population will have the same schemata?

Upvotes: 2

Views: 1328

Answers (2)

Andreas
Andreas

Reputation: 6475

Schemata are unrelated to a genetic algorithm. They are simply speaking just there. Holland identified their presence and related that to the capabilities of the genetic algorithm which is why they're associated with GAs.

For any bit string of length 4 you can identify a number of schemata:

****, 0***, 1***, *0**, *1**, 00**, 10**, 01**, 11**, etc.

These schemata always exist. An individual is part of many such schemata at the same time. All individuals will be part of the 4* schema, but only those with a 0 in front will be part of the 0*** schema.

Now comes the relation to the genetic algorithm. What types of schemata are active is determined by all individuals in the whole population. What schemata are strong is determined by their presence in multiple individuals. If many individuals in the population have a "1" at their 4th position, then that's a strong schema if additionally they all have a 0 in beginning the strong schema looks like 0**1. The more individuals match a certain schema the stronger it is. The fitness of a schema is the average fitness of all individuals that match the schema. Holland now says that using fitness-proportional selection, single-point crossover, and bit-flip mutation above-average schema will become exponentially stronger over the evolutionary process. Why is it necessary that schemata become stronger? Because the higher the order of a schema the more likely it is that it gets disrupted in the search process. If however that schema is present in multiple individuals the probability is again reduced over all individuals.

Upvotes: 5

Black
Black

Reputation: 5080

long answer: http://en.wikipedia.org/wiki/Holland%27s_schema_theorem

short answer:

A schema is a "mask" applied to the population. You can count how many individuals match that mask. Therefore, the schema is a type of characteristic of a part of the solution.

If the fitness of a schema is better than the average, then more and more individuals will match that schema (if I understood Holland correctly).

Upvotes: 5

Related Questions