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-11-01T18:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_156.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 N332a70cafde74284a9676121bc650635
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 Nccfee8bf24c046ad90aeae860b9baab1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3d19c81abb9e4ec4bd9046ff1d68631a
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 Nce428f3a67d74603b1bc53a1c1a2e169
75 Ndb0d12baf76943da9e19baa39ffdf4b2
76 schema:publisher N759190da94334ef282d336d384ce3d81
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-11-01T18:48
80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
81 schema:sdPublisher Nbd44a570fd6d4f48a1e48ce5d5e2b078
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 N1ca163092c4847cba8b73d1980317dd2 rdf:first sg:person.01266067540.80
87 rdf:rest rdf:nil
88 N210c9c7d73304bdd9bd03b9abca7370a rdf:first N51959956f4194fc4951b32a74a290bd7
89 rdf:rest rdf:nil
90 N29685db9580a4660aed08da37bef9c08 rdf:first Nd08cf274eea6485f99db4a309aacd0c3
91 rdf:rest N210c9c7d73304bdd9bd03b9abca7370a
92 N2ea8563143cf428693e1ea0414a409bc schema:familyName Poloni
93 schema:givenName Carlo
94 rdf:type schema:Person
95 N332a70cafde74284a9676121bc650635 rdf:first sg:person.07713700217.53
96 rdf:rest N1ca163092c4847cba8b73d1980317dd2
97 N3d19c81abb9e4ec4bd9046ff1d68631a schema:isbn 978-3-540-70927-5
98 978-3-540-70928-2
99 schema:name Evolutionary Multi-Criterion Optimization
100 rdf:type schema:Book
101 N3f37b6e4c10648e0a6919ff1ae7ddde0 schema:familyName Deb
102 schema:givenName Kalyanmoy
103 rdf:type schema:Person
104 N51959956f4194fc4951b32a74a290bd7 schema:familyName Murata
105 schema:givenName Tadahiko
106 rdf:type schema:Person
107 N759190da94334ef282d336d384ce3d81 schema:name Springer Nature
108 rdf:type schema:Organisation
109 N829191189b9344b581ecb647fe652c9f rdf:first N2ea8563143cf428693e1ea0414a409bc
110 rdf:rest N29685db9580a4660aed08da37bef9c08
111 N87b9f0b1da4a4d978adb95f38ab1ad08 schema:familyName Obayashi
112 schema:givenName Shigeru
113 rdf:type schema:Person
114 Nbd44a570fd6d4f48a1e48ce5d5e2b078 schema:name Springer Nature - SN SciGraph project
115 rdf:type schema:Organization
116 Nccfee8bf24c046ad90aeae860b9baab1 rdf:first N87b9f0b1da4a4d978adb95f38ab1ad08
117 rdf:rest Nd5f503b2c0014e25a133b5b9f651b78f
118 Nce428f3a67d74603b1bc53a1c1a2e169 schema:name doi
119 schema:value 10.1007/978-3-540-70928-2_57
120 rdf:type schema:PropertyValue
121 Nd08cf274eea6485f99db4a309aacd0c3 schema:familyName Hiroyasu
122 schema:givenName Tomoyuki
123 rdf:type schema:Person
124 Nd5f503b2c0014e25a133b5b9f651b78f rdf:first N3f37b6e4c10648e0a6919ff1ae7ddde0
125 rdf:rest N829191189b9344b581ecb647fe652c9f
126 Ndb0d12baf76943da9e19baa39ffdf4b2 schema:name dimensions_id
127 schema:value pub.1014873269
128 rdf:type schema:PropertyValue
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)


...