Header And Logo

PostgreSQL
| The world's most advanced open source database.

geqo_selection.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * geqo_selection.c
00004  *    linear selection scheme for the genetic query optimizer
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  * src/backend/optimizer/geqo/geqo_selection.c
00010  *
00011  *-------------------------------------------------------------------------
00012  */
00013 
00014 /* contributed by:
00015    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
00016    *  Martin Utesch              * Institute of Automatic Control      *
00017    =                             = University of Mining and Technology =
00018    *  [email protected]  * Freiberg, Germany                   *
00019    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
00020  */
00021 
00022 /* this is adopted from D. Whitley's Genitor algorithm */
00023 
00024 /*************************************************************/
00025 /*                                                           */
00026 /*  Copyright (c) 1990                                       */
00027 /*  Darrell L. Whitley                                       */
00028 /*  Computer Science Department                              */
00029 /*  Colorado State University                                */
00030 /*                                                           */
00031 /*  Permission is hereby granted to copy all or any part of  */
00032 /*  this program for free distribution.   The author's name  */
00033 /*  and this copyright notice must be included in any copy.  */
00034 /*                                                           */
00035 /*************************************************************/
00036 
00037 #include "postgres.h"
00038 
00039 #include <math.h>
00040 
00041 #include "optimizer/geqo_copy.h"
00042 #include "optimizer/geqo_random.h"
00043 #include "optimizer/geqo_selection.h"
00044 
00045 static int  linear_rand(PlannerInfo *root, int max, double bias);
00046 
00047 
00048 /*
00049  * geqo_selection
00050  *   according to bias described by input parameters,
00051  *   first and second genes are selected from the pool
00052  */
00053 void
00054 geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
00055                Pool *pool, double bias)
00056 {
00057     int         first,
00058                 second;
00059 
00060     first = linear_rand(root, pool->size, bias);
00061     second = linear_rand(root, pool->size, bias);
00062 
00063     /*
00064      * Ensure we have selected different genes, except if pool size is only
00065      * one, when we can't.
00066      *
00067      * This code was observed to hang up in an infinite loop when the
00068      * platform's implementation of erand48() was broken.  We now always use
00069      * our own version.
00070      */
00071     if (pool->size > 1)
00072     {
00073         while (first == second)
00074             second = linear_rand(root, pool->size, bias);
00075     }
00076 
00077     geqo_copy(root, momma, &pool->data[first], pool->string_length);
00078     geqo_copy(root, daddy, &pool->data[second], pool->string_length);
00079 }
00080 
00081 /*
00082  * linear_rand
00083  *    generates random integer between 0 and input max number
00084  *    using input linear bias
00085  *
00086  *    bias is y-intercept of linear distribution
00087  *
00088  *    probability distribution function is: f(x) = bias - 2(bias - 1)x
00089  *           bias = (prob of first rule) / (prob of middle rule)
00090  */
00091 static int
00092 linear_rand(PlannerInfo *root, int pool_size, double bias)
00093 {
00094     double      index;          /* index between 0 and pop_size */
00095     double      max = (double) pool_size;
00096 
00097     /*
00098      * If geqo_rand() returns exactly 1.0 then we will get exactly max from
00099      * this equation, whereas we need 0 <= index < max.  Also it seems
00100      * possible that roundoff error might deliver values slightly outside the
00101      * range; in particular avoid passing a value slightly less than 0 to
00102      * sqrt(). If we get a bad value just try again.
00103      */
00104     do
00105     {
00106         double      sqrtval;
00107 
00108         sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
00109         if (sqrtval > 0.0)
00110             sqrtval = sqrt(sqrtval);
00111         index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
00112     } while (index < 0.0 || index >= max);
00113 
00114     return (int) index;
00115 }