Kel*_*ang 5 algorithm genetic-algorithm ant-colony mixed-integer-programming
我对算法很新,现在正在处理一些路由优化问题,并且遇到了一些关于以下方法的论文:
元启发式方法 基于种群(遗传算法,蚁群优化等)基于单一解决方案(迭代本地搜索)
基于图的方法 ,例如A*算法
混合整数线性规划方法
我对这些方法之间的关系有点困惑,我们是否使用例如使用GA来解决MILP,或者它们都只是单独的方法？
提前致谢!!
混合整数线性规划比算法更像是一类问题.它包含所有问题,归结为最大化线性且具有整数值的成本函数.这些假设使得创建解决这个非常具体的问题的算法变得更容易,我认为这就是你所说的"MILP方法".但实现可能会有很大差异,因为特定于问题的优化可能适用于良好的通用解决方案.
基于图形的定义更难以定义,因为涉及图论的所有算法都没有明确表示它们使用图形,但是正确性或最优性的证明可能需要在图形上使用一些非平凡定理.
元启发式算法是一类旨在扩展启发式算法的算法.启发式算法是一种解决问题的"实用"方法,不能保证最优,但这对于直接目标来说已经足够了.元启发式将抽象级别提高一步:不是直接在问题上进行推理,而是为问题(即GA中的个体)构建解决方案并对其进行推理(即在GA中扩展您的人口).
路线优化可能属于三个类别中的任何一个,在我能够正确回答之前你需要更精确,但这里有一些例子:
流量最大化问题:线性规划.
例如:您的网络的每条路线最多可以使用k卡车,并且您希望在最短的时间内将沙子从A点运送到B点,您可以在每条路径上发送多少卡车？一条路径可能会分成两条更受限制的路径,或缩小并让您的卡车卡在路径中间,甚至合并等等(请注意它仍然是基于图形的)
最短路径,最长路径,路径数:纯图形.
深度优先和广度优先搜索(我假设您已经知道)可以解决大量基于图形的问题,而无需任何更复杂的方法.例如,A*是"仅"DFS的扩展版本.通过路由优化,您很可能将路由网络表示为图形,因此这可能是一个很好的起点.
旅行推销员问题:元启发式
TSP基本上找到了一次只访问所有城市的路径.它比它看起来要困难得多(NP-complete,如果它响铃).元启发式在这里非常有效,因为没有有效的解决方案.如果正确实施,遗传算法,蚁群优化和模拟退火都会产生相当好的结果.正如您所引用的,迭代本地搜索可用于例如每个全局优化轮之间的基于个体的局部优化,从而产生更好的结果.
对不起,我的三个例子属于与图形相关的问题,但它也表明图形可以帮助解决大量问题,即使在问题陈述中没有明确引用术语图表时也是如此.
这三个也恰好是路由优化问题,这一切都取决于您正在寻找的优化.您可以使用这三种方法中的一种方法最好地解决您的问题,或者通过组合两种方法(例如,针对Meta-heuristics的本地LP优化)来解决您的问题.