A genetic algorithm tutorial
Statistics and ComputingPublished 1 June 1994
Darrell Whitley
Citations4,451
SJR quartileQ1
SJR score0.81
SNIP1.26
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This tutorial covers the canonical genetic algorithm as well as more experimental forms of genetic algorithms, including parallel island models and parallel cellular genetic algorithms.
Abstract
This tutorial covers the canonical genetic algorithm as well as more experimental forms of genetic algorithms, including parallel island models and parallel cellular genetic algorithms. The tutorial also illustrates genetic search by hyperplane sampling. The theoretical foundations of genetic algorithms are reviewed, include the schema theorem as well as recently developed exact models of the canonical genetic algorithm.
Keywords
Computer Science
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Genetic Algorithms in Search, Optimization and Machine Learning
17,773 Citations1988David E. Goldberg, David Robson
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
IEEE Transactions on Systems Man and CyberneticsOptimization of Control Parameters for Genetic Algorithms
2,831 Citations1986John J. Grefenstette
GA's are shown to be effective for both levels of the systems optimization problem and are applied to the second level task of identifying efficient GA's for a set of numerical optimization problems.
Foundations of genetic algorithmsA Comparative Analysis of Selection Schemes Used in Genetic Algorithms
2,400 Citations1991David E. Goldberg, Kalyanmoy Deb
A number of selection schemes commonly used in modern genetic algorithms are compared on the basis of solutions to deterministic difference or differential equations, verified through computer simulations to provide convenient approximate or exact solutions and useful convergence time and growth ratio estimates.
Foundations of genetic algorithmsReal-Coded Genetic Algorithms and Interval-Schemata
1,645 Citations1993Larry J. Eshelman, J. David Schaffer
It is shown how interval-schemata are analogous to Holland's symbol- schemata and provide a key to understanding the implicit parallelism of real-valued GAs and support the intuition that real-coded GAs should have an advantage over binary coded GAs in exploiting local continuities in function optimization.
international conference on Genetic algorithmsReducing bias and inefficiency in the selection algorithm
1,408 Citations1987James E. Baker
A sheet which is a blend of water-insoluble fibers and pieces of film of a dry material which converts to a gel quickly on contact with a large amount of water.
Deep Blue (University of Michigan)An Analysis Of The Behavior Of A Class Of Genetic Adaptive Systems.
1,299 Citations1975Kenneth DeJong
ACM SIGART BulletinBook review: Genetic Algorithms + Data Structures = Evolution Programs by Zbigniew Michalewicz (Springer-Verlag, 1992)
1,091 Citations1993Michael de la Maza
Foundations of genetic algorithmsGenetic Algorithms for Real Parameter Optimization
989 Citations1991Alden H. Wright
It is shown that k-point crossover can be viewed as a crossover operation on the vector of parameters plus perturbations of some of the parameters, which suggests a genetic algorithm that uses real parameter vectors as chromosomes, real parameters as genes, and real numbers as alleles.
Physica D Nonlinear PhenomenaCo-evolving parasites improve simulated evolution as an optimization procedure
775 Citations1990W. Daniel Hillis
An example of how simulated evolution can be applied to a practical optimization problem and more specifically, how the addition of co-evolving parasites can improve the procedure by preventing the system from sticking at local maxima is shown.
A Survey of Evolution Strategies.
746 Citations1991Thomas Bäck, Frank Hoffmeister +1 more
Evolution Strategies are algorithms which imitate the principles of natural evolution as a method to solve parameter optimization problems and adaptation of the strategy parameters for the mutation variances as well as their covariances are described.
Kluwer international series in engineering and computer scienceA Connectionist Machine for Genetic Hillclimbing
717 Citations1987David H. Ackley
This dissertation focuses on the development of a heuristic search algorithm that automates the very labor-intensive and therefore time-heavy and expensive process of manually cataloging discrete-time components of a genealogy tree.
Foundations of genetic algorithmsA Study of Reproduction in Generational and Steady-State Genetic Algorithms
657 Citations1991Gilbert Syswerda
It is shown that while each techniques of population control can be made similar with respect to the schema theorem, in practice their behavior is quite different.
Annals of Mathematics and Artificial IntelligenceModeling genetic algorithms with Markov chains
446 Citations1992Allen E. Nix, Michael D. Vose
A simple genetic algorithm as a Markov chain is model, both complete and exact, which considers the asymptotics of the steady state distributions as population size increases.
Fraunhofer-Publica (Fraunhofer-Gesellschaft)How Genetic Algorithms Really Work: Mutation and Hillclimbing.
369 Citations1992Heinz Mühlenbein
The invention relates to the production of washing powders of stabilized or enhanced appearance which contain a fluorescent whitening agent of the formula or of the formulas wherein R1 is hydrogen or chlorine, and M is hydrogen, an alkali metal or ammonium ion.
Machine LearningGenetic algorithms in noisy environments
333 Citations1988J. Michael Fitzpatrick, John J. Grefenstette
This work explores in detail the tradeoffs between the amount of effort spent on evaluating each structure and the number of structures evaluated during a given iteration of the genetic algorithm.
Foundations of genetic algorithmsEvolution in Time and Space – The Parallel Genetic Algorithm
326 Citations1991Heinz Mühlenbein
This work investigates the PGA with deceptive problems and the traveling salesman problem, a parallel search with information exchange between the individuals, and shows the correlation for thetraveling salesman problem by a configuration space analysis.
Journal of Experimental & Theoretical Artificial IntelligenceGENITOR II: a distributed genetic algorithm
274 Citations1990Darrell Whitley, Timothy Starkweather
A distributed version of GENITOR which uses many smaller distributed populations in place of a single large population is introduced, and is able to optimize a broad range of sample problems more accurately and more consistently than GENITor with a single population.
Foundations of genetic algorithmsFundamental Principles of Deception in Genetic Search
241 Citations1991L. Darrell Whitley
Several theorems concerning the nature of deception and the central role that deception plays in function optimization using genetic algorithms are presented and different methods of dealing with deception and poor linkage during genetic search are presented.
Selection in Massively Parallel Genetic Algorithms.
234 Citations1991Robert J. Collins, David Jefferson
This paper characterize the difference between panmictic and local selection/mating schemes in terms of diversity of alleles, diversity of genotypes, the inbreeding, and the speed and robustness of the genetic algorithm.
Foundations of genetic algorithmsAn Analysis of Multi-Point Crossover
221 Citations1991William M. Spears, Kenneth De Jong
This analysis extends the work from De Jong's thesis, which dealt with disruption of n-point crossover on 2nd order hyperplanes, to present various extensions to this theory, including an analysis of the disruption of kth order hyperplane crossover.
Lecture notes in computer scienceOptimization using distributed genetic algorithms
181 Citations2006Timothy Starkweather, Darrell Whitley +1 more
Data collected concerning execution times show that the GENITOR genetic algorithm using multiple subpopulations may execute much faster than the single population version when the cost of the evaluation function is low; thus, total number of evaluations is not always a good metric for making performance comparisons.
Foundations of genetic algorithmsDeception Considered Harmful* *With apologies to Edsger Dijkstra (Dijkstra, 1968).
135 Citations1993John J. Grefenstette
It is argued that the characterization of hard problems must take into account the basic features of genetic algorithms, especially their dynamic, biased sampling strategy, such as the static average fitness of competing schemas.
Foundations of genetic algorithmsAn Executable Model of a Simple Genetic Algorithm
126 Citations1993Darrell Whitley
A set of executable equations are defined which model the ideal behavior of a simple genetic algorithm, which assume an infinitely large population and require the enumeration of all points in the search space.
Lecture notes in computer scienceExplicit parallelism of genetic algorithms through population structures
101 Citations2006M. Gorges-Schleuter
This paper specifies an algorithm which uses only local rules and local data making it massively parallel with an observed linear speedup on a transputer-based parallel system, and shows that both convergence speed and final quality are improved in comparison to a genetic algorithm without population structure.
Biological CyberneticsAn analysis of a reordering operator on a GA-hard problem
52 Citations1990David E. Goldberg, Clayton L. Bridges
This paper analyzes the performance of a genetic algorithm that combines reproduction, crossover, and a reordering operator to confirm this role and suggest directions for further research.
Lecture notes in computer scienceThe theory of virtual alphabets
36 Citations2006David E. Goldberg
A theory of convergence for real-coded genetic algorithms—GAs that use floating-point or other high-cardinality codings in their chromosomes—is presented, which postulates that selection dominates early GA performance and restricts subsequent search to intervals with above-average function value dimension by dimension.
Annals of Mathematics and Artificial IntelligenceTracking primary hyperplane competitors during genetic search
15 Citations1992Darrell Whitley, Rajarshi Das +1 more
Holland's fundamental theorem of genetic algorithms (the “schema theorem”) provides a lower bound on the sampling rate of a single hyperplane during genetic search, but its notion of “implicit parallelism” does not universally hold when conflicting hyperplanes interact.