TLA  Line data    Source code

       1                 : /*-------------------------------------------------------------------------
       2                 :  *
       3                 :  * geqo_selection.c
       4                 :  *    linear selection scheme for the genetic query optimizer
       5                 :  *
       6                 :  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
       7                 :  * Portions Copyright (c) 1994, Regents of the University of California
       8                 :  *
       9                 :  * src/backend/optimizer/geqo/geqo_selection.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                 : /* 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_rand(PlannerInfo *root, int pool_size, double bias);
      46                 : 
      47                 : 
      48                 : /*
      49                 :  * geqo_selection
      50                 :  *   according to bias described by input parameters,
      51                 :  *   first and second genes are selected from the pool
      52                 :  */
      53                 : void
      54 CBC         192 : geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
      55                 :                Pool *pool, double bias)
      56                 : {
      57                 :     int         first,
      58                 :                 second;
      59                 : 
      60             192 :     first = linear_rand(root, pool->size, bias);
      61             192 :     second = linear_rand(root, pool->size, bias);
      62                 : 
      63                 :     /*
      64                 :      * Ensure we have selected different genes, except if pool size is only
      65                 :      * one, when we can't.
      66                 :      */
      67             192 :     if (pool->size > 1)
      68                 :     {
      69             198 :         while (first == second)
      70               6 :             second = linear_rand(root, pool->size, bias);
      71                 :     }
      72                 : 
      73             192 :     geqo_copy(root, momma, &pool->data[first], pool->string_length);
      74             192 :     geqo_copy(root, daddy, &pool->data[second], pool->string_length);
      75             192 : }
      76                 : 
      77                 : /*
      78                 :  * linear_rand
      79                 :  *    generates random integer between 0 and input max number
      80                 :  *    using input linear bias
      81                 :  *
      82                 :  *    bias is y-intercept of linear distribution
      83                 :  *
      84                 :  *    probability distribution function is: f(x) = bias - 2(bias - 1)x
      85                 :  *           bias = (prob of first rule) / (prob of middle rule)
      86                 :  */
      87                 : static int
      88             390 : linear_rand(PlannerInfo *root, int pool_size, double bias)
      89                 : {
      90                 :     double      index;          /* index between 0 and pool_size */
      91             390 :     double      max = (double) pool_size;
      92                 : 
      93                 :     /*
      94                 :      * geqo_rand() is not supposed to return 1.0, but if it does then we will
      95                 :      * get exactly max from this equation, whereas we need 0 <= index < max.
      96                 :      * Also it seems possible that roundoff error might deliver values
      97                 :      * slightly outside the range; in particular avoid passing a value
      98                 :      * slightly less than 0 to sqrt().  If we get a bad value just try again.
      99                 :      */
     100                 :     do
     101                 :     {
     102                 :         double      sqrtval;
     103                 : 
     104             390 :         sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
     105             390 :         if (sqrtval > 0.0)
     106             390 :             sqrtval = sqrt(sqrtval);
     107             390 :         index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
     108             390 :     } while (index < 0.0 || index >= max);
     109                 : 
     110             390 :     return (int) index;
     111                 : }