Population-based incremental learning: Difference between revisions

Revision as of 12:06, 13 June 2009

Latest revision as of 08:36, 1 December 2020

(25 intermediate revisions by 15 users not shown)

Line 1:

In [[computer science]] and [[machine learning]], '''population-based incremental learning''' ('''PBIL''') is one of thean [[Optimization (mathematics)|optimization]] [[algorithm]], and one of thean [[estimation of distribution algorithm]]. This is a type of [[genetic algorithm]] where the [[genotype]] of an entire population ([[probability]] [[Euclidean vector|vector]]) is evolved rather than individual members.<ref>

{{Citation

| last1 = Karray | first1 = Fakhreddine O.

| last2 = de Silva | first2 = Clarence

| title = Soft computing and intelligent systems design

| dateyear = 2004

| publisher = Addison Wesley

| isbn = 0-321-11617-8}}</ref>. 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.<ref name="Baluja1">{{Citation

| last1 = Baluja | first1 = Shumeet

| title = Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning

| dateyear = 1994

| periodical = Technical Report

| number = CMU-CS-94-163

| publisher = Carnegie Mellon University

| place = Pittsburgh, PA

| issue = CMU–CS–94–163

| url = http://www.cs.cmu.edu/afs/cs/user/baluja/www/papers/CMU-CS-94-163.ps.gz

| citeseerx = 10.1.1.61.8554

}}</ref><ref name="Baluja2">{{Citation

| last1 = Baluja | first1 = Shumeet

| last2 = Caruana | first2 = Rich

| title = Removing the Genetics from the Standard Genetic Algorithm

| dateyear = 1995

| publisher = Morgan Kaufmann Publishers

| pages = 38-4638–46

| citeseerx = 10.1.1.44.5424

| url = http://www.cs.cmu.edu/afs/cs/user/baluja/www/papers/CMU-CS-95-141.ps.gz

}}</ref>.<ref name="Baluja3">{{Citation

| last1 = Baluja | first1 = Shumeet

| title = An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics

| year = 1995

| publisher =

| pages =

| citeseerx = 10.1.1.43.1108

}}</ref>

== Algorithm ==

Line 30 ⟶ 37:

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 2-31–4

== Source code ==

This is a part of source code implemented in [[Java (programming language)|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.

<sourcesyntaxhighlight lang="java">

public void optimize() {

final int totalBits = getTotalBits(domains);

final double[] probVec = new double[totalBits];

Arrays.fill(probVec, 0.5);

Line 46 ⟶ 54:

for (int i = 0; i < ITER_COUNT; i++) {

// Creates N genotypesgenes

final boolean[][] genoTypesgenes = new boolean[N][totalBits];

for (boolean[] genoTypegene : genoTypesgenes) {

for (int k = 0; k < genoTypegene.length; k++) {

if (rand.nextDoublerand_nextDouble() < probVec[k])

genoTypegene[k] = true;

}

}

// Calculate costs

final double[] costs = new double[N];

for (int j = 0; j < N; j++) {

costs[j] = costFunc.cost(toRealVec(genoTypesgenes[j], domains));

}

// Find min and max cost genotypesgenes

boolean[] minGenoTypeminGene = null, maxGenoTypemaxGene = null;

double minCost = POSITIVE_INFINITY, maxCost = NEGATIVE_INFINITY;

for (int j = 0; j < N; j++) {

Line 68 ⟶ 76:

if (minCost > cost) {

minCost = cost;

minGenoTypeminGene = genoTypesgenes[j];

}

if (maxCost < cost) {

maxCost = cost;

maxGenoTypemaxGene = genoTypesgenes[j];

}

}

// Compare with the best cost genotypesgene

if (bestCost > minCost) {

bestCost = minCost;

bestGenoTypebestGene = minGenoTypeminGene;

}

// Update the probability vector with max and min cost genotypesgenes

for (int j = 0; j < totalBits; j++) {

if (minGenoTypeminGene[j] == maxGenoTypemaxGene[j]) {

probVec[j] = probVec[j] * (1d - learnRate) +

(minGenoTypeminGene[j] ? 1d : 0d) * learnRate;

} else {

final double learnRate2 = learnRate + negLearnRate;

probVec[j] = probVec[j] * (1d - learnRate2) +

(minGenoTypeminGene[j] ? 1d : 0d) * learnRate2;

}

}

// Mutation

for (int j = 0; j < totalBits; j++) {

Line 103 ⟶ 111:

}

}

</syntaxhighlight>

</source>

==See also==

* [[Estimation of Distributiondistribution Algorithmalgorithm]] (EDA)

* [[Learning classifier system|Learning Classifier System]] (LCS)

== References ==

Line 112 ⟶ 121:

[[Category:Genetic algorithms]]

[[Category:Articles with example Java code]]

{{Comp-sci-stub}}