A genetic algorithm searches with a population instead of a single candidate. Each candidate is encoded as a string, classically a string of bits, and the population is improved one generation at a time. Selection gives better candidates more offspring. Crossover builds each offspring from pieces of two parents, and mutation changes a few positions at random. John Holland developed the method in the 1960s and 1970s as a model of adaptation, and David Goldberg's 1989 textbook made it the best-known evolutionary algorithm. Since then genetic algorithms have been applied to scheduling, design, routing, and parameter tuning, often with representations far from Holland's bit strings.
A population changes what search can do. Hill climbing keeps one candidate and stops at the first local optimum it reaches. A population can hold candidates in several regions of the search space at once, and crossover can combine good parts found by different candidates. Both advantages are conditional. Selection that is too strong collapses the population onto one region before it has explored, and crossover helps only when the encoding places related parts of a solution near each other and the problem can be solved by combining parts. Most of this topic is about those conditions: how the encoding shapes the search, how selection pressure is controlled, which operators suit which representations, what the schema theorem does and does not explain, and how constraints are handled. Two articles apply the method to the course's assignments, a binary genetic algorithm on De Jong's test functions and a genetic algorithm for bin packing, and test the original results with repeated runs.
Articles
The algorithm
- The simple genetic algorithm: Holland's and Goldberg's canonical algorithm, with fitness-proportional selection, one-point crossover, bit-flip mutation, and generational replacement, worked through on a small problem.
- Binary encoding and Gray codes: mapping real numbers to bit strings, precision and decoding, Hamming cliffs, Gray codes, and real-valued representations.
Operators and selection
- Selection pressure and premature convergence: roulette, stochastic universal sampling, ranking, and tournament selection; takeover time; elitism; and niching methods that preserve diversity.
- Crossover and mutation operators: binary, real-coded, and permutation operators, from one-point and uniform crossover to BLX-α, simulated binary crossover, PMX, order and cycle crossover, with an interactive demo of the permutation operators and an experiment on the mutation rate.
Theory and constraints
- Holland's schema theorem: schemata, the schema theorem and the building block hypothesis, and why later theory found them incomplete.
- Constraint handling in evolutionary algorithms: penalty functions, Deb's feasibility rules, stochastic ranking, repair and decoders, with penalties and Deb's rules compared on a standard constrained problem.
From my course work
- A binary GA on De Jong's test functions: the course's second assignment, De Jong's original function definitions alongside the assignment's versions, and the single-run results repeated over 30 seeds.
- A genetic algorithm for bin packing: the course's third assignment extended with a lower bound, First Fit Decreasing, thirty seeds on fixed instances, and a permutation encoding with a first-fit decoder.
Related topics
Genetic algorithms extend the single-candidate search of local search, and their behavior depends on the fitness landscape their encoding and operators induce. Multi-objective optimization adapts selection to several objectives at once. Genetic programming applies the same loop to programs, and evolution strategies take a different route to real-valued optimization, adapting the mutation distribution itself.
References
- Eiben, A. E., and Smith, J. E. (2015). Introduction to Evolutionary Computing, 2nd ed. Springer.
- Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
- Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.