Age Owner Branch data TLA Line data Source code
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.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 *
5386 tgl@sss.pgh.pa.us 56 :CBC 3 : 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 : :
9716 bruce@momjian.us 65 : 3 : edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
66 : :
9357 67 : 3 : return edge_table;
68 : : }
69 : :
70 : : /* free_edge_table
71 : : *
72 : : * deallocate memory of edge table
73 : : *
74 : : */
75 : : void
5386 tgl@sss.pgh.pa.us 76 : 3 : free_edge_table(PlannerInfo *root, Edge *edge_table)
77 : : {
9716 bruce@momjian.us 78 : 3 : pfree(edge_table);
79 : 3 : }
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
5386 tgl@sss.pgh.pa.us 95 : 192 : 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 */
9716 bruce@momjian.us 104 [ + + ]: 1152 : for (i = 1; i <= num_gene; i++)
105 : : {
106 : 960 : edge_table[i].total_edges = 0;
107 : 960 : edge_table[i].unused_edges = 0;
108 : : }
109 : :
110 : : /* fill edge table with new data */
111 : :
112 : 192 : edge_total = 0;
113 : :
114 [ + + ]: 1152 : 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 : 960 : 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 : :
5386 tgl@sss.pgh.pa.us 128 : 960 : edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
129 : 960 : gimme_edge(root, tour1[index2], tour1[index1], edge_table);
130 : :
131 : 960 : edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
132 : 960 : gimme_edge(root, tour2[index2], tour2[index1], edge_table);
133 : : }
134 : :
135 : : /* return average number of edges per index */
9357 bruce@momjian.us 136 : 192 : 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
5386 tgl@sss.pgh.pa.us 154 : 3840 : gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
155 : : {
156 : : int i;
157 : : int edges;
9715 bruce@momjian.us 158 : 3840 : int city1 = (int) gene1;
159 : 3840 : int city2 = (int) gene2;
160 : :
161 : :
162 : : /* check whether edge city1->city2 already exists */
9716 163 : 3840 : edges = edge_table[city1].total_edges;
164 : :
165 [ + + ]: 6759 : for (i = 0; i < edges; i++)
166 : : {
555 peter@eisentraut.org 167 [ + + ]: 4257 : if ((Gene) abs(edge_table[city1].edge_list[i]) == city2)
168 : : {
169 : :
170 : : /* mark shared edges as negative */
9716 bruce@momjian.us 171 : 1338 : edge_table[city1].edge_list[i] = 0 - city2;
172 : :
9357 173 : 1338 : return 0;
174 : : }
175 : : }
176 : :
177 : : /* add city1->city2; */
9716 178 : 2502 : edge_table[city1].edge_list[edges] = city2;
179 : :
180 : : /* increment the number of edges from city1 */
181 : 2502 : edge_table[city1].total_edges++;
182 : 2502 : edge_table[city1].unused_edges++;
183 : :
9357 184 : 2502 : 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
5386 tgl@sss.pgh.pa.us 196 : 192 : gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
197 : : {
198 : : int i;
9715 bruce@momjian.us 199 : 192 : int edge_failures = 0;
200 : :
201 : : /* choose int between 1 and num_gene */
5386 tgl@sss.pgh.pa.us 202 : 192 : new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
203 : :
9716 bruce@momjian.us 204 [ + + ]: 960 : 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 : :
5386 tgl@sss.pgh.pa.us 211 : 768 : 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 : :
9716 bruce@momjian.us 215 [ + - ]: 768 : if (edge_table[new_gene[i - 1]].unused_edges > 0)
5386 tgl@sss.pgh.pa.us 216 : 768 : new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
217 : :
218 : : else
219 : : { /* cope with fault */
9716 bruce@momjian.us 220 :UBC 0 : edge_failures++;
221 : :
5386 tgl@sss.pgh.pa.us 222 : 0 : new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
223 : : }
224 : :
225 : : /* mark this node as incorporated */
9716 bruce@momjian.us 226 :CBC 768 : edge_table[(int) new_gene[i - 1]].unused_edges = -1;
227 : : } /* for (i=1; i<num_gene; i++) */
228 : :
9357 229 : 192 : 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
5386 tgl@sss.pgh.pa.us 240 : 768 : 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 : :
9716 bruce@momjian.us 252 [ + + ]: 2019 : for (i = 0; i < edge.unused_edges; i++)
253 : : {
555 peter@eisentraut.org 254 : 1251 : possess_edge = abs(edge.edge_list[i]);
9716 bruce@momjian.us 255 : 1251 : genes_remaining = edge_table[possess_edge].unused_edges;
256 : :
257 : : /* find the input gene in all edge_lists and delete it */
258 [ + - ]: 1983 : for (j = 0; j < genes_remaining; j++)
259 : : {
260 : :
555 peter@eisentraut.org 261 [ + + ]: 1983 : if ((Gene) abs(edge_table[possess_edge].edge_list[j]) == gene)
262 : : {
263 : :
9716 bruce@momjian.us 264 : 1251 : edge_table[possess_edge].unused_edges--;
265 : :
266 : 1251 : edge_table[possess_edge].edge_list[j] =
267 : 1251 : edge_table[possess_edge].edge_list[genes_remaining - 1];
268 : :
269 : 1251 : break;
270 : : }
271 : : }
272 : : }
9916 scrappy@hub.org 273 : 768 : }
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
5386 tgl@sss.pgh.pa.us 282 : 768 : gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
283 : : {
284 : : int i;
285 : : Gene friend;
286 : : int minimum_edges;
9715 bruce@momjian.us 287 : 768 : 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 : :
9716 295 : 768 : minimum_edges = 5;
296 : :
297 : : /* consider candidate destination points in edge list */
298 : :
299 [ + + ]: 1221 : for (i = 0; i < edge.unused_edges; i++)
300 : : {
301 : 1026 : 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 [ + + ]: 1026 : if (friend < 0)
555 peter@eisentraut.org 312 : 573 : 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 : :
9716 bruce@momjian.us 331 [ + + ]: 453 : if (edge_table[(int) friend].unused_edges < minimum_edges)
332 : : {
333 : 249 : minimum_edges = edge_table[(int) friend].unused_edges;
334 : 249 : minimum_count = 1;
335 : : }
336 [ - + ]: 204 : else if (minimum_count == -1)
7569 tgl@sss.pgh.pa.us 337 [ # # ]:UBC 0 : elog(ERROR, "minimum_count not set");
9716 bruce@momjian.us 338 [ + - ]:CBC 204 : else if (edge_table[(int) friend].unused_edges == minimum_edges)
339 : 204 : minimum_count++;
340 : : } /* for (i=0; i<edge.unused_edges; i++) */
341 : :
342 : :
343 : : /* random decision of the possible candidates to use */
5386 tgl@sss.pgh.pa.us 344 : 195 : rand_decision = geqo_randint(root, minimum_count - 1, 0);
345 : :
346 : :
9716 bruce@momjian.us 347 [ + - ]: 285 : for (i = 0; i < edge.unused_edges; i++)
348 : : {
349 : 285 : friend = (Gene) edge.edge_list[i];
350 : :
351 : : /* return the chosen candidate point */
352 [ + - ]: 285 : if (edge_table[(int) friend].unused_edges == minimum_edges)
353 : : {
354 : 285 : minimum_count--;
355 : :
356 [ + + ]: 285 : if (minimum_count == rand_decision)
9357 357 : 195 : return friend;
358 : : }
359 : : }
360 : :
361 : : /* ... should never be reached */
7569 tgl@sss.pgh.pa.us 362 [ # # ]:UBC 0 : 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
5386 372 : 0 : edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
373 : : {
374 : : int i;
9715 bruce@momjian.us 375 : 0 : Gene fail_gene = gene[index];
376 : 0 : int remaining_edges = 0;
377 : 0 : 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 : :
9716 386 [ # # ]: 0 : for (i = 1; i <= num_gene; i++)
387 : : {
388 [ # # # # ]: 0 : if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
389 : : {
390 : 0 : remaining_edges++;
391 : :
392 [ # # ]: 0 : if (edge_table[i].total_edges == 4)
393 : 0 : four_count++;
394 : : }
395 : : }
396 : :
397 : : /*
398 : : * random decision of the gene with remaining edges and whose total_edges
399 : : * == 4
400 : : */
401 : :
402 [ # # ]: 0 : if (four_count != 0)
403 : : {
404 : :
5386 tgl@sss.pgh.pa.us 405 : 0 : rand_decision = geqo_randint(root, four_count - 1, 0);
406 : :
9716 bruce@momjian.us 407 [ # # ]: 0 : for (i = 1; i <= num_gene; i++)
408 : : {
409 : :
410 [ # # ]: 0 : if ((Gene) i != fail_gene &&
9916 scrappy@hub.org 411 [ # # ]: 0 : edge_table[i].unused_edges != -1 &&
9716 bruce@momjian.us 412 [ # # ]: 0 : edge_table[i].total_edges == 4)
413 : : {
414 : :
9916 scrappy@hub.org 415 : 0 : four_count--;
416 : :
9716 bruce@momjian.us 417 [ # # ]: 0 : if (rand_decision == four_count)
9357 418 : 0 : return (Gene) i;
419 : : }
420 : : }
421 : :
7569 tgl@sss.pgh.pa.us 422 [ # # ]: 0 : elog(LOG, "no edge found via random decision and total_edges == 4");
423 : : }
424 [ # # ]: 0 : else if (remaining_edges != 0)
425 : : {
426 : : /* random decision of the gene with remaining edges */
5386 427 : 0 : rand_decision = geqo_randint(root, remaining_edges - 1, 0);
428 : :
9716 bruce@momjian.us 429 [ # # ]: 0 : for (i = 1; i <= num_gene; i++)
430 : : {
431 : :
432 [ # # ]: 0 : if ((Gene) i != fail_gene &&
433 [ # # ]: 0 : edge_table[i].unused_edges != -1)
434 : : {
435 : :
9916 scrappy@hub.org 436 : 0 : remaining_edges--;
437 : :
9716 bruce@momjian.us 438 [ # # ]: 0 : if (rand_decision == remaining_edges)
9357 439 : 0 : return i;
440 : : }
441 : : }
442 : :
7569 tgl@sss.pgh.pa.us 443 [ # # ]: 0 : 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 : :
9716 bruce@momjian.us 457 [ # # ]: 0 : for (i = 1; i <= num_gene; i++)
458 [ # # ]: 0 : if (edge_table[i].unused_edges >= 0)
9357 459 : 0 : return (Gene) i;
460 : :
2588 peter_e@gmx.net 461 [ # # ]: 0 : elog(LOG, "no edge found via looking for the last unused point");
462 : : }
463 : :
464 : :
465 : : /* ... should never be reached */
7569 tgl@sss.pgh.pa.us 466 [ # # ]: 0 : elog(ERROR, "no edge found");
467 : : return 0; /* to keep the compiler quiet */
468 : : }
469 : :
470 : : #endif /* defined(ERX) */
|
