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 : }
|
