Matt Owen

source code for "files/robot birds and robot bees/genetics.py"

return to portfolio
  1.  # Matt
  2.  # Genetic Algorithm
  3.  
  4.  # imports # # #
  5.  # # # #
  6.  
  7.  from math import ceil, log
  8.  from matrix import matrix
  9.  import random
  10.  
  11.  
  12.  # binary vectors, K-matrix, permutation matrix # # #
  13.  # # # #
  14.  
  15.  class binaryvector:
  16.   def __init__(s, n, l=False):
  17.   s._n = n
  18.  
  19.   if l == False: s._l = int(log(n,2))+1
  20.   else: s._l = l
  21.  
  22.   s._v = s.vector()
  23.   s._m = sum(s._v)
  24.  
  25.   def vector(s):
  26.   n = s._n
  27.   v = []
  28.   while n:
  29.   v += [n%2]
  30.   n /= 2
  31.   if s._l == False: return v
  32.   return v + ([0] * (s._l - len(v)))
  33.  
  34.   def __getitem__(s, i): return bv._v[i]
  35.  
  36.   def __repr__(s): return ''.join(map(str, s._v))
  37.  
  38.  
  39.  def k_matrix(k, l):
  40.   c = 0
  41.   lis = []
  42.   bv = binaryvector(k)
  43.   m = matrix(ncols=bv._m, nrows=l)
  44.   for i in range(len(bv._v)):
  45.   if bv[i] == 1:
  46.   m[i,c] = 1
  47.   c += 1
  48.  
  49.   return m
  50.  
  51.  
  52.  def permutation_matrix(n, k):
  53.   m = matrix(ncols=n, nrows=n)
  54.   for i in range(n):
  55.   for j in range(n):
  56.   if i^j == k: m[i,j] = 1
  57.   return m
  58.  
  59.  
  60.  # create a set of chromosones and a map from [0, 2**l-1] -> [0,l]**l
  61.  class omega:
  62.   def __init__(s, k, l):
  63.   s._l = l
  64.   s._K = k_matrix(k=k, l=l)
  65.   s._bv = binaryvector(n=k, l=l)
  66.   s._m = s._bv._m
  67.   s._perm = permutation_matrix(n=s._m+1, k=s._m)
  68.   s._set = set()
  69.   s._hash = {}
  70.  
  71.   def points(s):
  72.   print s._K
  73.   for k in range(2**s._m):
  74.   bv = binaryvector(k, l=s._m)
  75.   yield ''.join(map(str,matrix.col(s._K * bv._v)))
  76.  
  77.  
  78.  # crossover # # #
  79.  # # # #
  80.  
  81.  def uniform_crossover(i,l): return 2**-l
  82.  
  83.  def one_point_crossover(i,l):
  84.   try:
  85.   k = log(i+1,2)
  86.   if 0 < k < l and k == int(k): return 1./(l-1)
  87.   except: return 0
  88.   return 0
  89.  
  90.  class crossover:
  91.   def __init__(s, xi, l, f):
  92.   s._l = l
  93.   s._xi = max(min(xi, 1),0)
  94.   s._crossover = [f(i=i, l=s._l) for i in range(2**s._l)]
  95.  
  96.   def __getitem__(s, i):
  97.   if i > 0: return s._xi * s._crossover[i]
  98.   elif i == 0: return 1 - s._xi + s._xi * s._crossover[0]
  99.   return False
  100.  
  101.   def __repr__(s):
  102.   st = '(Xi = ' + str(s._xi) + ', c = ' + str(s._crossover) + ', length = ' + str(s._l)
  103.   return st + ')'
  104.  
  105.  
  106.  # mutation # # #
  107.  # # # #
  108.  
  109.  def mutation_vector(mu, l):
  110.   v = []
  111.   for i in range(2**l):
  112.   s = binaryvector(i, l=l)._m
  113.   v += [mu**(s) * (1-mu)**(l-s)]
  114.   return v
  115.  
  116.  
  117.  # mix # # #
  118.  # # # #
  119.  
  120.  def child_probability(x,y,z,mu,xi,l):
  121.   # total
  122.   t = 0
  123.  
  124.   # recall m(x,y,z) = m(x^z,y^z,0)
  125.   x,y = x^z,y^z
  126.  
  127.   # helper classes
  128.   vmu = mutation_vector(mu,l)
  129.   X = crossover(xi=xi, l=l, f=one_point_crossover)
  130.  
  131.   for j in range(2**l):
  132.   for k in range(2**l):
  133.   notk = (2**l-1)^k
  134.   t += vmu[j] * (X[k] + X[notk])/2. * int(x & k ^ notk & y ^ j == 0)
  135.  
  136.   return t
  137.  
  138.  def mix_matrix(xi, mu):
  139.   l = xi._l
  140.   m = matrix([], ncols=2**l, nrows=2**l)
  141.   for x in range(2**l):
  142.   for y in range(2**l):
  143.   m[x,y] = child_probability(x,y,0,mu=mu,xi=xi,l=l)
  144.   return m
  145.  
  146.  
  147.  
  148.  # program start # # #
  149.  # # # #
  150.  
  151.  X = crossover(xi=.7, l=3, f=one_point_crossover)
  152.  mu = mutation_vector(mu=.3, l=3)