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-2026, 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              : /*
      15              :  * contributed by:
      16              :  * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      17              :  * *  Martin Utesch              * Institute of Automatic Control      *
      18              :  * =                             = University of Mining and Technology =
      19              :  * *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                   *
      20              :  * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      21              :  */
      22              : 
      23              : /* this is adopted from D. Whitley's Genitor algorithm */
      24              : 
      25              : /*************************************************************/
      26              : /*                                                           */
      27              : /*  Copyright (c) 1990                                       */
      28              : /*  Darrell L. Whitley                                       */
      29              : /*  Computer Science Department                              */
      30              : /*  Colorado State University                                */
      31              : /*                                                           */
      32              : /*  Permission is hereby granted to copy all or any part of  */
      33              : /*  this program for free distribution.   The author's name  */
      34              : /*  and this copyright notice must be included in any copy.  */
      35              : /*                                                           */
      36              : /*************************************************************/
      37              : 
      38              : #include "postgres.h"
      39              : 
      40              : #include <math.h>
      41              : 
      42              : #include "optimizer/geqo_copy.h"
      43              : #include "optimizer/geqo_random.h"
      44              : #include "optimizer/geqo_selection.h"
      45              : 
      46              : static int  linear_rand(PlannerInfo *root, int pool_size, double bias);
      47              : 
      48              : 
      49              : /*
      50              :  * geqo_selection
      51              :  *   according to bias described by input parameters,
      52              :  *   first and second genes are selected from the pool
      53              :  */
      54              : void
      55         1820 : geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
      56              :                Pool *pool, double bias)
      57              : {
      58              :     int         first,
      59              :                 second;
      60              : 
      61         1820 :     first = linear_rand(root, pool->size, bias);
      62         1820 :     second = linear_rand(root, pool->size, bias);
      63              : 
      64              :     /*
      65              :      * Ensure we have selected different genes, except if pool size is only
      66              :      * one, when we can't.
      67              :      */
      68         1820 :     if (pool->size > 1)
      69              :     {
      70         1950 :         while (first == second)
      71          130 :             second = linear_rand(root, pool->size, bias);
      72              :     }
      73              : 
      74         1820 :     geqo_copy(root, momma, &pool->data[first], pool->string_length);
      75         1820 :     geqo_copy(root, daddy, &pool->data[second], pool->string_length);
      76         1820 : }
      77              : 
      78              : /*
      79              :  * linear_rand
      80              :  *    generates random integer between 0 and input max number
      81              :  *    using input linear bias
      82              :  *
      83              :  *    bias is y-intercept of linear distribution
      84              :  *
      85              :  *    probability distribution function is: f(x) = bias - 2(bias - 1)x
      86              :  *           bias = (prob of first rule) / (prob of middle rule)
      87              :  */
      88              : static int
      89         3770 : linear_rand(PlannerInfo *root, int pool_size, double bias)
      90              : {
      91              :     double      index;          /* index between 0 and pool_size */
      92         3770 :     double      max = (double) pool_size;
      93              : 
      94              :     /*
      95              :      * geqo_rand() is not supposed to return 1.0, but if it does then we will
      96              :      * get exactly max from this equation, whereas we need 0 <= index < max.
      97              :      * Also it seems possible that roundoff error might deliver values
      98              :      * slightly outside the range; in particular avoid passing a value
      99              :      * slightly less than 0 to sqrt().  If we get a bad value just try again.
     100              :      */
     101              :     do
     102              :     {
     103              :         double      sqrtval;
     104              : 
     105         3770 :         sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
     106         3770 :         if (sqrtval > 0.0)
     107         3770 :             sqrtval = sqrt(sqrtval);
     108         3770 :         index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
     109         3770 :     } while (index < 0.0 || index >= max);
     110              : 
     111         3770 :     return (int) index;
     112              : }