Introduction
Machine learning is one of the most exciting aspects of computer science because it allows us to experiment with problem solving skills performed by a computer without the programmer hard wiring the steps needed to come up with a solution. A while back we explored the use of genetic algorithms to solve numerical problems. In this article I would like to discuss another offshoot of the genetic algorithm called Population Based Incremental Learning (PBIL).
Figure 1 - The Results of a PBIL algorithm on finding the points on a Circle with radius 25 and center 50,50.
Population Based Incremental Learning
PBIL allows you to represent your entire genetic population base through a probability vector rather than a
myriad of chromosomes. A probability vector is simply a sequence of probabilities. Each probability value in the
sequence represents the probability that we can generate a 1 or 0 at the gene position. For example the
probability vector {.5, .5, 1, 1} can be represented by the following population.
{0, 0, 1, 1}
{0, 1, 1, 1}
{1, 0, 1, 1}
{1, 1, 1, 1}
The probability that we will generate a 1 or 0 in the first position is 50/50, so 50% of the chromosomes in the
population have 1 in the first position, and 50% of the chromosomes in the population have 0 in the first
position. The probability of generating a one in the 3rd and 4th position is 1, so this number will always be one.
The algorithm for generating a solution using probability vectors is actually quite simple.
Listing 1 - PBIL Algorithm Steps.
- Initialize a probability vector with all probabilities being 1/2.
- Generate a population of N chromosomes using the probability vector to randomly determine the gene in
each chromosome position (1 or 0).
- Evaluate the fitness of each chromosome based on a fitness function for your particular problem.
- Sort all chromosomes by fitness value.
- Update the probability value in each vector position based on the top X chromosomes using a learning
rate.
Private Vector As Probability = Probabilty Vector * (1.0 - LR) + topchromosome* (LR)
where LR = some learning rate
- Check to see if the probability vector has converged. If not, repeat steps (2) through (5).
This algorithm is much easier to implement than the simple genetic algorithm (which involves crossovers,
mutations, reproductions, and deaths), but is actually just as effective. It's a better algorithm in that it doesn't
require you to remember as much information from generation to generation. You only need to maintain the
probability vector which contains the probability distribution of each gene in our chromosome.
The Design
Below is the simple UML Design used by our algorithm implementation. The BinaryGene class has five methods that aid us in our PBIL implementation: CalculateFitness, CompareTo, UpdateProbabilityVector, and HasConverged. CalculateFitness is the method that we use to calculate our fitness function. The higher the value returned from this method, the higher the fitness of the chromosome. CompareTo implements the IComparable interface to allow us to sort Genomes by fitness. UpdateProbabilityVector modifies the probability vector in our algorithm according to the learning rate and the genes in our highest fit chromosomes. The HasConverged method determines if the probability vector has converged to a final solution with all 1's and 0's.
Note that the chromosome contains an array of integers called _genome. This array will either contain a value of 0 or 1. The Generate method of the BinaryGene class allows us to generate a chromosome based on the probability vector. The FormNumber method is used to break down the binary 1's and 0's inside the genome into integer values for use in the fitness function. Finally, the ToString method allows us to write our gene to the console as a readable string of integer values.
Figure 2 - Chromosome for PBIL Algorithm reverse engineered using WithClass UML Tool.
Implementing PBIL through the Binary Gene Class
Once we've created our class to handle all major steps of the PBIL algorithm, we can easily implement our algorithm. Listing 2 shows the step by step implementation of PBIL through the binary gene class.
Listing 2 - PBIL Implementation of the BinaryGene class
Overloads Shared Sub Main(ByVal args() As String)
Dim _genomes(NUMBER_OF_SAMPLES) As BinaryGene
Dim _probabilities(BinaryGene.LENGTH) As Double
' (1) generate initial probability vector
Dim i As Integer
For i = 0 To BinaryGene.LENGTH - 1
_probabilities(i) = 0.5 ' initialize probabilities
Next i
'
' TODO: Add code to start application here
'
Dim counter As Integer = 0
While counter < MAX_COUNTER_VALUE
If counter Mod 1000 = 0 Then
Dim d As Double
For Each d In _probabilities
Console.Write("{0:0.00}, ", d)
Next d
Console.WriteLine()
Console.WriteLine()
If Not (_genomes(0) Is Nothing) Then
Console.WriteLine("---------Generation #{0}---------", counter)
Console.WriteLine(_genomes(0).ToString())
End If
Console.WriteLine()
Console.WriteLine()
End If
counter += 1
' (2) generate chromosomes based on probability vector
' (3) calculate fitness of each gene
'Dim i As Integer
For j As Integer = 0 To NUMBER_OF_SAMPLES - 1
_genomes(j) = New BinaryGene
_genomes(j).Generate(_probabilities)
_genomes(j).CalculateFitness()
Next j
' (4) Sort all chromosomes by fitness value
Array.Sort(_genomes)
' (5) Update the probability value in each vector position based on the top X chromosomes using a learning rate
'Dim i As Integer
For k As Integer = 0 To NUMBER_OF_VECTORS_TO_UPDATE_FROM - 1
_genomes(k).UpdateProbabilityVector(_probabilities)
Next k
'For l As Integer = 0 To 5
' l = i
'Next l
'
' (6) Check to see if the probability vector has converged.
' If not, repeat steps (2) through (5)
Dim convergenceFailureIndex As Integer = BinaryGene.HasConverged(_probabilities)
If convergenceFailureIndex < 0 Then
Console.WriteLine("** Final Probability Vector **")
Dim d As Double
For Each d In _probabilities
Console.Write("{0:0.00}, ", d)
Next d
Console.WriteLine()
Console.WriteLine()
Console.WriteLine("** Final Answer **")
Console.WriteLine("Converged at Generation {0}", counter)
Exit While
End If
End While
Console.WriteLine()
Console.WriteLine()
Console.WriteLine(_genomes(0).ToString())
Console.ReadLine()
End Sub 'Main
Experimenting with Fitness Functions
Once the algorithm is in place, we can test it on different fitness functions to produce different solutions. The first fitness function we will use to test PBIL is the fitness for a Fibonacci sequence. The Fibonacci sequence is a sequence of numbers whose previous two numbers in the sequence sum to produce the current number. The fitness function for this sequence is shown below:
Listing 3 - Fibonacci Fitness Function
'/ <summary>
'/ Find a Fibanocci sequence where x(i+2) = x(i) + x(i+1)
'/ </summary>
Sub FindFibanocci()
' track the previous number, and the number before
' the previous number
Dim _previousNumber As Integer = 1
Dim _previousPrevious As Integer = 0
Dim i As Integer
For i = 0 To LENGTH - NUMBER_SIZE Step NUMBER_SIZE
Dim nextNumber As Integer = FormNumber(i, NUMBER_SIZE)
' fitness is if the sum of the previous two numbers
' equals the current number
_fitness = _fitness + Math.Exp(-Math.Abs((nextNumber - (_previousNumber + _previousPrevious))))
_previousPrevious = _previousNumber
_previousNumber = nextNumber
Next i
If _previousNumber > 500 Then ' limit values to less than 500
_fitness = 0
End If
End Sub 'FindFibanocci
After running the PBIL algorithm on the fitness function above, the result produces a perfect Fibonacci sequence at generation 1986 shown in figure 3. Note that if you split the probability vector into groups of 10 bits, the first bit being the least significant, it will match the final solution produced in the fittest chromosome.
Figure 3 - Fibanocci Sequence Solution Produced from PBIL.
A more complicated fitness function we tried on PBIL is a function to test for perfect number factors. A perfect number is a number whose factors produce a sum of the same number. For example, the factors of the number 6 are 1,2, and 3.
(1)(2)(3) = (1+2+3) = 6. So 6 is a perfect number.
Below is the fitness function we used to find a set of factors for a perfect number. The fitness function looks for a product and sum that match. It also looks for other criteria such as only one factor of the number 1:
'/ <summary>
'/ Find a perfect number using PBIL
'/ </summary>
'/ <returns></returns>
Function CalculatePerfectNumber() As Double
Dim sum As Double = 0
Dim product As Double = 1
Dim nextNumber As Integer = 0
Dim oneThere As Boolean = False
Dim moreThanOneNonZero As Integer = 0
Dim moreThanOneOne As Integer = 0
Dim i As Integer
For i = 0 To LENGTH - NUMBER_SIZE Step NUMBER_SIZE
nextNumber = FormNumber(i, NUMBER_SIZE)
If nextNumber = 1 Then
oneThere = True ' always need a one.
moreThanOneOne += 1 ' don't want more than one 1
End If
' track all non-zero numbers
If nextNumber <> 0 Then
moreThanOneNonZero += 1
End If
' compute the sum of factors
sum = sum + nextNumber
' compute the sum of all non-zero factors
If nextNumber <> 0 Then
product = product * nextNumber
End If
Next i
' fitness is roughly 1/ (product - sum)
' the closer the sum is to the product,
' the greater the fitness
_fitness = 1.0 / (Math.Abs((product - sum)) * 10000.0 + 0.0000001)
' don't count infinite answers
If product = Double.NaN Then
_fitness = -100000
End If
' all perfect numbers have 1 as a factor
' so make sure we have one
If Not oneThere Then
_fitness = 0
End If
' can't have more than one one as a factor
If moreThanOneOne > 1 Then
_fitness = 0
End If
' must have at least 2 non-zero factors (which can include 1)
If moreThanOneNonZero < 2 Then
_fitness = 0
End If
Return _fitness
End Function 'CalculatePerfectNumber
The results of the perfect number fitness function are shown below in figure 4. Note that the factors for 6 are produced:
Figure 4 - Results of PBIL run on a Fitness Function for finding Perfect Number Factors.
Conclusion
Genetic Algorithms are a powerful tool in which computers can be used to solve problems without programmer knowledge. PBIL is a variation of iterative learning algorithm that performs as well as a genetic algorithm and is easier to implement and more compact for saving solution information from iteration to iteration. In this article we used PBIL to solve some simple math problems. However, you can expand PBIL to solve real world problems in fields such as chemistry, economics, and mechanics. In our next AI article we will examine a similar algorithm called the Compact Genetic Algorithm (cGA).
References
Implementing a Genetic Algorithm in C# and .NET
Removing Genetics from the Standard Genetic Algorithm
NOTE: THIS ARTICLE IS CONVERTED FROM C# TO VB.NET USING A CONVERSION TOOL. ORIGINAL ARTICLE CAN BE FOUND ON C# CORNER (WWW.C-SHARPCORNER.COM).