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 a Walsh 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 hillclimbing 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 reviewing schema processing in GAs. We then give 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.1023/a:1022626114466

    DOI

    http://dx.doi.org/10.1023/a:1022626114466

    DIMENSIONS

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


    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 a Walsh 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 hillclimbing 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 reviewing schema processing in GAs. We then give 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.1023/a:1022626114466", 
        "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": [
          "schema processing", 
          "machine learning", 
          "explanation", 
          "relationship", 
          "performance", 
          "learning", 
          "questions", 
          "processing", 
          "fundamental questions", 
          "people", 
          "expectations", 
          "problem", 
          "previous work", 
          "surprising result", 
          "diverse types", 
          "results", 
          "likelihood", 
          "work", 
          "article", 
          "members", 
          "relevance", 
          "function", 
          "Goldberg", 
          "genetic algorithm", 
          "population", 
          "analysis", 
          "GA performance", 
          "Walsh polynomials", 
          "theoretical results", 
          "form", 
          "description", 
          "features", 
          "types", 
          "certain theoretical results", 
          "number", 
          "features of problems", 
          "experimental results", 
          "large population", 
          "informal description", 
          "Walsh analysis", 
          "fitness function", 
          "polynomials", 
          "independent populations", 
          "algorithm", 
          "hillclimbing", 
          "optimization", 
          "structure", 
          "subclasses", 
          "gas applications", 
          "applications", 
          "anomalous results", 
          "transform", 
          "partitioning", 
          "single large population", 
          "work of Bethke", 
          "Bethke", 
          "anomalous experimental results", 
          "Tanese", 
          "smaller independent populations", 
          "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.1031194073"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1022626114466"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1022626114466", 
          "https://app.dimensions.ai/details/publication/pub.1031194073"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:07", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_231.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1023/a:1022626114466"
      }
    ]
     

    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.1023/a:1022626114466'

    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.1023/a:1022626114466'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1022626114466'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1022626114466'


     

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

    139 TRIPLES      22 PREDICATES      90 URIs      80 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1022626114466 schema:about anzsrc-for:17
    2 anzsrc-for:1701
    3 schema:author N425c67ae411049ce93c7a64b2d22d8e4
    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 a Walsh 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 hillclimbing 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 reviewing schema processing in GAs. We then give 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 N1bfe7d7fcc99469db3ec1229e45547b4
    13 N96fd4adc8ee0469f9f8104773e348bbc
    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 algorithm
    25 analysis
    26 anomalous experimental results
    27 anomalous results
    28 applications
    29 article
    30 certain theoretical results
    31 description
    32 diverse types
    33 expectations
    34 experimental results
    35 explanation
    36 features
    37 features of problems
    38 fitness function
    39 form
    40 function
    41 fundamental questions
    42 gas applications
    43 genetic algorithm
    44 hillclimbing
    45 independent populations
    46 informal description
    47 large population
    48 learning
    49 likelihood
    50 machine learning
    51 members
    52 number
    53 optimization
    54 partitioning
    55 people
    56 performance
    57 polynomials
    58 population
    59 previous work
    60 problem
    61 processing
    62 questions
    63 relationship
    64 relevance
    65 results
    66 schema processing
    67 single large population
    68 smaller independent populations
    69 structure
    70 subclasses
    71 successful GA performance
    72 surprising result
    73 theoretical results
    74 transform
    75 types
    76 work
    77 work of Bethke
    78 schema:name What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation
    79 schema:pagination 285-319
    80 schema:productId Na6eab9d43be64b7ab11fd818be328fc3
    81 Nbf557ad897e64c739756d44bbfc5b0ec
    82 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031194073
    83 https://doi.org/10.1023/a:1022626114466
    84 schema:sdDatePublished 2021-12-01T19:07
    85 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    86 schema:sdPublisher N26275d053ccf49058237c2a9a02f5f5b
    87 schema:url https://doi.org/10.1023/a:1022626114466
    88 sgo:license sg:explorer/license/
    89 sgo:sdDataset articles
    90 rdf:type schema:ScholarlyArticle
    91 N1bfe7d7fcc99469db3ec1229e45547b4 schema:issueNumber 2-3
    92 rdf:type schema:PublicationIssue
    93 N26275d053ccf49058237c2a9a02f5f5b schema:name Springer Nature - SN SciGraph project
    94 rdf:type schema:Organization
    95 N425c67ae411049ce93c7a64b2d22d8e4 rdf:first sg:person.0712103012.64
    96 rdf:rest N6706f8ec64da4f339b1ee227b7ea2445
    97 N6706f8ec64da4f339b1ee227b7ea2445 rdf:first sg:person.011607313427.76
    98 rdf:rest rdf:nil
    99 N96fd4adc8ee0469f9f8104773e348bbc schema:volumeNumber 13
    100 rdf:type schema:PublicationVolume
    101 Na6eab9d43be64b7ab11fd818be328fc3 schema:name doi
    102 schema:value 10.1023/a:1022626114466
    103 rdf:type schema:PropertyValue
    104 Nbf557ad897e64c739756d44bbfc5b0ec schema:name dimensions_id
    105 schema:value pub.1031194073
    106 rdf:type schema:PropertyValue
    107 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    108 schema:name Psychology and Cognitive Sciences
    109 rdf:type schema:DefinedTerm
    110 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
    111 schema:name Psychology
    112 rdf:type schema:DefinedTerm
    113 sg:journal.1125588 schema:issn 0885-6125
    114 1573-0565
    115 schema:name Machine Learning
    116 schema:publisher Springer Nature
    117 rdf:type schema:Periodical
    118 sg:person.011607313427.76 schema:affiliation grid-institutes:grid.214458.e
    119 schema:familyName Mitchell
    120 schema:givenName Melanie
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011607313427.76
    122 rdf:type schema:Person
    123 sg:person.0712103012.64 schema:affiliation grid-institutes:grid.266832.b
    124 schema:familyName Forrest
    125 schema:givenName Stephanie
    126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0712103012.64
    127 rdf:type schema:Person
    128 sg:pub.10.1023/a:1022602019183 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009899114
    129 https://doi.org/10.1023/a:1022602019183
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1023/a:1022625623050 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043669148
    132 https://doi.org/10.1023/a:1022625623050
    133 rdf:type schema:CreativeWork
    134 grid-institutes:grid.214458.e schema:alternateName Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI
    135 schema:name Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI
    136 rdf:type schema:Organization
    137 grid-institutes:grid.266832.b schema:alternateName Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM
    138 schema:name Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM
    139 rdf:type schema:Organization
     




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


    ...