Coevolutionary Algorithms

Cooperation and competition between populations of organisms in nature has inspired researchers to incorporate coevolutionary dynamics into genetic algorithms. The common element in these approaches is the inclusion of one or more additional populations. A growing body of research explores coevolutionary approaches that capitalize on this dynamic quality.

We have implemented a coevolutionary genetic algorithm (CGA) based on an algorithm used in previous evolvable hardware applications, and one that is based on competition between two populations. The population of candidate solutions, or trial population, is represented and manipulated much the same as the main population in a standard genetic algorithm. The second population, or target population, consists of target objective vectors (TOVs), vectors containing targets for the individual objectives to be optimized.

Overview of the CGA. Individuals in the trial population are compared to individuals in the target population in order to evaulate relative fitness.

The population of TOVs is used to encapsulate the level of difficulty that the trial population faces. Under the control of the genetic algorithm, the TOVs evolve from easy to difficult based on the level of proficiency of the trial population. The algorithm designer need only specify two TOVs: an easy TOV and a difficult TOV, the latter being the ultimate goal of the run (analogous to stopping criteria in standard evolutionary algorithms).

Empirical results using a suite of two-objective test functions indicate that the CGA performs well at finding solutions on convex, nonconvex, discrete, and deceptive Pareto-optimal fronts, while giving respectable results on a nonuniform optimization. On a multimodal Pareto front, the CGA yields poor coverage across the Pareto front, yet is successful at finding the solution that dominates all the solutions produced by other multiobjective algorithms.