Runtime analysis of the (1 + 1) EA on computing unique input output sequences

Per Kristian LEHRE, Xin YAO

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

22 Citations (SciVal)


Computing unique input output (UIO) sequences is a fundamental and hard problem in conformance testing of finite state machines (FSM). Previous experimental research has shown that evolutionary algorithms (EAs) can be applied successfully to find UIOs for some FSMs. However, before EAs can be recommended as a practical technique for computing UIOs, it is necessary to better understand the potential and limitations of these algorithms on this problem. In particular, more research is needed in determining for what instance classes of the problem EAs are feasible, and for what instance classes EAs are provably better than random search strategies. This paper presents rigorous theoretical and numerical analyses of the runtime of the (1 + 1) EA and random search on several selected instance classes of this problem. The theoretical analysis shows firstly, that there are instance classes where the EA is efficient, while random testing fails completely. Secondly, an instance class that is difficult for both random testing and the EA is presented. Finally, a parametrised instance class with tunable difficulty is presented. The numerical study estimates the constants in the asymptotic expressions obtained in the theoretical analysis, and the variability of the runtime. The numerical results fit well with the theoretical results, even for small problem instance sizes. Together, these results provide a first theoretical characterisation of the potential and limitations of the (1 + 1) EA on the problem of computing UIOs. © 2013 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)510-531
Number of pages22
JournalInformation Sciences
Early online date22 Feb 2010
Publication statusPublished - Feb 2014
Externally publishedYes

Bibliographical note

The authors would like to thank Mark Harman, Rob Hierons, Simon Poulding, Rami Bahsoon, Pietro Oliveto, Ramón Sagarna and Andrea Arcuri for their useful comments. This work was supported by EPSRC under Grant No. EP/D052785/1.


  • Conformance testing
  • Evolutionary algorithms
  • Finite state machines
  • Random search
  • Runtime analysis
  • Unique input output sequences


Dive into the research topics of 'Runtime analysis of the (1 + 1) EA on computing unique input output sequences'. Together they form a unique fingerprint.

Cite this