Population-based incremental learning: Difference between revisions

Revision as of 06:18, 13 June 2009

Latest revision as of 08:36, 1 December 2020

(28 intermediate revisions by 15 users not shown)

Line 1:

In [[machinecomputer learningscience]] and [[softmachine computinglearning]], '''population-based incremental learning''' ('''PBIL)''') is an [[Optimization (mathematics)|optimization]] [[algorithm]], and an [[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>. ThisThe algorithm is oneproposed ofby theShumeet [[EstimationBaluja ofin Distribution Algorithm]]1994. The algorithm is proposedsimpler bythan Shumeeta Balujastandard genetic algorithm, and in 1994many cases leads to better results than a standard genetic algorithm.<ref name="Baluja1">{{Citation

| last1 = Baluja | first1 = Shumeet

__TOC__

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

| year = 1994

| periodical = Technical Report

| publisher = Carnegie Mellon University

| place = Pittsburgh, PA

| issue = CMU–CS–94–163

| 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

| year = 1995

| publisher = Morgan Kaufmann Publishers

| pages = 38–46

| citeseerx = 10.1.1.44.5424

}}</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>

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

# 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);

bestCost = POSITIVE_INFINITY;

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

// Creates N genes

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

for (boolean[] gene : genes) {

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

if (rand.nextDoublerand_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;

Line 60 ⟶ 83:

}

}

// Compare with the best cost gene

if (bestCost > minCost) {

Line 66 ⟶ 89:

bestGene = minGene;

}

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

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

Line 78 ⟶ 101:

}

}

// Mutation

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

Line 88 ⟶ 111:

}

}

</syntaxhighlight>

</source>

==See also==

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

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

== References ==

Line 97 ⟶ 121:

[[Category:Genetic algorithms]]

[[Category:Articles with example Java code]]

{{Comp-sci-stub}}