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