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 : : /*
15 : : * contributed by:
16 : : * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
17 : : * * Martin Utesch * Institute of Automatic Control *
18 : : * = = University of Mining and Technology =
19 : : * * utesch@aut.tu-freiberg.de * Freiberg, Germany *
20 : : * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
21 : : */
22 : :
23 : : /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
24 : :
25 : : #include "postgres.h"
26 : :
27 : : #include <float.h>
28 : : #include <limits.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 : 35 : 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 : 35 : new_pool = palloc_object(Pool);
50 : 35 : new_pool->size = pool_size;
51 : 35 : new_pool->string_length = string_length;
52 : :
53 : : /* all chromosome */
54 : 35 : new_pool->data = palloc_array(Chromosome, pool_size);
55 : :
56 : : /* all gene */
57 : 35 : chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
58 [ + + ]: 1855 : for (i = 0; i < pool_size; i++)
59 : 1820 : chromo[i].string = palloc_array(Gene, string_length + 1);
60 : :
61 : 35 : return new_pool;
62 : : }
63 : :
64 : : /*
65 : : * free_pool
66 : : * deallocates memory for GA pool
67 : : */
68 : : void
69 : 35 : free_pool(PlannerInfo *root, Pool *pool)
70 : : {
71 : : Chromosome *chromo;
72 : : int i;
73 : :
74 : : /* all gene */
75 : 35 : chromo = (Chromosome *) pool->data; /* vector of all chromos */
76 [ + + ]: 1855 : for (i = 0; i < pool->size; i++)
77 : 1820 : pfree(chromo[i].string);
78 : :
79 : : /* all chromosome */
80 : 35 : pfree(pool->data);
81 : :
82 : : /* pool */
83 : 35 : pfree(pool);
84 : 35 : }
85 : :
86 : : /*
87 : : * random_init_pool
88 : : * initialize genetic pool
89 : : */
90 : : void
91 : 35 : random_init_pool(PlannerInfo *root, Pool *pool)
92 : : {
93 : 35 : Chromosome *chromo = (Chromosome *) pool->data;
94 : : int i;
95 : 35 : 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 : 35 : i = 0;
106 [ + + ]: 1855 : while (i < pool->size)
107 : : {
108 : 1820 : init_tour(root, chromo[i].string, pool->string_length);
109 : 1820 : pool->data[i].worth = geqo_eval(root, chromo[i].string,
110 : : pool->string_length);
111 [ + - ]: 1820 : if (pool->data[i].worth < DBL_MAX)
112 : 1820 : 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 : 35 : }
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 : 35 : sort_pool(PlannerInfo *root, Pool *pool)
136 : : {
137 : 35 : qsort(pool->data, pool->size, sizeof(Chromosome), compare);
138 : 35 : }
139 : :
140 : : /*
141 : : * compare
142 : : * qsort comparison function for sort_pool
143 : : */
144 : : static int
145 : 1785 : compare(const void *arg1, const void *arg2)
146 : : {
147 : 1785 : const Chromosome *chromo1 = (const Chromosome *) arg1;
148 : 1785 : const Chromosome *chromo2 = (const Chromosome *) arg2;
149 : :
150 [ + - ]: 1785 : if (chromo1->worth == chromo2->worth)
151 : 1785 : return 0;
152 [ # # ]: 0 : else if (chromo1->worth > chromo2->worth)
153 : 0 : return 1;
154 : : else
155 : 0 : return -1;
156 : : }
157 : :
158 : : /*
159 : : * alloc_chromo
160 : : * allocates a chromosome and string space
161 : : */
162 : : Chromosome *
163 : 70 : alloc_chromo(PlannerInfo *root, int string_length)
164 : : {
165 : : Chromosome *chromo;
166 : :
167 : 70 : chromo = palloc_object(Chromosome);
168 : 70 : chromo->string = palloc_array(Gene, string_length + 1);
169 : :
170 : 70 : return chromo;
171 : : }
172 : :
173 : : /*
174 : : * free_chromo
175 : : * deallocates a chromosome and string space
176 : : */
177 : : void
178 : 70 : free_chromo(PlannerInfo *root, Chromosome *chromo)
179 : : {
180 : 70 : pfree(chromo->string);
181 : 70 : pfree(chromo);
182 : 70 : }
183 : :
184 : : /*
185 : : * spread_chromo
186 : : * inserts a new chromosome into the pool, displacing worst gene in pool
187 : : * assumes best->worst = smallest->largest
188 : : */
189 : : void
190 : 1820 : spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
191 : : {
192 : : int top,
193 : : mid,
194 : : bot;
195 : : int i,
196 : : index;
197 : : Chromosome swap_chromo,
198 : : tmp_chromo;
199 : :
200 : : /* new chromo is so bad we can't use it */
201 [ - + ]: 1820 : if (chromo->worth > pool->data[pool->size - 1].worth)
202 : 0 : return;
203 : :
204 : : /* do a binary search to find the index of the new chromo */
205 : :
206 : 1820 : top = 0;
207 : 1820 : mid = pool->size / 2;
208 : 1820 : bot = pool->size - 1;
209 : 1820 : index = -1;
210 : :
211 [ + + ]: 3640 : while (index == -1)
212 : : {
213 : : /* these 4 cases find a new location */
214 : :
215 [ + - ]: 1820 : if (chromo->worth <= pool->data[top].worth)
216 : 1820 : index = top;
217 [ # # ]: 0 : else if (chromo->worth == pool->data[mid].worth)
218 : 0 : index = mid;
219 [ # # ]: 0 : else if (chromo->worth == pool->data[bot].worth)
220 : 0 : index = bot;
221 [ # # ]: 0 : else if (bot - top <= 1)
222 : 0 : index = bot;
223 : :
224 : :
225 : : /*
226 : : * these 2 cases move the search indices since a new location has not
227 : : * yet been found.
228 : : */
229 : :
230 [ # # ]: 0 : else if (chromo->worth < pool->data[mid].worth)
231 : : {
232 : 0 : bot = mid;
233 : 0 : mid = top + ((bot - top) / 2);
234 : : }
235 : : else
236 : : { /* (chromo->worth > pool->data[mid].worth) */
237 : 0 : top = mid;
238 : 0 : mid = top + ((bot - top) / 2);
239 : : }
240 : : } /* ... while */
241 : :
242 : : /* now we have index for chromo */
243 : :
244 : : /*
245 : : * move every gene from index on down one position to make room for chromo
246 : : */
247 : :
248 : : /*
249 : : * copy new gene into pool storage; always replace worst gene in pool
250 : : */
251 : :
252 : 1820 : geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
253 : :
254 : 1820 : swap_chromo.string = pool->data[pool->size - 1].string;
255 : 1820 : swap_chromo.worth = pool->data[pool->size - 1].worth;
256 : :
257 [ + + ]: 97300 : for (i = index; i < pool->size; i++)
258 : : {
259 : 95480 : tmp_chromo.string = pool->data[i].string;
260 : 95480 : tmp_chromo.worth = pool->data[i].worth;
261 : :
262 : 95480 : pool->data[i].string = swap_chromo.string;
263 : 95480 : pool->data[i].worth = swap_chromo.worth;
264 : :
265 : 95480 : swap_chromo.string = tmp_chromo.string;
266 : 95480 : swap_chromo.worth = tmp_chromo.worth;
267 : : }
268 : : }
|
