Genetic Algorithms

Example 17.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.