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_recombination.h"
36 : #include "optimizer/geqo_random.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 1 : 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 1 : edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
64 :
65 1 : return edge_table;
66 : }
67 :
68 : /* free_edge_table
69 : *
70 : * deallocate memory of edge table
71 : *
72 : */
73 : void
74 1 : free_edge_table(PlannerInfo *root, Edge *edge_table)
75 : {
76 1 : pfree(edge_table);
77 1 : }
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 64 : 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 384 : for (i = 1; i <= num_gene; i++)
103 : {
104 320 : edge_table[i].total_edges = 0;
105 320 : edge_table[i].unused_edges = 0;
106 : }
107 :
108 : /* fill edge table with new data */
109 :
110 64 : edge_total = 0;
111 :
112 384 : 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 320 : 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 320 : edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
127 320 : gimme_edge(root, tour1[index2], tour1[index1], edge_table);
128 :
129 320 : edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
130 320 : gimme_edge(root, tour2[index2], tour2[index1], edge_table);
131 : }
132 :
133 : /* return average number of edges per index */
134 64 : 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 1280 : gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
153 : {
154 : int i;
155 : int edges;
156 1280 : int city1 = (int) gene1;
157 1280 : int city2 = (int) gene2;
158 :
159 :
160 : /* check whether edge city1->city2 already exists */
161 1280 : edges = edge_table[city1].total_edges;
162 :
163 2401 : for (i = 0; i < edges; i++)
164 : {
165 1483 : if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
166 : {
167 :
168 : /* mark shared edges as negative */
169 362 : edge_table[city1].edge_list[i] = 0 - city2;
170 :
171 362 : return 0;
172 : }
173 : }
174 :
175 : /* add city1->city2; */
176 918 : edge_table[city1].edge_list[edges] = city2;
177 :
178 : /* increment the number of edges from city1 */
179 918 : edge_table[city1].total_edges++;
180 918 : edge_table[city1].unused_edges++;
181 :
182 918 : 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 64 : gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
195 : {
196 : int i;
197 64 : int edge_failures = 0;
198 :
199 : /* choose int between 1 and num_gene */
200 64 : new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
201 :
202 320 : 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 256 : 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 256 : if (edge_table[new_gene[i - 1]].unused_edges > 0)
214 256 : new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
215 :
216 : else
217 : { /* cope with fault */
218 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 256 : edge_table[(int) new_gene[i - 1]].unused_edges = -1;
225 :
226 : } /* for (i=1; i<num_gene; i++) */
227 :
228 64 : 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 : */
239 : static void
240 256 : 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 :
252 715 : for (i = 0; i < edge.unused_edges; i++)
253 : {
254 459 : possess_edge = (int) Abs(edge.edge_list[i]);
255 459 : genes_remaining = edge_table[possess_edge].unused_edges;
256 :
257 : /* find the input gene in all edge_lists and delete it */
258 788 : for (j = 0; j < genes_remaining; j++)
259 : {
260 :
261 788 : if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
262 : {
263 :
264 459 : edge_table[possess_edge].unused_edges--;
265 :
266 918 : edge_table[possess_edge].edge_list[j] =
267 459 : edge_table[possess_edge].edge_list[genes_remaining - 1];
268 :
269 459 : break;
270 : }
271 : }
272 : }
273 256 : }
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
282 256 : gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
283 : {
284 : int i;
285 : Gene friend;
286 : int minimum_edges;
287 256 : 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 256 : minimum_edges = 5;
296 :
297 : /* consider candidate destination points in edge list */
298 :
299 476 : for (i = 0; i < edge.unused_edges; i++)
300 : {
301 384 : 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 384 : if (friend < 0)
312 164 : 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 220 : if (edge_table[(int) friend].unused_edges < minimum_edges)
332 : {
333 133 : minimum_edges = edge_table[(int) friend].unused_edges;
334 133 : minimum_count = 1;
335 : }
336 87 : else if (minimum_count == -1)
337 0 : elog(ERROR, "minimum_count not set");
338 87 : else if (edge_table[(int) friend].unused_edges == minimum_edges)
339 84 : minimum_count++;
340 :
341 : } /* for (i=0; i<edge.unused_edges; i++) */
342 :
343 :
344 : /* random decision of the possible candidates to use */
345 92 : rand_decision = geqo_randint(root, minimum_count - 1, 0);
346 :
347 :
348 128 : for (i = 0; i < edge.unused_edges; i++)
349 : {
350 128 : friend = (Gene) edge.edge_list[i];
351 :
352 : /* return the chosen candidate point */
353 128 : if (edge_table[(int) friend].unused_edges == minimum_edges)
354 : {
355 128 : minimum_count--;
356 :
357 128 : if (minimum_count == rand_decision)
358 92 : return friend;
359 : }
360 : }
361 :
362 : /* ... should never be reached */
363 0 : 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 : */
372 : static Gene
373 0 : edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
374 : {
375 : int i;
376 0 : Gene fail_gene = gene[index];
377 0 : int remaining_edges = 0;
378 0 : 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 0 : for (i = 1; i <= num_gene; i++)
388 : {
389 0 : if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
390 : {
391 0 : remaining_edges++;
392 :
393 0 : if (edge_table[i].total_edges == 4)
394 0 : four_count++;
395 : }
396 : }
397 :
398 : /*
399 : * random decision of the gene with remaining edges and whose total_edges
400 : * == 4
401 : */
402 :
403 0 : if (four_count != 0)
404 : {
405 :
406 0 : rand_decision = geqo_randint(root, four_count - 1, 0);
407 :
408 0 : for (i = 1; i <= num_gene; i++)
409 : {
410 :
411 0 : if ((Gene) i != fail_gene &&
412 0 : edge_table[i].unused_edges != -1 &&
413 0 : edge_table[i].total_edges == 4)
414 : {
415 :
416 0 : four_count--;
417 :
418 0 : if (rand_decision == four_count)
419 0 : return (Gene) i;
420 : }
421 : }
422 :
423 0 : elog(LOG, "no edge found via random decision and total_edges == 4");
424 : }
425 0 : else if (remaining_edges != 0)
426 : {
427 : /* random decision of the gene with remaining edges */
428 0 : rand_decision = geqo_randint(root, remaining_edges - 1, 0);
429 :
430 0 : for (i = 1; i <= num_gene; i++)
431 : {
432 :
433 0 : if ((Gene) i != fail_gene &&
434 0 : edge_table[i].unused_edges != -1)
435 : {
436 :
437 0 : remaining_edges--;
438 :
439 0 : if (rand_decision == remaining_edges)
440 0 : return i;
441 : }
442 : }
443 :
444 0 : 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 0 : for (i = 1; i <= num_gene; i++)
459 0 : if (edge_table[i].unused_edges >= 0)
460 0 : return (Gene) i;
461 :
462 0 : elog(LOG, "no edge found via looking for the last unused point");
463 : }
464 :
465 :
466 : /* ... should never be reached */
467 0 : elog(ERROR, "no edge found");
468 : return 0; /* to keep the compiler quiet */
469 : }
470 :
471 : #endif /* defined(ERX) */
|
