Description
In this Assignment you will be implementing simple hill climbing and steepest descent hill climbing for the travelling salesman problem. Hill Climbing is a heuristic search used for mathematical optimisation problems in the field of Artificial Intelligence. So, given a large set of inputs and a good heuristic function, the algorithm tries to find the best possible solution to the problem in the most reasonable time period. This solution may not be the absolute best(global optimal maximum) but it is sufficiently good considering the time allotted. The definition above implies that hill-climbing solves the problems where we need to maximise or minimise a given real function by selecting values from the given inputs. A great example of this is the Travelling Salesman Problem where we need to minimise the distance travelled by the salesman. Inside src/data LEA you will find two input files (cities throughout the world along with their locations) for this weeks programming assignment. • Solve the Traveling-Salesperson problem by implementing random-restart hill-climbing. You can assume kartesian distances between the cities. • You can use the 49_cities.txt to test your program. Submit the final results on all cities (cities_full.txt). • Russel and Norvig describe the steepest-ascent/descent version of hill climbing: Given a state, all possible sucessors are being evaluated and the one with the highest/lowest objective function is chosen as the new state. The simple hill climbing variant is: Start evaluating the sucessors of your current state and as soon as any better one is found, take is as the new state and repeat. (For more information see variants here: https://en.wikipedia.org/wiki/Hill_climbing). • The goal of your agent is to find a cycle (a roundtrip) which visits every city once, while traveling the minimal possible distance. For more information see: https://en.wikipedia.org/wiki/ Travelling_salesman_problem. • Do random-restart hill-climbing atleast 5 times in both your implementations and for every 2000 iterations. This means that you restart each hill-climbing algorithm after every 2000 iterations and run until 10000 iteration to report the best result. • Generate plots of results for with iterations from 1 to 10000. (Hint: Use matplotlib for plotting) Look at the sample plot in results/plots to get an idea of how the plot should look like Coding Guidelines ● Please use .py files provided to code your solutions in Python 3.5 or above. ● A minimalistic template is provided so that you can organize your ideas and put them into the appropriate functions. ● Please fill out the docstrings (function args and return value type and description) after implementation. ● Please fill out the requirements.txt if you are using any third party python libraries (Eg: numpy). ● Please add travis build status label in markdown format at the top of the README.md. Follow the instructions https://docs.travis-ci.com/user/status-images/ ● Please add any extra functions if needed in the helper.py. ● Do not clutter your code and try to be more Pythonic in coding. ● Kindly use meaningful identifiers for variable/function/class names. Also add comments to help us easily evaluate your code. Deliverables ● Please store the results of simple hill climbing and steepest ascent hill climbing with restarts in a manually created output.txt file for both the cities.txt files. ● The txt file should compulsarily contain cost after every 2000 iteration, the best sequence, best cost and the time taken by the search algorithm. (Other details are optional) ● Plots should be generated in results/plots. Kindly name your plots as follows Hill_climbing_simple_.png or Hill_climbing_steepest_descent_.png
