Workshop Theory of Randomized Search Heuristics

(colocated with ICALP 2007)


Runtime Analysis of (1+1)-EA on Computing Unique Input Output Sequences

by Per Kristian Lehre, Xin Yao

Search based software engineering (SBSE) is an emerging field of research in which evolutionary algorithms and other randomised search heuristics are applied to solve problems in software engineering. Most previous research in this field has been experimental. To address the lack of rigorous theoretical research in SBSE, we propose to initiate such research on the problem of conformance testing of finite state machines.
Computing unique input output (UIO) sequences is a fundamental and hard problem in conformance testing. 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.
In this talk, we present runtime analysis of the (1+1) EA on various instance classes of this problem. It is shown that there are instances where the EA is highly efficient, while a random testing strategy fails completely. Secondly, an instance class that is difficult for both random testing and the EA is presented. Thirdly, an instance class with tunable difficulty is presented, showing how small changes in the FSM can make the problem harder. Finally, we present ongoing research on instances where choosing the right selection operator is necessary to efficiently solve the problem. Together, these results provide a first theoretical characterisation of the potential and limitations of the (1+1) EA on the problem of computing UIOs.

Back to mainpage