src/include/optimizer/geqo_recombination.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * geqo_recombination.h
   4  *        prototypes for recombination in the genetic query optimizer
   5  *
   6  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * $PostgreSQL$
  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 /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
  23
  24 #ifndef GEQO_RECOMBINATION_H
  25 #define GEQO_RECOMBINATION_H
  26
  27 #include "optimizer/geqo_gene.h"
  28
  29 extern void init_tour(Gene *tour, int num_gene);
  30
  31
  32 /* edge recombination crossover [ERX] */
  33
  34 typedef struct Edge
  35 {
  36         Gene            edge_list[4];   /* list of edges */
  37         int                     total_edges;
  38         int                     unused_edges;
  39 } Edge;
  40
  41 extern Edge *alloc_edge_table(int num_gene);
  42 extern void free_edge_table(Edge *edge_table);
  43
  44 extern float gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table);
  45
  46 extern int      gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene);
  47
  48
  49 /* partially matched crossover [PMX] */
  50
  51 #define DAD 1                                   /* indicator for gene from dad */
  52 #define MOM 0                                   /* indicator for gene from mom */
  53
  54 extern void pmx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene);
  55
  56
  57 typedef struct City
  58 {
  59         int                     tour2_position;
  60         int                     tour1_position;
  61         int                     used;
  62         int                     select_list;
  63 } City;
  64
  65 extern City *alloc_city_table(int num_gene);
  66 extern void free_city_table(City *city_table);
  67
  68 /* cycle crossover [CX] */
  69 extern int      cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table);
  70
  71 /* position crossover [PX] */
  72 extern void px(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table);
  73
  74 /* order crossover [OX1] according to Davis */
  75 extern void ox1(Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table);
  76
  77 /* order crossover [OX2] according to Syswerda */
  78 extern void ox2(Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table);
  79
  80 #endif   /* GEQO_RECOMBINATION_H */