**Assigned Date**: Thursday, Apr. 15, 2010**Due Date**: Tuesday, May 4**Due Time**: 11:45am

Last modified on April 30, 2010, at 09:14 AM (see updates)

This assignment focuses on developing an evolutionary programming application.

This is a pair-programming assignment (i.e., you **may** work with a partner). **You may discuss the assignment only with your partner or the instructor.**

Write an evolutionary algorithm. This application may span any area of interest, but its results should have some significance/interest (as opposed to the toy examples shown below). You may use a genetic-algorithm (GA) or genetic-programming (GP) approach (one or the other).

To do so, you should import (but NOT modify) the provided GA or GP code (NEvMusE_ga.py or NEvMusE_gp.py). Notice that the latter also requires share.py. Again, you should not modify the provided files.

Be prepared to demo your application in class. (No late days may be applied on this assignment.)

The following have been adapted from the Pyro evolutionary algorithm code repository.

This example requires NEvMusE_ga.py.

# maxSumGa.py

#

# Sample code for evolving a list of 10 integers (between 0 and 3), whose sum is as close to 30 as possible.

#

from NEvMusE_ga import *

class MaxSumGA(GA):

# overload fitness function

def fitnessFunction(self, i):

return max(sum(self.pop.individuals[i].genotype), 0)

# overload termination condition

def isDone(self):

return self.pop.bestMember.fitness > 30

# instantiate class

ga = MaxSumGA( Population(20, Gene, size=10, mode='integer',

verbose=1, elitePercent = .1,

max = 3, maxStep = 2, min = 0,

crossoverPoints = 1),

mutationRate=0.1, crossoverRate=0.5, verbose=1, maxGeneration=50)

# evolve solution

ga.evolve()

#

# Sample code for evolving a list of 10 integers (between 0 and 3), whose sum is as close to 30 as possible.

#

from NEvMusE_ga import *

class MaxSumGA(GA):

# overload fitness function

def fitnessFunction(self, i):

return max(sum(self.pop.individuals[i].genotype), 0)

# overload termination condition

def isDone(self):

return self.pop.bestMember.fitness > 30

# instantiate class

ga = MaxSumGA( Population(20, Gene, size=10, mode='integer',

verbose=1, elitePercent = .1,

max = 3, maxStep = 2, min = 0,

crossoverPoints = 1),

mutationRate=0.1, crossoverRate=0.5, verbose=1, maxGeneration=50)

# evolve solution

ga.evolve()

This example requires NEvMusE_gp.py and share.py.

# piGp.py

#

# Sample code for evolving a GP expression that calculates PI (3.14...).

#

from NEvMusE_gp import *

class PI_GP(GA):

def __init__(self, cnt, **args):

GA.__init__(self, GPPopulation( cnt, GPGene, **args), **args)

# overload fitness function

def fitnessFunction(self, pos):

try:

val = self.pop.individuals[pos].eval_tree(values)

except: # catch division by zero and assign low fitness

#print "Caught division by zero"

val = 0

score = abs(val - pi)

return max(pi - score, 0)

# overload termination condition

def isDone(self):

return abs(pi - self.pop.bestMember.fitness) < 0.001

# define GP operators...

share.operators = ['+', '-', '*', '/']

#... how many operands they require...

share.operands = {'+' : 2,

'-' : 2,

'*' : 2,

'/' : 2}

#... and their meanings

share.function = {}

share.function['+'] = lambda p1,p2: p1+p2

share.function['-'] = lambda p1,p2: p1-p2

share.function['*'] = lambda p1,p2: p1*p2

share.function['/'] = lambda p1,p2: p1/p2

share.terminals = ['0.1', '0.2']

values = {'0.1' : 0.1, '0.2' : 0.2}

# instantiate class

gp = PI_GP(cnt = 25, bias = .5, elitePercent = 0.1, verbose = 1, crossoverRate = 0.5, mutationRate = 0.5)

# output the initial population (out of curiocity)

for i in range(len(gp.pop.individuals)):

print i, ": ", gp.pop.individuals[i].toString()

# evolve solution

gp.evolve()

#

# Sample code for evolving a GP expression that calculates PI (3.14...).

#

from NEvMusE_gp import *

class PI_GP(GA):

def __init__(self, cnt, **args):

GA.__init__(self, GPPopulation( cnt, GPGene, **args), **args)

# overload fitness function

def fitnessFunction(self, pos):

try:

val = self.pop.individuals[pos].eval_tree(values)

except: # catch division by zero and assign low fitness

#print "Caught division by zero"

val = 0

score = abs(val - pi)

return max(pi - score, 0)

# overload termination condition

def isDone(self):

return abs(pi - self.pop.bestMember.fitness) < 0.001

# define GP operators...

share.operators = ['+', '-', '*', '/']

#... how many operands they require...

share.operands = {'+' : 2,

'-' : 2,

'*' : 2,

'/' : 2}

#... and their meanings

share.function = {}

share.function['+'] = lambda p1,p2: p1+p2

share.function['-'] = lambda p1,p2: p1-p2

share.function['*'] = lambda p1,p2: p1*p2

share.function['/'] = lambda p1,p2: p1/p2

share.terminals = ['0.1', '0.2']

values = {'0.1' : 0.1, '0.2' : 0.2}

# instantiate class

gp = PI_GP(cnt = 25, bias = .5, elitePercent = 0.1, verbose = 1, crossoverRate = 0.5, mutationRate = 0.5)

# output the initial population (out of curiocity)

for i in range(len(gp.pop.individuals)):

print i, ": ", gp.pop.individuals[i].toString()

# evolve solution

gp.evolve()

All programs that you complete in your career as a student and as a professional developer should be fully documented. Obviously, you should comment any variable, obscure statement, block of code, method, and class you create. Your comments should express *why something is being done*, as opposed to how – the how is shown by the code. Also, include opening comments as specified in the previous assignment.

The above applies only to the code you **write** and NOT NEvMusE_ga.py or NEvMusE_gp.py.

- Submit a
**README.txt**file. Include your names, class, homework assignment, date. Also discuss the following:- What problem your application solves (or what task it performs). Provide a thorough explanation of problem's/task's importance. Add references (e.g., research papers, Wikipedia articles, etc.).
- How your genotype models a problem solution.
- How your fitness function evaluates the worth of a genotype/solution.
- How to run your program.
- Any known limitations of your application (e.g., if/when it crashes, or something not implemented, etc.). You get more points by knowing and documenting your program's limitations (in the README file, and in your code).

- Your source code, named
*something-appropriate*.py, fully documented and tested. This program should import**NEvMusE_ga.py**or**NEvMusE_gp.py**. - All other necessary files (e.g.,
**NEvMusE_ga.py**,**NEvMusE_gp.py**,**share.py**, etc.). Do not modify the latter.

Your grade will be based on how well you followed the above instructions, and the depth/quality of your work.

(Printable View of http://www.cs.cofc.edu/~manaris/?n=Spring2010.CSCI470Homework5)