PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
geqo_cx.c
Go to the documentation of this file.
1/*------------------------------------------------------------------------
2*
3* geqo_cx.c
4*
5* cycle crossover [CX] routines;
6* CX operator according to Oliver et al
7* (Proc 2nd Int'l Conf on GA's)
8*
9* src/backend/optimizer/geqo/geqo_cx.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 cx 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
37#include "postgres.h"
38#include "optimizer/geqo.h"
39
40#if defined(CX)
41
44
45/* cx
46 *
47 * cycle crossover
48 */
49int
50cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
51 int num_gene, City * city_table)
52{
53 int i,
54 start_pos,
55 curr_pos;
56 int count = 0;
57 int num_diffs = 0;
58
59 /* initialize city table */
60 for (i = 1; i <= num_gene; i++)
61 {
62 city_table[i].used = 0;
63 city_table[tour2[i - 1]].tour2_position = i - 1;
64 city_table[tour1[i - 1]].tour1_position = i - 1;
65 }
66
67 /* choose random cycle starting position */
68 start_pos = geqo_randint(root, num_gene - 1, 0);
69
70 /* child inherits first city */
71 offspring[start_pos] = tour1[start_pos];
72
73 /* begin cycle with tour1 */
74 curr_pos = start_pos;
75 city_table[(int) tour1[start_pos]].used = 1;
76
77 count++;
78
79 /* cx main part */
80
81
82/* STEP 1 */
83
84 while (tour2[curr_pos] != tour1[start_pos])
85 {
86 city_table[(int) tour2[curr_pos]].used = 1;
87 curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
88 offspring[curr_pos] = tour1[curr_pos];
89 count++;
90 }
91
92
93/* STEP 2 */
94
95 /* failed to create a complete tour */
96 if (count < num_gene)
97 {
98 for (i = 1; i <= num_gene; i++)
99 {
100 if (!city_table[i].used)
101 {
102 offspring[city_table[i].tour2_position] =
103 tour2[(int) city_table[i].tour2_position];
104 count++;
105 }
106 }
107 }
108
109
110/* STEP 3 */
111
112 /* still failed to create a complete tour */
113 if (count < num_gene)
114 {
115
116 /* count the number of differences between mom and offspring */
117 for (i = 0; i < num_gene; i++)
118 if (tour1[i] != offspring[i])
119 num_diffs++;
120 }
121
122 return num_diffs;
123}
124
125#endif /* defined(CX) */
int Gene
Definition: geqo_gene.h:30
int geqo_randint(PlannerInfo *root, int upper, int lower)
Definition: geqo_random.c:36
int cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
int i
Definition: isn.c:72
tree ctl root
Definition: radixtree.h:1857
int tour2_position
int tour1_position