You can download G+ example programs written in Visual Basic separately by clicking the following link: Download Example. The sample contain nine problems: Rastrign function, Ackley function, Sphere function, TSP Circle problem, TSP Random problem, Single Knapsack problem, Simple bin packing problem, Steiner Circle problem, Steiner Weighted problem. Below is a brief description of each problem:
Rastrign function
The problem is defined as to minimize f(x) = 10×n+ ∑{x(i)×x(i)-10×cos(2πx(i))} (n=10). The minimal value of this function is zero when x_{i} is zero.
The problem is defined as to minimize f(x) = 20+e+ {20×exp(-0.2×(sqrt((1/n)×∑(x(i)^2))-exp((1/n)∑(cos(2×Pi×x(i)))} (n=10). The minimal value of this function is zero when x_{i} is zero.
The problem is defined as to minimize f(x) = ∑[x(i)-5+i]^2 (n=10). The minimal value of this function is zero when
x_{1}= 4, x_{2}= 3, x_{3}= 2, x_{4}= 1, x_{5}= 0, x_{6}= -1, x_{7}= -2, x_{8}= -3, x_{9}= -4, x_{10}= -5
The Traveling Salesman Problem: A hypothetical salesmen must make a complete tour of a given set of cities on a circle, in the order that minimizes his total distance traveled. Since all cities are located on a circle, it is obvious that the shortest trip is along the circle.
The problem is the same as the above one except that all the cities are randomly located.
A thief has a knapsack of a certain capacity (625 in this case). He looks around and sees different items of different weights and values. He would like the items he chooses for his knapsack to have the greatest value possible yet still fit in his knapsack. The problem is called the 0-1 Knapsack Problem because the thief can either take (1) or leave (0) each item.
It is required to put a given number of objects, each having a different size, into a minimal number of bins of a given size
In a certain area there are N villages, and j'th village requires M(j) phone lines. Cost of a line is $1 per 1 km. Where should a phone company locate a (unique) station to cover the demand at the minimum cost. In this case N= 24, M(j)=1 for all villiages.
The problem is the same as the previous one except that M(j)=j.
A more detailed description of the above problems is available at http://www.aridolan.com/ofiles/ga/gaa/gaa.aspx#DemoAll. For problem 1,2,3, and 6, both real encoding and binary encoding are implemented. The rest are implemented as real encoding only. You can specify the encoding method by select Real Number Encoding or Binary Encoding from the Option menu. The program supports two termination method. If the Custom Terminator of the Option menu is checked, then the GA will evolve until the user press the STOP button. Otherwise it will evolve a fixed number of generations defined within the program. For problem 4,5,8, and 9, you can have a vivid picture of how GA works by check the Graphic View of the option menu.
To solve a problem, first choose the encoding method and define the termination method from the Option menu. Then select the problem you want to solve from the Functions menu. Finally click the evolve button () from the tool bar. The best five solutions will be shown in the text box with the objective score and a string expression of each genome.
Below is a simplified program for minimize the Sphere function:
Option Explicit
Dim g_allelesetarr As
New AlleleSetArray
Dim g_pop As New population
Private Sub Form_Load()
Dim aset As AlleleSet
Dim i As Long
g_allelesetarr.newArray (10) 'create 10 allele sets
Set aset = g_allelesetarr(0) 'get the first allele set and initialize it
Call aset.newDiscrete(-5.12, 5.12, 0.001, GABOUND_INCLUSIVE, GABOUND_INCLUSIVE)
For i = 1 To 9 'copy the definition of the first allele set to the rest
Call g_allelesetarr.link(i, 0)
Next
g_allelesetarr.init 'initialization of all allele sets
'initialize GA parameters
g.algorithm = GA_CROWDINGGA 'use crowding GA
g.Crossover = GA_UNIFORMCROSSOVER 'use uniform crossover
g.defmutator = GA_GAUSSIANMUTATOR 'use Gaussian mutator
g.maxgeneration = 250 'let it evolve for 250 generations
Dim gTemplate As New genome
gTemplate.AlleleSetArray = g_allelesetarr 'define alleles for the genome
gTemplate.newGenome 'create a sample genome
g_pop.newPopulation , gTemplate 'create population based on gTemplate
Set g.population = g_pop 'assign the population to G+
g.evolve 0 'evolve the population
'print the best 5 genomes
For i = 0 To 4
Debug.Print Format(g.population.best(i).Evaluate, "#0.000") + Space(4) + _
g.population.best(i).ToString
Next
End Sub
'the objective function
Private Sub g_OnEvaluateFitnessFunction(ByVal genome
As GALib.IGenome, var As
Variant, result As Single)
Dim i As Long
Dim sngObj As Single
'calculate the fitness value: f(x)=∑{x(i)-5+i}^2 (n=10)
sngObj = 0
For i = 0 To 9
Dim xx as Single
xx = genome(i)
sngObj = sngObj + (xx - 5 + i) ^ 2
Next
result = sngObj
End Sub
Remarks
Generally there are three global objects for a typical G+ application: an AlleleSetArray Object, a Population Object and a GA control. All gene definitions are stored in the AlleleSetArray object, in this case g_allelesetarr. The Population Object will contain all individuals for evolution, in this case g_pop. Finally the GA control (in this case g) will contain all the parameters for the genetic algorithm and evolve the population until certain criteria is met.
Weidong Yuan, 23 September 2004