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-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 *
6086 tgl@sss.pgh.pa.us 41 :CBC 21 : alloc_pool(PlannerInfo *root, int pool_size, int string_length)
42 : : {
43 : : Pool *new_pool;
44 : : Chromosome *chromo;
45 : : int i;
46 : :
47 : : /* pool */
95 michael@paquier.xyz 48 :GNC 21 : new_pool = palloc_object(Pool);
103 peter@eisentraut.org 49 : 21 : new_pool->size = pool_size;
50 : 21 : new_pool->string_length = string_length;
51 : :
52 : : /* all chromosome */
95 michael@paquier.xyz 53 : 21 : new_pool->data = palloc_array(Chromosome, pool_size);
54 : :
55 : : /* all gene */
3189 tgl@sss.pgh.pa.us 56 :CBC 21 : chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
10416 bruce@momjian.us 57 [ + + ]: 1113 : for (i = 0; i < pool_size; i++)
95 michael@paquier.xyz 58 :GNC 1092 : chromo[i].string = palloc_array(Gene, string_length + 1);
59 : :
10057 bruce@momjian.us 60 :CBC 21 : return new_pool;
61 : : }
62 : :
63 : : /*
64 : : * free_pool
65 : : * deallocates memory for GA pool
66 : : */
67 : : void
6086 tgl@sss.pgh.pa.us 68 : 21 : free_pool(PlannerInfo *root, Pool *pool)
69 : : {
70 : : Chromosome *chromo;
71 : : int i;
72 : :
73 : : /* all gene */
10416 bruce@momjian.us 74 : 21 : chromo = (Chromosome *) pool->data; /* vector of all chromos */
75 [ + + ]: 1113 : for (i = 0; i < pool->size; i++)
76 : 1092 : pfree(chromo[i].string);
77 : :
78 : : /* all chromosome */
79 : 21 : pfree(pool->data);
80 : :
81 : : /* pool */
82 : 21 : pfree(pool);
10616 scrappy@hub.org 83 : 21 : }
84 : :
85 : : /*
86 : : * random_init_pool
87 : : * initialize genetic pool
88 : : */
89 : : void
6086 tgl@sss.pgh.pa.us 90 : 21 : random_init_pool(PlannerInfo *root, Pool *pool)
91 : : {
10415 bruce@momjian.us 92 : 21 : Chromosome *chromo = (Chromosome *) pool->data;
93 : : int i;
4051 tgl@sss.pgh.pa.us 94 : 21 : 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 : 21 : i = 0;
105 [ + + ]: 1113 : while (i < pool->size)
106 : : {
6086 107 : 1092 : init_tour(root, chromo[i].string, pool->string_length);
108 : 1092 : pool->data[i].worth = geqo_eval(root, chromo[i].string,
109 : : pool->string_length);
4051 110 [ + - ]: 1092 : if (pool->data[i].worth < DBL_MAX)
111 : 1092 : i++;
112 : : else
113 : : {
4051 tgl@sss.pgh.pa.us 114 :UBC 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
10616 scrappy@hub.org 125 :CBC 21 : }
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
6086 tgl@sss.pgh.pa.us 134 : 21 : sort_pool(PlannerInfo *root, Pool *pool)
135 : : {
10212 bruce@momjian.us 136 : 21 : qsort(pool->data, pool->size, sizeof(Chromosome), compare);
10616 scrappy@hub.org 137 : 21 : }
138 : :
139 : : /*
140 : : * compare
141 : : * qsort comparison function for sort_pool
142 : : */
143 : : static int
10205 bruce@momjian.us 144 : 1071 : compare(const void *arg1, const void *arg2)
145 : : {
8087 tgl@sss.pgh.pa.us 146 : 1071 : const Chromosome *chromo1 = (const Chromosome *) arg1;
147 : 1071 : const Chromosome *chromo2 = (const Chromosome *) arg2;
148 : :
149 [ + - ]: 1071 : if (chromo1->worth == chromo2->worth)
10057 bruce@momjian.us 150 : 1071 : return 0;
8087 tgl@sss.pgh.pa.us 151 [ # # ]:UBC 0 : else if (chromo1->worth > chromo2->worth)
10057 bruce@momjian.us 152 : 0 : return 1;
153 : : else
154 : 0 : return -1;
155 : : }
156 : :
157 : : /* alloc_chromo
158 : : * allocates a chromosome and string space
159 : : */
160 : : Chromosome *
6086 tgl@sss.pgh.pa.us 161 :CBC 42 : alloc_chromo(PlannerInfo *root, int string_length)
162 : : {
163 : : Chromosome *chromo;
164 : :
95 michael@paquier.xyz 165 :GNC 42 : chromo = palloc_object(Chromosome);
166 : 42 : chromo->string = palloc_array(Gene, string_length + 1);
167 : :
10057 bruce@momjian.us 168 :CBC 42 : return chromo;
169 : : }
170 : :
171 : : /* free_chromo
172 : : * deallocates a chromosome and string space
173 : : */
174 : : void
6086 tgl@sss.pgh.pa.us 175 : 42 : free_chromo(PlannerInfo *root, Chromosome *chromo)
176 : : {
10416 bruce@momjian.us 177 : 42 : pfree(chromo->string);
178 : 42 : pfree(chromo);
10616 scrappy@hub.org 179 : 42 : }
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
6086 tgl@sss.pgh.pa.us 186 : 1092 : spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
187 : : {
188 : : int top,
189 : : mid,
190 : : bot;
191 : : int i,
192 : : index;
193 : : Chromosome swap_chromo,
194 : : tmp_chromo;
195 : :
196 : : /* new chromo is so bad we can't use it */
10416 bruce@momjian.us 197 [ - + ]: 1092 : if (chromo->worth > pool->data[pool->size - 1].worth)
10416 bruce@momjian.us 198 :UBC 0 : return;
199 : :
200 : : /* do a binary search to find the index of the new chromo */
201 : :
10416 bruce@momjian.us 202 :CBC 1092 : top = 0;
203 : 1092 : mid = pool->size / 2;
204 : 1092 : bot = pool->size - 1;
205 : 1092 : index = -1;
206 : :
207 [ + + ]: 2184 : while (index == -1)
208 : : {
209 : : /* these 4 cases find a new location */
210 : :
211 [ + - ]: 1092 : if (chromo->worth <= pool->data[top].worth)
212 : 1092 : index = top;
10416 bruce@momjian.us 213 [ # # ]:UBC 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 : : }
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 : :
6086 tgl@sss.pgh.pa.us 248 :CBC 1092 : geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
249 : :
10416 bruce@momjian.us 250 : 1092 : swap_chromo.string = pool->data[pool->size - 1].string;
251 : 1092 : swap_chromo.worth = pool->data[pool->size - 1].worth;
252 : :
253 [ + + ]: 58380 : for (i = index; i < pool->size; i++)
254 : : {
255 : 57288 : tmp_chromo.string = pool->data[i].string;
256 : 57288 : tmp_chromo.worth = pool->data[i].worth;
257 : :
258 : 57288 : pool->data[i].string = swap_chromo.string;
259 : 57288 : pool->data[i].worth = swap_chromo.worth;
260 : :
261 : 57288 : swap_chromo.string = tmp_chromo.string;
262 : 57288 : swap_chromo.worth = tmp_chromo.worth;
263 : : }
264 : : }
|
