PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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_random.h"
39 
40 #if defined(PMX)
41 
42 /* pmx
43  *
44  * partially matched crossover
45  */
46 void
47 pmx(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) */
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
void pfree(void *pointer)
Definition: mcxt.c:949
#define DAD
#define MOM
void * palloc(Size size)
Definition: mcxt.c:848
void pmx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
int i