Spring 2010»CSCI 470 Homework 5

CSCI 470 Homework 5

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)

Purpose

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.

Assignment

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

Examples

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

Genetic Algorithm (GA) Example

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

Genetic Programming (GA) Example

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

Documentation

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.

Submission

  1. Submit a README.txt file. Include your names, class, homework assignment, date. Also discuss the following:
    1. 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.).
    2. How your genotype models a problem solution.
    3. How your fitness function evaluates the worth of a genotype/solution.
    4. How to run your program.
    5. 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).
  2. Your source code, named something-appropriate.py, fully documented and tested. This program should import NEvMusE_ga.py or NEvMusE_gp.py.
  3. All other necessary files (e.g., NEvMusE_ga.py, NEvMusE_gp.py, share.py, etc.). Do not modify the latter.

Grading

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