/src/postgres/src/backend/optimizer/geqo/geqo_selection.c
Line | Count | Source |
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 | | geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, |
56 | | Pool *pool, double bias) |
57 | 0 | { |
58 | 0 | int first, |
59 | 0 | second; |
60 | |
|
61 | 0 | first = linear_rand(root, pool->size, bias); |
62 | 0 | 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 | 0 | if (pool->size > 1) |
69 | 0 | { |
70 | 0 | while (first == second) |
71 | 0 | second = linear_rand(root, pool->size, bias); |
72 | 0 | } |
73 | |
|
74 | 0 | geqo_copy(root, momma, &pool->data[first], pool->string_length); |
75 | 0 | geqo_copy(root, daddy, &pool->data[second], pool->string_length); |
76 | 0 | } |
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 | | linear_rand(PlannerInfo *root, int pool_size, double bias) |
90 | 0 | { |
91 | 0 | double index; /* index between 0 and pool_size */ |
92 | 0 | 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 | 0 | do |
102 | 0 | { |
103 | 0 | double sqrtval; |
104 | |
|
105 | 0 | sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root); |
106 | 0 | if (sqrtval > 0.0) |
107 | 0 | sqrtval = sqrt(sqrtval); |
108 | 0 | index = max * (bias - sqrtval) / 2.0 / (bias - 1.0); |
109 | 0 | } while (index < 0.0 || index >= max); |
110 | |
|
111 | 0 | return (int) index; |
112 | 0 | } |