Genetic Algorithms

Example 17.4: Optimization with Linear Constraints Using Repair Strategy

This problem seeks a minimum within a convex domain specified by a convex hull, a set of points such that all points in the search space are normalized linear combinations of those points. Each solution is represented by a set of weights such that there is one for each point in the convex hull, , and . In this example the feasible region is the convex hull defined by the set of points (-3 -2), (3 -2), (-3 2), and (3 2). The objective function is a six-hump camel-back function (see Michalewicz 1996, Appendix B), with a known global minimum value of -1.0316 at two different points, (-0.0898,0.7126) and (0.0898,-0.7126). A user mutation module is specified, and the simple crossover operator is used. Both the mutation operator and the crossover operator will produce solutions that violate the constraints, so in the objective function each solution will be checked and renormalized to bring it back within the convex hull.

  
 proc iml; 
  
 /* Test case using user modules for the mutation operator and 
  * for initialization 
  */ 
  
 start sixhump(w) global(cvxhull); 
 /* Function has global minimum value of -1.0316 
  * at x = {-0.0898  0.7126} and 
  *    x = { 0.0898 -0.7126} 
  */ 
   sum = w[1,+]; 
  
   /* guard against the remote possibility of all-0 weights */ 
   if sum=0 then do; 
      nc = ncol(w); 
      w = j(1, nc, 1/nc ); 
          sum = 1; 
   end; 
  
   /* re-normalize weights */ 
   w = w/sum; 
  
   /* convert to x-coordinate form */ 
   x = (w * cvxhull)[+,]; 
   x1 = x[1]; 
   x2 = x[2]; 
  
   /* compute objective value */ 
   r = (4 - 2.1*x1##2 + x1##4/3)*x1##2 + x1*x2 + 
        (-4 + 4*x2*x2)*x2##2; 
   return(r); 
 finish; 
  
 /* each row is one point on the boundary of 
  * the convex hull */ 
 cvxhull = {-3 -2, 
             3 -2, 
             -3 2, 
             3 2}; 
  
 /* initialization module */ 
 start cvxinit( w ) global(cvxhull); 
 sum = 0; 
 a = j(1, nrow(cvxhull), 1234); 
 do while(sum = 0); 
   r = uniform(a); 
   sum = r[1,+]; 
 end; 
 w = r / sum; 
 finish; 
  
 /* mutation module */ 
 start cvxmut(w)global(cvxhull); 
   row = int(uniform(1234) * nrow(cvxhull)) + 1; 
   r = uniform(1234); 
   w[1,row] = r; 
 finish; 
  
 id = gasetup(1, /* real fixed-length vector encoding */ 
              nrow(cvxhull), /* vector size = number of points 
                              * specifying convex hull 
                              */ 
              1234); 
 call gasetobj(id, 
                0, /* minimize a user-specified objective function */ 
               "sixhump" 
               ); 
 call gasetsel( id, 
                 5, /* carry over the best 5 from each generation */ 
                 1, /* dual tournament */ 
               0.95  /* best-player-wins probability */ 
              ); 
 call gasetcro(id, 
               0.8, /* crossover probability */ 
               1    /* simple crossover operator */ 
               ); 
 call gasetmut(id,0.05,0,"cvxmut"); 
  
 call gainit( id, 
             100,         /* population size */ 
                ,         /* not using constant bounds */ 
        "cvxinit"         /* initialization module */ 
            ); 
  
 niter = 35; /* number of iterations */ 
 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); 
 bestX = (mem * cvxhull)[+,]; 
 print  "best X " bestX[l = ""], 
        "best value " value[l = ""]; 
 iteration = t(1:niter); 
 print iteration summary; 
 call gaend(id);
 

The output results are

  
                  best X   0.089842 -0.712658 
                      best value  -1.031628 
  
                           SUMMARY 
               ITERATION bestValue avgValue 
  
                       1 -0.082301 0.9235856 
                       2 -0.948434 0.1262678 
                       3 -0.956136 0.2745601 
                       4 -1.017636 0.1367912 
                       5 -1.028457 -0.241069 
                       6 -1.028457 -0.353218 
                       7 -1.028457  -0.56789 
                       8 -1.028457  -0.73044 
                       9 -1.028457 -0.854496 
                      10 -1.028509 -0.941693 
                      11 -1.031334 -0.936541 
                      12 -1.031334  -0.90363 
                      13 -1.031373 -0.774917 
                      14 -1.031614 -0.873418 
                      15 -1.031614 -0.886818 
                      16 -1.031618  -0.95678 
                      17 -1.031619 -0.933061 
                      18 -1.031626 -0.885132 
                      19 -1.031628 -0.936944 
                      20 -1.031628 -0.906637 
                      21 -1.031628 -0.925809 
                      22 -1.031628 -0.860156 
                      23 -1.031628 -0.946146 
                      24 -1.031628 -0.817196 
                      25 -1.031628 -0.883284 
                      26 -1.031628 -0.904361 
                      27 -1.031628 -0.974893 
                      28 -1.031628 -0.975647 
                      29 -1.031628 -0.872004 
                      30 -1.031628 -1.031628 
                      31 -1.031628 -0.897558 
                      32 -1.031628 -0.922121 
                      33 -1.031628 -0.855045 
                      34 -1.031628 -0.922061 
                      35 -1.031628 -0.958257
 

Any problem with linear constraints could be formulated in this way, by determining the convex hull corresponding to the constraints. The genetic operators and the repair strategy are straightforward to apply, and as this case shows, can give reasonable convergence to a global optimum.