Individuals' genes are made of strings of bits. Each Gene is composed by 1 allele.

In this line It is declared the genotype's structure:

- Type of alleles: In the example the alleles will be of type 'Bits'. Other possible types are 'Packed_Binary' and 'Real'.
- Size: number of alleles that compose each gene. In the example each gene is made of '1' allele.
- Type of binary alleles: The type of binary alleles may be 'standard' (in the example) or 'gray'.

Here the individual structure is declared: We have declared individuals of 100 genotypes for ONEMAX problem.

In the case of MAXSAT we have 10 variables. So line
13 will be:

typedef Individual<genotype, 10> ind_type;

We declare here the population structure:

- individuals: like those declared at line 13
- Population size: 400 of these individuals
- Mode of evolution: it can be 'steady_state' -ssGA-, where every step computes a single individual, or 'generational' -genGA- (in the example), where a whole new pop is computed every step.
- Neighborhood used: We set the neighborhood
size and shape on lines 23 and 24. There are 4 different kinds of neighborhood:
- 'Any' : The neighborhood is the whole population
- 'UniD_Ring' : The neighborhood is a unidirectional ring
- 'BiD_Ring' : The neighborhood is a bidirectional ring
- 'Grid' : The neighborhood is a 2D grid

- Problem: The problem to be solved is 'ONEMAX'.

In the case of MAXSAT line 14 would be:

typedef Population<ind_type, 400, generational,
Neighborhood, MAXSAT> pop_type;

'opp_type' is a class for the management of operators applied to the population class 'pop_type'

'ga_type' is a class for the management of the GA, which will have a population defined on 'pop_type' and an operator pool defined on 'opp_type'

In lines 17 to 21 we declare some needed variables:

- 'sh' holds the shape of a 3D grid
- 'ga' is an instance of the class 'ga_type', which manages the GA
- 'pst' is an instance of the class that gather process statistics
- 'p' is a record that contains the process statistics
- 'stats' is a record that contains the population statistics

We define here the population shape.

In this particular case the population is allocated in a 20 x 20 grid (400
individuals).

We set the shape defined in line 22.

We set the neighborhood type as 'grid': we are using a cellular GA with NEWS Neighborhood.

In lines 25 to 29 the GA is initialized with the values of 'island.params' (see below). The algorithm's parameters may be included either using file 'island.params', using the corresponding class methods, or both ways. In this example 'island.params' contains:

[NUMBER_OF_OPERATORS]

5

[OPERATORS]

rw // roulette wheel selection for one parent

rw // roulette wheel selection for the other parent

dpx 1.0 // crossover probability

mutation 0.01 //mutation probability: 1 DIV 100

rep_least_fit // individuals replacement policy

[OUTPUT_DISPLAY]

nothing

[SEED]

37

[NUMERIC_RANGES]

0 1

// End of file

In the case of solving MAXSAT problem, we need to modify the mutation probability in 'island.params' file:

[NUMBER_OF_OPERATORS]

5

[OPERATORS]

rw // roulette wheel selection for one parent

rw // roulette wheel selection for the other parent

dpx 1.0 // crossover probability

*mutation 0.0233 // mutation probability: 1 DIV 43*

rep_least_fit // individuals replacement policy

[OUTPUT_DISPLAY]

nothing

[SEED]

37

[NUMERIC_RANGES]

0 1

// End of file

We reset the process statistics

The fitness value for the best solution is set to 100

In the case of solving MAXSAT problem, we need to change the global optima to 43, so line 31 will be:

MAXSAT: ga.Set_Solution_Fitness(43);

The GA iterates until a solution is found or a million evaluations is done (in this case it is supposed that the algorithm can not find any solution)

A generation of the GA is made in this line

We update the statistics

The process statistics are copied to 'p'

The algorithm writes to the output the number of function evaluations and the time employed to solve the problem

In this page, we describe an example where a cGA is applied to solve the ONEMAX problem (in concrete, it solve a problem instance of 100 variables).

Other possible configurations (i.e. ssGA, genGA, dcGA, other problems...) can be seen by moving the mouse over blue words. In orange color are the configuration elements for the problem to solve. An explanation of each line is showing when the mouse moves over the line number.

1:
#include "gene.hpp"

2:
#include "individual.hpp"

3:
#include "population.hpp"

4:
#include "neighb.hpp"

5:
#include "functs.hpp"

6:
#include "op_pool.hpp"

7: #include "ga.hpp"

8: #include "procst.hpp"

9: #include "network.hpp"

10: main()

11: {

12:
typedef Gene<Bit, 1, standard> genotype;

13: typedef Individual<genotype, 100> ind_type;

14: typedef Population<ind_type, 400, generational, Neighborhood, ONEMAX> pop_type;

15: typedef Operator_Pool<pop_type> opp_type;

16: typedef GA<pop_type,opp_type> ga_type;

17:
struct SHAPE sh;

18:
ga_type ga;

19:
Proc_Stats pst;

20:
PROC_STATS p;

21:
POP_STATS stats;

22: sh.x = 20; sh.y = 20; sh.z = 0;

23: ga.pop.neigh.Set_Shape( sh );

24: ga.pop.neigh.Set_Known_Neighb( grid );

25:
if(!ga.Init_GA("island.params"))

26: {

27: cerr<<"dcGA> ERROR! In initializing the GA"<<endl;

28: exit(-1);

29: }

30: pst.Reset();

31: ga.Set_Solution_Fitness(100);

32: while (ga.pop.problem.Get_Fitness_Counter()<1002900)

33: {

34: if(!ga.Step_Up())

35: break;

36: }

37: pst.Update();

38: p = pst.Get();

39: cout <<ga.pop.problem.Get_Fitness_Counter()<<" "

40: <<p.time_since_reset<<endl;

41: }