Source Code for Module pyvision.optimize.testsuite

  1  ''' 
  2  Copyright David S. Bolme 
  3   
  4  Created on Feb 28, 2011 
  5   
  6  @author: bolme 
  7  ''' 
  8  import unittest 
  9   
 10  import pyvision as pv 
 11  import pyvision.optimize.genetic as ga 
 12  #import scipy as sp 
 13  import numpy as np 
 14  import random 
 15   
 16 -def callback(population): 
 17      plot = pv.Plot(xrange=[0,10],yrange=[0,10]) 
 18      pts = [ [each[1][0].value,each[1][1].value] for each in population ] 
 19      #pts = [ pv.Point(each[1][0],each[1][1]) for each in population ] 
 20      #print pts 
 21      plot.points(pts) 
 22      plot.show(delay=10) 
 23      #for each in population: 
 24      #    plot.point(each[1]) 
 25   
 26 -def unitRectCallback(population): 
 27      if random.random() < 0.05: 
 28          return 
 29      #print "Score:",population[0][0] 
 30      im = pv.Image(np.zeros((1000,1000),dtype=np.float32)) 
 31      for each in population: 
 32          rect = each[1][0].generate() 
 33          im.annotateRect(1000*rect,color='gray') 
 34      rect = population[0][1][0].generate() 
 35      im.annotatePolygon((1000*rect).asPolygon(),color='green',width=3) 
 36      target_rect = pv.CenteredRect(.33385,.69348,.3482,.55283) 
 37      im.annotatePolygon((1000*target_rect).asPolygon(),color='white',width=3) 
 38      im.show() 
 39   
 40 -class Fitness: 
 41      ''' 
 42      Min values is approx -0.63 @ [8,2] 
 43      ''' 
 44   
 45 -    def __call__(self,*args,**kwargs): 
 46           
 47          val = 0.0 
 48          x,y = args 
 49          cx,cy,sigma=3.0,4.0,1.0 
 50          dist2 = (x-cx)**2 + (y-cy)**2 
 51          scale = 1.0/(2*np.pi*sigma**2) 
 52          val += scale*np.exp(-dist2/(2*sigma**2)) 
 53           
 54          cx,cy,sigma=8.0,2.0,0.5 
 55          dist2 = (x-cx)**2 + (y-cy)**2 
 56          scale = 1.0/(2*np.pi*sigma**2) 
 57          val += scale*np.exp(-dist2/(2*sigma**2)) 
 58           
 59          cx,cy,sigma=5.0,9.0,2.0 
 60          dist2 = (x-cx)**2 + (y-cy)**2 
 61          scale = 1.0/(2*np.pi*sigma**2) 
 62          val += scale*np.exp(-dist2/(2*sigma**2)) 
 63           
 64          return -val 
 65   
 66 -class FitnessInt: 
 67      ''' 
 68      Min values is approx -0.63 @ [8,2] 
 69      ''' 
 70   
 71 -    def __call__(self,*args,**kwargs): 
 72           
 73          val = 0.0 
 74          x,y = args 
 75          x = 0.01*x 
 76          y = 0.01*y 
 77          cx,cy,sigma=3.0,4.0,1.0 
 78          dist2 = (x-cx)**2 + (y-cy)**2 
 79          scale = 1.0/(2*np.pi*sigma**2) 
 80          val += scale*np.exp(-dist2/(2*sigma**2)) 
 81           
 82          cx,cy,sigma=8.0,2.0,0.5 
 83          dist2 = (x-cx)**2 + (y-cy)**2 
 84          scale = 1.0/(2*np.pi*sigma**2) 
 85          val += scale*np.exp(-dist2/(2*sigma**2)) 
 86           
 87          cx,cy,sigma=5.0,9.0,2.0 
 88          dist2 = (x-cx)**2 + (y-cy)**2 
 89          scale = 1.0/(2*np.pi*sigma**2) 
 90          val += scale*np.exp(-dist2/(2*sigma**2)) 
 91           
 92          return -val 
 93   
 94 -class FitnessNapsack: 
 95      ''' 
 96      Greedy:     2122.02170961 
 97      GreedySoft: 2154.98878966 
 98      Best:       2151.52428896     
 99      ''' 
100 -    def __init__(self): 
101          # Napsack items: [weight, value] 
102          self.napsack = [ [3.8498804596455516, 2.6158205192194539],[4.5189125797608938, 8.8903995320853131],  
103                           [6.1173469407134675, 4.3700978933395547],[6.9007385880574246, 3.8692730664014396],  
104                           [8.9144167464846280, 4.7836252543936624],[0.4693004547062529, 2.8221296183042233],  
105                           [2.4015132415591500, 8.8948724188649706],[7.2119610986308178, 8.2189050746603627],  
106                           [6.8742463976743275, 0.1290666476865909],[6.1975443218025514, 9.6352852208891058],  
107                           [0.3292378884007918, 7.6920571985448998],[6.7891716791357046, 4.8137531832815919],  
108                           [8.5514192788966188, 5.2561657811810658],[5.9180556988418376, 1.3006205399658544],  
109                           [8.0671560149320385, 7.7731218970116878],[6.0386660285670946, 1.7900969964148827],  
110                           [3.3174935387979518, 3.6922312089695852],[6.5380617593654211, 1.1739197783343658],  
111                           [7.2019215829854657, 4.8665738855354270],[0.0410115173309621, 9.5962099162512047],  
112                           [0.5160585719043453, 2.7326870371658032],[1.8277846017416532, 6.3544813031122178],  
113                           [9.8842564999823956, 3.0262295865225219],[7.4860989752014362, 0.3089877071335456],  
114                           [8.0834584531638498, 1.6854024634582421],[0.5425377493637173, 6.5310787408262119],  
115                           [3.4843324863054215, 2.4315902552567992],[3.5779710897236816, 8.2106929764375973],  
116                           [5.7742315723856166, 1.2463078836786967],[6.0318777890316246, 0.3670870890735067],  
117                           [2.8774075634643435, 6.1738364797893110],[9.1450725522551473, 7.7914018397822620],  
118                           [3.2047077180287742, 9.4598588612822070],[1.1167027704978094, 5.1292430796049526],  
119                           [7.5335325192597722, 4.2008849118851144],[8.0060003984360364, 0.3453745034545285],  
120                           [4.1572532576362811, 5.5826759970594120],[4.8295916369681580, 6.0661961083185245],  
121                           [0.9635142164770282, 1.1439694238709974],[0.5460964518464928, 6.8024967241254943],  
122                           [5.4975251734276585, 4.5029749519689997],[5.0668911404556907, 6.2606269283238518],  
123                           [2.5506607296936989, 2.0198909909102314],[9.4149331889825678, 7.5664649402992747],  
124                           [7.8120957703705578, 2.5173457559511805],[2.4158740472850893, 3.6750720594921651],  
125                           [4.7301946764109806, 6.7643300136764939],[1.9817641689609866, 7.2181879836120642],  
126                           [5.0366321352514918, 2.5843130510050702],[2.5304869867849886, 9.7949844854539752],  
127                           [2.9403099192214190, 9.2996118833243067],[6.9036989146152470, 7.8085029359642233],  
128                           [2.4789462548245877, 2.1278890919908844],[6.1657324514331684, 9.3948950035790020],  
129                           [5.9704063048726823, 8.4484636770335069],[6.1647182439418247, 4.9416598764541302],  
130                           [1.3433171070152927, 0.9436729442012903],[3.0503134091567716, 8.5014086442476948],  
131                           [8.9857262873424233, 4.4395019567438601],[6.7615506265458354, 3.1237402173999982],  
132                           [6.5496041740782642, 5.3398880866520937],[8.8279482373425360, 4.6869911466232654],  
133                           [5.6171331059380067, 1.7649945424378233],[4.5323876725646244, 0.8070819665916628],  
134                           [6.7986694347766043, 3.8074853591525404],[9.3562536405189149, 9.0672137648276987],  
135                           [4.3728896028925277, 2.2430957497192483],[2.2243966554075776, 5.8479695623273065],  
136                           [2.2920587007505979, 2.2437759237758925],[7.2566755756751231, 5.0412626439851183],  
137                           [6.7249111241940165, 1.5536858497584638],[8.0579178682464629, 1.2343910851579643],  
138                           [6.8754141358879455, 6.0317671757976203],[1.1863969223776127, 1.5399740016422581],  
139                           [1.7084302568288123, 6.6386825337328892],[3.6323577569600474, 6.9916456275588459],  
140                           [8.8824506098079468, 4.0975086517123795],[8.4492722663078563, 9.5384267527149156],  
141                           [7.5004514342733666, 9.5470395401946533],[3.8623626673491032, 1.3184566778556683],  
142                           [5.2176965749255499, 1.6969605910220198],[7.6971622834725126, 9.3186430484212899],  
143                           [6.4352319531434858, 2.6571361421874986],[9.4682994732626895, 5.0475691909212648],  
144                           [3.8968677899083382, 7.7746635634368637],[0.7252874406688580, 7.2339157247591448], 
145                           [7.4042465769195678, 4.6402243401612644],[2.0952606356353831, 0.2403152717438195],  
146                           [5.9367836289158511, 0.8062172968135816],[1.0589966668958084, 9.4899899882108389],  
147                           [8.1105586869235786, 8.7516004555149731],[4.8618052284517219, 0.5721366593317134],  
148                           [1.5843720121388560, 1.6309946195183456],[8.2770272808876406, 2.2543326689249712],  
149                           [2.2764817157991581, 2.9509378599705984],[0.7103568684070182, 6.9414136185046340],  
150                           [2.6785942780931373, 2.5005917823412362],[0.7277672847554017, 4.5486326841546845],  
151                           [7.6984307141459416, 7.0418998319943871],[8.4203479639455541, 7.2403257387387328]] 
152          self.napsack = 50+np.array(self.napsack) 
153           
154          self.max_weight = 2000.0 
155   
156 -    def solve(self): 
157          # split into seperate lists 
158          weights = self.napsack[:,0].flatten() 
159          values  = self.napsack[:,1].flatten() 
160   
161          # compute density         
162          density = values/weights 
163   
164          # Reorder by density 
165          order = density.argsort()[::-1] 
166          weights = weights[order] 
167          values = values[order] 
168          density = density[order] 
169           
170          _ = self.greedy(weights,values,self.max_weight) 
171          #score = self.greedy_soft(weights,values,self.max_weight) 
172          #print "Greedy",score,remaining,solution 
173          #print "GreedySoft",self.greedy_soft(weights, values, self.max_weight) 
174          #print "Search",self.search(weights, values, self.max_weight,0.0,0.0,[]) 
175               
176 -    def greedy(self,weights,values,remaining): 
177          if len(weights) == 0: 
178              return [],0.0,remaining 
179           
180          if weights[0] <= remaining: 
181              solution,score,remaining = self.greedy(weights[1:],values[1:],remaining-weights[0]) 
182              return [True]+solution,values[0]+score,remaining 
183          else:  
184              solution,score,remaining = self.greedy(weights[1:],values[1:],remaining) 
185              return [False]+solution,score,remaining 
186   
187 -    def greedy_soft(self,weights,values,remaining): 
188          if len(weights) == 0: 
189              return 0.0 
190           
191          if weights[0] <= remaining: 
192              score = self.greedy_soft(weights[1:],values[1:],remaining-weights[0]) 
193              return values[0]+score 
194          else:  
195              frac = float(remaining) / weights[0] 
196              score = frac*values[0] 
197              return score 
198       
199 -    def search(self,weights,values,remaining,best,score,solution): 
200          if len(weights) == 0 and score > best: 
201              #print "New Best:",score,solution 
202              #assert 0  
203              return score 
204   
205          soft = self.greedy_soft(weights, values, remaining) 
206           
207          if score + soft > best: 
208              if weights[0] <= remaining: 
209                  new_score = self.search(weights[1:],values[1:],remaining-weights[0],best,score+values[0],solution+[True]) 
210                  if new_score > best: 
211                      best = new_score 
212   
213              new_score = self.search(weights[1:],values[1:],remaining,best,score,solution+[False]) 
214              if new_score > best: 
215                  best = new_score 
216               
217          return best 
218   
219 -    def __call__(self,*args,**kwargs): 
220          ranking = args[0] 
221          weight = 0.0 
222          value = 0.0 
223          for i in ranking: 
224              weight += self.napsack[i,0] 
225              if weight < self.max_weight: 
226                  value += self.napsack[i,1] 
227              else: 
228                  break 
229          return -value 
230               
231       
232 -def fitnessUnitRect(rect,**kwargs): 
233      target_rect = pv.CenteredRect(.33385,.69348,.3482,.55283) 
234      return -target_rect.overlap(rect) 
235   
236   
237 -def fitnessUnitVector(vec,**kwargs): 
238      target = [1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0] 
239      sum_sq = 0.0 
240      for i in range(len(vec)): 
241          sum_sq += (target[i] - vec[i])**2 
242      score =  np.sqrt(sum_sq) 
243      #print "Score:",score 
244      return score 
245   
246   
247 -class GeneticAlgorithmTest(unittest.TestCase): 
248   
249   
250 -    def setUp(self): 
251          pass 
252   
253   
254 -    def tearDown(self): 
255          pass 
256   
257   
258 -    def dtest2DSurfaceFloatMP(self): 
259          alg = ga.GeneticAlgorithm(Fitness(),[ga.GAFloat(0.0,10.0),ga.GAFloat(0.0,10.0)],n_processes=4) 
260          _ = alg.optimize(max_iter=1000) 
261          #print "test2DSurfaceFloatMP",score,args,kwargs 
262           
263 -    def dtest2DSurfaceFloatSP(self): 
264          alg = ga.GeneticAlgorithm(Fitness(),[ga.GAFloat(0.0,10.0),ga.GAFloat(0.0,10.0)],n_processes=1) 
265          _ = alg.optimize(max_iter=5000,callback=callback) 
266          #print "test2DSurfaceFloatSP",score,args,kwargs 
267           
268 -    def dtest2DSurfaceIntSP(self): 
269          alg = ga.GeneticAlgorithm(FitnessInt(),[ga.GAInteger(0,1000),ga.GAInteger(0,1000)],n_processes=1) 
270          _ = alg.optimize(max_iter=1000) 
271          #print "test2DSurfaceIntSP",score,args,kwargs 
272           
273 -    def dtestNapsack(self): 
274          fitness = FitnessNapsack() 
275          #fitness.solve() 
276          alg = ga.GeneticAlgorithm(fitness,[ga.GARanking(100)],n_processes=1) 
277          _ = alg.optimize(max_iter=1000) 
278          #print "testNapsack",score,args,kwargs 
279   
280 -    def testGAUnitVector(self): 
281          #print "Running unitrect test" 
282          alg = ga.GeneticAlgorithm(fitnessUnitVector,[ga.GAUnitVector(9)],population_size=20,n_processes=1) 
283          _ = alg.optimize(max_iter=10000) 
284          #print "testGAUnitVector",score,args,kwargs 
285           
286       
287 -    def dtestGAUnitRect(self): 
288          #print "Running unitrect test" 
289          alg = ga.GeneticAlgorithm(fitnessUnitRect,[ga.GAUnitRect2(min_width=0.05,min_height=0.05,max_height=1.0,max_width=1.0)],population_size=20,n_processes=4) 
290          _ = alg.optimize(max_iter=10000,callback=unitRectCallback) 
291          #print "testGAUnitRect",score,args,kwargs 
292           
293           
294 -    def dtestCircularRange(self): 
295          self.assertAlmostEqual(ga._circularRange(10, -np.pi, np.pi),10-4*np.pi) 
296          self.assertAlmostEqual(ga._circularRange(50.77, -np.pi, np.pi),50.77-16*np.pi) 
297          self.assertAlmostEqual(ga._circularRange(-10, -np.pi, np.pi),-10+4*np.pi) 
298          self.assertAlmostEqual(ga._circularRange(-50.77, -np.pi, np.pi),-50.77+16*np.pi) 
299          self.assertAlmostEqual(ga._circularRange(-1.54, -np.pi, np.pi),-1.54) 
300          self.assertAlmostEqual(ga._circularRange(0.5, -np.pi, np.pi),0.5) 
301           
302 -    def dtestGAAngle(self): 
303          # Test random 
304          for _ in range(100): 
305              ang = ga.GAAngle() 
306              #print ang 
307          # Test mutate 
308          for _ in range(100): 
309              ang = ga.GAAngle(mutation_rate=0.5) 
310              #print ang, 
311              ang.mutate() 
312              #print ang 
313               
314          # Test Combine 
315          for _ in range(100): 
316              ang1 = ga.GAAngle() 
317              ang2 = ga.GAAngle() 
318              ang2.value = ang1.value + 0.1 
319              ang2.clipRange() 
320              #print ang1,ang2, 
321              ang1.combine(ang2) 
322              #print ang1 
323           
324          # Test Combine 
325          for _ in range(100): 
326              ang1 = ga.GAAngle() 
327              ang2 = ga.GAAngle() 
328              ang2.value = ang1.value + 1 
329              ang2.clipRange() 
330              #print ang1,ang2, 
331              ang1.combine(ang2) 
332              #print ang1 
333           
334           
335           
336           
337   
338   
339  if __name__ == "__main__": 
340      print "Running GA Test Suite" 
341      #import sys;sys.argv = ['', 'Test.test2DSurface'] 
342      unittest.main() 
343