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"
38 #include "optimizer/geqo_recombination.h"
39
40 #if defined(PX)
41
42 /* px
43 *
44 * position crossover
45 */
46 void
px(PlannerInfo * root,Gene * tour1,Gene * tour2,Gene * offspring,int num_gene,City * city_table)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) */
111