← Back to branch summary

~ubuntu-branches/ubuntu/saucy/python-scipy/saucy

« back to all changes in this revision

Viewing changes to scipy/sandbox/ga/selection.py

  • Committer: Bazaar Package Importer
  • Author(s): Ondrej Certik
  • Date: 2008-06-16 22:58:01 UTC
  • mfrom: (2.1.24 intrepid)
  • Revision ID: james.westby@ubuntu.com-20080616225801-irdhrpcwiocfbcmt
Tags: 0.6.0-12
http://bugs.debian.org/489149
* The description updated to match the current SciPy (Closes: #489149).
* Standards-Version bumped to 3.8.0 (no action needed)
* Build-Depends: netcdf-dev changed to libnetcdf-dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
scipy/sandbox/ga/selection.py
 
1
#genetic algorithm selection routines
 
2
#based on galib.
 
3
#exception - these classes only work on the scaled fitness
 
4
 
 
5
import numpy as np
 
6
 
 
7
from ga_util import GAError
 
8
from prng import prng
 
9
 
 
10
class selector(object):
 
11
    def update(self,pop):
 
12
        pass
 
13
    def select(self,pop):
 
14
        raise GAError('selector.select() must be overridden')
 
15
    def clear(self):
 
16
        pass
 
17
 
 
18
class uniform_selector(selector):
 
19
    def select(self,pop,cnt = 1):
 
20
        if cnt == 1:
 
21
            return prng.choice(pop)
 
22
        res = []
 
23
        for i in range(cnt):
 
24
            res.append(prng.choice(pop))
 
25
        return res
 
26
 
 
27
#class rank_selector(selector):
 
28
#    def select(self,pop,cnt = 1):
 
29
#        pop.sort()
 
30
#        studliest = pop[0].fitness()
 
31
#        # XXX: y?
 
32
#        tied_for_first = [x for x in pop if x.fitness() == y]
 
33
#        if cnt == 1:
 
34
#            return prng.choice(tied_for_first)
 
35
#        res = []
 
36
#        for i in range(cnt):
 
37
#            res.append(prng.choice(tied_for_first))
 
38
#        return res
 
39
 
 
40
#scores must all be positive
 
41
class roulette_selector(selector):
 
42
    def update(self,pop):
 
43
        self.pop = pop[:]
 
44
        sz = len(pop)
 
45
        if not sz:
 
46
            raise GAError('srs_selector - the pop size is 0!')
 
47
        f =self.pop.fitnesses()
 
48
        f_max = max(f); f_min = min(f)
 
49
        if not ( (f_max >= 0 and f_min >= 0) or
 
50
                   (f_max <= 0 and f_min <= 0)):
 
51
            raise GAError('srs_selector requires all fitnesses values to be either strictly positive or strictly negative')
 
52
        if f_max == f_min:
 
53
            f = np.ones_like(f)
 
54
        self.dart_board = np.add.accumulate(f / sum(f,axis=0))
 
55
 
 
56
    def select(self,pop,cnt = 1):
 
57
        returns = []
 
58
        for i in range(cnt):
 
59
            dart = prng.random()
 
60
            idx = 0
 
61
            #binary search would be faster
 
62
            while dart > self.dart_board[idx]:
 
63
                idx = idx + 1
 
64
            returns.append(self.pop[idx])
 
65
        if cnt == 1:
 
66
            return returns[0]
 
67
        else:
 
68
            return returns
 
69
 
 
70
    def clear(self):
 
71
        del self.pop
 
72
 
 
73
#scores must all be positive
 
74
class srs_selector(selector):
 
75
    def update(self,pop):
 
76
        sz = len(pop)
 
77
        if not sz:
 
78
            raise GAError('srs_selector - the pop size is 0!')
 
79
        f =pop.fitnesses()
 
80
        f_max = max(f); f_min = min(f)
 
81
        if not ( (f_max >= 0. and f_min >= 0.) or
 
82
                   (f_max <= 0. and f_min <= 0.)):
 
83
            raise GAError('srs_selector requires all fitnesses values to be either strictly positive or strictly negative - min %f, max %f' %(f_min,f_max))
 
84
        f_avg = sum(f,axis=0)/sz
 
85
        if f_avg == 0.:
 
86
            e = np.ones_like(f)
 
87
        else:
 
88
            if pop.min_or_max() == 'max':
 
89
                e = f/f_avg
 
90
            else:
 
91
                e = (-f+f_max+f_min)/f_avg
 
92
        self.expected_value = e
 
93
        garauntee,chance = divmod(e,1.)
 
94
#               garauntee = floor(e)
 
95
#               chance = remainder(e,1)
 
96
        choices = []
 
97
        for i in xrange(sz):
 
98
            choices = choices + [pop[i]] * int(garauntee[i])
 
99
        #now deal with the remainder
 
100
        dart_board = np.add.accumulate(chance / sum(chance,axis=0))
 
101
        for i in range(len(choices),sz):
 
102
            dart = prng.random()
 
103
            idx = 0
 
104
            while dart > dart_board[idx]:
 
105
                idx = idx + 1
 
106
            choices.append(pop[idx])
 
107
        self.choices = choices
 
108
 
 
109
    def select(self,pop,cnt = 1): #ignore the past in pop
 
110
        res = []
 
111
        for i in range(cnt):
 
112
            res.append(prng.choice(self.choices))
 
113
#               for chosen in res: self.choices.remove(chosen)
 
114
        if cnt == 1:
 
115
            return res[0]
 
116
        return res
 
117
 
 
118
    def clear(self):
 
119
        if hasattr(self,'choices'):
 
120
            del self.choices