Add support for grammatical evolution

[markcoletti]

We have a few work-related needs for grammatical evolution support.

[escott-mitre]

https://github.com/PonyGE/PonyGE2

[escott-mitre]

I like how PonyGE calls its high-level EA a "search_loop"

That's more intuitive than the way we call our generational_ea methods and the like "metaheuristics" or "monolithic algorithms." They are search loops.

[escott-mitre]

What we will want from PonyGE2 is in the grammar.py and possibly derivation.py modules.

PonyGE2 is well-organized and documented at the meso-level, but doesn't appear to have unit tests. So we'll start there.

[escott-mitre]

Cataloguing a few places in grammar.py that we'll need to refactor and/or think about to make compatible with LEAP:

Special "ramping" and "reverse-mapping" features:

Problem-specific parameters that Pony associates with a fitness function:

Dependence of ramping on population size:

[escott-mitre]

See the PonyGE2 tech report. The complication around ramping is probably part of the "Ramped Half-and-Half" initialization scheme they discuss.

Paper discussing initailization schemes in GE—may need to read it to understand what the code is doing: Fagan et al., 2016

[lukepmccombs]

Genomes are mapped to phenomes here mapper.py

[lukepmccombs]

Started trying to translate code on my end, beginning with constructing the Tree class and all its base functionality. I wasn't eager to use their classes (some functions I found clunky or they depend on their framework) and was looking to replace it with an existing library if possible. rustworkx won't work since you can't order a traversal without effectively rebuilding the tree elsewhere. I found treelib which looks well used and has a lot of the base functionality we'd need to implement and maintain (subtree replacement, tree expansion / traversal, etc.). Their documentation isn't the easiest to work with, though.

[escott-mitre]

@lukepmccombs — Any further thoughts/progress/plans on this?

We're dusting it off to try and continue. What we've got (and you'd already seen) is a light adaptation of the Grammar class in the 311-ge branch. I still had a couple questions about how it works but having perfect docs/test suite maybe isn't the most important.

Looks like what still needs done is

• Porting over the mapper functions, which you noted use a custom Tree implementation, and
• Porting over the derivation module (Or is this really needed?).