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  * Portions Copyright (c) 1996-2004, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_selection.c,v 1.17 2004/08/29 04:12:33 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 /* this is adopted from D. Whitley's Genitor algorithm */
  23
  24 /*************************************************************/
  25 /*                                                                                                                       */
  26 /*      Copyright (c) 1990                                                                               */
  27 /*      Darrell L. Whitley                                                                               */
  28 /*      Computer Science Department                                                              */
  29 /*      Colorado State University                                                                */
  30 /*                                                                                                                       */
  31 /*      Permission is hereby granted to copy all or any part of  */
  32 /*      this program for free distribution.   The author's name  */
  33 /*      and this copyright notice must be included in any copy.  */
  34 /*                                                                                                                       */
  35 /*************************************************************/
  36
  37 #include "postgres.h"
  38
  39 #include <math.h>
  40
  41 #include "optimizer/geqo_copy.h"
  42 #include "optimizer/geqo_random.h"
  43 #include "optimizer/geqo_selection.h"
  44
  45 static int      linear(int max, double bias);
  46
  47 /* geqo_selection
  48  *
  49  *       according to bias described by input parameters,
  50  *       second genes are selected from the pool
  51  */
  52 void
  53 geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
  54 {
  55         int                     first,
  56                                 second;
  57
  58         first = (int) linear(pool->size, bias);
  59         second = (int) linear(pool->size, bias);
  60
  61         if (pool->size > 1)
  62         {
  63                 while (first == second)
  64                         second = (int) linear(pool->size, bias);
  65         }
  66
  67         geqo_copy(momma, &pool->data[first], pool->string_length);
  68         geqo_copy(daddy, &pool->data[second], pool->string_length);
  69 }
  70
  71 /* linear
  72  *        generates random integer between 0 and input max number
  73  *        using input linear bias
  74  *
  75  *        probability distribution function is: f(x) = bias - 2(bias - 1)x
  76  *                       bias = (prob of first rule) / (prob of middle rule)
  77  *
  78  */
  79
  80 static int
  81 linear(int pool_size, double bias)              /* bias is y-intercept of linear
  82                                                                                  * distribution */
  83 {
  84         double          index;                  /* index between 0 and pop_size */
  85         double          max = (double) pool_size;
  86
  87         index = max * (bias - sqrt((bias * bias) - 4.0 * (bias - 1.0) * geqo_rand()))
  88                 / 2.0 / (bias - 1.0);
  89
  90         return (int) index;
  91 }