Cited By
View all- Rada RDu J(2014)Knowledge in Memetic Algorithms for Stock ClassificationInternational Journal of Artificial Life Research10.4018/ijalr.20140101024:1(13-29)Online publication date: 1-Jan-2014
Crossover: the divine afflatus in search
Pages 2497 - 2502
Abstract
The traditional GA theory is pillared on the Building Block Hypothesis (BBH) which states that Genetic Algorithms (GAs) work by discovering, emphasizing and recombining low order schemata in high-quality strings, in a strongly parallel manner. Historically, attempts to capture the topological fitness landscape features which exemplify this intuitively straight-forward process, have been mostly unsuccessful. Population-based recombinative methods had been repeatedly outperformed on the special designed abstract test suites, by different variants of mutation-based algorithms. Departing from the BBH, in this paper we seek to exemplify the utility of crossover from a different point of view, emphasizing the creative potential of the crossover operator. We design a special class of abstract test suites, called Trident functions, which exploits the ability of modern GAs to mix good but significantly different solutions. This approach has been so far neglected as it is widely believed that disruption caused by mating individuals that are too dissimilar is harmful. We anticipate that hybridizing different designs induces a complex neighborhood structure unattainable by trajectory-based methods which can conceal novel solutions. Empirical results confirm that the proposed class of problems can be solved efficiently only by population-based panmictic recombinative methods, employing diversity maintaining mechanisms.
References
[1]
S. Chen. Is the Common Good? A New Perspective Developed in Genetic Algorithms. PhD thesis, Robotics Institute, Carnegie Mellon University, 1999.
[2]
S. Forrest and M. Mitchell. What makes a problem hard for a genetic algorithm? some anomalous results and their explanation. MACHLEARN: Machine Learning, 13, 1993.
[3]
D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989.
[4]
D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002.
[5]
D. E. Goldberg, K. Sastry, and X. Llora. Toward routine billion-variable optimization using genetic algorithms: Short communication. Complex., 12(3):27--29, 2007.
[6]
G. R. Harik and D. E. Goldberg. Learning linkage. In R. K. Belew and M. D. Vose, editors, FOGA, pages 247--262. Morgan Kaufmann, 1996.
[7]
J. H. Holland. Adaptation in natural artificial systems. University of Michigan Press, Ann Arbor, 1975.
[8]
J. Horn and D. E. Goldberg. Genetic algorithm difficulty and the modality of fitness landscapes. In L. D. Whitley and M. D. Vose, editors, FOGA, pages 243--269. Morgan Kaufmann, 1994.
[9]
D. Iclanzan and D. Dumitrescu. Overcoming Hierarchical Difficulty by Hill-Climbing the Building Block Structure. In GECCO '07: Proc. of the Genetic and Evolutionary Computation Conference, July 2007. (accepted).
[10]
T. Jones. Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, University of New Mexico, Albuquerque, NM, 1995.
[11]
H. Kargupta. Gene expression: The missing link in evolutionary computation. In Genetic Algorithms in Engineering and Computer Science, pages 159--160, Las Vegas, Nevada, USA, 8 July 2000.
[12]
P. Larranaga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, Norwell, MA, USA, 2001.
[13]
S. W. Mahfoud. Niching methods for genetic algorithms. PhD thesis, Dept. General Engineering, University of Illinois, Urbana, Illinois, 1995. Also, IlliGAL Report No. 95001.
[14]
M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer Verlag, 2005.
[15]
M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. In L. S. et al., editor, GECCO '01: Proc. of the Genetic and Evolutionary Computation Conference, pages 511--518, San Francisco, California, USA, 7-11 2001. Morgan Kaufmann.
[16]
M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In W. B. et al., editor, GECCO '99: Proceedings of the Genetic and Evolutionary Computation Conference, volume I, pages 525--532, Orlando, FL, 13-17 July 1999. Morgan Kaufmann Publishers, San Fransisco, CA.
[17]
K. Sastry and D. E. Goldberg. Let's get ready to rumble: Crossover versus mutation head to head. In GECCO '04: Proc. of the Genetic and Evolutionary Computation Conference, Seattle, WA, USA, pages 126--137. Springer, LNCS, vol. 3103, June 26-30, 2004.
[18]
R. Shipman, M. Shackleton, and I. Harvey. The use of neutral genotype-phenotype mappings for improved evolutionary search. BT Technology Journal, 18(4):103--111, 2000.
[19]
T. Starkweather, K. Mathias, and D. Whitley. Optimization using distributed genetic algorithms. In Proceedings of the First International Conference on Parallel Problem Solving from Nature, pages 176--186. Springer, 1991.
[20]
G. Syswerda. Uniform crossover in genetic algorithms. In Proceedings of Third International Conference on Genetic Algorithms, 1989.
[21]
Watson, Beck, Howe, and Whitley. Problem difficulty for tabu search in job-shop scheduling. AIJ: Artificial Intelligence, 143, 2003.
[22]
R. A. Watson, G. Hornby, and J. B. Pollack. Modeling building-block interdependency. In PPSN V: Proc. of the 5th International Conference on Parallel Problem Solving from Nature, pages 97--108, London, UK, 1998. Springer, LNCS.
[23]
T.-L. Yu and D. E. Goldberg. Conquering hierarchical difficulty by explicit chunking: substructural chromosome compression. In GECCO '06: Proc. of the Genetic and Evolutionary Computation Conference, pages 1385--1392, NY, USA, 2006. ACM Press.
Index Terms
- Crossover: the divine afflatus in search
Recommendations
Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlap
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationThis paper presents a class of NK landscapes with nearest-neighbor interactions and tunable overlap. The considered class of NK landscapes is solvable in polynomial time using dynamic programming; this allows us to generate a large number of random ...
The creativity potential within evolutionary algorithms
ECAL'07: Proceedings of the 9th European conference on Advances in artificial lifeThe traditional GA theory is pillared on the Building Block Hypothesis (BBH) which states that Genetic Algorithms (GAs) work by discovering, emphasizing and recombining low order schemata in high-quality strings, in a strongly parallel manner. ...
Differential evolution using a superior---inferior crossover scheme
Differential evolution (DE) is a new population-based stochastic optimization, which has difficulties in solving large-scale and multimodal optimization problems. The reason is that the population diversity decreases rapidly, which leads to the failure ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2007
1450 pages
Copyright © 2007 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: 07 July 2007
Check for updates
Author Tags
Qualifiers
- Article
Conference
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 174Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
Cited By
View all- Rada RDu J(2014)Knowledge in Memetic Algorithms for Stock ClassificationInternational Journal of Artificial Life Research10.4018/ijalr.20140101024:1(13-29)Online publication date: 1-Jan-2014
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in