granicus.if.org Git - postgresql/blob - src/backend/optimizer/geqo/geqo_pmx.c

   1 /*------------------------------------------------------------------------
   2 *
   3 * geqo_pmx.c
   4 *
   5 *        partially matched crossover [PMX] routines;
   6 *        PMX operator according to Goldberg & Lingle
   7 *        (Proc Int'l Conf on GA's)
   8 *
   9 * $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_pmx.c,v 1.10 2003/11/29 22:39:49 pgsql Exp $
  10 *
  11 *-------------------------------------------------------------------------
  12 */
  13
  14 /* contributed by:
  15    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  16    *  Martin Utesch                              * Institute of Automatic Control          *
  17    =                                                     = University of Mining and Technology =
  18    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                               *
  19    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  20  */
  21
  22 /* the pmx algorithm is adopted from Genitor : */
  23 /*************************************************************/
  24 /*                                                                                                                       */
  25 /*      Copyright (c) 1990                                                                               */
  26 /*      Darrell L. Whitley                                                                               */
  27 /*      Computer Science Department                                                              */
  28 /*      Colorado State University                                                                */
  29 /*                                                                                                                       */
  30 /*      Permission is hereby granted to copy all or any part of  */
  31 /*      this program for free distribution.   The author's name  */
  32 /*      and this copyright notice must be included in any copy.  */
  33 /*                                                                                                                       */
  34 /*************************************************************/
  35
  36 #include "postgres.h"
  37 #include "optimizer/geqo_random.h"
  38 #include "optimizer/geqo_recombination.h"
  39
  40
  41 /* pmx
  42  *
  43  *       partially matched crossover
  44  */
  45 void
  46 pmx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
  47 {
  48         int                *failed = (int *) palloc((num_gene + 1) * sizeof(int));
  49         int                *from = (int *) palloc((num_gene + 1) * sizeof(int));
  50         int                *indx = (int *) palloc((num_gene + 1) * sizeof(int));
  51         int                *check_list = (int *) palloc((num_gene + 1) * sizeof(int));
  52
  53         int                     left,
  54                                 right,
  55                                 temp,
  56                                 i,
  57                                 j,
  58                                 k;
  59         int                     mx_fail,
  60                                 found,
  61                                 mx_hold;
  62
  63
  64 /* no mutation so start up the pmx replacement algorithm */
  65 /* initialize failed[], from[], check_list[] */
  66         for (k = 0; k < num_gene; k++)
  67         {
  68                 failed[k] = -1;
  69                 from[k] = -1;
  70                 check_list[k + 1] = 0;
  71         }
  72
  73 /* locate crossover points */
  74         left = geqo_randint(num_gene - 1, 0);
  75         right = geqo_randint(num_gene - 1, 0);
  76
  77         if (left > right)
  78         {
  79                 temp = left;
  80                 left = right;
  81                 right = temp;
  82         }
  83
  84
  85 /* copy tour2 into offspring */
  86         for (k = 0; k < num_gene; k++)
  87         {
  88                 offspring[k] = tour2[k];
  89                 from[k] = DAD;
  90                 check_list[tour2[k]]++;
  91         }
  92
  93 /* copy tour1 into offspring */
  94         for (k = left; k <= right; k++)
  95         {
  96                 check_list[offspring[k]]--;
  97                 offspring[k] = tour1[k];
  98                 from[k] = MOM;
  99                 check_list[tour1[k]]++;
 100         }
 101
 102
 103 /* pmx main part */
 104
 105         mx_fail = 0;
 106
 107 /* STEP 1 */
 108
 109         for (k = left; k <= right; k++)
 110         {                                                       /* for all elements in the tour1-2 */
 111
 112                 if (tour1[k] == tour2[k])
 113                         found = 1;                      /* find match in tour2 */
 114
 115                 else
 116                 {
 117                         found = 0;                      /* substitute elements */
 118
 119                         j = 0;
 120                         while (!(found) && (j < num_gene))
 121                         {
 122                                 if ((offspring[j] == tour1[k]) && (from[j] == DAD))
 123                                 {
 124
 125                                         check_list[offspring[j]]--;
 126                                         offspring[j] = tour2[k];
 127                                         found = 1;
 128                                         check_list[tour2[k]]++;
 129                                 }
 130
 131                                 j++;
 132                         }
 133
 134                 }
 135
 136                 if (!(found))
 137                 {                                               /* failed to replace gene */
 138                         failed[mx_fail] = (int) tour1[k];
 139                         indx[mx_fail] = k;
 140                         mx_fail++;
 141                 }
 142
 143         }                                                       /* ... for */
 144
 145
 146 /* STEP 2 */
 147
 148         /* see if any genes could not be replaced */
 149         if (mx_fail > 0)
 150         {
 151                 mx_hold = mx_fail;
 152
 153                 for (k = 0; k < mx_hold; k++)
 154                 {
 155                         found = 0;
 156
 157                         j = 0;
 158                         while (!(found) && (j < num_gene))
 159                         {
 160
 161                                 if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
 162                                 {
 163                                         check_list[offspring[j]]--;
 164                                         offspring[j] = tour2[indx[k]];
 165                                         check_list[tour2[indx[k]]]++;
 166
 167                                         found = 1;
 168                                         failed[k] = -1;
 169                                         mx_fail--;
 170                                 }
 171
 172                                 j++;
 173                         }
 174
 175                 }                                               /* ... for       */
 176
 177         }                                                       /* ... if        */
 178
 179
 180 /* STEP 3 */
 181
 182         for (k = 1; k <= num_gene; k++)
 183         {
 184
 185                 if (check_list[k] > 1)
 186                 {
 187                         i = 0;
 188
 189                         while (i < num_gene)
 190                         {
 191                                 if ((offspring[i] == (Gene) k) && (from[i] == DAD))
 192                                 {
 193                                         j = 1;
 194
 195                                         while (j <= num_gene)
 196                                         {
 197                                                 if (check_list[j] == 0)
 198                                                 {
 199                                                         offspring[i] = (Gene) j;
 200                                                         check_list[k]--;
 201                                                         check_list[j]++;
 202                                                         i = num_gene + 1;
 203                                                         j = i;
 204                                                 }
 205
 206                                                 j++;
 207                                         }
 208
 209                                 }                               /* ... if        */
 210
 211                                 i++;
 212                         }                                       /* end while */
 213
 214                 }
 215         }                                                       /* ... for       */
 216
 217         pfree(failed);
 218         pfree(from);
 219         pfree(indx);
 220         pfree(check_list);
 221 }