Quantifying the Effects of Objective Space Dimension in Evolutionary Multiobjective Optimization View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Joshua Knowles , David Corne

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 uncorrelated 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. More... »

PAGES

757-771

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-70928-2_57

DOI

http://dx.doi.org/10.1007/978-3-540-70928-2_57

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1014873269


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School\u00a0of\u00a0Computer Science, Kilburn Building, University of Manchester, Manchester M13 9PL, UK", 
          "id": "http://www.grid.ac/institutes/grid.5379.8", 
          "name": [
            "School\u00a0of\u00a0Computer Science, Kilburn Building, University of Manchester, Manchester M13 9PL, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Knowles", 
        "givenName": "Joshua", 
        "id": "sg:person.07713700217.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07713700217.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Mathematical and Computer Sciences (MACS), Heriot-Watt University, UK", 
          "id": "http://www.grid.ac/institutes/grid.9531.e", 
          "name": [
            "School of Mathematical and Computer Sciences (MACS), Heriot-Watt University, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Corne", 
        "givenName": "David", 
        "id": "sg:person.01266067540.80", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01266067540.80"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "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 uncorrelated 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.", 
    "editor": [
      {
        "familyName": "Obayashi", 
        "givenName": "Shigeru", 
        "type": "Person"
      }, 
      {
        "familyName": "Deb", 
        "givenName": "Kalyanmoy", 
        "type": "Person"
      }, 
      {
        "familyName": "Poloni", 
        "givenName": "Carlo", 
        "type": "Person"
      }, 
      {
        "familyName": "Hiroyasu", 
        "givenName": "Tomoyuki", 
        "type": "Person"
      }, 
      {
        "familyName": "Murata", 
        "givenName": "Tadahiko", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-70928-2_57", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-70927-5", 
        "978-3-540-70928-2"
      ], 
      "name": "Evolutionary Multi-Criterion Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "objective space dimension", 
      "EMO algorithms", 
      "number of objectives", 
      "random search", 
      "efficiency of search", 
      "evolutionary multiobjective optimization", 
      "algorithm developers", 
      "search space", 
      "algorithm", 
      "scalability", 
      "multiobjective optimization", 
      "true PF", 
      "objective value", 
      "discrete space", 
      "search", 
      "space dimensions", 
      "empirical results", 
      "correlation values", 
      "developers", 
      "large number", 
      "performance indicators", 
      "users", 
      "key aspects", 
      "iteration", 
      "space", 
      "issues", 
      "things", 
      "efficiency", 
      "benchmarking", 
      "significant concern", 
      "optimization", 
      "performance", 
      "random sampling", 
      "number", 
      "objective", 
      "dimensions", 
      "general analytical expression", 
      "analytical expressions", 
      "method", 
      "aspects", 
      "terms", 
      "function", 
      "analytical method", 
      "results", 
      "concern", 
      "sampling", 
      "different correlations", 
      "values", 
      "cases", 
      "indicators", 
      "range", 
      "EA", 
      "correlation", 
      "PF", 
      "observations", 
      "expression", 
      "effect", 
      "fraction", 
      "cardinality-based (scaling-independent) performance indicator", 
      "inter-objective correlation values"
    ], 
    "name": "Quantifying the Effects of Objective Space Dimension in Evolutionary Multiobjective Optimization", 
    "pagination": "757-771", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014873269"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-70928-2_57"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-70928-2_57", 
      "https://app.dimensions.ai/details/publication/pub.1014873269"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_213.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-70928-2_57"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70928-2_57'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70928-2_57'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70928-2_57'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70928-2_57'


 

This table displays all metadata directly associated to this object as RDF triples.

150 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-70928-2_57 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N31b755482939468ca9f9f905639b1c9e
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description 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 uncorrelated 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.
7 schema:editor Nf79b3013b8f744ada7d6e9d931665367
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb3c86dbfdae14f95a0cb3e843b766e3d
12 schema:keywords EA
13 EMO algorithms
14 PF
15 algorithm
16 algorithm developers
17 analytical expressions
18 analytical method
19 aspects
20 benchmarking
21 cardinality-based (scaling-independent) performance indicator
22 cases
23 concern
24 correlation
25 correlation values
26 developers
27 different correlations
28 dimensions
29 discrete space
30 effect
31 efficiency
32 efficiency of search
33 empirical results
34 evolutionary multiobjective optimization
35 expression
36 fraction
37 function
38 general analytical expression
39 indicators
40 inter-objective correlation values
41 issues
42 iteration
43 key aspects
44 large number
45 method
46 multiobjective optimization
47 number
48 number of objectives
49 objective
50 objective space dimension
51 objective value
52 observations
53 optimization
54 performance
55 performance indicators
56 random sampling
57 random search
58 range
59 results
60 sampling
61 scalability
62 search
63 search space
64 significant concern
65 space
66 space dimensions
67 terms
68 things
69 true PF
70 users
71 values
72 schema:name Quantifying the Effects of Objective Space Dimension in Evolutionary Multiobjective Optimization
73 schema:pagination 757-771
74 schema:productId N74f14eeac19f4c33ae17a3aafa2de1ec
75 N9bef5cff61644c1e95dd9026c8762922
76 schema:publisher Nf233768210c64ffc994e60a51a793de8
77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014873269
78 https://doi.org/10.1007/978-3-540-70928-2_57
79 schema:sdDatePublished 2021-12-01T20:00
80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
81 schema:sdPublisher N1496913cddfa44fa9823181393e187a1
82 schema:url https://doi.org/10.1007/978-3-540-70928-2_57
83 sgo:license sg:explorer/license/
84 sgo:sdDataset chapters
85 rdf:type schema:Chapter
86 N1496913cddfa44fa9823181393e187a1 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N2def4adcb7bc4e2b8c47f444019c2ecb rdf:first N3fc0a43514b546f094f9e58466e96d0c
89 rdf:rest N537327ce408a4e92a61dd0142de4a5ad
90 N31b755482939468ca9f9f905639b1c9e rdf:first sg:person.07713700217.53
91 rdf:rest N6c8dbb30ec544b7089e109848d2d89b0
92 N3fc0a43514b546f094f9e58466e96d0c schema:familyName Deb
93 schema:givenName Kalyanmoy
94 rdf:type schema:Person
95 N50cd28a50dcc44ff873e35c1a03b1cc0 schema:familyName Obayashi
96 schema:givenName Shigeru
97 rdf:type schema:Person
98 N537327ce408a4e92a61dd0142de4a5ad rdf:first N94271b41c1ce4eeb8af3aa42b455a381
99 rdf:rest Na41b2b3c3d5443229b25ec95da8af2e2
100 N6c8dbb30ec544b7089e109848d2d89b0 rdf:first sg:person.01266067540.80
101 rdf:rest rdf:nil
102 N74f14eeac19f4c33ae17a3aafa2de1ec schema:name dimensions_id
103 schema:value pub.1014873269
104 rdf:type schema:PropertyValue
105 N7c40e0dca1f947378cc37698807d7e52 schema:familyName Hiroyasu
106 schema:givenName Tomoyuki
107 rdf:type schema:Person
108 N94271b41c1ce4eeb8af3aa42b455a381 schema:familyName Poloni
109 schema:givenName Carlo
110 rdf:type schema:Person
111 N9bef5cff61644c1e95dd9026c8762922 schema:name doi
112 schema:value 10.1007/978-3-540-70928-2_57
113 rdf:type schema:PropertyValue
114 Na41b2b3c3d5443229b25ec95da8af2e2 rdf:first N7c40e0dca1f947378cc37698807d7e52
115 rdf:rest Na50c8542baa147519bb88bd2d62336a4
116 Na50c8542baa147519bb88bd2d62336a4 rdf:first Ncf95c07dafb34a9a8f3d805706740bc5
117 rdf:rest rdf:nil
118 Nb3c86dbfdae14f95a0cb3e843b766e3d schema:isbn 978-3-540-70927-5
119 978-3-540-70928-2
120 schema:name Evolutionary Multi-Criterion Optimization
121 rdf:type schema:Book
122 Ncf95c07dafb34a9a8f3d805706740bc5 schema:familyName Murata
123 schema:givenName Tadahiko
124 rdf:type schema:Person
125 Nf233768210c64ffc994e60a51a793de8 schema:name Springer Nature
126 rdf:type schema:Organisation
127 Nf79b3013b8f744ada7d6e9d931665367 rdf:first N50cd28a50dcc44ff873e35c1a03b1cc0
128 rdf:rest N2def4adcb7bc4e2b8c47f444019c2ecb
129 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
130 schema:name Information and Computing Sciences
131 rdf:type schema:DefinedTerm
132 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
133 schema:name Artificial Intelligence and Image Processing
134 rdf:type schema:DefinedTerm
135 sg:person.01266067540.80 schema:affiliation grid-institutes:grid.9531.e
136 schema:familyName Corne
137 schema:givenName David
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01266067540.80
139 rdf:type schema:Person
140 sg:person.07713700217.53 schema:affiliation grid-institutes:grid.5379.8
141 schema:familyName Knowles
142 schema:givenName Joshua
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07713700217.53
144 rdf:type schema:Person
145 grid-institutes:grid.5379.8 schema:alternateName School of Computer Science, Kilburn Building, University of Manchester, Manchester M13 9PL, UK
146 schema:name School of Computer Science, Kilburn Building, University of Manchester, Manchester M13 9PL, UK
147 rdf:type schema:Organization
148 grid-institutes:grid.9531.e schema:alternateName School of Mathematical and Computer Sciences (MACS), Heriot-Watt University, UK
149 schema:name School of Mathematical and Computer Sciences (MACS), Heriot-Watt University, UK
150 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...