1 /*------------------------------------------------------------------------
4 * edge recombination crossover [ER]
6 * $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_erx.c,v 1.19 2003/11/29 22:39:49 pgsql Exp $
8 *-------------------------------------------------------------------------
12 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
13 * Martin Utesch * Institute of Automatic Control *
14 = = University of Mining and Technology =
15 * utesch@aut.tu-freiberg.de * Freiberg, Germany *
16 =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
19 /* the edge recombination algorithm is adopted from Genitor : */
20 /*************************************************************/
22 /* Copyright (c) 1990 */
23 /* Darrell L. Whitley */
24 /* Computer Science Department */
25 /* Colorado State University */
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. */
31 /*************************************************************/
35 #include "optimizer/geqo_recombination.h"
36 #include "optimizer/geqo_random.h"
39 static int gimme_edge(Gene gene1, Gene gene2, Edge *edge_table);
40 static void remove_gene(Gene gene, Edge edge, Edge *edge_table);
41 static Gene gimme_gene(Edge edge, Edge *edge_table);
43 static Gene edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene);
48 * allocate memory for edge table
53 alloc_edge_table(int num_gene)
58 * palloc one extra location so that nodes numbered 1..n can be
59 * indexed directly; 0 will not be used
62 edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
69 * deallocate memory of edge table
73 free_edge_table(Edge *edge_table)
80 * fills a data structure which represents the set of explicit
81 * edges between points in the (2) input genes
83 * assumes circular tours and bidirectional edges
85 * gimme_edge() will set "shared" edges to negative values
87 * returns average number edges/city in range 2.0 - 4.0
88 * where 2.0=homogeneous; 4.0=diverse
92 gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
97 int edge_total; /* total number of unique edges in two
100 /* at first clear the edge table's old data */
101 for (i = 1; i <= num_gene; i++)
103 edge_table[i].total_edges = 0;
104 edge_table[i].unused_edges = 0;
107 /* fill edge table with new data */
111 for (index1 = 0; index1 < num_gene; index1++)
114 * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this
115 * operaton maps n back to 1
118 index2 = (index1 + 1) % num_gene;
121 * edges are bidirectional, i.e. 1->2 is same as 2->1 call
122 * gimme_edge twice per edge
125 edge_total += gimme_edge(tour1[index1], tour1[index2], edge_table);
126 gimme_edge(tour1[index2], tour1[index1], edge_table);
128 edge_total += gimme_edge(tour2[index1], tour2[index2], edge_table);
129 gimme_edge(tour2[index2], tour2[index1], edge_table);
132 /* return average number of edges per index */
133 return ((float) (edge_total * 2) / (float) num_gene);
138 * registers edge from city1 to city2 in input edge table
140 * no assumptions about directionality are made;
141 * therefor 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)
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
151 gimme_edge(Gene gene1, Gene gene2, Edge *edge_table)
155 int city1 = (int) gene1;
156 int city2 = (int) gene2;
159 /* check whether edge city1->city2 already exists */
160 edges = edge_table[city1].total_edges;
162 for (i = 0; i < edges; i++)
164 if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
167 /* mark shared edges as negative */
168 edge_table[city1].edge_list[i] = 0 - city2;
174 /* add city1->city2; */
175 edge_table[city1].edge_list[edges] = city2;
177 /* increment the number of edges from city1 */
178 edge_table[city1].total_edges++;
179 edge_table[city1].unused_edges++;
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.)
193 gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene)
196 int edge_failures = 0;
198 new_gene[0] = (Gene) geqo_randint(num_gene, 1); /* choose int between 1
201 for (i = 1; i < num_gene; i++)
204 * as each point is entered into the tour, remove it from the edge
208 remove_gene(new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
210 /* find destination for the newly entered point */
212 if (edge_table[new_gene[i - 1]].unused_edges > 0)
213 new_gene[i] = gimme_gene(edge_table[(int) new_gene[i - 1]], edge_table);
216 { /* cope with fault */
219 new_gene[i] = edge_failure(new_gene, i - 1, edge_table, num_gene);
222 /* mark this node as incorporated */
223 edge_table[(int) new_gene[i - 1]].unused_edges = -1;
225 } /* for (i=1; i<num_gene; i++) */
227 return edge_failures;
233 * removes input gene from edge_table.
235 * to identify deletion locations within edge table.
239 remove_gene(Gene gene, Edge edge, Edge *edge_table)
247 * do for every gene known to have an edge to input gene (i.e. in
248 * edge_list for input edge)
251 for (i = 0; i < edge.unused_edges; i++)
253 possess_edge = (int) Abs(edge.edge_list[i]);
254 genes_remaining = edge_table[possess_edge].unused_edges;
256 /* find the input gene in all edge_lists and delete it */
257 for (j = 0; j < genes_remaining; j++)
260 if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
263 edge_table[possess_edge].unused_edges--;
265 edge_table[possess_edge].edge_list[j] =
266 edge_table[possess_edge].edge_list[genes_remaining - 1];
276 * priority is given to "shared" edges
277 * (i.e. edges which both genes possess)
281 gimme_gene(Edge edge, Edge *edge_table)
286 int minimum_count = -1;
290 * no point has edges to more than 4 other points thus, this contrived
291 * minimum will be replaced
296 /* consider candidate destination points in edge list */
298 for (i = 0; i < edge.unused_edges; i++)
300 friend = (Gene) edge.edge_list[i];
303 * give priority to shared edges that are negative; so return 'em
307 * negative values are caught here so we need not worry about
308 * converting to absolute values
311 return (Gene) Abs(friend);
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 cadidate with the
318 * minimum number of unused edges keep count of this number
323 * The test for minimum_count can probably be removed at some
324 * point but comments should probably indicate exactly why it is
325 * guaranteed that the test will always succeed the first time
326 * around. If it can fail then the code is in error
330 if (edge_table[(int) friend].unused_edges < minimum_edges)
332 minimum_edges = edge_table[(int) friend].unused_edges;
335 else if (minimum_count == -1)
336 elog(ERROR, "minimum_count not set");
337 else if (edge_table[(int) friend].unused_edges == minimum_edges)
340 } /* for (i=0; i<edge.unused_edges; i++) */
343 /* random decision of the possible candidates to use */
344 rand_decision = (int) geqo_randint(minimum_count - 1, 0);
347 for (i = 0; i < edge.unused_edges; i++)
349 friend = (Gene) edge.edge_list[i];
351 /* return the chosen candidate point */
352 if (edge_table[(int) friend].unused_edges == minimum_edges)
356 if (minimum_count == rand_decision)
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 */
368 * routine for handling edge failure
372 edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene)
375 Gene fail_gene = gene[index];
376 int remaining_edges = 0;
382 * how many edges remain? how many gene with four total (initial)
386 for (i = 1; i <= num_gene; i++)
388 if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
392 if (edge_table[i].total_edges == 4)
398 * random decision of the gene with remaining edges and whose
405 rand_decision = (int) geqo_randint(four_count - 1, 0);
407 for (i = 1; i <= num_gene; i++)
410 if ((Gene) i != fail_gene &&
411 edge_table[i].unused_edges != -1 &&
412 edge_table[i].total_edges == 4)
417 if (rand_decision == four_count)
422 elog(LOG, "no edge found via random decision and total_edges == 4");
424 else if (remaining_edges != 0)
426 /* random decision of the gene with remaining edges */
427 rand_decision = (int) geqo_randint(remaining_edges - 1, 0);
429 for (i = 1; i <= num_gene; i++)
432 if ((Gene) i != fail_gene &&
433 edge_table[i].unused_edges != -1)
438 if (rand_decision == remaining_edges)
443 elog(LOG, "no edge found via random decision with remaining edges");
447 * edge table seems to be empty; this happens sometimes on the last
448 * point due to the fact that the first point is removed from the
449 * table even though only one of its edges has been determined
453 { /* occurs only at the last point in the
454 * tour; simply look for the point which
457 for (i = 1; i <= num_gene; i++)
458 if (edge_table[i].unused_edges >= 0)
461 elog(LOG, "no edge found via looking for the last ununsed point");
465 /* ... should never be reached */
466 elog(ERROR, "no edge found");
467 return 0; /* to keep the compiler quiet */