Skip navigation

So as I mentioned in my last post, I am currently taking a discrete optimization class from Coursera.  It is a pretty challenging class, especially because I have never taken an algorithms class before (I majored in Conservation and Resource Studies in college).  I have been fairly successful in implementing some tried and true algorithms to solve some of the problem sets, but I have been having a lot of difficulty getting an understanding of the performance details of the various algorithms.  My typical routine has been to write up a few solutions to each problem, and use the run-time, solution score, and my (limited) intuition to try and improve the implementations.

In yesterday’s post I discussed a little plotting function that I wrote to help visualize my implementations to the Traveling Salesman Problem (TSP).  Today, I am going to talk about using a line profiler to get detailed feedback on the performance of your code.  I found this blog post to be very helpful in navigating the various options for performance analysis.

For the (TSP) problem, I wrote up a Tabu Search algorithm, which is a type of Local Search algorithm, that uses ‘short term memory’ to ensure that old solutions are not revisited.  While I have successfully implemented a version of the algorithm in python, I am fairly certain that I am glossing over a few key implementation details as my algorithm is not performing nearly as well as it should.  A good way to get detailed feedback on the algorithm’s performance is to use the line profiler package.  It is extremely easy to use and it provides valuable feedback on your code’s performance.  You simply add the @profile decorator to any function in your program that you want feedback on, then run a python executable at the command line (see the source blog post for details).  I threw in the profile decorator on my main Tabu function and got the following output:

Line #      Hits         Time  Per Hit   % Time  Line Contents
    85                                               @profile
    86                                               def search(cities, candidate_list_size, max_iter):
    87         1        13160  13160.0      0.1  	current_vector = random_permutation()
    88         1          839    839.0      0.0  	current_cost = calc_cost(current_vector)
    89         1            3      3.0      0.0  	tabu_list = []
    90         1            5      5.0      0.0  	path = [current_vector[:]]
    91     10001        30512      3.1      0.3  	for i in range(0, max_iter):
    92     10000      9332657    933.3     99.1  	    new_perm, new_cost, tabu_list = generate_candidates(current_vector, tabu_list)
    93     10000        37371      3.7      0.4  	    if new_cost < current_cost:
    94                                           		#path.append(new_perm[:])
    95        11           53      4.8      0.0  		current_vector = new_perm[:]
    96        11           34      3.1      0.0  		current_cost = new_cost
    97         1            4      4.0      0.0  	return current_vector, current_cost, path

The output of the profiler displays Hits (which is the number of times a line of code was run), Time Per Hit, and % Time. Looking at the output from the profiler, it looks like the line of code that uses the most resources is the generate_candidates function call in the main for loop (which makes sense, as the search function is basically a for loop over the generate_candidates function . So in order to take this analysis further, I added a profile decorator to the generate_candidates function and displayed the results below.

Line #      Hits         Time  Per Hit   % Time  Line Contents
    74                                               @profile
    75                                               def generate_candidates(best_perm, tabu_list):
    76     10000        37295      3.7      0.4  	perm = best_perm[:]
    77     10326        29927      2.9      0.3  	while True:
    78     10326       426132     41.3      4.7  	    perm = two_opt(best_perm)
    79     10326        73413      7.1      0.8  	    if perm not in tabu_list:
    80     10000        95461      9.5      1.1  		tabu_list = tabu(perm, tabu_list)
    81     10000        28268      2.8      0.3  		break
    82     10000      8269102    826.9     92.0  	perm_cost = calc_cost(perm)
    83     10000        29902      3.0      0.3  	return perm, perm_cost, tabu_list

As you can see from the output of the profiler on the generate_candidates function, the bottleneck appears to be the calc_cost function. This was not surprising as cost functions, which are used to measure the effectiveness of your solution, can be expensive to compute but are an important tool in providing your algorithm feedback in order to direct it to an optimal solution.  In this case, the cost function is a simple for loop that calculates the distance traveled in a given solution, so if I want to improve upon it, I am going to need to figure out a better way to estimate or approximate the cost without having to do the full calculation.

So know that I know where my bottleneck is, I am going to get to work on trying to find a way to improve the algorithm so that I can get some good solutions for the problem sets.  I will post an update, with some comparative metrics on performance if/when I find a way to reduce the bottleneck.