| 1 |
/*------------------------------------------------------------------------ |
| 2 |
* |
| 3 |
* geqo_erx.c |
| 4 |
* edge recombination crossover [ER] |
| 5 |
* |
| 6 |
* src/backend/optimizer/geqo/geqo_erx.c |
| 7 |
* |
| 8 |
*------------------------------------------------------------------------- |
| 9 |
*/ |
| 10 |
|
| 11 |
/* contributed by: |
| 12 |
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= |
| 13 |
* Martin Utesch * Institute of Automatic Control * |
| 14 |
= = University of Mining and Technology = |
| 15 |
* [email protected] * Freiberg, Germany * |
| 16 |
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= |
| 17 |
*/ |
| 18 |
|
| 19 |
/* the edge recombination algorithm is adopted from Genitor : */ |
| 20 |
/*************************************************************/ |
| 21 |
/* */ |
| 22 |
/* Copyright (c) 1990 */ |
| 23 |
/* Darrell L. Whitley */ |
| 24 |
/* Computer Science Department */ |
| 25 |
/* Colorado State University */ |
| 26 |
/* */ |
| 27 |
/* Permission is hereby granted to copy all or any part of */ |
| 28 |
/* this program for free distribution. The author's name */ |
| 29 |
/* and this copyright notice must be included in any copy. */ |
| 30 |
/* */ |
| 31 |
/*************************************************************/ |
| 32 |
|
| 33 |
|
| 34 |
#include "postgres.h" |
| 35 |
#include "optimizer/geqo.h" |
| 36 |
|
| 37 |
#if defined(ERX) |
| 38 |
|
| 39 |
#include "optimizer/geqo_random.h" |
| 40 |
#include "optimizer/geqo_recombination.h" |
| 41 |
|
| 42 |
static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table); |
| 43 |
static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table); |
| 44 |
static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table); |
| 45 |
|
| 46 |
static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene); |
| 47 |
|
| 48 |
|
| 49 |
/* alloc_edge_table |
| 50 |
* |
| 51 |
* allocate memory for edge table |
| 52 |
* |
| 53 |
*/ |
| 54 |
|
| 55 |
Edge * |
| 56 |
alloc_edge_table(PlannerInfo *root, int num_gene) |
| 57 |
{ |
| 58 |
Edge *edge_table; |
| 59 |
|
| 60 |
/* |
| 61 |
* palloc one extra location so that nodes numbered 1..n can be indexed |
| 62 |
* directly; 0 will not be used |
| 63 |
*/ |
| 64 |
|
| 65 |
edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge)); |
| 66 |
|
| 67 |
return edge_table; |
| 68 |
} |
| 69 |
|
| 70 |
/* free_edge_table |
| 71 |
* |
| 72 |
* deallocate memory of edge table |
| 73 |
* |
| 74 |
*/ |
| 75 |
void |
| 76 |
free_edge_table(PlannerInfo *root, Edge *edge_table) |
| 77 |
{ |
| 78 |
pfree(edge_table); |
| 79 |
} |
| 80 |
|
| 81 |
/* gimme_edge_table |
| 82 |
* |
| 83 |
* fills a data structure which represents the set of explicit |
| 84 |
* edges between points in the (2) input genes |
| 85 |
* |
| 86 |
* assumes circular tours and bidirectional edges |
| 87 |
* |
| 88 |
* gimme_edge() will set "shared" edges to negative values |
| 89 |
* |
| 90 |
* returns average number edges/city in range 2.0 - 4.0 |
| 91 |
* where 2.0=homogeneous; 4.0=diverse |
| 92 |
* |
| 93 |
*/ |
| 94 |
float |
| 95 |
gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2, |
| 96 |
int num_gene, Edge *edge_table) |
| 97 |
{ |
| 98 |
int i, |
| 99 |
index1, |
| 100 |
index2; |
| 101 |
int edge_total; /* total number of unique edges in two genes */ |
| 102 |
|
| 103 |
/* at first clear the edge table's old data */ |
| 104 |
for (i = 1; i <= num_gene; i++) |
| 105 |
{ |
| 106 |
edge_table[i].total_edges = 0; |
| 107 |
edge_table[i].unused_edges = 0; |
| 108 |
} |
| 109 |
|
| 110 |
/* fill edge table with new data */ |
| 111 |
|
| 112 |
edge_total = 0; |
| 113 |
|
| 114 |
for (index1 = 0; index1 < num_gene; index1++) |
| 115 |
{ |
| 116 |
/* |
| 117 |
* presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operation |
| 118 |
* maps n back to 1 |
| 119 |
*/ |
| 120 |
|
| 121 |
index2 = (index1 + 1) % num_gene; |
| 122 |
|
| 123 |
/* |
| 124 |
* edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge |
| 125 |
* twice per edge |
| 126 |
*/ |
| 127 |
|
| 128 |
edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table); |
| 129 |
gimme_edge(root, tour1[index2], tour1[index1], edge_table); |
| 130 |
|
| 131 |
edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table); |
| 132 |
gimme_edge(root, tour2[index2], tour2[index1], edge_table); |
| 133 |
} |
| 134 |
|
| 135 |
/* return average number of edges per index */ |
| 136 |
return ((float) (edge_total * 2) / (float) num_gene); |
| 137 |
} |
| 138 |
|
| 139 |
/* gimme_edge |
| 140 |
* |
| 141 |
* registers edge from city1 to city2 in input edge table |
| 142 |
* |
| 143 |
* no assumptions about directionality are made; |
| 144 |
* therefore it is up to the calling routine to |
| 145 |
* call gimme_edge twice to make a bi-directional edge |
| 146 |
* between city1 and city2; |
| 147 |
* uni-directional edges are possible as well (just call gimme_edge |
| 148 |
* once with the direction from city1 to city2) |
| 149 |
* |
| 150 |
* returns 1 if edge was not already registered and was just added; |
| 151 |
* 0 if edge was already registered and edge_table is unchanged |
| 152 |
*/ |
| 153 |
static int |
| 154 |
gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table) |
| 155 |
{ |
| 156 |
int i; |
| 157 |
int edges; |
| 158 |
int city1 = (int) gene1; |
| 159 |
int city2 = (int) gene2; |
| 160 |
|
| 161 |
|
| 162 |
/* check whether edge city1->city2 already exists */ |
| 163 |
edges = edge_table[city1].total_edges; |
| 164 |
|
| 165 |
for (i = 0; i < edges; i++) |
| 166 |
{ |
| 167 |
if ((Gene) abs(edge_table[city1].edge_list[i]) == city2) |
| 168 |
{ |
| 169 |
|
| 170 |
/* mark shared edges as negative */ |
| 171 |
edge_table[city1].edge_list[i] = 0 - city2; |
| 172 |
|
| 173 |
return 0; |
| 174 |
} |
| 175 |
} |
| 176 |
|
| 177 |
/* add city1->city2; */ |
| 178 |
edge_table[city1].edge_list[edges] = city2; |
| 179 |
|
| 180 |
/* increment the number of edges from city1 */ |
| 181 |
edge_table[city1].total_edges++; |
| 182 |
edge_table[city1].unused_edges++; |
| 183 |
|
| 184 |
return 1; |
| 185 |
} |
| 186 |
|
| 187 |
/* gimme_tour |
| 188 |
* |
| 189 |
* creates a new tour using edges from the edge table. |
| 190 |
* priority is given to "shared" edges (i.e. edges which |
| 191 |
* all parent genes possess and are marked as negative |
| 192 |
* in the edge table.) |
| 193 |
* |
| 194 |
*/ |
| 195 |
int |
| 196 |
gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene) |
| 197 |
{ |
| 198 |
int i; |
| 199 |
int edge_failures = 0; |
| 200 |
|
| 201 |
/* choose int between 1 and num_gene */ |
| 202 |
new_gene[0] = (Gene) geqo_randint(root, num_gene, 1); |
| 203 |
|
| 204 |
for (i = 1; i < num_gene; i++) |
| 205 |
{ |
| 206 |
/* |
| 207 |
* as each point is entered into the tour, remove it from the edge |
| 208 |
* table |
| 209 |
*/ |
| 210 |
|
| 211 |
remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table); |
| 212 |
|
| 213 |
/* find destination for the newly entered point */ |
| 214 |
|
| 215 |
if (edge_table[new_gene[i - 1]].unused_edges > 0) |
| 216 |
new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table); |
| 217 |
|
| 218 |
else |
| 219 |
{ /* cope with fault */ |
| 220 |
edge_failures++; |
| 221 |
|
| 222 |
new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene); |
| 223 |
} |
| 224 |
|
| 225 |
/* mark this node as incorporated */ |
| 226 |
edge_table[(int) new_gene[i - 1]].unused_edges = -1; |
| 227 |
} /* for (i=1; i<num_gene; i++) */ |
| 228 |
|
| 229 |
return edge_failures; |
| 230 |
} |
| 231 |
|
| 232 |
/* remove_gene |
| 233 |
* |
| 234 |
* removes input gene from edge_table. |
| 235 |
* input edge is used |
| 236 |
* to identify deletion locations within edge table. |
| 237 |
* |
| 238 |
*/ |
| 239 |
static void |
| 240 |
remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table) |
| 241 |
{ |
| 242 |
int i, |
| 243 |
j; |
| 244 |
int possess_edge; |
| 245 |
int genes_remaining; |
| 246 |
|
| 247 |
/* |
| 248 |
* do for every gene known to have an edge to input gene (i.e. in |
| 249 |
* edge_list for input edge) |
| 250 |
*/ |
| 251 |
|
| 252 |
for (i = 0; i < edge.unused_edges; i++) |
| 253 |
{ |
| 254 |
possess_edge = abs(edge.edge_list[i]); |
| 255 |
genes_remaining = edge_table[possess_edge].unused_edges; |
| 256 |
|
| 257 |
/* find the input gene in all edge_lists and delete it */ |
| 258 |
for (j = 0; j < genes_remaining; j++) |
| 259 |
{ |
| 260 |
|
| 261 |
if ((Gene) abs(edge_table[possess_edge].edge_list[j]) == gene) |
| 262 |
{ |
| 263 |
|
| 264 |
edge_table[possess_edge].unused_edges--; |
| 265 |
|
| 266 |
edge_table[possess_edge].edge_list[j] = |
| 267 |
edge_table[possess_edge].edge_list[genes_remaining - 1]; |
| 268 |
|
| 269 |
break; |
| 270 |
} |
| 271 |
} |
| 272 |
} |
| 273 |
} |
| 274 |
|
| 275 |
/* gimme_gene |
| 276 |
* |
| 277 |
* priority is given to "shared" edges |
| 278 |
* (i.e. edges which both genes possess) |
| 279 |
* |
| 280 |
*/ |
| 281 |
static Gene |
| 282 |
gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table) |
| 283 |
{ |
| 284 |
int i; |
| 285 |
Gene friend; |
| 286 |
int minimum_edges; |
| 287 |
int minimum_count = -1; |
| 288 |
int rand_decision; |
| 289 |
|
| 290 |
/* |
| 291 |
* no point has edges to more than 4 other points thus, this contrived |
| 292 |
* minimum will be replaced |
| 293 |
*/ |
| 294 |
|
| 295 |
minimum_edges = 5; |
| 296 |
|
| 297 |
/* consider candidate destination points in edge list */ |
| 298 |
|
| 299 |
for (i = 0; i < edge.unused_edges; i++) |
| 300 |
{ |
| 301 |
friend = (Gene) edge.edge_list[i]; |
| 302 |
|
| 303 |
/* |
| 304 |
* give priority to shared edges that are negative; so return 'em |
| 305 |
*/ |
| 306 |
|
| 307 |
/* |
| 308 |
* negative values are caught here so we need not worry about |
| 309 |
* converting to absolute values |
| 310 |
*/ |
| 311 |
if (friend < 0) |
| 312 |
return (Gene) abs(friend); |
| 313 |
|
| 314 |
|
| 315 |
/* |
| 316 |
* give priority to candidates with fewest remaining unused edges; |
| 317 |
* find out what the minimum number of unused edges is |
| 318 |
* (minimum_edges); if there is more than one candidate with the |
| 319 |
* minimum number of unused edges keep count of this number |
| 320 |
* (minimum_count); |
| 321 |
*/ |
| 322 |
|
| 323 |
/* |
| 324 |
* The test for minimum_count can probably be removed at some point |
| 325 |
* but comments should probably indicate exactly why it is guaranteed |
| 326 |
* that the test will always succeed the first time around. If it can |
| 327 |
* fail then the code is in error |
| 328 |
*/ |
| 329 |
|
| 330 |
|
| 331 |
if (edge_table[(int) friend].unused_edges < minimum_edges) |
| 332 |
{ |
| 333 |
minimum_edges = edge_table[(int) friend].unused_edges; |
| 334 |
minimum_count = 1; |
| 335 |
} |
| 336 |
else if (minimum_count == -1) |
| 337 |
elog(ERROR, "minimum_count not set"); |
| 338 |
else if (edge_table[(int) friend].unused_edges == minimum_edges) |
| 339 |
minimum_count++; |
| 340 |
} /* for (i=0; i<edge.unused_edges; i++) */ |
| 341 |
|
| 342 |
|
| 343 |
/* random decision of the possible candidates to use */ |
| 344 |
rand_decision = geqo_randint(root, minimum_count - 1, 0); |
| 345 |
|
| 346 |
|
| 347 |
for (i = 0; i < edge.unused_edges; i++) |
| 348 |
{ |
| 349 |
friend = (Gene) edge.edge_list[i]; |
| 350 |
|
| 351 |
/* return the chosen candidate point */ |
| 352 |
if (edge_table[(int) friend].unused_edges == minimum_edges) |
| 353 |
{ |
| 354 |
minimum_count--; |
| 355 |
|
| 356 |
if (minimum_count == rand_decision) |
| 357 |
return friend; |
| 358 |
} |
| 359 |
} |
| 360 |
|
| 361 |
/* ... should never be reached */ |
| 362 |
elog(ERROR, "neither shared nor minimum number nor random edge found"); |
| 363 |
return 0; /* to keep the compiler quiet */ |
| 364 |
} |
| 365 |
|
| 366 |
/* edge_failure |
| 367 |
* |
| 368 |
* routine for handling edge failure |
| 369 |
* |
| 370 |
*/ |
| 371 |
static Gene |
| 372 |
edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene) |
| 373 |
{ |
| 374 |
int i; |
| 375 |
Gene fail_gene = gene[index]; |
| 376 |
int remaining_edges = 0; |
| 377 |
int four_count = 0; |
| 378 |
int rand_decision; |
| 379 |
|
| 380 |
|
| 381 |
/* |
| 382 |
* how many edges remain? how many gene with four total (initial) edges |
| 383 |
* remain? |
| 384 |
*/ |
| 385 |
|
| 386 |
for (i = 1; i <= num_gene; i++) |
| 387 |
{ |
| 388 |
if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene)) |
| 389 |
{ |
| 390 |
remaining_edges++; |
| 391 |
|
| 392 |
if (edge_table[i].total_edges == 4) |
| 393 |
four_count++; |
| 394 |
} |
| 395 |
} |
| 396 |
|
| 397 |
/* |
| 398 |
* random decision of the gene with remaining edges and whose total_edges |
| 399 |
* == 4 |
| 400 |
*/ |
| 401 |
|
| 402 |
if (four_count != 0) |
| 403 |
{ |
| 404 |
|
| 405 |
rand_decision = geqo_randint(root, four_count - 1, 0); |
| 406 |
|
| 407 |
for (i = 1; i <= num_gene; i++) |
| 408 |
{ |
| 409 |
|
| 410 |
if ((Gene) i != fail_gene && |
| 411 |
edge_table[i].unused_edges != -1 && |
| 412 |
edge_table[i].total_edges == 4) |
| 413 |
{ |
| 414 |
|
| 415 |
four_count--; |
| 416 |
|
| 417 |
if (rand_decision == four_count) |
| 418 |
return (Gene) i; |
| 419 |
} |
| 420 |
} |
| 421 |
|
| 422 |
elog(LOG, "no edge found via random decision and total_edges == 4"); |
| 423 |
} |
| 424 |
else if (remaining_edges != 0) |
| 425 |
{ |
| 426 |
/* random decision of the gene with remaining edges */ |
| 427 |
rand_decision = geqo_randint(root, remaining_edges - 1, 0); |
| 428 |
|
| 429 |
for (i = 1; i <= num_gene; i++) |
| 430 |
{ |
| 431 |
|
| 432 |
if ((Gene) i != fail_gene && |
| 433 |
edge_table[i].unused_edges != -1) |
| 434 |
{ |
| 435 |
|
| 436 |
remaining_edges--; |
| 437 |
|
| 438 |
if (rand_decision == remaining_edges) |
| 439 |
return i; |
| 440 |
} |
| 441 |
} |
| 442 |
|
| 443 |
elog(LOG, "no edge found via random decision with remaining edges"); |
| 444 |
} |
| 445 |
|
| 446 |
/* |
| 447 |
* edge table seems to be empty; this happens sometimes on the last point |
| 448 |
* due to the fact that the first point is removed from the table even |
| 449 |
* though only one of its edges has been determined |
| 450 |
*/ |
| 451 |
|
| 452 |
else |
| 453 |
{ /* occurs only at the last point in the tour; |
| 454 |
* simply look for the point which is not yet |
| 455 |
* used */ |
| 456 |
|
| 457 |
for (i = 1; i <= num_gene; i++) |
| 458 |
if (edge_table[i].unused_edges >= 0) |
| 459 |
return (Gene) i; |
| 460 |
|
| 461 |
elog(LOG, "no edge found via looking for the last unused point"); |
| 462 |
} |
| 463 |
|
| 464 |
|
| 465 |
/* ... should never be reached */ |
| 466 |
elog(ERROR, "no edge found"); |
| 467 |
return 0; /* to keep the compiler quiet */ |
| 468 |
} |
| 469 |
|
| 470 |
#endif /* defined(ERX) */ |