Model representation and cooperative coevolution for finite-state machine evolution

Grant Dick*, Xin Yao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages2700-2707
Number of pages8
ISBN (Print)9781479914883
DOIs
Publication statusPublished - 16 Sept 2014
Event2014 IEEE Congress on Evolutionary Computation, CEC 2014 - Beijing, China
Duration: 6 Jul 201411 Jul 2014

Conference

Conference2014 IEEE Congress on Evolutionary Computation, CEC 2014
Country/TerritoryChina
CityBeijing
Period6/07/1411/07/14

Keywords

  • cooperative coevolution
  • evolutionary search
  • Finite-state machines
  • representation

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Model representation and cooperative coevolution for finite-state machine evolution'. Together they form a unique fingerprint.

Cite this