← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/backend/optimizer/geqo/geqo_selection.c

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/geqo/geqo_selection.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * geqo_selection.c
 
4
 *        linear selection scheme for the genetic query optimizer
 
5
 *
 
6
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 
7
 * Portions Copyright (c) 1994, Regents of the University of California
 
8
 *
 
9
 * $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_selection.c,v 1.18 2004-12-31 21:59:58 pgsql Exp $
 
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(int max, double bias);
 
46
 
 
47
/* geqo_selection
 
48
 *
 
49
 *       according to bias described by input parameters,
 
50
 *       second genes are selected from the pool
 
51
 */
 
52
void
 
53
geqo_selection(Chromosome *momma, Chromosome *daddy, Pool *pool, double bias)
 
54
{
 
55
        int                     first,
 
56
                                second;
 
57
 
 
58
        first = (int) linear(pool->size, bias);
 
59
        second = (int) linear(pool->size, bias);
 
60
 
 
61
        if (pool->size > 1)
 
62
        {
 
63
                while (first == second)
 
64
                        second = (int) linear(pool->size, bias);
 
65
        }
 
66
 
 
67
        geqo_copy(momma, &pool->data[first], pool->string_length);
 
68
        geqo_copy(daddy, &pool->data[second], pool->string_length);
 
69
}
 
70
 
 
71
/* linear
 
72
 *        generates random integer between 0 and input max number
 
73
 *        using input linear bias
 
74
 *
 
75
 *        probability distribution function is: f(x) = bias - 2(bias - 1)x
 
76
 *                       bias = (prob of first rule) / (prob of middle rule)
 
77
 *
 
78
 */
 
79
 
 
80
static int
 
81
linear(int pool_size, double bias)              /* bias is y-intercept of linear
 
82
                                                                                 * distribution */
 
83
{
 
84
        double          index;                  /* index between 0 and pop_size */
 
85
        double          max = (double) pool_size;
 
86
 
 
87
        index = max * (bias - sqrt((bias * bias) - 4.0 * (bias - 1.0) * geqo_rand()))
 
88
                / 2.0 / (bias - 1.0);
 
89
 
 
90
        return (int) index;
 
91
}