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#if defined(ERX)
39
40static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table);
41static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table);
42static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table);
43
44static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene);
45
46
47/* alloc_edge_table
48 *
49 * allocate memory for edge table
50 *
51 */
52
53Edge *
54alloc_edge_table(PlannerInfo *root, int num_gene)
55{
56 Edge *edge_table;
57
58 /*
59 * palloc one extra location so that nodes numbered 1..n can be indexed
60 * directly; 0 will not be used
61 */
62
63 edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
64
65 return edge_table;
66}
67
68/* free_edge_table
69 *
70 * deallocate memory of edge table
71 *
72 */
73void
74free_edge_table(PlannerInfo *root, Edge *edge_table)
75{
76 pfree(edge_table);
77}
78
79/* gimme_edge_table
80 *
81 * fills a data structure which represents the set of explicit
82 * edges between points in the (2) input genes
83 *
84 * assumes circular tours and bidirectional edges
85 *
86 * gimme_edge() will set "shared" edges to negative values
87 *
88 * returns average number edges/city in range 2.0 - 4.0
89 * where 2.0=homogeneous; 4.0=diverse
90 *
91 */
92float
93gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
94 int num_gene, Edge *edge_table)
95{
96 int i,
97 index1,
98 index2;
99 int edge_total; /* total number of unique edges in two genes */
100
101 /* at first clear the edge table's old data */
102 for (i = 1; i <= num_gene; i++)
103 {
104 edge_table[i].total_edges = 0;
105 edge_table[i].unused_edges = 0;
106 }
107
108 /* fill edge table with new data */
109
110 edge_total = 0;
111
112 for (index1 = 0; index1 < num_gene; index1++)
113 {
114 /*
115 * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operation
116 * maps n back to 1
117 */
118
119 index2 = (index1 + 1) % num_gene;
120
121 /*
122 * edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
123 * twice per edge
124 */
125
126 edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
127 gimme_edge(root, tour1[index2], tour1[index1], edge_table);
128
129 edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
130 gimme_edge(root, tour2[index2], tour2[index1], edge_table);
131 }
132
133 /* return average number of edges per index */
134 return ((float) (edge_total * 2) / (float) num_gene);
135}
136
137/* gimme_edge
138 *
139 * registers edge from city1 to city2 in input edge table
140 *
141 * no assumptions about directionality are made;
142 * therefore it is up to the calling routine to
143 * call gimme_edge twice to make a bi-directional edge
144 * between city1 and city2;
145 * uni-directional edges are possible as well (just call gimme_edge
146 * once with the direction from city1 to city2)
147 *
148 * returns 1 if edge was not already registered and was just added;
149 * 0 if edge was already registered and edge_table is unchanged
150 */
151static int
152gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
153{
154 int i;
155 int edges;
156 int city1 = (int) gene1;
157 int city2 = (int) gene2;
158
159
160 /* check whether edge city1->city2 already exists */
161 edges = edge_table[city1].total_edges;
162
163 for (i = 0; i < edges; i++)
164 {
165 if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
166 {
167
168 /* mark shared edges as negative */
169 edge_table[city1].edge_list[i] = 0 - city2;
170
171 return 0;
172 }
173 }
174
175 /* add city1->city2; */
176 edge_table[city1].edge_list[edges] = city2;
177
178 /* increment the number of edges from city1 */
179 edge_table[city1].total_edges++;
180 edge_table[city1].unused_edges++;
181
182 return 1;
183}
184
185/* gimme_tour
186 *
187 * creates a new tour using edges from the edge table.
188 * priority is given to "shared" edges (i.e. edges which
189 * all parent genes possess and are marked as negative
190 * in the edge table.)
191 *
192 */
193int
194gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
195{
196 int i;
197 int edge_failures = 0;
198
199 /* choose int between 1 and num_gene */
200 new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
201
202 for (i = 1; i < num_gene; i++)
203 {
204 /*
205 * as each point is entered into the tour, remove it from the edge
206 * table
207 */
208
209 remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
210
211 /* find destination for the newly entered point */
212
213 if (edge_table[new_gene[i - 1]].unused_edges > 0)
214 new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
215
216 else
217 { /* cope with fault */
218 edge_failures++;
219
220 new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
221 }
222
223 /* mark this node as incorporated */
224 edge_table[(int) new_gene[i - 1]].unused_edges = -1;
225
226 } /* for (i=1; i<num_gene; i++) */
227
228 return edge_failures;
229
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 */
239static void
240remove_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 = (int) 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 */
281static Gene
282gimme_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
341 } /* for (i=0; i<edge.unused_edges; i++) */
342
343
344 /* random decision of the possible candidates to use */
345 rand_decision = geqo_randint(root, minimum_count - 1, 0);
346
347
348 for (i = 0; i < edge.unused_edges; i++)
349 {
350 friend = (Gene) edge.edge_list[i];
351
352 /* return the chosen candidate point */
353 if (edge_table[(int) friend].unused_edges == minimum_edges)
354 {
355 minimum_count--;
356
357 if (minimum_count == rand_decision)
358 return friend;
359 }
360 }
361
362 /* ... should never be reached */
363 elog(ERROR, "neither shared nor minimum number nor random edge found");
364 return 0; /* to keep the compiler quiet */
365}
366
367/* edge_failure
368 *
369 * routine for handling edge failure
370 *
371 */
372static Gene
373edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
374{
375 int i;
376 Gene fail_gene = gene[index];
377 int remaining_edges = 0;
378 int four_count = 0;
379 int rand_decision;
380
381
382 /*
383 * how many edges remain? how many gene with four total (initial) edges
384 * remain?
385 */
386
387 for (i = 1; i <= num_gene; i++)
388 {
389 if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
390 {
391 remaining_edges++;
392
393 if (edge_table[i].total_edges == 4)
394 four_count++;
395 }
396 }
397
398 /*
399 * random decision of the gene with remaining edges and whose total_edges
400 * == 4
401 */
402
403 if (four_count != 0)
404 {
405
406 rand_decision = geqo_randint(root, four_count - 1, 0);
407
408 for (i = 1; i <= num_gene; i++)
409 {
410
411 if ((Gene) i != fail_gene &&
412 edge_table[i].unused_edges != -1 &&
413 edge_table[i].total_edges == 4)
414 {
415
416 four_count--;
417
418 if (rand_decision == four_count)
419 return (Gene) i;
420 }
421 }
422
423 elog(LOG, "no edge found via random decision and total_edges == 4");
424 }
425 else if (remaining_edges != 0)
426 {
427 /* random decision of the gene with remaining edges */
428 rand_decision = geqo_randint(root, remaining_edges - 1, 0);
429
430 for (i = 1; i <= num_gene; i++)
431 {
432
433 if ((Gene) i != fail_gene &&
434 edge_table[i].unused_edges != -1)
435 {
436
437 remaining_edges--;
438
439 if (rand_decision == remaining_edges)
440 return i;
441 }
442 }
443
444 elog(LOG, "no edge found via random decision with remaining edges");
445 }
446
447 /*
448 * edge table seems to be empty; this happens sometimes on the last point
449 * due to the fact that the first point is removed from the table even
450 * though only one of its edges has been determined
451 */
452
453 else
454 { /* occurs only at the last point in the tour;
455 * simply look for the point which is not yet
456 * used */
457
458 for (i = 1; i <= num_gene; i++)
459 if (edge_table[i].unused_edges >= 0)
460 return (Gene) i;
461
462 elog(LOG, "no edge found via looking for the last unused point");
463 }
464
465
466 /* ... should never be reached */
467 elog(ERROR, "no edge found");
468 return 0; /* to keep the compiler quiet */
469}
470
471#endif /* defined(ERX) */
472