Quelle  geqo_selection.c

/*-------------------------------------------------------------------------
 *
 * geqo_selection.c
 *   linear selection scheme for the genetic query optimizer
 *
 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/backend/optimizer/geqo/geqo_selection.c
 *
 *-------------------------------------------------------------------------
 */

/* contributed by:
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch     * Institute of Automatic Control    *
   =        = University of Mining and Technology =
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany       *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* this is adopted from D. Whitley's Genitor algorithm */

/*************************************************************/
/*  */
/* Copyright (c) 1990  */
/* Darrell L. Whitley  */
/* Computer Science Department  */
/* Colorado State University  */
/*  */
/* Permission is hereby granted to copy all or any part of  */
/* this program for free distribution.   The author's name  */
/* and this copyright notice must be included in any copy.  */
/*  */
/*************************************************************/

#include "postgres.h"

#include <math.h>

#include "optimizer/geqo_copy.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_selection.h"

static int linear_rand(PlannerInfo *root, int pool_size, double bias);


/*
 * geqo_selection
 *  according to bias described by input parameters,
 *  first and second genes are selected from the pool
 */
void
geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
      Pool *pool, double bias)
{
 int   first,
    second;

 first = linear_rand(root, pool->size, bias);
 second = linear_rand(root, pool->size, bias);

 /*
  * Ensure we have selected different genes, except if pool size is only
  * one, when we can't.
 */
 if (pool->size > 1)
 {
  while (first == second)
   second = linear_rand(root, pool->size, bias);
 }

 geqo_copy(root, momma, &pool->data[first], pool->string_length);
 geqo_copy(root, daddy, &pool->data[second], pool->string_length);
}

/*
 * linear_rand
 *   generates random integer between 0 and input max number
 *   using input linear bias
 *
 *   bias is y-intercept of linear distribution
 *
 *   probability distribution function is: f(x) = bias - 2(bias - 1)x
 *    bias = (prob of first rule) / (prob of middle rule)
 */
static int
linear_rand(PlannerInfo *root, int pool_size, double bias)
{
 double  index;   /* index between 0 and pool_size */
 double  max = (double) pool_size;

 /*
  * geqo_rand() is not supposed to return 1.0, but if it does then we will
  * get exactly max from this equation, whereas we need 0 <= index < max.
  * Also it seems possible that roundoff error might deliver values
  * slightly outside the range; in particular avoid passing a value
  * slightly less than 0 to sqrt().  If we get a bad value just try again.
 */
 do
 {
  double  sqrtval;

  sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
  if (sqrtval > 0.0)
   sqrtval = sqrt(sqrtval);
  index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
 } while (index < 0.0 || index >= max);

 return (int) index;
}