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