8
$\begingroup$

I'm doing a Traveling Salesman Problem (TSP) homework for a coursera optimization course. My first attempt was a regular naive greedy approach, from each point, moving to the closest node (that hadn't yet been selected). The second algorithm I tried was heuristic search, as described by Sutton and Barto Sec 8.9. I build a planning tree to consider possible paths looking several steps forward, then choose the first step along the shortest potential path. Very surprisingly to me, this second approach does consistently worse than regular naive greedy. (In fact the second approach can be reduced to regular greedy, by running it with --depth 1 or --breadth 1).

I was sure at first this was due to a bug in my implementation, but after tons of time stepping through results, it seems not to be? e.g. It finds the global optimum on small enough problems it can plan through to the end, as expected. I also hired a tutor to re-implement heuristic search a different way(recursively), he got the same results (deeper planning worse than greedy, across a variety of tree depth/breadths and problems), which he also didn't understand. It seems obvious one should be able to contrive examples where the foresight performs worse than naive greedy, but I don't understand why it's so consistently doing worse, across different tree depths/breadths and across different problems.

One final note: I'm not asking how to get a better solution to the TSP. I have alternative approaches that do much better. What is bothering me is that I can't grok why this particular algorithm is consistently worse than naive greedy.

Below is a reproducible example of my issue; my code, and a sample dataset, along with examples of running it from shell. Code below can be run with dataset provided below as follows:

(tspenv) ~/.../tsp$ python solver.py data/tsp_51_1 --depth 8 --breadth 3

565.68 0
0 33 22 1 25 20 37 21 43 29 42 11 40 19 7 35 23 34 24 41 3 45 28 2 47 26 6 36 12 30 18 16 44 15 38 50 39 49 17 32 48 5 10 9 27 46 8 4 13 14 31```

as compared to e.g. much better solution (total distance 506 vs 565 above) for regular-greedy (no planning tree):

(tspenv) ~/.../tsp$ python solver.py data/tsp_51_1 --depth 1 --breadth 1
506.36 0
0 33 5 2 28 45 9 10 3 46 24 34 23 12 36 6 26 47 27 41 8 4 35 13 7 19 40 18 11 42 29 43 21 37 20 25 1 22 31 39 50 38 15 44 16 14 30 48 32 17 49

solver.py can also be run with --debug CLI flag to pause (prompt for user to input 'Enter') after each next-node selection, and print out some helpful info.

My program below:

import argparse
from anytree import Node, RenderTree
import math
import numpy as np
import random
from sklearn.metrics import pairwise_distances
import subprocess
import sys
import pandas as pd
from pprint import PrettyPrinter
from tqdm import tqdm


def unique_l(l):
    return list(set(l))


def get_dist_matrix(input_data):
    """input_data comes in as raw multiline text string"""
    lines = input_data.split('\n')
    xypairs = [i.split() for i in lines[1:-1]]  # first line is num-points, last line is blank
    dist_matrix = pairwise_distances(xypairs, metric='euclidean')
    return dist_matrix

def get_closest_nodes(current_pt, dist_matrix, n, exclude=[], verbose=False):
    dist_to_alternatives = dist_matrix[current_pt].copy()

    # don't consider as neighbors any points already visited
    dist_to_alternatives[unique_l(exclude + [current_pt])] = np.inf
    n_valid = min(n, np.isfinite(dist_to_alternatives).sum())

    neighbors_idx = np.argpartition(dist_to_alternatives, n_valid)[:n_valid]  # argpartition like an argmin to return n smallest
    return neighbors_idx


def calc_tour_dist(tour_order, dist_matrix):

    # dist-matrix entry between each consecutive pair of stops in tour_order.
    # (plus last-entry back to first)
    total_dist = sum([dist_matrix[i,j] for i,j in zip(tour_order[:-1], tour_order[1:])])
    total_dist += dist_matrix[tour_order[-1], tour_order[0]]
    return total_dist


def heuristic_search_salesman(distance_matrix, 
                              startnode=0, 
                              breadth=3, 
                              depth=3, 
                              verbose=False, 
                              debug=False):
    ''' Build out a heuristic search tree considering possible paths forward. 
        Take first step along shortest planned path.
        See for ref Sec 8.9 "Reinforcement Learning," by Sutton and Barto: 
        http://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf

        (Note: if depth or breadth is 1, this reduces to regular greedy search)

    params
    ------
    distance_matrix: square matrix of distance from each point to each other point
    startnode:       node the TSP starts from 
    breadth:         breadth of the search tree (how many next-steps considered from each step)
    depth:           depth of the search tree (how many steps forward to plan)
    '''
    print(f"Starting Heuristic Search Salesman for depth={depth} & breadth={breadth}")

    visit_order = [startnode]
    for i in tqdm(range(distance_matrix.shape[0]-1)):  # i is the tour position we're deciding now
        current_pt = visit_order[-1]

        # From current point, create a tree gaming out paths moving forward
        root = Node(str(current_pt))

        # first level of planning tree: candidates for next-move from current point
        candidates = get_closest_nodes(current_pt, distance_matrix, breadth, exclude=visit_order)
        nodes_by_tree_lvl = {k:[] for k in range(depth+1)}
        nodes_by_tree_lvl[0] = [Node(str(c), parent=root) for c in candidates]

        # fill out rest of planning tree in a loop
        for level in range(1, depth):
            for candidate in nodes_by_tree_lvl[level-1]:
                candidate_ancestors = [int(a.name) for a in candidate.ancestors]
                exclude = unique_l(visit_order + candidate_ancestors)
                next_candidates = get_closest_nodes(int(candidate.name), distance_matrix, breadth, exclude=exclude)
                nodes_by_tree_lvl[level] = nodes_by_tree_lvl[level] + [Node(str(nc), parent=candidate) for nc in next_candidates]

        # Now that the heuristic search tree is constructed, calculate full distance for each potential path,
        # next-step will be first-step along shortest planned path
        next_step = np.nan
        shortest_dist = np.inf
        for possible_path in root.leaves:
            nodes = [n.name for n in possible_path.ancestors] + [possible_path.name]
            dist = sum(distance_matrix[int(i),int(j)] for i,j in zip(nodes[0:-1],nodes[1:]))

            # if nodes already visited + depth of planning tree extends to all nodes, need
            # to include distance back to start to complete circuit in path's planned dist
            if len(visit_order) + len(nodes)-1 == distance_matrix.shape[0]:
                distance_back_to_start = distance_matrix[startnode, int(nodes[-1])]
                dist = dist + distance_back_to_start

            if verbose:
                print(f"distance for {nodes} is {dist}")
            if dist < shortest_dist:
                shortest_dist = dist
                next_step = int(nodes[1])  # nodes[0] is current-point. so nodes[1] is next step

        visit_order.append(next_step)
        if verbose:
            print(f"{visit_order}, cumulative distance: {sum([distance_matrix[i,j] for i,j in zip(visit_order[:-1], visit_order[1:])])}")
        if debug:
            input("Press Enter to continue...")

    return visit_order


def solve_it(input_data, 
             depth=3, 
             breadth=3, 
             verbose=False, 
             debug=False):
    """ Run python solver.py -h from shell for explanations of parameters """

    # Calculate distance matrix. Optionally save to csv disk for debugging
    distance_matrix = get_dist_matrix(input_data)
    if verbose ==1:
        print("Saving Distance-Matrix for distances among all nodes to each other to distance_matrix.csv\n")
        pd.DataFrame(distance_matrix, columns=[[str(i) for i in range(len(distance_matrix))]]).to_csv('distance_matrix.csv')

    # Conduct heuristic search. Breadth or Depth of 1 reduces to regular greedy search
    start = 0
    tour = heuristic_search_salesman(distance_matrix, 
                                     startnode=start, 
                                     breadth=breadth,
                                     depth=depth, 
                                     verbose=verbose,
                                     debug=debug)  
    tour_dist = calc_tour_dist(tour, distance_matrix)

    # Format output as desired by course grader
    proved_opt=0
    output_data = f'{tour_dist:.2f} {proved_opt}\n'
    output_data += ' '.join(map(str, tour))
    return output_data


if __name__ == '__main__':
    # CLI Argument Parser
    parser = argparse.ArgumentParser()
    parser.add_argument('datafile', type=str, help = "path to data file. required")
    parser.add_argument('-d', '--depth', type=int, default='3', 
                        help='Number of Levels to plan forward in heuristic search tree. 1 means regular greedy search')
    parser.add_argument('-b', '--breadth', type=int, default='3', 
                        help='Number of closest nodes to consider at each level of the heuristic search tree')
    parser.add_argument('-v', '--verbose', action="store_true", help="Show extra print statements")
    parser.add_argument('--debug', action="store_true", 
                        help="Pause execution until keypress after each next-step selection. Sets verbose to True as well")

    # Parse CLI args and call solver 
    args = parser.parse_args()

    with open(args.datafile, 'r') as input_data_file:
        input_data = input_data_file.read()

    print(solve_it(input_data,  
                  depth=args.depth, 
                  breadth=args.breadth,
                  verbose=max(args.verbose,args.debug),  # no point calling debug w/o verbose
                  debug=args.debug))

Sample Dataset:

51
27 68
30 48
43 67
58 48
58 27
37 69
38 46
46 10
61 33
62 63
63 69
32 22
45 35
59 15
5 6
10 17
21 10
5 64
30 15
39 10
32 39
25 32
25 55
48 28
56 37
30 40
37 52
49 49
52 64
20 26
40 30
21 47
17 63
31 62
52 33
51 21
42 41
31 32
5 25
12 42
36 16
52 41
27 23
17 33
13 13
57 58
62 42
42 57
16 57
8 52
7 38
$\endgroup$
  • $\begingroup$ Hi Max. Are you solving some instances from a certain benchmark? Have you tried another one, e.g. a randomly generated benchmark? $\endgroup$ – Mostafa Apr 13 at 13:53
  • $\begingroup$ Hi Mostafa, I've tried on different problems from the course, I think they're randomly generated but not sure. And the tutor I hired who reproduced my results said he tried on randomly generated problems. Is there a standard problem or set of problems I should try? $\endgroup$ – Max Power Apr 13 at 14:06
  • $\begingroup$ And have you read the following paper? You may find the answer in that.sciencedirect.com/science/article/pii/… $\endgroup$ – Mostafa Apr 13 at 14:06
  • $\begingroup$ Yes, you can find the standard library here: pubsonline.informs.org/doi/abs/10.1287/… $\endgroup$ – Mostafa Apr 13 at 14:11
  • $\begingroup$ I had not seen that paper, thanks, although I don't think either my greedy or n-step greedy approaches described here fall under the category of LK-methods or stem-and-cycle methods that paper seems focused on. (ungated link for reference: leeds-faculty.colorado.edu/glover/fred%20pubs/…) $\endgroup$ – Max Power Apr 13 at 14:14
3
+150
$\begingroup$

It seems that heuristic search prioritizes searching in the middle at versus greedy search, which is especially problematic to minimizing the cost function of TSP. Searching in the middle is bad because this often cuts the graph in half which leads to suboptimal solutions (where the final path crosses each other).

The reason why heuristic search cuts to the center is because the point density is higher in the middle of the graph and often, these dense points in the center will always lead to a lower path length when heuristic searching.

And this leads the underlying reason why search isn't the optimal solution for TSP here because the heuristic objective function is not a great approximation for the true Hamiltonian cycle objective function. I would conclude here that minimizing the path for the next 5 nodes does not take into account that Hamiltonian path length is a function of all the nodes.

It seems that greedy pathing is better because it avoids this middle cutting behavior.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That makes total sense, thanks! $\endgroup$ – Max Power Apr 15 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.