Compact genetic algorithm

Compact genetic algorithm

The information processing objective of the compact genetic algorithm is to simulate the behavior of a genetic algorithm with a much smaller memory footprint (without requiring the maintenance of a population). This is achieved by maintaining a vector that specifies the probability of including each component in a solution in new candidate solutions. The candidate solutions are probabilistically generated from the vector, and the components of the best 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 that each component will be expressed in a candidate solution. The following algorithm provides a pseudocode of the compact genetic algorithm to maximize a cost function. The parameter n indicates the number of probabilities of updating the conflicting bits at each iteration.

compact genetic algorithm

The vector update parameter (n) influences the quantity of probability updates at each iteration of the algorithm. The vector update parameter (n) can be considered comparable to the population size parameter in the genetic algorithm. The first results demonstrate that cGA can be compared to a standard genetic algorithm on classical binary string optimization problems (such as OneMax). The algorithm can be considered to have converged if the vector probabilities are all equal to 0 or 1.

To share
%d bloggers like this: