← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/backend/optimizer/geqo/geqo_pool.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
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-2011, 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
}