The initial population being successfully created, evolution of the solutions in that population can then begin. This evolution is brought about by the application of genetic operators such as mutation and crossover to members of the population. Additionally, here the power and flexibility of constraint programming will be used to inhibit the creation of poor quality solutions. The latter is done by adding constraints to the cost variable before the application of a genetic operator. The idea here is to say that with probability p, the new solution produced is constrained to be better than the worst of the parents. With probability 1-p, the new solution is no worse than the worst parent. (For a mutation operator where there is only one parent, read ``parent'' for ``worst parent.'') This means that children can never be worse than their worst parent in this example. This leads to an intensified search which could in general be damaging as it limits exploration. However, in the case of bin packing, the cost function is not very fine-grained and there are large numbers of different solutions at the same cost. Hence, in this case, such a constraint is not particularly limiting in terms of exploration.

You will write an operator that performs this cost-constraining function.

Add the following code after the comment: // Improve on worst in input pool

ILOIIMOP2(ImproveOn, 1, IloIntVar, used, IlcFloat, p) {
  IloInt limit = (IloInt)getInputPool().getWorstSolution().getValue(used);
  IloSolver solver(getSolver());
  solver.setMax(used, limit - (solver.getRandom().getFloat() < p));
  return 0;
}

This operator is defined by the ILCIIMOP2 macro and takes six parameters. The first parameter is the name of the operator to be created. The second is the minimum number of solutions that the operator requires as input; one solution in this case. Next come the two optional parameters with their types, as for the definition of a goal using the ILCGOAL macro. In this case, these are the cost variable (the number of bins used), and a probability of improvement. Contained in the input pool are the parents of the operator. The above code simply sets an upper bound on the number of bins used which is limit-1 with probability p, and limit with probability 1-p.

You will now move on to the creation of the genetic operators themselves. This lesson creates two genetic operators: a mutation operator and a crossover operator, based on a generic combination operator which can work with arbitrarily many parents. You will write this operator later, but first you will begin with the code which uses it.

The genetic operators used will correspond to a particular form. They will first limit the cost variable using ImproveOn as described above and then enter the operator proper. As you will see later, the operator may not build a complete solution, and so a third part--a completion operator--is required which extends this partial solution to a complete one. This completion operator is none other than the packing goal Pack. The code to build a genetic operator from its three basic components (constrain, mutation or crossover, completion) will be created using the && operator over pool operators. Finally, the complete genetic operators that are built will be limited in their execution to avoid very long times being spent on potentially fruitless search.

Add the following code after the comment: // Genetic operators

  IloPoolOperator improve = ImproveOn(env, used, 0.75);
  IloSearchLimit limit(IloFailLimit(env, 1000));
  IloPoolOperator mutop = PackingOperator(env, 1, load, where, weight, used);
  IloPoolProc mut = IloLimitOperator(env, improve && mutop && packGoal, limit);
  IloPoolProc breed = mut;
  if (popSize > 1) {
    IloPoolProcArray ops(env);
    ops.add(mut);
    IloPoolOperator xoop = PackingOperator(env, 2, load, where, weight, used);
    IloPoolProc xo = IloLimitOperator(env, improve && xoop && packGoal, limit);
    ops.add(xo);
    IloExplicitEvaluator<IloPoolProc> operatorProbs(env);
    operatorProbs.setEvaluation(mut, mutationProb);
    operatorProbs.setEvaluation(xo, 1.0 - mutationProb);
    IloRouletteWheelSelector<IloPoolProc, IloPoolProcArray> opSel(
      env, operatorProbs
    );
    breed = IloSelectProcessor(env, ops, opSel);
  } 

There are a few points to note in the above code. The goal of the code is to produce a pool processor breed capable of taking an input and producing offspring. How this is done depends upon the size of the population; if it has only one member it is via mutation, otherwise it is via a combination of mutation and crossover (combination). The genetic operator PackingOperator, which you will define later, is used to construct both the mutation and crossover operators. The second parameter of this operator is the number of parents to operate over, and it is this parameter that differentiates the mutation and crossover operators. Note that both the mutation and crossover operators are subjected to a modification via the && operator on processors and via IloLimitOperator. These modifications result in operators limited in number of fails and which constrain the cost first (with probability 0.75) and complete the solution after the execution of the main operator. Finally, when both mutation and crossover operators are used, a roulette wheel selector is used to select between them for each new child generated. A roulette wheel selector uses a table of probabilities (or equally non-negative weights, which are normalized internally to give probabilities) to select one item from the given pool. After selection, IloApplyProcessor executes the processor found in the pool of processors given as parameter.