import numpy as np import random as rd import math import matplotlib.pyplot as pl def energy(b,w): energy = -sum([w*b*bs for w,b,bs in zip(w,b,np.roll(b,1))]) return energy def e_min(w): return -sum(abs(e) for e in w) def flip_one(b): nb = b.copy() i = rd.randint(0,99) nb[i]= -nb[i] return nb def anneal_step(b,w,alpha): e = energy(b,w) nb = flip_one(b) ne = energy(nb,w) de = ne-e if de>0: p = math.exp(-alpha*t*de) else: p = 1 if p >= rd.random(): b,e = nb,ne return b def make_b(): return np.array([rd.choice((-1,1)) for i in xrange(100)]) def fitness(b): return math.exp(-beta*(energy(b,w)-e_min)) def weighted_choice(weights): rnd = rd.random() * sum(weights) for i, w in enumerate(weights): rnd -= w if rnd < 0: return i def mate(b1,b2): i = rd.randint(0,99) b3 = np.hstack((b1[0:i],b2[i:])) return flip_one(b3) b = np.array([rd.choice((-1,1)) for i in xrange(100)]) w = np.array([rd.gauss(0,1) for i in xrange(100)]) e_min =e_min(w) print "e_min",e_min """ init_b = b.copy() alpha = .1 trace1 = [] b = init_b.copy() for t in xrange(5000): b = anneal_step(b,w,alpha) trace1.append(energy(b,w)) print "e after 100 steps with alpha .1", energy(b,w) b = init_b.copy() alpha = .01 trace01 = [] for t in xrange(5000): b = anneal_step(b,w,alpha) trace01.append(energy(b,w)) print "e after 100 steps with alpha .01", energy(b,w) b = init_b.copy() alpha = .001 trace001 = [] for t in xrange(5000): b = anneal_step(b,w,alpha) trace001.append(energy(b,w)) print "e after 100 steps with alpha .001", energy(b,w) """ #g a search init_pop = [make_b() for i in xrange(100)] pop= init_pop beta = 10 trace_ga_1 = [] for t in xrange(300): fit = [fitness(i) for i in pop] min_e_pop = energy(pop[fit.index(max(fit))],w) trace_ga_1.append(min_e_pop) newpop = [mate(pop[weighted_choice(fit)],pop[weighted_choice(fit)]) for i in xrange(100)] pop = newpop print "e after g a search steps with alpha .1", trace_ga_1[-1] #g a search init_pop = [make_b() for i in xrange(100)] pop= init_pop beta = 1 trace_ga_01 = [] for t in xrange(300): fit = [fitness(i) for i in pop] min_e_pop = energy(pop[fit.index(max(fit))],w) trace_ga_01.append(min_e_pop) newpop = [mate(pop[weighted_choice(fit)],pop[weighted_choice(fit)]) for i in xrange(100)] pop = newpop print "e after g a search steps with alpha .1", trace_ga_01[-1] #g a search init_pop = [make_b() for i in xrange(100)] pop= init_pop beta = .1 trace_ga_001 = [] for t in xrange(300): fit = [fitness(i) for i in pop] min_e_pop = energy(pop[fit.index(max(fit))],w) trace_ga_001.append(min_e_pop) newpop = [mate(pop[weighted_choice(fit)],pop[weighted_choice(fit)]) for i in xrange(100)] pop = newpop print "e after g a search steps with alpha .1", trace_ga_001[-1] #pl.plot(trace1,c="g") #pl.plot(trace01,c="r") #pl.plot(trace001,c="y") pl.plot(trace_ga_1,c="g") pl.plot(trace_ga_01,c="r") pl.plot(trace_ga_001,c="y") pl.show()