granicus.if.org Git - postgresql/blob - src/backend/optimizer/geqo/geqo_ox2.c

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