PostgreSQL Source Code  git master
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 
41 #include "optimizer/geqo_random.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) */
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:74
int i
Definition: isn.c:73
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc(Size size)
Definition: mcxt.c:1304