Sorting Networks

In this project, we will work with sorting networks, and it is the first time we will encounter "agents" in our study. (For more info on sorting networks, see the Mitchell textbook, p.21.)

To evaluate the fitness of a sorting network, we can't apply a simple function. Instead we subject the network to a series of tests to determine its fitness. In each test, we give the network a list of numbers to sort, and in some sense the network "comes alive" to try to sort the list.

This "testing" and "coming alive" will become a recurring theme in future projects.

1. Decide on a genetic encoding for a sorting network. The encoding can be thought of as the network's program.

2. Create a simulator that brings the network to life. It should be a function that takes in 1) a network's program and 2) a list of unsorted number, and returns the results of the network's work on the list.

3. Create a fitness function that uses the simulator above to test the sucessfulness of the network. You will probably want to test the network with several different inputs before deciding its fitness.

4. Run the GA to find a sorting network for lists of eight numbers. (Careful: the text discusses the problem for lists of 16 numbers, but we're working on a simpler problem.)

Extra Credit - Find a sorting network of fewer than 61 comparisons that will sort of list of 16 numbers. (70 points!)

Best Credit - Awarded to the student who finds the smallest sorting network for a list of 16 numbers. (10 points.)

Files for the project are available here.