Age Owner Branch data TLA 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 *
5386 tgl@sss.pgh.pa.us 42 :CBC 3 : alloc_pool(PlannerInfo *root, int pool_size, int string_length)
43 : : {
44 : : Pool *new_pool;
45 : : Chromosome *chromo;
46 : : int i;
47 : :
48 : : /* pool */
9716 bruce@momjian.us 49 : 3 : new_pool = (Pool *) palloc(sizeof(Pool));
50 : 3 : new_pool->size = (int) pool_size;
51 : 3 : new_pool->string_length = (int) string_length;
52 : :
53 : : /* all chromosome */
54 : 3 : new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
55 : :
56 : : /* all gene */
2489 tgl@sss.pgh.pa.us 57 : 3 : chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
9716 bruce@momjian.us 58 [ + + ]: 195 : for (i = 0; i < pool_size; i++)
59 : 192 : chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
60 : :
9357 61 : 3 : return new_pool;
62 : : }
63 : :
64 : : /*
65 : : * free_pool
66 : : * deallocates memory for GA pool
67 : : */
68 : : void
5386 tgl@sss.pgh.pa.us 69 : 3 : free_pool(PlannerInfo *root, Pool *pool)
70 : : {
71 : : Chromosome *chromo;
72 : : int i;
73 : :
74 : : /* all gene */
9716 bruce@momjian.us 75 : 3 : chromo = (Chromosome *) pool->data; /* vector of all chromos */
76 [ + + ]: 195 : for (i = 0; i < pool->size; i++)
77 : 192 : pfree(chromo[i].string);
78 : :
79 : : /* all chromosome */
80 : 3 : pfree(pool->data);
81 : :
82 : : /* pool */
83 : 3 : pfree(pool);
9916 scrappy@hub.org 84 : 3 : }
85 : :
86 : : /*
87 : : * random_init_pool
88 : : * initialize genetic pool
89 : : */
90 : : void
5386 tgl@sss.pgh.pa.us 91 : 3 : random_init_pool(PlannerInfo *root, Pool *pool)
92 : : {
9715 bruce@momjian.us 93 : 3 : Chromosome *chromo = (Chromosome *) pool->data;
94 : : int i;
3351 tgl@sss.pgh.pa.us 95 : 3 : 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 : 3 : i = 0;
106 [ + + ]: 195 : while (i < pool->size)
107 : : {
5386 108 : 192 : init_tour(root, chromo[i].string, pool->string_length);
109 : 192 : pool->data[i].worth = geqo_eval(root, chromo[i].string,
110 : : pool->string_length);
3351 111 [ + - ]: 192 : if (pool->data[i].worth < DBL_MAX)
112 : 192 : i++;
113 : : else
114 : : {
3351 tgl@sss.pgh.pa.us 115 :UBC 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
9916 scrappy@hub.org 126 :CBC 3 : }
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
5386 tgl@sss.pgh.pa.us 135 : 3 : sort_pool(PlannerInfo *root, Pool *pool)
136 : : {
9512 bruce@momjian.us 137 : 3 : qsort(pool->data, pool->size, sizeof(Chromosome), compare);
9916 scrappy@hub.org 138 : 3 : }
139 : :
140 : : /*
141 : : * compare
142 : : * qsort comparison function for sort_pool
143 : : */
144 : : static int
9505 bruce@momjian.us 145 : 189 : compare(const void *arg1, const void *arg2)
146 : : {
7387 tgl@sss.pgh.pa.us 147 : 189 : const Chromosome *chromo1 = (const Chromosome *) arg1;
148 : 189 : const Chromosome *chromo2 = (const Chromosome *) arg2;
149 : :
150 [ + - ]: 189 : if (chromo1->worth == chromo2->worth)
9357 bruce@momjian.us 151 : 189 : return 0;
7387 tgl@sss.pgh.pa.us 152 [ # # ]:UBC 0 : else if (chromo1->worth > chromo2->worth)
9357 bruce@momjian.us 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 *
5386 tgl@sss.pgh.pa.us 162 :CBC 6 : alloc_chromo(PlannerInfo *root, int string_length)
163 : : {
164 : : Chromosome *chromo;
165 : :
9716 bruce@momjian.us 166 : 6 : chromo = (Chromosome *) palloc(sizeof(Chromosome));
167 : 6 : chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
168 : :
9357 169 : 6 : return chromo;
170 : : }
171 : :
172 : : /* free_chromo
173 : : * deallocates a chromosome and string space
174 : : */
175 : : void
5386 tgl@sss.pgh.pa.us 176 : 6 : free_chromo(PlannerInfo *root, Chromosome *chromo)
177 : : {
9716 bruce@momjian.us 178 : 6 : pfree(chromo->string);
179 : 6 : pfree(chromo);
9916 scrappy@hub.org 180 : 6 : }
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
5386 tgl@sss.pgh.pa.us 187 : 192 : 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 */
9716 bruce@momjian.us 198 [ - + ]: 192 : if (chromo->worth > pool->data[pool->size - 1].worth)
9716 bruce@momjian.us 199 :UBC 0 : return;
200 : :
201 : : /* do a binary search to find the index of the new chromo */
202 : :
9716 bruce@momjian.us 203 :CBC 192 : top = 0;
204 : 192 : mid = pool->size / 2;
205 : 192 : bot = pool->size - 1;
206 : 192 : index = -1;
207 : :
208 [ + + ]: 384 : while (index == -1)
209 : : {
210 : : /* these 4 cases find a new location */
211 : :
212 [ + - ]: 192 : if (chromo->worth <= pool->data[top].worth)
213 : 192 : index = top;
9716 bruce@momjian.us 214 [ # # ]:UBC 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 : :
5386 tgl@sss.pgh.pa.us 249 :CBC 192 : geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
250 : :
9716 bruce@momjian.us 251 : 192 : swap_chromo.string = pool->data[pool->size - 1].string;
252 : 192 : swap_chromo.worth = pool->data[pool->size - 1].worth;
253 : :
254 [ + + ]: 12480 : for (i = index; i < pool->size; i++)
255 : : {
256 : 12288 : tmp_chromo.string = pool->data[i].string;
257 : 12288 : tmp_chromo.worth = pool->data[i].worth;
258 : :
259 : 12288 : pool->data[i].string = swap_chromo.string;
260 : 12288 : pool->data[i].worth = swap_chromo.worth;
261 : :
262 : 12288 : swap_chromo.string = tmp_chromo.string;
263 : 12288 : swap_chromo.worth = tmp_chromo.worth;
264 : : }
265 : : }
|
