1. Algorithm

2. Source code

3. See also

4. References

In computer science and machine learning, population-based incremental learning (PBIL) is an optimization algorithm, and an estimation of distribution algorithm. This is a type of genetic algorithm where the genotype of an entire population (probability vector) is evolved rather than individual members.^[1] The algorithm is proposed by Shumeet Baluja in 1994. The algorithm is simpler than a standard genetic algorithm, and in many cases leads to better results than a standard genetic algorithm.^[2][3][4]

Algorithm

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

The PBIL algorithm is as follows:

1. A population is generated from the probability vector.
2. The fitness of each member is evaluated and ranked.
3. Update population genotype (probability vector) based on fittest individual.
4. Mutate.
5. Repeat steps 1-4

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. N = 100 and ITER_COUNT = 1000 is enough for a small problem.

public void optimize() {

    final int totalBits = getTotalBits();    final double[] probVec = new double[totalBits];    Arrays.fill(probVec, 0.5);    bestCost = POSITIVE_INFINITY;     for (int i = 0; i < ITER_COUNT; i++) {        // Creates N genes        final boolean[][] genes = new [N][totalBits];        for (boolean[] gene : genes) {            for (int k = 0; k < gene.length; k++) {                if (rand_nextDouble() < probVec[k])                    gene[k] = true;            }        }

        // Calculate costs        final 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 (EDA)
• Learning Classifier System (LCS)

References

• Casualty 1909
• Casualty Clearing Station
• Casualty clearing station
• Casualty Clearing Stations
• Casualty clearing stations
• Casualty (disambiguation)
• Casualty estimation
• Casualty loss
• Casualty Notification
• Casualty notification officer
• Casualty of Love
• Casualty prediction
• Casualty (series)
• Casualty (series 1)
• Casualty (Series 1)
• Casualty (series 10)
• Casualty (series 11)
• Casualty (series 12)
• Casualty (series 13)
• Casualty (series 14)
• Casualty (series 15)
• Casualty (series 16)
• Casualty (series 17)
• Casualty (series 18)
• Casualty (series 19)