不一样的人生分享 http://blog.sciencenet.cn/u/josh

博文

No-Free-Lunch Theorem之于优化

已有 8161 次阅读 2011-5-20 15:14 |个人分类:Engineering Cybernetics|系统分类:科研笔记| 优化, Theorem, No-Free-Lunch

        No-Free-Lunch Theorem说,没有优化算法适合于所有优化问题:只能说针对某一类优化问题,某某算法更有优势。而不能笼统的说,某种优化算法比另一种更优。

 

        换个角度说,如果某种算法已经被证明在对某类问题有优势,那几乎可以肯定的是,它对另一类问题存在劣势(虽然可能并没有必要找到是哪一类问题);而如果某种算法被证明不适合于某类问题,也不可将其“一票否决”,因为它几乎肯定适合于另外的某类问题(而找到它适合的这一类问题就非常有必要了)。

 

        这样来解释的话,No-Free-Lunch Theorem更像是某种“守恒定律”,优化算法如果在某个地方“高”,那它会在另外一个地方“低”——遍历所有种类的优化问题,优化方法的“平均高度”是一样的:(在平均意义上)人人平等。

 

        假设针对某个优化问题,有两个优化算法:一个优化算法利用了所有能够应用的信息,而另外一个优化算法则对某些信息视而不见。那么从概率意义上来说,利用所有信息的优化算法的效果会更好。当然也不尽然,不过这时更应该高兴才对,因为利用了更多信息的优化方法“平均身高”增加了:如果针对当前这个问题效果没有更好的话,那么针对另一类问题其效果一定有了更大地提升。

 

        对于同一个优化算法而言,利用的优化问题本身的信息越多,效果(也是从概率意义上来说)将会越好。而这些信息的利用比单纯的试凑法(交叉实验法),对优化算法本身的参数调节具有更大的指导意义。这也算是No-Free-Lunch Theorem的一个方面:(在平均意义上)没有白花的力气。

 

        于是人们不禁要问:为什么选择某某算法,它真的比其它算法更加适合于当前需要解决的问题吗?优化问题本身的哪些信息可以利用,以指导算法本身的参数选择,以使得优化效果(从概率意义上)更好呢?想要真正回答这些问题(而不是事后来个“马后炮”,硬是给某算法冠以“具有某某特点因此具有某某优势”的美名)是不容易的(可能也是没必要甚至错误的)。

 

       设想如下这种可能:即使是同一个优化问题,其问题的结构不变,而只是参数变化,也会触发No-Free-Lunch Theorem:即某优化算法对某些参数效果好,另外一些效果差,而我们只是凑巧地碰到了那些使得它优化效果好的参数:这时如果非得“推而广之”,说这一优化算法就适合这类问题、并硬是找出个理由安在上面、最后信誓旦旦地说这是大量实践总结出的规律的话,就没有意义了(当然对写论文仍然具有意义,因为相当多的论文是这样写出的)。



https://blog.sciencenet.cn/blog-286797-446192.html

上一篇:毛拉五日谈
下一篇:二十年后或许能见分晓
收藏 IP: 61.170.4.*| 热度|

1 吴吉良

发表评论 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-5-21 06:51

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部