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()