PopulationBased Incremental LearningPopulationBased Incremental Learning, PBIL. TaxonomyPopulationBased Incremental Learning is an Estimation of Distribution Algorithm (EDA), also referred to as Population ModelBuilding 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. InspirationPopulationBased Incremental Learning is a populationbased 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. StrategyThe 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. ProcedureThe PopulationBased Incremental Learning algorithm maintains a realvalued prototype vector that represents the probability of each component being expressed in a candidate solution. Algorithm (below) provides a pseudocode listing of the PopulationBased 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$ End End End 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}$End End End Return ($S_{best}$)Heuristics
Code ListingListing (below) provides an example of the PopulationBased 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} end def generate_candidate(vector) candidate = {} candidate[:bitstring] = Array.new(vector.size) vector.each_with_index do p, i candidate[:bitstring][i] = (rand()<p) ? 1 : 0 end return candidate end def update_vector(vector, current, lrate) vector.each_with_index do p, i vector[i] = p*(1.0lrate) + current[:bitstring][i]*lrate end end def mutate_vector(vector, current, coefficient, rate) vector.each_with_index do p, i if rand() < rate vector[i] = p*(1.0coefficient) + rand()*coefficient end end end def search(num_bits, max_iter, num_samples, p_mutate, mut_factor, l_rate) vector = Array.new(num_bits){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] end 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 end return best end 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]}" end Download: pbil.rb.
ReferencesPrimary SourcesThe PopulationBased 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 MoreBaluja 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]. Bibliography

Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...


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

Do you like Clever Algorithms? Buy the book now. 