Thursday 25 October 2018

using domain knowledge to evolve graphs

We are investigating using evolutionary algorithms to evolve graph structures directly, and are getting some rather nice results.

One thing that’s made a lot easier by using an explicit graph representation is encoding domain knowledge about “semantics preserving mutations”.  This allows domain specific neutral mutations to be added easily.  Since neutral mutations are supposed to help evolution, this should be good?  And yes, it is!

Our latest paper, just up on the arXiv, shows how including certain propositional logic tautologies, such as de Morgan’s laws, as neutral mutations, makes for imporved performance when evolving benchmark circuits.

Timothy Atkinson, Detlef Plump, Susan Stepney
Semantic Neutral Drift
arXiv:1810.10453 [cs.NE]

We introduce the concept of Semantic Neutral Drift (SND) for evolutionary algorithms, where we exploit equivalence laws to design semantics preserving mutations guaranteed to preserve individuals’ fitness scores. A number of digital circuit benchmark problems have been implemented with rule-based graph programs and empirically evaluated, demonstrating quantitative improvements in evolutionary performance. Analysis reveals that the benefits of the designed SND reside in more complex processes than simple growth of individuals, and that there are circumstances where it is beneficial to choose otherwise detrimental parameters for an evolutionary algorithm if that facilitates the inclusion of SND.



No comments:

Post a Comment