What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1993

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 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 reviewingschema processingin 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

129-163

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4615-2740-4_6

DOI

http://dx.doi.org/10.1007/978-1-4615-2740-4_6

DIMENSIONS

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


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, USA", 
          "id": "http://www.grid.ac/institutes/grid.266832.b", 
          "name": [
            "Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM, USA"
          ], 
          "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, USA", 
          "id": "http://www.grid.ac/institutes/grid.214458.e", 
          "name": [
            "Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI, USA"
          ], 
          "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"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-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 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 reviewingschema processingin GAs. We then give an informal description of how Walsh analysis and Bethke\u2019s 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\u2019s 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?", 
    "editor": [
      {
        "familyName": "Grefenstette", 
        "givenName": "John J.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4615-2740-4_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-1-4613-6182-4", 
        "978-1-4615-2740-4"
      ], 
      "name": "Genetic Algorithms for Machine Learning", 
      "type": "Book"
    }, 
    "keywords": [
      "genetic algorithm", 
      "theoretical results", 
      "GA performance", 
      "machine learning", 
      "certain theoretical results", 
      "learning", 
      "explanation", 
      "features of problems", 
      "questions", 
      "relationship", 
      "performance", 
      "Walsh polynomials", 
      "Walsh analysis", 
      "fundamental questions", 
      "people", 
      "fitness function", 
      "polynomials", 
      "expectations", 
      "problem", 
      "surprising result", 
      "algorithm", 
      "diverse types", 
      "previous work", 
      "likelihood", 
      "results", 
      "optimization", 
      "work", 
      "function", 
      "article", 
      "subclasses", 
      "members", 
      "hillclimbing", 
      "relevance", 
      "gas applications", 
      "Goldberg", 
      "experimental results", 
      "number", 
      "population", 
      "form", 
      "informal description", 
      "description", 
      "analysis", 
      "applications", 
      "features", 
      "types", 
      "transform", 
      "partitioning", 
      "large population", 
      "independent populations", 
      "structure", 
      "anomalous results", 
      "single large population", 
      "aWalsh polynomial", 
      "work of Bethke", 
      "Bethke", 
      "anomalous experimental results", 
      "Tanese", 
      "smaller independent populations", 
      "reviewingschema processingin GAs", 
      "processingin GAs", 
      "Bethke\u2019s Walsh-schema transform", 
      "\u2019s Walsh-schema transform", 
      "Tanese\u2019s surprising results", 
      "successful GA performance"
    ], 
    "name": "What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation", 
    "pagination": "129-163", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030381250"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4615-2740-4_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4615-2740-4_6", 
      "https://app.dimensions.ai/details/publication/pub.1030381250"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:10", 
    "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/chapter/chapter_423.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-1-4615-2740-4_6"
  }
]
 

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-1-4615-2740-4_6'

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-1-4615-2740-4_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4615-2740-4_6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4615-2740-4_6'


 

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

134 TRIPLES      23 PREDICATES      90 URIs      83 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4615-2740-4_6 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author Nf5facd9eb1d943a989f9f0784d78ac8c
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 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 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 reviewingschema processingin 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?
7 schema:editor Nefb48bd82ae84c8981885599a6049ea2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na740295ba2e24a6f8d2a5a5e27bbca6c
12 schema:keywords Bethke
13 Bethke’s Walsh-schema transform
14 GA performance
15 Goldberg
16 Tanese
17 Tanese’s surprising results
18 Walsh analysis
19 Walsh polynomials
20 aWalsh polynomial
21 algorithm
22 analysis
23 anomalous experimental results
24 anomalous results
25 applications
26 article
27 certain theoretical results
28 description
29 diverse types
30 expectations
31 experimental results
32 explanation
33 features
34 features of problems
35 fitness function
36 form
37 function
38 fundamental questions
39 gas applications
40 genetic algorithm
41 hillclimbing
42 independent populations
43 informal description
44 large population
45 learning
46 likelihood
47 machine learning
48 members
49 number
50 optimization
51 partitioning
52 people
53 performance
54 polynomials
55 population
56 previous work
57 problem
58 processingin GAs
59 questions
60 relationship
61 relevance
62 results
63 reviewingschema processingin GAs
64 single large population
65 smaller independent populations
66 structure
67 subclasses
68 successful GA performance
69 surprising result
70 theoretical results
71 transform
72 types
73 work
74 work of Bethke
75 ’s Walsh-schema transform
76 schema:name What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation
77 schema:pagination 129-163
78 schema:productId N19d6db55add14670969a364515500729
79 N8967a9a5d09649778c302209d4ba2099
80 schema:publisher N0cdbc386917e41b4bd309a5f6166a981
81 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030381250
82 https://doi.org/10.1007/978-1-4615-2740-4_6
83 schema:sdDatePublished 2021-12-01T20:10
84 schema:sdLicense https://scigraph.springernature.com/explorer/license/
85 schema:sdPublisher Ne1dd203864fd4f7c9b94d51b3d5d7479
86 schema:url https://doi.org/10.1007/978-1-4615-2740-4_6
87 sgo:license sg:explorer/license/
88 sgo:sdDataset chapters
89 rdf:type schema:Chapter
90 N0cdbc386917e41b4bd309a5f6166a981 schema:name Springer Nature
91 rdf:type schema:Organisation
92 N19d6db55add14670969a364515500729 schema:name dimensions_id
93 schema:value pub.1030381250
94 rdf:type schema:PropertyValue
95 N33e9d0d293a84afcbc1d51ab7a8c3be0 rdf:first sg:person.011607313427.76
96 rdf:rest rdf:nil
97 N8967a9a5d09649778c302209d4ba2099 schema:name doi
98 schema:value 10.1007/978-1-4615-2740-4_6
99 rdf:type schema:PropertyValue
100 Na740295ba2e24a6f8d2a5a5e27bbca6c schema:isbn 978-1-4613-6182-4
101 978-1-4615-2740-4
102 schema:name Genetic Algorithms for Machine Learning
103 rdf:type schema:Book
104 Nb3e497ae63d84e0bae54f989cccc9af0 schema:familyName Grefenstette
105 schema:givenName John J.
106 rdf:type schema:Person
107 Ne1dd203864fd4f7c9b94d51b3d5d7479 schema:name Springer Nature - SN SciGraph project
108 rdf:type schema:Organization
109 Nefb48bd82ae84c8981885599a6049ea2 rdf:first Nb3e497ae63d84e0bae54f989cccc9af0
110 rdf:rest rdf:nil
111 Nf5facd9eb1d943a989f9f0784d78ac8c rdf:first sg:person.0712103012.64
112 rdf:rest N33e9d0d293a84afcbc1d51ab7a8c3be0
113 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
114 schema:name Psychology and Cognitive Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
117 schema:name Psychology
118 rdf:type schema:DefinedTerm
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 grid-institutes:grid.214458.e schema:alternateName Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI, USA
130 schema:name Artificial Intelligence Laboratory, University of Michigan, 48109-2110, Ann Arbor, MI, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.266832.b schema:alternateName Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM, USA
133 schema:name Department of Computer Science, University of New Mexico, 87181-1386, Albuquerque, NM, USA
134 rdf:type schema:Organization
 




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


...