亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全，請及時綁定郵箱和手機立即綁定

用約束編程解決優化問題的方法——以旅行商問題為例

一个案例：旅行推销员问题
TLDR

约束编程是解决约束满足问题的一种关键技术。这篇文章将展示约束编程也适用于解决小型到中型优化问题。我们将以著名的旅行商问题 (TSP)为例，详细解释通往高效模型的所有步骤。

为了简单起见，我们考虑TSP的对称情况，即两个城市之间的距离不论方向都是相同的。

本文中的所有代码示例均使用NuCS，这是一个完全用Python编写的快速约束求解工具，我目前正在将其作为一个业余项目来开发。NuCS在MIT许可证下发布。

对称TSP

据维基百科，

给定一组城市及其之间每一对城市的距离，求出每个城市只访问一次并最终返回出发城市的最短路径是什么？

来源：Wikipedia (注：原文链接为法国维基百科)

这是一个NP难题。从现在起，假设共有n个城市。

这个问题最简单的说法是，对于每一对城市之间可能存在的边，决定它是否属于最佳解决方案。搜索空间的大小为 2ⁿ⁽ⁿ⁻¹⁾ ᐟ²，当 n=30 时，这个数值大约为 8.8e130，远超过宇宙中的原子数量。

找到每个城市的继任者要好得多。复杂度变为n!，当_n=30_时，即大约为2.6e32，虽然较小但仍是非常庞大。

接下来，我们将用以下TSP实例来测试我们的模型：GR17, GR21, GR24。

GR17 是一个具有 17 个节点的具有对称性的TSP，其成本由 17 x 17 的对称邻接成本矩阵定义：

    [  
        [0, 633, 257, 91, 412, 150, 80, 134, 259, 505, 353, 324, 70, 211, 268, 246, 121],  
        [633, 0, 390, 661, 227, 488, 572, 530, 555, 289, 282, 638, 567, 466, 420, 745, 518],  
        [257, 390, 0, 228, 169, 112, 196, 154, 372, 262, 110, 437, 191, 74, 53, 472, 142],  
        [91, 661, 228, 0, 383, 120, 77, 105, 175, 476, 324, 240, 27, 182, 239, 237, 84],  
        [412, 227, 169, 383, 0, 267, 351, 309, 338, 196, 61, 421, 346, 243, 199, 528, 297],  
        [150, 488, 112, 120, 267, 0, 63, 34, 264, 360, 208, 329, 83, 105, 123, 364, 35],  
        [80, 572, 196, 77, 351, 63, 0, 29, 232, 444, 292, 297, 47, 150, 207, 332, 29],  
        [134, 530, 154, 105, 309, 34, 29, 0, 249, 402, 250, 314, 68, 108, 165, 349, 36],  
        [259, 555, 372, 175, 338, 264, 232, 249, 0, 495, 352, 95, 189, 326, 383, 202, 236],  
        [505, 289, 262, 476, 196, 360, 444, 402, 495, 0, 154, 578, 439, 336, 240, 685, 390],  
        [353, 282, 110, 324, 61, 208, 292, 250, 352, 154, 0, 435, 287, 184, 140, 542, 238],  
        [324, 638, 437, 240, 421, 329, 297, 314, 95, 578, 435, 0, 254, 391, 448, 157, 301],  
        [70, 567, 191, 27, 346, 83, 47, 68, 189, 439, 287, 254, 0, 145, 202, 289, 55],  
        [211, 466, 74, 182, 243, 105, 150, 108, 326, 336, 184, 391, 145, 0, 57, 426, 96],  
        [268, 420, 53, 239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0, 483, 153],  
        [246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157, 289, 426, 483, 0, 336],  
        [121, 518, 142, 84, 297, 35, 29, 36, 236, 390, 238, 301, 55, 96, 153, 336, 0],  
    ]

咱们来看看第一行数据。

[0, 633, 257, 91, 412, 150, 80, 134, 259, 505, 353, 324, 70, 211, 268, 246, 121]

以下是电路中节点 0 的可能继任者所对应的成本。若不考虑节点 0 自身作为继任者的情况（即排除值 0），最小值为 70 （节点 12 成为节点 0 的继任者时），最大值为 633 （节点 1 成为节点 0 的继任者时）。因此，节点 0 的继任者成本范围为 70 到 633。

TSP模型

我们将利用NuCS提供的现成的CircuitProblem来建模我们的问题。但在开始之前，让我们先看看背后发生了什么。CircuitProblem本身是NuCS提供的另一个现成模型 Permutation的子类，而Permutation也是NuCS提供的现成模型之一。

排列组合问题

置换问题定义了两个冗余模型，后继模型和前驱模型。

def __init__(self, n: int):  
    """  
    初始化排列问题实例。  
    :param n: 变量和值的数量  
    """  
    self.n = n  
    shr_domains = [(0, n - 1)] * 2 * n  
    super().__init__(shr_domains)  # 调用父类的初始化方法，传入shr_domains
    self.add_propagator((list(range(n)), ALG_ALLDIFFERENT, []))  # 添加传播器，参数为范围列表、算法和辅助参数
    self.add_propagator((list(range(n, 2 * n)), ALG_ALLDIFFERENT, []))  # 添加传播器，参数为另一范围列表、算法和辅助参数
    for i in range(n):  
        self.add_propagator((list(range(n)) + [n + i], ALG_PERMUTATION_AUX, [i]))  # 添加传播器，参数为范围列表、辅助排列算法和辅助参数i
        self.add_propagator((list(range(n, 2 * n)) + [i], ALG_PERMUTATION_AUX, [i]))  # 添加传播器，参数为另一范围列表、辅助排列算法和辅助参数i

前n个变量表示继承者模型，也就是说，电路中每个节点的继承者必须不同。换句话说，后n个变量表示前驱模型，每个节点的前驱也必须不同。

两个模型都与规则相关（参见 _ALG_PERMUTATIONAUX 约束）——

  • 当 succ[i] = j，pred[j] = i
  • 当 pred[j] = i，succ[i] = j
  • 当 pred[j] ≠ i，succ[i] ≠ j
  • 当 succ[i] ≠ j，pred[j] ≠ i
电路故障

电路问题优化了后续节点和前驱节点的范围，并增加了额外的限制来防止子循环的出现（这些约束的具体细节我们这里不展开讨论）。

    def __init__(self, n: int):    
        """    
        初始化电路问题实例。    
        :param n: 节点的数量    
        """    
        self.n = n    
        super().__init__(n)    
        self.shr_domains_lst[0] = [1, n - 1]    
        self.shr_domains_lst[n - 1] = [0, n - 2]    
        self.shr_domains_lst[n] = [1, n - 1]    
        self.shr_domains_lst[2 * n - 1] = [0, n - 2]    
        self.add_propagator((range(n), ALG_NO_SUB_CYCLE, []))    
        self.add_propagator((range(n, 2 * n), ALG_NO_SUB_CYCLE, []))
TSP模型（旅行商问题）

[/TSP模型（旅行商问题）]

借助电路问题，将TSP建模非常简单。

让我们考虑节点 i ，之前我们提到过，costs[i] 是一个包含节点 i 所有可能后续节点成本的列表。如果 j 是 i 的后续节点，则其相关成本是 costs[i]ⱼ。这可以通过下面这行代码来实现，这里的 _succcosts 表示后续节点成本列表的起始索引。

self添加传播者([([迭代索引i, self.succ_costs + i], ALG_ELEMENT_IV, costs[i]) for i in range(n)])

对称地，对于前置节点的成本，我们得到：

    self.add_propagators([([n + i, self.pred_costs + i], ALG_ELEMENT_IV, costs[i]) for i in range(n)])

最后，我们将中间成本加起来，就可以算出总成本了。

        def __init__(self, costs: List[List[int]]) -> None:  
            """  
            初始化问题实例。  
            :param costs: 表示顶点之间成本的二维整数列表  
            """  
            n = len(costs)  
            super().__init__(n)  
            max_costs = [max(cost_row) for cost_row in costs]  
            min_costs = [min([cost for cost in cost_row if cost > 0]) for cost_row in costs]  
            self.succ_costs = self.add_variables([(min_costs[i], max_costs[i]) for i in range(n)])  
            self.pred_costs = self.add_variables([(min_costs[i], max_costs[i]) for i in range(n)])  
            self.total_cost = self.add_variable((sum(min_costs), sum(max_costs)))  # 总成本  
            self.add_propagators([([i, self.succ_costs + i], ALG_ELEMENT_IV, costs[i]) for i in range(n)])  
            self.add_propagators([([n + i, self.pred_costs + i], ALG_ELEMENT_IV, costs[i]) for i in range(n)])  
            self.add_propagator(  
                (list(range(self.succ_costs, self.succ_costs + n)) + [self.total_cost], ALG_AFFINE_EQ, [1] * n + [-1, 0])  
            )  
            self.add_propagator(  
                (list(range(self.pred_costs, self.pred_costs + n)) + [self.total_cost], ALG_AFFINE_EQ, [1] * n + [-1, 0])  
            )

需要注意的是，无需同时拥有前后模型（一个就够了），但一起使用会更高效。

分支

我们使用BacktrackSolver的默认分支策略，决策变量为后续节点和前置节点。

    solver = BacktrackSolver(problem, decision_domains=decision_domains)  
    solution = solver.minimize(problem.total_cost)

最优解在 MacBook Pro M2 上使用 Python 3.12、Numpy 2.0.1、Numba 0.60.0 和 NuCS 4.2.0 在 248秒内找到。NuCS 提供的详细统计信息如下：

    {  
        '算法BC计数': 16141979,  
        '算法BC带剃除计数': 0,  
        '算法剃除计数': 0,  
        '算法剃除变化计数': 0,  
        '算法剃除无变化计数': 0,  
        '传播者蕴含计数': 136986225,  
        '传播者过滤计数': 913725313,  
        '传播者过滤无变化计数': 510038945,  
        '传播者不一致性计数': 8070394,  
        '求解器回溯计数': 8070393,  
        '求解器选择计数': 8071487,  
        '求解器选择深度': 15,  
        '求解器解决方案计数': 98  
    }

特别值得注意的是有8070393次回滚。咱们试着优化一下这个数值。

NuCS提供了一种基于后悔（即最佳成本与次佳成本之间的差距）的启发式来选择这个变量。然后我们将选择一个能最小化成本的值。

    solver = BacktrackSolver(  
      problem,   # 其中 problem 是问题实例
      decision_domains=决策域,  # decision_domains 是决策域
      var_heuristic_idx=VAR_HEURISTIC_MAX_REGRET,  # 变量启发式策略：最大遗憾法
      var_heuristic_params=成本列表,  # var_heuristic_params 是成本列表
      dom_heuristic_idx=DOM_HEURISTIC_MIN_COST,  # 域启发式策略：最小成本法
      dom_heuristic_params=成本列表  # dom_heuristic_params 是成本列表
    )  
    solution = 求解器.最小化(问题.总成本)  # solution 是求解器最小化问题总成本的结果

有了这些新的启发式方法，38秒内找到了最优解，统计如下：

    {  
        'ALG_BC_NB': 2673045,  
        'ALG_BC_WITH_SHAVING_NB': 0,  
        'ALG_SHAVING_NB': 0,  
        'ALG_SHAVING_CHANGE_NB': 0,  
        'ALG_SHAVING_NO_CHANGE_NB': 0,  
        'PROPAGATOR_ENTAILMENT_NB': 12,295,905,  
        'PROPAGATOR_FILTER_NB': 125,363,225,  
        'PROPAGATOR_FILTER_NO_CHANGE_NB': 69,928,021,  
        'PROPAGATOR_INCONSISTENCY_NB': 1,647,125,  
        'SOLVER_BACKTRACK_NB': 1,647,124,  
        'SOLVER_CHOICE_NB': 1,025,875,  
        'SOLVER_CHOICE_DEPTH': 36,  
        'SOLVER_SOLUTION_NB': 45  
    }

特别地，有1,647,124次回退。

我们可以不断改进，通过设计一个自定义启发式，结合最大遗憾值和最小定义域来进行变量选择。

    tsp_var_heuristic_idx = register_var_heuristic(tsp_var_heuristic)  
    solver = BacktrackSolver(  
      problem,   
      decision_domains=decision_domains,  
      var_heuristic_idx=tsp_var_heuristic_idx,  
      var_heuristic_params=costs,  
      dom_heuristic_idx=DOM_HEURISTIC_MIN_COST,  
      dom_heuristic_params=costs  
    )  
    solution = solver.minimize(problem.total_cost)

现在最优解能在11秒内找到，如下：

    {  
        'ALG_BC_NB': 660718, // 算法BC数量
        'ALG_BC_WITH_SHAVING_NB': 0, // 带剃须的算法BC数量
        'ALG_SHAVING_NB': 0, // 剃须算法数量
        'ALG_SHAVING_CHANGE_NB': 0, // 剃须变更算法数量
        'ALG_SHAVING_NO_CHANGE_NB': 0, // 剃须无变更算法数量
        'PROPAGATOR_ENTAILMENT_NB': 3596146, // 传播器推导数量
        'PROPAGATOR_FILTER_NB': 36847171, // 传播器过滤数量
        'PROPAGATOR_FILTER_NO_CHANGE_NB': 20776276, // 传播器过滤无变更数量
        'PROPAGATOR_INCONSISTENCY_NB': 403024, // 传播器不一致数量
        'SOLVER_BACKTRACK_NB': 403023, // 求解器回溯数量
        'SOLVER_CHOICE_NB': 257642, // 求解器选择数量
        'SOLVER_CHOICE_DEPTH': 33, // 求解器选择深度
        'SOLVER_SOLUTION_NB': 52 // 求解器解决方案数量
    }

特别地，其中有403,023次回退。

最小化是怎么工作的？

最小化（或者说更广泛的优化）依赖于一种分支定界算法。回溯过程允许通过进行选择（分支）来搜索搜索空间。通过限制目标变量，搜索空间的部分会被剪除。

在最小化变量 t 时，每当找到一个中间解 s，可以加入额外的限制 t < s。

NuCS 提供两种优化模式的选择，对应于利用 t < s 的两种方法（这里的 t < s 是特定的符号或表示方式）。

  • 重置模式会从头开始搜索，并更新目标变量的范围
  • 修剪模式会调整选择点以适应目标变量的新范围

现在我们来试试 PRUNE（一种特定模式）模式。

        solution = 求解器最小化(问题的总成本, 模式=剪枝)

在5.4秒内找到了最优解，统计如下：

    {  
        '算法BC数量': 255824,  
        '算法剃须数量（含剃须）': 0,  
        '算法剃须数量': 0,  
        '算法剃须变化数量': 0,  
        '算法剃须不变数量': 0,  
        '传播者蕴含数量': 1435607,  
        '传播者过滤数量': 14624422,  
        '传播者过滤不变数量': 8236378,  
        '传播者不一致数量': 156628,  
        '求解器回溯数量': 156627,  
        '求解器选择数量': 99143,  
        '求解器选择深度': 34,  
        '求解器解决方案数量': 53  
    }

只有156,627次回溯。

最后

下面是的表格列出了我们的实验：

TSP进行实验与NuCS实验

你可以在这里找到所有相关的代码#。

当然，还有很多其他我们可以探索的方法来提升这些结果，

  • 设计一个关于总成本的冗余约束（如在 链接 中所示）
  • 改进分支策略，尝试新的启发式方法
  • 使用不同的连贯算法（如NuCS提供的_剃须_方法）
  • 用其他方法计算下限和上限

旅行售货员问题已经受到了广泛的研宄，并且有大量的文献。在这篇文章中，我们希望说服读者能够在短时间内找到中等规模的问题的最优解，而不必对旅行商问题有深入的了解。

一些有用的链接，帮助你更深入地了解NuCS：

如果你喜欢这篇介绍NuCS的文章，请给它点50次赞！

點擊查看更多內容
為 TA 點贊

若覺得本文不錯，就分享一下吧！

評論

作者其他優質文章

正在加載中
  • 推薦
  • 評論
  • 收藏
  • 共同學習，寫下你的評論
感謝您的支持，我會繼續努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

 幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

 公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消