PostgreSQL Source Code  git master
geqo_ox2.c
Go to the documentation of this file.
1 /*------------------------------------------------------------------------
2 *
3 * geqo_ox2.c
4 *
5 * order crossover [OX] routines;
6 * OX2 operator according to Syswerda
7 * (The Genetic Algorithms Handbook, ed L Davis)
8 *
9 * src/backend/optimizer/geqo/geqo_ox2.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 ox 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.h"
38 
39 #if defined(OX2)
40 
41 #include "optimizer/geqo_random.h"
43 
44 /* ox2
45  *
46  * position crossover
47  */
48 void
49 ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City * city_table)
50 {
51  int k,
52  j,
53  count,
54  pos,
55  select,
56  num_positions;
57 
58  /* initialize city table */
59  for (k = 1; k <= num_gene; k++)
60  {
61  city_table[k].used = 0;
62  city_table[k - 1].select_list = -1;
63  }
64 
65  /* determine the number of positions to be inherited from tour1 */
66  num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
67 
68  /* make a list of selected cities */
69  for (k = 0; k < num_positions; k++)
70  {
71  pos = geqo_randint(root, num_gene - 1, 0);
72  city_table[pos].select_list = (int) tour1[pos];
73  city_table[(int) tour1[pos]].used = 1; /* mark used */
74  }
75 
76 
77  count = 0;
78  k = 0;
79 
80  /* consolidate the select list to adjacent positions */
81  while (count < num_positions)
82  {
83  if (city_table[k].select_list == -1)
84  {
85  j = k + 1;
86  while ((city_table[j].select_list == -1) && (j < num_gene))
87  j++;
88 
89  city_table[k].select_list = city_table[j].select_list;
90  city_table[j].select_list = -1;
91  count++;
92  }
93  else
94  count++;
95  k++;
96  }
97 
98  select = 0;
99 
100  for (k = 0; k < num_gene; k++)
101  {
102  if (city_table[(int) tour2[k]].used)
103  {
104  offspring[k] = (Gene) city_table[select].select_list;
105  select++; /* next city in the select list */
106  }
107  else
108  /* city isn't used yet, so inherit from tour2 */
109  offspring[k] = tour2[k];
110  }
111 }
112 
113 #endif /* defined(OX2) */
int Gene
Definition: geqo_gene.h:30
int geqo_randint(PlannerInfo *root, int upper, int lower)
Definition: geqo_random.c:36
void ox2(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
int j
Definition: isn.c:74
int select_list
#define select(n, r, w, e, timeout)
Definition: win32_port.h:495