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 */
46void
47px(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