Runtime analysis of simple interactive evolutionary biobjective optimization algorithms

Dimo Brockhoff; Manuel López-Ibáñez; Boris Naujoks; Günter Rudolph

doi:10.1007/978-3-642-32937-1_13

Runtime analysis of simple interactive evolutionary biobjective optimization algorithms

Dimo Brockhoff
, Manuel López-Ibáñez
, Boris Naujoks
, Günter Rudolph

IRIDIA
Université Libre de Bruxelles
Institute for Informatics
Cologne University of Applied Sciences
Fakultät für Informatik
University of Dortmund

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

Development and deployment of interactive evolutionary multiobjective optimization algorithms (EMOAs) have recently gained broad interest. In this study, first steps towards a theory of interactive EMOAs are made by deriving bounds on the expected number of function evaluations and queries to a decision maker. We analyze randomized local search and the (1+1)-EA on the biobjective problems LOTZ and COCZ under the scenario that the decision maker interacts with these algorithms by providing a subjective preference whenever solutions are incomparable. It is assumed that this decision is based on the decision maker's internal utility function. We show that the performance of the interactive EMOAs may dramatically worsen if the utility function is non-linear instead of linear.

Original language	English
Title of host publication	Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings
Pages	123-132
Number of pages	10
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-32937-1_13
Publication status	Published - 24 Sept 2012
Event	12th International Conference on Parallel Problem Solving from Nature, PPSN 2012 - Taormina, Italy Duration: 1 Sept 2012 → 5 Sept 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7491 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Parallel Problem Solving from Nature, PPSN 2012
Country/Territory	Italy
City	Taormina
Period	1/09/12 → 5/09/12

Access to Document

10.1007/978-3-642-32937-1_13

Cite this

Brockhoff, D., López-Ibáñez, M., Naujoks, B., & Rudolph, G. (2012). Runtime analysis of simple interactive evolutionary biobjective optimization algorithms. In Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings (PART 1 ed., pp. 123-132). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7491 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-32937-1_13

Brockhoff, Dimo ; López-Ibáñez, Manuel ; Naujoks, Boris et al. / Runtime analysis of simple interactive evolutionary biobjective optimization algorithms. Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1. ed. 2012. pp. 123-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{e14587a122db40a6886d6293e01c90c6,

title = "Runtime analysis of simple interactive evolutionary biobjective optimization algorithms",

abstract = "Development and deployment of interactive evolutionary multiobjective optimization algorithms (EMOAs) have recently gained broad interest. In this study, first steps towards a theory of interactive EMOAs are made by deriving bounds on the expected number of function evaluations and queries to a decision maker. We analyze randomized local search and the (1+1)-EA on the biobjective problems LOTZ and COCZ under the scenario that the decision maker interacts with these algorithms by providing a subjective preference whenever solutions are incomparable. It is assumed that this decision is based on the decision maker's internal utility function. We show that the performance of the interactive EMOAs may dramatically worsen if the utility function is non-linear instead of linear.",

author = "Dimo Brockhoff and Manuel L{\'o}pez-Ib{\'a}{\~n}ez and Boris Naujoks and G{\"u}nter Rudolph",

year = "2012",

month = sep,

day = "24",

doi = "10.1007/978-3-642-32937-1\_13",

language = "English",

isbn = "9783642329364",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "123--132",

booktitle = "Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings",

edition = "PART 1",

note = "12th International Conference on Parallel Problem Solving from Nature, PPSN 2012 ; Conference date: 01-09-2012 Through 05-09-2012",

}

Brockhoff, D, López-Ibáñez, M, Naujoks, B & Rudolph, G 2012, Runtime analysis of simple interactive evolutionary biobjective optimization algorithms. in Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7491 LNCS, pp. 123-132, 12th International Conference on Parallel Problem Solving from Nature, PPSN 2012, Taormina, Italy, 1/09/12. https://doi.org/10.1007/978-3-642-32937-1_13

Runtime analysis of simple interactive evolutionary biobjective optimization algorithms. / Brockhoff, Dimo; López-Ibáñez, Manuel; Naujoks, Boris et al.
Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1. ed. 2012. p. 123-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7491 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Runtime analysis of simple interactive evolutionary biobjective optimization algorithms

AU - Brockhoff, Dimo

AU - López-Ibáñez, Manuel

AU - Naujoks, Boris

AU - Rudolph, Günter

PY - 2012/9/24

Y1 - 2012/9/24

N2 - Development and deployment of interactive evolutionary multiobjective optimization algorithms (EMOAs) have recently gained broad interest. In this study, first steps towards a theory of interactive EMOAs are made by deriving bounds on the expected number of function evaluations and queries to a decision maker. We analyze randomized local search and the (1+1)-EA on the biobjective problems LOTZ and COCZ under the scenario that the decision maker interacts with these algorithms by providing a subjective preference whenever solutions are incomparable. It is assumed that this decision is based on the decision maker's internal utility function. We show that the performance of the interactive EMOAs may dramatically worsen if the utility function is non-linear instead of linear.

AB - Development and deployment of interactive evolutionary multiobjective optimization algorithms (EMOAs) have recently gained broad interest. In this study, first steps towards a theory of interactive EMOAs are made by deriving bounds on the expected number of function evaluations and queries to a decision maker. We analyze randomized local search and the (1+1)-EA on the biobjective problems LOTZ and COCZ under the scenario that the decision maker interacts with these algorithms by providing a subjective preference whenever solutions are incomparable. It is assumed that this decision is based on the decision maker's internal utility function. We show that the performance of the interactive EMOAs may dramatically worsen if the utility function is non-linear instead of linear.

U2 - 10.1007/978-3-642-32937-1_13

DO - 10.1007/978-3-642-32937-1_13

M3 - Conference contribution

AN - SCOPUS:84866368599

SN - 9783642329364

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 123

EP - 132

BT - Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings

T2 - 12th International Conference on Parallel Problem Solving from Nature, PPSN 2012

Y2 - 1 September 2012 through 5 September 2012

ER -

Brockhoff D, López-Ibáñez M, Naujoks B, Rudolph G. Runtime analysis of simple interactive evolutionary biobjective optimization algorithms. In Parallel Problem Solving from Nature, PPSN XII - 12th International Conference, Proceedings. PART 1 ed. 2012. p. 123-132. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-32937-1_13

Runtime analysis of simple interactive evolutionary biobjective optimization algorithms

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this