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

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

17 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.
Original languageEnglish
Title of host publication IEEE Congress on Evolutionary Computation, 2007. CEC 2007.
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages8
ISBN (Electronic)978-1-4244-1340-9
ISBN (Print)978-1-4244-1339-3
Publication statusPublished - 1 Jan 2007
EventIEEE Congress on Evolutionary Computation, 2007 (CEC 2007) - Singapore, Singapore
Duration: 25 Sept 200728 Sept 2007


ConferenceIEEE Congress on Evolutionary Computation, 2007 (CEC 2007)


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

Cite this