PostgreSQL Source Code  git master
geqo_cx.c
Go to the documentation of this file.
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.h"
39 
40 #if defined(CX)
41 
42 #include "optimizer/geqo_random.h"
44 
45 /* cx
46  *
47  * cycle crossover
48  */
49 int
50 cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
51  int num_gene, City * city_table)
52 {
53  int i,
54  start_pos,
55  curr_pos;
56  int count = 0;
57  int num_diffs = 0;
58 
59  /* initialize city table */
60  for (i = 1; i <= num_gene; i++)
61  {
62  city_table[i].used = 0;
63  city_table[tour2[i - 1]].tour2_position = i - 1;
64  city_table[tour1[i - 1]].tour1_position = i - 1;
65  }
66 
67  /* choose random cycle starting position */
68  start_pos = geqo_randint(root, num_gene - 1, 0);
69 
70  /* child inherits first city */
71  offspring[start_pos] = tour1[start_pos];
72 
73  /* begin cycle with tour1 */
74  curr_pos = start_pos;
75  city_table[(int) tour1[start_pos]].used = 1;
76 
77  count++;
78 
79  /* cx main part */
80 
81 
82 /* STEP 1 */
83 
84  while (tour2[curr_pos] != tour1[start_pos])
85  {
86  city_table[(int) tour2[curr_pos]].used = 1;
87  curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
88  offspring[curr_pos] = tour1[curr_pos];
89  count++;
90  }
91 
92 
93 /* STEP 2 */
94 
95  /* failed to create a complete tour */
96  if (count < num_gene)
97  {
98  for (i = 1; i <= num_gene; i++)
99  {
100  if (!city_table[i].used)
101  {
102  offspring[city_table[i].tour2_position] =
103  tour2[(int) city_table[i].tour2_position];
104  count++;
105  }
106  }
107  }
108 
109 
110 /* STEP 3 */
111 
112  /* still failed to create a complete tour */
113  if (count < num_gene)
114  {
115 
116  /* count the number of differences between mom and offspring */
117  for (i = 0; i < num_gene; i++)
118  if (tour1[i] != offspring[i])
119  num_diffs++;
120  }
121 
122  return num_diffs;
123 }
124 
125 #endif /* defined(CX) */
int Gene
Definition: geqo_gene.h:30
int geqo_randint(PlannerInfo *root, int upper, int lower)
Definition: geqo_random.c:36
int cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
int i
Definition: isn.c:73
tree ctl root
Definition: radixtree.h:1880
int tour2_position
int tour1_position