globalrev

  from __future__ import division
  import matplotlib.mlab as M
  import matplotlib.pyplot as plt
  import random as R
  
  def crossover(a, b):
      new = []
      for x,y in zip(a,b):
          if R.random() > 0.5:
              new.append(x)
          else:
              new.append(y)
      return new

  def mutate(xs):
      xs[int(R.uniform(0, len(xs)))] = int(R.uniform(1, 10))
      return xs

  def fitness(xs, goal):
      summa = 0
      for x,y in zip(xs, goal):
          summa += abs(x-y)
      return summa, xs, True if summa == 0 else False

  def nFittest(xs, goal, n=2):
      fittest = sorted(fitness(x, goal) for x in xs)[:n]
      if fittest[0][2] :
          return fittest[0]
      elif fittest[1][2]:
          return fittest[1]
      else:
          return fittest

  def init(fields, n):
      return [[int(R.uniform(1,10)) for x in     xrange(fields)] for y in xrange(n)]

  def newGen(a,b,n):
      next = [crossover(a,b) for x in xrange(n)]
      mutated = []
      for x in next:
          if R.random() > 0.9: mutated.append(mutate(x))
          else: mutated.append(x)
      return mutated

  def run(printing=True):
      n = 0
      first = init(15, 10)
      while n < 1000000:
          n += 1
          next = nFittest(first,   [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 2)
          if type(next) == tuple: break
          first = newGen(next[0][1],next[1][1], 10)
      if printing:
          print "Nbr of generations: ", n
          print next
      return n, next

  def plot():
      trials = [run(False)[0] for x in range(100)]
      print "Done trials"
       averages = [sum(trials[:x]) / len(trials[:x])\
                  for x in xrange(1,len(trials)+1)]
      print "Done averages"
      plt.plot([x for x in xrange(len(averages))],   averages, 'ro')
      plt.axis([1, 100, 0, 1000])
      plt.show()

  def test():
      goal = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
      c=0
      while 1:
          c += 1
          x = [int(R.uniform(1,10)) for y in range(15)]
          if sum(x) == 15: break
          if c % 10000 == 0: print c
      print x