The GA Procedure

Example 4.2 Nonlinear Objective with Constraints Using Repair Mechanism

This example illustrates the use of a repair mechanism to satisfy problem constraints. The problem is to minimize the six-hump camel-back function (Michalewicz 1996, Appendix B):

$f(x) = \left( 4 - 2.1 x_1^2 + \frac{x_1^4}{3} \right) x_1^2 + x_1 x_2 + \left( -4 + 4 x_2^2 \right) x_2^2$

where $x$ is within the triangle with vertices $V_1 = (-2,0)$ , $V_2 = (0,2)$ , and $V_3 = (2,-2)$ . The problem formulation takes advantage of the fact that all feasible solutions can be expressed as a convex combination of $V_1$ , $V_2$ , and $V_3$ in the following form:

$x = a V_1 + b V_2 + c V_3$

In this form, $a$ , $b$ , and $c$ are nonnegative coefficients and satisfy the following linear equality constraint:

$a + b + c = 1$

Therefore, the solution encoding 'R3' is used with the three elements corresponding to the values of $a$ , $b$ , and $c$ . Note that this strategy can be generalized to any solution domain that can be specified by a convex hull. An additional 'R2' segment is also created to store the corresponding $x$ value. In the following program, FUNCTION SIXHUMP computes the objective value. Lower and upper bounds of 0 and 1, respectively, are used to ensure that solution elements are nonnegative. Violations of the linear equality constraint are fixed by a simple repair strategy, implemented in FUNCTION SIXHUMP: the sum of the solution elements is computed, and each element is divided by the sum, so that the sum of the new elements is 1. For the special case of all elements equal to 0, equal values are assigned to the solution elements.

proc ga seed = 555;
call SetEncoding('R3R2');
npoints = 3;
array cvxhull[3,2] /nosym ( -2 0
                             0 2
                             2 -2 );
/* Objective function */
function sixhump(selected[*],cvxhull[*,*],npoints);
   /* Function has global minimum value of -1.0316
    * at x = {-0.0898  0.7126} and
    *    x = { 0.0898 -0.7126}
    */
   array w[1] /nosym;
   call dynamic_array(w,npoints);
   array x[2] /nosym;
   call ReadMember(selected,1,w);
   /* make sure that weights add up to 1 */
   sum = 0;
   do i = 1 to npoints;
      sum + w[i];
   end;
   /* if all weights 0, then reinitialize */
   if sum=0 then do;
      sum = npoints;
      do i = 1 to npoints;
         w[i] = 1;
      end;
   end;
   /* re-normalize weights */
   do i = 1 to npoints;
      w[i] = w[i] / sum;
   end;
   call WriteMember(selected,1,w);
   /* convert weights to x-coordinate form */
   x[1] = 0;
   x[2] = 0;
   do i = 1 to npoints;
      x[1] + w[i] * cvxhull[i,1];
      x[2] + w[i] * cvxhull[i,2];
   end;
   /* write out x coordinates to second segment */
   call WriteMember(selected,2,x);
   /* compute objective value */
   r = (4 - 2.1*x[1]**2 + x[1]**4/3)*x[1]**2 + x[1]*x[2] +
       (-4 + 4*x[2]**2)*x[2]**2;
   return(r);
endsub;
call SetObjFunc('sixhump',0);
array lower[1] /nosym;
array upper[1] /nosym;
call dynamic_array(lower, npoints);
call dynamic_array(upper, npoints);
do i = 1 to npoints;
   lower[i] = 0;
   upper[i] = 1;
end;
call SetBounds(lower, upper, 1);
array delta[3] /nosym (0.01 0.01 0.01);
call SetMut('delta', 'nchange', 1, 'delta', delta);
call SetMutProb(0.05);
call SetCross('Twopoint', 'alpha', 0.9);
call SetCrossProb(0.8);
call SetSel('tournament', 'size', 2);
call SetElite(3);
call Initialize('DEFAULT', 200);
call ContinueFor(200);
run;

Note that this problem uses the standard genetic operators and default initialization, even though they generate solutions that violate the constraints. This is possible because all solutions are passed into the user objective function for evaluation, where they are repaired to fit the constraints. The output is shown in Output 4.2.1.

Output 4.2.1: Nonlinear Objective with Constraints Using Repair Mechanism

PROC GA Optimum Values

Objective
-1.031617314

Solution
Segment	Element	Value
1	1	0.2439660392
1	2	0.5561415112
1	3	0.1998924497
2	1	-0.088147179
2	2	0.712498123

This objective function has a global minimum at $-1.0316$ , at two different points: $(x_1,x_2) = (-0.0898, 0.7126)$ and $(x_1,x_2) = (0.0898, -0.7126)$ . The genetic algorithm can converge to either of these minima, depending on the random number seed set by the SEED= option.