PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_selection.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * geqo_selection.c
4  * linear selection scheme for the genetic query optimizer
5  *
6  * Portions Copyright (c) 1996-2017, 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"
44 
45 static int linear_rand(PlannerInfo *root, int max, 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
55  Pool *pool, double bias)
56 {
57  int first,
58  second;
59 
60  first = linear_rand(root, pool->size, bias);
61  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  * This code was observed to hang up in an infinite loop when the
68  * platform's implementation of erand48() was broken. We now always use
69  * our own version.
70  */
71  if (pool->size > 1)
72  {
73  while (first == second)
74  second = linear_rand(root, pool->size, bias);
75  }
76 
77  geqo_copy(root, momma, &pool->data[first], pool->string_length);
78  geqo_copy(root, daddy, &pool->data[second], pool->string_length);
79 }
80 
81 /*
82  * linear_rand
83  * generates random integer between 0 and input max number
84  * using input linear bias
85  *
86  * bias is y-intercept of linear distribution
87  *
88  * probability distribution function is: f(x) = bias - 2(bias - 1)x
89  * bias = (prob of first rule) / (prob of middle rule)
90  */
91 static int
92 linear_rand(PlannerInfo *root, int pool_size, double bias)
93 {
94  double index; /* index between 0 and pop_size */
95  double max = (double) pool_size;
96 
97  /*
98  * If geqo_rand() returns exactly 1.0 then we will get exactly max from
99  * this equation, whereas we need 0 <= index < max. Also it seems
100  * possible that roundoff error might deliver values slightly outside the
101  * range; in particular avoid passing a value slightly less than 0 to
102  * sqrt(). If we get a bad value just try again.
103  */
104  do
105  {
106  double sqrtval;
107 
108  sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
109  if (sqrtval > 0.0)
110  sqrtval = sqrt(sqrtval);
111  index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
112  } while (index < 0.0 || index >= max);
113 
114  return (int) index;
115 }
double geqo_rand(PlannerInfo *root)
Definition: geqo_random.c:35
int size
Definition: geqo_gene.h:41
static int linear_rand(PlannerInfo *root, int max, double bias)
Definition: type.h:89
int string_length
Definition: geqo_gene.h:42
Definition: geqo_gene.h:38
void geqo_copy(PlannerInfo *root, Chromosome *chromo1, Chromosome *chromo2, int string_length)
Definition: geqo_copy.c:45
Chromosome * data
Definition: geqo_gene.h:40
void geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)