[globalrev]

I just did this because I got inspired. What does it count as, genetic programming? It uses naive mutation and crossover(don't know if they qualfiy as real crossover and mutation) and a simple fitness function. It is fairly pointless since all it does is find a list with ones but it does so in just around 400 generations while random guessing takes forever.

  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

[yters]

Good GA, but for genetic programming, you need to come up with a program representation and then evolve something in that space that spits out a solution. V. simple in lisp, given the code/data are the same thing. You could try the same thing with python's string eval, but it'll be trickier to define the lexemes and what qualifies as a feasible program.

Here's Koza's material from his Stanford class: http://www.genetic-programming.com/coursemainpage.html

[randomwalker]

Dude, pastebin? :-)

Yeah, I guess this is GA alright. Your crossover is not right -- it should "cross over" at one point, not flip flop at each location :-)

[Edit] And there's a lot of in-breeding going on! You want to keep 10-20 sequences from each generation, not just 2.

[yters]

Crossing over at one point is not as effective as an even crossover, since it is actually equivalent to an even crossover with one static and one dynamic point. Thus, building blocks in the middle are more likely to be disrupted than building blocks on the ends.

That being said, his approach is also a viable GA operator. It is called a uniform crossover. But really, to qualify as a GA, his solution only needs some kind of variation, mutation, and selection.