1 /*------------------------------------------------------------------------
2 *
3 * geqo_cx.c
4 *
5 * cycle crossover [CX] routines;
6 * CX operator according to Oliver et al
7 * (Proc 2nd Int'l Conf on GA's)
8 *
9 * src/backend/optimizer/geqo/geqo_cx.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 cx 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
37 #include "postgres.h"
38 #include "optimizer/geqo_random.h"
39 #include "optimizer/geqo_recombination.h"
40
41 #if defined(CX)
42
43 /* cx
44 *
45 * cycle crossover
46 */
47 int
cx(PlannerInfo * root,Gene * tour1,Gene * tour2,Gene * offspring,int num_gene,City * city_table)48 cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
49 int num_gene, City * city_table)
50 {
51 int i,
52 start_pos,
53 curr_pos;
54 int count = 0;
55 int num_diffs = 0;
56
57 /* initialize city table */
58 for (i = 1; i <= num_gene; i++)
59 {
60 city_table[i].used = 0;
61 city_table[tour2[i - 1]].tour2_position = i - 1;
62 city_table[tour1[i - 1]].tour1_position = i - 1;
63 }
64
65 /* choose random cycle starting position */
66 start_pos = geqo_randint(root, num_gene - 1, 0);
67
68 /* child inherits first city */
69 offspring[start_pos] = tour1[start_pos];
70
71 /* begin cycle with tour1 */
72 curr_pos = start_pos;
73 city_table[(int) tour1[start_pos]].used = 1;
74
75 count++;
76
77 /* cx main part */
78
79
80 /* STEP 1 */
81
82 while (tour2[curr_pos] != tour1[start_pos])
83 {
84 city_table[(int) tour2[curr_pos]].used = 1;
85 curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
86 offspring[curr_pos] = tour1[curr_pos];
87 count++;
88 }
89
90
91 /* STEP 2 */
92
93 /* failed to create a complete tour */
94 if (count < num_gene)
95 {
96 for (i = 1; i <= num_gene; i++)
97 {
98 if (!city_table[i].used)
99 {
100 offspring[city_table[i].tour2_position] =
101 tour2[(int) city_table[i].tour2_position];
102 count++;
103 }
104 }
105 }
106
107
108 /* STEP 3 */
109
110 /* still failed to create a complete tour */
111 if (count < num_gene)
112 {
113
114 /* count the number of differences between mom and offspring */
115 for (i = 0; i < num_gene; i++)
116 if (tour1[i] != offspring[i])
117 num_diffs++;
118
119 }
120
121 return num_diffs;
122 }
123
124 #endif /* defined(CX) */
125