啟發式搜索計劃樹,比天真貪婪的TSP解決方案更糟


8

我正在做coursera optimization course的旅行商問題(TSP)作業。我的第一個嘗試是從每個點開始使用常規的樸素貪婪方法,然後移動到最近的節點(尚未選擇)。我嘗試的第二個算法是啟發式搜索,如Sutton and Barto Sec 8.9所述。我構建了一個計劃樹,以考慮可能的路徑,並展望未來的幾步,然後選擇最短潛在路徑中的第一步。讓我非常驚訝的是,第二種方法的確比常規的天真貪婪更糟。(實際上,第二種方法可以通過與--depth 1--breadth 1運行來簡化為常規貪婪)。

我確信起初這是由於我的實施中的錯誤所致,但是經過大量時間逐步檢查結果,似乎不是嗎?例如它找到了可以計劃到最後的足夠小的問題的全局最優方案。我還聘請了一位導師以不同的方式(遞歸)重新實施啟發式搜索,他得到了相同的結果(在各種樹的深度/寬度和問題上,更深的計劃要比貪婪更糟糕),這也是他不理解的。似乎應該能夠構想出一些例子,這些例子的預見力要比幼稚的貪婪差,但我不明白為什麼在不同的樹深度/寬度以及不同的問題上,這種預見總是如此糟糕。

最後一點:我不是在問如何為TSP獲得更好的解決方案。我有更好的替代方法。讓我困擾的是,我無法理解為什麼這種特定算法始終比幼稚的貪婪更糟。

以下是我的問題的可複制示例;我的代碼和示例數據集,以及從shell運行示例的示例。下面的代碼可以與下面提供的數據集一起運行:

(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```
與例如對於常規貪婪(無計劃樹)而言,更好的解決方案(總距離506比上面的565):

(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也可以與--debug CLI標誌一起運行,以在每次選擇下一節點後暫停(提示用戶輸入" Enter"),並打印一些有用的信息。

我的程序如下:

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))

樣本數據集:

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
3

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.