CS 171, Spring 2007
Prof. Max Welling
Project 1: Genetic Algorithm
Due: Friday May 18
Project Description
Implement a genetic algorithm to solve the following problem:
Consider filling a MxN rectangle with the numbers 1...MN in some random order.
For example:
Each number has either 4 neighbors or 3 neighbors (on the edge) or 2 neighbors (in a corner).
The total cost is the sum of the absolute differences between all neighboring pairs of numbers.
We’ll give you a big problem after the deadline and you willhave a couple of days to find the best solution you can find.The lowest cost solution wins.
If you come up with a fancy alternative to the genetic algorithm, you may requestto implement that as an alternative to solve the same problem.
To construct the initial population of completed states, you can initialize the rectangle however you want. For example, you might generate completely random initial states, use a specific ordering of the numbers, or use some other algorithm to create the initial states.
Your program will accept the M and N values on the command line where N follows M, e.g., java GeneticAlgorithm 2 5, where M=2 and N=5. Your program will output the solution to a test file (solution.txt) and the total cost to the standard output (screen).
A text file with your solution should contain just the data. In other words, it should have M rows separated by a new line character ( \n ) and each one of the N columns should be separated by a comma.
You can use the following programming languages: Java, C#, perl or matlab. We will compile (if necessary) and run your code, therefore, make sure you are not using any non-standard libraries. For example, if you write your program in Java, it should use only objects/function supported by the JRE.
Your algorithm has to run on Windows XP or, if you wrote your code under linux/unix/bsd, it should run on ICS unix computers.
Submission Instructions
Submit all of your code and a report. In a report, describe what algorithm you have implemented and how to run your code. The report is required to be in a doc, txt, or a pdf format.
Zip all of your code and report in a zip file titled <lastname_studentid>.zip (e.g. smith_12345678.zip). Upload your zip file to EEE dropbox named “Project 1” by the deadline.