What makes a problem hard for a genetic algorithm? Some anomalous results and their explanation View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1993-11

AUTHORS

Stephanie Forrest, Melanie Mitchell

ABSTRACT

What makes a problem easy or hard for a genetic algorithm (GA)? This question has become increasingly important as people have tried to apply the GA to ever more diverse types of problems. Much previous work on this question has studied the relationship between GA performance and the structure of a given fitness function when it is expressed as aWalsh polynomial. The work of Bethke, Goldberg, and others has produced certain theoretical results about this relationship. In this article we review these theoretical results, and then discuss a number of seemingly anomalous experimental results reported by Tanese concerning the performance of the GA on a subclass of Walsh polynomials, some members of which were expected to be easy for the GA to optimize. Tanese found that the GA was poor at optimizing all functions in this subclass, that a partitioning of a single large population into a number of smaller independent populations seemed to improve performance, and that hillelimbing outperformed both the original and partitioned forms of the GA on these functions. These results seemed to contradict several commonly held expectations about GAs.We begin by reviewingschema processing in GAs. We then given an informal description of how Walsh analysis and Bethke's Walsh-schema transform relate to GA performance, and we discuss the relevance of this analysis for GA applications in optimization and machine learning. We then describe Tanese's surprising results, examine them experimentally and theoretically, and propose and evaluate some explanations. These explanations lead to a more fundamental question about GAs: what are the features of problems that determine the likelihood of successful GA performance? More... »

PAGES

285-319

References to SciGraph publications

  • 1988-10. Genetic Algorithms and Machine Learning in MACHINE LEARNING
  • 1990-10. Introduction in MACHINE LEARNING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf00993046

    DOI

    http://dx.doi.org/10.1007/bf00993046

    DIMENSIONS

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


    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/17", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology and Cognitive Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM", 
              "id": "http://www.grid.ac/institutes/grid.266832.b", 
              "name": [
                "Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Forrest", 
            "givenName": "Stephanie", 
            "id": "sg:person.0712103012.64", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI", 
              "id": "http://www.grid.ac/institutes/grid.214458.e", 
              "name": [
                "Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mitchell", 
            "givenName": "Melanie", 
            "id": "sg:person.011607313427.76", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011607313427.76"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1023/a:1022625623050", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043669148", 
              "https://doi.org/10.1023/a:1022625623050"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1022602019183", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009899114", 
              "https://doi.org/10.1023/a:1022602019183"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1993-11", 
        "datePublishedReg": "1993-11-01", 
        "description": "What makes a problem easy or hard for a genetic algorithm (GA)? This question has become increasingly important as people have tried to apply the GA to ever more diverse types of problems. Much previous work on this question has studied the relationship between GA performance and the structure of a given fitness function when it is expressed as aWalsh polynomial. The work of Bethke, Goldberg, and others has produced certain theoretical results about this relationship. In this article we review these theoretical results, and then discuss a number of seemingly anomalous experimental results reported by Tanese concerning the performance of the GA on a subclass of Walsh polynomials, some members of which were expected to be easy for the GA to optimize. Tanese found that the GA was poor at optimizing all functions in this subclass, that a partitioning of a single large population into a number of smaller independent populations seemed to improve performance, and that hillelimbing outperformed both the original and partitioned forms of the GA on these functions. These results seemed to contradict several commonly held expectations about GAs.We begin by reviewingschema processing in GAs. We then given an informal description of how Walsh analysis and Bethke's Walsh-schema transform relate to GA performance, and we discuss the relevance of this analysis for GA applications in optimization and machine learning. We then describe Tanese's surprising results, examine them experimentally and theoretically, and propose and evaluate some explanations. These explanations lead to a more fundamental question about GAs: what are the features of problems that determine the likelihood of successful GA performance?", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf00993046", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1125588", 
            "issn": [
              "0885-6125", 
              "1573-0565"
            ], 
            "name": "Machine Learning", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2-3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "13"
          }
        ], 
        "keywords": [
          "machine learning", 
          "explanation", 
          "learning", 
          "relationship", 
          "performance", 
          "questions", 
          "processing", 
          "fundamental questions", 
          "people", 
          "expectations", 
          "surprising result", 
          "problem", 
          "previous work", 
          "diverse types", 
          "likelihood", 
          "results", 
          "work", 
          "article", 
          "members", 
          "relevance", 
          "function", 
          "Goldberg", 
          "population", 
          "analysis", 
          "genetic algorithm", 
          "features", 
          "types", 
          "theoretical results", 
          "form", 
          "description", 
          "GA performance", 
          "number", 
          "certain theoretical results", 
          "experimental results", 
          "large population", 
          "informal description", 
          "features of problems", 
          "Walsh polynomials", 
          "Walsh analysis", 
          "fitness function", 
          "polynomials", 
          "independent populations", 
          "algorithm", 
          "structure", 
          "optimization", 
          "subclasses", 
          "gas applications", 
          "applications", 
          "anomalous results", 
          "transform", 
          "partitioning", 
          "single large population", 
          "aWalsh polynomial", 
          "work of Bethke", 
          "Bethke", 
          "anomalous experimental results", 
          "Tanese", 
          "smaller independent populations", 
          "hillelimbing", 
          "reviewingschema processing", 
          "Bethke's Walsh-schema transform", 
          "'s Walsh-schema transform", 
          "Tanese's surprising results", 
          "successful GA performance"
        ], 
        "name": "What makes a problem hard for a genetic algorithm? Some anomalous results and their explanation", 
        "pagination": "285-319", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048698842"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf00993046"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf00993046", 
          "https://app.dimensions.ai/details/publication/pub.1048698842"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:00", 
        "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/article/article_262.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf00993046"
      }
    ]
     

    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/bf00993046'

    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/bf00993046'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00993046'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00993046'


     

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

    140 TRIPLES      22 PREDICATES      91 URIs      81 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf00993046 schema:about anzsrc-for:17
    2 anzsrc-for:1701
    3 schema:author Nf58599b20c554ccfaeb12d2ce8ce80d1
    4 schema:citation sg:pub.10.1023/a:1022602019183
    5 sg:pub.10.1023/a:1022625623050
    6 schema:datePublished 1993-11
    7 schema:datePublishedReg 1993-11-01
    8 schema:description What makes a problem easy or hard for a genetic algorithm (GA)? This question has become increasingly important as people have tried to apply the GA to ever more diverse types of problems. Much previous work on this question has studied the relationship between GA performance and the structure of a given fitness function when it is expressed as aWalsh polynomial. The work of Bethke, Goldberg, and others has produced certain theoretical results about this relationship. In this article we review these theoretical results, and then discuss a number of seemingly anomalous experimental results reported by Tanese concerning the performance of the GA on a subclass of Walsh polynomials, some members of which were expected to be easy for the GA to optimize. Tanese found that the GA was poor at optimizing all functions in this subclass, that a partitioning of a single large population into a number of smaller independent populations seemed to improve performance, and that hillelimbing outperformed both the original and partitioned forms of the GA on these functions. These results seemed to contradict several commonly held expectations about GAs.We begin by reviewingschema processing in GAs. We then given an informal description of how Walsh analysis and Bethke's Walsh-schema transform relate to GA performance, and we discuss the relevance of this analysis for GA applications in optimization and machine learning. We then describe Tanese's surprising results, examine them experimentally and theoretically, and propose and evaluate some explanations. These explanations lead to a more fundamental question about GAs: what are the features of problems that determine the likelihood of successful GA performance?
    9 schema:genre article
    10 schema:inLanguage en
    11 schema:isAccessibleForFree true
    12 schema:isPartOf N6905ac5fe2924b9b8e3575575acda541
    13 N7f02f1651c6b4540a6c9629c4258c834
    14 sg:journal.1125588
    15 schema:keywords 's Walsh-schema transform
    16 Bethke
    17 Bethke's Walsh-schema transform
    18 GA performance
    19 Goldberg
    20 Tanese
    21 Tanese's surprising results
    22 Walsh analysis
    23 Walsh polynomials
    24 aWalsh polynomial
    25 algorithm
    26 analysis
    27 anomalous experimental results
    28 anomalous results
    29 applications
    30 article
    31 certain theoretical results
    32 description
    33 diverse types
    34 expectations
    35 experimental results
    36 explanation
    37 features
    38 features of problems
    39 fitness function
    40 form
    41 function
    42 fundamental questions
    43 gas applications
    44 genetic algorithm
    45 hillelimbing
    46 independent populations
    47 informal description
    48 large population
    49 learning
    50 likelihood
    51 machine learning
    52 members
    53 number
    54 optimization
    55 partitioning
    56 people
    57 performance
    58 polynomials
    59 population
    60 previous work
    61 problem
    62 processing
    63 questions
    64 relationship
    65 relevance
    66 results
    67 reviewingschema processing
    68 single large population
    69 smaller independent populations
    70 structure
    71 subclasses
    72 successful GA performance
    73 surprising result
    74 theoretical results
    75 transform
    76 types
    77 work
    78 work of Bethke
    79 schema:name What makes a problem hard for a genetic algorithm? Some anomalous results and their explanation
    80 schema:pagination 285-319
    81 schema:productId N426419336bc9438db2a5867c4040b5ff
    82 Ne9cb7535c85d413fa14078d78905a46f
    83 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048698842
    84 https://doi.org/10.1007/bf00993046
    85 schema:sdDatePublished 2021-11-01T18:00
    86 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    87 schema:sdPublisher N6b1528d4382a4602a75eed9ed316c15f
    88 schema:url https://doi.org/10.1007/bf00993046
    89 sgo:license sg:explorer/license/
    90 sgo:sdDataset articles
    91 rdf:type schema:ScholarlyArticle
    92 N332aea8f3fba45bc8c2c4d8860182ab4 rdf:first sg:person.011607313427.76
    93 rdf:rest rdf:nil
    94 N426419336bc9438db2a5867c4040b5ff schema:name doi
    95 schema:value 10.1007/bf00993046
    96 rdf:type schema:PropertyValue
    97 N6905ac5fe2924b9b8e3575575acda541 schema:volumeNumber 13
    98 rdf:type schema:PublicationVolume
    99 N6b1528d4382a4602a75eed9ed316c15f schema:name Springer Nature - SN SciGraph project
    100 rdf:type schema:Organization
    101 N7f02f1651c6b4540a6c9629c4258c834 schema:issueNumber 2-3
    102 rdf:type schema:PublicationIssue
    103 Ne9cb7535c85d413fa14078d78905a46f schema:name dimensions_id
    104 schema:value pub.1048698842
    105 rdf:type schema:PropertyValue
    106 Nf58599b20c554ccfaeb12d2ce8ce80d1 rdf:first sg:person.0712103012.64
    107 rdf:rest N332aea8f3fba45bc8c2c4d8860182ab4
    108 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    109 schema:name Psychology and Cognitive Sciences
    110 rdf:type schema:DefinedTerm
    111 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
    112 schema:name Psychology
    113 rdf:type schema:DefinedTerm
    114 sg:journal.1125588 schema:issn 0885-6125
    115 1573-0565
    116 schema:name Machine Learning
    117 schema:publisher Springer Nature
    118 rdf:type schema:Periodical
    119 sg:person.011607313427.76 schema:affiliation grid-institutes:grid.214458.e
    120 schema:familyName Mitchell
    121 schema:givenName Melanie
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011607313427.76
    123 rdf:type schema:Person
    124 sg:person.0712103012.64 schema:affiliation grid-institutes:grid.266832.b
    125 schema:familyName Forrest
    126 schema:givenName Stephanie
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64
    128 rdf:type schema:Person
    129 sg:pub.10.1023/a:1022602019183 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009899114
    130 https://doi.org/10.1023/a:1022602019183
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1023/a:1022625623050 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043669148
    133 https://doi.org/10.1023/a:1022625623050
    134 rdf:type schema:CreativeWork
    135 grid-institutes:grid.214458.e schema:alternateName Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI
    136 schema:name Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI
    137 rdf:type schema:Organization
    138 grid-institutes:grid.266832.b schema:alternateName Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM
    139 schema:name Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM
    140 rdf:type schema:Organization
     




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


    ...