5

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

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

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

  • 混合整数线性规划方法

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

提前致谢！！

4

1 回答 1

6

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

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

元启发式算法是一类旨在扩展启发式算法的算法。启发式是解决问题的“实用”方法，它不能保证是最优的，但对于直接目标来说已经足够了。元启发式将抽象级别提高了一步：不是直接对问题进行推理，而是为问题构建解决方案（即 GA 中的个人）并对其进行推理（即在 GA 中进化您的人口）。

路线优化可能属于这三个类别中的任何一个，您需要更精确才能正确回答，但这里有几个示例：

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

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

  • 最短路径、最长路径、路径数：Pure Graph-based。

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

  • 旅行商问题：元启发式

    TSP 基本上是在寻找一条只访问所有城市一次的路径。它比看起来要困难得多（NP-complete，如果这敲响了钟声）。元启发式在这里非常有效，因为没有已知的有效解决方案。如果实施得当，遗传算法、蚁群优化和模拟退火都可以得到很好的结果。正如您所引用的，迭代局部搜索可用于例如每个全局优化轮之间的基于局部个体的优化，从而产生更好的结果。

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

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

于 2018-03-06T08:16:14.333 回答