Population-based incremental learning

In machine learning and soft computing, population-based incremental learning (PBIL) is a type of genetic algorithm where the genotype of an entire population is evolved rather than individual members. This is one of the Estimation of Distribution Algorithm. The algorithm is proposed by Shumeet Baluja in 1994.

Genotype representation

In PBIL, genes are represented as real values in the range [0,1], indicating the probability that any particular allele appears in that gene.

Algorithm

The PBIL algorithm is as follows:

1. A population is generated.
2. The fitness of each member is evaluated and ranked.
3. Update population genotype based on fittest individual.
4. Repeat steps 2-3

Source code

This is a part of source code implemented in Java. In the paper, learnRate = 0.1, negLearnRate = 0.075, mutProb = 0.02, and mutShift = 0.05 is used.

public void optimize() {
    final int totalBits = getTotalBits(domains);
    final double[] probVec = new double[totalBits];
    Arrays.fill(probVec, 0.5);
    bestCost = POSITIVE_INFINITY;
 
    for (int i = 0; i < LOOP_COUNT; i++) {
        // Creates N genes
        boolean[][] genes = new boolean[N][totalBits];
        for (boolean[] gene : genes) {
            for (int k = 0; k < gene.length; k++) {
                if (rand.nextDouble() < probVec[k])
                    gene[k] = true;
            }
        }
 
        // Calculate costs
        double[] costs = new double[N];
        for (int j = 0; j < N; j++) {
            costs[j] = costFunc.cost(toRealVec(genes[j], domains));
        }
 
        // Find min and max cost genes
        boolean[] minGene = null, maxGene = null;
        double minCost = POSITIVE_INFINITY, maxCost = NEGATIVE_INFINITY;
        for (int j = 0; j < N; j++) {
            double cost = costs[j];
            if (minCost > cost) {
                minCost = cost;
                minGene = genes[j];
            }
            if (maxCost < cost) {
                maxCost = cost;
                maxGene = genes[j];
            }
        }
 
        // Compare with the best cost gene
        if (bestCost > minCost) {
            bestCost = minCost;
            bestGene = minGene;
        }
 
        // Update the probability vector with max and min cost genes
        for (int j = 0; j < totalBits; j++) {
            if (minGene[j] == maxGene[j]) {
                probVec[j] = probVec[j] * (1d - learnRate) +
                        (minGene[j] ? 1d : 0d) * learnRate;
            } else {
                final double learnRate2 = learnRate + negLearnRate;
                probVec[j] = probVec[j] * (1d - learnRate2) +
                        (minGene[j] ? 1d : 0d) * learnRate2;
            }
        }
 
        // Mutation
        for (int j = 0; j < totalBits; j++) {
            if (rand.nextDouble() < mutProb) {
                probVec[j] = probVec[j] * (1d - mutShift) +
                        (rand.nextBoolean() ? 1d : 0d) * mutShift;
            }
        }
    }
}

See also

• Estimation of Distribution Algorithm