blob: 14c63551afb68b0e92b0aad1658e2772dd36cd8e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
/*------------------------------------------------------------------------
*
* geqo_ox1.c
*
* order crossover [OX] routines;
* OX1 operator according to Davis
* (Proc Int'l Joint Conf on AI)
*
* $Id: geqo_ox1.c,v 1.8 1999/07/16 04:59:10 momjian Exp $
*
*-------------------------------------------------------------------------
*/
/* contributed by:
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
* Martin Utesch * Institute of Automatic Control *
= = University of Mining and Technology =
* utesch@aut.tu-freiberg.de * Freiberg, Germany *
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
*/
/* the ox algorithm is adopted from Genitor : */
/*************************************************************/
/* */
/* Copyright (c) 1990 */
/* Darrell L. Whitley */
/* Computer Science Department */
/* Colorado State University */
/* */
/* Permission is hereby granted to copy all or any part of */
/* this program for free distribution. The author's name */
/* and this copyright notice must be included in any copy. */
/* */
/*************************************************************/
#include "postgres.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"
/* ox1
*
* position crossover
*/
void
ox1(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
{
int left,
right,
k,
p,
temp;
/* initialize city table */
for (k = 1; k <= num_gene; k++)
city_table[k].used = 0;
/* select portion to copy from tour1 */
left = geqo_randint(num_gene - 1, 0);
right = geqo_randint(num_gene - 1, 0);
if (left > right)
{
temp = left;
left = right;
right = temp;
}
/* copy portion from tour1 to offspring */
for (k = left; k <= right; k++)
{
offspring[k] = tour1[k];
city_table[(int) tour1[k]].used = 1;
}
k = (right + 1) % num_gene; /* index into offspring */
p = k; /* index into tour2 */
/* copy stuff from tour2 to offspring */
while (k != left)
{
if (!city_table[(int) tour2[p]].used)
{
offspring[k] = tour2[p];
k = (k + 1) % num_gene;
city_table[(int) tour2[p]].used = 1;
}
p = (p + 1) % num_gene; /* increment tour2-index */
}
}
|
