Crossover can be constructive when computing unique input-output sequences

Per Kristian LEHRE, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

34 Citations (Scopus)


Unique input-output (UIO) sequences have important applications in conformance testing of finite state machines (FSMs). Previous experimental and theoretical research has shown that evolutionary algorithms (EAs) can compute UIOs efficiently on many FSM instance classes, but fail on others. However, it has been unclear how and to what degree EA parameter settings influence the runtime on the UIO problem. This paper investigates the choice of acceptance criterion in the (1 + 1) EA and the use of crossover in the (μ + 1) Steady State Genetic Algorithm. It is rigorously proved that changing these parameters can reduce the runtime from exponential to polynomial for some instance classes of the UIO problem. © 2010 Springer-Verlag.
Original languageEnglish
Pages (from-to)1675-1687
Number of pages13
JournalSoft Computing
Issue number9
Early online date8 Jun 2010
Publication statusPublished - Sept 2011
Externally publishedYes

Bibliographical note

The authors would like to thank Pietro Oliveto for useful comments. This work was supported by EPSRC under grant no. EP/D052785/1.


  • Crossover operator
  • Evolutionary algorithms
  • Finite state machines
  • Runtime analysis
  • Unique input-output sequences


Dive into the research topics of 'Crossover can be constructive when computing unique input-output sequences'. Together they form a unique fingerprint.

Cite this