due Friday, December 10
Develop a program that uses genetic algorithms to optimize two-dimensional packing problems. You can write the program using any language so long as you can provide me with an executable and the source code. (For Java, you can provide me with just the source.) I will need to be able to run your program myself.
Your program should open the file C:\tmp\packing.dat as its input file. (Note that Java will render this pathname as C:/tmp/packing.dat.) The data file specifies a series of sequences of 10 jigsaw pieces to be packed into as small an area as possible. Each piece is comprised of a subset of the cells of a 3x3 grid. A piece is specfied by a 9-character string of ones and zeroes. The first three characters represent the top row of the 3x3 grid, the next three represent the middle row, etc. Let a row be represented by the sequence "abc". a=1 indicates that the leftmost square in that row is occupied, b=1 indicates the same for the center square, and c = 1 indicates the rightmost square. Thus, the string "100100110" represents the piece
The input file consists of 3 lines, each line representing one packing problem. A line consists of 10 piece descriptions, each piece description delineated by whitespace.
The goal of your program is to provide, for each packing problem, an arrangement of the 10 pieces, on a grid, that minimizes the area of the smallest rectangle that encloses all 10 pieces. The pieces may be rotated, but may not overlap.
Thus, the pieces "100100110", "000011011", "110100100":
can be minimally packed via any orientation of:
(There are other optimal packings for these as well. Can you think of any?)
For each problem, your program should print the input pieces that will be packed. You can do this via graphics, or a simple text-based scheme. The three pieces above would be rendered:
0-- --- 22- 0-- -11 2-- 00- -11 2--
Then your program should run a GA to attempt to find a good packing. After the run has completed, print out the best packing identified, using a similar scheme. Thus, the text-based approach would yield:
0112 0112 0022
You should also indicate the area of the smallest enclosing rectangle. The area of the sample above would be 12 (3x4).
Hint:
You will need to come up with a binary representation of possible solutions. One possibility: the binary string could be comprised of 10 substrings, one for each piece. Each substring would somehow encode the location & orientation of the corresponding piece. Another possibility: each string might represent an ordering of the 10 pieces, and an orientation of each. Your packing could be generated a la the old computer game Tetris: "drop" the pieces into a "bin". There are many other possible encoding schemes.
You will probably have the most success if you use larger populations (say 1000 or more individuals per population.) Keep your mutation rate fairly low (no more than 5% of each generation should be generated by mutation.) You should have some straight reproduction (copying individuals directly from a generation into the next.)
The AI Award Program Continues:
I will award extra credit of a half-grade addition to the final exam grade to the program that comes up with the best packing, averaged over the three test cases.
In addition to submitting your program electronically, you must also submit a one page written report, in class, explaining whether you think that GA is a good approach to solving this problem. Please explain why or why not.
Go to my homework submission page, http://caddis.acad.emich.edu/~hwmatt/student, and follow the directions.