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 * utesch@aut.tu-freiberg.de * 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_random.h"
38#include "optimizer/geqo_recombination.h"
39
40#if defined(OX2)
41
42/* ox2
43 *
44 * position crossover
45 */
46void
47ox2(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City * city_table)
48{
49 int k,
50 j,
51 count,
52 pos,
53 select,
54 num_positions;
55
56 /* initialize city table */
57 for (k = 1; k <= num_gene; k++)
58 {
59 city_table[k].used = 0;
60 city_table[k - 1].select_list = -1;
61 }
62
63 /* determine the number of positions to be inherited from tour1 */
64 num_positions = geqo_randint(root, 2 * num_gene / 3, num_gene / 3);
65
66 /* make a list of selected cities */
67 for (k = 0; k < num_positions; k++)
68 {
69 pos = geqo_randint(root, num_gene - 1, 0);
70 city_table[pos].select_list = (int) tour1[pos];
71 city_table[(int) tour1[pos]].used = 1; /* mark used */
72 }
73
74
75 count = 0;
76 k = 0;
77
78 /* consolidate the select list to adjacent positions */
79 while (count < num_positions)
80 {
81 if (city_table[k].select_list == -1)
82 {
83 j = k + 1;
84 while ((city_table[j].select_list == -1) && (j < num_gene))
85 j++;
86
87 city_table[k].select_list = city_table[j].select_list;
88 city_table[j].select_list = -1;
89 count++;
90 }
91 else
92 count++;
93 k++;
94 }
95
96 select = 0;
97
98 for (k = 0; k < num_gene; k++)
99 {
100 if (city_table[(int) tour2[k]].used)
101 {
102 offspring[k] = (Gene) city_table[select].select_list;
103 select++; /* next city in the select list */
104 }
105 else
106 /* city isn't used yet, so inherit from tour2 */
107 offspring[k] = tour2[k];
108 }
109
110}
111
112#endif /* defined(OX2) */
113