Once the initial population has been generated you can now move on to the construction of the genetic algorithm main loop; each cycle around the loop being termed a generation. Here, in each generation, only one new individual will be generated, and hence in this genetic algorithm, a system of replacement will be used; this will be described later.

First, an intensification method will be introduced. Here, constraint programming is used to improve the quality of the new solutions produced by the genetic algorithm. This is done by adding constraints on the cost which state that any produced solution must be better than the parent or parents that produced it. To avoid stagnation and stalling where it is very difficult to improve on a parent, the improvement rule is only applied probabilistically. Imagine two probabilities p and q. You will stipulate that the newly generated solution must be (strictly) better than the best parent with probability p, otherwise it must be strictly better than the worst parent with probability q. This enforcement is carried out via an operator.

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

ILOIIMOP2(ImproveOn, AnySize, IlcFloat, p, IlcFloat, q) {
  IloSolutionPool pool = getInputPool();
  IloIntVar var = pool.getSolution(0).getObjectiveVar();
  IlcInt limit = IlcIntMax;
  if (getSolver().getRandom().getFloat() < p)
    limit = (IloInt)pool.getBestSolution().getObjectiveValue() - 1;
  else if (getSolver().getRandom().getFloat() < q)
    limit = (IloInt)pool.getWorstSolution().getObjectiveValue() - 1;
  return getSolver().getIntVar(var) <= limit;
}

The operator is relatively straightforward, deciding on limit based on the best and worst solutions in the input pool (which will be the pool of parents when later used). A wrapper to produce an IloPoolProcessor from this operator is provided for you.

The operator factory is now primed such that ImproveOn is called before the invocation of any genetic operator generated by the factory.

Add the following code after the comment
// Enforce probabilistic improvement

  factory.setBeforeOperate(ImproveOn(env, 0.5, 0.9));

The operator dictates that with 50% chance a constraint is added which will insist that the offspring is better than the best parent, and with 45% chance that it is better than the worst parent. A 5% chance remains that the offspring can be equal in quality or worse than the worst parent.

You will now create the genetic operators to be used over the indirect representation.

Add the following code after the comment // Create genetic operators

  IloPoolProcArray ops(env);
  ops.add(factory.mutate(2.0 / problem._numberOfCars, "mutation"));
  ops.add(factory.uniformXover("uxover"));
  ops.add(factory.onePointXover("1ptxo"));

  // Make a processor that will perform a breeding cycle
  IloRandomSelector<IloSolution, IloSolutionPool> randomSelector(env);
  IloPoolProc rndSel = IloSelectSolutions(env, randomSelector, IloTrue);
  IloPoolProc breed = IloSelectProcessor(
    env,
    ops,
    IloRandomSelector<IloPoolProc,IloPoolProcArray>(env)
  );

Here, a pool of processors is created. To this pool is added a mutation operator, which will mutate around two priorities each time it is applied, a uniform crossover operator, and a one-point crossover operator. A breeding operator is then created which applies a random selection of one of the above operators.

The breeding operator will produce a single offspring. After its application, a decision needs to be made on how this new solution is combined into the population: a replacement mechanism is needed. First, you will write the code for the use of the replacement, and then the details of its implementation will be examined.

Add the following code after the comment // Child replaces worst parent

  IloSolutionPool parents(env);
  IloPoolProc replace =
    IloSelectSolutions(env, ReplaceWorstParent(env, pop, parents));
  IloPoolProc destroy = IloDestroyAll(env);
  IloPoolProc replaceAndDestroy = replace >> destroy;

First, a pool to represent the parents selected for a genetic operator is created. Then, a selector is created which will both select a solution for destruction (producing it as output), and produce a side-effect on the population, removing the solution to be replaced and adding the solution that replaces it. The selector is passed the pool of parents because (as you will see) it operates by replacing one of the parent solutions in the population. The solution produced as output by replace will then be destroyed by processor destroy.

Before describing the replacement selector, you will see how all of the processors interact to produce one generation of the genetic algorithm.

Add the following code after the comment
// Create single-generation processor

  IloPoolProc cycle = pop >> rndSel >> parents >> breed(1) >> 
replaceAndDestroy;

The flow is relatively self-explanatory: solutions are selected randomly from the population, and placed in the parents pool; these parents are then bred using an operator chosen at random from the three available; the new solution then replaces a member of the population and the replaced solution is destroyed.

A more subtle point is revealed if we ask ourselves: how do we know how many parents to select from the population? The mutation operator requires only one parent, but the crossover operators need two. This problem is resolved by the manner in which pool processor connection (via >>) operates. Roughly speaking, control flow is right to left while data flow is left to right. This means that replaceAndDestroy is invoked first, which then asks breed for solutions. breed then chooses one of the three available operators, from which it can work out the number of parents needed. It then asks rndSel (indirectly, by passing via the parents pool) for the correct number of parents, which are in turn fetched from pop. At this point the selected solutions can flow back down the chain to the breed pool which creates the offspring which will then be passed to replaceAndDestroy to be merged with the population.