Source Code for Module pycv.cs.opt.de

  1  # PyCV - A Computer Vision Package for Python Incorporating Fast Training of Face Detection 
  2   
  3  # Copyright 2007 Nanyang Technological University, Singapore. 
  4  # Authors: Minh-Tri Pham, Viet-Dung D. Hoang, and Tat-Jen Cham. 
  5   
  6  # This file is part of PyCV. 
  7   
  8  # PyCV is free software: you can redistribute it and/or modify 
  9  # it under the terms of the GNU General Public  
 10  # License as published by the Free Software Foundation, either version  
 11  # 3 of the License, or (at your option) any later version. 
 12   
 13  # PyCV is distributed in the hope that it will be useful, 
 14  # but WITHOUT ANY WARRANTY; without even the implied warranty of 
 15  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 16  # GNU General Public License for more details. 
 17   
 18  # You should have received a copy of the GNU General Public License 
 19  # along with this program.  If not, see <http://www.gnu.org/licenses/>. 
 20   
 21  # --------------------------------------------------------------------- 
 22  #!/usr/bin/env python 
 23   
 24   
 25  """Differential Evolution Optimization 
 26   
 27  :Author: Robert Kern 
 28   
 29  Modified a little bit by Minh-Tri Pham to work with scipy 0.6.0+ 
 30   
 31  Copyright 2005 by Robert Kern. 
 32  """ 
 33   
 34  import scipy as sp 
 35  from numpy.random import rand, permutation 
 36   
 37  __all__ = ['DiffEvolver'] 
 38   
 39  # Notes: for future modifications: 
 40  # Ali, M. M., and A. Toern. Topographical differential evoltion using 
 41  # pre-calculated differentials. _Stochastic and Global Optimization_. 1--17. 
 42  # 
 43  #  A good scale value: 
 44  #    F = max(l_min, 1-min(abs(f_min/f_max), abs(f_max/f_min))) 
 45  #      ~ 0.3 <= l_min <= 0.4 
 46  #      ~ f_min and f_max are the minimum and maximum values in the initial 
 47  #        population. 
 48  # 
 49  #  Pre-calculated differentials: 
 50  #    Keep a set of differentials A. 
 51  #    For each x_i of the population S: 
 52  #      Every M steps, randomly select 3 points x_r1, x_r2, x_r3 from S (not x_i). 
 53  #        Compute new x_i using x_r1 + F*(x_r2-x_r3). 
 54  #        Store differential in A. 
 55  #      Each other step: 
 56  #        Randomly select x_r1 from S and a differential vector from A. 
 57  #      Crossover. 
 58  # 
 59  #  Convergence criterion: 
 60  #    f_max - f_min < eps 
 61  # 
 62  #  Topographical DEPD: 
 63  #    Two populations S and Sa (auxiliary). 
 64  #    Phase counter t = 0 and array shift[:] = False. 
 65  #    Stopping condition: e.g. t >= 4. 
 66  #    g << N, number of nearest neighbors to search for graph minima. 
 67  #    Ng << N, number of points for graph. 
 68  #    For each x_i in S, do DEPD as described above to get y_i. 
 69  #    if f(y_i) < f(x_i): 
 70  #      if shift[i] is False: 
 71  #        shift[i] = True 
 72  #        S[i] = y_i 
 73  #      else: 
 74  #        Sa[i] = y_i 
 75  #      if alltrue(shift,axis=0): 
 76  #        Find graph minima of f(x) using the Ng best points in S. 
 77  #        Do local search from each minimum. 
 78  #        Replace worst Ng points in S with best Ng points in Sa. 
 79  #        If best from this phase is better than previous best, t=0. 
 80  #        Else: t += 1. 
 81  #        shift[:] = False 
 82  #    Next generation. 
 83   
 84 -class DiffEvolver: 
 85      """Minimize a function using differential evolution. 
 86   
 87      Constructors 
 88      ------------ 
 89      DiffEvolver(func, pop0, args=(), crossover_rate=0.5, scale=None, 
 90          strategy=('rand', 2, 'bin'), eps=1e-6) 
 91        func -- function to minimize 
 92        pop0 -- sequence of initial vectors 
 93        args -- additional arguments to apply to func 
 94        crossover_rate -- crossover probability [0..1] usually 0.5 or so 
 95        scale -- scaling factor to apply to differences [0..1] usually > 0.5 
 96          if None, then calculated from pop0 using a heuristic 
 97        strategy -- tuple specifying the differencing/crossover strategy 
 98          The first element is one of 'rand', 'best', 'rand-to-best' to specify 
 99          how to obtain an initial trial vector. 
100          The second element is either 1 or 2 (or only 1 for 'rand-to-best') to 
101          specify the number of difference vectors to add to the initial trial. 
102          The third element is (currently) 'bin' to specify binomial crossover. 
103        eps -- if the maximum and minimum function values of a given generation are 
104          with eps of each other, convergence has been achieved. 
105   
106      DiffEvolver.frombounds(func, lbound, ubound, npop, crossover_rate=0.5, 
107          scale=None, strategy=('rand', 2, 'bin'), eps=1e-6) 
108        Randomly initialize the population within given rectangular bounds. 
109        lbound -- lower bound vector 
110        ubound -- upper bound vector 
111        npop -- size of population 
112   
113      Public Methods 
114      -------------- 
115      solve(newgens=100) 
116        Run the minimizer for newgens more generations. Return the best parameter 
117        vector from the whole run. 
118   
119      Public Members 
120      -------------- 
121      best_value -- lowest function value in the history 
122      best_vector -- minimizing vector 
123      best_val_history -- list of best_value's for each generation 
124      best_vec_history -- list of best_vector's for each generation 
125      population -- current population 
126      pop_values -- respective function values for each of the current population 
127      generations -- number of generations already computed 
128      func, args, crossover_rate, scale, strategy, eps -- from constructor 
129      """ 
130 -    def __init__(self, func, pop0, args=(), crossover_rate=0.5, scale=None, 
131              strategy=('rand', 2, 'bin'), eps=1e-6): 
132          self.func = func 
133          self.population = sp.array(pop0) 
134   
135          # added by Minh-Tri Pham 
136          for n in xrange(len(self.population)): 
137              self.refine(self.population[n]) 
138   
139          self.npop, self.ndim = self.population.shape 
140          self.args = args 
141          self.crossover_rate = crossover_rate 
142          self.strategy = strategy 
143          self.eps = eps 
144   
145          self.pop_values = [self.func(m, *args) for m in self.population] 
146          bestidx = sp.argmin(self.pop_values) 
147          self.best_vector = self.population[bestidx] 
148          self.best_value = self.pop_values[bestidx] 
149   
150          if scale is None: 
151              self.scale = self.calculate_scale() 
152          else: 
153              self.scale = scale 
154   
155          self.generations = 0 
156          self.best_val_history = [] 
157          self.best_vec_history = [] 
158   
159          self.jump_table = { 
160              ('rand', 1, 'bin'): (self.choose_rand, self.diff1, self.bin_crossover), 
161              ('rand', 2, 'bin'): (self.choose_rand, self.diff2, self.bin_crossover), 
162              ('best', 1, 'bin'): (self.choose_best, self.diff1, self.bin_crossover), 
163              ('best', 2, 'bin'): (self.choose_best, self.diff2, self.bin_crossover), 
164              ('rand-to-best', 1, 'bin'): 
165                  (self.choose_rand_to_best, self.diff1, self.bin_crossover), 
166              } 
167   
168 -    def clear(self): 
169          self.best_val_history = [] 
170          self.best_vec_history = [] 
171          self.generations = 0 
172          self.pop_values = [self.func(m, *self.args) for m in self.population] 
173   
174 -    def frombounds(cls, func, lbound, ubound, npop, crossover_rate=0.5, 
175              scale=None, strategy=('rand', 2, 'bin'), eps=1e-6): 
176          lbound = sp.asarray(lbound) 
177          ubound = sp.asarray(ubound) 
178          pop0 = rand(npop, len(lbound))*(ubound-lbound) + lbound 
179          return cls(func, pop0, crossover_rate=crossover_rate, scale=scale, 
180              strategy=strategy, eps=eps) 
181      frombounds = classmethod(frombounds) 
182   
183 -    def calculate_scale(self): 
184          rat = abs(max(self.pop_values)/self.best_value) 
185          rat = min(rat, 1./rat) 
186          return max(0.3, 1.-rat) 
187   
188 -    def bin_crossover(self, oldgene, newgene): 
189          mask = rand(self.ndim) < self.crossover_rate 
190          return sp.where(mask, newgene, oldgene) 
191   
192 -    def select_samples(self, candidate, nsamples): 
193          possibilities = range(self.npop) 
194          possibilities.remove(candidate) 
195          return permutation(possibilities)[:nsamples] 
196   
197 -    def diff1(self, candidate): 
198          i1, i2 = self.select_samples(candidate, 2) 
199          return self.scale * (self.population[i1] - self.population[i2]) 
200   
201 -    def diff2(self, candidate): 
202          i1, i2, i3, i4 = self.select_samples(candidate, 4) 
203          return self.scale * (self.population[i1] - self.population[i2] + 
204                               self.population[i3] - self.population[i4]) 
205   
206 -    def choose_best(self, candidate): 
207          return self.best_vector 
208   
209 -    def choose_rand(self, candidate): 
210          i = self.select_samples(candidate, 1)[0] 
211          return self.population[i] 
212   
213 -    def choose_rand_to_best(self, candidate): 
214          return ((1-self.scale) * self.population[candidate] + 
215                  self.scale * self.best_vector) 
216   
217 -    def get_trial(self, candidate): 
218          chooser, differ, crosser = self.jump_table[self.strategy] 
219          trial = crosser(self.population[candidate], 
220              chooser(candidate) + differ(candidate)) 
221   
222          self.refine(trial) # added by Minh-Tri Pham 
223   
224          return trial 
225           
226      # begin of addition by Minh-Tri Pham 
227 -    def refine(self,trial): 
228          """Refine the current trial (e.g. constrain it) 
229           
230          :Parameters: 
231              trial : array 
232                  a trial whose content is to be refined 
233          """ 
234          pass 
235      #end of addition by Minh Tri Pham 
236   
237 -    def converged(self): 
238          return max(self.pop_values) - min(self.pop_values) <= self.eps 
239   
240 -    def solve(self, newgens=100): 
241          """Run for newgens more generations. 
242   
243          Return best parameter vector from the entire run. 
244          """ 
245          for gen in xrange(self.generations+1, self.generations+newgens+1): 
246              for candidate in range(self.npop): 
247                  trial = self.get_trial(candidate) 
248                  trial_value = self.func(trial, *self.args) 
249                  if trial_value < self.pop_values[candidate]: 
250                      self.population[candidate] = trial 
251                      self.pop_values[candidate] = trial_value 
252                      if trial_value < self.best_value: 
253                          self.best_vector = trial 
254                          self.best_value = trial_value 
255              self.best_val_history.append(self.best_value) 
256              self.best_vec_history.append(self.best_vector) 
257              if self.converged(): 
258                  break 
259          self.generations = gen 
260          return self.best_vector 
261