PostgreSQL Source Code  git master
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"
35 #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 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  edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
64 
65  return edge_table;
66 }
67 
68 /* free_edge_table
69  *
70  * deallocate memory of edge table
71  *
72  */
73 void
74 free_edge_table(PlannerInfo *root, Edge *edge_table)
75 {
76  pfree(edge_table);
77 }
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 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  for (i = 1; i <= num_gene; i++)
103  {
104  edge_table[i].total_edges = 0;
105  edge_table[i].unused_edges = 0;
106  }
107 
108  /* fill edge table with new data */
109 
110  edge_total = 0;
111 
112  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  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  edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
127  gimme_edge(root, tour1[index2], tour1[index1], edge_table);
128 
129  edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
130  gimme_edge(root, tour2[index2], tour2[index1], edge_table);
131  }
132 
133  /* return average number of edges per index */
134  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 gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
153 {
154  int i;
155  int edges;
156  int city1 = (int) gene1;
157  int city2 = (int) gene2;
158 
159 
160  /* check whether edge city1->city2 already exists */
161  edges = edge_table[city1].total_edges;
162 
163  for (i = 0; i < edges; i++)
164  {
165  if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
166  {
167 
168  /* mark shared edges as negative */
169  edge_table[city1].edge_list[i] = 0 - city2;
170 
171  return 0;
172  }
173  }
174 
175  /* add city1->city2; */
176  edge_table[city1].edge_list[edges] = city2;
177 
178  /* increment the number of edges from city1 */
179  edge_table[city1].total_edges++;
180  edge_table[city1].unused_edges++;
181 
182  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 gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
195 {
196  int i;
197  int edge_failures = 0;
198 
199  /* choose int between 1 and num_gene */
200  new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
201 
202  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  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  if (edge_table[new_gene[i - 1]].unused_edges > 0)
214  new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
215 
216  else
217  { /* cope with fault */
218  edge_failures++;
219 
220  new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
221  }
222 
223  /* mark this node as incorporated */
224  edge_table[(int) new_gene[i - 1]].unused_edges = -1;
225  } /* for (i=1; i<num_gene; i++) */
226 
227  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 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  for (i = 0; i < edge.unused_edges; i++)
251  {
252  possess_edge = (int) Abs(edge.edge_list[i]);
253  genes_remaining = edge_table[possess_edge].unused_edges;
254 
255  /* find the input gene in all edge_lists and delete it */
256  for (j = 0; j < genes_remaining; j++)
257  {
258 
259  if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
260  {
261 
262  edge_table[possess_edge].unused_edges--;
263 
264  edge_table[possess_edge].edge_list[j] =
265  edge_table[possess_edge].edge_list[genes_remaining - 1];
266 
267  break;
268  }
269  }
270  }
271 }
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 gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
281 {
282  int i;
283  Gene friend;
284  int minimum_edges;
285  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  minimum_edges = 5;
294 
295  /* consider candidate destination points in edge list */
296 
297  for (i = 0; i < edge.unused_edges; i++)
298  {
299  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  if (friend < 0)
310  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  if (edge_table[(int) friend].unused_edges < minimum_edges)
330  {
331  minimum_edges = edge_table[(int) friend].unused_edges;
332  minimum_count = 1;
333  }
334  else if (minimum_count == -1)
335  elog(ERROR, "minimum_count not set");
336  else if (edge_table[(int) friend].unused_edges == minimum_edges)
337  minimum_count++;
338  } /* for (i=0; i<edge.unused_edges; i++) */
339 
340 
341  /* random decision of the possible candidates to use */
342  rand_decision = geqo_randint(root, minimum_count - 1, 0);
343 
344 
345  for (i = 0; i < edge.unused_edges; i++)
346  {
347  friend = (Gene) edge.edge_list[i];
348 
349  /* return the chosen candidate point */
350  if (edge_table[(int) friend].unused_edges == minimum_edges)
351  {
352  minimum_count--;
353 
354  if (minimum_count == rand_decision)
355  return friend;
356  }
357  }
358 
359  /* ... should never be reached */
360  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 edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
371 {
372  int i;
373  Gene fail_gene = gene[index];
374  int remaining_edges = 0;
375  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  for (i = 1; i <= num_gene; i++)
385  {
386  if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
387  {
388  remaining_edges++;
389 
390  if (edge_table[i].total_edges == 4)
391  four_count++;
392  }
393  }
394 
395  /*
396  * random decision of the gene with remaining edges and whose total_edges
397  * == 4
398  */
399 
400  if (four_count != 0)
401  {
402 
403  rand_decision = geqo_randint(root, four_count - 1, 0);
404 
405  for (i = 1; i <= num_gene; i++)
406  {
407 
408  if ((Gene) i != fail_gene &&
409  edge_table[i].unused_edges != -1 &&
410  edge_table[i].total_edges == 4)
411  {
412 
413  four_count--;
414 
415  if (rand_decision == four_count)
416  return (Gene) i;
417  }
418  }
419 
420  elog(LOG, "no edge found via random decision and total_edges == 4");
421  }
422  else if (remaining_edges != 0)
423  {
424  /* random decision of the gene with remaining edges */
425  rand_decision = geqo_randint(root, remaining_edges - 1, 0);
426 
427  for (i = 1; i <= num_gene; i++)
428  {
429 
430  if ((Gene) i != fail_gene &&
431  edge_table[i].unused_edges != -1)
432  {
433 
434  remaining_edges--;
435 
436  if (rand_decision == remaining_edges)
437  return i;
438  }
439  }
440 
441  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  for (i = 1; i <= num_gene; i++)
456  if (edge_table[i].unused_edges >= 0)
457  return (Gene) i;
458 
459  elog(LOG, "no edge found via looking for the last unused point");
460  }
461 
462 
463  /* ... should never be reached */
464  elog(ERROR, "no edge found");
465  return 0; /* to keep the compiler quiet */
466 }
467 
468 #endif /* defined(ERX) */
#define Abs(x)
Definition: c.h:992
#define LOG
Definition: elog.h:25
#define ERROR
Definition: elog.h:33
#define elog(elevel,...)
Definition: elog.h:218
static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
Definition: geqo_erx.c:152
float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
Definition: geqo_erx.c:93
void free_edge_table(PlannerInfo *root, Edge *edge_table)
Definition: geqo_erx.c:74
static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:280
int gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
Definition: geqo_erx.c:194
static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
Definition: geqo_erx.c:370
static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:238
Edge * alloc_edge_table(PlannerInfo *root, int num_gene)
Definition: geqo_erx.c:54
int Gene
Definition: geqo_gene.h:30
int geqo_randint(PlannerInfo *root, int upper, int lower)
Definition: geqo_random.c:36
struct Edge Edge
int j
Definition: isn.c:74
int i
Definition: isn.c:73
void pfree(void *pointer)
Definition: mcxt.c:1175
void * palloc(Size size)
Definition: mcxt.c:1068
int unused_edges
Gene edge_list[4]
int total_edges
Definition: type.h:90