algorithm - 优化方法(元启发式、基于图形的、MILP)

Question

我对算法很陌生，现在正在研究一些路线优化问题，并看到了一些关于以下方法的论文:

• 元启发式方法基于种群(遗传算法、蚁群优化等)基于单一解决方案(迭代局部搜索)

• 基于图的方法例如A*算法

• 混合整数线性规划方法

我对这些方法之间的关系有点困惑，我们是使用例如 GA 来解决 MILP，还是它们都只是单独的方法？

提前致谢!

Answer 1

混合整数线性规划与其说是一种算法，不如说是一类问题。它包含所有归结为最大化线性且具有整数值的成本函数的问题。这些假设使得创建算法来解决这个非常具体的问题变得更加容易，我认为这就是您所说的“MILP 方法”。不过，实现可能会有很大差异，因为针对特定问题的优化可能适用于良好的通用解决方案。

Graph-based 更难定义，因为所有涉及图论的算法都没有明确表示它们正在使用图，但正确性或最优性的证明可能需要使用一些非平凡的图上的定理。

元启发式 是一类旨在扩展启发式的算法。启发式是解决问题的“实用”方法，它不能保证是最佳的，但足以实现近期目标。元启发式将抽象级别提高了一个层次:不是直接对问题进行推理，而是为问题构建解决方案(即 GA 中的个体)并对其进行推理(即在 GA 中进化你的种群)。

---

路线优化可能属于这三个类别中的任何一个，在我能够正确回答之前你需要更加精确，但这里有几个例子:

• 流量最大化问题:线性规划。

  例如:你的网络中的每条路线最多可以被 k 辆卡车使用，你想在尽可能短的时间内将沙子从 A 点运到 B 点，你可以在每条路径上发送多少辆卡车？一条路径可能会分成两条更受限制的路径，或者缩小并让您的卡车卡在路径中间，甚至合并等。(请注意它仍然是基于图形的)

• 最短路径、最长路径、路径数:基于纯图。

  深度优先和广度优先搜索(我假设您已经知道)可以解决大量基于图的问题，而无需任何更复杂的方法。例如，A*“只是”DFS 的一个扩展版本。通过路线优化，您很可能将路线网络表示为图形，因此这可能是一个很好的起点。

• 旅行商问题:元启发式

  TSP 基本上是找到一条访问所有城市一次的路径。它比看起来要困难得多(NP 完全，如果它响起的话)。元启发式算法在这里非常有效，因为目前还没有有效的解决方案。如果实现得当，遗传算法、蚁群优化 和模拟退火 都会产生相当不错的结果。例如，正如您引用的那样，迭代本地搜索可能用于在每个全局优化轮次之间进行基于本地个体的优化，从而产生更好的结果。

很抱歉，我的三个示例属于与图相关的问题，但它也表明图可以帮助解决数量惊人的问题，即使术语图没有在问题陈述。

这三个也恰好是路由优化问题，这完全取决于您要寻找什么优化。您的问题可能最好使用这三种方法中的一种来解决，或者结合使用两种方法(例如元启发式的本地 LP 优化)。