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 * src/backend/optimizer/geqo/geqo_pmx.c 10 * 11 *------------------------------------------------------------------------- 12 */ 13 14 /* contributed by: 15 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= 16 * Martin Utesch * Institute of Automatic Control * 17 = = University of Mining and Technology = default_boost::parameter::aux::default_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 #if defined(PMX) 41 42 /* pmx 43 * 44 * partially matched crossover 45 */ 46 void 47 pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene) 48 { 49 int *failed = (int *) palloc((num_gene + 1) * sizeof(int)); 50 int *from = (int *) palloc((num_gene + 1) * sizeof(int)); 51 int *indx = (int *) palloc((num_gene + 1) * sizeof(int)); 52 int *check_list = (int *) palloc((num_gene + 1) * sizeof(int)); 53 54 int left, 55 right, 56 temp, 57 i, 58 j, 59 k; 60 int mx_fail, 61 found, 62 mx_hold; 63 64 65 /* no mutation so start up the pmx replacement algorithm */ 66 /* initialize failed[], from[], check_list[] */ 67 for (k = 0; k < num_gene; k++) 68 { 69 failed[k] = -1; 70 from[k] = -1; 71 check_list[k + 1] = 0; 72 } 73 74 /* locate crossover points */ 75 left = geqo_randint(root, num_gene - 1, 0); 76 right = geqo_randint(root, num_gene - 1, 0); 77 78 if (left > right) 79 { 80 temp = left; 81 left = right; 82 right = temp; 83 } 84 85 86 /* copy tour2 into offspring */ 87 for (k = 0; k < num_gene; k++) 88 { 89 offspring[k] = tour2[k]; 90 from[k] = DAD; 91 check_list[tour2[k]]++; 92 } 93 94 /* copy tour1 into offspring */ 95 for (k = left; k <= right; k++) 96 { 97 check_list[offspring[k]]--; 98 offspring[k] = tour1[k]; 99 from[k] = MOM; 100 check_list[tour1[k]]++; 101 } 102 103 104 /* pmx main part */ 105 106 mx_fail = 0; 107 108 /* STEP 1 */ 109 110 for (k = left; k <= right; k++) 111 { /* for all elements in the tour1-2 */ 112 113 if (tour1[k] == tour2[k]) 114 found = 1; /* find match in tour2 */ 115 116 else 117 { 118 found = 0; /* substitute elements */ 119 120 j = 0; 121 while (!(found) && (j < num_gene)) 122 { 123 if ((offspring[j] == tour1[k]) && (from[j] == DAD)) 124 { 125 126 check_list[offspring[j]]--; 127 offspring[j] = tour2[k]; 128 found = 1; 129 check_list[tour2[k]]++; 130 } 131 132 j++; 133 } 134 135 } 136 137 if (!(found)) 138 { /* failed to replace gene */ 139 failed[mx_fail] = (int) tour1[k]; 140 indx[mx_fail] = k; 141 mx_fail++; 142 } 143 144 } /* ... for */ 145 146 147 /* STEP 2 */ 148 149 /* see if any genes could not be replaced */ 150 if (mx_fail > 0) 151 { 152 mx_hold = mx_fail; 153 154 for (k = 0; k < mx_hold; k++) 155 { 156 found = 0; 157 158 j = 0; 159 while (!(found) && (j < num_gene)) 160 { 161 162 if ((failed[k] == (int) offspring[j]) && (from[j] == DAD)) 163 { 164 check_list[offspring[j]]--; 165 offspring[j] = tour2[indx[k]]; 166 check_list[tour2[indx[k]]]++; 167 168 found = 1; 169 failed[k] = -1; 170 mx_fail--; 171 } 172 173 j++; 174 } 175 176 } /* ... for */ 177 178 } /* ... if */ 179 180 181 /* STEP 3 */ 182 183 for (k = 1; k <= num_gene; k++) 184 { 185 186 if (check_list[k] > 1) 187 { 188 i = 0; 189 190 while (i < num_gene) 191 { 192 if ((offspring[i] == (Gene) k) && (from[i] == DAD)) 193 { 194 j = 1; 195 196 while (j <= num_gene) 197 { 198 if (check_list[j] == 0) 199 { 200 offspring[i] = (Gene) j; 201 check_list[k]--; 202 check_list[j]++; 203 i = num_gene + 1; 204 j = i; 205 } 206 207 j++; 208 } 209 210 } /* ... if */ 211 212 i++; 213 } /* end while */ 214 215 } 216 } /* ... for */ 217 218 pfree(failed); 219 pfree(from); 220 pfree(indx); 221 pfree(check_list); 222 } 223 224 #endif /* defined(PMX) */ 225