granicus.if.org Git - postgresql/blob - 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 * $Id: geqo_cx.c,v 1.9 1999/07/16 04:59:07 momjian 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 }