pyvision.optimize.genetic

1 # PyVision License 2 # 3 # Copyright (c) 2006-2008 David S. Bolme 4 # All rights reserved. 5 # 6 # Redistribution and use in source and binary forms, with or without 7 # modification, are permitted provided that the following conditions 8 # are met: 9 # 10 # 1. Redistributions of source code must retain the above copyright 11 # notice, this list of conditions and the following disclaimer. 12 # 13 # 2. Redistributions in binary form must reproduce the above copyright 14 # notice, this list of conditions and the following disclaimer in the 15 # documentation and/or other materials provided with the distribution. 16 # 17 # 3. Neither name of copyright holders nor the names of its contributors 18 # may be used to endorse or promote products derived from this software 19 # without specific prior written permission. 20 # 21 # 22 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 # ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 25 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR 26 # CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 27 # EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 28 # PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 29 # PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 30 # LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 31 # NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 32 # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 33 34 ''' 35 This module contains a basic framework for a genetic algorithm. This specific 36 implentation specifically keeps high selective pressure on the population by 37 always keeping the best individuals found. The algorithm checks to make sure 38 that no individual is tested twice. 39 40 Chromozomes are constructed from "Variable" classes that govern rondom 41 generation and recombination of each element in the chromozome. For 42 example if your fitness function requires a number from one to ten you 43 could uses a ChoiceVariable with choices = [1,2,3,4,5,6,7,8,9,10]. 44 45 TODO: Add a tutorial. 46 47 This class also has some examples in the unit tests. 48 ''' 49 50 import random 51 #import unittest 52 import math 53 import multiprocessing as mp 54 #import sys 55 import traceback 56 import numpy as np 57 import copy 58 #import time 59 import pyvision as pv 60 61 # Genetic algorithm message types 62 _GA_EVALUATE="GA_EVALUATE" 63 _GA_STOP_WORKER="GA_STOP_WORKER" 64 _GA_SCORE = "GA_SCORE" 65

66 -def _clipRange(val,minval,maxval):

67 minval,maxval = min(minval,maxval),max(minval,maxval) 68 val = min(val,maxval) 69 val = max(val,minval) 70 return val

71 72

73 -def _circularRange(val,minval,maxval):

74 minval,maxval = min(minval,maxval),max(minval,maxval) 75 dist = maxval - minval 76 if val > maxval: 77 t1 = (val - maxval)/dist 78 t2 = t1 - math.floor(t1) 79 t3 = minval + dist*t2 80 return t3 81 elif val < minval: 82 t1 = (val - minval)/dist 83 t2 = t1 - math.ceil(t1) 84 t3 = maxval + dist*t2 85 return t3 86 87 return val

88 89

90 -class GAVariable:

91 ''' 92 This is a superclass for a variable that is optimized by the GA. It 93 has three methods that need to be overridden by subclasses: combine, 94 mutate, and generate. 95 96 97 '''

98 - def __init__(self,mutation_rate=0.025):

99 self.mutation_rate = mutation_rate

100

101 - def random(self):

102 ''' Initialize this variable randomly ''' 103 raise NotImplementedError("This method should be overridden by subclasses")

104

105 - def combine(self,other):

106 '''combine this variable with other.''' 107 raise NotImplementedError("This method should be overridden by subclasses")

108

109 - def mutate(self):

110 '''introduce mutations into the variable.''' 111 raise NotImplementedError("This method should be overridden by subclasses")

112

113 - def generate(self):

114 '''generate the actual value that will be populated in the arguments''' 115 raise NotImplementedError("This method should be overridden by subclasses")

116

117 - def flatValue(self):

118 return self.generate()

119

120 - def __repr__(self):

121 return str(self.value)

122 123 124

125 -class GAFloat(GAVariable):

126

127 - def __init__(self,minval,maxval,**kwargs):

128 GAVariable.__init__(self, **kwargs) 129 self.minval,self.maxval = min(minval,maxval),max(minval,maxval) 130 self.random()

131

132 - def clipRange(self):

133 self.value = _clipRange(self.value, self.minval, self.maxval)

134

135 - def random(self):

136 ''' Initialize this variable randomly ''' 137 self.value = self.minval + (self.maxval - self.minval)*random.random() 138 self.clipRange()

139

140 - def combine(self,other):

141 '''combine this variable with other.''' 142 dist = np.abs(self.value - other.value)+0.000001 143 if random.randint(0,1) == 0: 144 self.value = other.value 145 self.value += np.random.normal(0,dist/3.0) 146 self.clipRange()

147

148 - def mutate(self):

149 '''introduce mutations into the variable.''' 150 if random.random() < self.mutation_rate: 151 dist = np.abs(self.maxval-self.minval) 152 self.value += np.random.normal(0,dist/50.0) 153 self.clipRange()

154

155 - def generate(self):

156 '''generate the actual value that will be populated in the arguments''' 157 return self.value

158

159 - def __repr__(self):

160 return str(self.value)

161 162

163 -class GALogFloat(GAVariable):

164 ''' 165 A float on a log scale. 166 ''' 167

168 - def __init__(self,minval,maxval,**kwargs):

169 GAVariable.__init__(self, **kwargs) 170 minval = np.log(minval) 171 maxval = np.log(maxval) 172 self.minval,self.maxval = min(minval,maxval),max(minval,maxval) 173 self.random()

174

175 - def clipRange(self):

176 self.value = _clipRange(self.value, self.minval, self.maxval)

177

178 - def random(self):

179 ''' Initialize this variable randomly ''' 180 self.value = self.minval + (self.maxval - self.minval)*random.random() 181 self.clipRange()

182

183 - def combine(self,other):

184 '''combine this variable with other.''' 185 dist = np.abs(self.value - other.value)+0.000001 186 if random.randint(0,1) == 0: 187 self.value = other.value 188 self.value += np.random.normal(0,dist/3.0) 189 self.clipRange()

190

191 - def mutate(self):

192 '''introduce mutations into the variable.''' 193 if random.random() < self.mutation_rate: 194 dist = np.abs(self.maxval-self.minval) 195 self.value += np.random.normal(0,dist/50.0) 196 self.clipRange()

197

198 - def generate(self):

199 '''generate the actual value that will be populated in the arguments''' 200 return np.exp(self.value)

201

202 - def __repr__(self):

203 return str(np.exp(self.value))

204 205

206 -class GAAngle(GAVariable):

207 ''' 208 Maps to an angle in the range -pi to pi. 209 ''' 210

211 - def __init__(self,minval=-np.pi,maxval=np.pi,**kwargs):

212 GAVariable.__init__(self, **kwargs) 213 self.minval,self.maxval = minval,maxval 214 self.random()

215

216 - def clipRange(self):

217 self.value = _circularRange(self.value, self.minval, self.maxval)

218

219 - def random(self):

220 ''' Initialize this variable randomly ''' 221 self.value = self.minval + (self.maxval - self.minval)*random.random() 222 self.clipRange()

223

224 - def combine(self,other):

225 '''combine this variable with other.''' 226 t1 = 0.5*(self.minval + self.maxval) # find the center of the range 227 t2 = t1 - self.value # adjustment to center self.value 228 t3 = _circularRange( other.value + t2, self.minval, self.maxval) # adjust other.value 229 dist = np.abs(t3 - t1) # compute dist 230 231 # select one value 232 if random.randint(0,1) == 0: 233 self.value = other.value 234 235 # adjust it 236 self.value += np.random.normal(0,dist/3.0) 237 238 # clip 239 self.clipRange()

240

241 - def mutate(self):

242 '''introduce mutations into the variable.''' 243 if random.random() < self.mutation_rate: 244 dist = np.abs(self.maxval-self.minval) 245 self.value += np.random.normal(0,dist/50.0) 246 self.clipRange()

247

248 - def generate(self):

249 '''generate the actual value that will be populated in the arguments''' 250 return self.value

251

252 - def __repr__(self):

253 return str(self.value)

254

255 -class GAUnitRect(GAVariable):

256

257 - def __init__(self,min_width=0.2,max_width=1.0,min_height=0.2,max_height=1.0,**kwargs):

258 GAVariable.__init__(self,**kwargs) 259 260 assert min_width >= 0 261 assert min_width <= 1 262 assert max_width >= 0 263 assert max_width <= 1 264 assert min_height >= 0 265 assert min_height <= 1 266 assert max_height >= 0 267 assert max_height <= 1 268 assert min_width <= max_width 269 assert min_height <= max_height 270 271 self.min_width = min_width 272 self.max_width = max_width 273 self.min_height = min_height 274 self.max_height = max_height 275 276 self.random()

277

278 - def clipRange(self):

279 self.width = _clipRange(self.width, self.min_width, self.max_width) 280 self.height = _clipRange(self.height, self.min_height, self.max_height) 281 self.cx = _clipRange(self.cx, 0.5*self.width, 1.0 - 0.5*self.width) 282 self.cy = _clipRange(self.cy, 0.5*self.height, 1.0 - 0.5*self.height)

283 284

285 - def random(self):

286 ''' Initialize this variable randomly ''' 287 self.cx = random.random() 288 self.cy = random.random() 289 290 diff = self.max_width - self.min_width 291 self.width = self.min_width + random.random() * diff 292 293 diff = self.max_height - self.min_height 294 self.height = self.min_height + random.random() * diff 295 self.clipRange()

296 297

298 - def combine(self,other):

299 '''combine this variable with other.''' 300 301 # select one value 302 cx_dist = np.abs(self.cx - other.cx) + 1e-7 303 cy_dist = np.abs(self.cy - other.cy) + 1e-7 304 w_dist = np.abs(self.width - other.width) + 1e-7 305 h_dist = np.abs(self.height - other.height) + 1e-7 306 307 if random.randint(0,1) == 0: 308 self.cx = other.cx 309 self.cy = other.cy 310 self.width = other.width 311 self.height = other.height 312 313 if cx_dist <= 0 or cy_dist <= 0 or w_dist <= 0 or h_dist <= 0 : 314 print "Combining:",self,other,cx_dist,cy_dist,w_dist,h_dist 315 self.cx += np.random.normal(0,cx_dist/3.0) 316 self.cy += np.random.normal(0,cy_dist/3.0) 317 self.width += np.random.normal(0,w_dist/3.0) 318 self.height += np.random.normal(0,h_dist/3.0) 319 320 # clip 321 self.clipRange()

322

323 - def mutate(self):

324 '''introduce mutations into the variable.''' 325 if random.random() < self.mutation_rate: 326 dist = np.abs(1.0) 327 self.cx += np.random.normal(0,dist/50.0) 328 329 dist = np.abs(1.0) 330 self.cy += np.random.normal(0,dist/50.0) 331 332 dist = np.abs(1.0) 333 self.cy += np.random.normal(0,dist/50.0) 334 335 dist = np.abs(1.0) 336 self.cy += np.random.normal(0,dist/50.0) 337 338 self.clipRange()

339

340 - def generate(self):

341 '''generate the actual value that will be populated in the arguments''' 342 return pv.CenteredRect(self.cx, self.cy, self.width, self.height)

343

344 - def flatValue(self):

345 return self.value.asCenteredTuple()

346

347 - def __repr__(self):

348 return str(self.generate())

349 350 351

352 -class GAUnitRect2(GAVariable):

353

354 - def __init__(self,min_width=0.2,max_width=1.0,min_height=0.2,max_height=1.0,**kwargs):

355 GAVariable.__init__(self,**kwargs) 356 357 assert min_width >= 0 358 assert min_width <= 1 359 assert max_width >= 0 360 assert max_width <= 1 361 assert min_height >= 0 362 assert min_height <= 1 363 assert max_height >= 0 364 assert max_height <= 1 365 assert min_width <= max_width 366 assert min_height <= max_height 367 368 self.min_width = min_width 369 self.max_width = max_width 370 self.min_height = min_height 371 self.max_height = max_height 372 373 self.random()

374

375 - def clipRange(self):

376 self.left = _clipRange(0, self.left, 1) 377 self.right = _clipRange(0, self.right, 1) 378 self.top = _clipRange(0, self.top, 1) 379 self.bottom = _clipRange(0, self.bottom,1) 380 if self.left > self.right: 381 self.left,self.right = self.right,self.left 382 if self.bottom < self.top: 383 self.bottom,self.top = self.top,self.bottom

384 385

386 - def random(self):

387 ''' Initialize this variable randomly ''' 388 self.left = random.random() 389 self.right = random.random() 390 self.top = random.random() 391 self.bottom = random.random() 392 self.clipRange()

393 394

395 - def combine(self,other):

396 '''combine this variable with other.''' 397 398 # select one value 399 l_dist = np.abs(self.left - other.left) + 1e-7 400 r_dist = np.abs(self.right - other.right) + 1e-7 401 t_dist = np.abs(self.top - other.top) + 1e-7 402 b_dist = np.abs(self.bottom - other.bottom) + 1e-7 403 404 if random.randint(0,1) == 0: 405 self.left = other.left 406 self.right = other.right 407 self.top = other.top 408 self.bottom = other.bottom 409 410 if l_dist <= 0 or r_dist <= 0 or t_dist <= 0 or b_dist <= 0 : 411 print "Combining:",self,other,l_dist,r_dist,t_dist,b_dist 412 self.left += np.random.normal(0,l_dist/3.0) 413 self.right += np.random.normal(0,r_dist/3.0) 414 self.top += np.random.normal(0,t_dist/3.0) 415 self.bottom += np.random.normal(0,b_dist/3.0) 416 417 # clip 418 self.clipRange()

419

420 - def mutate(self):

421 '''introduce mutations into the variable.''' 422 if random.random() < self.mutation_rate: 423 dist = np.abs(1.0) 424 self.left += np.random.normal(0,dist/50.0) 425 426 dist = np.abs(1.0) 427 self.right += np.random.normal(0,dist/50.0) 428 429 dist = np.abs(1.0) 430 self.top += np.random.normal(0,dist/50.0) 431 432 dist = np.abs(1.0) 433 self.bottom += np.random.normal(0,dist/50.0) 434 435 self.clipRange()

436

437 - def generate(self):

438 '''generate the actual value that will be populated in the arguments''' 439 return pv.BoundingRect([pv.Point(self.left,self.top),pv.Point(self.right,self.bottom)])

440

441 - def flatValue(self):

442 return self.value.asCenteredTuple()

443

444 - def __repr__(self):

445 return str(self.generate())

446 447 448 449

450 -class GAInteger(GAVariable):

451

452 - def __init__(self,minval,maxval,**kwargs):

453 GAVariable.__init__(self, **kwargs) 454 self.minval,self.maxval = min(minval,maxval),max(minval,maxval) 455 self.random()

456

457 - def clipRange(self):

458 self.value = _clipRange(self.value, self.minval, self.maxval)

459

460 - def random(self):

461 ''' Initialize this variable randomly ''' 462 self.value = random.randint(self.minval,self.maxval) 463 self.clipRange()

464

465 - def combine(self,other):

466 '''combine this variable with other.''' 467 dist = np.abs(self.value - other.value) 468 if random.randint(0,1) == 0: 469 self.value = other.value 470 self.value += random.randint(-dist-1,dist+1) 471 self.clipRange()

472

473 - def mutate(self):

474 '''introduce mutations into the variable.''' 475 if random.random() < self.mutation_rate: 476 dist = np.abs(self.maxval-self.minval) 477 self.value += random.randint(-dist-1,dist+1) 478 self.clipRange()

479

480 - def generate(self):

481 '''generate the actual value that will be populated in the arguments''' 482 return self.value

483

484 - def __repr__(self):

485 return str(self.value)

486 487

488 -class GABoolean(GAVariable):

489

490 - def __init__(self,**kwargs):

491 GAVariable.__init__(self, **kwargs) 492 self.random()

493 494

495 - def random(self):

496 ''' Initialize this variable randomly ''' 497 self.value = random.randint(0,1) == 1

498

499 - def combine(self,other):

500 '''combine this variable with other.''' 501 if random.randint(0,1) == 0: 502 self.value = other.value

503

504 - def mutate(self):

505 '''introduce mutations into the variable.''' 506 if random.random() < self.mutation_rate: 507 self.random()

508

509 - def generate(self):

510 '''generate the actual value that will be populated in the arguments''' 511 return self.value

512

513 - def __repr__(self):

514 return str(self.value)

515 516

517 -class GAChoice(GAVariable):

518

519 - def __init__(self,*choices, **kwargs):

520 GAVariable.__init__(self, **kwargs) 521 self.choices = choices 522 self.random()

523 524

525 - def random(self):

526 ''' Initialize this variable randomly ''' 527 self.value = random.sample(self.choices,1)[0]

528

529 - def combine(self,other):

530 '''combine this variable with other.''' 531 if random.randint(0,1) == 0: 532 self.value = other.value

533

534 - def mutate(self):

535 '''introduce mutations into the variable.''' 536 if random.random() < self.mutation_rate: 537 self.value = random.sample(self.choices,1)[0]

538

539 - def generate(self):

540 '''generate the actual value that will be populated in the arguments''' 541 return self.value

542

543 - def __repr__(self):

544 return str(self.value)

545 546

547 -class GARanking(GAVariable):

548

549 - def __init__(self,n_elements,**kwargs):

550 GAVariable.__init__(self, **kwargs) 551 self.n_elements = n_elements 552 self.ranking = list(range(n_elements)) 553 self.random()

554

555 - def random(self):

556 ''' Initialize this variable randomly ''' 557 random.shuffle(self.ranking)

558

559 - def combine(self,other):

560 '''combine this variable with other.''' 561 a = [ (i,self.ranking[i]) for i in range(len(self.ranking))] 562 b = [ (i,other.ranking[i]) for i in range(len(self.ranking))] 563 564 a.sort(lambda x,y: cmp(x[1],y[1])) 565 b.sort(lambda x,y: cmp(x[1],y[1])) 566 567 c = [] 568 for i in range(len(a)): 569 if random.randint(0,1) == 0: 570 c.append(a[i]) 571 else: 572 c.append(b[i]) 573 574 random.shuffle(c) 575 576 c.sort(lambda x,y: cmp(x[0],y[0])) 577 578 self.ranking = [r for _,r in c]

579 580

581 - def mutate(self):

582 '''introduce mutations into the variable.''' 583 n = int(self.mutation_rate * self.n_elements) + 1 584 for _ in range(n): 585 i1 = random.randint(0,self.n_elements-1) 586 i2 = random.randint(0,self.n_elements-1) 587 x = self.ranking[i1] 588 del self.ranking[i1] 589 self.ranking.insert(i2,x)

590 591

592 - def generate(self):

593 '''generate the actual value that will be populated in the arguments''' 594 return self.ranking

595

596 - def flatValue(self):

597 return self.ranking

598

599 - def __repr__(self):

600 return str(self.ranking)

601 602

603 -class GAUnitVector(GAVariable):

604 ''' A vector constrained to length 1.0. '''

605 - def __init__(self,n_elements,**kwargs):

606 GAVariable.__init__(self, **kwargs) 607 self.n_elements = n_elements 608 self.random()

609

610 - def clipRange(self):

611 self.value = pv.unit(self.value)

612

613 - def random(self):

614 ''' Initialize this variable randomly ''' 615 self.value = np.random.normal(size=[self.n_elements]) 616 self.clipRange()

617

618 - def combine(self,other):

619 '''combine this variable with other.''' 620 for i in range(len(self.value)): 621 dist = np.abs(self.value[i] - other.value[i])+0.000001 622 if random.randint(0,1) == 0: 623 self.value[i] = other.value[i] 624 self.value[i] += np.random.normal(0,dist/3.0) 625 self.clipRange()

626 627 628

629 - def mutate(self):

630 '''introduce mutations into the variable.''' 631 if random.random() < self.mutation_rate: 632 for i in range(len(self.value)): 633 self.value[i] += np.random.normal(0,0.02) 634 self.clipRange()

635 636

637 - def generate(self):

638 '''generate the actual value that will be populated in the arguments''' 639 return self.value

640

641 - def flatValue(self):

642 return list(self.value.flatten())

643

644 - def __repr__(self):

645 return str(self.value)

646

647 -class GAWeighting(GAVariable):

648 ''' A positive vector that sums to 1.0. ''' 649

650 - def __init__(self,n_elements,**kwargs):

651 GAVariable.__init__(self, **kwargs) 652 self.n_elements = n_elements 653 self.random()

654

655 - def clipRange(self):

656 self.value = self.value*(self.value > 0) 657 weight = self.value.sum() 658 659 # prevent divide by zero 660 weight = max(weight,0.0001) 661 662 self.value = self.value/weight

663 664

665 - def random(self):

666 ''' Initialize this variable randomly ''' 667 self.value = np.random.random(size=[self.n_elements]) 668 self.clipRange()

669

670 - def combine(self,other):

671 '''combine this variable with other.''' 672 for i in range(len(self.value)): 673 dist = np.abs(self.value[i] - other.value[i])+0.000001 674 if random.randint(0,1) == 0: 675 self.value[i] = other.value[i] 676 self.value[i] += np.random.normal(0,dist/3.0) 677 self.clipRange()

678

679 - def mutate(self):

680 '''introduce mutations into the variable.''' 681 if random.random() < self.mutation_rate: 682 for i in range(len(self.value)): 683 self.value[i] += np.random.normal(0,1)/(50.0*self.n_elements) 684 self.clipRange()

685 686

687 - def generate(self):

688 '''generate the actual value that will be populated in the arguments''' 689 return self.value

690

691 - def flatValue(self):

692 return list(self.value.flatten())

693

694 - def __repr__(self):

695 return str(self.value)

696 697

698 -class GASequence:

699 # TODO: Create this class 700 pass

701

702 -class GASet:

703 # TODO: Create this class 704 pass

705 706 707

708 -def list_generate(args):

709 for i in range(len(args)): 710 #print args[i] 711 if isinstance(args[i],GAVariable): 712 args[i] = args[i].generate() 713 elif isinstance(args[i],(list,tuple)): 714 list_generate(args[i]) 715 elif isinstance(args[i],dict): 716 dict_generate(args[i])

717

718 -def dict_generate(args):

719 for i in args.keys(): 720 if isinstance(args[i],GAVariable): 721 args[i] = args[i].generate() 722 elif isinstance(args[i],(list,tuple)): 723 list_generate(args[i]) 724 elif isinstance(args[i],dict): 725 dict_generate(args[i]) 726 727

728 -def _gaWork(data):

729 ''' 730 This is a work function that gets called on child processes 731 to evaluate a fitness function. 732 ''' 733 try: 734 fitness,args,kwargs = data 735 assert isinstance(args, (list,tuple)) 736 assert isinstance(kwargs, dict) 737 args = copy.deepcopy(args) 738 kwargs = copy.deepcopy(kwargs) 739 list_generate(args) 740 dict_generate(kwargs) 741 score = fitness(*args,**kwargs) 742 except: 743 print "Error in work queue." 744 traceback.print_exc() 745 score = np.inf 746 return score

747 748

749 -class GeneticAlgorithm:

750

751 - def __init__(self,fitness,args=[],kwargs={},initializer=None,initargs=[],population_size=100,n_processes="AUTO"):

752 self.fitness = fitness 753 self.args = args 754 self.kwargs = kwargs 755 self.initializer = initializer 756 self.initargs=initargs 757 self.population_size = population_size 758 self.n_processes = n_processes 759 if self.n_processes == "AUTO": 760 self.n_processes = mp.cpu_count() 761 762 self.run_data = None 763 764 self.running_workers = 0 765 766 self.best_score = np.inf 767 self.population = [] 768 self.bests = [] 769 self.worsts = [] 770 self.history = [] 771 self.iter = 0

772

773 - def list_random(self,args):

774 for i in range(len(args)): 775 if isinstance(args[i],GAVariable): 776 args[i].random() 777 elif isinstance(args[i],(list,tuple)): 778 self.list_random(args[i]) 779 elif isinstance(args[i],dict): 780 self.dict_random(args[i])

781

782 - def dict_random(self,args):

783 for i in args.keys(): 784 if isinstance(args[i],GAVariable): 785 args[i].random() 786 elif isinstance(args[i],(list,tuple)): 787 self.list_random(args[i]) 788 elif isinstance(args[i],dict): 789 self.dict_random(args[i])

790 791

792 - def random(self):

793 ''' 794 Randomly generate an individual for initialization 795 ''' 796 args = copy.deepcopy(self.args) 797 kwargs = copy.deepcopy(self.kwargs) 798 799 self.list_random(args) 800 self.dict_random(kwargs) 801 802 return args,kwargs

803 804

805 - def list_mutate(self,args):

806 for i in range(len(args)): 807 if isinstance(args[i],GAVariable): 808 args[i].mutate() 809 elif isinstance(args[i],(list,tuple)): 810 self.list_mutate(args[i]) 811 elif isinstance(args[i],dict): 812 self.dict_mutate(args[i])

813

814 - def dict_mutate(self,args):

815 for i in args.keys(): 816 if isinstance(args[i],GAVariable): 817 args[i].mutate() 818 elif isinstance(args[i],(list,tuple)): 819 self.list_mutate(args[i]) 820 elif isinstance(args[i],dict): 821 self.dict_mutate(args[i])

822 823

824 - def mutate(self,args):

825 ''' 826 Randomly generate an individual for initialization 827 ''' 828 args = copy.deepcopy(args) 829 830 if isinstance(args, (list,tuple)): 831 self.list_mutate(args) 832 if isinstance(args, dict): 833 self.dict_mutate(args) 834 835 return args

836 837

838 - def list_combine(self,args,other):

839 assert len(args) == len(other) 840 841 for i in range(len(args)): 842 if isinstance(args[i],GAVariable): 843 args[i].combine(other[i]) 844 elif isinstance(args[i],(list,tuple)): 845 self.list_combine(args[i], other[i]) 846 elif isinstance(args[i],dict): 847 self.dict_combine(args[i], other[i]) 848 else: 849 pass

850

851 - def dict_combine(self,args,other):

852 assert len(args) == len(other) 853 854 for key in args.keys(): 855 if isinstance(args[key],GAVariable): 856 args[key].combine(other[key]) 857 elif isinstance(args[key],(list,tuple)): 858 self.list_combine(args[key], other[key]) 859 elif isinstance(args[key],dict): 860 self.dict_combine(args[key], other[key]) 861 else: 862 pass

863

864 - def combine(self,args1,args2):

865 # Make deep copies to preserve data 866 args = copy.deepcopy(args1) 867 other = copy.deepcopy(args2) 868 869 if isinstance(args,list): 870 self.list_combine(args, other) 871 else: 872 self.dict_combine(args, other) 873 874 return args

875 876

877 - def addIndividual(self,score,args,kwargs,ilog=None):

878 # This try block allows multiple values to be returned by the fitness function. 879 # Everything except the score will be stored in extra and should be picklible. 880 extras = [] 881 try: 882 extras = score[1:] 883 score = score[0] 884 except: 885 # this means score must be a single value 886 pass 887 888 if not np.isfinite(score): 889 return 890 891 if score < self.best_score: 892 self.best_score = score 893 if ilog != None: 894 # Print data 895 print "New Best Score:",score 896 897 for i in range(len(args)): 898 print " arg%02d"%i,args[i] 899 keys = list(kwargs.keys()) 900 keys.sort() 901 for key in keys: 902 print " %10s:"%key,kwargs[key] 903 904 self.population.append([score,args,kwargs]) 905 self.population.sort(lambda x,y: cmp(x[0],y[0])) 906 self.population = self.population[:self.population_size] 907 908 self.history.append(score) 909 self.bests.append(self.population[0][0]) 910 self.worsts.append(self.population[-1][0]) 911 912 self.iter += 1 913 914 if ilog != None: 915 self.printPopulation() 916 917 ilog.pickle([score,args,kwargs],"Fitness_%0.8f"%score) 918 for i in xrange(len(extras)): 919 extra = extras[i] 920 if isinstance(extra,pv.Image): 921 ilog(extra,"extra_%02d_%0.8f"%(i,score)) 922 else: 923 ilog.pickle(extra,"extra_%02d_%0.8f"%(i,score)) 924 925 if self.iter % 64 == 0: 926 plot = pv.Plot(title="Population Statistics",xlabel="Iteration",ylabel="Score") 927 data = [ [i,self.bests[i]] for i in range(len(self.bests)) ] 928 plot.lines(data,width=3,color='green') 929 data = [ [i,self.history[i]] for i in range(len(self.bests)) ] 930 plot.points(data,shape=16,color='blue',size=2) 931 data = [ [i,self.worsts[i]] for i in range(len(self.bests)) ] 932 plot.lines(data,width=3,color='red') 933 ilog(plot,"PopulationData")

934 935

936 - def printPopulation(self):

937 print "GA Population (Iteration %d):"%self.iter, 938 for i in range(len(self.population)): 939 if i % 10 == 0: 940 print 941 print " ", 942 print "%8.3f"%self.population[i][0], 943 print 944 print

945 946

947 - def optimize(self,max_iter=1000,callback=None,ilog=None,restart_dir=None):

948 ''' 949 @returns: best_score, args, kwargs 950 ''' 951 952 # Create worker process pool 953 if self.n_processes > 1: 954 print "Init Params (%d cores):"%self.n_processes,self.initializer, self.initargs 955 pool = mp.Pool(self.n_processes,initializer=self.initializer,initargs=self.initargs) 956 957 # Initialize the population with random members 958 work = [] 959 for i in range(max(self.population_size-len(self.population),0)): 960 args,kwargs = self.random() 961 work.append((self.fitness,args,kwargs)) 962 963 if self.n_processes > 1: 964 scores = pool.map(_gaWork, work) 965 for i in range(len(scores)): 966 score = scores[i] 967 _,args,kwargs = work[i] 968 self.addIndividual(score,args,kwargs,ilog=ilog) 969 else: 970 for each in work: 971 score = _gaWork(each) 972 _,args,kwargs = each 973 self.addIndividual(score,args,kwargs,ilog=ilog) 974 975 if len(self.population) < 2: 976 raise ValueError("Could not initialize population.") 977 978 979 while self.iter < max_iter: 980 981 # Generate the next round of work 982 n_work = max(1,self.n_processes) 983 work = [] 984 while len(work) < n_work: 985 i1 = random.randint(0,len(self.population)-1) 986 i2 = random.randint(0,len(self.population)-1) 987 if i1 != i2: 988 _,args1,kwargs1 = self.population[i1] 989 _,args2,kwargs2 = self.population[i2] 990 args = self.combine(args1, args2) 991 kwargs = self.combine(kwargs1, kwargs2) 992 args = self.mutate(args) 993 kwargs = self.mutate(kwargs) 994 work.append((self.fitness,args,kwargs)) 995 996 if self.n_processes > 1: 997 scores = pool.map(_gaWork, work) 998 for i in range(len(scores)): 999 score = scores[i] 1000 _,args,kwargs = work[i] 1001 self.addIndividual(score,args,kwargs,ilog=ilog) 1002 else: 1003 for each in work: 1004 score = _gaWork(each) 1005 _,args,kwargs = each 1006 self.addIndividual(score,args,kwargs,ilog=ilog) 1007 1008 if callback != None: 1009 callback(self.population) 1010 1011 args = copy.deepcopy(self.population[0][1]) 1012 kwargs = copy.deepcopy(self.population[0][2]) 1013 list_generate(args) 1014 dict_generate(kwargs) 1015 1016 return self.population[0][0],args,kwargs

1017

Source Code for Module pyvision.optimize.genetic