The GA Procedure

Defining a User Fitness Comparison Routine

Most of the selection techniques used in this procedure require comparisons of fitness to decide which solutions should be propagated into the next generation. Normally fitness is directly related to the solution objective value, with the better objective value indicating the higher fitness. However, sometimes it is useful to base fitness on multiple criteria, not just a single calculated objective value. Doing so enables you to solve multiobjective optimization problems, or to find optima that also satisfy secondary objectives. For example, for a multiobjective problem you might want to find a set of construction schedules that simultaneously minimize completion time and minimize cost, so that you can examine the tradeoff between the two objectives and choose a schedule that best meets your needs. You might also have a scheduling problem where there is more than one solution that meets your primary objective, but you would like to converge on the one that also provides adequate worker breaks, or minimizes overtime. One single-valued objective function might not be adequate to express these preferences.

You can define a function and designate that function to be used for comparing the fitness of two competing solutions with the call

call SetCompareRoutine( 'routine');

where routine is the name of the function you have defined. The function name must be a quoted string. The first parameter of the function, designated the selection parameter, must be a numeric array. The procedure calls your compare function whenever it needs to compare the fitness of two solutions. Your function can also have an arbitrary number of additional parameters, whose names and data types should match variables defined in the global portion of your input. When the procedure calls your function, the selection parameter will be filled in with information identifying which solutions are to be compared, and any other parameters will be filled in with the corresponding global symbol values. Your function should not alter the selection parameter in any way, but pass it unchanged into a ReadCompare Call to obtain the solution elements your program needs to compare the fitness. If solution 1 has higher fitness than solution 2, then your function should return a positive number. If solution 2 is more fit than solution 1, then a negative number should be returned. If the two solutions have the same fitness then a value of 0 might be returned. Following is a simple example of a fitness comparison function.

   /* This function is designed to maximize a
    * primary and secondary objective. The objectives
    * are stored in segment 2 of the encoding. If
    * the difference in primary objective is less than
    * the value of delta, then the secondary objective
    * is used to determine the fitness
    */
   function compare2(selected[*], delta);
  
   /* arrays to hold solution elements */
   array member1[2] /nosym;
   array member2[2] /nosym;

   /* read segment 2 of solution 1 into member1 */
   call ReadCompare(selected, 2, 1, member1); 
 
   /* read segment 2 of solution 2 into member2 */
   call ReadCompare(selected, 2, 2, member2); 

   /* element 1 contains the primary objective value, */
   /* element 2 contains a secondary objective value  */

   /* if objective 1 is nearly the same, then use */
   /* objective 2 to compare the fitness          */
   if( abs(member1[1] - member2[1]) < delta) then do;
     /* primary objectives are nearly the same, check secondary */
     if(member1[2] > member2[2]) then
       return(1);
     if(member2[2] > member1[2]) then
       return(-1);
   end;

   /* base fitness on primary objective */
   if(member1[1] > member2[1]) then
     return(1);
   if(member2[1] > member1[1]) then
     return(-1);

   /* all objectives are the same, return 0 */
   return(0);
   endsub;

   /* in global scope of the input */
   delta = 0.01;
   call SetCompareRoutine('compare2');

For an example of a comparison routine used in a multiobjective optimization, see Example 3.3.