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_random.h"
36 : #include "optimizer/geqo_recombination.h"
37 :
38 : #if defined(ERX)
39 :
40 : static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table);
41 : static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table);
42 : static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table);
43 :
44 : static 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 :
53 : Edge *
54 CBC 3 : alloc_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 3 : edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
64 :
65 3 : return edge_table;
66 : }
67 :
68 : /* free_edge_table
69 : *
70 : * deallocate memory of edge table
71 : *
72 : */
73 : void
74 3 : free_edge_table(PlannerInfo *root, Edge *edge_table)
75 : {
76 3 : pfree(edge_table);
77 3 : }
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 : */
92 : float
93 192 : gimme_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 1152 : for (i = 1; i <= num_gene; i++)
103 : {
104 960 : edge_table[i].total_edges = 0;
105 960 : edge_table[i].unused_edges = 0;
106 : }
107 :
108 : /* fill edge table with new data */
109 :
110 192 : edge_total = 0;
111 :
112 1152 : 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 960 : 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 960 : edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
127 960 : gimme_edge(root, tour1[index2], tour1[index1], edge_table);
128 :
129 960 : edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
130 960 : gimme_edge(root, tour2[index2], tour2[index1], edge_table);
131 : }
132 :
133 : /* return average number of edges per index */
134 192 : 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 : */
151 : static int
152 3840 : gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
153 : {
154 : int i;
155 : int edges;
156 3840 : int city1 = (int) gene1;
157 3840 : int city2 = (int) gene2;
158 :
159 :
160 : /* check whether edge city1->city2 already exists */
161 3840 : edges = edge_table[city1].total_edges;
162 :
163 6759 : for (i = 0; i < edges; i++)
164 : {
165 GNC 4257 : if ((Gene) abs(edge_table[city1].edge_list[i]) == city2)
166 : {
167 :
168 : /* mark shared edges as negative */
169 CBC 1338 : edge_table[city1].edge_list[i] = 0 - city2;
170 :
171 1338 : return 0;
172 : }
173 : }
174 :
175 : /* add city1->city2; */
176 2502 : edge_table[city1].edge_list[edges] = city2;
177 :
178 : /* increment the number of edges from city1 */
179 2502 : edge_table[city1].total_edges++;
180 2502 : edge_table[city1].unused_edges++;
181 :
182 2502 : 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 : */
193 : int
194 192 : gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
195 : {
196 : int i;
197 192 : int edge_failures = 0;
198 :
199 : /* choose int between 1 and num_gene */
200 192 : new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
201 :
202 960 : 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 768 : 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 768 : if (edge_table[new_gene[i - 1]].unused_edges > 0)
214 768 : new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
215 :
216 : else
217 : { /* cope with fault */
218 UBC 0 : edge_failures++;
219 :
220 0 : new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
221 : }
222 :
223 : /* mark this node as incorporated */
224 CBC 768 : edge_table[(int) new_gene[i - 1]].unused_edges = -1;
225 : } /* for (i=1; i<num_gene; i++) */
226 :
227 192 : return edge_failures;
228 : }
229 :
230 : /* remove_gene
231 : *
232 : * removes input gene from edge_table.
233 : * input edge is used
234 : * to identify deletion locations within edge table.
235 : *
236 : */
237 : static void
238 768 : remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
239 : {
240 : int i,
241 : j;
242 : int possess_edge;
243 : int genes_remaining;
244 :
245 : /*
246 : * do for every gene known to have an edge to input gene (i.e. in
247 : * edge_list for input edge)
248 : */
249 :
250 2019 : for (i = 0; i < edge.unused_edges; i++)
251 : {
252 GNC 1251 : possess_edge = abs(edge.edge_list[i]);
253 CBC 1251 : genes_remaining = edge_table[possess_edge].unused_edges;
254 :
255 : /* find the input gene in all edge_lists and delete it */
256 1983 : for (j = 0; j < genes_remaining; j++)
257 : {
258 :
259 GNC 1983 : if ((Gene) abs(edge_table[possess_edge].edge_list[j]) == gene)
260 : {
261 :
262 CBC 1251 : edge_table[possess_edge].unused_edges--;
263 :
264 1251 : edge_table[possess_edge].edge_list[j] =
265 1251 : edge_table[possess_edge].edge_list[genes_remaining - 1];
266 :
267 1251 : break;
268 : }
269 : }
270 : }
271 768 : }
272 :
273 : /* gimme_gene
274 : *
275 : * priority is given to "shared" edges
276 : * (i.e. edges which both genes possess)
277 : *
278 : */
279 : static Gene
280 768 : gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
281 : {
282 : int i;
283 : Gene friend;
284 : int minimum_edges;
285 768 : int minimum_count = -1;
286 : int rand_decision;
287 :
288 : /*
289 : * no point has edges to more than 4 other points thus, this contrived
290 : * minimum will be replaced
291 : */
292 :
293 768 : minimum_edges = 5;
294 :
295 : /* consider candidate destination points in edge list */
296 :
297 1221 : for (i = 0; i < edge.unused_edges; i++)
298 : {
299 1026 : friend = (Gene) edge.edge_list[i];
300 :
301 : /*
302 : * give priority to shared edges that are negative; so return 'em
303 : */
304 :
305 : /*
306 : * negative values are caught here so we need not worry about
307 : * converting to absolute values
308 : */
309 1026 : if (friend < 0)
310 GNC 573 : return (Gene) abs(friend);
311 :
312 :
313 : /*
314 : * give priority to candidates with fewest remaining unused edges;
315 : * find out what the minimum number of unused edges is
316 : * (minimum_edges); if there is more than one candidate with the
317 : * minimum number of unused edges keep count of this number
318 : * (minimum_count);
319 : */
320 :
321 : /*
322 : * The test for minimum_count can probably be removed at some point
323 : * but comments should probably indicate exactly why it is guaranteed
324 : * that the test will always succeed the first time around. If it can
325 : * fail then the code is in error
326 : */
327 :
328 :
329 CBC 453 : if (edge_table[(int) friend].unused_edges < minimum_edges)
330 : {
331 249 : minimum_edges = edge_table[(int) friend].unused_edges;
332 249 : minimum_count = 1;
333 : }
334 204 : else if (minimum_count == -1)
335 UBC 0 : elog(ERROR, "minimum_count not set");
336 CBC 204 : else if (edge_table[(int) friend].unused_edges == minimum_edges)
337 204 : minimum_count++;
338 : } /* for (i=0; i<edge.unused_edges; i++) */
339 :
340 :
341 : /* random decision of the possible candidates to use */
342 195 : rand_decision = geqo_randint(root, minimum_count - 1, 0);
343 :
344 :
345 285 : for (i = 0; i < edge.unused_edges; i++)
346 : {
347 285 : friend = (Gene) edge.edge_list[i];
348 :
349 : /* return the chosen candidate point */
350 285 : if (edge_table[(int) friend].unused_edges == minimum_edges)
351 : {
352 285 : minimum_count--;
353 :
354 285 : if (minimum_count == rand_decision)
355 195 : return friend;
356 : }
357 : }
358 :
359 : /* ... should never be reached */
360 UBC 0 : elog(ERROR, "neither shared nor minimum number nor random edge found");
361 : return 0; /* to keep the compiler quiet */
362 : }
363 :
364 : /* edge_failure
365 : *
366 : * routine for handling edge failure
367 : *
368 : */
369 : static Gene
370 0 : edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
371 : {
372 : int i;
373 0 : Gene fail_gene = gene[index];
374 0 : int remaining_edges = 0;
375 0 : int four_count = 0;
376 : int rand_decision;
377 :
378 :
379 : /*
380 : * how many edges remain? how many gene with four total (initial) edges
381 : * remain?
382 : */
383 :
384 0 : for (i = 1; i <= num_gene; i++)
385 : {
386 0 : if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
387 : {
388 0 : remaining_edges++;
389 :
390 0 : if (edge_table[i].total_edges == 4)
391 0 : four_count++;
392 : }
393 : }
394 :
395 : /*
396 : * random decision of the gene with remaining edges and whose total_edges
397 : * == 4
398 : */
399 :
400 0 : if (four_count != 0)
401 : {
402 :
403 0 : rand_decision = geqo_randint(root, four_count - 1, 0);
404 :
405 0 : for (i = 1; i <= num_gene; i++)
406 : {
407 :
408 0 : if ((Gene) i != fail_gene &&
409 0 : edge_table[i].unused_edges != -1 &&
410 0 : edge_table[i].total_edges == 4)
411 : {
412 :
413 0 : four_count--;
414 :
415 0 : if (rand_decision == four_count)
416 0 : return (Gene) i;
417 : }
418 : }
419 :
420 0 : elog(LOG, "no edge found via random decision and total_edges == 4");
421 : }
422 0 : else if (remaining_edges != 0)
423 : {
424 : /* random decision of the gene with remaining edges */
425 0 : rand_decision = geqo_randint(root, remaining_edges - 1, 0);
426 :
427 0 : for (i = 1; i <= num_gene; i++)
428 : {
429 :
430 0 : if ((Gene) i != fail_gene &&
431 0 : edge_table[i].unused_edges != -1)
432 : {
433 :
434 0 : remaining_edges--;
435 :
436 0 : if (rand_decision == remaining_edges)
437 0 : return i;
438 : }
439 : }
440 :
441 0 : elog(LOG, "no edge found via random decision with remaining edges");
442 : }
443 :
444 : /*
445 : * edge table seems to be empty; this happens sometimes on the last point
446 : * due to the fact that the first point is removed from the table even
447 : * though only one of its edges has been determined
448 : */
449 :
450 : else
451 : { /* occurs only at the last point in the tour;
452 : * simply look for the point which is not yet
453 : * used */
454 :
455 0 : for (i = 1; i <= num_gene; i++)
456 0 : if (edge_table[i].unused_edges >= 0)
457 0 : return (Gene) i;
458 :
459 0 : elog(LOG, "no edge found via looking for the last unused point");
460 : }
461 :
462 :
463 : /* ... should never be reached */
464 0 : elog(ERROR, "no edge found");
465 : return 0; /* to keep the compiler quiet */
466 : }
467 :
468 : #endif /* defined(ERX) */
|
