← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/backend/optimizer/geqo/geqo_cx.c

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/geqo/geqo_cx.c
 
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
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_cx.c,v 1.10 2003-11-29 22:39:49 pgsql Exp $
 
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_recombination.h"
 
39
#include "optimizer/geqo_random.h"
 
40
 
 
41
 
 
42
/* cx
 
43
 *
 
44
 *       cycle crossover
 
45
 */
 
46
int
 
47
cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
 
48
{
 
49
 
 
50
        int                     i,
 
51
                                start_pos,
 
52
                                curr_pos;
 
53
        int                     count = 0;
 
54
        int                     num_diffs = 0;
 
55
 
 
56
        /* initialize city table */
 
57
        for (i = 1; i <= num_gene; i++)
 
58
        {
 
59
                city_table[i].used = 0;
 
60
                city_table[tour2[i - 1]].tour2_position = i - 1;
 
61
                city_table[tour1[i - 1]].tour1_position = i - 1;
 
62
        }
 
63
 
 
64
        /* choose random cycle starting position */
 
65
        start_pos = geqo_randint(num_gene - 1, 0);
 
66
 
 
67
        /* child inherits first city  */
 
68
        offspring[start_pos] = tour1[start_pos];
 
69
 
 
70
        /* begin cycle with tour1 */
 
71
        curr_pos = start_pos;
 
72
        city_table[(int) tour1[start_pos]].used = 1;
 
73
 
 
74
        count++;
 
75
 
 
76
        /* cx main part */
 
77
 
 
78
 
 
79
/* STEP 1 */
 
80
 
 
81
        while (tour2[curr_pos] != tour1[start_pos])
 
82
        {
 
83
                city_table[(int) tour2[curr_pos]].used = 1;
 
84
                curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
 
85
                offspring[curr_pos] = tour1[curr_pos];
 
86
                count++;
 
87
        }
 
88
 
 
89
 
 
90
/* STEP 2 */
 
91
 
 
92
        /* failed to create a complete tour */
 
93
        if (count < num_gene)
 
94
        {
 
95
                for (i = 1; i <= num_gene; i++)
 
96
                {
 
97
                        if (!city_table[i].used)
 
98
                        {
 
99
                                offspring[city_table[i].tour2_position] =
 
100
                                        tour2[(int) city_table[i].tour2_position];
 
101
                                count++;
 
102
                        }
 
103
                }
 
104
        }
 
105
 
 
106
 
 
107
/* STEP 3 */
 
108
 
 
109
        /* still failed to create a complete tour */
 
110
        if (count < num_gene)
 
111
        {
 
112
 
 
113
                /* count the number of differences between mom and offspring */
 
114
                for (i = 0; i < num_gene; i++)
 
115
                        if (tour1[i] != offspring[i])
 
116
                                num_diffs++;
 
117
 
 
118
        }
 
119
 
 
120
        return num_diffs;
 
121
}