This page is not finalized.

Do the following exercises from the text:

1. Exercise 4.1, all parts - Please give a one-or-two-sentence solution to each question.

2. Exercise 4.3.a - Use the AIMA hill-climbing and simulated annealing implementations for the travelling salesperson problem, not A*/MST or genetic algorithms as specified in the text. The problem is described briefly on page 74. As part of your solution, do the following:

   • Describe your state and action representations in your code documentation.
   • Configure your system so that you can build TSP worlds of any number of cities with random distances between them. The distances are symmetric, that is the distance from city A to city B is the same as that from B to A. The distances can be random and thus may not be geographically coherent in 2D space. You may assume that the cities are completely interconnected.
   • Explain which local search algorithm works better and why?

   This is a famously hard problem, so there is no clear way to determine the optimal answer; program your system to do its best and see how well it can do on some large, random city configurations.

Final project suggestion - Study some useful and/or interesting application of genetic algorithms (see Section 4.1.4) along with a more general analysis of evolution and computational evolution.

Checking in

Submit the files specified above in Moodle under homework 3. We will grade your work according to the following criteria:

• 25% - Exercise 1- Write brief but compelling answers to the given questions.
• 75% - Exercise 2 - Build correct, efficient and understandable code that solves the given problem.