Grammatical evolution engine

From Makers Local 256
Jump to: navigation, search

Born On:
27 July 2009
Last Updated:
28 July 2009


This is an attempt at grammatical evolution, subsuming the GED project. Grammatical evolution is similar to genetic programming, but it is able to generate code in any arbitrary language. The actual genome representation for a generated program or algorithm is merely a sequence of codons. Each codon represents a choice to make in a BNF for the language the final program is to be written and tested in.


These ideas are deltas to the original grammatical evolution research:

  • Generate only well-typed programs from the codons.
  • Use a stream of codons for each program rather than a bounded array. This would prevent the need to loop back to the beginning during program generation.
    • Simple lazy evaluation would be enough for this, although it may lead to a gradual space leak (population size * generations). This may be acceptable, but if it isn't then the alternative would be manual appending on demand, which I would like to avoid.
  • The idea of reproducing program-generating codons rather than programs is much closer to biology than genetic programming gets. Experiment with making this even closer to biology by trying alternative representations and recombination operations.
    • Stream of pairs of codons instead of single codons, with an idea of "dominance" (like dominant vs. recessive genes).
      • For example, maybe the larger valued codon is the more dominant.
      • The most dominant codon of the pair is the one used in generating the program.
      • Try combining a random choice from each pair from each parent instead of crossover operations. Among other things, this might allow interesting recessive traits to survive along with the most fit individuals in the population, giving more variety later in the simulation.