Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

Home | Read Online

This is the ad-supported version of the book. Buy it now if you like it.

Population-Based Incremental Learning

Population-Based Incremental Learning, PBIL.


Population-Based Incremental Learning is an Estimation of Distribution Algorithm (EDA), also referred to as Population Model-Building Genetic Algorithms (PMBGA) an extension to the field of Evolutionary Computation. PBIL is related to other EDAs such as the Compact Genetic Algorithm, the Probabilistic Incremental Programing Evolution Algorithm, and the Bayesian Optimization Algorithm. The fact the the algorithm maintains a single prototype vector that is updated competitively shows some relationship to the Learning Vector Quantization algorithm.


Population-Based Incremental Learning is a population-based technique without an inspiration. It is related to the Genetic Algorithm and other Evolutionary Algorithms that are inspired by the biological theory of evolution by means of natural selection.


The information processing objective of the PBIL algorithm is to reduce the memory required by the genetic algorithm. This is done by reducing the population of a candidate solutions to a single prototype vector of attributes from which candidate solutions can be generated and assessed. Updates and mutation operators are also performed to the prototype vector, rather than the generated candidate solutions.


The Population-Based Incremental Learning algorithm maintains a real-valued prototype vector that represents the probability of each component being expressed in a candidate solution. Algorithm (below) provides a pseudocode listing of the Population-Based Incremental Learning algorithm for maximizing a cost function.

Input: $Bits_{num}$, $Samples_{num}$, $Learn_{rate}$, $P_{mutation}$, $Mutation_{factor}$
Output: $S_{best}$
$V$ $\leftarrow$ InitializeVector($Bits_{num}$)
$S_{best}$ $\leftarrow$ $\emptyset$
While ($\neg$StopCondition())
    $S_{current}$ $\leftarrow$ $\emptyset$
    For ($i$ To $Samples_{num}$)
        $S_i$ $\leftarrow$ GenerateSamples($V$)
        If (Cost($S_i$) $\leq$ Cost($S_{current}$))
            $S_{current}$ $\leftarrow$ $S_i$
            If (Cost($S_i$) $\leq$ Cost($S_{best}$))
                $S_{best}$ $\leftarrow$ $S_i$
    For ($S_{bit}^i$ $\in$ $S_{current}$)
        $V_{bit}^i$ $\leftarrow$ $V_{bit}^i$ $\times$ (1.0 – $Learn_{rate}$) + $S_{bit}^i$ $\times$ $Learn_{rate}$
        If (Rand() < $P_{mutation}$)
            $V_{bit}^i$ $\leftarrow$ $V_{bit}^i$ $\times$ (1.0 – $Mutation_{factor}$) + Rand() $\times$ $Mutation_{factor}$
Return ($S_{best}$)
Pseudocode for PBIL.


  • PBIL was designed to optimize the probability of components from low cardinality sets, such as bit's in a binary string.
  • The algorithm has a very small memory footprint (compared to some population-based evolutionary algorithms) given the compression of information into a single prototype vector.
  • Extensions to PBIL have been proposed that extend the representation beyond sets to real-valued vectors.
  • Variants of PBIL that were proposed in the original paper include updating the prototype vector with more than one competitive candidate solution (such as an average of top candidate solutions), and moving the prototype vector away from the least competitive candidate solution each iteration.
  • Low learning rates are preferred, such as 0.1.

Code Listing

Listing (below) provides an example of the Population-Based Incremental Learning algorithm implemented in the Ruby Programming Language. The demonstration problem is a maximizing binary optimization problem called OneMax that seeks a binary string of unity (all '1' bits). The objective function only provides an indication of the number of correct bits in a candidate string, not the positions of the correct bits. The algorithm is an implementation of the simple PBIL algorithm that updates the prototype vector based on the best candidate solution generated each iteration.

def onemax(vector)
  return vector.inject(0){|sum, value| sum + value}

def generate_candidate(vector)
  candidate = {}
  candidate[:bitstring] =
  vector.each_with_index do |p, i|
    candidate[:bitstring][i] = (rand()<p) ? 1 : 0
  return candidate

def update_vector(vector, current, lrate)
  vector.each_with_index do |p, i|
    vector[i] = p*(1.0-lrate) + current[:bitstring][i]*lrate

def mutate_vector(vector, current, coefficient, rate)
  vector.each_with_index do |p, i|
    if rand() < rate
      vector[i] = p*(1.0-coefficient) + rand()*coefficient

def search(num_bits, max_iter, num_samples, p_mutate, mut_factor, l_rate)
  vector ={0.5}
  best = nil
  max_iter.times do |iter|
    current = nil
    num_samples.times do
      candidate = generate_candidate(vector)
      candidate[:cost] = onemax(candidate[:bitstring])
      current = candidate if current.nil? or candidate[:cost]>current[:cost]
      best = candidate if best.nil? or candidate[:cost]>best[:cost]
    update_vector(vector, current, l_rate)
    mutate_vector(vector, current, mut_factor, p_mutate)
    puts " >iteration=#{iter}, f=#{best[:cost]}, s=#{best[:bitstring]}"
    break if best[:cost] == num_bits
  return best

if __FILE__ == $0
  # problem configuration
  num_bits = 64
  # algorithm configuration
  max_iter = 100
  num_samples = 100
  p_mutate = 1.0/num_bits
  mut_factor = 0.05
  l_rate = 0.1
  # execute the algorithm
  best=search(num_bits, max_iter, num_samples, p_mutate, mut_factor, l_rate)
  puts "done! Solution: f=#{best[:cost]}/#{num_bits}, s=#{best[:bitstring]}"
Population-Based Incremental Learning in Ruby
Download: pbil.rb.


Primary Sources

The Population-Based Incremental Learning algorithm was proposed by Baluja in a technical report that proposed the base algorithm as well as a number of variants inspired by the Learning Vector Quantization algorithm [Baluja1994].

Learn More

Baluja and Caruana provide an excellent overview of PBIL and compare it to the standard Genetic Algorithm, released as a technical report [Baluja1995] and later published [Baluja1995a]. Baluja provides a detailed comparison between the Genetic algorithm and PBIL on a range of problems and scales in another technical report [Baluja1995b]. Greene provided an excellent account on the applicability of PBIL as a practical optimization algorithm [Greene1996]. Höhfeld and Rudolph provide the first theoretical analysis of the technique and provide a convergence proof [Hohfeld1997].


[Baluja1994] S. Baluja, "Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning", Technical Report CMU-CS-94-163, School of Computer Science, Carnegie Mellon University, 1994.
[Baluja1995] S. Baluja and R. Caruana, "Removing the Genetics from the Standard Genetic Algorithm", Technical Report CMU-CS-95-141, School of Computer Science Carnegie Mellon University, 1995.
[Baluja1995a] S. Baluja and R. Caruana, "Removing the Genetics from the Standard Genetic Algorithm", in Proceedings of the International Conference on Machine Learning, 1995.
[Baluja1995b] S. Baluja, "An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics", Technical Report CMU-CS-95-193, School of Computer Science Carnegie Mellon University, 1995.
[Greene1996] J. R. Greene, "Population-based incremental learning as a simple versatile tool for engineering optimization", in Proceedings of the First International Conference on Evolutionary Computation and Its Applications, 1996.
[Hohfeld1997] M. Höhfeld and G. Rudolph, "Towards a theory of population based incremental learning", in Proceedings of the IEEE Conference on Evolutionary Computation, 1997.
Clever Algorithms: Nature-Inspired Programming Recipes

Free Course

Get one algorithm per week...
  • ...delivered to your inbox
  • ...described in detail
  • read at your own pace
Sign-up Now

Own A Copy

This 438-page ebook has...
  • ...45 algorithm descriptions
  • practice usage
  • ...pseudo code
  • ...Ruby code
  • ...primary sources
Buy Now

Please Note: This content was automatically generated from the book content and may contain minor differences.

Clever Algorithms: Nature-Inspired Programming Recipes

Do you like Clever Algorithms?
Buy the book now.

© Copyright 2015. All Rights Reserved. | About | Contact | Privacy