Population-based incremental learning: Difference between revisions

Revision as of 06:29, 13 June 2009

Revision as of 10:11, 13 June 2009

Line 1:

In [[machinecomputer learningscience]] and [[softmachine computinglearning]], '''population-based incremental learning''' ('''PBIL)''') is one of the [[Optimization (mathematics)|optimization]] [[algorithm]], and one of the [[estimation of distribution algorithm]]. This is a type of [[genetic algorithm]] where the [[genotype]] of an entire population is evolved rather than individual members<ref>

{{Citation

| last1 = Karray | first1 = Fakhreddine O.

Line 6:

| date = 2004

| publisher = Addison Wesley

| isbn = 0-321-11617-8}}</ref>. This is one of the [[Estimation of Distribution Algorithm]]. The algorithm is proposed by Shumeet Baluja in 1994<ref>{{Citation

| last1 = Baluja | first1 = Shumeet

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

Line 20:

| pages = 38-46

}}</ref>.

__TOC__

== Genotype representationAlgorithm ==

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:

Line 34 ⟶ 32:

== 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.

<source lang="java">

Line 43 ⟶ 41:

bestCost = POSITIVE_INFINITY;

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

// Creates N genesgenotypes

boolean[][] genesgenoTypes = new boolean[N][totalBits];

for (boolean[] genegenoType : genesgenoTypes) {

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

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

genegenoType[k] = true;

}

}

Line 56 ⟶ 54:

double[] costs = new double[N];

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

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

}

// Find min and max cost genesgenotypes

boolean[] minGeneminGenoType = null, maxGenemaxGenoType = null;

double minCost = POSITIVE_INFINITY, maxCost = NEGATIVE_INFINITY;

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

Line 66 ⟶ 64:

if (minCost > cost) {

minCost = cost;

minGeneminGenoType = genesgenoTypes[j];

}

if (maxCost < cost) {

maxCost = cost;

maxGenemaxGenoType = genesgenoTypes[j];

}

}

// Compare with the best cost genegenotypes

if (bestCost > minCost) {

bestCost = minCost;

bestGenebestGenoType = minGeneminGenoType;

}

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

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

if (minGeneminGenoType[j] == maxGenemaxGenoType[j]) {

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

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

} else {

final double learnRate2 = learnRate + negLearnRate;

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

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

}

}

Line 104 ⟶ 102:

==See also==

* [[Estimation of Distribution Algorithm]] (EDA)

== References ==