← Back to branch summary

~ubuntu-branches/ubuntu/natty/python-cogent/natty

« back to all changes in this revision

Viewing changes to cogent/maths/simannealingoptimiser.py

  • Committer: Bazaar Package Importer
  • Author(s): Steffen Moeller
  • Date: 2010-12-04 22:30:35 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20101204223035-j11kinhcrrdgg2p2
Tags: 1.5-1
* Bumped standard to 3.9.1, no changes required.
* New upstream version.
  - major additions to Cookbook
  - added AlleleFreqs attribute to ensembl Variation objects.
  - added getGeneByStableId method to genome objects.
  - added Introns attribute to Transcript objects and an Intron class.
  - added Mann-Whitney test and a Monte-Carlo version
  - exploratory and confirmatory period estimation techniques (suitable for
    symbolic and continuous data)
  - Information theoretic measures (AIC and BIC) added
  - drawing of trees with collapsed nodes
  - progress display indicator support for terminal and GUI apps
  - added parser for illumina HiSeq2000 and GAiix sequence files as 
    cogent.parse.illumina_sequence.MinimalIlluminaSequenceParser.
  - added parser to FASTQ files, one of the output options for illumina's
    workflow, also added cookbook demo.
  - added functionality for parsing of SFF files without the Roche tools in
    cogent.parse.binary_sff
  - thousand fold performance improvement to nmds
  - >10-fold performance improvements to some Table operations

Show diffs side-by-side

added added

removed removed

Lines of Context:
cogent/maths/simannealingoptimiser.py
8
8
Annealing," Goffe, Ferrier and Rogers, Journal of Econometrics, vol. 60, no. 1/2,
9
9
Jan./Feb. 1994, pp. 65-100.
10
10
"""
11
 
 
 
11
from __future__ import division
12
12
from optimiser import OptimiserBase
13
 
 
14
13
import numpy
15
 
Float = numpy.core.numerictypes.sctype2char(float)
16
14
import time
17
 
 
18
 
__author__ = "Andrew Butterfield"
 
15
from collections import deque
 
16
 
 
17
 
 
18
__author__ = "Andrew Butterfield and Peter Maxwell"
19
19
__copyright__ = "Copyright 2007-2009, The Cogent Project"
20
20
__credits__ = ["Gavin Huttley", "Andrew Butterfield", "Peter Maxwell"]
21
21
__license__ = "GPL"
22
 
__version__ = "1.4.1"
 
22
__version__ = "1.5.0"
23
23
__maintainer__ = "Gavin Huttley"
24
24
__email__ = "gavin.huttley@anu.edu.au"
25
25
__status__ = "Production"
41
41
            if getattr(self, attr) != getattr(other, attr):
42
42
                raise ValueError('Checkpoint file ignored - %s different' % attr)
43
43
    
 
44
    def roundsToReach(self, T):
 
45
        from math import log
 
46
        return int(-log(self.initial_temp/T) / log(self.temp_reduction)) + 1
 
47
        
44
48
    def cool(self):
45
49
        self.T = self.temp_reduction * self.T
46
50
    
53
57
    """Keeps the last few results, for convergence testing"""
54
58
    
55
59
    def __init__(self, sample=4):
56
 
        self.values = [None] * sample
57
 
        self.i = 0
 
60
        self.sample_size = sample
 
61
        #self.values = deque([None]*sample, sample) Py2.6
 
62
        self.values = deque([None]*sample)
58
63
    
59
64
    def note(self, F):
60
 
        self.values[self.i] = F
61
 
        self.i = (self.i + 1) % len(self.values)
62
 
    
63
 
    def hasConverged(self, tolerance):
64
 
        return None not in self.values and max(self.values) - min(self.values) < tolerance
 
65
        self.values.append(F)
 
66
        # Next 2 lines not required once above Py2.6 line is uncommented
 
67
        if len(self.values) > self.sample_size:
 
68
            self.values.popleft()
 
69
            
 
70
    def minRemainingRounds(self, tolerance):
 
71
        last = self.values[-1]
 
72
        return max([0]+[i+1 for (i,v) in enumerate(self.values)
 
73
                if v is None or abs(v-last)>tolerance])
65
74
    
66
75
 
67
76
class AnnealingState(object):
68
77
    def __init__(self, X, function, random_series):
69
78
        self.random_series = random_series
70
79
        self.NFCNEV = 1
71
 
        self.VM = numpy.ones(len(X), Float)
 
80
        self.VM = numpy.ones(len(X), float)
72
81
        self.setX(X, function(X))
73
82
        (self.XOPT, self.FOPT) = (X, self.F)
74
83
        self.NACP = [0] * len(X)
76
85
        self.elapsed_time = 0
77
86
    
78
87
    def setX(self, X, F):
79
 
        self.X = numpy.array(X, Float)
 
88
        self.X = numpy.array(X, float)
80
89
        self.F = F
81
90
    
82
91
    def step(self, function, accept_test):
135
144
                "Function to optimise doesn't match checkpoint file " \
136
145
                "'%s': F=%s now, %s in file." % (
137
146
                    checkpointing_filename, now, then))
138
 
    
 
147
        
139
148
    def run(self, function, tolerance, max_iterations, checkpointer,
140
 
                show_progress):
 
149
                show_remaining):
141
150
        state = self.state
142
151
        history = self.history
143
152
        schedule = self.schedule
144
153
        
145
 
        while not history.hasConverged(tolerance):
146
 
            if show_progress:
147
 
                print "Outer loop = %d" % self.test_count
148
 
            
 
154
        est_anneal_remaining = schedule.roundsToReach(tolerance/10) + 3
 
155
        while True:
 
156
            min_history_remaining = history.minRemainingRounds(tolerance)
 
157
            if min_history_remaining == 0:
 
158
                break
149
159
            self.save(checkpointer)
 
160
            remaining = max(min_history_remaining, est_anneal_remaining)
 
161
            est_anneal_remaining += -1
150
162
            
151
163
            for i in range(self.schedule.dwell):
 
164
                show_remaining(remaining + 1 - i/self.schedule.dwell, 
 
165
                        state.FOPT, schedule.T, state.NFCNEV)
152
166
                state.step(function, self.schedule.willAccept)
153
167
                self.test_count += 1
154
168
                if max_iterations and self.test_count >= max_iterations:
157
171
                    state.adjustStepSizes()
158
172
            
159
173
            history.note(state.F)
160
 
            if show_progress:
161
 
                print "\tF = %f EVALS = %s" % (state.FOPT, state.NFCNEV)
162
174
            state.setX(state.XOPT, state.FOPT)
163
175
            schedule.cool()
164
176
        
182
194
class SimulatedAnnealing(OptimiserBase):
183
195
    """Simulated annealing optimiser for bounded functions
184
196
    """
 
197
    label = "global"
 
198
    
185
199
    # this is a maximiser
186
200
    algorithm_direction = +1
187
201
    
214
228
            if value is not None:
215
229
                setattr(self, attr, value)
216
230
    
217
 
    def runInner(self, function, xopt, show_progress, random_series):
 
231
    def runInner(self, function, xopt, show_remaining, random_series):
218
232
        """Optimise the vector within the bounds specified by the base class.
219
233
        
220
234
        Arguments:
244
258
                self.tolerance,
245
259
                max_iterations,
246
260
                checkpointer = self.checkpointer,
247
 
                show_progress = show_progress)
 
261
                show_remaining = show_remaining)
248
262
        except MaximumEvaluationsReached, detail:
249
263
            print detail.__doc__
250
264
            result = detail.args[0]