A Simple Proof for the Usefulness of Crossover in Black-Box Optimization View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-21

AUTHORS

Eduardo Carvalho Pinto , Carola Doerr

ABSTRACT

The idea to recombine two or more search points into a new solution is one of the main design principles of evolutionary computation (EC). Its usefulness in the combinatorial optimization context, however, is subject to a highly controversial discussion between EC practitioners and the broader Computer Science research community. While the former, naturally, report significant speedups procured by crossover, the belief that sexual reproduction cannot advance the search for high-quality solutions seems common, for example, amongst theoretical computer scientists. Examples that help understand the role of crossover in combinatorial optimization are needed to promote an intensified discussion on this subject. We contribute with this work an example of a crossover-based genetic algorithm (GA) that provably outperforms any mutation-based black-box heuristic on a classic benchmark problem. The appeal of our examples lies in its simplicity: the proof of the result uses standard mathematical techniques and can be taught in a basic algorithms lecture. Our theoretical result is complemented by an empirical evaluation, which demonstrates that the superiority of the GA holds already for quite small problem instances. More... »

PAGES

29-41

Book

TITLE

Parallel Problem Solving from Nature – PPSN XV

ISBN

978-3-319-99258-7
978-3-319-99259-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-99259-4_3

DOI

http://dx.doi.org/10.1007/978-3-319-99259-4_3

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "DreamQuark, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pinto", 
        "givenName": "Eduardo Carvalho", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "French National Centre for Scientific Research", 
          "id": "https://www.grid.ac/institutes/grid.4444.0", 
          "name": [
            "Sorbonne Universit\u00e9, CNRS, LIP6, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Doerr", 
        "givenName": "Carola", 
        "id": "sg:person.010360414373.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/2330163.2330260", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004118286"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1162/evco_a_00171", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007746230"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2014.11.028", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008296423"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1162/evco_a_00148", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013902553"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2908812.2908950", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017940419"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0963548312000600", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020245943"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2010.10.035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021244275"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1967654.1967656", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023650622"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-015-0019-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032720526", 
          "https://doi.org/10.1007/s00453-015-0019-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-002-0940-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038676592", 
          "https://doi.org/10.1007/s00453-002-0940-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9616-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045973415", 
          "https://doi.org/10.1007/s00453-012-9616-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tevc.2012.2202241", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061605104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-017-0354-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091088346", 
          "https://doi.org/10.1007/s00453-017-0354-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-017-0354-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091088346", 
          "https://doi.org/10.1007/s00453-017-0354-9"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-08-21", 
    "datePublishedReg": "2018-08-21", 
    "description": "The idea to recombine two or more search points into a new solution is one of the main design principles of evolutionary computation (EC). Its usefulness in the combinatorial optimization context, however, is subject to a highly controversial discussion between EC practitioners and the broader Computer Science research community. While the former, naturally, report significant speedups procured by crossover, the belief that sexual reproduction cannot advance the search for high-quality solutions seems common, for example, amongst theoretical computer scientists. Examples that help understand the role of crossover in combinatorial optimization are needed to promote an intensified discussion on this subject. We contribute with this work an example of a crossover-based genetic algorithm (GA) that provably outperforms any mutation-based black-box heuristic on a classic benchmark problem. The appeal of our examples lies in its simplicity: the proof of the result uses standard mathematical techniques and can be taught in a basic algorithms lecture. Our theoretical result is complemented by an empirical evaluation, which demonstrates that the superiority of the GA holds already for quite small problem instances.", 
    "editor": [
      {
        "familyName": "Auger", 
        "givenName": "Anne", 
        "type": "Person"
      }, 
      {
        "familyName": "Fonseca", 
        "givenName": "Carlos M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Louren\u00e7o", 
        "givenName": "Nuno", 
        "type": "Person"
      }, 
      {
        "familyName": "Machado", 
        "givenName": "Penousal", 
        "type": "Person"
      }, 
      {
        "familyName": "Paquete", 
        "givenName": "Lu\u00eds", 
        "type": "Person"
      }, 
      {
        "familyName": "Whitley", 
        "givenName": "Darrell", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-99259-4_3", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-99258-7", 
        "978-3-319-99259-4"
      ], 
      "name": "Parallel Problem Solving from Nature \u2013 PPSN XV", 
      "type": "Book"
    }, 
    "name": "A Simple Proof for the Usefulness of Crossover in Black-Box Optimization", 
    "pagination": "29-41", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-99259-4_3"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6cbc602e28b0803fa55fd6885f340503506afd2f404c6de2062dd8a6f06758c3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106254457"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-99259-4_3", 
      "https://app.dimensions.ai/details/publication/pub.1106254457"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:01", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000325_0000000325/records_100801_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-319-99259-4_3"
  }
]
 

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-319-99259-4_3'

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-319-99259-4_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99259-4_3'

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-319-99259-4_3'


 

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

141 TRIPLES      23 PREDICATES      39 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-99259-4_3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N00e8ca7ace3b4aee8bd4e5b2179e3ac4
4 schema:citation sg:pub.10.1007/s00453-002-0940-2
5 sg:pub.10.1007/s00453-012-9616-8
6 sg:pub.10.1007/s00453-015-0019-5
7 sg:pub.10.1007/s00453-017-0354-9
8 https://doi.org/10.1016/j.tcs.2010.10.035
9 https://doi.org/10.1016/j.tcs.2014.11.028
10 https://doi.org/10.1017/s0963548312000600
11 https://doi.org/10.1109/tevc.2012.2202241
12 https://doi.org/10.1145/1967654.1967656
13 https://doi.org/10.1145/2330163.2330260
14 https://doi.org/10.1145/2908812.2908950
15 https://doi.org/10.1162/evco_a_00148
16 https://doi.org/10.1162/evco_a_00171
17 schema:datePublished 2018-08-21
18 schema:datePublishedReg 2018-08-21
19 schema:description The idea to recombine two or more search points into a new solution is one of the main design principles of evolutionary computation (EC). Its usefulness in the combinatorial optimization context, however, is subject to a highly controversial discussion between EC practitioners and the broader Computer Science research community. While the former, naturally, report significant speedups procured by crossover, the belief that sexual reproduction cannot advance the search for high-quality solutions seems common, for example, amongst theoretical computer scientists. Examples that help understand the role of crossover in combinatorial optimization are needed to promote an intensified discussion on this subject. We contribute with this work an example of a crossover-based genetic algorithm (GA) that provably outperforms any mutation-based black-box heuristic on a classic benchmark problem. The appeal of our examples lies in its simplicity: the proof of the result uses standard mathematical techniques and can be taught in a basic algorithms lecture. Our theoretical result is complemented by an empirical evaluation, which demonstrates that the superiority of the GA holds already for quite small problem instances.
20 schema:editor N6ae1a45368e74667a4db94c1325bf296
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree false
24 schema:isPartOf N7670ca531bbd461a8b9e4a59a1602572
25 schema:name A Simple Proof for the Usefulness of Crossover in Black-Box Optimization
26 schema:pagination 29-41
27 schema:productId N8019c168461242e4b72ebc23bdb7d3a2
28 N815bf5184ab94a77be2194bbcf0c4e5f
29 Ncf8c3efd28cb4e29b18b15b74e7be829
30 schema:publisher Nc7a09e1a951b443489fff7d529af4626
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106254457
32 https://doi.org/10.1007/978-3-319-99259-4_3
33 schema:sdDatePublished 2019-04-16T05:01
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nf29c8b08ee2f49c0b911e4f494fd3213
36 schema:url https://link.springer.com/10.1007%2F978-3-319-99259-4_3
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N00e8ca7ace3b4aee8bd4e5b2179e3ac4 rdf:first N6d3e4970aef84f2a932e401777a0cf10
41 rdf:rest Ncb6de8625d7b4fd58584d7e4b24a1c67
42 N1d4af04753544fb0bd73338cb49b35d9 rdf:first N780fb9ad024a4294bf2e2638e861d644
43 rdf:rest Na370db02d8cf4c55ba14b9fdeacd5501
44 N23b73b9a730e4597bc5c09e004da1a09 rdf:first N9e91e47128f747ff94b60ffe89cd13b7
45 rdf:rest rdf:nil
46 N47033d7c1a05451daca92673e73f3d9e schema:familyName Lourenço
47 schema:givenName Nuno
48 rdf:type schema:Person
49 N51f5bf15617e4533a8d7a9ad74bef304 rdf:first N9f5ac50472244d489ee49dfae4577be3
50 rdf:rest Nbc34e70d63cd4f858dc1fd1840aaeb1c
51 N6ae1a45368e74667a4db94c1325bf296 rdf:first N72432e16c63f46dd8b1e1334f45120a8
52 rdf:rest N1d4af04753544fb0bd73338cb49b35d9
53 N6d3e4970aef84f2a932e401777a0cf10 schema:affiliation N7705f1ebcff04020991570d44b2c83d4
54 schema:familyName Pinto
55 schema:givenName Eduardo Carvalho
56 rdf:type schema:Person
57 N72432e16c63f46dd8b1e1334f45120a8 schema:familyName Auger
58 schema:givenName Anne
59 rdf:type schema:Person
60 N7670ca531bbd461a8b9e4a59a1602572 schema:isbn 978-3-319-99258-7
61 978-3-319-99259-4
62 schema:name Parallel Problem Solving from Nature – PPSN XV
63 rdf:type schema:Book
64 N7705f1ebcff04020991570d44b2c83d4 schema:name DreamQuark, Paris, France
65 rdf:type schema:Organization
66 N780fb9ad024a4294bf2e2638e861d644 schema:familyName Fonseca
67 schema:givenName Carlos M.
68 rdf:type schema:Person
69 N8019c168461242e4b72ebc23bdb7d3a2 schema:name doi
70 schema:value 10.1007/978-3-319-99259-4_3
71 rdf:type schema:PropertyValue
72 N815bf5184ab94a77be2194bbcf0c4e5f schema:name dimensions_id
73 schema:value pub.1106254457
74 rdf:type schema:PropertyValue
75 N9e91e47128f747ff94b60ffe89cd13b7 schema:familyName Whitley
76 schema:givenName Darrell
77 rdf:type schema:Person
78 N9f5ac50472244d489ee49dfae4577be3 schema:familyName Machado
79 schema:givenName Penousal
80 rdf:type schema:Person
81 Na370db02d8cf4c55ba14b9fdeacd5501 rdf:first N47033d7c1a05451daca92673e73f3d9e
82 rdf:rest N51f5bf15617e4533a8d7a9ad74bef304
83 Nbc34e70d63cd4f858dc1fd1840aaeb1c rdf:first Needf770256fb4e5ea263b8c950fa6867
84 rdf:rest N23b73b9a730e4597bc5c09e004da1a09
85 Nc7a09e1a951b443489fff7d529af4626 schema:location Cham
86 schema:name Springer International Publishing
87 rdf:type schema:Organisation
88 Ncb6de8625d7b4fd58584d7e4b24a1c67 rdf:first sg:person.010360414373.45
89 rdf:rest rdf:nil
90 Ncf8c3efd28cb4e29b18b15b74e7be829 schema:name readcube_id
91 schema:value 6cbc602e28b0803fa55fd6885f340503506afd2f404c6de2062dd8a6f06758c3
92 rdf:type schema:PropertyValue
93 Needf770256fb4e5ea263b8c950fa6867 schema:familyName Paquete
94 schema:givenName Luís
95 rdf:type schema:Person
96 Nf29c8b08ee2f49c0b911e4f494fd3213 schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
99 schema:name Information and Computing Sciences
100 rdf:type schema:DefinedTerm
101 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
102 schema:name Computation Theory and Mathematics
103 rdf:type schema:DefinedTerm
104 sg:person.010360414373.45 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
105 schema:familyName Doerr
106 schema:givenName Carola
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
108 rdf:type schema:Person
109 sg:pub.10.1007/s00453-002-0940-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038676592
110 https://doi.org/10.1007/s00453-002-0940-2
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/s00453-012-9616-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045973415
113 https://doi.org/10.1007/s00453-012-9616-8
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/s00453-015-0019-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032720526
116 https://doi.org/10.1007/s00453-015-0019-5
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/s00453-017-0354-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091088346
119 https://doi.org/10.1007/s00453-017-0354-9
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1016/j.tcs.2010.10.035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021244275
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/j.tcs.2014.11.028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008296423
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1017/s0963548312000600 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020245943
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1109/tevc.2012.2202241 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061605104
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1145/1967654.1967656 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023650622
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1145/2330163.2330260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004118286
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1145/2908812.2908950 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017940419
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1162/evco_a_00148 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013902553
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1162/evco_a_00171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007746230
138 rdf:type schema:CreativeWork
139 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
140 schema:name Sorbonne Université, CNRS, LIP6, Paris, France
141 rdf:type schema:Organization
 




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


...