Courses/CS 461/Winter 2006/Chris Lemcke/Week 9
From CSWiki
[edit] Rubik's Cube Solver
My final project is a program that creates solutions for rubik's cubes using genetic programming. Each side is numbered 0-5, and each move is represented by a byte, value between 0 and 5, each move representing a clockwise rotation of the respective side. A solution is represented by a list of bytes, and crossover is implemented by selecting a random portion from two byte arrays, and swapping them, then putting the original arrays and the children back into the breeding pool. The program implements elitism by replacing the best solutions, and taking out the worst. The program utilizes a weighted roulette system for choosing the best solutions.
Fitness is determined by counting the number of correctly colored cells on a side, after a copy of the cube has been rotated in all the moves of the solution. In this way, the worst possible fitness is 6, for the center cells, and the maximum is 54. A more advanced solution would be to count the number of correctly positioned pieces. For example, if side 0 has a cell colored 0 on the side adjacent to side 1, it only counts if side 1 has a cell colored 0 in the same position adjacent to side 0. This would require a lot more calculations, though.
Due to the short-sighted fitness function, the program has a very hard time of getting fitness values above approximately 30. Despite this shortcoming, I consider this to be a successful simulation. It exhibits many of the common behaviors of genetic programming, such as similar "batches" of solutions arising, and bursts of progress followed by lulls in productivity.
