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?
$\begingroup$
$\endgroup$
2
-
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 VenkatCommented Aug 25, 2010 at 14:32
-
1$\begingroup$ Why are the tags based on newsgroup names (instead of just plain english)? $\endgroup$– Chris SCommented Aug 26, 2010 at 11:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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
-
$\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$ Commented Aug 27, 2010 at 10:10
-
$\begingroup$ The course I'm doing takes a lot from the Mitchell book, almost rewriting a lot of it $\endgroup$– Chris SCommented Aug 27, 2010 at 21:31
$\begingroup$
$\endgroup$
2
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.
-
$\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 SCommented Aug 26, 2010 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$ Commented Aug 30, 2010 at 16:21