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:
- A population is generated from the probability vector.
- The fitness of each member is evaluated and ranked.
- Update population genotype (probability vector) based on fittest individual.
- Mutate.
- 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 doubletotalBits;
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() < probVeck)
genek = true;
}
}
// Calculate costs
final double[] costs = new doubleN;
for (int j = 0; j < N; j++) {
costsj = costFunc.cost(toRealVec(genesj, 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 = costsj;
if (minCost > cost) {
minCost = cost;
minGene = genesj;
}
if (maxCost < cost) {
maxCost = cost;
maxGene = genesj;
}
}
// 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 (minGenej == maxGenej) {
probVecj = probVecj * (1d - learnRate) +
(minGenej ? 1d : 0d) * learnRate;
} else {
final double learnRate2 = learnRate + negLearnRate;
probVecj = probVecj * (1d - learnRate2) +
(minGenej ? 1d : 0d) * learnRate2;
}
}
// Mutation
for (int j = 0; j < totalBits; j++) {
if (rand.nextDouble() < mutProb) {
probVecj = probVecj * (1d - mutShift) +
(rand.nextBoolean() ? 1d : 0d) * mutShift;
}
}
}
}
See also
References
- ^ Karray, Fakhreddine O.; de Silva, Clarence (2004), Soft computing and intelligent systems design, Addison Wesley, ISBN 0-321-11617-8
- ^ Baluja, Shumeet (1994), "Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning", Technical Report, no. CMU–CS–94–163, Pittsburgh, PA: Carnegie Mellon University, CiteSeerX 10.1.1.61.8554
- ^ Baluja, Shumeet; Caruana, Rich (1995), Removing the Genetics from the Standard Genetic Algorithm, Morgan Kaufmann Publishers, pp. 38–46, CiteSeerX 10.1.1.44.5424
- ^ Baluja, Shumeet (1995), An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics, CiteSeerX 10.1.1.43.1108
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:
- A population is generated from the probability vector.
- The fitness of each member is evaluated and ranked.
- Update population genotype (probability vector) based on fittest individual.
- Mutate.
- 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 doubletotalBits;
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() < probVeck)
genek = true;
}
}
// Calculate costs
final double[] costs = new doubleN;
for (int j = 0; j < N; j++) {
costsj = costFunc.cost(toRealVec(genesj, 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 = costsj;
if (minCost > cost) {
minCost = cost;
minGene = genesj;
}
if (maxCost < cost) {
maxCost = cost;
maxGene = genesj;
}
}
// 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 (minGenej == maxGenej) {
probVecj = probVecj * (1d - learnRate) +
(minGenej ? 1d : 0d) * learnRate;
} else {
final double learnRate2 = learnRate + negLearnRate;
probVecj = probVecj * (1d - learnRate2) +
(minGenej ? 1d : 0d) * learnRate2;
}
}
// Mutation
for (int j = 0; j < totalBits; j++) {
if (rand.nextDouble() < mutProb) {
probVecj = probVecj * (1d - mutShift) +
(rand.nextBoolean() ? 1d : 0d) * mutShift;
}
}
}
}
See also
References
- ^ Karray, Fakhreddine O.; de Silva, Clarence (2004), Soft computing and intelligent systems design, Addison Wesley, ISBN 0-321-11617-8
- ^ Baluja, Shumeet (1994), "Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning", Technical Report, no. CMU–CS–94–163, Pittsburgh, PA: Carnegie Mellon University, CiteSeerX 10.1.1.61.8554
- ^ Baluja, Shumeet; Caruana, Rich (1995), Removing the Genetics from the Standard Genetic Algorithm, Morgan Kaufmann Publishers, pp. 38–46, CiteSeerX 10.1.1.44.5424
- ^ Baluja, Shumeet (1995), An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics, CiteSeerX 10.1.1.43.1108