Crossover can be constructive when computing unique input output sequences

Per Kristian LEHRE; Xin YAO

doi:10.1007/978-3-540-89694-4_60

Crossover can be constructive when computing unique input output sequences

Per Kristian LEHRE, Xin YAO

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

18 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. © 2008 Springer Berlin Heidelberg.

Original language	English
Title of host publication	Simulated Evolution and Learning : 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 Berlin Heidelberg
Pages	595-604
Number of pages	10
ISBN (Electronic)	9783540896944
ISBN (Print)	9783540896937
DOIs	https://doi.org/10.1007/978-3-540-89694-4_60
Publication status	Published - 2008
Externally published	Yes
Event	7th International Conference on Simulated Evolution and Learning, SEAL 2008 - Melbourne, Australia Duration: 7 Dec 2008 → 10 Dec 2008

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin, Heidelberg
Volume	5361
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Simulated Evolution and Learning, 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

Access to Document

10.1007/978-3-540-89694-4_60

Cite this

LEHRE, P. K., & YAO, X. (2008). Crossover can be constructive when computing unique input output sequences. In X. LI, M. KIRLEY, M. ZHANG, D. GREEN, V. CIESIELSKI, H. ABBASS, Z. MICHALEWICZ, T. HENDTLASS, K. DEB, K. C. TAN, J. BRANKE, & Y. SHI (Eds.), Simulated Evolution and Learning : 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings (pp. 595-604). (Lecture Notes in Computer Science; Vol. 5361). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-89694-4_60

LEHRE, Per Kristian ; YAO, Xin. / Crossover can be constructive when computing unique input output sequences. Simulated Evolution and Learning : 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings. editor / 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. Springer Berlin Heidelberg, 2008. pp. 595-604 (Lecture Notes in Computer Science).

@inproceedings{7088215983014097a7f2a18d974c2fb1,

title = "Crossover can be constructive when computing unique input output sequences",

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. {\textcopyright} 2008 Springer Berlin Heidelberg.",

keywords = "Input Sequence, Acceptance Criterion, Vertex Cover, Crossover Probability, Search Point",

author = "LEHRE, {Per Kristian} and Xin YAO",

year = "2008",

doi = "10.1007/978-3-540-89694-4_60",

language = "English",

isbn = "9783540896937",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "595--604",

editor = "Xiaodong LI and Michael KIRLEY and Mengjie ZHANG and David GREEN and Vic CIESIELSKI and Hussein ABBASS and Zbigniew MICHALEWICZ and Tim HENDTLASS and Kalyanmoy DEB and TAN, {Kay Chen} and J{\"u}rgen BRANKE and Yuhui SHI",

booktitle = "Simulated Evolution and Learning : 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings",

note = "7th International Conference on Simulated Evolution and Learning, SEAL 2008 ; Conference date: 07-12-2008 Through 10-12-2008",

}

LEHRE, PK & YAO, X 2008, Crossover can be constructive when computing unique input output sequences. in X LI, M KIRLEY, M ZHANG, D GREEN, V CIESIELSKI, H ABBASS, Z MICHALEWICZ, T HENDTLASS, K DEB, KC TAN, J BRANKE & Y SHI (eds), Simulated Evolution and Learning : 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings. Lecture Notes in Computer Science, vol. 5361, Springer Berlin Heidelberg, pp. 595-604, 7th International Conference on Simulated Evolution and Learning, SEAL 2008, Melbourne, Australia, 7/12/08. https://doi.org/10.1007/978-3-540-89694-4_60

Crossover can be constructive when computing unique input output sequences. / LEHRE, Per Kristian; YAO, Xin.
Simulated Evolution and Learning : 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings. ed. / 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. Springer Berlin Heidelberg, 2008. p. 595-604 (Lecture Notes in Computer Science; Vol. 5361).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - Crossover can be constructive when computing unique input output sequences

AU - LEHRE, Per Kristian

AU - YAO, Xin

PY - 2008

Y1 - 2008

N2 - 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. © 2008 Springer Berlin Heidelberg.

AB - 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. © 2008 Springer Berlin Heidelberg.

KW - Input Sequence

KW - Acceptance Criterion

KW - Vertex Cover

KW - Crossover Probability

KW - Search Point

UR - http://www.scopus.com/inward/record.url?scp=58349089548&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-89694-4_60

DO - 10.1007/978-3-540-89694-4_60

M3 - Conference paper (refereed)

SN - 9783540896937

T3 - Lecture Notes in Computer Science

SP - 595

EP - 604

BT - Simulated Evolution and Learning : 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings

A2 - LI, Xiaodong

A2 - KIRLEY, Michael

A2 - ZHANG, Mengjie

A2 - GREEN, David

A2 - CIESIELSKI, Vic

A2 - ABBASS, Hussein

A2 - MICHALEWICZ, Zbigniew

A2 - HENDTLASS, Tim

A2 - DEB, Kalyanmoy

A2 - TAN, Kay Chen

A2 - BRANKE, Jürgen

A2 - SHI, Yuhui

PB - Springer Berlin Heidelberg

T2 - 7th International Conference on Simulated Evolution and Learning, SEAL 2008

Y2 - 7 December 2008 through 10 December 2008

ER -

LEHRE PK, YAO X. Crossover can be constructive when computing unique input output sequences. In LI X, KIRLEY M, ZHANG M, GREEN D, CIESIELSKI V, ABBASS H, MICHALEWICZ Z, HENDTLASS T, DEB K, TAN KC, BRANKE J, SHI Y, editors, Simulated Evolution and Learning : 7th International Conference, SEAL 2008, Melbourne, Australia, December 7-10, 2008, Proceedings. Springer Berlin Heidelberg. 2008. p. 595-604. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-89694-4_60

Crossover can be constructive when computing unique input output sequences

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this