CSC 440 - Homework 3
SpinCycle
Overview
Arrange the 26 letters of the alphabet in a circle. Find the arrangement that lets
you spell the most words, where words can be found by traversing the circle
clockwise or counterclockwise.
Implementation
For this homework, you can use either Python or Java.
Objective Functions
You must implement two objective functions for this problem.
- Each letter in a word is worth 1 point. A letter can be part of multiple words.
- Words are worth their triangular number. So a word of length 1 is 1 points,
length 2 is 3 points, length 3 is 6 points, etc.
Neighborhood
You will separately investigate two neighborhoods for local moves in this problem
which were discussed in relation to TSP.
Local Search Algorithms
You will investigate three search algorithms for this problem.
- Hill Climbing with 10 random restarts
- Simulated Annealing, your choice of initial T, cooling schedule and halting criteria
- Genetic Algorithms
Crossover Operators
Withing the Genetic Algorithm, you must investigate one of the
following crossover operators. For extra credit, implement both and compare them.
- Order Crossover (OX)
- Edge Recombination (ER)
You may choose your own selection method and initialization
method from what we discussed in class. Your variation method should include
crossover and one or both of the mutation operators.
Results
In total, you will be running 8 different experiments for hill climbing and simulated
annealing.
| Alg |
Obj |
Nei |
| Hill Climbing |
1 point |
two-swap |
| Hill Climbing |
1 point |
two-interchange |
| Hill Climbing |
triangular points |
two-swap |
| Hill Climbing |
triangular points |
two-interchange |
| Simulated Annealing |
1 point |
two-swap |
| Simulated Annealing |
1 point |
two-interchange |
| Simulated Annealing |
triangular points |
two-swap |
| Simulated Annealing |
triangular points |
two-interchange |
For each local search experiment combination, your code should
output the score, the list of words found that generate that score, and the
number of configurations examined by your algorithm. For each
objective function, plot the scores found
versus the number of configurations with a scatter plot. Choose one
simulated annealing experiment
and plot the score of the solutions found within the search as a function of the
number of nodes explores so far.
Run your genetic algorithm implementation with both of the objective functions
described above, calculating the score, list of words
found that generate that score, and the number of configurations
examined by your algorith. Add your results to the scatter plots for Hill
Climbing and Simulated Annealing.
What to Hand In
To hand in your Homework 3 files, place your code in a directory on the cs server called csc440/hw3.
© Mark Goadrich 2010, Centenary College of Louisiana