Line data Source code
1 : /*------------------------------------------------------------------------
2 : *
3 : * geqo_pool.c
4 : * Genetic Algorithm (GA) pool stuff
5 : *
6 : * Portions Copyright (c) 1996-2024, 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 :
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 6 : 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 6 : new_pool = (Pool *) palloc(sizeof(Pool));
50 6 : new_pool->size = (int) pool_size;
51 6 : new_pool->string_length = (int) string_length;
52 :
53 : /* all chromosome */
54 6 : new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
55 :
56 : /* all gene */
57 6 : chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
58 390 : for (i = 0; i < pool_size; i++)
59 384 : chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
60 :
61 6 : return new_pool;
62 : }
63 :
64 : /*
65 : * free_pool
66 : * deallocates memory for GA pool
67 : */
68 : void
69 6 : free_pool(PlannerInfo *root, Pool *pool)
70 : {
71 : Chromosome *chromo;
72 : int i;
73 :
74 : /* all gene */
75 6 : chromo = (Chromosome *) pool->data; /* vector of all chromos */
76 390 : for (i = 0; i < pool->size; i++)
77 384 : pfree(chromo[i].string);
78 :
79 : /* all chromosome */
80 6 : pfree(pool->data);
81 :
82 : /* pool */
83 6 : pfree(pool);
84 6 : }
85 :
86 : /*
87 : * random_init_pool
88 : * initialize genetic pool
89 : */
90 : void
91 6 : random_init_pool(PlannerInfo *root, Pool *pool)
92 : {
93 6 : Chromosome *chromo = (Chromosome *) pool->data;
94 : int i;
95 6 : 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 6 : i = 0;
106 390 : while (i < pool->size)
107 : {
108 384 : init_tour(root, chromo[i].string, pool->string_length);
109 384 : pool->data[i].worth = geqo_eval(root, chromo[i].string,
110 : pool->string_length);
111 384 : if (pool->data[i].worth < DBL_MAX)
112 384 : i++;
113 : else
114 : {
115 0 : bad++;
116 0 : if (i == 0 && bad >= 10000)
117 0 : 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 6 : }
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
135 6 : sort_pool(PlannerInfo *root, Pool *pool)
136 : {
137 6 : qsort(pool->data, pool->size, sizeof(Chromosome), compare);
138 6 : }
139 :
140 : /*
141 : * compare
142 : * qsort comparison function for sort_pool
143 : */
144 : static int
145 378 : compare(const void *arg1, const void *arg2)
146 : {
147 378 : const Chromosome *chromo1 = (const Chromosome *) arg1;
148 378 : const Chromosome *chromo2 = (const Chromosome *) arg2;
149 :
150 378 : if (chromo1->worth == chromo2->worth)
151 378 : return 0;
152 0 : else if (chromo1->worth > chromo2->worth)
153 0 : return 1;
154 : else
155 0 : return -1;
156 : }
157 :
158 : /* alloc_chromo
159 : * allocates a chromosome and string space
160 : */
161 : Chromosome *
162 12 : alloc_chromo(PlannerInfo *root, int string_length)
163 : {
164 : Chromosome *chromo;
165 :
166 12 : chromo = (Chromosome *) palloc(sizeof(Chromosome));
167 12 : chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
168 :
169 12 : return chromo;
170 : }
171 :
172 : /* free_chromo
173 : * deallocates a chromosome and string space
174 : */
175 : void
176 12 : free_chromo(PlannerInfo *root, Chromosome *chromo)
177 : {
178 12 : pfree(chromo->string);
179 12 : pfree(chromo);
180 12 : }
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 384 : 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 384 : if (chromo->worth > pool->data[pool->size - 1].worth)
199 0 : return;
200 :
201 : /* do a binary search to find the index of the new chromo */
202 :
203 384 : top = 0;
204 384 : mid = pool->size / 2;
205 384 : bot = pool->size - 1;
206 384 : index = -1;
207 :
208 768 : while (index == -1)
209 : {
210 : /* these 4 cases find a new location */
211 :
212 384 : if (chromo->worth <= pool->data[top].worth)
213 384 : index = top;
214 0 : else if (chromo->worth == pool->data[mid].worth)
215 0 : index = mid;
216 0 : else if (chromo->worth == pool->data[bot].worth)
217 0 : index = bot;
218 0 : else if (bot - top <= 1)
219 0 : 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 0 : else if (chromo->worth < pool->data[mid].worth)
228 : {
229 0 : bot = mid;
230 0 : mid = top + ((bot - top) / 2);
231 : }
232 : else
233 : { /* (chromo->worth > pool->data[mid].worth) */
234 0 : top = mid;
235 0 : 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 384 : geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
250 :
251 384 : swap_chromo.string = pool->data[pool->size - 1].string;
252 384 : swap_chromo.worth = pool->data[pool->size - 1].worth;
253 :
254 24960 : for (i = index; i < pool->size; i++)
255 : {
256 24576 : tmp_chromo.string = pool->data[i].string;
257 24576 : tmp_chromo.worth = pool->data[i].worth;
258 :
259 24576 : pool->data[i].string = swap_chromo.string;
260 24576 : pool->data[i].worth = swap_chromo.worth;
261 :
262 24576 : swap_chromo.string = tmp_chromo.string;
263 24576 : swap_chromo.worth = tmp_chromo.worth;
264 : }
265 : }
|
