Program 2: Genetic Algorithms

Due Date

This assignment is due at the beginning of the lecture on Friday, October 22nd.

Partners

You may work with (at most) one other person on this assignment. If you work with a partner, submit one solution with both of your names on it.

General Requirements

You must solve this problem by implementing the genetic algorithm that is described on page 119 (with one minor modification) of the course textbook. The minor modification is to retain the best individual from the previous generation in the current generation. This is known as elitism. The implementation must be in Common Lisp and/or CLOS.

Constraint Satisfaction

A variety of problems (mostly resource allocation) can be described in terms of precedence or ordering constraints, e.g., A > B means "A comes before B" or "A is more important/preferred over B". This is inherently a decision problem: Given a list of tasks and a list of constraints, is there a total ordering of tasks that preserves the constraints? This is called finding a feasible solution. It can also be re-phrased as an optimization problem: Given a list of tasks and a list of constraints, what ordering of tasks violates the fewest constraints? For purposes of this class, we will be treating this as an optimization problem.

Sample Input

You must define a function named evolve-solution. The function has five parameters that appear in the order below.

  1. number-of-tasks corresponds to the number of tasks that need to be performed. The tasks will be numbered from 0 through number-of-tasks - 1.
  2. constraints corresponds to the constraints of the problem. This parameter is a list of sublists. Each sublist contains two task numbers where the first number in the list is a task that must be completed before the second. For example, in the sample call below, task 0 must be completed before task 3 can begin.
  3. population-size is the number of individuals that are in one generation of the genetic algorithm.
  4. number-of-generations is the number of generations that the genetic algorithm should be run for.
  5. mutation-rate is a number between 0.0 and 100.0 that indicates the percentage of the time that the mutation operator should be applied.
(evolve-solution 5 '((0 1)(0 3)(2 1)(1 3)(4 3)) 20 50 1.5)

Required Output

The evolve-solution function should return the ordering of the tasks that it finds with the smallest number of constraint violations. For example, '(0 2 1 4 3) below. In addition, match the output format below: 

Constraint Satisfaction
-----------------------

Number of tasks: 5
Constraints: '((0 1)(0 3)(2 1)(1 3)(4 3))
Population Size: 20
Number of Generations: 50
Mutation Rate: 1.5

The number of constraint violations is 0
The ordering of the tasks is '(0 2 1 4 3)

What to Submit

  1. A printout of the source code that you produce.
  2. A printout of your program running on the this input file.
  3. An e-mail of your solution to John at paxton@cs.montana.edu on or before Friday, October 22nd at noon.

Grading

Valid XHTML 1.0!