Debian Codegraph @

src/backend/optimizer/geqo/geqo_ox2.c

raw
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 * [email protected] * 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"
42 #include "optimizer/geqo_recombination.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) */