granicus.if.org Git - postgresql/blob - src/backend/optimizer/geqo/geqo_pool.c

   1 /*------------------------------------------------------------------------
   2  *
   3  * geqo_pool.c
   4  *        Genetic Algorithm (GA) pool stuff
   5  *
   6  * Portions Copyright (c) 1996-2004, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_pool.c,v 1.25 2004/08/29 05:06:43 momjian Exp $
  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 #include <math.h>
  29
  30 #include "optimizer/geqo.h"
  31 #include "optimizer/geqo_copy.h"
  32 #include "optimizer/geqo_pool.h"
  33 #include "optimizer/geqo_recombination.h"
  34
  35
  36 static int      compare(const void *arg1, const void *arg2);
  37
  38 /*
  39  * alloc_pool
  40  *              allocates memory for GA pool
  41  */
  42 Pool *
  43 alloc_pool(int pool_size, int string_length)
  44 {
  45         Pool       *new_pool;
  46         Chromosome *chromo;
  47         int                     i;
  48
  49         /* pool */
  50         new_pool = (Pool *) palloc(sizeof(Pool));
  51         new_pool->size = (int) pool_size;
  52         new_pool->string_length = (int) string_length;
  53
  54         /* all chromosome */
  55         new_pool->data = (Chromosome *) palloc(pool_size * sizeof(Chromosome));
  56
  57         /* all gene */
  58         chromo = (Chromosome *) new_pool->data;         /* vector of all chromos */
  59         for (i = 0; i < pool_size; i++)
  60                 chromo[i].string = palloc((string_length + 1) * sizeof(Gene));
  61
  62         return new_pool;
  63 }
  64
  65 /*
  66  * free_pool
  67  *              deallocates memory for GA pool
  68  */
  69 void
  70 free_pool(Pool *pool)
  71 {
  72         Chromosome *chromo;
  73         int                     i;
  74
  75         /* all gene */
  76         chromo = (Chromosome *) pool->data; /* vector of all chromos */
  77         for (i = 0; i < pool->size; i++)
  78                 pfree(chromo[i].string);
  79
  80         /* all chromosome */
  81         pfree(pool->data);
  82
  83         /* pool */
  84         pfree(pool);
  85 }
  86
  87 /*
  88  * random_init_pool
  89  *              initialize genetic pool
  90  */
  91 void
  92 random_init_pool(Pool *pool, GeqoEvalData *evaldata)
  93 {
  94         Chromosome *chromo = (Chromosome *) pool->data;
  95         int                     i;
  96         int                     bad = 0;
  97
  98         /*
  99          * We immediately discard any invalid individuals (those that
 100          * geqo_eval returns DBL_MAX for), thereby not wasting pool space on
 101          * them.
 102          *
 103          * If we fail to make any valid individuals after 10000 tries, give up;
 104          * this probably means something is broken, and we shouldn't just let
 105          * ourselves get stuck in an infinite loop.
 106          */
 107         i = 0;
 108         while (i < pool->size)
 109         {
 110                 init_tour(chromo[i].string, pool->string_length);
 111                 pool->data[i].worth = geqo_eval(chromo[i].string,
 112                                                                                 pool->string_length,
 113                                                                                 evaldata);
 114                 if (pool->data[i].worth < DBL_MAX)
 115                         i++;
 116                 else
 117                 {
 118                         bad++;
 119                         if (i == 0 && bad >= 10000)
 120                                 elog(ERROR, "failed to make a valid plan");
 121                 }
 122         }
 123
 124 #ifdef GEQO_DEBUG
 125         if (bad > 0)
 126                 elog(DEBUG1, "%d invalid tours found while selecting %d pool entries",
 127                          bad, pool->size);
 128 #endif
 129 }
 130
 131 /*
 132  * sort_pool
 133  *       sorts input pool according to worth, from smallest to largest
 134  *
 135  *       maybe you have to change compare() for different ordering ...
 136  */
 137 void
 138 sort_pool(Pool *pool)
 139 {
 140         qsort(pool->data, pool->size, sizeof(Chromosome), compare);
 141 }
 142
 143 /*
 144  * compare
 145  *       qsort comparison function for sort_pool
 146  */
 147 static int
 148 compare(const void *arg1, const void *arg2)
 149 {
 150         const Chromosome *chromo1 = (const Chromosome *) arg1;
 151         const Chromosome *chromo2 = (const Chromosome *) arg2;
 152
 153         if (chromo1->worth == chromo2->worth)
 154                 return 0;
 155         else if (chromo1->worth > chromo2->worth)
 156                 return 1;
 157         else
 158                 return -1;
 159 }
 160
 161 /* alloc_chromo
 162  *        allocates a chromosome and string space
 163  */
 164 Chromosome *
 165 alloc_chromo(int string_length)
 166 {
 167         Chromosome *chromo;
 168
 169         chromo = (Chromosome *) palloc(sizeof(Chromosome));
 170         chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
 171
 172         return chromo;
 173 }
 174
 175 /* free_chromo
 176  *        deallocates a chromosome and string space
 177  */
 178 void
 179 free_chromo(Chromosome *chromo)
 180 {
 181         pfree(chromo->string);
 182         pfree(chromo);
 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 spread_chromo(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         if (chromo->worth > pool->data[pool->size - 1].worth)
 202                 return;
 203
 204         /* do a binary search to find the index of the new chromo */
 205
 206         top = 0;
 207         mid = pool->size / 2;
 208         bot = pool->size - 1;
 209         index = -1;
 210
 211         while (index == -1)
 212         {
 213                 /* these 4 cases find a new location */
 214
 215                 if (chromo->worth <= pool->data[top].worth)
 216                         index = top;
 217                 else if (chromo->worth == pool->data[mid].worth)
 218                         index = mid;
 219                 else if (chromo->worth == pool->data[bot].worth)
 220                         index = bot;
 221                 else if (bot - top <= 1)
 222                         index = bot;
 223
 224
 225                 /*
 226                  * these 2 cases move the search indices since a new location has
 227                  * not yet been found.
 228                  */
 229
 230                 else if (chromo->worth < pool->data[mid].worth)
 231                 {
 232                         bot = mid;
 233                         mid = top + ((bot - top) / 2);
 234                 }
 235                 else
 236                 {                                               /* (chromo->worth > pool->data[mid].worth) */
 237                         top = mid;
 238                         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
 246          * chromo
 247          */
 248
 249         /*
 250          * copy new gene into pool storage; always replace worst gene in pool
 251          */
 252
 253         geqo_copy(&pool->data[pool->size - 1], chromo, pool->string_length);
 254
 255         swap_chromo.string = pool->data[pool->size - 1].string;
 256         swap_chromo.worth = pool->data[pool->size - 1].worth;
 257
 258         for (i = index; i < pool->size; i++)
 259         {
 260                 tmp_chromo.string = pool->data[i].string;
 261                 tmp_chromo.worth = pool->data[i].worth;
 262
 263                 pool->data[i].string = swap_chromo.string;
 264                 pool->data[i].worth = swap_chromo.worth;
 265
 266                 swap_chromo.string = tmp_chromo.string;
 267                 swap_chromo.worth = tmp_chromo.worth;
 268         }
 269 }