现在的位置: 首页 > 综合 > 正文

No Free Lunch定理

2013年10月16日 ⁄ 综合 ⁄ 共 451字 ⁄ 字号 评论关闭

Stanford大学Wolpert和Macready教授提出了NFL定理,它是优化领域中的一个重要理论研究成果,意义较为深远。现将其结论概括如下:

定理1 假设有A、B两种任意(随机或确定)算法,对于所有问题集,它们的平均性能是相同的(性能可采用多种方法度量,如最优解、收敛速率等),即

式中c为个体适应度的概率曲线;f为适应度函数;N为群体大小。

对于上述结论,Radcliffe和Surry也有相同的结论。例如,如果进化算法求解问题集A时的性能比模拟退火的性能好,那么必然会有模拟退火求解问题集B时的性能比进化算法的性能好。平均所有情况,两种算法的性能是相同的,甚至可以说没有哪种算法比随机搜索算法更好。根据NFL定理,算法性能“好”与“坏”不进与一定的问题有关,而且与个体适应度的概率曲线c有关,显然只有知道c才可评价算法性能的好坏。

比如,多目标协调进化算法(MOCEA)对于解决高维多目标优化问题尤其有效,但是由于其算法复杂,计算繁多,在解决低维多目标优化问题时,却不一定优于其它已有的多目标进化算法。

抱歉!评论已关闭.