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