In the previous section, PackingOperator was introduced as the genetic operator used for both mutation and crossover. Here, you will see how you can implement such a genetic operator and also learn how to make such an operator work well by favoring good features in the parents.

The first idea of the genetic operator is to take not single objects, but the contents of entire bins from the parents for inclusion in the child. The advantage of this is that groups of objects that go well together can be maintained in the child. The second idea is that only ``good'' bins are chosen to go into the child; a good bin being one that is filled to the average required load--an idea that will be fully introduced in what follows. The third idea is to pack a randomized number of bins in the operator itself, leaving a randomized number of bins to be packed by the decreasing first fit packing goal; this increases the robustness and exploration capability of the search.

As before, an algorithm will be presented first:

The algorithm picks bins from the parents randomly, packing those which meet the criteria, until the desired number of bins have been packed, or a certain number of tries have been exhausted. Two criteria are used. The first has to do with the feasibility of packing: no bin can be included which contains an item already packed in the child, as no item can be packed in more than one bin. The second has to do with the quality of the bins chosen from the parents; these bins must meet the average load requirement to produce a solution in the number of bins required. That is, only bins which are ``good enough'' are selected.

You are now ready to write the code of the genetic operator. Steps 1-4 of the above algorithm are already coded. You will find the code below:

// A genetic operator over bins
ILOIIMOP5(PackingOperator, numParents,
          IloInt, numParents,
          IloIntVarArray, load,
          IloIntVarArray, where,
          IloIntArray, weight,
          IloIntVar, used) {
  IloSolver solver = getSolver();
  IloInt numItems = weight.getSize();
  IloInt numBins = solver.getMax(used);
  IloSolutionPool parents = getInputPool();
  IloInt numParents = parents.getSize();
  IloInt reqdMeanLoad = (IloSum(weight) + numBins - 1) / numBins;
  IlcRandom rnd = solver.getRandom();
  IloInt targetBin = rnd.getInt(numBins);
  IloInt currentBin = 0;
  IloInt tries = 0;

  while (currentBin < targetBin && tries < numParents * numBins) {

The above code is relatively simple and closely follows algorithmic steps 1-4. However, it is important to point out the parameters of the ILCIIMOP5 macro. Recall that the first two parameters are the name of the operator and the minimum number of parents required. For the ImproveOn operator, this second parameter is the constant 1. However, this parameter can be any general expression, and here the size is equal to numParents, the first optional parameter of the operator. In this way, you can create operators which use a variable number of parents, specified when the operator is constructed.

The above code chooses to set the limit on the number of tries equal to the product of the number of parents and the number of available bins.

You will now add the remaining code which chooses a parent and bin, and inserts its contents into the child.

Insert the following code after the comment: // Pack a single bin

    IloSolution p = parents.getSolution(rnd.getInt(numParents));
    IloInt srcBin = rnd.getInt(p.getValue(used));
    if (p.getValue(load[srcBin]) >= reqdMeanLoad) {
      IloBool fit = IloTrue;
      for (IlcInt i = 0; fit && i < numItems; i++) {
        if (p.getValue(where[i]) == srcBin)
          fit = solver.getIntVar(where[i]).isInDomain(currentBin);
      }
      if (fit) {
        for (IlcInt i = 0; i < numItems; i++) {
          if (p.getValue(where[i]) == srcBin)
            solver.setValue(where[i], currentBin);
        }
        tries = 0;
        currentBin++;
      }
    }
    tries++;

Again, this code closely follows the algorithm. First, a random parent and bin from that parent are selected. Then, given that the load of the chosen bin is sufficient, the code looks to see if all items from the selected bin can be placed in the current bin in the child. This is done by examination of the domains of the variables of the child. (Recall that the purpose of a genetic operator is to take solutions--instances of IloSolution--as input, and to produce as output an instantiation of Solver variables which is the child solution.) This examination is equivalent to testing if the objects from the chosen bin have already been scheduled in the child because if they have been scheduled, they will have a where variable bound to a value strictly less than currentBin. Assuming all objects can go in currentBin, they are placed there via solver.setValue(), the current bin is moved on, and the number of tries is reset.