PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_pool.c
Go to the documentation of this file.
1 /*------------------------------------------------------------------------
2  *
3  * geqo_pool.c
4  * Genetic Algorithm (GA) pool stuff
5  *
6  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  * src/backend/optimizer/geqo/geqo_pool.c
10  *
11  *-------------------------------------------------------------------------
12  */
13 
14 /* contributed by:
15  =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
16  * Martin Utesch * Institute of Automatic Control *
17  = = University of Mining and Technology =
18  * utesch@aut.tu-freiberg.de * Freiberg, Germany *
19  =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
20  */
21 
22 /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
23 
24 #include "postgres.h"
25 
26 #include <float.h>
27 #include <limits.h>
28 #include <math.h>
29 
30 #include "optimizer/geqo_copy.h"
31 #include "optimizer/geqo_pool.h"
33 
34 
35 static int compare(const void *arg1, const void *arg2);
36 
37 /*
38  * alloc_pool
39  * allocates memory for GA pool
40  */
41 Pool *
42 alloc_pool(PlannerInfo *root, int pool_size, int string_length)
43 {
44  Pool *new_pool;
45  Chromosome *chromo;
46  int i;
47 
48  /* pool */
49  new_pool = (Pool *) palloc(sizeof(Pool));
50  new_pool->size = (int) pool_size;
51  new_pool->string_length = (int) string_length;
52 
53  /* all chromosome */
54  new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
55 
56  /* all gene */
57  chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
58  for (i = 0; i < pool_size; i++)
59  chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
60 
61  return new_pool;
62 }
63 
64 /*
65  * free_pool
66  * deallocates memory for GA pool
67  */
68 void
69 free_pool(PlannerInfo *root, Pool *pool)
70 {
71  Chromosome *chromo;
72  int i;
73 
74  /* all gene */
75  chromo = (Chromosome *) pool->data; /* vector of all chromos */
76  for (i = 0; i < pool->size; i++)
77  pfree(chromo[i].string);
78 
79  /* all chromosome */
80  pfree(pool->data);
81 
82  /* pool */
83  pfree(pool);
84 }
85 
86 /*
87  * random_init_pool
88  * initialize genetic pool
89  */
90 void
92 {
93  Chromosome *chromo = (Chromosome *) pool->data;
94  int i;
95  int bad = 0;
96 
97  /*
98  * We immediately discard any invalid individuals (those that geqo_eval
99  * returns DBL_MAX for), thereby not wasting pool space on them.
100  *
101  * If we fail to make any valid individuals after 10000 tries, give up;
102  * this probably means something is broken, and we shouldn't just let
103  * ourselves get stuck in an infinite loop.
104  */
105  i = 0;
106  while (i < pool->size)
107  {
108  init_tour(root, chromo[i].string, pool->string_length);
109  pool->data[i].worth = geqo_eval(root, chromo[i].string,
110  pool->string_length);
111  if (pool->data[i].worth < DBL_MAX)
112  i++;
113  else
114  {
115  bad++;
116  if (i == 0 && bad >= 10000)
117  elog(ERROR, "geqo failed to make a valid plan");
118  }
119  }
120 
121 #ifdef GEQO_DEBUG
122  if (bad > 0)
123  elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
124  bad, pool->size);
125 #endif
126 }
127 
128 /*
129  * sort_pool
130  * sorts input pool according to worth, from smallest to largest
131  *
132  * maybe you have to change compare() for different ordering ...
133  */
134 void
136 {
137  qsort(pool->data, pool->size, sizeof(Chromosome), compare);
138 }
139 
140 /*
141  * compare
142  * qsort comparison function for sort_pool
143  */
144 static int
145 compare(const void *arg1, const void *arg2)
146 {
147  const Chromosome *chromo1 = (const Chromosome *) arg1;
148  const Chromosome *chromo2 = (const Chromosome *) arg2;
149 
150  if (chromo1->worth == chromo2->worth)
151  return 0;
152  else if (chromo1->worth > chromo2->worth)
153  return 1;
154  else
155  return -1;
156 }
157 
158 /* alloc_chromo
159  * allocates a chromosome and string space
160  */
161 Chromosome *
162 alloc_chromo(PlannerInfo *root, int string_length)
163 {
164  Chromosome *chromo;
165 
166  chromo = (Chromosome *) palloc(sizeof(Chromosome));
167  chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
168 
169  return chromo;
170 }
171 
172 /* free_chromo
173  * deallocates a chromosome and string space
174  */
175 void
177 {
178  pfree(chromo->string);
179  pfree(chromo);
180 }
181 
182 /* spread_chromo
183  * inserts a new chromosome into the pool, displacing worst gene in pool
184  * assumes best->worst = smallest->largest
185  */
186 void
187 spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
188 {
189  int top,
190  mid,
191  bot;
192  int i,
193  index;
194  Chromosome swap_chromo,
195  tmp_chromo;
196 
197  /* new chromo is so bad we can't use it */
198  if (chromo->worth > pool->data[pool->size - 1].worth)
199  return;
200 
201  /* do a binary search to find the index of the new chromo */
202 
203  top = 0;
204  mid = pool->size / 2;
205  bot = pool->size - 1;
206  index = -1;
207 
208  while (index == -1)
209  {
210  /* these 4 cases find a new location */
211 
212  if (chromo->worth <= pool->data[top].worth)
213  index = top;
214  else if (chromo->worth == pool->data[mid].worth)
215  index = mid;
216  else if (chromo->worth == pool->data[bot].worth)
217  index = bot;
218  else if (bot - top <= 1)
219  index = bot;
220 
221 
222  /*
223  * these 2 cases move the search indices since a new location has not
224  * yet been found.
225  */
226 
227  else if (chromo->worth < pool->data[mid].worth)
228  {
229  bot = mid;
230  mid = top + ((bot - top) / 2);
231  }
232  else
233  { /* (chromo->worth > pool->data[mid].worth) */
234  top = mid;
235  mid = top + ((bot - top) / 2);
236  }
237  } /* ... while */
238 
239  /* now we have index for chromo */
240 
241  /*
242  * move every gene from index on down one position to make room for chromo
243  */
244 
245  /*
246  * copy new gene into pool storage; always replace worst gene in pool
247  */
248 
249  geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
250 
251  swap_chromo.string = pool->data[pool->size - 1].string;
252  swap_chromo.worth = pool->data[pool->size - 1].worth;
253 
254  for (i = index; i < pool->size; i++)
255  {
256  tmp_chromo.string = pool->data[i].string;
257  tmp_chromo.worth = pool->data[i].worth;
258 
259  pool->data[i].string = swap_chromo.string;
260  pool->data[i].worth = swap_chromo.worth;
261 
262  swap_chromo.string = tmp_chromo.string;
263  swap_chromo.worth = tmp_chromo.worth;
264  }
265 }
void free_chromo(PlannerInfo *root, Chromosome *chromo)
Definition: geqo_pool.c:176
#define DEBUG1
Definition: elog.h:25
Cost geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
Definition: geqo_eval.c:57
void init_tour(PlannerInfo *root, Gene *tour, int num_gene)
Cost worth
Definition: geqo_gene.h:35
int Gene
Definition: geqo_gene.h:30
void random_init_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:91
void spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
Definition: geqo_pool.c:187
int size
Definition: geqo_gene.h:41
Chromosome * alloc_chromo(PlannerInfo *root, int string_length)
Definition: geqo_pool.c:162
Definition: type.h:90
void pfree(void *pointer)
Definition: mcxt.c:992
int string_length
Definition: geqo_gene.h:42
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
#define ERROR
Definition: elog.h:43
void sort_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:135
Pool * alloc_pool(PlannerInfo *root, int pool_size, int string_length)
Definition: geqo_pool.c:42
Definition: geqo_gene.h:38
void geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2, int string_length)
Definition: geqo_copy.c:45
Chromosome * data
Definition: geqo_gene.h:40
void free_pool(PlannerInfo *root, Pool *pool)
Definition: geqo_pool.c:69
void * palloc(Size size)
Definition: mcxt.c:891
int i
Gene * string
Definition: geqo_gene.h:34
#define elog
Definition: elog.h:219
#define qsort(a, b, c, d)
Definition: port.h:440