PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_recombination.h File Reference
#include "optimizer/geqo.h"
Include dependency graph for geqo_recombination.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  Edge
 
struct  City
 

Macros

#define DAD   1 /* indicator for gene from dad */
 
#define MOM   0 /* indicator for gene from mom */
 

Typedefs

typedef struct Edge Edge
 
typedef struct City City
 

Functions

void init_tour (PlannerInfo *root, Gene *tour, int num_gene)
 
Edgealloc_edge_table (PlannerInfo *root, int num_gene)
 
void free_edge_table (PlannerInfo *root, Edge *edge_table)
 
float gimme_edge_table (PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
 
int gimme_tour (PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
 
void pmx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
 
Cityalloc_city_table (PlannerInfo *root, int num_gene)
 
void free_city_table (PlannerInfo *root, City *city_table)
 
int cx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
 
void px (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
 
void ox1 (PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
 
void ox2 (PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
 

Macro Definition Documentation

#define DAD   1 /* indicator for gene from dad */

Definition at line 54 of file geqo_recombination.h.

Referenced by pmx().

#define MOM   0 /* indicator for gene from mom */

Definition at line 55 of file geqo_recombination.h.

Referenced by pmx().

Typedef Documentation

typedef struct City City
typedef struct Edge Edge

Function Documentation

City* alloc_city_table ( PlannerInfo root,
int  num_gene 
)

Definition at line 66 of file geqo_recombination.c.

References palloc().

Referenced by geqo().

67 {
68  City *city_table;
69 
70  /*
71  * palloc one extra location so that nodes numbered 1..n can be indexed
72  * directly; 0 will not be used
73  */
74  city_table = (City *) palloc((num_gene + 1) * sizeof(City));
75 
76  return city_table;
77 }
struct City City
void * palloc(Size size)
Definition: mcxt.c:891
Edge* alloc_edge_table ( PlannerInfo root,
int  num_gene 
)

Definition at line 53 of file geqo_erx.c.

References palloc().

Referenced by geqo().

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 }
struct Edge Edge
void * palloc(Size size)
Definition: mcxt.c:891
int cx ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene,
City city_table 
)

Definition at line 47 of file geqo_cx.c.

References geqo_randint, i, City::tour1_position, City::tour2_position, and City::used.

Referenced by bf_decrypt(), bf_encrypt(), bf_init(), bf_load(), geqo(), intctx_free(), px_find_combo(), rj_decrypt(), rj_encrypt(), rj_init(), and rj_load().

49 {
50  int i,
51  start_pos,
52  curr_pos;
53  int count = 0;
54  int num_diffs = 0;
55 
56  /* initialize city table */
57  for (i = 1; i <= num_gene; i++)
58  {
59  city_table[i].used = 0;
60  city_table[tour2[i - 1]].tour2_position = i - 1;
61  city_table[tour1[i - 1]].tour1_position = i - 1;
62  }
63 
64  /* choose random cycle starting position */
65  start_pos = geqo_randint(root, num_gene - 1, 0);
66 
67  /* child inherits first city */
68  offspring[start_pos] = tour1[start_pos];
69 
70  /* begin cycle with tour1 */
71  curr_pos = start_pos;
72  city_table[(int) tour1[start_pos]].used = 1;
73 
74  count++;
75 
76  /* cx main part */
77 
78 
79 /* STEP 1 */
80 
81  while (tour2[curr_pos] != tour1[start_pos])
82  {
83  city_table[(int) tour2[curr_pos]].used = 1;
84  curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
85  offspring[curr_pos] = tour1[curr_pos];
86  count++;
87  }
88 
89 
90 /* STEP 2 */
91 
92  /* failed to create a complete tour */
93  if (count < num_gene)
94  {
95  for (i = 1; i <= num_gene; i++)
96  {
97  if (!city_table[i].used)
98  {
99  offspring[city_table[i].tour2_position] =
100  tour2[(int) city_table[i].tour2_position];
101  count++;
102  }
103  }
104  }
105 
106 
107 /* STEP 3 */
108 
109  /* still failed to create a complete tour */
110  if (count < num_gene)
111  {
112 
113  /* count the number of differences between mom and offspring */
114  for (i = 0; i < num_gene; i++)
115  if (tour1[i] != offspring[i])
116  num_diffs++;
117 
118  }
119 
120  return num_diffs;
121 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int tour1_position
int tour2_position
int i
void free_city_table ( PlannerInfo root,
City city_table 
)

Definition at line 84 of file geqo_recombination.c.

References pfree().

Referenced by geqo().

85 {
86  pfree(city_table);
87 }
void pfree(void *pointer)
Definition: mcxt.c:992
void free_edge_table ( PlannerInfo root,
Edge edge_table 
)

Definition at line 73 of file geqo_erx.c.

References pfree().

Referenced by geqo().

74 {
75  pfree(edge_table);
76 }
void pfree(void *pointer)
Definition: mcxt.c:992
float gimme_edge_table ( PlannerInfo root,
Gene tour1,
Gene tour2,
int  num_gene,
Edge edge_table 
)

Definition at line 92 of file geqo_erx.c.

References gimme_edge(), i, Edge::total_edges, and Edge::unused_edges.

Referenced by geqo().

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 }
int total_edges
static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
Definition: geqo_erx.c:151
int i
int unused_edges
int gimme_tour ( PlannerInfo root,
Edge edge_table,
Gene new_gene,
int  num_gene 
)

Definition at line 193 of file geqo_erx.c.

References edge_failure(), geqo_randint, gimme_gene(), i, and remove_gene().

Referenced by geqo().

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 }
static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
Definition: geqo_erx.c:372
static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:281
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:239
int i
void init_tour ( PlannerInfo root,
Gene tour,
int  num_gene 
)

Definition at line 34 of file geqo_recombination.c.

References geqo_randint, and i.

Referenced by random_init_pool().

35 {
36  int i,
37  j;
38 
39  /*
40  * We must fill the tour[] array with a random permutation of the numbers
41  * 1 .. num_gene. We can do that in one pass using the "inside-out"
42  * variant of the Fisher-Yates shuffle algorithm. Notionally, we append
43  * each new value to the array and then swap it with a randomly-chosen
44  * array element (possibly including itself, else we fail to generate
45  * permutations with the last city last). The swap step can be optimized
46  * by combining it with the insertion.
47  */
48  if (num_gene > 0)
49  tour[0] = (Gene) 1;
50 
51  for (i = 1; i < num_gene; i++)
52  {
53  j = geqo_randint(root, i, 0);
54  /* i != j check avoids fetching uninitialized array element */
55  if (i != j)
56  tour[i] = tour[j];
57  tour[j] = (Gene) (i + 1);
58  }
59 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
int i
void ox1 ( PlannerInfo root,
Gene mom,
Gene dad,
Gene offspring,
int  num_gene,
City city_table 
)

Definition at line 46 of file geqo_ox1.c.

References geqo_randint, and City::used.

Referenced by geqo().

48 {
49  int left,
50  right,
51  k,
52  p,
53  temp;
54 
55  /* initialize city table */
56  for (k = 1; k <= num_gene; k++)
57  city_table[k].used = 0;
58 
59  /* select portion to copy from tour1 */
60  left = geqo_randint(root, num_gene - 1, 0);
61  right = geqo_randint(root, num_gene - 1, 0);
62 
63  if (left > right)
64  {
65  temp = left;
66  left = right;
67  right = temp;
68  }
69 
70  /* copy portion from tour1 to offspring */
71  for (k = left; k <= right; k++)
72  {
73  offspring[k] = tour1[k];
74  city_table[(int) tour1[k]].used = 1;
75  }
76 
77  k = (right + 1) % num_gene; /* index into offspring */
78  p = k; /* index into tour2 */
79 
80  /* copy stuff from tour2 to offspring */
81  while (k != left)
82  {
83  if (!city_table[(int) tour2[p]].used)
84  {
85  offspring[k] = tour2[p];
86  k = (k + 1) % num_gene;
87  city_table[(int) tour2[p]].used = 1;
88  }
89  p = (p + 1) % num_gene; /* increment tour2-index */
90  }
91 
92 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
void ox2 ( PlannerInfo root,
Gene mom,
Gene dad,
Gene offspring,
int  num_gene,
City city_table 
)

Definition at line 46 of file geqo_ox2.c.

References geqo_randint, select, City::select_list, and City::used.

Referenced by geqo().

47 {
48  int k,
49  j,
50  count,
51  pos,
52  select,
53  num_positions;
54 
55  /* initialize city table */
56  for (k = 1; k <= num_gene; k++)
57  {
58  city_table[k].used = 0;
59  city_table[k - 1].select_list = -1;
60  }
61 
62  /* determine the number of positions to be inherited from tour1 */
63  num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
64 
65  /* make a list of selected cities */
66  for (k = 0; k < num_positions; k++)
67  {
68  pos = geqo_randint(root, num_gene - 1, 0);
69  city_table[pos].select_list = (int) tour1[pos];
70  city_table[(int) tour1[pos]].used = 1; /* mark used */
71  }
72 
73 
74  count = 0;
75  k = 0;
76 
77  /* consolidate the select list to adjacent positions */
78  while (count < num_positions)
79  {
80  if (city_table[k].select_list == -1)
81  {
82  j = k + 1;
83  while ((city_table[j].select_list == -1) && (j < num_gene))
84  j++;
85 
86  city_table[k].select_list = city_table[j].select_list;
87  city_table[j].select_list = -1;
88  count++;
89  }
90  else
91  count++;
92  k++;
93  }
94 
95  select = 0;
96 
97  for (k = 0; k < num_gene; k++)
98  {
99  if (city_table[(int) tour2[k]].used)
100  {
101  offspring[k] = (Gene) city_table[select].select_list;
102  select++; /* next city in the select list */
103  }
104  else
105  /* city isn't used yet, so inherit from tour2 */
106  offspring[k] = tour2[k];
107  }
108 
109 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
int select_list
#define select(n, r, w, e, timeout)
Definition: win32.h:384
void pmx ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene 
)

Definition at line 46 of file geqo_pmx.c.

References DAD, geqo_randint, i, MOM, palloc(), and pfree().

Referenced by geqo().

47 {
48  int *failed = (int *) palloc((num_gene + 1) * sizeof(int));
49  int *from = (int *) palloc((num_gene + 1) * sizeof(int));
50  int *indx = (int *) palloc((num_gene + 1) * sizeof(int));
51  int *check_list = (int *) palloc((num_gene + 1) * sizeof(int));
52 
53  int left,
54  right,
55  temp,
56  i,
57  j,
58  k;
59  int mx_fail,
60  found,
61  mx_hold;
62 
63 
64 /* no mutation so start up the pmx replacement algorithm */
65 /* initialize failed[], from[], check_list[] */
66  for (k = 0; k < num_gene; k++)
67  {
68  failed[k] = -1;
69  from[k] = -1;
70  check_list[k + 1] = 0;
71  }
72 
73 /* locate crossover points */
74  left = geqo_randint(root, num_gene - 1, 0);
75  right = geqo_randint(root, num_gene - 1, 0);
76 
77  if (left > right)
78  {
79  temp = left;
80  left = right;
81  right = temp;
82  }
83 
84 
85 /* copy tour2 into offspring */
86  for (k = 0; k < num_gene; k++)
87  {
88  offspring[k] = tour2[k];
89  from[k] = DAD;
90  check_list[tour2[k]]++;
91  }
92 
93 /* copy tour1 into offspring */
94  for (k = left; k <= right; k++)
95  {
96  check_list[offspring[k]]--;
97  offspring[k] = tour1[k];
98  from[k] = MOM;
99  check_list[tour1[k]]++;
100  }
101 
102 
103 /* pmx main part */
104 
105  mx_fail = 0;
106 
107 /* STEP 1 */
108 
109  for (k = left; k <= right; k++)
110  { /* for all elements in the tour1-2 */
111 
112  if (tour1[k] == tour2[k])
113  found = 1; /* find match in tour2 */
114 
115  else
116  {
117  found = 0; /* substitute elements */
118 
119  j = 0;
120  while (!(found) && (j < num_gene))
121  {
122  if ((offspring[j] == tour1[k]) && (from[j] == DAD))
123  {
124 
125  check_list[offspring[j]]--;
126  offspring[j] = tour2[k];
127  found = 1;
128  check_list[tour2[k]]++;
129  }
130 
131  j++;
132  }
133 
134  }
135 
136  if (!(found))
137  { /* failed to replace gene */
138  failed[mx_fail] = (int) tour1[k];
139  indx[mx_fail] = k;
140  mx_fail++;
141  }
142 
143  } /* ... for */
144 
145 
146 /* STEP 2 */
147 
148  /* see if any genes could not be replaced */
149  if (mx_fail > 0)
150  {
151  mx_hold = mx_fail;
152 
153  for (k = 0; k < mx_hold; k++)
154  {
155  found = 0;
156 
157  j = 0;
158  while (!(found) && (j < num_gene))
159  {
160 
161  if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
162  {
163  check_list[offspring[j]]--;
164  offspring[j] = tour2[indx[k]];
165  check_list[tour2[indx[k]]]++;
166 
167  found = 1;
168  failed[k] = -1;
169  mx_fail--;
170  }
171 
172  j++;
173  }
174 
175  } /* ... for */
176 
177  } /* ... if */
178 
179 
180 /* STEP 3 */
181 
182  for (k = 1; k <= num_gene; k++)
183  {
184 
185  if (check_list[k] > 1)
186  {
187  i = 0;
188 
189  while (i < num_gene)
190  {
191  if ((offspring[i] == (Gene) k) && (from[i] == DAD))
192  {
193  j = 1;
194 
195  while (j <= num_gene)
196  {
197  if (check_list[j] == 0)
198  {
199  offspring[i] = (Gene) j;
200  check_list[k]--;
201  check_list[j]++;
202  i = num_gene + 1;
203  j = i;
204  }
205 
206  j++;
207  }
208 
209  } /* ... if */
210 
211  i++;
212  } /* end while */
213 
214  }
215  } /* ... for */
216 
217  pfree(failed);
218  pfree(from);
219  pfree(indx);
220  pfree(check_list);
221 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
void pfree(void *pointer)
Definition: mcxt.c:992
#define DAD
#define MOM
void * palloc(Size size)
Definition: mcxt.c:891
int i
void px ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene,
City city_table 
)

Definition at line 46 of file geqo_px.c.

References geqo_randint, i, and City::used.

Referenced by byteapos(), geqo(), and interpret_function_parameter_list().

48 {
49  int num_positions;
50  int i,
51  pos,
52  tour2_index,
53  offspring_index;
54 
55  /* initialize city table */
56  for (i = 1; i <= num_gene; i++)
57  city_table[i].used = 0;
58 
59  /* choose random positions that will be inherited directly from parent */
60  num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
61 
62  /* choose random position */
63  for (i = 0; i < num_positions; i++)
64  {
65  pos = geqo_randint(root, num_gene - 1, 0);
66 
67  offspring[pos] = tour1[pos]; /* transfer cities to child */
68  city_table[(int) tour1[pos]].used = 1; /* mark city used */
69  }
70 
71  tour2_index = 0;
72  offspring_index = 0;
73 
74 
75  /* px main part */
76 
77  while (offspring_index < num_gene)
78  {
79 
80  /* next position in offspring filled */
81  if (!city_table[(int) tour1[offspring_index]].used)
82  {
83 
84  /* next city in tour1 not used */
85  if (!city_table[(int) tour2[tour2_index]].used)
86  {
87 
88  /* inherit from tour1 */
89  offspring[offspring_index] = tour2[tour2_index];
90 
91  tour2_index++;
92  offspring_index++;
93  }
94  else
95  { /* next city in tour2 has been used */
96  tour2_index++;
97  }
98 
99  }
100  else
101  { /* next position in offspring is filled */
102  offspring_index++;
103  }
104 
105  }
106 
107 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int i