Section: New Results

Runtime Analyses of Interactive Evolutionary Algorithms

Participant from DOLPHIN: Dimo Brockhoff; External Participants: Manuel López-Ibáñez (Université Libre de Bruxelles, Belgium), Boris Naujoks (Cologne University of Applied Sciences, Germany), and Gunter Rudolph (TU Dortmund University, Germany)

If a decision maker (DM) expresses preferences, e.g., towards certain points or regions of the search space, during the algorithm run, we call such an algorithm interactive. Interactive algorithms are frequently used in the field of multi-criteria decision making, but theoretical results on interactive evolutionary multiobjective algorithms (EMOAs) have not been derived until recently. In [36] , we started to analyze interactive versions of an evolutionary algorithm with plus-selection and a population size of one, the so-called $i$RLS and $i(1+1)$EA. On two pseudo-boolean problems, recently used for theoretically analyzing EMOAs, we could prove upper bounds on the expected runtime of the two mentioned algorithms and on the number of times, the DM is asked about his/her preferences until the most-preferred search point is found. The analyzes showed that the internal value function of the DM has a strong, non-desired influence on the algorithms' runtimes and that the number of questions to the DM are too high for a practical relevant algorithm. It is an open question which algorithm designs are necessary to circumvent these two drawbacks.