4
$\begingroup$

I understand (some) of the workings behind schema theory in genetic algorithms, for example:

*****0 would match the genome 010100

But could anyone explain what schema theory (in Genetic Algorithms) is used for, and how it's used?

$\endgroup$
  • 1
    $\begingroup$ not sure this is within scope, but am unsure enough to not want to vote to close, or even downvote. See this discussion: meta.cstheory.stackexchange.com/questions/114/… $\endgroup$ – Suresh Venkat Aug 25 '10 at 14:32
  • 1
    $\begingroup$ Why are the tags based on newsgroup names (instead of just plain english)? $\endgroup$ – Chris S Aug 26 '10 at 11:06
4
$\begingroup$

If I remember correctly (it's years since I last studied this), schema theory isn't really used for anything. Rather, it's an attempt to explain why genetic algorithms seem to work well. As I'm not an expert, I can only point you to a book that I remember reading about schemata, Melanie Mitchell's book

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Holland's_schema_theorem "Holland's schema theorem is [...] the foundation for explanations of the power of genetic algorithms." $\endgroup$ – Radu GRIGore Aug 27 '10 at 10:10
  • $\begingroup$ The course I'm doing takes a lot from the Mitchell book, almost rewriting a lot of it $\endgroup$ – Chris S Aug 27 '10 at 21:31
2
$\begingroup$

When designing a genetic algorithm, you have to choose how to represent the problem in terms of schema, and the representation is vitally important to the performance of the algorithm. I think this is what schema theory is about.

Specifically, the common operations a GA will use to perturb or evolve are mutation and one- or two-point crossover. This means that the proximity of certain traits to other traits in the "chromosome" is significant, since crossover operations slice the chromosome, essentially keeping groups of contiguous traits together. If you've designed a schema in which key related traits are distant in the chromosome, optimal (or even good) solutions may not be found quickly (or at all), because those traits are unlikely to be retained as a collection.

It also means that even optimal groups that are quite large will tend not to be favored, because they will be frequently broken apart by mutation and crossover operations. This, again, relates to the schema.

My best understanding of this is that schema theory deals with these issues (and more). It is designed to address the design of a chromosome in which good and/or optimal solutions are likely to be found given the functions used to evolve the population.

$\endgroup$
  • $\begingroup$ So if I've understood, schema theory just helps you to design how you represent or encode the problem as artificial genes/bit strings, and design the fitness function? $\endgroup$ – Chris S Aug 26 '10 at 11:05
  • $\begingroup$ Yes, that's my understanding, which is limited. While it is easy conceptually, in my work I've found that managing the interaction between the fitness function and the schema is one of the more challenging design problems. $\endgroup$ – R. P. Dillon Aug 30 '10 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.