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