The Compact and Extended Compact GA

by J.D. Marble on February 1, 2010

Overview

Not a computer display standard!

  • Compact Genetic Algorithm (CGA)

  • Extended Compact Genetic Algorithm (ECGA)

Compact Genetic Algorithm

  • Represents the population as a probability distribution (multiple, independent Bernoulli distributions)

  • Less memory used than GA

  • Less bandwidth used in master/slave parallel implementation

  • “Operationally equivalent to the order-one behavior of the simple GA with uniform crossover”

cGA Algorithm

  1. Initialize probability vector

p \leftarrow \langle 0.5, 0.5, \cdots, 0.5 \rangle

  1. Generate two individuals from the vector

a \leftarrow generate(p)

b \leftarrow generate(p)

  1. Let them compete

winner \leftarrow evaulate(a, b)

  1. Update the probability vector towards the better one

p \leftarrow p + (2 winner - 1)/n

  1. Repeat from step 2 until converged

Extended Compact Genetic Algorithm

  • Like cGA, represents the population as a probability distribution

  • “The choice of a good distribution is equivalent to linkage learning.”

  • “…simpler distributions are better than complex ones.” (Occam’s Razor)

Marginal Product Model (MPM)

  • Example:
bits 0,3pbit 1pbit 2p
00 0.50 0.50 0.5
01 0.01 0.51 0.5
10 0.0
11 0.5

ECGA Algorithm

  1. Generate a random population

  2. Undergo tournament selection

  3. Model the population using a greedy MPM search

  4. Generate a new population using the given model

  5. Repeat until converged

ECGA Algorithm

ECGA Algorithm Flowchart

ECGA Algorithm Flowchart

Future work

  • Study existing implementations of real-coded ECGAs

  • Find modularity in the model

  • Apply to 2-D pole balancing and finless rocket guidance problems

  • ???

  • Profit!

Bibliography

[1] G. Harik, “The compact genetic algorithm,” IEEE Transactions on Evolutionary Computation, vol. 9, 1999, pp. 38–297.

[2] G. Harik, “Linkage learning via probabilistic modeling in the ECGA,” Urbana, IL: University of Illinois at Urbana-Champaign, 1999.

[3] K. Sastry and D.E. Goldberg, “On Extended Compact Genetic Algorithm,” Urbana, IL: University of Illinois at Urbana-Champaign, 2000.