Debian Codegraph @

src/backend/optimizer/geqo/geqo_pmx.c

raw
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 * src/backend/optimizer/geqo/geqo_pmx.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 /* 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.h"
38
39 #if defined(PMX)
40
41 #include "optimizer/geqo_random.h"
42 #include "optimizer/geqo_recombination.h"
43
44 /* pmx
45 *
46 * partially matched crossover
47 */
48 void
49 pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
50 {
51 int *failed = (int *) palloc((num_gene + 1) * sizeof(int));
52 int *from = (int *) palloc((num_gene + 1) * sizeof(int));
53 int *indx = (int *) palloc((num_gene + 1) * sizeof(int));
54 int *check_list = (int *) palloc((num_gene + 1) * sizeof(int));
55
56 int left,
57 right,
58 temp,
59 i,
60 j,
61 k;
62 int mx_fail,
63 found,
64 mx_hold;
65
66
67 /* no mutation so start up the pmx replacement algorithm */
68 /* initialize failed[], from[], check_list[] */
69 for (k = 0; k < num_gene; k++)
70 {
71 failed[k] = -1;
72 from[k] = -1;
73 check_list[k + 1] = 0;
74 }
75
76 /* locate crossover points */
77 left = geqo_randint(root, num_gene - 1, 0);
78 right = geqo_randint(root, num_gene - 1, 0);
79
80 if (left > right)
81 {
82 temp = left;
83 left = right;
84 right = temp;
85 }
86
87
88 /* copy tour2 into offspring */
89 for (k = 0; k < num_gene; k++)
90 {
91 offspring[k] = tour2[k];
92 from[k] = DAD;
93 check_list[tour2[k]]++;
94 }
95
96 /* copy tour1 into offspring */
97 for (k = left; k <= right; k++)
98 {
99 check_list[offspring[k]]--;
100 offspring[k] = tour1[k];
101 from[k] = MOM;
102 check_list[tour1[k]]++;
103 }
104
105
106 /* pmx main part */
107
108 mx_fail = 0;
109
110 /* STEP 1 */
111
112 for (k = left; k <= right; k++)
113 { /* for all elements in the tour1-2 */
114
115 if (tour1[k] == tour2[k])
116 found = 1; /* find match in tour2 */
117
118 else
119 {
120 found = 0; /* substitute elements */
121
122 j = 0;
123 while (!(found) && (j < num_gene))
124 {
125 if ((offspring[j] == tour1[k]) && (from[j] == DAD))
126 {
127
128 check_list[offspring[j]]--;
129 offspring[j] = tour2[k];
130 found = 1;
131 check_list[tour2[k]]++;
132 }
133
134 j++;
135 }
136 }
137
138 if (!(found))
139 { /* failed to replace gene */
140 failed[mx_fail] = (int) tour1[k];
141 indx[mx_fail] = k;
142 mx_fail++;
143 }
144 } /* ... for */
145
146
147 /* STEP 2 */
148
149 /* see if any genes could not be replaced */
150 if (mx_fail > 0)
151 {
152 mx_hold = mx_fail;
153
154 for (k = 0; k < mx_hold; k++)
155 {
156 found = 0;
157
158 j = 0;
159 while (!(found) && (j < num_gene))
160 {
161
162 if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
163 {
164 check_list[offspring[j]]--;
165 offspring[j] = tour2[indx[k]];
166 check_list[tour2[indx[k]]]++;
167
168 found = 1;
169 failed[k] = -1;
170 mx_fail--;
171 }
172
173 j++;
174 }
175 } /* ... for */
176 } /* ... if */
177
178
179 /* STEP 3 */
180
181 for (k = 1; k <= num_gene; k++)
182 {
183
184 if (check_list[k] > 1)
185 {
186 i = 0;
187
188 while (i < num_gene)
189 {
190 if ((offspring[i] == (Gene) k) && (from[i] == DAD))
191 {
192 j = 1;
193
194 while (j <= num_gene)
195 {
196 if (check_list[j] == 0)
197 {
198 offspring[i] = (Gene) j;
199 check_list[k]--;
200 check_list[j]++;
201 i = num_gene + 1;
202 j = i;
203 }
204
205 j++;
206 }
207 } /* ... if */
208
209 i++;
210 } /* end while */
211 }
212 } /* ... for */
213
214 pfree(failed);
215 pfree(from);
216 pfree(indx);
217 pfree(check_list);
218 }
219
220 #endif /* defined(PMX) */