Crossover can be constructive when computing unique input-output sequences

被引：27

作者：

Lehre, Per Kristian ^{[1
]}

Yao, Xin ^{[1
]}

机构：

[1] Univ Birmingham, Sch Comp Sci, Ctr Excellence Res Computat Intelligence & Applic, Birmingham B15 2TT, W Midlands, England

来源：

SOFT COMPUTING | 2011年 / 15卷 / 09期

基金：

英国工程与自然科学研究理事会;

关键词：

Finite state machines; Unique input-output sequences; Evolutionary algorithms; Runtime analysis; Crossover operator; EVOLUTIONARY ALGORITHMS;

D O I：

10.1007/s00500-010-0610-2

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Unique input-output (UIO) sequences have important applications in conformance testing of finite state machines (FSMs). Previous experimental and theoretical research has shown that evolutionary algorithms (EAs) can compute UIOs efficiently on many FSM instance classes, but fail on others. However, it has been unclear how and to what degree EA parameter settings influence the runtime on the UIO problem. This paper investigates the choice of acceptance criterion in the (1 + 1) EA and the use of crossover in the (mu + 1) Steady State Genetic Algorithm. It is rigorously proved that changing these parameters can reduce the runtime from exponential to polynomial for some instance classes of the UIO problem.

引用

页码：1675 / 1687

页数：13

共 23 条

[1] Clarke J., 2003, IEE Proceedings-Software, V150, P161, DOI 10.1049/ip-sen:20030559
[2] Cormen T., 2001, Introduction to Algorithms
[3] Derderian K, 2006, COMPUT J, V49, P331, DOI [10.1093/comjnl/bx1003, 10.1093/comjnl/bxl003]
[4] The analysis of a recombinative hill-climber on H-IFF
Dietzfelbinger, M
Naudts, B
Van Hoyweghen, C
Wegener, I
[J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2003, 7 (05) : 417 - 423
[5] Doerr B., 2009, GENETIC EVOLUTIONARY, P247
[6] Doerr B., 2008, GECCO, P539
[7] On the analysis of the (1+1) evolutionary algorithm
Droste, S
Jansen, T
Wegener, I
[J]. THEORETICAL COMPUTER SCIENCE, 2002, 276 (1-2) : 51 - 81
[8] The one-dimensional Ising model: Mutation versus recombination
Fischer, S
Wegener, I
[J]. THEORETICAL COMPUTER SCIENCE, 2005, 344 (2-3) : 208 - 225
[9] Friedrich T., 2008, P 10 ANN C GEN EV CO, P945, DOI DOI 10.1145/1389095.1389276
[10] Constructing multiple unique input/output sequences using metaheuristic optimisation techniques
Guo, Q
Hierons, RM
Harman, M
Derderian, K
[J]. IEE PROCEEDINGS-SOFTWARE, 2005, 152 (03): : 127 - 140

← 1 2 3 →