首页 > 搜索 > 算法中上界函数怎么写,如何证明一个启发式算法的上界(下界)是无限逼近复杂问题最优

算法中上界函数怎么写,如何证明一个启发式算法的上界(下界)是无限逼近复杂问题最优

互联网 2020-10-23 04:46:32
在线算命,八字测算命理

这是所有初接触智能算法的新手共有的担心,就是算法的成立性。所有的智能算法都可以被证明概率的收敛于最优解(注意,是概率性的证明而不是确定性的证明)。这也意味着,假定迭代次数足够长,那么最优解一定可以获得。当然在实际科学和工程计算中不会有无穷次的迭代,但是只要迭代或者重复运行次数足够长,解已经很接近最优解了。

关于你提到的这几种算法的证明,我仅简单文字提及遗传算法的两种证明方法,至于其他的你需要自己去查阅相关的数学文献(都很晦涩)。早期遗传算法的证明来源于Holland的模式定理,也被称为BBH(building block hypothesis),其大意是在进化过程中健壮模式组合得以高概率的保留下去,因此如果进化足够长,那么最终的结果是最健壮的模式组合,也就是最优解。近年来更为流行的理解是Beyer的基因修复(genetic repair),即不是最健壮的模式组合,而是父代的带来高适应度的共同特点能够更高概率的得益保留,而不同特点逐渐在进化过程中被修复为相同特点。这样的观点同样意味着进化足够长则全局最优解可以获得。

"Evolution strategies -- A comprehensive introduction"你可以去查阅一下,里面对于理论证明的提及肯定比我说的更详细。尽管名字是ES,但是今天的ES和GA已经互相借鉴了很多,所以很类似了,统称为EC(evolutionary computation)应该更合适。

至于其它的算法,证明思路类似,当然细节很不同,有兴趣就慢慢翻查数学文献吧。

【 在 vcpshine (CADILLAC) 的大作中提到: 】

: 启发式搜索算法很多,比如遗传算啊,蚂蚁算法,免疫算法,微粒群算法

: 有些书说这些算法收敛于问题的最优解,我很好奇的是这是怎么证明的?

: 尤其是很多问题的最优解尚无法得知的情况下

: ...................

加好友 回复
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多