Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Schema theorem for non binary sets?

  1. Apr 10, 2016 #1
    Hey all, the schema theorem shows that in all probability a genetic algorithm will converge to a solution. much like the second law of thermodynamics for optimization. Although, it is taught with the genes being $$ \in (0,1, *), * \in (0,1) $$ is there a proof for non binary genes? example ASCII characters? and if you want to modify it yourself do you need t do proof the whole way through or just show that each element in your set of genes can be respresnted in binary? Any help appreciated.
  2. jcsd
  3. Apr 13, 2016 #2
    The theorem is not only based on binary strings, although the most common examples to explain it are shown using binary strings (and this also happens to GA's in general). But what the schema theorem really means is that those chromossomes (or strings) with higher fitness have the tendency to grow exponentially in number, thus they will eventually (in a short period of time) dominate the population untill a point where you will not be able to improve the solution with the current population. At this point, you have reached a local optimum, which can be the global optimum, but there is no guarantee of such thing for most problems.

    Quoting Wikipedia: "It says that short, low-order schemata with above-average fitness increase exponentially in successive generations".

    Also, note that a schema is a template that identifies a subset of strings with similarities at certain string positions, but it makes no "rule" on the type of string you are working with, be them binary, integer or real strings.
  4. Apr 15, 2016 #3
    Thanks :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted