Quantifying the effects of objective space dimension in evolutionary multiobjective optimization

Joshua Knowles, David Corne

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

    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 publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.
    PublisherSpringer Nature
    Pages757-771
    Number of pages14
    Volume4403
    ISBN (Print)9783540709275
    Publication statusPublished - 2007
    Event4th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2007 - Matsushima, Japan
    Duration: 5 Mar 20078 Mar 2007

    Conference

    Conference4th International Conference on Evolutionary Multi-Criterion Optimization, EMO 2007
    Country/TerritoryJapan
    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