我知道大多数现实世界的优化问题在搜索空间中都会有局部最优值,但是有没有办法知道是否确定?
如果我能确定没有任何局部最优需要担心,我就可以安全地应用简单的爬山算法来解决问题,而不是更复杂的搜索算法,如 GA。
对不起,如果这有点基础
最佳答案
没有。
大多数现实世界的优化问题都是 NP 难问题的具体实例。 “NP-hard”意味着在最坏情况下(“NP”)可以快速验证其解决方案的每个问题都可以编码为特殊情况(“-hard”)。
我认为没有人知道任何 NP-hard 问题的爬山启发式,在这种情况下,每个步骤都可以在最坏情况下有效地实现,并且最终总是返回最佳解决方案。 (我可能对此有误;这比我更确定的“我们不知道任何 NP 难问题的任何多项式时间算法”更有说服力。)
顺便说一句,如果您有兴趣为大量困难问题寻找全局最优解,我不建议您过于依赖爬山法、遗传算法、模拟退火等。如果您有兴趣为大量简单问题找到全局最优解决方案,我根本不建议使用它们。研究和利用问题的结构几乎总是值得的,或者至少使用混合整数规划或约束规划等框架来利用它能找到的东西。
关于algorithm - 有什么方法可以预测搜索空间中的局部最优值吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24847056/