Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization

Thomas Jansen; Christine Zarges

doi:10.1007/978-3-319-99259-4_13

Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization

Thomas Jansen, Christine Zarges

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

2 Citations (Scopus)

Abstract

Lexicase selection is a parent selection mechanism originally introduced for genetic programming that has also been considered in the context of multi-objective optimization. This is the first theoretical runtime analysis of lexicase selection showing results for the bi-objective leading ones trailing zeroes benchmark problem. The lexicase selection operator is embedded into a simple hillclimbing algorithm and compared with different selection operators from the literature that are based on the classical dominance relationship. Strengths and weaknesses of the operators are demonstrated providing insights into their working principles. Results of experiments accompany the theoretical findings and point towards interesting questions for future research.

Original language	English
Title of host publication	Parallel Problem Solving from Nature – PPSN XV
Subtitle of host publication	15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II
Editors	Carlos M. Fonseca, Nuno Lourenco, Penousal Machado, Luis Paquete, Anne Auger, Darrell Whitley
Publisher	Springer Nature
Pages	153-164
Number of pages	12
ISBN (Electronic)	978-3-319-99259-4
ISBN (Print)	978-3-319-99258-7
DOIs	https://doi.org/10.1007/978-3-319-99259-4_13
Publication status	Published - 2018
Event	Parallel Problem Solving from Nature - University of Coimbra, Coimbra, Portugal Duration: 08 Sept 2018 → 12 Sept 2018 Conference number: XV http://ppsn2018.dei.uc.pt

Publication series

Name	Lecture Notes in Computer Science
Volume	11102 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Parallel Problem Solving from Nature
Abbreviated title	PPSN
Country/Territory	Portugal
City	Coimbra
Period	08 Sept 2018 → 12 Sept 2018
Internet address	http://ppsn2018.dei.uc.pt

Keywords

Multi-objective optimisation
Runtime analysis
Selection operators

Access to Document

10.1007/978-3-319-99259-4_13

Permanent link

Persistent link

Cite this

Jansen, T., & Zarges, C. (2018). Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization. In C. M. Fonseca, N. Lourenco, P. Machado, L. Paquete, A. Auger, & D. Whitley (Eds.), Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II (pp. 153-164). (Lecture Notes in Computer Science; Vol. 11102 LNCS). Springer Nature. https://doi.org/10.1007/978-3-319-99259-4_13

Jansen, Thomas ; Zarges, Christine. / Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization. Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II. editor / Carlos M. Fonseca ; Nuno Lourenco ; Penousal Machado ; Luis Paquete ; Anne Auger ; Darrell Whitley. Springer Nature, 2018. pp. 153-164 (Lecture Notes in Computer Science).

@inproceedings{054192c93c554b158428749f29c860d0,

title = "Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization",

abstract = "Lexicase selection is a parent selection mechanism originally introduced for genetic programming that has also been considered in the context of multi-objective optimization. This is the first theoretical runtime analysis of lexicase selection showing results for the bi-objective leading ones trailing zeroes benchmark problem. The lexicase selection operator is embedded into a simple hillclimbing algorithm and compared with different selection operators from the literature that are based on the classical dominance relationship. Strengths and weaknesses of the operators are demonstrated providing insights into their working principles. Results of experiments accompany the theoretical findings and point towards interesting questions for future research.",

keywords = "Multi-objective optimisation, Runtime analysis, Selection operators",

author = "Thomas Jansen and Christine Zarges",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; Parallel Problem Solving from Nature, PPSN ; Conference date: 08-09-2018 Through 12-09-2018",

year = "2018",

doi = "10.1007/978-3-319-99259-4_13",

language = "English",

isbn = "978-3-319-99258-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer Nature",

pages = "153--164",

editor = "Fonseca, {Carlos M.} and Nuno Lourenco and Penousal Machado and Luis Paquete and Anne Auger and Darrell Whitley",

booktitle = "Parallel Problem Solving from Nature – PPSN XV",

address = "Switzerland",

url = "http://ppsn2018.dei.uc.pt",

}

Jansen, T & Zarges, C 2018, Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization. in CM Fonseca, N Lourenco, P Machado, L Paquete, A Auger & D Whitley (eds), Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II. Lecture Notes in Computer Science, vol. 11102 LNCS, Springer Nature, pp. 153-164, Parallel Problem Solving from Nature, Coimbra, Portugal, 08 Sept 2018. https://doi.org/10.1007/978-3-319-99259-4_13

Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization. / Jansen, Thomas ; Zarges, Christine.
Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II. ed. / Carlos M. Fonseca; Nuno Lourenco; Penousal Machado; Luis Paquete; Anne Auger; Darrell Whitley. Springer Nature, 2018. p. 153-164 (Lecture Notes in Computer Science; Vol. 11102 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

TY - GEN

T1 - Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization

AU - Jansen, Thomas

AU - Zarges, Christine

N1 - Conference code: XV

PY - 2018

Y1 - 2018

N2 - Lexicase selection is a parent selection mechanism originally introduced for genetic programming that has also been considered in the context of multi-objective optimization. This is the first theoretical runtime analysis of lexicase selection showing results for the bi-objective leading ones trailing zeroes benchmark problem. The lexicase selection operator is embedded into a simple hillclimbing algorithm and compared with different selection operators from the literature that are based on the classical dominance relationship. Strengths and weaknesses of the operators are demonstrated providing insights into their working principles. Results of experiments accompany the theoretical findings and point towards interesting questions for future research.

AB - Lexicase selection is a parent selection mechanism originally introduced for genetic programming that has also been considered in the context of multi-objective optimization. This is the first theoretical runtime analysis of lexicase selection showing results for the bi-objective leading ones trailing zeroes benchmark problem. The lexicase selection operator is embedded into a simple hillclimbing algorithm and compared with different selection operators from the literature that are based on the classical dominance relationship. Strengths and weaknesses of the operators are demonstrated providing insights into their working principles. Results of experiments accompany the theoretical findings and point towards interesting questions for future research.

KW - Multi-objective optimisation

KW - Runtime analysis

KW - Selection operators

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

U2 - 10.1007/978-3-319-99259-4_13

DO - 10.1007/978-3-319-99259-4_13

M3 - Conference Proceeding (Non-Journal item)

SN - 978-3-319-99258-7

T3 - Lecture Notes in Computer Science

SP - 153

EP - 164

BT - Parallel Problem Solving from Nature – PPSN XV

A2 - Fonseca, Carlos M.

A2 - Lourenco, Nuno

A2 - Machado, Penousal

A2 - Paquete, Luis

A2 - Auger, Anne

A2 - Whitley, Darrell

PB - Springer Nature

T2 - Parallel Problem Solving from Nature

Y2 - 8 September 2018 through 12 September 2018

ER -

Jansen T , Zarges C. Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization. In Fonseca CM, Lourenco N, Machado P, Paquete L, Auger A, Whitley D, editors, Parallel Problem Solving from Nature – PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II. Springer Nature. 2018. p. 153-164. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-99259-4_13

Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization

Abstract

Publication series

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice - ImAppNIO

Cite this

Theoretical Analysis of Lexicase Selection in Multi-Objective Optimization

Abstract

Publication series

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Projects

Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice - ImAppNIO

Cite this