diff options
Diffstat (limited to 'src/backend/optimizer/geqo/geqo_selection.c')
-rw-r--r-- | src/backend/optimizer/geqo/geqo_selection.c | 111 |
1 files changed, 111 insertions, 0 deletions
diff --git a/src/backend/optimizer/geqo/geqo_selection.c b/src/backend/optimizer/geqo/geqo_selection.c new file mode 100644 index 0000000..50f678a --- /dev/null +++ b/src/backend/optimizer/geqo/geqo_selection.c @@ -0,0 +1,111 @@ +/*------------------------------------------------------------------------- + * + * geqo_selection.c + * linear selection scheme for the genetic query optimizer + * + * Portions Copyright (c) 1996-2022, 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 max, 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; +} |