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-2000, PostgreSQL, Inc
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * $Id: geqo_selection.c,v 1.11 2000/01/26 05:56: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 <math.h>
  38
  39 #include "postgres.h"
  40 #include "optimizer/geqo_copy.h"
  41 #include "optimizer/geqo_random.h"
  42 #include "optimizer/geqo_selection.h"
  43
  44 static int      linear(int max, double bias);
  45
  46 /* geqo_selection
  47  *
  48  *       according to bias described by input parameters,
  49  *       second genes are selected from the pool
  50  */
  51 void
  52 geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
  53 {
  54         int                     first,
  55                                 second;
  56
  57         first = (int) linear(pool->size, bias);
  58         second = (int) linear(pool->size, bias);
  59
  60         if (pool->size > 1)
  61         {
  62                 while (first == second)
  63                         second = (int) linear(pool->size, bias);
  64         }
  65
  66         geqo_copy(momma, &pool->data[first], pool->string_length);
  67         geqo_copy(daddy, &pool->data[second], pool->string_length);
  68 }
  69
  70 /* linear
  71  *        generates random integer between 0 and input max number
  72  *        using input linear bias
  73  *
  74  *        probability distribution function is: f(x) = bias - 2(bias - 1)x
  75  *                       bias = (prob of first rule) / (prob of middle rule)
  76  *
  77  */
  78
  79 static int
  80 linear(int pool_size, double bias)              /* bias is y-intercept of linear
  81                                                                                  * distribution */
  82 {
  83         double          index;                  /* index between 0 and pop_size */
  84         double          max = (double) pool_size;
  85
  86         index = max * (bias - sqrt((bias * bias) - 4.0 * (bias - 1.0) * geqo_rand()))
  87                 / 2.0 / (bias - 1.0);
  88
  89         return (int) index;
  90 }