Runtime Analysis of Simple Interactive Evolutionary Biobjective Optimization Algorithms

Dimo Brockhoff¹, Manuel López-Ibáñez², Boris Naujoks³, and Günter Rudolph⁴

¹INRIA Lille - Nord Europe, DOLPHIN Team, 59650, Villeneuve d’Ascq, France

²IRIDIA, Université Libre de Bruxelles (ULB), Av. F. Roosevelt 50, CP 194/6, 1050, Brussels, Belgium

³Institute for Informatics, Cologne University of Applied Sciences, Steinmüllerallee 1, D-51643, Gummersbach, Germany

⁴Fakultät für Informatik, Technische Universität Dortmund, 44221, Dortmund, Germany

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.

LNCS 7491, p. 123 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012