Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-05

AUTHORS

Benjamin Doerr, Carola Doerr, Timo Kötzing

ABSTRACT

The most common representation in evolutionary computation are bit strings. With very little theoretical work existing on how to use evolutionary algorithms for decision variables taking more than two values, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over Ω={0,1,…,r-1}n. We observe a crucial difference in how we extend the one-bit-flip and standard-bit mutation operators to the multi-valued domain. While it is natural to modify a random position of the string or select each position of the solution vector for modification independently with probability 1/n, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of Θ(nrlogn). If we change each selected position by +1 or -1 (random choice), the optimization time reduces to Θ(nr+nlogn). If we use a random mutation strength i∈{0,1,…,r-1} with probability inversely proportional to i and change the selected position by +i or -i (random choice), then the optimization time becomes Θ(nlog(r)(logn+logr)), which is asymptotically faster than the previous if r=ω(log(n)loglog(n)). Interestingly, a better expected performance can be achieved with a self-adjusting mutation strength that is based on the success of previous iterations. For the mutation operator that modifies a randomly chosen position, we show that the self-adjusting mutation strength yields an expected optimization time of Θ(n(logn+logr)), which is best possible among all dynamic mutation strengths. In our proofs, we use a new multiplicative drift theorem for computing lower bounds, which is not restricted to processes that move only towards the target. More... »

PAGES

1732-1768

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-017-0341-1

DOI

http://dx.doi.org/10.1007/s00453-017-0341-1

DIMENSIONS

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


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": {
          "alternateName": "\u00c9cole Polytechnique", 
          "id": "https://www.grid.ac/institutes/grid.10877.39", 
          "name": [
            "LIX - UMR 7161, \u00c9cole Polytechnique, CS35003, 91120, Palaiseau, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Doerr", 
        "givenName": "Benjamin", 
        "id": "sg:person.01327223002.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327223002.89"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "CNRS, LIP6 UMR 7606, Sorbonne Universit\u00e9s, UPMC Univ Paris 06, 4 place Jussieu, 75005, 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"
      }, 
      {
        "affiliation": {
          "name": [
            "Hasso-Plattner-Institut, Prof.-Dr.-Helmert-Str. 2-3, 14482, Potsdam, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "K\u00f6tzing", 
        "givenName": "Timo", 
        "id": "sg:person.014204051473.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014204051473.89"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-15844-5_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000452291", 
          "https://doi.org/10.1007/978-3-642-15844-5_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-87700-4_12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003069470", 
          "https://doi.org/10.1007/978-3-540-87700-4_12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-87700-4_12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003069470", 
          "https://doi.org/10.1007/978-3-540-87700-4_12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1967654.1967671", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004292096"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2576768.2598301", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007356485"
        ], 
        "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.1145/2001576.2001856", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008768215"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2739480.2754684", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012276676"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2330163.2330346", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012586543"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17339-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012726107", 
          "https://doi.org/10.1007/978-3-642-17339-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17339-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012726107", 
          "https://doi.org/10.1007/978-3-642-17339-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-58484-6_258", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013453413", 
          "https://doi.org/10.1007/3-540-58484-6_258"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0004-3702(01)00058-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014205266"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11513575_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014437848", 
          "https://doi.org/10.1007/11513575_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2725494.2725502", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015081096"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0963548309990599", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017811806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9622-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017937785", 
          "https://doi.org/10.1007/s00453-012-9622-x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2908812.2908950", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017940419"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-45823-6_75", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019329847", 
          "https://doi.org/10.1007/978-3-319-45823-6_75"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0963548312000600", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020245943"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/b:jmma.0000049379.14872.f5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020814341", 
          "https://doi.org/10.1023/b:jmma.0000049379.14872.f5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1967654.1967665", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026965563"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2576768.2598359", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026971837"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1276958.1277192", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031955158"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-45823-6_73", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033020271", 
          "https://doi.org/10.1007/978-3-319-45823-6_73"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-87744-8_46", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038138435", 
          "https://doi.org/10.1007/978-3-540-87744-8_46"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-87744-8_46", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038138435", 
          "https://doi.org/10.1007/978-3-540-87744-8_46"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-011-9585-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040023322", 
          "https://doi.org/10.1007/s00453-011-9585-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2908812.2908891", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040036399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-004-1177-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040195428", 
          "https://doi.org/10.1007/s00224-004-1177-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1527125.1527132", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040237716"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jda.2005.01.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040724236"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1043679011", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-05094-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043679011", 
          "https://doi.org/10.1007/978-3-662-05094-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-05094-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043679011", 
          "https://doi.org/10.1007/978-3-662-05094-1"
        ], 
        "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.1145/1068009.1068106", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048237334"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-10762-2_88", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052759453", 
          "https://doi.org/10.1007/978-3-319-10762-2_88"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-45823-6_77", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053595609", 
          "https://doi.org/10.1007/978-3-319-45823-6_77"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1108/17563780910959893", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053735829"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/4235.771166", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061172023"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tevc.2014.2308294", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061605203"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/9789814282673_0001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088792900"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3071178.3071297", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1090604631"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3071178.3071279", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1090604759"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/cec.2009.4983114", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095146579"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icec.1995.489123", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095760180"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-05", 
    "datePublishedReg": "2018-05-01", 
    "description": "The most common representation in evolutionary computation are bit strings. With very little theoretical work existing on how to use evolutionary algorithms for decision variables taking more than two values, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over \u03a9={0,1,\u2026,r-1}n. We observe a crucial difference in how we extend the one-bit-flip and standard-bit mutation operators to the multi-valued domain. While it is natural to modify a random position of the string or select each position of the solution vector for modification independently with probability 1/n, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of \u0398(nrlogn). If we change each selected position by +1 or -1 (random choice), the optimization time reduces to \u0398(nr+nlogn). If we use a random mutation strength i\u2208{0,1,\u2026,r-1} with probability inversely proportional to i and change the selected position by +i or -i (random choice), then the optimization time becomes \u0398(nlog(r)(logn+logr)), which is asymptotically faster than the previous if r=\u03c9(log(n)loglog(n)). Interestingly, a better expected performance can be achieved with a self-adjusting mutation strength that is based on the success of previous iterations. For the mutation operator that modifies a randomly chosen position, we show that the self-adjusting mutation strength yields an expected optimization time of \u0398(n(logn+logr)), which is best possible among all dynamic mutation strengths. In our proofs, we use a new multiplicative drift theorem for computing lower bounds, which is not restricted to processes that move only towards the target.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-017-0341-1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "5", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "80"
      }
    ], 
    "name": "Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables", 
    "pagination": "1732-1768", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "788ec262b2596105773fce56d40f11904e172760fa8cd375f7521b4f24235839"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-017-0341-1"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1090357901"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-017-0341-1", 
      "https://app.dimensions.ai/details/publication/pub.1090357901"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:28", 
    "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/0000000362_0000000362/records_87119_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-017-0341-1"
  }
]
 

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/s00453-017-0341-1'

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/s00453-017-0341-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0341-1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0341-1'


 

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

223 TRIPLES      21 PREDICATES      70 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-017-0341-1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na219644fcf064a94a78995c4a6c6d50a
4 schema:citation sg:pub.10.1007/11513575_14
5 sg:pub.10.1007/3-540-58484-6_258
6 sg:pub.10.1007/978-3-319-10762-2_88
7 sg:pub.10.1007/978-3-319-45823-6_73
8 sg:pub.10.1007/978-3-319-45823-6_75
9 sg:pub.10.1007/978-3-319-45823-6_77
10 sg:pub.10.1007/978-3-540-87700-4_12
11 sg:pub.10.1007/978-3-540-87744-8_46
12 sg:pub.10.1007/978-3-642-15844-5_1
13 sg:pub.10.1007/978-3-642-17339-4
14 sg:pub.10.1007/978-3-662-05094-1
15 sg:pub.10.1007/s00224-004-1177-z
16 sg:pub.10.1007/s00453-011-9585-3
17 sg:pub.10.1007/s00453-012-9616-8
18 sg:pub.10.1007/s00453-012-9622-x
19 sg:pub.10.1023/b:jmma.0000049379.14872.f5
20 https://app.dimensions.ai/details/publication/pub.1043679011
21 https://doi.org/10.1016/j.jda.2005.01.002
22 https://doi.org/10.1016/j.tcs.2014.11.028
23 https://doi.org/10.1016/s0004-3702(01)00058-3
24 https://doi.org/10.1017/s0963548309990599
25 https://doi.org/10.1017/s0963548312000600
26 https://doi.org/10.1108/17563780910959893
27 https://doi.org/10.1109/4235.771166
28 https://doi.org/10.1109/cec.2009.4983114
29 https://doi.org/10.1109/icec.1995.489123
30 https://doi.org/10.1109/tevc.2014.2308294
31 https://doi.org/10.1142/9789814282673_0001
32 https://doi.org/10.1145/1068009.1068106
33 https://doi.org/10.1145/1276958.1277192
34 https://doi.org/10.1145/1527125.1527132
35 https://doi.org/10.1145/1967654.1967665
36 https://doi.org/10.1145/1967654.1967671
37 https://doi.org/10.1145/2001576.2001856
38 https://doi.org/10.1145/2330163.2330346
39 https://doi.org/10.1145/2576768.2598301
40 https://doi.org/10.1145/2576768.2598359
41 https://doi.org/10.1145/2725494.2725502
42 https://doi.org/10.1145/2739480.2754684
43 https://doi.org/10.1145/2908812.2908891
44 https://doi.org/10.1145/2908812.2908950
45 https://doi.org/10.1145/3071178.3071279
46 https://doi.org/10.1145/3071178.3071297
47 schema:datePublished 2018-05
48 schema:datePublishedReg 2018-05-01
49 schema:description The most common representation in evolutionary computation are bit strings. With very little theoretical work existing on how to use evolutionary algorithms for decision variables taking more than two values, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over Ω={0,1,…,r-1}n. We observe a crucial difference in how we extend the one-bit-flip and standard-bit mutation operators to the multi-valued domain. While it is natural to modify a random position of the string or select each position of the solution vector for modification independently with probability 1/n, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of Θ(nrlogn). If we change each selected position by +1 or -1 (random choice), the optimization time reduces to Θ(nr+nlogn). If we use a random mutation strength i∈{0,1,…,r-1} with probability inversely proportional to i and change the selected position by +i or -i (random choice), then the optimization time becomes Θ(nlog(r)(logn+logr)), which is asymptotically faster than the previous if r=ω(log(n)loglog(n)). Interestingly, a better expected performance can be achieved with a self-adjusting mutation strength that is based on the success of previous iterations. For the mutation operator that modifies a randomly chosen position, we show that the self-adjusting mutation strength yields an expected optimization time of Θ(n(logn+logr)), which is best possible among all dynamic mutation strengths. In our proofs, we use a new multiplicative drift theorem for computing lower bounds, which is not restricted to processes that move only towards the target.
50 schema:genre research_article
51 schema:inLanguage en
52 schema:isAccessibleForFree false
53 schema:isPartOf N4b264d17cb5e40319b93b468dbc04051
54 N78af00dcab3e4ea4b311ae736482de5b
55 sg:journal.1047644
56 schema:name Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables
57 schema:pagination 1732-1768
58 schema:productId Ncae8fdfd089e495599192240fb85da52
59 Ne2e92f7b77744529b464b8e3c90f955d
60 Neac37101c207494ebbceb0922b9c8dd7
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090357901
62 https://doi.org/10.1007/s00453-017-0341-1
63 schema:sdDatePublished 2019-04-11T12:28
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Nd8140085b8fd4fef8ea7c71ceeb64284
66 schema:url https://link.springer.com/10.1007%2Fs00453-017-0341-1
67 sgo:license sg:explorer/license/
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
70 N05180a8654cc4cd8ab1573e65bf9b718 rdf:first sg:person.014204051473.89
71 rdf:rest rdf:nil
72 N4615dc2f12bd4e949b7394040fff8a7d schema:name CNRS, LIP6 UMR 7606, Sorbonne Universités, UPMC Univ Paris 06, 4 place Jussieu, 75005, Paris, France
73 rdf:type schema:Organization
74 N4b264d17cb5e40319b93b468dbc04051 schema:volumeNumber 80
75 rdf:type schema:PublicationVolume
76 N72fbb00cdbe346baac17a666d29c54ac rdf:first sg:person.010360414373.45
77 rdf:rest N05180a8654cc4cd8ab1573e65bf9b718
78 N78af00dcab3e4ea4b311ae736482de5b schema:issueNumber 5
79 rdf:type schema:PublicationIssue
80 Na219644fcf064a94a78995c4a6c6d50a rdf:first sg:person.01327223002.89
81 rdf:rest N72fbb00cdbe346baac17a666d29c54ac
82 Nb0967c5c91944408a147c87fae4f7cf8 schema:name Hasso-Plattner-Institut, Prof.-Dr.-Helmert-Str. 2-3, 14482, Potsdam, Germany
83 rdf:type schema:Organization
84 Ncae8fdfd089e495599192240fb85da52 schema:name doi
85 schema:value 10.1007/s00453-017-0341-1
86 rdf:type schema:PropertyValue
87 Nd8140085b8fd4fef8ea7c71ceeb64284 schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 Ne2e92f7b77744529b464b8e3c90f955d schema:name dimensions_id
90 schema:value pub.1090357901
91 rdf:type schema:PropertyValue
92 Neac37101c207494ebbceb0922b9c8dd7 schema:name readcube_id
93 schema:value 788ec262b2596105773fce56d40f11904e172760fa8cd375f7521b4f24235839
94 rdf:type schema:PropertyValue
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
99 schema:name Computation Theory and Mathematics
100 rdf:type schema:DefinedTerm
101 sg:journal.1047644 schema:issn 0178-4617
102 1432-0541
103 schema:name Algorithmica
104 rdf:type schema:Periodical
105 sg:person.010360414373.45 schema:affiliation N4615dc2f12bd4e949b7394040fff8a7d
106 schema:familyName Doerr
107 schema:givenName Carola
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
109 rdf:type schema:Person
110 sg:person.01327223002.89 schema:affiliation https://www.grid.ac/institutes/grid.10877.39
111 schema:familyName Doerr
112 schema:givenName Benjamin
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01327223002.89
114 rdf:type schema:Person
115 sg:person.014204051473.89 schema:affiliation Nb0967c5c91944408a147c87fae4f7cf8
116 schema:familyName Kötzing
117 schema:givenName Timo
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014204051473.89
119 rdf:type schema:Person
120 sg:pub.10.1007/11513575_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014437848
121 https://doi.org/10.1007/11513575_14
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/3-540-58484-6_258 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013453413
124 https://doi.org/10.1007/3-540-58484-6_258
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/978-3-319-10762-2_88 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052759453
127 https://doi.org/10.1007/978-3-319-10762-2_88
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/978-3-319-45823-6_73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033020271
130 https://doi.org/10.1007/978-3-319-45823-6_73
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/978-3-319-45823-6_75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019329847
133 https://doi.org/10.1007/978-3-319-45823-6_75
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/978-3-319-45823-6_77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053595609
136 https://doi.org/10.1007/978-3-319-45823-6_77
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/978-3-540-87700-4_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003069470
139 https://doi.org/10.1007/978-3-540-87700-4_12
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/978-3-540-87744-8_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038138435
142 https://doi.org/10.1007/978-3-540-87744-8_46
143 rdf:type schema:CreativeWork
144 sg:pub.10.1007/978-3-642-15844-5_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000452291
145 https://doi.org/10.1007/978-3-642-15844-5_1
146 rdf:type schema:CreativeWork
147 sg:pub.10.1007/978-3-642-17339-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012726107
148 https://doi.org/10.1007/978-3-642-17339-4
149 rdf:type schema:CreativeWork
150 sg:pub.10.1007/978-3-662-05094-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043679011
151 https://doi.org/10.1007/978-3-662-05094-1
152 rdf:type schema:CreativeWork
153 sg:pub.10.1007/s00224-004-1177-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1040195428
154 https://doi.org/10.1007/s00224-004-1177-z
155 rdf:type schema:CreativeWork
156 sg:pub.10.1007/s00453-011-9585-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040023322
157 https://doi.org/10.1007/s00453-011-9585-3
158 rdf:type schema:CreativeWork
159 sg:pub.10.1007/s00453-012-9616-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045973415
160 https://doi.org/10.1007/s00453-012-9616-8
161 rdf:type schema:CreativeWork
162 sg:pub.10.1007/s00453-012-9622-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1017937785
163 https://doi.org/10.1007/s00453-012-9622-x
164 rdf:type schema:CreativeWork
165 sg:pub.10.1023/b:jmma.0000049379.14872.f5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020814341
166 https://doi.org/10.1023/b:jmma.0000049379.14872.f5
167 rdf:type schema:CreativeWork
168 https://app.dimensions.ai/details/publication/pub.1043679011 schema:CreativeWork
169 https://doi.org/10.1016/j.jda.2005.01.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040724236
170 rdf:type schema:CreativeWork
171 https://doi.org/10.1016/j.tcs.2014.11.028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008296423
172 rdf:type schema:CreativeWork
173 https://doi.org/10.1016/s0004-3702(01)00058-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014205266
174 rdf:type schema:CreativeWork
175 https://doi.org/10.1017/s0963548309990599 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017811806
176 rdf:type schema:CreativeWork
177 https://doi.org/10.1017/s0963548312000600 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020245943
178 rdf:type schema:CreativeWork
179 https://doi.org/10.1108/17563780910959893 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053735829
180 rdf:type schema:CreativeWork
181 https://doi.org/10.1109/4235.771166 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061172023
182 rdf:type schema:CreativeWork
183 https://doi.org/10.1109/cec.2009.4983114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095146579
184 rdf:type schema:CreativeWork
185 https://doi.org/10.1109/icec.1995.489123 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095760180
186 rdf:type schema:CreativeWork
187 https://doi.org/10.1109/tevc.2014.2308294 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061605203
188 rdf:type schema:CreativeWork
189 https://doi.org/10.1142/9789814282673_0001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088792900
190 rdf:type schema:CreativeWork
191 https://doi.org/10.1145/1068009.1068106 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048237334
192 rdf:type schema:CreativeWork
193 https://doi.org/10.1145/1276958.1277192 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031955158
194 rdf:type schema:CreativeWork
195 https://doi.org/10.1145/1527125.1527132 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040237716
196 rdf:type schema:CreativeWork
197 https://doi.org/10.1145/1967654.1967665 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026965563
198 rdf:type schema:CreativeWork
199 https://doi.org/10.1145/1967654.1967671 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004292096
200 rdf:type schema:CreativeWork
201 https://doi.org/10.1145/2001576.2001856 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008768215
202 rdf:type schema:CreativeWork
203 https://doi.org/10.1145/2330163.2330346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012586543
204 rdf:type schema:CreativeWork
205 https://doi.org/10.1145/2576768.2598301 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007356485
206 rdf:type schema:CreativeWork
207 https://doi.org/10.1145/2576768.2598359 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026971837
208 rdf:type schema:CreativeWork
209 https://doi.org/10.1145/2725494.2725502 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015081096
210 rdf:type schema:CreativeWork
211 https://doi.org/10.1145/2739480.2754684 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012276676
212 rdf:type schema:CreativeWork
213 https://doi.org/10.1145/2908812.2908891 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040036399
214 rdf:type schema:CreativeWork
215 https://doi.org/10.1145/2908812.2908950 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017940419
216 rdf:type schema:CreativeWork
217 https://doi.org/10.1145/3071178.3071279 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090604759
218 rdf:type schema:CreativeWork
219 https://doi.org/10.1145/3071178.3071297 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090604631
220 rdf:type schema:CreativeWork
221 https://www.grid.ac/institutes/grid.10877.39 schema:alternateName École Polytechnique
222 schema:name LIX - UMR 7161, École Polytechnique, CS35003, 91120, Palaiseau, France
223 rdf:type schema:Organization
 




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


...