G+ Examples

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:

  1. 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 xi is zero.

  1. Ackley function

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 xi is zero.

  1. Sphere function

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

 x1= 4, x2= 3,  x3= 2, x4= 1,  x5= 0,  x6= -1,  x7= -2,  x8= -3,  x9= -4,  x10= -5

  1.  TSP Circle problem

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.

  1. TSP Random problem

The problem is the same as the above one except that all the cities are randomly located.

  1. Single Knapsack problem with 50 objects

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.

  1. Simple bin packing problem (60 objects in 'triplets' of items from (25,50), bins of size 100)

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

  1. Steiner Circle problem

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.

  1. Steiner Weighted problem

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