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