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 条

[21] Analysis of Population-based Evolutionary Algorithms for the Vertex Cover Problem
Oliveto, Pietro S.
He, Jun
Yao, Xin
[J]. 2008 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-8, 2008, : 1563 - 1570
[22] Real royal road functions for constant population size
Storch, T
Wegener, I
[J]. THEORETICAL COMPUTER SCIENCE, 2004, 320 (01) : 123 - 134
[23] Sudholt D, 2005, GECCO 2005: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOLS 1 AND 2, P1161

← 1 2 3 →