research-article

CrossNet: a framework for crossover with network-based chromosomal representations

Authors:

Forrest Stonedahl,

Uri WilenskyAuthors Info & Claims

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

Pages 1057 - 1064

https://doi.org/10.1145/1389095.1389290

Published: 12 July 2008 Publication History

Abstract

We propose a new class of crossover operators for genetic algorithms (CrossNet) which use a network-based (or graph-based) chromosomal representation. We designed CrossNet with the intent of providing a framework for creating crossover operators that take advantage of domain-specific knowledge for solving problems. Specifically, GA users supply a network which defines the epistatic relationships between genes in the genotype. CrossNet-based crossover uses this information with the goal of improving linkage. We performed two experiments that compared CrossNet-based crossover with one-point and uniform crossover. The first experiment involved the density classification problem for cellular automata (CA), and the second experiment involved fitting two randomly generated hyperplane-defined functions (hdf's). Both of these exploratory experiments support the hypothesis that CrossNet-based crossover can be useful, although performance improvements were modest. We discuss the results and remain hopeful about the successful application of CrossNet to other domains. We conjecture that future work with the CrossNet framework will provide a useful new perspective for investigating linkage and chromosomal representations.

References

[1]

Chen, Y.-P., Yu, T.-L., Sastry, K., and Goldberg, D. E. A survey of linkage learning techniques in genetic and evolutionary algorithms. Tech. Rep. 2007014, Illinois Genetic Algorithms Laboratory, Urbana, Illinois, 2007.

[2]

DeJong, K., and Spears, W. An analysis of the interacting roles of population-size and crossover in genetic algorithms. In Lecture Notes in Computer Science (1991), vol. 496, p. 38.

[3]

De Jong, K., and Spears, W. A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematics and Artificial Intelligence 5, 1 (1992), 1--26.

[4]

Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics 2, 1 (1996), 5--30.

[5]

Goldberg, D., and Lingle Jr, R. Alleles, loci, and the traveling salesman problem. Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications (1985), 154--159.

Digital Library

[6]

Greene, W. A. A genetic algorithm with self-distancing bits but no overt linkage. In Proceedings of GECCO '02 (2002), pp. 367--374.

Digital Library

[7]

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

Digital Library

[8]

Holland, J. H. Building blocks, cohort genetic algorithms, and hyperplane-defined functions. Evolutionary Computation 8, 4 (2000), 373--391.

Digital Library

[9]

Land, M., and Belew, R. No perfect two-state cellular automata for density classification exists. Physical Review Letters 74, 25 (1995), 5148--50.

[10]

Mitchell, M., Crutchfield, J. P., and Hraber, P. T. Evolving cellular automata to perform computations: mechanisms and impediments. In Proceedings of the Oji international seminar on complex systems : from complex dynamical systems to sciences of artificial reality (New York, NY, USA, 1994), Elsevier North-Holland, Inc., pp. 361--391.

Digital Library

[11]

Moon, B., Lee, Y., and Kim, C. GEORG: VLSI circuit partitioner with a new genetic algorithm framework. Journal of Intelligent Manufacturing 9, 5 (1998), 401--412.

[12]

Pelikan, M., Goldberg, D., and Cantu-Paz, E. BOA: The Bayesian optimization algorithm. In Proceedings of GECCO '99 (1999), vol. 1, pp. 525--532.

[13]

Pereira, F. B., Machado, P., Costa, E., and Cardoso, A. Graph based crossover - a case study with the busy beaver problem. In Proceedings of GECCO '99 (13-17 1999), vol. 2, pp. 1149--1155.

[14]

Rand, W., and Riolo, R. Shaky ladders, hyperplane-defined functions and genetic algorithms: Systematic controlled observation in dynamic environments. In Applications of Evolutionary Comp., Evoworkshops (2005), F. Rothlauf et al., Eds., vol. 3449 of Lecture Notes In Comp. Sci., Springer.

Digital Library

[15]

Seo, D., and Moon, B. Voronoi quantized crossover for traveling salesman problem. In Proceedings of GECCO '02 (2002), pp. 544--552.

Digital Library

[16]

Seo, D., and Moon, B. A survey on chromosomal structures and operators for exploiting topological linkages of genes. In Proceedings of GECCO '03 (2003), vol. 1, pp. 1357--1368.

Digital Library

[17]

Stanley, K. O., and Miikkulainen, R. Efficient reinforcement learning through evolving neural network topologies. In Proceedings of GECCO '02 (2002), pp. 569--577.

Digital Library

[18]

Verel, S., Collard, P., Tomassini, M., and Vanneschi, L. Fitness landscape of the cellular automata majority problem: View from the "Olympus". Theoretical Computer Science 378, 1 (2007), 54--77.

Digital Library

[19]

Watts, D., and Strogatz, S. Collective dynamics of 'small-world' networks. Nature 393, 6684 (1998), 409--10.

[20]

Werfel, J., Mitchell, M., and Crutchfield, J. P. Resource sharing and coevolution in evolving cellular automata. IEEE-EC 4, 4 (Nov. 2000), 388.

Digital Library

[21]

Wilensky, U. NetLogo. Center for Connected Learning and Computer-based Modeling, Northwestern University, Evanston, IL, 1999.

Cited By

Jiang MLee THsu W(2013)The Left and Right Context of a WordACM Transactions on Asian Language Information Processing10.1145/2425327.242532912:1(1-23)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2425327.2425329
Pelikan MHauschild MMoore J(2012)Distance-based bias in model-directed optimization of additively decomposable problemsProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330203(273-280)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330203
Azzini ATettamanzi ADragoni M(2011)SimBa-2: Improving a novel similarity-based crossover for the evolution of artificial neural networks2011 11th International Conference on Intelligent Systems Design and Applications10.1109/ISDA.2011.6121684(374-379)Online publication date: Nov-2011
https://doi.org/10.1109/ISDA.2011.6121684
Show More Cited By

Index Terms

CrossNet: a framework for crossover with network-based chromosomal representations
1. Computing methodologies
  1. Artificial intelligence

Recommendations

Network structure optimization: genetic operators: mutation and crossover
ICUIMC '13: Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication

Genetic algorithms are applicable solution for network structure optimization. It lets us obtain good results within acceptable periods of time. In this paper we present several ways of using such genetic operators as mutation and crossover for solving ...
Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process

Traditional genetic algorithms use only one crossover and one mutation operator to generate the next generation. The chosen crossover and mutation operators are critical to the success of genetic algorithms. Different crossover or mutation operators, ...
Positional Bias Does Not Influence Cartesian Genetic Programming with Crossover
Parallel Problem Solving from Nature – PPSN XVIII
Abstract
The recombination operator plays an important role in many evolutionary algorithms. However, in Cartesian Genetic Programming (CGP), which is part of the aforementioned category, the usefulness of crossover is contested. In this work, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
170
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang MLee THsu W(2013)The Left and Right Context of a WordACM Transactions on Asian Language Information Processing10.1145/2425327.242532912:1(1-23)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2425327.2425329
Pelikan MHauschild MMoore J(2012)Distance-based bias in model-directed optimization of additively decomposable problemsProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330203(273-280)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330203
Azzini ATettamanzi ADragoni M(2011)SimBa-2: Improving a novel similarity-based crossover for the evolution of artificial neural networks2011 11th International Conference on Intelligent Systems Design and Applications10.1109/ISDA.2011.6121684(374-379)Online publication date: Nov-2011
https://doi.org/10.1109/ISDA.2011.6121684
Hauschild MPelikan M(2010)Performance of network crossover on NK landscapes and spin glassesProceedings of the 11th international conference on Parallel problem solving from nature: Part II10.5555/1887255.1887306(462-471)Online publication date: 11-Sep-2010
https://dl.acm.org/doi/10.5555/1887255.1887306
Thierens D(2010)The linkage tree genetic algorithmProceedings of the 11th international conference on Parallel problem solving from nature: Part I10.5555/1885031.1885060(264-273)Online publication date: 11-Sep-2010
https://dl.acm.org/doi/10.5555/1885031.1885060
Hauschild MPelikan MPelikan MBranke J(2010)Network crossover performance on NK landscapes and deceptive problemsProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830612(713-720)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830612
Hauschild MPelikan M(2010)Performance of Network Crossover on NK Landscapes and Spin GlassesParallel Problem Solving from Nature, PPSN XI10.1007/978-3-642-15871-1_47(462-471)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15871-1_47
Thierens D(2010)The Linkage Tree Genetic AlgorithmParallel Problem Solving from Nature, PPSN XI10.1007/978-3-642-15844-5_27(264-273)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15844-5_27
Huang YChen YRothlauf F(2009)On the detection of general problem structures by using inductive linkage identificationProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570200(1853-1854)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570200

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.

Media

Figures

Other

Tables

View Table of Contents