PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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_random.h"
39 
40 #if defined(OX2)
41 
42 /* ox2
43  *
44  * position crossover
45  */
46 void
47 ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
48 {
49  int k,
50  j,
51  count,
52  pos,
53  select,
54  num_positions;
55 
56  /* initialize city table */
57  for (k = 1; k <= num_gene; k++)
58  {
59  city_table[k].used = 0;
60  city_table[k - 1].select_list = -1;
61  }
62 
63  /* determine the number of positions to be inherited from tour1 */
64  num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
65 
66  /* make a list of selected cities */
67  for (k = 0; k < num_positions; k++)
68  {
69  pos = geqo_randint(root, num_gene - 1, 0);
70  city_table[pos].select_list = (int) tour1[pos];
71  city_table[(int) tour1[pos]].used = 1; /* mark used */
72  }
73 
74 
75  count = 0;
76  k = 0;
77 
78  /* consolidate the select list to adjacent positions */
79  while (count < num_positions)
80  {
81  if (city_table[k].select_list == -1)
82  {
83  j = k + 1;
84  while ((city_table[j].select_list == -1) && (j < num_gene))
85  j++;
86 
87  city_table[k].select_list = city_table[j].select_list;
88  city_table[j].select_list = -1;
89  count++;
90  }
91  else
92  count++;
93  k++;
94  }
95 
96  select = 0;
97 
98  for (k = 0; k < num_gene; k++)
99  {
100  if (city_table[(int) tour2[k]].used)
101  {
102  offspring[k] = (Gene) city_table[select].select_list;
103  select++; /* next city in the select list */
104  }
105  else
106  /* city isn't used yet, so inherit from tour2 */
107  offspring[k] = tour2[k];
108  }
109 
110 }
111 
112 #endif /* defined(OX2) */
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
int select_list
#define select(n, r, w, e, timeout)
Definition: win32.h:374
void ox2(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)