Adding Local Edge Mobility to Graph Evolution

Daniel Ashlock and Meghan Timmins
Submitted to CEC 2016

Abstract PDF eprint

This study extends an earlier generative representation for the evolution of graphs to include a local reconfiguration operator and a null operator. The local reconfiguration operator is shown to be more effective in evolving graphs with a particular geometric character (eccentricity sequence). The null operator permits evolution to select the number of active commands used, avoiding a problem with needing to tune a "gene length" parameter. The representation is parametrized by the probability of each command appearing in initial populations and during mutation. A parameter study leads to a number of rules of thumb for using the new representation and it is found that the number of failures to find a solution, in 3000 attempts, varies from 17 in 3000 as the parameters are changed. The representation is tested on 100 instances of the eccentricity sequence matching problem. Use of the null operator has the beneficial side effect of reducing observed variation in problem difficulty.