More Web Proxy on the site http://driver.im/

research-article

Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes

Authors:

Benjamin P. Carlson,

Dean F. HougenAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 791 - 798

https://doi.org/10.1145/1830483.1830622

Published: 07 July 2010 Publication History

Abstract

Many complex problems can be solved by a sequence of steps or simple heuristics. In many cases a good solution relies on both good heuristics and proper ordering of their application. Problems such as creating a constrained path through a graph can be solved in this way if we can find a mechanism for ordering the heuristics. We propose using a genetic algorithm (GA) for this purpose to solve the snake-in-the-box problem. However, the additional layer of abstraction created by heuristics weakens the guiding effects of traditional GA operators. We also propose a new set of GA operators that solve this problem by, in the manipulation of the population, applying information from the paths (snakes) produced by the population members. In addition we show the efficacy of this approach by producing a new record length snake of 98 edges in an eight dimensional hypercube. We also compare our new operators with more traditional ones.

References

[1]

Altenberg, L. Evolving better representation through selective genome growth. In Proceedings of the IEEE World Congress on Computational Intelligence, 1994, 182--187.

[2]

Bitterman, D. New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach. Master of Science Thesis, University of Georgia, Athens, Georgia, 2004.

[3]

Carlson, B. Rule coding for genetic algorithms: an alternative solution to the traveling salesman problem. In International Conference on Artificial Intelligence, Las Vegas, NV, June 2002, 878--883.

[4]

Diaz-Gomez, P. and Hougen, D. The snake in the box problem: mathematical conjecture and a genetic algorithm approach. In Genetic and Evolutionary Computation Conference, July 2006, 1409--1410.

Digital Library

[5]

Hart, E. and Ross, P. A heuristic combination method for solving job-shop scheduling problems. In Lecture Notes in Computer Science Volume 1498/1998, Parallel Problem Solving from Nature V (PPSN V), Springer Berlin/Heidelberg, 1998, 845--854.

Digital Library

[6]

Holland, J. H. Adaptation in Natural and Artificial Systems. Ann Arbor, University of Michigan Press, 1975.

Digital Library

[7]

Jung, S. and Moon, B. Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP. IEEE Transactions on Evolutionary Computation, 6, 6 (Dec 2002), 557--565.

Digital Library

[8]

Kauffman, S. A. Adaptation on Rugged Fitness Landscapes. In Lectures in the Sciences of Complexity, (1989), (Stein, D., ed.), 527--618, Redwood City: Addison-Wesley. SFI Studies in the Sciences of Complexity, Lecture Volume I.

[9]

Kautz, W. Unit-distance error-checking codes. IRE Trans. Electronic Computers, 7 (1958), 179--180.

[10]

Kochut, K. Snake-in-the-Box Codes for Dimension 7. In Journal of Combinatorial Mathematics and Combinatorial Computations, 20 (1996), 175--185.

[11]

Livingston, M. and Stout, Q. Distributed resources in hypercube computers. In Proceedings 3rd Conference on Hypercube Concurrent Computers and Applications, ACM, (1988), 222--231.

Digital Library

[12]

Potter, W. UGA Snake-in-the-Box Page -- Records. Retrieved April 1, 2010 from http://www.ai.uga.edu/sib/records/.

[13]

Potter, W., Robinson, R., Miller, J., Kochut, K., and Redys, D. Using the genetic algorithm to find snake-in-the-box codes. In Proceedings of the 7th International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, (1994) 307--314.

Digital Library

[14]

Rajan, D. and Shende, A. Maximal and reversible snakes in hypercubes. 24th Annual Australasian Conference on Combinatorial Mathematics and Combinatorial Computation, 1999.

[15]

Tuohy, D., Potter, W., and Casella, D. Searching for snake-in-the-box codes with evolved pruning models. In Proceedings of the International Conference on Genetic and Evolutionary Methods (2007), 3--9.

Cited By

Hood SRecoskie DSawada JWong D(2015)Snakes, coils, and single-track circuit codes with spread $$k$$kJournal of Combinatorial Optimization10.1007/s10878-013-9630-z30:1(42-62)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s10878-013-9630-z
Östergård PPettersson V(2015)Exhaustive Search for Snake-in-the-Box CodesGraphs and Combinatorics10.1007/s00373-014-1423-331:4(1019-1028)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00373-014-1423-3
Meyerson SDrapela TWhiteside WPotter W(2015)Finding Longest Paths in HypercubesProceedings of the 28th International Conference on Current Approaches in Applied Artificial Intelligence - Volume 910110.1007/978-3-319-19066-2_3(23-32)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-19066-2_3
Show More Cited By

Index Terms

Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Backtracking

Recommendations

A Hyper-Heuristic Using GRASP with Path-Relinking: A Case Study of the Nurse Rostering Problem

The goal of hyper-heuristics is to design and choose heuristics to solve complex problems. The primary motivation behind the hyper-heuristics is to generalize the solving ability of the heuristics. In this paper, the authors propose a Hyper-heuristic ...
Heuristic Search for the Generalized Minimum Spanning Tree Problem

The generalized minimum spanning tree (GMST) problem occurs in telecommunications network planning, where a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. The problem is known to be NP-hard, ...
A Set-Covering-Based Heuristic Approach for Bin-Packing Problems

Several combinatorial optimization problems can be formulated as large set-covering problems. In this work, we use the set-covering formulation to obtain a general heuristic algorithm for this type of problem, and describe our implementation of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
185
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hood SRecoskie DSawada JWong D(2015)Snakes, coils, and single-track circuit codes with spread $$k$$kJournal of Combinatorial Optimization10.1007/s10878-013-9630-z30:1(42-62)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s10878-013-9630-z
Östergård PPettersson V(2015)Exhaustive Search for Snake-in-the-Box CodesGraphs and Combinatorics10.1007/s00373-014-1423-331:4(1019-1028)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00373-014-1423-3
Meyerson SDrapela TWhiteside WPotter W(2015)Finding Longest Paths in HypercubesProceedings of the 28th International Conference on Current Approaches in Applied Artificial Intelligence - Volume 910110.1007/978-3-319-19066-2_3(23-32)Online publication date: 10-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-19066-2_3
Ruiz KArnold D(2014)Search for maximal snake-in-the-box using new genetic algorithmProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598296(831-838)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598296
Meyerson SWhiteside WDrapela TPotter W(2014)Finding longest paths in hypercubes, snakes and coils2014 IEEE Symposium on Computational Intelligence for Engineering Solutions (CIES)10.1109/CIES.2014.7011838(103-109)Online publication date: Dec-2014
https://doi.org/10.1109/CIES.2014.7011838
Östergård PPettersson V(2014)On the maximum length of coil-in-the-box codes in dimension 8Discrete Applied Mathematics10.1016/j.dam.2014.07.010179:C(193-200)Online publication date: 31-Dec-2014
https://dl.acm.org/doi/10.1016/j.dam.2014.07.010
Kinny D(2012)Monte-Carlo Search for Snakes and CoilsMulti-disciplinary Trends in Artificial Intelligence10.1007/978-3-642-35455-7_25(271-283)Online publication date: 2012
https://doi.org/10.1007/978-3-642-35455-7_25

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten