Assignment 1
Question 1
1) (40%) Implement a simple GA Your GA - write it yourself! - should do mutation, crossover, and fitnessproportional reproduction. To convince yourself (and me or the TA) that your GA works, run the following simple problems:
a) OneMax: maximize Σi=1 l xi, xi ∈ {0, 1}. The best string obviously has all 1's. Use a string length l = 50.
b) SimpleMax: maximize (x1*x2*x3*x4*x5) / (x6*x7*x8*x9*x10), 1 ≤ xi ≤ 10.
Use ordinary positive integers (i.e. don't use a binary representation). While the solution is obvious, the GA doesn't know it 
Question 2
(60%) In this part of the assignment you are being asked to program a GA for the Traveling Salesman Problem (TSP). Use the simple GA from 1) as a starting point! The problem is as follows. You are given a set of cities (represented as points in the plane with X and Y co-ordinates). The goal is to find the shortest tour that visits each city exactly once, returning in the end to its starting point.
Finding the optimal tour is no simple matter. Given just 50 cities, there are more tours possible than the estimated number of atoms in the known universe! Even with the power of GA we are forced, by the difficulty of this NP-complete problem, to settle for «good» solutions instead of the optimum solution. The genetic material of the individuals in your GA's population should be an array or list of cities. If there are n cities, this array or list should have size n. If one uses normal crossover operators (uniform, 1-point, 2-point) and bit mutation, there will be many invalid tours in the population and short but invalid tours will likely come to dominate unless one devises an appropriate fitness penalty system which ensures that valid tours always have better fitness than invalid ones. For this assignment, we choose to prevent invalid tours from entering the population in the first place by using a variety of order-preserving crossover and mutation methods (see pdf).
