PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_pmx.c File Reference
Include dependency graph for geqo_pmx.c:

Go to the source code of this file.

Functions

void pmx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
 

Function Documentation

void pmx ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene 
)

Definition at line 46 of file geqo_pmx.c.

References DAD, geqo_randint, i, MOM, palloc(), and pfree().

Referenced by geqo().

47 {
48  int *failed = (int *) palloc((num_gene + 1) * sizeof(int));
49  int *from = (int *) palloc((num_gene + 1) * sizeof(int));
50  int *indx = (int *) palloc((num_gene + 1) * sizeof(int));
51  int *check_list = (int *) palloc((num_gene + 1) * sizeof(int));
52 
53  int left,
54  right,
55  temp,
56  i,
57  j,
58  k;
59  int mx_fail,
60  found,
61  mx_hold;
62 
63 
64 /* no mutation so start up the pmx replacement algorithm */
65 /* initialize failed[], from[], check_list[] */
66  for (k = 0; k < num_gene; k++)
67  {
68  failed[k] = -1;
69  from[k] = -1;
70  check_list[k + 1] = 0;
71  }
72 
73 /* locate crossover points */
74  left = geqo_randint(root, num_gene - 1, 0);
75  right = geqo_randint(root, num_gene - 1, 0);
76 
77  if (left > right)
78  {
79  temp = left;
80  left = right;
81  right = temp;
82  }
83 
84 
85 /* copy tour2 into offspring */
86  for (k = 0; k < num_gene; k++)
87  {
88  offspring[k] = tour2[k];
89  from[k] = DAD;
90  check_list[tour2[k]]++;
91  }
92 
93 /* copy tour1 into offspring */
94  for (k = left; k <= right; k++)
95  {
96  check_list[offspring[k]]--;
97  offspring[k] = tour1[k];
98  from[k] = MOM;
99  check_list[tour1[k]]++;
100  }
101 
102 
103 /* pmx main part */
104 
105  mx_fail = 0;
106 
107 /* STEP 1 */
108 
109  for (k = left; k <= right; k++)
110  { /* for all elements in the tour1-2 */
111 
112  if (tour1[k] == tour2[k])
113  found = 1; /* find match in tour2 */
114 
115  else
116  {
117  found = 0; /* substitute elements */
118 
119  j = 0;
120  while (!(found) && (j < num_gene))
121  {
122  if ((offspring[j] == tour1[k]) && (from[j] == DAD))
123  {
124 
125  check_list[offspring[j]]--;
126  offspring[j] = tour2[k];
127  found = 1;
128  check_list[tour2[k]]++;
129  }
130 
131  j++;
132  }
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 
143  } /* ... for */
144 
145 
146 /* STEP 2 */
147 
148  /* see if any genes could not be replaced */
149  if (mx_fail > 0)
150  {
151  mx_hold = mx_fail;
152 
153  for (k = 0; k < mx_hold; k++)
154  {
155  found = 0;
156 
157  j = 0;
158  while (!(found) && (j < num_gene))
159  {
160 
161  if ((failed[k] == (int) offspring[j]) && (from[j] == DAD))
162  {
163  check_list[offspring[j]]--;
164  offspring[j] = tour2[indx[k]];
165  check_list[tour2[indx[k]]]++;
166 
167  found = 1;
168  failed[k] = -1;
169  mx_fail--;
170  }
171 
172  j++;
173  }
174 
175  } /* ... for */
176 
177  } /* ... if */
178 
179 
180 /* STEP 3 */
181 
182  for (k = 1; k <= num_gene; k++)
183  {
184 
185  if (check_list[k] > 1)
186  {
187  i = 0;
188 
189  while (i < num_gene)
190  {
191  if ((offspring[i] == (Gene) k) && (from[i] == DAD))
192  {
193  j = 1;
194 
195  while (j <= num_gene)
196  {
197  if (check_list[j] == 0)
198  {
199  offspring[i] = (Gene) j;
200  check_list[k]--;
201  check_list[j]++;
202  i = num_gene + 1;
203  j = i;
204  }
205 
206  j++;
207  }
208 
209  } /* ... if */
210 
211  i++;
212  } /* end while */
213 
214  }
215  } /* ... for */
216 
217  pfree(failed);
218  pfree(from);
219  pfree(indx);
220  pfree(check_list);
221 }
#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:950
#define DAD
#define MOM
void * palloc(Size size)
Definition: mcxt.c:849
int i