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

Per Kristian LEHRE, Yao XIN

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

20 Citations (Scopus)


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 on some instances. 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 instances of the problem EAs are feasible. This paper presents a rigorous runtime analysis of the (1+1) EA on three classes of instances of this problem. First, it is shown that there are instances 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. Together, these results provide a first theoretical characterisation of the potential and limitations of the (1+1) EA on the problem of computing UIOs. ©2007 IEEE.
Original languageEnglish
Title of host publication2007 IEEE Congress on Evolutionary Computation, CEC 2007
Number of pages8
Publication statusPublished - Sept 2007
Externally publishedYes


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

Cite this