Compact genetic algorithm
The information processing purpose of thegenetic algorithm compact is to simulate the behavior of a algorithm genetics with a much smaller memory footprint (without requiring 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. 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 is 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.
The vector update parameter (n) influences the amount of updates of the probabilities 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 ones results demonstrate that cGA can be comparable 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.