Why doesn't it work?
There are a number of reasons why it's fiendishly difficult to use a genetic algorithm to
evolve any but the most trivial JavaScript functions (e.g. constant functions or the identity function).
Here are a few of them:
- The search spaces are HUGE. The number of possible JavaScript programs is exponential in the
maximum number of statements (/expressions) per program, hence why we included a bound on the number
of statements in each candidate program and given example grammars that only contain the kinds of
expressions needed by the example target programs.
-
The gaps between viable (e.g. syntactically valid) programs in the search space
are very large, and most mutations are
therefore detrimental to the viability of the program.
We could improve this by enriching the grammar used for the templates
(i.e. the basic building blocks) to only allow syntactically correct programs, but even syntactically
correct programs will frequently be semantically invalid (i.e. raising type errors and alike.)
Furthermore, this would seem
like an artificial constraint which would not reflect chemical evolution where the
proportion of functional proteins of the set of all possible proteins has been estimated to be
vanishingly small (i.e. 1 in 1077, see DD Axe 2004).
-
Finding a valid solution depends on using a carefully designed fitness test. Without this
the algorithm is blind and unable to converge to a solution. The specification of
the desired behaviour in the fitness test often contains most of the information that would
be required for a human to design the solution, such that we are really finding variations
on the design inherrent in the fitness test, rather than a solution ex nihilo (i.e. out of nothing).
So you could try improving your fitness test...
-
Computers are fast but to give it a fair chance you still probably want to run the
page for a few hours. Try setting the maximum number of generations to a few thousand
and then leaving it running.
In summary, although genetic algorithms can be very good at optimizing parameters for existing programs,
we've not yet found our genetic algorithm to be at all successful in generating/finding fit
solution programs out of nothing.
What are we doing wrong?
We'd be the first admit that we're no experts in genetic/evolutionary algorithms, so we've probably
missed a trick. So if you have more degrees than us, do
drop us a line, we'd love to hear from you!
Back...