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 * utesch@aut.tu-freiberg.de * 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_recombination.h"
36 #include "optimizer/geqo_random.h"
37
38
39 static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table);
40 static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table);
41 static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table);
42
43 static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene);
44
45
46 /* alloc_edge_table
47 *
48 * allocate memory for edge table
49 *
50 */
51
52 Edge *
alloc_edge_table(PlannerInfo * root,int num_gene)53 alloc_edge_table(PlannerInfo *root, int num_gene)
54 {
55 Edge *edge_table;
56
57 /*
58 * palloc one extra location so that nodes numbered 1..n can be indexed
59 * directly; 0 will not be used
60 */
61
62 edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
63
64 return edge_table;
65 }
66
67 /* free_edge_table
68 *
69 * deallocate memory of edge table
70 *
71 */
72 void
free_edge_table(PlannerInfo * root,Edge * edge_table)73 free_edge_table(PlannerInfo *root, Edge *edge_table)
74 {
75 pfree(edge_table);
76 }
77
78 /* gimme_edge_table
79 *
80 * fills a data structure which represents the set of explicit
81 * edges between points in the (2) input genes
82 *
83 * assumes circular tours and bidirectional edges
84 *
85 * gimme_edge() will set "shared" edges to negative values
86 *
87 * returns average number edges/city in range 2.0 - 4.0
88 * where 2.0=homogeneous; 4.0=diverse
89 *
90 */
91 float
gimme_edge_table(PlannerInfo * root,Gene * tour1,Gene * tour2,int num_gene,Edge * edge_table)92 gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
93 int num_gene, Edge *edge_table)
94 {
95 int i,
96 index1,
97 index2;
98 int edge_total; /* total number of unique edges in two genes */
99
100 /* at first clear the edge table's old data */
101 for (i = 1; i <= num_gene; i++)
102 {
103 edge_table[i].total_edges = 0;
104 edge_table[i].unused_edges = 0;
105 }
106
107 /* fill edge table with new data */
108
109 edge_total = 0;
110
111 for (index1 = 0; index1 < num_gene; index1++)
112 {
113 /*
114 * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operation
115 * maps n back to 1
116 */
117
118 index2 = (index1 + 1) % num_gene;
119
120 /*
121 * edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
122 * twice per edge
123 */
124
125 edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
126 gimme_edge(root, tour1[index2], tour1[index1], edge_table);
127
128 edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
129 gimme_edge(root, tour2[index2], tour2[index1], edge_table);
130 }
131
132 /* return average number of edges per index */
133 return ((float) (edge_total * 2) / (float) num_gene);
134 }
135
136 /* gimme_edge
137 *
138 * registers edge from city1 to city2 in input edge table
139 *
140 * no assumptions about directionality are made;
141 * therefore it is up to the calling routine to
142 * call gimme_edge twice to make a bi-directional edge
143 * between city1 and city2;
144 * uni-directional edges are possible as well (just call gimme_edge
145 * once with the direction from city1 to city2)
146 *
147 * returns 1 if edge was not already registered and was just added;
148 * 0 if edge was already registered and edge_table is unchanged
149 */
150 static int
gimme_edge(PlannerInfo * root,Gene gene1,Gene gene2,Edge * edge_table)151 gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
152 {
153 int i;
154 int edges;
155 int city1 = (int) gene1;
156 int city2 = (int) gene2;
157
158
159 /* check whether edge city1->city2 already exists */
160 edges = edge_table[city1].total_edges;
161
162 for (i = 0; i < edges; i++)
163 {
164 if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
165 {
166
167 /* mark shared edges as negative */
168 edge_table[city1].edge_list[i] = 0 - city2;
169
170 return 0;
171 }
172 }
173
174 /* add city1->city2; */
175 edge_table[city1].edge_list[edges] = city2;
176
177 /* increment the number of edges from city1 */
178 edge_table[city1].total_edges++;
179 edge_table[city1].unused_edges++;
180
181 return 1;
182 }
183
184 /* gimme_tour
185 *
186 * creates a new tour using edges from the edge table.
187 * priority is given to "shared" edges (i.e. edges which
188 * all parent genes possess and are marked as negative
189 * in the edge table.)
190 *
191 */
192 int
gimme_tour(PlannerInfo * root,Edge * edge_table,Gene * new_gene,int num_gene)193 gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
194 {
195 int i;
196 int edge_failures = 0;
197
198 /* choose int between 1 and num_gene */
199 new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
200
201 for (i = 1; i < num_gene; i++)
202 {
203 /*
204 * as each point is entered into the tour, remove it from the edge
205 * table
206 */
207
208 remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
209
210 /* find destination for the newly entered point */
211
212 if (edge_table[new_gene[i - 1]].unused_edges > 0)
213 new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
214
215 else
216 { /* cope with fault */
217 edge_failures++;
218
219 new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
220 }
221
222 /* mark this node as incorporated */
223 edge_table[(int) new_gene[i - 1]].unused_edges = -1;
224
225 } /* for (i=1; i<num_gene; i++) */
226
227 return edge_failures;
228
229 }
230
231 /* remove_gene
232 *
233 * removes input gene from edge_table.
234 * input edge is used
235 * to identify deletion locations within edge table.
236 *
237 */
238 static void
remove_gene(PlannerInfo * root,Gene gene,Edge edge,Edge * edge_table)239 remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
240 {
241 int i,
242 j;
243 int possess_edge;
244 int genes_remaining;
245
246 /*
247 * do for every gene known to have an edge to input gene (i.e. in
248 * edge_list for input edge)
249 */
250
251 for (i = 0; i < edge.unused_edges; i++)
252 {
253 possess_edge = (int) Abs(edge.edge_list[i]);
254 genes_remaining = edge_table[possess_edge].unused_edges;
255
256 /* find the input gene in all edge_lists and delete it */
257 for (j = 0; j < genes_remaining; j++)
258 {
259
260 if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
261 {
262
263 edge_table[possess_edge].unused_edges--;
264
265 edge_table[possess_edge].edge_list[j] =
266 edge_table[possess_edge].edge_list[genes_remaining - 1];
267
268 break;
269 }
270 }
271 }
272 }
273
274 /* gimme_gene
275 *
276 * priority is given to "shared" edges
277 * (i.e. edges which both genes possess)
278 *
279 */
280 static Gene
gimme_gene(PlannerInfo * root,Edge edge,Edge * edge_table)281 gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
282 {
283 int i;
284 Gene friend;
285 int minimum_edges;
286 int minimum_count = -1;
287 int rand_decision;
288
289 /*
290 * no point has edges to more than 4 other points thus, this contrived
291 * minimum will be replaced
292 */
293
294 minimum_edges = 5;
295
296 /* consider candidate destination points in edge list */
297
298 for (i = 0; i < edge.unused_edges; i++)
299 {
300 friend = (Gene) edge.edge_list[i];
301
302 /*
303 * give priority to shared edges that are negative; so return 'em
304 */
305
306 /*
307 * negative values are caught here so we need not worry about
308 * converting to absolute values
309 */
310 if (friend < 0)
311 return (Gene) Abs(friend);
312
313
314 /*
315 * give priority to candidates with fewest remaining unused edges;
316 * find out what the minimum number of unused edges is
317 * (minimum_edges); if there is more than one candidate with the
318 * minimum number of unused edges keep count of this number
319 * (minimum_count);
320 */
321
322 /*
323 * The test for minimum_count can probably be removed at some point
324 * but comments should probably indicate exactly why it is guaranteed
325 * that the test will always succeed the first time around. If it can
326 * fail then the code is in error
327 */
328
329
330 if (edge_table[(int) friend].unused_edges < minimum_edges)
331 {
332 minimum_edges = edge_table[(int) friend].unused_edges;
333 minimum_count = 1;
334 }
335 else if (minimum_count == -1)
336 elog(ERROR, "minimum_count not set");
337 else if (edge_table[(int) friend].unused_edges == minimum_edges)
338 minimum_count++;
339
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
edge_failure(PlannerInfo * root,Gene * gene,int index,Edge * edge_table,int num_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