PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_px.c
Go to the documentation of this file.
1 /*------------------------------------------------------------------------
2 *
3 * geqo_px.c
4 *
5 * position crossover [PX] routines;
6 * PX operator according to Syswerda
7 * (The Genetic Algorithms Handbook, L Davis, ed)
8 *
9 * src/backend/optimizer/geqo/geqo_px.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 px 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(PX)
41 
42 /* px
43  *
44  * position crossover
45  */
46 void
47 px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
48  City *city_table)
49 {
50  int num_positions;
51  int i,
52  pos,
53  tour2_index,
54  offspring_index;
55 
56  /* initialize city table */
57  for (i = 1; i <= num_gene; i++)
58  city_table[i].used = 0;
59 
60  /* choose random positions that will be inherited directly from parent */
61  num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
62 
63  /* choose random position */
64  for (i = 0; i < num_positions; i++)
65  {
66  pos = geqo_randint(root, num_gene - 1, 0);
67 
68  offspring[pos] = tour1[pos]; /* transfer cities to child */
69  city_table[(int) tour1[pos]].used = 1; /* mark city used */
70  }
71 
72  tour2_index = 0;
73  offspring_index = 0;
74 
75 
76  /* px main part */
77 
78  while (offspring_index < num_gene)
79  {
80 
81  /* next position in offspring filled */
82  if (!city_table[(int) tour1[offspring_index]].used)
83  {
84 
85  /* next city in tour1 not used */
86  if (!city_table[(int) tour2[tour2_index]].used)
87  {
88 
89  /* inherit from tour1 */
90  offspring[offspring_index] = tour2[tour2_index];
91 
92  tour2_index++;
93  offspring_index++;
94  }
95  else
96  { /* next city in tour2 has been used */
97  tour2_index++;
98  }
99 
100  }
101  else
102  { /* next position in offspring is filled */
103  offspring_index++;
104  }
105 
106  }
107 
108 }
109 
110 #endif /* defined(PX) */
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
void px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
int i