优化方法（元启发式，基于图形，混合整数线性规划）

Question

我对算法非常陌生，现在正在解决一些路线优化问题，并阅读了以下几种方法的论文：

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

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

• 混合整数线性规划方法

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

谢谢您提前的帮助！

- Kelly Zhang

Answer 1

混合整数线性规划是一类问题，而不是一个算法。它包括所有将线性和整数值的成本函数最大化的问题。这些假设使得创建解决此特定问题的算法更容易，我想这就是你所说的"MILP方法"。然而，实现可能会有很大的差异，因为针对特定问题的优化可能适用于良好的通用解决方案之上。

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

元启发式算法是一类旨在扩展启发式算法的算法。启发式算法是一种“实用”的问题解决方法，不能保证最优，但对于即时目标足够。元启发式算法将抽象层次提高了一步：不是直接对问题进行推理，而是构建问题的解决方案（例如GA中的个体）并对其进行推理（例如在GA中演变人口）。

路线优化可能属于三个类别中的任何一个，您需要更精确地说明才能得到恰当的答案，但以下是一些示例：

- 流量最大化问题：线性规划。 例如：网络中的每条路线最多可以由k辆卡车使用，您想在最短时间内从A点到B点运送沙子，每条路径上可以发送多少辆卡车？一条路径可能会分裂成两条更受限制的路径，或缩小并让您的卡车陷在路径的中间，甚至合并等。 （请注意，它仍然是基于图形的）。

- 最短路径、最长路径、路径数：纯基于图形。 深度优先和广度优先搜索（我假设您已经知道了）可以解决大量基于图形的问题，无需任何更复杂的方法。例如，A*只是DFS的扩展版本。对于路线优化，您很可能将路线网络表示为图形，因此这可能是一个好的起点。

- 旅行商问题：元启发式算法 TSP基本上是找到一条路径，该路径恰好访问所有城市一次。它比看起来困难得多（NP完全，如果那是你听过的）。元启发式算法在这里非常有效，因为没有已知的有效解决方案。遗传算法、蚁群优化和模拟退火都能够给出相当不错的结果，如果实现得当。例如，在每个全局优化轮之间，迭代局部搜索可以用于局部基于个体的优化，从而产生更好的结果。

很抱歉我的三个例子都涉及图形相关的问题，但这也表明图形可以帮助解决大量的问题，即使问题陈述中没有明确引用“图形”这个术语。

这三个问题都是路线优化问题，具体取决于您要优化什么。也许您的问题最好通过这三种方法之一来解决，或者通过组合两种方法（例如，局部线性规划优化和元启发式算法）来解决。

- Robindar