Overview

Estimation of Distribution algorithms:

• Real-Coded Extended Compact Genetic Algorithm (rECGA) [1]

• Real-Coded Bayesian Optimization Algorithm (rBOA) [2]

Estimation of Distribution Algorithms

1. Evaluate population

2. Select good candidates

3. Build a probabilistic model

4. Generate new candidates from model

[1]

rECGA Model Building

1. Combine pairs of distributions

2. Keep the model that reduces complexity while maintaining accuracy

[1]

rECGA Model Building

3. Repeat until it stops working (greedy search)

[1]

rECGA Model Parameters

4. Cluster individuals to form mixtures of Gaussians

[1]

rBOA Model Building

1. Bayesian factorization

[2]

rBOA Model Building

2. Find maximal connected subgraphs

[2]

rBOA Model Parameters

3. Cluster individuals to form mixtures of Gaussians

[1]

What did I just say?

rECGA

• Model building: simple, greedy algorithm
• Model parameters: clustering / mixtures of Gaussians

rBOA

• Model building: Bayesian factorization graph
• Model parameters: clustering / mixtures of Gaussians

Bibliography

[1] P.L. Lanzi, L. Nichetti, K. Sastry, D. Voltini, and D.E. Goldberg, “Real-Coded Extended Compact Genetic Algorithm Based on Mixtures of Models,” Studies in Computational Intelligence, vol. 157, 2008, pp. 335–358.

[2] C. Ahn, R. Ramakrishna, and D. Goldberg, “Real-Coded Bayesian Optimization Algorithm: …,” Lecture Notes in Computer Science, 2004, pp. 840–851.