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 : : /*
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 : : }
|
