Quantifying the effects of objective space dimension in evolutionary multiobjective optimization

Joshua Knowles, David Corne

Research output: Chapter in Book/Report/Conference proceedingConference contribution

99 Citations (Scopus)

Abstract

The scalability of EMO algorithms is an issue of significant concern for both algorithm developers and users. A key aspect of the issue is scalability to objective space dimension, other things being equal. Here, we make some observations about the efficiency of search in discrete spaces as a function of the number of objectives, considering both uncorrected and correlated objective values. Efficiency is expressed in terms of a cardinality-based (scaling-independent) performance indicator. Considering random sampling of the search space, we measure, empirically, the fraction of the true PF covered after p iterations, as the number of objectives grows, and for different correlations. A general analytical expression for the expected performance of random search is derived, and is shown to agree with the empirical results. We postulate that for even moderately large numbers of objectives, random search will be competitive with an EMO algorithm and show that this is the case empirically: on a function where each objective is relatively easy for an EA to optimize (an NK-landscape with K=2), random search compares favourably to a well-known EMO algorithm when objective space dimension is ten, for a range of inter-objective correlation values. The analytical methods presented here may be useful for benchmarking of other EMO algorithms. © Springer-Verlag Berlin Heidelberg 2007.

Original languageEnglish
Title of host publicationEvolutionary Multi-Criterion Optimization - 4th International Conference, EMO 2007, Proceedings
Pages757-771
Number of pages15
Volume4403 LNCS
Publication statusPublished - 2007
Event4th International Conference on Evolutionary Multi-Criterion Optimization - Matsushima, Japan
Duration: 5 Mar 20078 Mar 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4403 LNCS
ISSN (Print)0302-9743

Conference

Conference4th International Conference on Evolutionary Multi-Criterion Optimization
Abbreviated titleEMO 2007
CountryJapan
CityMatsushima
Period5/03/078/03/07

Keywords

  • Coverage indicator
  • Inter-objective correlation
  • Many objectives
  • Multiobjective optimization
  • Non-dominated ranking
  • Nondominated sorting
  • Random search

Fingerprint Dive into the research topics of 'Quantifying the effects of objective space dimension in evolutionary multiobjective optimization'. Together they form a unique fingerprint.

  • Cite this

    Knowles, J., & Corne, D. (2007). Quantifying the effects of objective space dimension in evolutionary multiobjective optimization. In Evolutionary Multi-Criterion Optimization - 4th International Conference, EMO 2007, Proceedings (Vol. 4403 LNCS, pp. 757-771). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4403 LNCS).