Age Owner TLA 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-2023, 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
5015 tgl 54 CBC 192 : geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
55 : Pool *pool, double bias)
56 : {
57 : int first,
58 : second;
59 :
5007 60 192 : first = linear_rand(root, pool->size, bias);
61 192 : 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 : */
9345 bruce 67 192 : if (pool->size > 1)
68 : {
69 198 : while (first == second)
5007 tgl 70 6 : second = linear_rand(root, pool->size, bias);
71 : }
72 :
5015 73 192 : geqo_copy(root, momma, &pool->data[first], pool->string_length);
74 192 : geqo_copy(root, daddy, &pool->data[second], pool->string_length);
9545 scrappy 75 192 : }
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
5007 tgl 88 390 : linear_rand(PlannerInfo *root, int pool_size, double bias)
89 : {
90 : double index; /* index between 0 and pool_size */
9344 bruce 91 390 : 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 : do
101 : {
102 : double sqrtval;
103 :
5015 tgl 104 390 : sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
6508 105 390 : if (sqrtval > 0.0)
106 390 : sqrtval = sqrt(sqrtval);
107 390 : index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
108 390 : } while (index < 0.0 || index >= max);
109 :
8986 bruce 110 390 : return (int) index;
111 : }
|
