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 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 */
48 21 : new_pool = palloc_object(Pool);
49 21 : new_pool->size = pool_size;
50 21 : new_pool->string_length = string_length;
51 :
52 : /* all chromosome */
53 21 : new_pool->data = palloc_array(Chromosome, pool_size);
54 :
55 : /* all gene */
56 21 : chromo = (Chromosome *) new_pool->data; /* vector of all chromos */
57 1113 : for (i = 0; i < pool_size; i++)
58 1092 : chromo[i].string = palloc_array(Gene, string_length + 1);
59 :
60 21 : return new_pool;
61 : }
62 :
63 : /*
64 : * free_pool
65 : * deallocates memory for GA pool
66 : */
67 : void
68 21 : free_pool(PlannerInfo *root, Pool *pool)
69 : {
70 : Chromosome *chromo;
71 : int i;
72 :
73 : /* all gene */
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);
83 21 : }
84 :
85 : /*
86 : * random_init_pool
87 : * initialize genetic pool
88 : */
89 : void
90 21 : random_init_pool(PlannerInfo *root, Pool *pool)
91 : {
92 21 : Chromosome *chromo = (Chromosome *) pool->data;
93 : int i;
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 : {
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);
110 1092 : if (pool->data[i].worth < DBL_MAX)
111 1092 : 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 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
134 21 : sort_pool(PlannerInfo *root, Pool *pool)
135 : {
136 21 : qsort(pool->data, pool->size, sizeof(Chromosome), compare);
137 21 : }
138 :
139 : /*
140 : * compare
141 : * qsort comparison function for sort_pool
142 : */
143 : static int
144 1071 : compare(const void *arg1, const void *arg2)
145 : {
146 1071 : const Chromosome *chromo1 = (const Chromosome *) arg1;
147 1071 : const Chromosome *chromo2 = (const Chromosome *) arg2;
148 :
149 1071 : if (chromo1->worth == chromo2->worth)
150 1071 : return 0;
151 0 : else if (chromo1->worth > chromo2->worth)
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 *
161 42 : alloc_chromo(PlannerInfo *root, int string_length)
162 : {
163 : Chromosome *chromo;
164 :
165 42 : chromo = palloc_object(Chromosome);
166 42 : chromo->string = palloc_array(Gene, string_length + 1);
167 :
168 42 : return chromo;
169 : }
170 :
171 : /* free_chromo
172 : * deallocates a chromosome and string space
173 : */
174 : void
175 42 : free_chromo(PlannerInfo *root, Chromosome *chromo)
176 : {
177 42 : pfree(chromo->string);
178 42 : pfree(chromo);
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
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 */
197 1092 : 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 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;
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 : }
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 1092 : geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
249 :
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 : }
|
