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.

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.

Crossover Operators

Withing the Genetic Algorithm, you must investigate one of the following crossover operators. For extra credit, implement both and compare them. 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