Crossover Can Be Constructive When Computing Unique Input Output Sequences

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

16 Citations (Scopus)

Abstract

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 (μ+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.
Original languageEnglish
Title of host publicationSimulated Evolution and Learning
Subtitle of host publication7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings
EditorsXiaodong Li, Michael Kirley, Mengjie Zhang, David Green, Vic Ciesielski, Hussein Abbass, Zbigniew Michalewicz, Tim Hendtlass, Kalyanmoy Deb, Kay Chen Tan, Jürgen Branke, Yuhui Shi
PublisherSpringer
Pages595-604
Number of pages10
Edition1
ISBN (Electronic)9783540896944
ISBN (Print)9783540896937
DOIs
Publication statusPublished - 19 Nov 2008
Event7th International Conference on Simulated Evolution and Learning - Melbourne, Australia
Duration: 7 Dec 200810 Dec 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5361
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on Simulated Evolution and Learning
Abbreviated titleSEAL 2008
Country/TerritoryAustralia
CityMelbourne
Period7/12/0810/12/08

Keywords

  • Input Sequence
  • Acceptance Criterion
  • Vertex Cover
  • Crossover Probability
  • Search Point

Fingerprint

Dive into the research topics of 'Crossover Can Be Constructive When Computing Unique Input Output Sequences'. Together they form a unique fingerprint.

Cite this