The Wayback Machine - https://web.archive.org/web/20221028220805/https://baike.sogou.com/kexue/d10188.htm

分支界限

编辑

分支定界（BB、B&B或BnB）是一种用于离散和组合优化问题以及数学优化的算法设计范例。分支定界算法由通过状态空间搜索的候选解进行系统枚举：候选解的集合被认为是在根上形成一个完整集合的根树。该算法探索该树的分支，这些分支代表解集的子集。在枚举分支的候选解之前，它会对照最优解的上下限估计检查分支，如果分支不能产生比算法迄今为止找到的最佳解更好的解，则将其丢弃。

该算法依赖于对搜索空间的区域/分支的下限和上限的有效估计。如果没有可用的边界，该算法退化为穷举搜索。

1960年，在英国石油公司[1][2]赞助的伦敦经济学院进行离散规划研究时，Ailsa Land和Alison Doig首次提出了该方法，该方法已成为解决NP难优化问题最常用的工具。“分支定界”这个名字最早出现在利特尔（Little）等人关于旅行推销员问题的著作中。[3]

1 概述编辑

分支定界算法的目标是在一些可容许的集合S或候选的解集合中找到一个最大化或最小化被称为目标函数的实值函数f(x)的值x。该集合S被称为搜索空间，或可行区域。本节其余部分假设f(x)最小化是理想的；这一假设不失一般性，因为人们可以通过找到g(x)=- f(x)的最小值来找到f(x)的最大值。B&B算法根据两个原则运行：

  • 它递归地将搜索空间分割成更小的空间，然后最小化这些更小空间上的f(x)；这种分裂叫做分支。
  • 分支本身就相当于对候选解决方案进行的强力枚举并对它们进行测试。为了提高蛮力搜索的性能，B&B算法跟踪它试图找到的最小值的边界，并使用这些边界来“修剪”搜索空间，消除它可以证明不包含最优解的候选解。

将这些原则转化为特定优化问题的具体算法需要某种表示候选解集合的数据结构。这种表示被称为问题的一个实例。用符号SI表示实例I的候选解集。实例表示必须有三个操作：

  • 分支(I)产生两个或多个实例，每个实例代表一个SI子集。(通常，子集是不相交的，以防止算法访问同一候选解两次，但这不是必需的。然而，国际社会中的最佳解决方案必须包含在至少一个子集内。)[4]
  • 界限(I)计算由I表示的空间中任何候选解的值的下限，即，对于SI中的所有x，界限(I)≤f(x)。
  • 解决方案(I)确定I是否代表单一候选解决方案。(可选地，如果没有，操作可以选择从SI中返回一些可行的解决方案。)[4]

使用这些操作，B&B算法通过分支操作形成的实例树执行自上而下的递归搜索。在访问实例I时，它检查绑定(I)是否大于它已经访问的其他实例的下限；如果是这样，I可能会被安全地从搜索中丢弃，递归会停止。这个修剪步骤通常是通过维护一个全局变量来实现的，该变量记录了迄今为止所检查的所有实例中的最小下限。

1.1 通用版本

下面是用于最小化任意目标函数f的通用分支和定界算法的框架。[5]要从中获得实际算法，需要一个定界函数g，它计算搜索树节点上f的下限，以及特定问题的分支规则。因此，这里给出的一般算法是高阶函数。

  1. 使用启发式方法，找到优化问题的解xh。存储其值，B=f(xh)。(如果没有启发式算法可用，则将B设置为无穷大。)B将表示迄今为止找到的最佳解决方案，并将用作候选解决方案的上限。
  2. 初始化一个队列来保存没有分配问题变量的部分解决方案。
  3. 循环，直到队列为空:
    1. 从队列中删除一个节点N。
    2. 如果N代表单个候选解x和f(x) < B，那么x是迄今为止最好的解。记录并设置B ← f(x)。
    3. 否则，分支到N产生新的节点Ni。对于其中的每一项：
      1. 如果界限(Ni) > B，则什么也不做；由于该节点上的下限大于问题的上限，因此它永远不会得到最优解，并且可以被丢弃。
      2. 否则，将Ni存储在队列中。

可以使用几种不同队列的数据结构。这种基于先进先出队列的实现产生了广度优先搜索。堆栈(后进先出队列)将产生深度优先算法。最佳优先分支和绑定算法可以通过使用优先级队列来获得，该队列在节点的下限对节点进行排序。[5]具有这一前提的最佳优先搜索算法的例子是迪克斯特拉（Dijkstra）算法及其派生的A*搜索。当没有好的启发式算法可用于产生初始解时，推荐深度优先变量，因为它能快速产生完整解，从而产生上限。[5]

1.2 改进

当   是   的一个向量时，分支定界算法可以与区间分析[6]和承包技术相结合，以提供全局最小值的保证。[7][8]

2 应用程序编辑

这种方法用于许多NP难题

  • 整数规划（Integer programming）
  • 非线性规划（Nonlinear programming）
  • 旅行推销员问题（Travelling salesman problem (TSP)）[9][9]
  • 二次分配问题(QAP) （Quadratic assignment problem (QAP)）
  • 最大可满足性问题（Maximum satisfiability problem (MAX-SAT)）
  • 最近邻搜索[10]（Nearest neighbor search(by Keinosuke Fukunaga)）
  • 流水调度（Flow shop scheduling）
  • 库存削减问题（Cutting stock problem）
  • 虚假噪声分析(FNA) （False noise analysis (FNA)）
  • 计算系统发生学（Computational phylogenetics）
  • 集合倒置（Set inversion）
  • 参数估计（Parameter estimation）
  • 0/1背包问题（0/1 knapsack problem）
  • 机器学习中的特征选择[11]（Feature selection in machine learning）
  • 计算机视觉中的结构化预测[12]

分支定界法也可以是各种启发式方法的基础。例如，当上限和下限之间的差距变得小于某个阈值时，可能希望停止分支。当解决方案“对于实际目的来说足够好”并且可以大大减少所需的计算时，就使用这种方法。这种类型的解决方案特别适用当所使用的成本函数有噪声或者是统计估计的结果，因此不能精确地知道，而是仅知道它处于具有特定值范围内的概率。

3 与其他算法的关系编辑

Nau等人提出了普遍化分支定界法，它也包含了人工智能中的A*、B*和α-β搜索算法。[13]

参考文献

  • [1]

    ^A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica. 28 (3). pp. 497–520. doi:10.2307/1910129..

  • [2]

    ^"Staff News". www.lse.ac.uk. Retrieved 2018-10-08..

  • [3]

    ^Balas, Egon; Toth, Paolo (1983). Branch and bound methods for the traveling salesman problem (PDF). Carnegie Mellon University Graduate School of Industrial Administration..

  • [4]

    ^Bader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "Parallel Algorithm Design for Branch and Bound" (PDF). In Greenberg, H. J. Tutorials on Emerging Methodologies and Applications in Operations Research. Kluwer Academic Press..

  • [5]

    ^Clausen, Jens (1999). Branch and Bound Algorithms—Principles and Examples (PDF) (Technical report). University of Copenhagen..

  • [6]

    ^Moore, R. E. (1966). Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall. ISBN 0-13-476853-1..

  • [7]

    ^Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0..

  • [8]

    ^Hansen, E.R. (1992). Global Optimization using Interval Analysis. New York: Marcel Dekker..

  • [9]

    ^Little, John D. C.; Murty, Katta G.; Sweeney, Dura W.; Karel, Caroline (1963). "An algorithm for the traveling salesman problem" (PDF). Operations Research. 11 (6): 972–989. doi:10.1287/opre.11.6.972..

  • [10]

    ^Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "A branch and bound algorithm for computing k-nearest neighbors". IEEE Transactions on Computers: 750–753. doi:10.1109/t-c.1975.224297..

  • [11]

    ^Narendra, Patrenahalli M.; Fukunaga, K. (1977). "A branch and bound algorithm for feature subset selection" (PDF). IEEE Transactions on Computers. C-26 (9): 917–922. doi:10.1109/TC.1977.1674939..

  • [12]

    ^Nowozin, Sebastian; Lampert, Christoph H. (2011). "Structured Learning and Prediction in Computer Vision". Foundations and Trends in Computer Graphics and Vision. 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651. doi:10.1561/0600000033. ISBN 978-1-60198-457-9..

  • [13]

    ^Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984). "General branch and bound, and its relation to A∗ and AO∗" (PDF). Artificial Intelligence. 23 (1): 29–58. doi:10.1016/0004-3702(84)90004-3..

阅读 1095
版本记录

  • 暂无