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_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  if (!(found))
137  { /* failed to replace gene */
138  failed[mx_fail] = (int) tour1[k];
139  indx[mx_fail] = k;
140  mx_fail++;
141  }
142  } /* ... for */
143 
144 
145 /* STEP 2 */
146 
147  /* see if any genes could not be replaced */
148  if (mx_fail > 0)
149  {
150  mx_hold = mx_fail;
151 
152  for (k = 0; k < mx_hold; k++)
153  {
154  found = 0;
155 
156  j = 0;
157  while (!(found) && (j < num_gene))
158  {
159 
160  if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
161  {
162  check_list[offspring[j]]--;
163  offspring[j] = tour2[indx[k]];
164  check_list[tour2[indx[k]]]++;
165 
166  found = 1;
167  failed[k] = -1;
168  mx_fail--;
169  }
170 
171  j++;
172  }
173  } /* ... for */
174  } /* ... if */
175 
176 
177 /* STEP 3 */
178 
179  for (k = 1; k <= num_gene; k++)
180  {
181 
182  if (check_list[k] > 1)
183  {
184  i = 0;
185 
186  while (i < num_gene)
187  {
188  if ((offspring[i] == (Gene) k) && (from[i] == DAD))
189  {
190  j = 1;
191 
192  while (j <= num_gene)
193  {
194  if (check_list[j] == 0)
195  {
196  offspring[i] = (Gene) j;
197  check_list[k]--;
198  check_list[j]++;
199  i = num_gene + 1;
200  j = i;
201  }
202 
203  j++;
204  }
205  } /* ... if */
206 
207  i++;
208  } /* end while */
209  }
210  } /* ... for */
211 
212  pfree(failed);
213  pfree(from);
214  pfree(indx);
215  pfree(check_list);
216 }
217 
218 #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:1175
void * palloc(Size size)
Definition: mcxt.c:1068