Debian Codegraph @

src/backend/optimizer/geqo/geqo_px.c

raw
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 * [email protected] * 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.h"
38
39 #if defined(PX)
40
41 #include "optimizer/geqo_random.h"
42 #include "optimizer/geqo_recombination.h"
43
44 /* px
45 *
46 * position crossover
47 */
48 void
49 px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene,
50 City * city_table)
51 {
52 int num_positions;
53 int i,
54 pos,
55 tour2_index,
56 offspring_index;
57
58 /* initialize city table */
59 for (i = 1; i <= num_gene; i++)
60 city_table[i].used = 0;
61
62 /* choose random positions that will be inherited directly from parent */
63 num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
64
65 /* choose random position */
66 for (i = 0; i < num_positions; i++)
67 {
68 pos = geqo_randint(root, num_gene - 1, 0);
69
70 offspring[pos] = tour1[pos]; /* transfer cities to child */
71 city_table[(int) tour1[pos]].used = 1; /* mark city used */
72 }
73
74 tour2_index = 0;
75 offspring_index = 0;
76
77
78 /* px main part */
79
80 while (offspring_index < num_gene)
81 {
82
83 /* next position in offspring filled */
84 if (!city_table[(int) tour1[offspring_index]].used)
85 {
86
87 /* next city in tour1 not used */
88 if (!city_table[(int) tour2[tour2_index]].used)
89 {
90
91 /* inherit from tour1 */
92 offspring[offspring_index] = tour2[tour2_index];
93
94 tour2_index++;
95 offspring_index++;
96 }
97 else
98 { /* next city in tour2 has been used */
99 tour2_index++;
100 }
101 }
102 else
103 { /* next position in offspring is filled */
104 offspring_index++;
105 }
106 }
107 }
108
109 #endif /* defined(PX) */