Statistical Methods for Convergence Detection of Multi-Objective Evolutionary Algorithms

Trautmann, H.1, a; Wagner, T.2, b; Naujoks, B.3, c; Preuss, M.4, d; Mehnen, J.5, e

1)
Lehrstuhl Computergestützte Statistik, Technische Universität Dortmund, 44227 Dortmund
2)
Institut für Spanende Fertigung, Technische Universität Dortmund, Baroper Str. 301, 44227 Dortmund
3)
Log!n GmbH, Schwelm
4)
Fakultät für Informatik, Lehrstuhl für Algorithm Engineering (LS 11), Technische Universität Dortmund, 44227 Dortmund
5)
Decision Engineering Centre, University Cranfield, Cranfield, United Kingdom

a) trautmann@statistik.tu-dortmund.de; b) wagner@isf.de; c) Boris.Naujoks@login-online.de; d) mike.preuss@tu-dortmund.de; e) j.mehnen@cranfield.ac.uk

Kurzfassung

In this paper, two approaches for estimating the generation in which a multi-objective evolutionary algorithm (MOEA) shows statistically significant signs of convergence are introduced. A set-based perspective is taken where convergence is measured by performance indicators. The proposed techniques fulfill the requirements of proper statistical assessment on the one hand and efficient optimisation for real-world problems on the other hand. The first approach accounts for the stochastic nature of theMOEAby repeating the optimisation runs for increasing generation numbers and analysing the performance indicators using statistical tools. This technique results in a very robust offline procedure. Moreover, an online convergence detection method is introduced as well. This method automatically stops the MOEA when either the variance of the performance indicators falls below a specified threshold or a stagnation of their overall trend is detected. Both methods are analysed and compared for two MOEA and on different classes of benchmark functions. It is shown that the methods successfully operate on all stated problems needing less function evaluations while preserving good approximation quality at the same time.

Schlüsselwörter

Convergence detection, termination criterion, evolutionary algorithms, multi-objective optimisation, performance indicators, performance assessment

Veröffentlichung

Evolutionary Computation, 17 (2009) 4, S. 493-509, doi: 10.1162/evco.2009.17.4.17403