In this section, you will learn how to:

Make a copy of the example file YourSolverHome/examples/src/tutorial/ea1max_values_partial.cpp and open this copy in your development environment. After filling in the blanks in each step in this section, you will have completed the example.

In this example, you will replace only half of the population at each generation. You will also decide to select parents depending on solution objective values. To do this, you will use pool evaluators to do customized value computation.

You will follow the idea in this example that the probability of selecting a parent will be proportional to the square of the number of 1's (the objective value) of the parent. We introduce an evaluator which performs this function: given another evaluator as argument, it raises its evaluation to a specified power.

The following macro definition allows you to raise the values obtained from pools to a given power, and then normalizes these values so that they sum to unity. (Such a normalization can be useful for various purposes, not least displaying.) This evaluator will be used later to modify the evaluations of solutions. The evaluator calls the update method on the subordinate evaluator passed. Note that the macro receives two parameters, a subordinate evaluator, and a power. ILOMULTIPLEEVALUATOR must call the function setEvaluation for each solution of the input pool.

Add the following code after the comment
//Raise the result of an evaluator to a given power, and normalize

ILOMULTIPLEEVALUATOR2(PowerEvaluator, IloSolution, IloSolutionPool, pool,
                      IloSolutionPoolEvaluator, eval,
                      IloNum, power) {
  eval.update(pool);
  IloNum sum = 0.0;
  for (IloSolutionPool::Iterator it1(pool); it1.ok(); ++it1)
    sum += pow(eval(*it1), power);
  for (IloSolutionPool::Iterator it2(pool); it2.ok(); ++it2)
    setEvaluation(*it2, pow(eval(*it2), power) / sum);
}

In the main body, when performing parent selection, we first declare an IloSolutionPoolEvaluator based on a simple IloSolutionEvaluator which collects objective values from solution pools.

Add the following code after the comment
//Evaluate objective values of solutions

    IloSolutionPoolEvaluator parentEvaluator(env, IloSolutionEvaluator(env));

This line constructs a multiple evaluator which evaluates each solution in an entire pool using the objective (which is evaluated using IloSolutionEvaluator). Then you use the PowerEvaluator constructor to square and normalize the objective value.

Add the following code after the comment
//Increases discrepancies between solutions

    parentEvaluator = PowerEvaluator(env, parentEvaluator, 2.0);

You will now create a parent selector using parentEvaluator, and for this you will use a roulette wheel selector. In a roulette wheel selector, the probability for a given solution at index i to be selected is proportional to its evaluation. This selector is known as a roulette wheel selector as each parent evaluation can be viewed as a distance along the circumference of a roulette wheel which is spun to choose a parent.

Add the following code after the comment
//Selects parents depending on their probabilities

    IloRouletteWheelSelector<IloSolution,IloSolutionPool>
      rwsel(env, parentEvaluator);
    IloPoolProc selector = IloSelectSolutions(env, rwsel, IloTrue);

The boolean parameter set to IloTrue indicates that when selecting more than one parent, the same solution cannot be selected more than once. You will see later that the content of this array will be computed using the parentEvaluator object as a preliminary step of the generation goal. Now, you will expand the repertoire of operators. Add one-point and two-point crossover operators, which exchange segments of parent solutions.

Add the following code after the comment //Add 1 and 2 point crossover

    ops.add(BuildGAProcessor(factory.onePointXover("1ptXover")));
    ops.add(BuildGAProcessor(factory.twoPointXover("2ptXover")));

You also add operators which may not directly produce improvements but help maintain the population diversity by moving solution values around.

Add the following code after the comment //Add transposition operators

    ops.add(BuildGAProcessor(factory.swap("swap")));
    ops.add(BuildGAProcessor(factory.translocate("transloc")));

In this example, you will replace only half of the current population with the offspring. You will thus generate only half the number of offspring as the size of the population, ensuring that the population will be kept constant in number.

Add the following code after the comment //Create the reproduction goal

    IloSolutionPool offspring(env, "offspring");
    IloGoal reproduceGoal = IloExecuteProcessor(
      env, population >> selector >> applyOp(populationSize / 2) >> offspring
    );

Here, the genetic operator is instructed to produce populationSize / 2 solutions which are then placed in the offspring pool.

Since you use partial replacement instead of full replacement in this example, you need to define a way to choose which solutions get replaced or become "dead." This can be done using a tournament selector (here, with tournament size 3) and using an IloWorstSolutionComparator which tends to choose bad solutions rather than good ones. The last argument of this selector's factory is a flag (in this case IloTrue) indicating that selected pool elements should appear only once in the selector's output pool (named dead). The selector is not allowed to select the same solution twice.

Add the following code after the comment
//Create the selector of individuals to remove

    IloTournamentSelector<IloSolution,IloSolutionPool> deadSelector(
      env, 3, IloWorstSolutionComparator(env)
    );

Now, you can create the replacement goal.

Add the following code after the comment //Create the replacement goal

    IloGoal replacementGoal = IloExecuteProcessor(env,
      offspring >>
      IloReplaceSolutions(env, population, deadSelector) >>
      IloDestroyAll(env)
    );

The IloReplaceSolutions processor takes its input (the offspring pool), and examines its size n. It then removes n solutions from population, using the deadSelector to select which ones and places them on the output. All solutions on the input are then added to the population. Finally, IloDestroyAll reclaims the memory used by the solutions in its input (that is, those selected for destruction by IloReplaceSolutions).

Finally, you have to add the code that will compute solution values used for selecting parents each generation. This is done by using the IloUpdate goal which will perform the computation specified by PowerEvaluator on values stored in solutions for the count solver variable.

Add the following code after the comment
//Compute parent probabilites before each generation

    generationGoal = IloUpdate(env, parentEvaluator, population)
                  && generationGoal;

You have now learned how to use pool evaluators.

Compile and run the program. You should get the following results:

Problem size: 50
Population size: 50
Max generation: 60
GENERATION 0 WORST 17 BEST 34 AVERAGE 25.06
Optimum value: 50
GENERATION 1 WORST 20 BEST 34 AVERAGE 26.36
 IMPROVEMENT 35 BY IloArrayOnePointXover GENERATION 2
GENERATION 2 WORST 21 BEST 35 AVERAGE 28.26
GENERATION 3 WORST 21 BEST 35 AVERAGE 28.98
GENERATION 4 WORST 23 BEST 35 AVERAGE 30.14
GENERATION 5 WORST 24 BEST 35 AVERAGE 30.9
 IMPROVEMENT 38 BY IloArrayOnePointXover GENERATION 6
GENERATION 6 WORST 23 BEST 38 AVERAGE 31.1
GENERATION 7 WORST 27 BEST 38 AVERAGE 32.44
 IMPROVEMENT 40 BY IloArrayOnePointXover GENERATION 8
GENERATION 8 WORST 31 BEST 40 AVERAGE 33.68
GENERATION 9 WORST 31 BEST 40 AVERAGE 34.46
GENERATION 10 WORST 31 BEST 40 AVERAGE 35.02
 IMPROVEMENT 41 BY IloArrayTwoPointXover GENERATION 11
GENERATION 11 WORST 31 BEST 41 AVERAGE 35.64
 IMPROVEMENT 42 BY IloArrayUniformXover GENERATION 12
GENERATION 12 WORST 30 BEST 42 AVERAGE 36.2
GENERATION 13 WORST 33 BEST 42 AVERAGE 37.4
GENERATION 14 WORST 31 BEST 42 AVERAGE 37.48
GENERATION 15 WORST 32 BEST 42 AVERAGE 37.7
 IMPROVEMENT 44 BY IloArrayUniformXover GENERATION 16
GENERATION 16 WORST 34 BEST 44 AVERAGE 39
GENERATION 17 WORST 36 BEST 44 AVERAGE 39.28
GENERATION 18 WORST 36 BEST 44 AVERAGE 39.88
GENERATION 19 WORST 36 BEST 44 AVERAGE 40.46
GENERATION 20 WORST 36 BEST 44 AVERAGE 41.38
GENERATION 21 WORST 36 BEST 44 AVERAGE 42.06
 IMPROVEMENT 45 BY IloArrayTwoPointXover GENERATION 22
GENERATION 22 WORST 39 BEST 45 AVERAGE 42.4
 IMPROVEMENT 47 BY IloArrayUniformXover GENERATION 23
GENERATION 23 WORST 39 BEST 47 AVERAGE 42.9
GENERATION 24 WORST 39 BEST 47 AVERAGE 43.4
GENERATION 25 WORST 39 BEST 47 AVERAGE 43.62
GENERATION 26 WORST 40 BEST 47 AVERAGE 43.94
GENERATION 27 WORST 40 BEST 47 AVERAGE 43.86
 IMPROVEMENT 48 BY IloArrayTwoPointXover GENERATION 28
GENERATION 28 WORST 39 BEST 48 AVERAGE 44.08
GENERATION 29 WORST 39 BEST 48 AVERAGE 44.66
GENERATION 30 WORST 39 BEST 48 AVERAGE 45.24
GENERATION 31 WORST 38 BEST 48 AVERAGE 45.34
GENERATION 32 WORST 41 BEST 48 AVERAGE 45.82
GENERATION 33 WORST 43 BEST 48 AVERAGE 46.26
 IMPROVEMENT 49 BY IloArrayTwoPointXover GENERATION 34
GENERATION 34 WORST 42 BEST 49 AVERAGE 46.48
GENERATION 35 WORST 44 BEST 49 AVERAGE 46.72
GENERATION 36 WORST 44 BEST 49 AVERAGE 46.86
GENERATION 37 WORST 45 BEST 49 AVERAGE 47.14
GENERATION 38 WORST 45 BEST 49 AVERAGE 47.36
 IMPROVEMENT 50 BY IloArrayOnePointXover GENERATION 39
GENERATION 39 WORST 45 BEST 50 AVERAGE 47.52
OPTIMUM FOUND 
 IloArrayOnePointXover INVOKE 150 SUCCESS 150 IMPROVE 4
 IloArrayTwoPointXover INVOKE 181 SUCCESS 181 IMPROVE 4
 IloArrayUniformXover INVOKE 154 SUCCESS 154 IMPROVE 3
 IloArraySwap INVOKE 153 SUCCESS 153 IMPROVE 0
 IloArrayTranslocate INVOKE 156 SUCCESS 156 IMPROVE 0
 IloArrayMutate INVOKE 181 SUCCESS 181 IMPROVE 0
 
 

The complete program is available in the YourSolverHome/examples/src/ea1max_values.cpp file.