Projects per year
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 language | English |
---|---|
Title of host publication | Simulated Evolution and Learning |
Subtitle of host publication | 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings |
Editors | Xiaodong 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 |
Publisher | Springer |
Pages | 595-604 |
Number of pages | 10 |
Edition | 1 |
ISBN (Electronic) | 9783540896944 |
ISBN (Print) | 9783540896937 |
DOIs | |
Publication status | Published - 19 Nov 2008 |
Event | 7th International Conference on Simulated Evolution and Learning - Melbourne, Australia Duration: 7 Dec 2008 → 10 Dec 2008 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 5361 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 7th International Conference on Simulated Evolution and Learning |
---|---|
Abbreviated title | SEAL 2008 |
Country/Territory | Australia |
City | Melbourne |
Period | 7/12/08 → 10/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.Projects
- 2 Finished
-
SEBASE: Software Engineered By Automated SEarch
Yao, X. (Principal Investigator)
Engineering & Physical Science Research Council
29/06/06 → 28/12/11
Project: Research Councils
-
Computational Complexity Analysis of Evoloutionary Algarithms.
Yao, X. (Principal Investigator) & Rowe, J. (Co-Investigator)
Engineering & Physical Science Research Council
1/05/05 → 31/10/08
Project: Research Councils