PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
geqo_pmx.c
Go to the documentation of this file.
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.h"
38
39#if defined(PMX)
40
43
44/* pmx
45 *
46 * partially matched crossover
47 */
48void
49pmx(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) */
int Gene
Definition: geqo_gene.h:30
int geqo_randint(PlannerInfo *root, int upper, int lower)
Definition: geqo_random.c:36
void pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
#define DAD
#define MOM
int j
Definition: isn.c:73
int i
Definition: isn.c:72
void pfree(void *pointer)
Definition: mcxt.c:1521
void * palloc(Size size)
Definition: mcxt.c:1317
tree ctl root
Definition: radixtree.h:1857