Test-based extended finite-state machines induction with evolutionary algorithms and ant colony optimization
Чивилихин Даниил Сергеевич, Vladimir I. Ulyantsev, Fedor Tsarev · 2012
In this paper we consider the problem of extended finite-state machines induction. The input data for this problem is a set of tests. Each test consists of two sequences - an input sequence and a corresponding output sequence. We present a new method of Extended Finite-State Machines (EFSM) induction based on an Ant Colony Optimization algorithm (ACO) and a new meaningful test-based crossover operator for EFSMs. New algorithms are compared with a genetic algorithm (GA) using a traditional crossover, a (1+1) evolutionary strategy and a random mutation hill climber. This comparison shows that the use of test-based crossover greatly improves performance of GA. GA on average also significantly outperforms the hill climber and evolutionary strategy. ACO outperforms GA, and the difference between average performance of ACO and GA hybridized with hill climber is insignificant.