Example 20.3 Integer Programming Knapsack Problem

The next example uses the integer encoding, along with user modules for crossover and mutation. It formulates the knapsack problem using fixed-length integer encoding. The integer vector solution s is a vector of ones and zeros, where s[i]=1 implies that item i is packed in the knapsack. The weight constraints of the problem are not handled explicitly, but are accounted for by including a penalty for overweight in the objective function. The crossover operator randomly chooses a value for each element of the solution vector from each parent. The mutation operator randomly changes the values of a user-set number of elements in the solution vector. For this problem the value of the global optimum is 18.

proc iml;
weight = {2 3 4 4 1 1 1 1 1 1 1 1 1 1 1};
limit = 9; /* weight limit */
reward = {6 6 6 5 1.3 1.2 1.1 1.0 1.1 1.3 1.0 1.0 0.9 0.8 0.6};

start knapsack( x ) global( weight, reward, limit);
        wsum = sum(weight # x);
        rew = sum(reward # x);
        /* subtract penalty for exceeding weight */
        if wsum>limit then
                rew = rew - 5 * (wsum - limit);
        return(rew);
finish;

start switch_mut(s) global(nswitches);
   n = ncol(s);
   do i = 1 to nswitches;
      k = int(uniform(1234) * n) + 1;
      if s[k]=0 then
            s[k] = 1;
          else
            s[k] = 0;
   end;
finish;

start uniform_cross(child1, child2, parent1, parent2);
    child1 = parent1;
    child2 = parent2;
    do i = 1 to ncol(parent1);
       r = uniform(1234);
       if r<=0.5 then do;
         child1[i] = parent2[i];
         child2[i] = parent1[i];
       end;
    end;
finish;
        
id = gasetup(2,15, 123);
call gasetobj(id, 1, "knapsack"); /* maximize objective module */
call gasetcro(id, 1.0, 0,"uniform_cross"); /* user crossover module */
call gasetmut(id,
              0.20,            /* mutation probabilty */
              0, "switch_mut"  /* user mutation module */
             );
nswitches = 3;
call gasetsel(id, 3,     /* carry 3 over to next generation */
                  1,     /* dual tournament */
                  0.95   /* best-player-wins probabilty */
             );
call gainit(id,100,{0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,
                    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1}); 
niter = 20;
summary = j(niter,2);
mattrib summary [c = {"bestValue", "avgValue"}];
call gagetval(value, id);
summary[1,1] = value[1];
summary[1,2] = value[:];

do i = 1 to niter;
   call garegen(id);
   call gagetval(value, id); 
   summary[i,1] = value[1];
   summary[i,2] = value[:];
end;
call gagetmem(mem, value, id, 1);
print  "best member " mem[f = 1.0 l = ""],
       "best value " value[l = ""];
iteration = t(1:niter);
print iteration summary;
call gaend(id);

The output of the program is

             best member  1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
                    best value         18

                              SUMMARY
                  ITERATION bestValue avgValue

                          1        16      2.44
                          2        16     6.257
                          3        16     6.501
                          4      16.7     7.964
                          5      16.7     8.812
                          6      16.7     9.254
                          7      16.7    10.021
                          8      16.8    11.216
                          9      16.9    12.279
                         10      16.9    12.094
                         11      16.9    11.633
                         12      16.9    11.431
                         13        18    11.502
                         14        18      13.2
                         15        18    13.128
                         16        18    13.282
                         17        18    12.876
                         18        18    13.715
                         19        18    12.889
                         20        18     13.15

Note that for this problem, the mutation parameters are set higher than is often seen for GAs. For this example, this is necessary to prevent premature convergence.