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