Overview

• Parallel Genetic Algorithms

• Attempted Linkage Learning

Parallel Genetic Algorithms

• Master/Slave parallelism [1]

• Master: perform selection, cross over, mutation

• Slaves: only evaluate fitness

My implementations

Parallel Python library

• running on multiple lab workstations

• problems deploying native libraries (BLAS)

Scala Actors Library

• currently trying it out

Parallel NEAT

NeuroEvolution of Augmenting Topologies

Compositional Pattern Producing Network

CPPNs

Compositional Pattern Producing Networks

Compositional Pattern Producing Network result

Reproduced existing results

2-D pole balancing using Enforced Subpopulations (ESP) [2]

• Network structure not well described in that paper

• Had to try many different variations before matching results

• Some variations performed better than those reported in the paper

Random search for linkage

• 55 different weights in 2-D pole balancing problem

• combinatorial explosion: 55! \approx 1.3 × 10^{73}

• Tried just a few combinations a generation hoping to find a partial solution

• Performance was worse

Future work

• Implement Extended Compact Genetic Algorithm (ECGA)[3] as described

• Modify ECGA for real value strings (instead of bit strings)

• Parallelize ECGA

• Learn linkage in 2-D pole balancing problem

• Learn linkage in finless rocket guidance problem

Bibliography

[1] E. Cantú-Paz, “A survey of parallel genetic algorithms,” Calculateurs Paralleles, Reseaux et Systems Repartis, vol. 10, 1998, p. 141–171.

[2] F. Gomez and R. Miikkulainen, “2-D pole balancing with recurrent evolutionary networks,” ICANN, 1998, p. 758–763.

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