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 =
default_boost::parameter::aux::default_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"
38 #include "optimizer/geqo_recombination.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) */
225