← Back to branch summary

~ubuntu-branches/ubuntu/lucid/postgresql-8.4/lucid-proposed

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/geqo/geqo_pmx.c
 
1
/*------------------------------------------------------------------------
 
2
*
 
3
* geqo_pmx.c
 
4
*
 
5
*        partially matched crossover [PMX] routines;
 
6
*        PMX operator according to Goldberg & Lingle
 
7
*        (Proc Int'l Conf on GA's)
 
8
*
 
9
* $PostgreSQL$
 
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
/* the pmx algorithm is adopted from Genitor : */
 
23
/*************************************************************/
 
24
/*                                                                                                                       */
 
25
/*      Copyright (c) 1990                                                                               */
 
26
/*      Darrell L. Whitley                                                                               */
 
27
/*      Computer Science Department                                                              */
 
28
/*      Colorado State University                                                                */
 
29
/*                                                                                                                       */
 
30
/*      Permission is hereby granted to copy all or any part of  */
 
31
/*      this program for free distribution.   The author's name  */
 
32
/*      and this copyright notice must be included in any copy.  */
 
33
/*                                                                                                                       */
 
34
/*************************************************************/
 
35
 
 
36
#include "postgres.h"
 
37
#include "optimizer/geqo_random.h"
 
38
#include "optimizer/geqo_recombination.h"
 
39
 
 
40
 
 
41
/* pmx
 
42
 *
 
43
 *       partially matched crossover
 
44
 */
 
45
void
 
46
pmx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
 
47
{
 
48
        int                *failed = (int *) palloc((num_gene + 1) * sizeof(int));
 
49
        int                *from = (int *) palloc((num_gene + 1) * sizeof(int));
 
50
        int                *indx = (int *) palloc((num_gene + 1) * sizeof(int));
 
51
        int                *check_list = (int *) palloc((num_gene + 1) * sizeof(int));
 
52
 
 
53
        int                     left,
 
54
                                right,
 
55
                                temp,
 
56
                                i,
 
57
                                j,
 
58
                                k;
 
59
        int                     mx_fail,
 
60
                                found,
 
61
                                mx_hold;
 
62
 
 
63
 
 
64
/* no mutation so start up the pmx replacement algorithm */
 
65
/* initialize failed[], from[], check_list[] */
 
66
        for (k = 0; k < num_gene; k++)
 
67
        {
 
68
                failed[k] = -1;
 
69
                from[k] = -1;
 
70
                check_list[k + 1] = 0;
 
71
        }
 
72
 
 
73
/* locate crossover points */
 
74
        left = geqo_randint(num_gene - 1, 0);
 
75
        right = geqo_randint(num_gene - 1, 0);
 
76
 
 
77
        if (left > right)
 
78
        {
 
79
                temp = left;
 
80
                left = right;
 
81
                right = temp;
 
82
        }
 
83
 
 
84
 
 
85
/* copy tour2 into offspring */
 
86
        for (k = 0; k < num_gene; k++)
 
87
        {
 
88
                offspring[k] = tour2[k];
 
89
                from[k] = DAD;
 
90
                check_list[tour2[k]]++;
 
91
        }
 
92
 
 
93
/* copy tour1 into offspring */
 
94
        for (k = left; k <= right; k++)
 
95
        {
 
96
                check_list[offspring[k]]--;
 
97
                offspring[k] = tour1[k];
 
98
                from[k] = MOM;
 
99
                check_list[tour1[k]]++;
 
100
        }
 
101
 
 
102
 
 
103
/* pmx main part */
 
104
 
 
105
        mx_fail = 0;
 
106
 
 
107
/* STEP 1 */
 
108
 
 
109
        for (k = left; k <= right; k++)
 
110
        {                                                       /* for all elements in the tour1-2 */
 
111
 
 
112
                if (tour1[k] == tour2[k])
 
113
                        found = 1;                      /* find match in tour2 */
 
114
 
 
115
                else
 
116
                {
 
117
                        found = 0;                      /* substitute elements */
 
118
 
 
119
                        j = 0;
 
120
                        while (!(found) && (j < num_gene))
 
121
                        {
 
122
                                if ((offspring[j] == tour1[k]) && (from[j] == DAD))
 
123
                                {
 
124
 
 
125
                                        check_list[offspring[j]]--;
 
126
                                        offspring[j] = tour2[k];
 
127
                                        found = 1;
 
128
                                        check_list[tour2[k]]++;
 
129
                                }
 
130
 
 
131
                                j++;
 
132
                        }
 
133
 
 
134
                }
 
135
 
 
136
                if (!(found))
 
137
                {                                               /* failed to replace gene */
 
138
                        failed[mx_fail] = (int) tour1[k];
 
139
                        indx[mx_fail] = k;
 
140
                        mx_fail++;
 
141
                }
 
142
 
 
143
        }                                                       /* ... for */
 
144
 
 
145
 
 
146
/* STEP 2 */
 
147
 
 
148
        /* see if any genes could not be replaced */
 
149
        if (mx_fail > 0)
 
150
        {
 
151
                mx_hold = mx_fail;
 
152
 
 
153
                for (k = 0; k < mx_hold; k++)
 
154
                {
 
155
                        found = 0;
 
156
 
 
157
                        j = 0;
 
158
                        while (!(found) && (j < num_gene))
 
159
                        {
 
160
 
 
161
                                if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
 
162
                                {
 
163
                                        check_list[offspring[j]]--;
 
164
                                        offspring[j] = tour2[indx[k]];
 
165
                                        check_list[tour2[indx[k]]]++;
 
166
 
 
167
                                        found = 1;
 
168
                                        failed[k] = -1;
 
169
                                        mx_fail--;
 
170
                                }
 
171
 
 
172
                                j++;
 
173
                        }
 
174
 
 
175
                }                                               /* ... for       */
 
176
 
 
177
        }                                                       /* ... if        */
 
178
 
 
179
 
 
180
/* STEP 3 */
 
181
 
 
182
        for (k = 1; k <= num_gene; k++)
 
183
        {
 
184
 
 
185
                if (check_list[k] > 1)
 
186
                {
 
187
                        i = 0;
 
188
 
 
189
                        while (i < num_gene)
 
190
                        {
 
191
                                if ((offspring[i] == (Gene) k) && (from[i] == DAD))
 
192
                                {
 
193
                                        j = 1;
 
194
 
 
195
                                        while (j <= num_gene)
 
196
                                        {
 
197
                                                if (check_list[j] == 0)
 
198
                                                {
 
199
                                                        offspring[i] = (Gene) j;
 
200
                                                        check_list[k]--;
 
201
                                                        check_list[j]++;
 
202
                                                        i = num_gene + 1;
 
203
                                                        j = i;
 
204
                                                }
 
205
 
 
206
                                                j++;
 
207
                                        }
 
208
 
 
209
                                }                               /* ... if        */
 
210
 
 
211
                                i++;
 
212
                        }                                       /* end while */
 
213
 
 
214
                }
 
215
        }                                                       /* ... for       */
 
216
 
 
217
        pfree(failed);
 
218
        pfree(from);
 
219
        pfree(indx);
 
220
        pfree(check_list);
 
221
}