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.