Two ideas share this topic because both change what a population is. The first is practical. Evaluating fitness is usually the expensive part of an evolutionary algorithm, and the evaluations in one generation are independent, so they can run in parallel. A master process can farm them out to workers without changing the algorithm at all. Splitting the population itself into islands that evolve separately and occasionally exchange migrants is a different matter. It changes the algorithm's behavior, often for the better, because the islands explore different regions before migration mixes their discoveries.
The second idea is coevolution, in which an individual's fitness depends on other evolving individuals rather than on a fixed function. In competitive coevolution, solutions are scored against opponents that are themselves improving, as when sorting networks were evolved against populations of hard test cases, or game strategies against each other. In cooperative coevolution, a problem is split into parts, each evolved by its own population and scored by how well it works with the others. Both can find solutions that a fixed fitness function would not have rewarded, and both bring problems of their own. When fitness is relative, a population can run hard and stay in place, cycle through strategies without improving, or lose the gradient entirely. Biology calls the first situation the Red Queen effect, after the Red Queen's race in Through the Looking-Glass. Measuring real progress under those conditions takes its own methods.
Articles
Parallel evolution
- Master-slave parallel evaluation: distributing fitness evaluations to workers, the model of the optimal number of workers and the speedup it predicts, measured against a real multi-core run, and asynchronous designs for uneven evaluation times.
- Island model genetic algorithms: subpopulations, migration rate, interval, and topology, cellular evolutionary algorithms, and their effects on diversity and takeover time, compared on Rastrigin and a deceptive function.
Coevolution
- Competitive coevolution: relative fitness, Hillis's host-parasite sorting networks, game strategies, and the evaluation designs and archives used to keep competition productive.
- Cooperative coevolution: decomposing a problem into coevolving species, choosing collaborators, relative overgeneralization, and grouping variables for large-scale optimization.
- Red Queen dynamics in coevolution: cycling, disengagement, forgetting, and mediocre stable states; Lotka-Volterra as an analogy; and the CIAO, master, and dominance tournaments used to measure progress.
Related topics
Island models are one of the diversity-preserving methods discussed with selection pressure in genetic algorithms. Cooperative coevolution is the principle behind the subpopulation methods of neuroevolution, and the course's final project coevolved robot bodies with their controllers. Pareto coevolution borrows its comparisons from multi-objective optimization.
References
- Cantú-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms. Kluwer.
- Popovici, E., Bucci, A., Wiegand, R. P., and de Jong, E. D. (2012). Coevolutionary principles. In G. Rozenberg, T. Bäck, and J. N. Kok (eds.), Handbook of Natural Computing, 987–1033. Springer.