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-2024, 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         384 : geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
      55             :                Pool *pool, double bias)
      56             : {
      57             :     int         first,
      58             :                 second;
      59             : 
      60         384 :     first = linear_rand(root, pool->size, bias);
      61         384 :     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         384 :     if (pool->size > 1)
      68             :     {
      69         396 :         while (first == second)
      70          12 :             second = linear_rand(root, pool->size, bias);
      71             :     }
      72             : 
      73         384 :     geqo_copy(root, momma, &pool->data[first], pool->string_length);
      74         384 :     geqo_copy(root, daddy, &pool->data[second], pool->string_length);
      75         384 : }
      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         780 : linear_rand(PlannerInfo *root, int pool_size, double bias)
      89             : {
      90             :     double      index;          /* index between 0 and pool_size */
      91         780 :     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         780 :         sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
     105         780 :         if (sqrtval > 0.0)
     106         780 :             sqrtval = sqrt(sqrtval);
     107         780 :         index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
     108         780 :     } while (index < 0.0 || index >= max);
     109             : 
     110         780 :     return (int) index;
     111             : }