Population-based incremental learning: Difference between revisions

Revision as of 12:43, 22 January 2010

Latest revision as of 08:36, 1 December 2020

(12 intermediate revisions by 9 users not shown)

Line 1:

In [[computer science]] and [[machine learning]], '''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>. 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://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.8554

| 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–46

| urlciteseerx = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=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

| dateyear = 1995

| publisher =

| pages =

| urlciteseerx = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.1108

}}</ref>.

== Algorithm ==

Line 41:

# Update population genotype (probability vector) based on fittest individual.

# Mutate.

# Repeat steps 1-41–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 55:

for (int i = 0; i < ITER_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;

}

Line 111:

}

}

</syntaxhighlight>

</source>

==See also==

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

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

== References ==

Line 120 ⟶ 121:

[[Category:Genetic algorithms]]

[[Category:Articles with example Java code]]

[[ja:Population-based incremental learning]]