Multi-Objective Equivalent Random Search

This paper introduces a new metric vector for assessing the performance of different multi-objective algorithms, relative to the range of performance expected from a random search. The metric requires an ensemble of repeated trials to be performed, reducing the chance of overly favourable results. The random search baseline for the function-under-test may be either analytic, or created from a Monte-Carlo process: thus the metric is repeatable and accurate.

The metric allows both the median and worst performance of different algorithms to be compared directly, and scales well with high-dimensional many-objective problems. The metric quantifies and is sensitive to the distance of the solutions to the Pareto set, the distribution of points across the set, and the repeatability of the trials. Both the Monte-Carlo and closed form analysis methods will provide accurate analytic confidence intervals on the observed results.

Authors and Affiliations

1. Department of Aerospace, Power and Sensors, Cranfield University, Shrivenham, Swindon, Wiltshire, SN6 8LA, England

   Evan J. Hughes

Editors and Affiliations

1. Science Institute, University of Iceland, P.O. Box, Iceland

   Thomas Philip Runarsson

2. Vorarlberg University of Applied Sciences, Hochschulstr. 1, A-6850, Dornbirn, Austria

   Hans-Georg Beyer

3. Automated Scheduling, Optimisation and Planning Group, School of Computer Science & IT, University of Nottingham, NG8 1BB, Nottingham, UK

   Edmund Burke

4. Depto. Arquitectura y Tecnologa de Computadores, ETS Ingeiera Informtica, C/Daniel Saucedo Aranda, s/n, 18071, Granada, Spain

   Juan J. Merelo-Guervós

5. Colorado State University, 80523, Fort Collins, CO, USA

   L. Darrell Whitley

6. University of Birmingham, Birmingham, UK

   Xin Yao

Reprints and permissions

© 2006 Springer-Verlag Berlin Heidelberg

Policies and ethics