1/*------------------------------------------------------------------------
2 *
3 * geqo_pool.c
4 * Genetic Algorithm (GA) pool stuff
5 *
6 * Portions Copyright (c) 1996-2019, 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"
32#include "optimizer/geqo_recombination.h"
33
34
35static int compare(const void *arg1, const void *arg2);
36
37/*
38 * alloc_pool
39 * allocates memory for GA pool
40 */
41Pool *
42alloc_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 */
68void
69free_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 */
90void
91random_init_pool(PlannerInfo *root, Pool *pool)
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 */
134void
135sort_pool(PlannerInfo *root, Pool *pool)
136{
137 qsort(pool->data, pool->size, sizeof(Chromosome), compare);
138}
139
140/*
141 * compare
142 * qsort comparison function for sort_pool
143 */
144static int
145compare(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 */
161Chromosome *
162alloc_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 */
175void
176free_chromo(PlannerInfo *root, Chromosome *chromo)
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 */
186void
187spread_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}
266