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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * geqo_selection.c--
   4  *        linear selection scheme for the genetic query optimizer
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  * $Id: geqo_selection.c,v 1.6 1999/02/03 21:16:23 momjian Exp $
   9  *
  10  *-------------------------------------------------------------------------
  11  */
  12
  13 /* contributed by:
  14    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  15    *  Martin Utesch                              * Institute of Automatic Control          *
  16    =                                                     = University of Mining and Technology =
  17    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                               *
  18    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  19  */
  20
  21 /* this is adopted from D. Whitley's Genitor algorithm */
  22
  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 <math.h>
  37
  38 #include "postgres.h"
  39
  40 #include "nodes/pg_list.h"
  41 #include "nodes/relation.h"
  42 #include "nodes/primnodes.h"
  43
  44 #include "utils/palloc.h"
  45 #include "utils/elog.h"
  46
  47 #include "optimizer/internal.h"
  48 #include "optimizer/paths.h"
  49 #include "optimizer/pathnode.h"
  50 #include "optimizer/clauses.h"
  51 #include "optimizer/cost.h"
  52
  53 #include "optimizer/geqo_gene.h"
  54 #include "optimizer/geqo_selection.h"
  55 #include "optimizer/geqo_copy.h"
  56 #include "optimizer/geqo_random.h"
  57
  58 static int      linear(int max, double bias);
  59
  60 /* geqo_selection--
  61  *
  62  *       according to bias described by input parameters,
  63  *       second genes are selected from the pool
  64  */
  65 void
  66 geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
  67 {
  68         int                     first,
  69                                 second;
  70
  71         first = (int) linear(pool->size, bias);
  72         second = (int) linear(pool->size, bias);
  73
  74         if (pool->size > 1)
  75         {
  76                 while (first == second)
  77                         second = (int) linear(pool->size, bias);
  78         }
  79
  80         geqo_copy(momma, &pool->data[first], pool->string_length);
  81         geqo_copy(daddy, &pool->data[second], pool->string_length);
  82 }
  83
  84 /* linear--
  85  *        generates random integer between 0 and input max number
  86  *        using input linear bias
  87  *
  88  *        probability distribution function is: f(x) = bias - 2(bias - 1)x
  89  *                       bias = (prob of first rule) / (prob of middle rule)
  90  *
  91  */
  92
  93 static int
  94 linear(int pool_size, double bias)              /* bias is y-intercept of linear
  95                                                                                  * distribution */
  96 {
  97         double          index;                  /* index between 0 and pop_size */
  98         double          max = (double) pool_size;
  99
 100         index = max * (bias - sqrt((bias * bias) - 4.0 * (bias - 1.0) * geqo_rand()))
 101                 / 2.0 / (bias - 1.0);
 102
 103         return (int) index;
 104 }