PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_erx.c
Go to the documentation of this file.
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"
36 #include "optimizer/geqo_random.h"
37 
38 
39 static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table);
40 static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table);
41 static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table);
42 
43 static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene);
44 
45 
46 /* alloc_edge_table
47  *
48  * allocate memory for edge table
49  *
50  */
51 
52 Edge *
53 alloc_edge_table(PlannerInfo *root, int num_gene)
54 {
55  Edge *edge_table;
56 
57  /*
58  * palloc one extra location so that nodes numbered 1..n can be indexed
59  * directly; 0 will not be used
60  */
61 
62  edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
63 
64  return edge_table;
65 }
66 
67 /* free_edge_table
68  *
69  * deallocate memory of edge table
70  *
71  */
72 void
73 free_edge_table(PlannerInfo *root, Edge *edge_table)
74 {
75  pfree(edge_table);
76 }
77 
78 /* gimme_edge_table
79  *
80  * fills a data structure which represents the set of explicit
81  * edges between points in the (2) input genes
82  *
83  * assumes circular tours and bidirectional edges
84  *
85  * gimme_edge() will set "shared" edges to negative values
86  *
87  * returns average number edges/city in range 2.0 - 4.0
88  * where 2.0=homogeneous; 4.0=diverse
89  *
90  */
91 float
92 gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
93  int num_gene, Edge *edge_table)
94 {
95  int i,
96  index1,
97  index2;
98  int edge_total; /* total number of unique edges in two genes */
99 
100  /* at first clear the edge table's old data */
101  for (i = 1; i <= num_gene; i++)
102  {
103  edge_table[i].total_edges = 0;
104  edge_table[i].unused_edges = 0;
105  }
106 
107  /* fill edge table with new data */
108 
109  edge_total = 0;
110 
111  for (index1 = 0; index1 < num_gene; index1++)
112  {
113  /*
114  * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operation
115  * maps n back to 1
116  */
117 
118  index2 = (index1 + 1) % num_gene;
119 
120  /*
121  * edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
122  * twice per edge
123  */
124 
125  edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
126  gimme_edge(root, tour1[index2], tour1[index1], edge_table);
127 
128  edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
129  gimme_edge(root, tour2[index2], tour2[index1], edge_table);
130  }
131 
132  /* return average number of edges per index */
133  return ((float) (edge_total * 2) / (float) num_gene);
134 }
135 
136 /* gimme_edge
137  *
138  * registers edge from city1 to city2 in input edge table
139  *
140  * no assumptions about directionality are made;
141  * therefore it is up to the calling routine to
142  * call gimme_edge twice to make a bi-directional edge
143  * between city1 and city2;
144  * uni-directional edges are possible as well (just call gimme_edge
145  * once with the direction from city1 to city2)
146  *
147  * returns 1 if edge was not already registered and was just added;
148  * 0 if edge was already registered and edge_table is unchanged
149  */
150 static int
151 gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
152 {
153  int i;
154  int edges;
155  int city1 = (int) gene1;
156  int city2 = (int) gene2;
157 
158 
159  /* check whether edge city1->city2 already exists */
160  edges = edge_table[city1].total_edges;
161 
162  for (i = 0; i < edges; i++)
163  {
164  if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
165  {
166 
167  /* mark shared edges as negative */
168  edge_table[city1].edge_list[i] = 0 - city2;
169 
170  return 0;
171  }
172  }
173 
174  /* add city1->city2; */
175  edge_table[city1].edge_list[edges] = city2;
176 
177  /* increment the number of edges from city1 */
178  edge_table[city1].total_edges++;
179  edge_table[city1].unused_edges++;
180 
181  return 1;
182 }
183 
184 /* gimme_tour
185  *
186  * creates a new tour using edges from the edge table.
187  * priority is given to "shared" edges (i.e. edges which
188  * all parent genes possess and are marked as negative
189  * in the edge table.)
190  *
191  */
192 int
193 gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
194 {
195  int i;
196  int edge_failures = 0;
197 
198  /* choose int between 1 and num_gene */
199  new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
200 
201  for (i = 1; i < num_gene; i++)
202  {
203  /*
204  * as each point is entered into the tour, remove it from the edge
205  * table
206  */
207 
208  remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
209 
210  /* find destination for the newly entered point */
211 
212  if (edge_table[new_gene[i - 1]].unused_edges > 0)
213  new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
214 
215  else
216  { /* cope with fault */
217  edge_failures++;
218 
219  new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
220  }
221 
222  /* mark this node as incorporated */
223  edge_table[(int) new_gene[i - 1]].unused_edges = -1;
224 
225  } /* for (i=1; i<num_gene; i++) */
226 
227  return edge_failures;
228 
229 }
230 
231 /* remove_gene
232  *
233  * removes input gene from edge_table.
234  * input edge is used
235  * to identify deletion locations within edge table.
236  *
237  */
238 static void
239 remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
240 {
241  int i,
242  j;
243  int possess_edge;
244  int genes_remaining;
245 
246  /*
247  * do for every gene known to have an edge to input gene (i.e. in
248  * edge_list for input edge)
249  */
250 
251  for (i = 0; i < edge.unused_edges; i++)
252  {
253  possess_edge = (int) Abs(edge.edge_list[i]);
254  genes_remaining = edge_table[possess_edge].unused_edges;
255 
256  /* find the input gene in all edge_lists and delete it */
257  for (j = 0; j < genes_remaining; j++)
258  {
259 
260  if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
261  {
262 
263  edge_table[possess_edge].unused_edges--;
264 
265  edge_table[possess_edge].edge_list[j] =
266  edge_table[possess_edge].edge_list[genes_remaining - 1];
267 
268  break;
269  }
270  }
271  }
272 }
273 
274 /* gimme_gene
275  *
276  * priority is given to "shared" edges
277  * (i.e. edges which both genes possess)
278  *
279  */
280 static Gene
281 gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
282 {
283  int i;
284  Gene friend;
285  int minimum_edges;
286  int minimum_count = -1;
287  int rand_decision;
288 
289  /*
290  * no point has edges to more than 4 other points thus, this contrived
291  * minimum will be replaced
292  */
293 
294  minimum_edges = 5;
295 
296  /* consider candidate destination points in edge list */
297 
298  for (i = 0; i < edge.unused_edges; i++)
299  {
300  friend = (Gene) edge.edge_list[i];
301 
302  /*
303  * give priority to shared edges that are negative; so return 'em
304  */
305 
306  /*
307  * negative values are caught here so we need not worry about
308  * converting to absolute values
309  */
310  if (friend < 0)
311  return (Gene) Abs(friend);
312 
313 
314  /*
315  * give priority to candidates with fewest remaining unused edges;
316  * find out what the minimum number of unused edges is
317  * (minimum_edges); if there is more than one candidate with the
318  * minimum number of unused edges keep count of this number
319  * (minimum_count);
320  */
321 
322  /*
323  * The test for minimum_count can probably be removed at some point
324  * but comments should probably indicate exactly why it is guaranteed
325  * that the test will always succeed the first time around. If it can
326  * fail then the code is in error
327  */
328 
329 
330  if (edge_table[(int) friend].unused_edges < minimum_edges)
331  {
332  minimum_edges = edge_table[(int) friend].unused_edges;
333  minimum_count = 1;
334  }
335  else if (minimum_count == -1)
336  elog(ERROR, "minimum_count not set");
337  else if (edge_table[(int) friend].unused_edges == minimum_edges)
338  minimum_count++;
339 
340  } /* for (i=0; i<edge.unused_edges; i++) */
341 
342 
343  /* random decision of the possible candidates to use */
344  rand_decision = geqo_randint(root, minimum_count - 1, 0);
345 
346 
347  for (i = 0; i < edge.unused_edges; i++)
348  {
349  friend = (Gene) edge.edge_list[i];
350 
351  /* return the chosen candidate point */
352  if (edge_table[(int) friend].unused_edges == minimum_edges)
353  {
354  minimum_count--;
355 
356  if (minimum_count == rand_decision)
357  return friend;
358  }
359  }
360 
361  /* ... should never be reached */
362  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
372 edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
373 {
374  int i;
375  Gene fail_gene = gene[index];
376  int remaining_edges = 0;
377  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 
386  for (i = 1; i <= num_gene; i++)
387  {
388  if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
389  {
390  remaining_edges++;
391 
392  if (edge_table[i].total_edges == 4)
393  four_count++;
394  }
395  }
396 
397  /*
398  * random decision of the gene with remaining edges and whose total_edges
399  * == 4
400  */
401 
402  if (four_count != 0)
403  {
404 
405  rand_decision = geqo_randint(root, four_count - 1, 0);
406 
407  for (i = 1; i <= num_gene; i++)
408  {
409 
410  if ((Gene) i != fail_gene &&
411  edge_table[i].unused_edges != -1 &&
412  edge_table[i].total_edges == 4)
413  {
414 
415  four_count--;
416 
417  if (rand_decision == four_count)
418  return (Gene) i;
419  }
420  }
421 
422  elog(LOG, "no edge found via random decision and total_edges == 4");
423  }
424  else if (remaining_edges != 0)
425  {
426  /* random decision of the gene with remaining edges */
427  rand_decision = geqo_randint(root, remaining_edges - 1, 0);
428 
429  for (i = 1; i <= num_gene; i++)
430  {
431 
432  if ((Gene) i != fail_gene &&
433  edge_table[i].unused_edges != -1)
434  {
435 
436  remaining_edges--;
437 
438  if (rand_decision == remaining_edges)
439  return i;
440  }
441  }
442 
443  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 
457  for (i = 1; i <= num_gene; i++)
458  if (edge_table[i].unused_edges >= 0)
459  return (Gene) i;
460 
461  elog(LOG, "no edge found via looking for the last ununsed point");
462  }
463 
464 
465  /* ... should never be reached */
466  elog(ERROR, "no edge found");
467  return 0; /* to keep the compiler quiet */
468 }
static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
Definition: geqo_erx.c:372
int gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
Definition: geqo_erx.c:193
static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:281
float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
Definition: geqo_erx.c:92
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
int total_edges
#define LOG
Definition: elog.h:26
#define Abs(x)
Definition: c.h:808
Definition: type.h:90
void pfree(void *pointer)
Definition: mcxt.c:992
#define ERROR
Definition: elog.h:43
static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:239
Gene edge_list[4]
void free_edge_table(PlannerInfo *root, Edge *edge_table)
Definition: geqo_erx.c:73
static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
Definition: geqo_erx.c:151
struct Edge Edge
Edge * alloc_edge_table(PlannerInfo *root, int num_gene)
Definition: geqo_erx.c:53
void * palloc(Size size)
Definition: mcxt.c:891
int i
#define elog
Definition: elog.h:219
int unused_edges