Lab 2: Local Search
Due Sept. 22 by midnight

An example of a solution from a local search over 25 cities in the United States. It depicts a rough outline of the US. An example of a solution from a local search over 75 cities in North America

(left) Traveling salesperson problem tour found for 25 cities in the US. (right) Traveling salesperson problem tour found for 75 cities in North America.

Starting point code

Use Teammaker to form your team. You can log in to that site to indicate your partner preference. Once the lab is released and you and your partner have specified each other, a GitHub repository will be created for your team.

Introduction

The objectives of this lab are to:

You will implement the following local search methods:

You will need to modify the following python files:

LocalSearch.py

This week you will be implementing three different algorithms and running them on different instances of TSP problems. You can run all three local search algorithms using the program LocalSearch.py. Here are some examples of how to run LocalSearch.py (however they will all raise errors at first):

./LocalSearch.py HC coordinates/South_Africa_10.json
./LocalSearch.py SA coordinates/India_15.json
./LocalSearch.py BS coordinates/Lower_48.json 
The first example runs hill climbing to solve a TSP problem on the 10-city South Africa map. The second example runs simulated annealing to solve a TSP problem on the 15-city India map. The third example runs stochastic beam search on a TSP problem for a map of the lower 48 states in the United States.

NOTE: In order to execute python files directly (as shown above, without having to type python3), you'll need to make the file executable first. Type the following at the unix prompt to change the file's permissions:

    chmod u+x LocalSearch.py 
  

By default the best solution found will be saved to a file called map.pdf, and the parameters used for each search are defined in the file default_config.json. There are additional optional parameters you may add that allow you to load a non-default parameter file and/or save the resulting map to a non-default output file.

-config my_config.json -plot USA25_map.pdf  

Local search is typically used on hard problems where informed search is not viable (for example TSP is an NP-complete problem). Thus the search often runs for an extended period of time. It is important to keep the user informed of the search's progress. Each of your local search methods (HC, SA, BS), should print informative messages during the search execution. For instance, you should inform the user whenever the best value found so far is updated along with the current search step at that point.

Work on implementing your solution following the steps listed below.

1. Traveling Salesperson Problem

A traveling salesperson tour visits each of a collection of cities once before returning to the starting point. The objective is to minimize the total distance traveled. We will represent a tour by listing cities in the order visited. Neighbors of a tour are produced by moving one city to a new position in the ordering.

The class TSP, defined in the file TSP.py, represents instances of the traveling salesperson problem. Here are some useful methods within this class:

Instances of the TSP class are constructed by passing in the name of a JSON file specifying the latitude and longitude of locations that must be visited. Example JSON files are located in the coordinates directory.

Note that the TSP method _all_neighbors() begins with a single underscore. This is a python convention for indicating a 'private' method. Python doesn't actually distinguish between private and public class members, but the underscore lets programmers know that the method isn't intended to be called directly. In this case, your local search functions should not call this method. However, other methods within the class definition may call such private methods.

You should incrementally test your code as you develop it. The best way to do this is to add tests inside the if at the bottom of the TSP.py file:

  if __name__ == '__main__':
     ...

Once you have completed and tested the implementations in the TSP.py file you can move on to start implementing the local search methods.

2. Hill Climbing

In the file HillClimbing.py, you need to implement the function hill_climbing. To get started, replace the NotImplementedError with the following lines:
candidate = problem.random_candidate()
cost = problem.cost(candidate)
return candidate, cost
This will allow you to run hill climbing without generating errors:
./LocalSearch.py HC coordinates/United_States_25.json
Doing so will print the random candidate and its cost, and will also create a file that plots the tour in latitude/longitude coordinates. By default the plot is saved in a file called map.pdf.

Your next job is to implement the following hill climbing algorithm. This is a slightly different version than what we discussed in class. With some probability (determined by one of the parameters) it will take a random move. It will always execute the requested number of steps, keeping track of the best state found so far.

initialize best_state, best_cost
loop over runs
  curr_state = random candidate
  curr_cost = cost(curr_state)
  loop over steps
    if random move 
      curr_state, curr_cost = random neighbor of curr_state
    else
      neighbor_state, neighbor_cost =  best neighbor of curr_state
      if neighbor_cost < curr_cost:
         update curr_state, curr_cost
    if curr_cost < best_cost
       update best_state, best_cost   	  
       print status information about new best cost
return best_state, best_cost
Note that computing the cost of a tour takes non-trivial time, so whenever possible, you should save the value rather than making another function call.

Several of the parameters used above are specified in a config file. By default, LocalSearch.py reads default_config.json. You may want to copy this file and modify it:

cp default_config.json my_config.json
Then edit the "HC" portion of my_config.json to whatever defaults you would like to use. Then you can re-run the local search based on your own selections rather than the default ones.
./LocalSearch.py HC coordinates/South_Africa_10.json -config my_config.json

Once your hill climbing search is successfully finding good tours for the easier problems with fewer cities, you can move on to the next local search algorithm.

3. Simulated Annealing

SimulatedAnnealing.py is set up much like HillClimbing.py. Your next task is to implement the algorithm that we discussed in class:

initialize best_state, best_cost
loop over runs
  temp = init_temp
  curr_state = random starting state
  curr_cost = cost(curr_state)
  loop over steps
    neighbor_state, neighbor_cost = random neighbor of curr_state
    delta = curr_cost - neighbor_cost
    if delta > 0 or with probability e^(delta/temp)
       curr_state = neighbor_state
       curr_cost = neighbor_cost
    if curr_cost < best_cost # minimizing
       best_state = curr_state
       best_cost = curr_cost
       print status information about new best cost
    temp *= temp_decay
return best_state, best_cost

Edit the "SA" portion of the config file to set the defaults for simulated annealing. The init_temp specifies the starting temperature, and temp_decay gives the geometric rate at which the temperature decays. The runs and steps parameters have the same interpretation as in hill climbing: specifying how many random starting points simulated annealing should be run from, and how long each run should last.

Once your simulated annealing search is successfully finding good tours, you can move on to the next local search algorithm.

4. Beam Search

Beam search uses temperature and steps parameters similar to simulated annealing. However, instead of starting several separate runs, beam search maintains a population of candidates at each step. The pop_size parameter specifies the number of candidates.

Your final implementation task is to implement the stochastic beam search as discussed in class:

initialize best_state, best_cost
pop = initial population of pop_size random states
temp = init_temp
loop over steps
  generate max_neighbors random successors of each member of pop
  find overall best_neigh_cost and associated best_neigh_state
  if best_neigh_cost < best_cost
     best_state = best_neigh_state
     best_cost = best_neigh_cost                  
     print status information about new best cost
  generate probabilities for selecting neighbors based on cost
  pop = pop_size neighbors selected by random sampling w/ probs
  temp *= decay

Stochastic beam search considers neighbors of all individual candidates in the population and preserves each with probability proportional to its temperature score. It is recommended that you add a helper function for beam search that evaluates the cost of each neighbor and determines its temperature score, then randomly selects the neighbors that will appear in the next iteration. Remember to avoid excess calls to cost by saving the value whenever possible.

For the larger maps, the number of neighbors grows quite large, making it impractical to evaluate every neighbor of every candidate. Your helper function should therefore consider only a random subset of each individual's neighbors. The size of this subset is given by the max_neighbors parameter in the "BS" section of the config file.

A very useful python function for stochastic beam search is numpy.random.choice. This function takes a list of items to choose from, a number of samples to draw, and optionally another list representing a discrete probability distribution over the items. It returns a list of items that were selected. Here is an example:

import numpy.random
items = ["a", "b", "c", "d", "e"]
indices = list(range(len(items)))
probs = [0.1, 0.1, 0.2, 0.3, 0.3]
for i in range(5):
  choices = numpy.random.choice(indices, 10, p=probs)
  print(choices)

In this particular example, items "d" and "e" have the highest probability of being selected (30 percent chance each), and they are at indices 3 and 4. You can see in the sample results below that indices 3 and 4 are selected more often on average than indices 0, 1, and 2.

[3 2 2 2 4 3 4 4 4 4]
[3 4 2 4 4 4 4 4 4 3]
[4 4 4 3 4 2 3 0 3 2]
[4 2 3 0 1 0 3 4 4 2]
[4 0 1 4 4 2 4 0 4 3]

Unfortunately, numpy will treat a list of Tours as a multidimensional array, so it is better to select indices (as demonstrated above) rather than choosing from a list of neighbors directly.

Once your stochastic beam search is successfully finding good tours, you can move on to final step of comparing the three local search algorithms.

5. Comparing the three local search algorithms

After all three of your local search algorithms are complete and working correctly, do some experimental comparisons between the algorithms on the coordinates North_America_75.json. Be sure to spend a little time trying to tune the parameters of each algorithm to achieve its best results. If you find any particularly impressive tours, save them by renaming the file map.pdf to a more informative name.

In the file called summary.md, fill in the tables provided with your results and explain which local search algorithm was most successful at solving TSP problems. Did the outcome match your hypothesis that you voted on in class?

Submitting your code

To submit your code, you need to use git to add, commit, and push the files that you modified.