Model representation and cooperative coevolution for finite-state machine evolution

The use and search of finite-state machine (FSM) representations has a long history in evolutionary computation. The flexibility of Mealy-style and Moore-style FSMs is traded against the large number of parameters required to encode machines with many states and/or large output alphabets. Recent work using Mealy FSMs on the Tartarus problem has shown good performance of the resulting machines, but the evolutionary search is slower than for other representations. The aim of this paper is two-fold: first, a comparison between Mealy and Moore representations is considered on two problems, and then the impact of cooperative coevolution on FSM evolutionary search is examined. The results suggest that the search space of Moore-style FSMs may be easier to explore through evolutionary search than the search space of an equivalent-sized Mealy FSM representation. The results presented also suggest that the tested cooperative coevolutionary algorithms struggle to appropriately manage the non-separability present in FSMs, indicating that new approaches to cooperative coevolution may be needed to explore FSMs and similar graphical structures.