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-2013, 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 #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
  96         for (i = 0; i < pool->size; i++)
  97         {
  98                 init_tour(root, chromo[i].string, pool->string_length);
  99                 pool->data[i].worth = geqo_eval(root, chromo[i].string,
 100                                                                                 pool->string_length);
 101         }
 102 }
 103
 104 /*
 105  * sort_pool
 106  *       sorts input pool according to worth, from smallest to largest
 107  *
 108  *       maybe you have to change compare() for different ordering ...
 109  */
 110 void
 111 sort_pool(PlannerInfo *root, Pool *pool)
 112 {
 113         qsort(pool->data, pool->size, sizeof(Chromosome), compare);
 114 }
 115
 116 /*
 117  * compare
 118  *       qsort comparison function for sort_pool
 119  */
 120 static int
 121 compare(const void *arg1, const void *arg2)
 122 {
 123         const Chromosome *chromo1 = (const Chromosome *) arg1;
 124         const Chromosome *chromo2 = (const Chromosome *) arg2;
 125
 126         if (chromo1->worth == chromo2->worth)
 127                 return 0;
 128         else if (chromo1->worth > chromo2->worth)
 129                 return 1;
 130         else
 131                 return -1;
 132 }
 133
 134 /* alloc_chromo
 135  *        allocates a chromosome and string space
 136  */
 137 Chromosome *
 138 alloc_chromo(PlannerInfo *root, int string_length)
 139 {
 140         Chromosome *chromo;
 141
 142         chromo = (Chromosome *) palloc(sizeof(Chromosome));
 143         chromo->string = (Gene *) palloc((string_length + 1) * sizeof(Gene));
 144
 145         return chromo;
 146 }
 147
 148 /* free_chromo
 149  *        deallocates a chromosome and string space
 150  */
 151 void
 152 free_chromo(PlannerInfo *root, Chromosome *chromo)
 153 {
 154         pfree(chromo->string);
 155         pfree(chromo);
 156 }
 157
 158 /* spread_chromo
 159  *       inserts a new chromosome into the pool, displacing worst gene in pool
 160  *       assumes best->worst = smallest->largest
 161  */
 162 void
 163 spread_chromo(PlannerInfo *root, Chromosome *chromo, Pool *pool)
 164 {
 165         int                     top,
 166                                 mid,
 167                                 bot;
 168         int                     i,
 169                                 index;
 170         Chromosome      swap_chromo,
 171                                 tmp_chromo;
 172
 173         /* new chromo is so bad we can't use it */
 174         if (chromo->worth > pool->data[pool->size - 1].worth)
 175                 return;
 176
 177         /* do a binary search to find the index of the new chromo */
 178
 179         top = 0;
 180         mid = pool->size / 2;
 181         bot = pool->size - 1;
 182         index = -1;
 183
 184         while (index == -1)
 185         {
 186                 /* these 4 cases find a new location */
 187
 188                 if (chromo->worth <= pool->data[top].worth)
 189                         index = top;
 190                 else if (chromo->worth == pool->data[mid].worth)
 191                         index = mid;
 192                 else if (chromo->worth == pool->data[bot].worth)
 193                         index = bot;
 194                 else if (bot - top <= 1)
 195                         index = bot;
 196
 197
 198                 /*
 199                  * these 2 cases move the search indices since a new location has not
 200                  * yet been found.
 201                  */
 202
 203                 else if (chromo->worth < pool->data[mid].worth)
 204                 {
 205                         bot = mid;
 206                         mid = top + ((bot - top) / 2);
 207                 }
 208                 else
 209                 {                                               /* (chromo->worth > pool->data[mid].worth) */
 210                         top = mid;
 211                         mid = top + ((bot - top) / 2);
 212                 }
 213         }                                                       /* ... while */
 214
 215         /* now we have index for chromo */
 216
 217         /*
 218          * move every gene from index on down one position to make room for chromo
 219          */
 220
 221         /*
 222          * copy new gene into pool storage; always replace worst gene in pool
 223          */
 224
 225         geqo_copy(root, &pool->data[pool->size - 1], chromo, pool->string_length);
 226
 227         swap_chromo.string = pool->data[pool->size - 1].string;
 228         swap_chromo.worth = pool->data[pool->size - 1].worth;
 229
 230         for (i = index; i < pool->size; i++)
 231         {
 232                 tmp_chromo.string = pool->data[i].string;
 233                 tmp_chromo.worth = pool->data[i].worth;
 234
 235                 pool->data[i].string = swap_chromo.string;
 236                 pool->data[i].worth = swap_chromo.worth;
 237
 238                 swap_chromo.string = tmp_chromo.string;
 239                 swap_chromo.worth = tmp_chromo.worth;
 240         }
 241 }