2
import scipy.stats as stats
4
#import scipy.io.dumb_shelve
7
import time, pprint, types,copy
10
if sys.platform != 'win32':
12
timer = time.clock #clock behaves differently work on linux
16
dberror = dumbdbm.error
18
def max_score(pop): return max(map(lambda x: x.score(),pop))
21
"""A basic genetic algorithm. The genetic algorithm is responsible
22
for evolving a population of genomes. While the population and
23
the genomes are in charge of defining most of the genetic operators
24
such as selection, scaling, mutation, and crossover, it is the
25
genetic algorithm class that orchestrates the evolution and calls
26
the operators in the correct order. Most of the work is done
27
in the **step()** method.
29
valid_settings = ['pop_size','p_replace',
30
'p_cross', 'p_mutate','p_deviation',
31
'gens','rand_seed','rand_alg','dbase','update_rate']
32
output_settings = ['crossover','selector', 'scaler','genome_type']
33
default_settings = {'pop_size':150,'p_replace':.8,
34
'p_cross': .8, 'p_mutate':'gene',
35
'p_deviation': 0.,'gens':35,
36
'rand_seed':0,'rand_alg':'CMRG',
37
'update_rate': 10000,'dbase':''}
40
def __init__(self,pop):
41
self.verbose = self.default_verbose
42
self.settings = copy.copy(galg.default_settings)
44
def test_settings(self,settings):
45
for key in settings.keys():
47
self.output_settings.index(key)
48
print 'Warning: The key "%s" in settings is readonly.' % key
50
try: self.valid_settings.index(key)
52
print 'Warning: The key "%s" in not a valid setting.' % key
53
print 'The valid settings are %s' % self.valid_settings
55
def initialize(self,reseed = 1):
57
self.test_settings(self.settings)
59
sd = self.settings['rand_seed']; alg = self.settings['rand_alg']
60
if reseed: rv.initialize(seed = sd, algorithm = alg)
61
self.settings['seed_used'] = rv.initial_seed()
62
self._print('initializing... seed = %d' % self.settings['seed_used'])
63
self.crossover = self.pop.model_genome.crossover # get the crossover op from the first genome
64
self.pop.settings = self.settings #should these be shared?
65
self.size_pop(self.settings['pop_size'])
67
self.settings['crossover'] = string.split(str(self.crossover))[0][1:]
68
self.settings['selector'] = string.split(str(self.pop.selector))[0][1:]
69
self.settings['scaler'] = string.split(str(self.pop.scaler))[0][1:]
70
self.settings['genome_type'] = string.split(str(self.pop.model_genome))[0][1:]
71
# self._print(self.settings)
73
self.pop.initialize(self.settings);
74
self.stats = {'selections':0,'crossovers':0,'mutations':0,
75
'replacements':0,'pop_evals':1,'ind_evals':0}
76
self.stats.update(self.pop.stats)
77
self.step_time = timer() - b
80
self.settings['pop_size'] = s
83
def step(self,steps=1):
85
replace = int(self.settings['p_replace'] * len(self.pop))
86
p_crossover = self.settings['p_cross']
87
for st in range(steps):
89
for i in range(0,replace,2):
90
mom,dad= self.pop.select(2)
91
self.stats['selections'] = self.stats['selections'] + 2
92
if flip_coin(p_crossover):
94
bro,sis = self.crossover((mom,dad))
95
self.stats['crossovers'] = self.stats['crossovers'] + 2
96
self.pop.append(bro); self.pop.append(sis)
98
#crossover failed - just act as if this iteration never happened
100
#print 'crossover failure - ignoring and continuing'
102
self.pop.append(mom.clone());self.pop.append(dad.clone());
103
if replace % 2: #we did one to many - remove the last individual
105
self.stats['crossovers'] = self.stats['crossovers'] - 1
107
self.stats['mutations'] = self.stats['mutations'] + self.pop[sz:].mutate()
108
# for ind in self.pop[sz:]:
110
# self.stats['mutations'] = self.stats['mutations'] + m
115
del self.pop[sz:] #touch removed from del
117
self.pop.update_stats()
118
self.stats['pop_evals'] = self.stats['pop_evals'] + 1
119
self.gen = self.gen + 1
120
e = timer(); self.step_time = e - b
121
#print 'cross:',e1-b,'mutate:',e2-e1,'eval:',e3-e2,'rest:',e-e3
122
self.stats.update(self.pop.stats)
123
self.db_entry['best_scores'].append(self.stats['current']['max'])
129
self.p_dev = self.pop_deviation()
130
self.iteration_output()
131
while ( self.gen < self.settings['gens'] and
132
self.settings['p_deviation'] < self.p_dev ):
134
self.p_dev = self.pop_deviation()
135
self.iteration_output()
136
if(self.gen % self.settings['update_rate'] == 0):
138
self.update_dbase() #enter status prior to post_evolve in dbase
140
self.db_entry['run_time'] = timer() - b
142
def iteration_output(self):
143
output = ( 'gen: ' + `self.gen` + ' '
144
+ 'max: ' + `self.stats['current']['max']` + ' '
145
+ 'dev: ' + `self.p_dev` + ' '
146
+ 'eval time: ' + `self.step_time` + ' ')
147
self._print( output )
149
def pre_evolve(self): pass
150
def post_evolve(self): pass
151
def pop_deviation(self):
152
#calculate the std deviation across all populations as a percent of mean
153
scores = self.pop.scores()
154
denom = my_mean(scores)
155
if denom == 0.: denom = .0001 # what should I do here?
156
return abs(my_std(scores)/denom)
158
def init_dbase(self):
160
self.db_entry['settings'] = self.settings
162
self.db_entry['raw_time'] = t
163
self.db_entry['time'] = time.ctime(t)
164
self.db_entry['best_scores'] = [self.stats['current']['max']]
165
self.db_entry['stats'] = [copy.deepcopy(self.stats)]
166
self.db_entry['step_time'] = [self.step_time]
167
self.db_entry['optimization_type'] = string.split(str(self.__class__))[0][1:]
169
def update_dbase(self):
170
# self.db_entry['best_scores'].append(self.pop.best().score())
171
self.db_entry['stats'].append(copy.deepcopy(self.stats))
172
self.db_entry['step_time'].append(self.step_time)
174
def write_dbase(self):
175
"""This does not do file locking on NT - which isn't that big
176
a deal because at the most, two runs are going at a time, and
177
they are unlikely going to write at the same time (but could).
178
On NT, hopefully we're using the gdbm module which does automatic
181
if(self.settings['dbase'] != ''):
182
fname= self.settings['dbase']
184
if sys.platform == 'win32': pass
186
f = open(fname +'.lock','a')
187
fcntl.flock(f.fileno(),fcntl.LOCK_EX)
189
try: db = my_shelve.open(fname,'w')
190
except dberror: db = my_shelve.open(fname,'c')
192
if(len(keys) == 0): self.dbkey = `1`
196
try: gkeys.append(string.atoi(k))
197
except ValueError: pass
198
self.dbkey = `max(gkeys)+1`
199
print 'DB NAME: ', self.settings['dbase'], 'KEY: ', self.dbkey
200
db[self.dbkey] = self.db_entry
202
except: pass #if an error occured, we still need to unlock the db
203
if sys.platform == 'win32': pass
205
fcntl.flock(f.fileno(),fcntl.LOCK_UN)
208
if sys.platform == 'win32': pass
210
f = open('error.lock','a')
211
f.write(os.environ['HOST'])
214
else: "no dbase specified"
216
def _print(self,val, level = 1):
217
if(self.verbose >= level):
218
if type(val) == types.StringType: print val
220
pp = pprint.PrettyPrinter(indent=4)
226
valid_settings = galg.valid_settings + ['num_pops', 'migrants']
227
default_settings = galg.default_settings
228
default_settings['pop_size'] = 30; default_settings['num_pops'] = 4
229
default_settings['migrants'] = 2
232
def __init__(self,pop):
233
galg.__init__(self,pop)
234
# self.GAs = self.GAs + [galg(pop.clone())]
235
self.settings = copy.copy(self.default_settings)
237
def initialize(self, mode = 'serial'):
240
self.test_settings(self.settings)
242
sd = self.settings['rand_seed']; alg = self.settings['rand_alg']
243
rv.initialize(seed = sd, algorithm = alg)
244
self.settings['seed_used'] = rv.initial_seed()
245
self._print('initializing... seed = %d' % self.settings['seed_used'])
246
self.crossover = self.pop[0].crossover # get the crossover op from the first genome
247
self.pop.settings = self.settings
250
#set up my population to hold the best from each sub-pop
251
self.pop._size(0) #erase any current member of the pop
252
self.pop._size(self.settings['num_pops'])
253
self.crossover = self.pop[0].crossover
255
#extract the galg settings so we don't get a ton of warnings
256
#and create the sub ga_s
259
for key in galg.valid_settings:
260
sub_ga_settings[key] = self.settings[key]
261
for i in range(self.settings['num_pops']):
262
self.GAs.append(galg(self.pop.clone()))
263
self.GAs[i].settings = sub_ga_settings.copy()
265
self.settings['crossover'] = string.split(str(self.crossover))[0][1:]
266
self.settings['selector'] = string.split(str(self.pop.selector))[0][1:]
267
self.settings['scaler'] = string.split(str(self.pop.scaler))[0][1:]
268
self.settings['genome_type'] = string.split(str(self.pop.model_genome))[0][1:]
269
self._print(self.settings)
271
if mode[0] == 'p' or mode[0] == 'P':
273
sys.setcheckinterval(1000)
274
finished = sync.event()
275
bar = sync.barrier(len(self.GAs))
277
thread.start_new_thread(GA_initializer,(bar,finished,ga))
279
sys.setcheckinterval(10)
282
for ga in self.GAs: ga.initialize(reseed = 0)
285
self.pop[cnt] = ga.pop.best()
289
self.step_time = timer() - b
292
def init_stats(self):
293
#first set up the pops stats, since we don't officially initialize it.
294
self.pop.stats = {'current':{},'initial':{},'overall':{}}
295
self.pop.stats['selections'] =0; self.pop.stats['crossovers'] =0
296
self.pop.stats['mutations'] = 0; self.pop.stats['replacements'] = 0
297
self.pop.stats['ind_evals'] = 0
298
self.stats = self.pop.stats.copy()
300
def update_stats(self):
301
"""Gather statistics from the various populations to the mga's population.
303
sum_fields = ['selections','crossovers','mutations','replacements','ind_evals']
306
for field in sum_fields:
307
self.pop.stats[field] = self.pop.stats[field] + ga.stats[field]
308
s = s + ga.pop.scores().tolist()
310
self.pop.stats['current']['max'] = self.pop.best().score()
311
self.pop.stats['current']['avg'] = my_mean(s)
312
self.pop.stats['current']['min'] = min(s)
313
if len(s) > 1: self.pop.stats['current']['dev'] = my_std(s)
314
else: self.pop.stats['current']['dev'] = 0
315
try: self.pop.stats['overall']['max'] = max(self.pop.stats['overall']['max'],
316
self.pop.stats['current']['max'])
317
except KeyError: self.pop.stats['overall']['max'] = self.pop.stats['current']['max']
318
try: self.pop.stats['overall']['min'] = min(self.pop.stats['overall']['min'],
319
self.pop.stats['current']['min'])
320
except KeyError: self.pop.stats['overall']['min'] = self.pop.stats['current']['min']
322
self.pop.stats['pop_evals'] = self.GAs[0].stats['pop_evals']
323
self.stats.update(self.pop.stats)
326
def step(self,steps=1,mode = 'serial'):
327
for st in range(steps):
330
#self.pop._size(0) # used if we keep a single pop
331
if mode[0] == 'p' or mode[0] == 'P':
333
sys.setcheckinterval(100)
334
finished = sync.event()
335
bar = sync.barrier(len(self.GAs))
337
thread.start_new_thread(GA_stepper,(bar,finished,ga))
339
sys.setcheckinterval(10)
342
for ga in self.GAs: ga.step()
345
#replace the worst member of the local pop
346
self.pop[-1] = ga.pop.best()
348
#probabaly not the fast approach to things, but... keeps an itelligent pop
349
#for ind in ga.pop: self.pop.append(ind)
352
self.gen = self.gen + 1
353
e = timer(); self.step_time = e - b
355
self.db_entry['best_scores'].append(self.stats['current']['max'])
357
def pop_deviation(self):
358
"""calculate the std deviation across all populations"""
361
all_scores = all_scores + ga.pop.scores().tolist()
362
if len(all_scores) > 1:
363
denom = my_mean(all_scores)
364
if denom == 0.: denom = .0001 # what should I do here?
365
return abs(my_std(all_scores)/denom)
368
def evolve(self, mode = 'serial'):
370
self.initialize(mode)
372
self.p_dev = self.pop_deviation()
373
self.iteration_output()
374
while ( self.gen < self.settings['gens'] and
375
self.settings['p_deviation'] < self.p_dev ):
377
self.p_dev = self.pop_deviation()
378
self.iteration_output()
379
self.update_dbase() #enter status prior to post_evolve in dbase
381
self.db_entry['run_time'] = timer() - b
385
"""Migration moves members from one population to another. It takes
386
the best N individuals of GAs[0] and puts clones of them into
387
GAs[1], replacing the worst individuals. Likewise,
388
GAs[1] best replace GAs[2] worst. GAs[-1] best are moved
389
to GAs[0]. This 'stepping stone' migration of individuals allows
390
good ideas to move from one population to another, but still
391
allows the individual population to maintain som diversity.
393
if len(self.GAs) == 1: return
394
migrants = self.settings['migrants']
395
if migrants > self.settings['pop_size']:
396
migrants = self.settings['pop_size']
399
for i in range(migrants):
400
movers.append(self.GAs[0].pop[i])
401
for ga in self.GAs[1:]:
402
for i in range(migrants):
403
ga.pop[-i] = movers[i].clone() #replace the worst individual
404
movers[i] = ga.pop[i]
405
for i in range(migrants):
406
self.GAs[0].pop[-i] = movers[i].clone() #replace the worst individual
410
def GA_stepper(bar,finished,GA):
414
print 'thread ' + `thread.get_ident()` + 'time ' + `t2-t1` + ' sec.'
418
def GA_initializer(bar,finished,GA):
420
GA.initialize(reseed = 0)
422
print 'thread ' + `thread.get_ident()` + 'time ' + `t2-t1` + ' sec.'
added
removed
Lib/ga/algorithm.py
