Compact Genetic Algorithm

The information processing objective of the algorithm is to simulate the behavior of a Genetic Algorithm with a much smaller memory footprint (without requiring a population to be maintained). This is achieved by maintaining a vector that specifies the probability of including each component in a solution in new candidate solutions. Candidate solutions are probabilistically generated from the vector and the components in the better solution are used to make small changes to the probabilities in the vector.

The Compact Genetic Algorithm maintains a real-valued prototype vector that represents the probability of each component being expressed in a candidate solution. The following algorithm provides a pseudocode listing of the Compact Genetic Algorithm for maximizing a cost function. The parameter n indicates the amount to update probabilities for conflicting bits in each algorithm iteration.

The vector update parameter (n) influences the amount that the probabilities are updated each algorithm iteration. The vector update parameter (n) may be considered to be comparable to the population size parameter in the Genetic Algorithm. Early results demonstrate that the cGA may be comparable to a standard Genetic Algorithm on classical binary string optimization problems (such as OneMax). The algorithm may be considered to have converged if the vector probabilities are all either 0 or 1.