In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
and
machine learning
Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
, population-based incremental learning (PBIL) is an
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
, and an
estimation of distribution algorithm
''Estimation of distribution algorithms'' (EDAs), sometimes called ''probabilistic model-building genetic algorithms'' (PMBGAs), are stochastic optimization methods that guide the search for the optimum by building and sampling explicit probabili ...
. This is a type of
genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to g ...
where the
genotype
The genotype of an organism is its complete set of genetic material. Genotype can also be used to refer to the alleles or variants an individual carries in a particular gene or genetic location. The number of alleles an individual can have in a ...
of an entire population (
probability
Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
vector
Vector most often refers to:
* Euclidean vector, a quantity with a magnitude and a direction
* Disease vector, an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematics a ...
) is evolved rather than individual members.
[
] 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.
Algorithm
In PBIL, genes are represented as real values in the range
,1 indicating the probability that any particular
allele
An allele is a variant of the sequence of nucleotides at a particular location, or Locus (genetics), locus, on a DNA molecule.
Alleles can differ at a single position through Single-nucleotide polymorphism, single nucleotide polymorphisms (SNP), ...
appears in that
gene
In biology, the word gene has two meanings. The Mendelian gene is a basic unit of heredity. The molecular gene is a sequence of nucleotides in DNA that is transcribed to produce a functional RNA. There are two types of molecular genes: protei ...
.
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
Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...
. 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 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 = 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
if (minCost > cost) {
minCost = cost;
minGene = genes
}
if (maxCost < cost) {
maxCost = cost;
maxGene = genes
}
}
// 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 maxGene {
probVec = probVec * (1d - learnRate) +
(minGene ? 1d : 0d) * learnRate;
} else {
final double learnRate2 = learnRate + negLearnRate;
probVec = probVec * (1d - learnRate2) +
(minGene ? 1d : 0d) * learnRate2;
}
}
// Mutation
for (int j = 0; j < totalBits; j++) {
if (rand.nextDouble() < mutProb) {
probVec = probVec * (1d - mutShift) +
(rand.nextBoolean() ? 1d : 0d) * mutShift;
}
}
}
}
See also
*
Estimation of distribution algorithm
''Estimation of distribution algorithms'' (EDAs), sometimes called ''probabilistic model-building genetic algorithms'' (PMBGAs), are stochastic optimization methods that guide the search for the optimum by building and sampling explicit probabili ...
(EDA)
*
Learning Classifier System
Learning classifier systems, or LCS, are a paradigm of rule-based machine learning methods that combine a discovery component (e.g. typically a genetic algorithm in evolutionary computation) with a learning component (performing either supervised ...
(LCS)
References
Genetic algorithms
Articles with example Java code