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

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

Colleges, School and Institutes

Abstract

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.

Details

Original languageEnglish
Title of host publication IEEE Congress on Evolutionary Computation, 2007. CEC 2007.
Publication statusPublished - 1 Jan 2007
EventIEEE Congress on Evolutionary Computation, 2007 (CEC 2007) - Singapore, Singapore
Duration: 25 Sep 200728 Sep 2007

Conference

ConferenceIEEE Congress on Evolutionary Computation, 2007 (CEC 2007)
CountrySingapore
CitySingapore
Period25/09/0728/09/07