benchmark问题

2.5.2算法测试性能评价标准启发式优化算法有着诸多优点，但通常启发式算法都具有无法保证得到最优解的缺陷，因此对算法性能的评价和分析显得非常重要。一个好的启发式算法可以使得其解尽可能的接近最优解，同时还能保证有较好的稳定性。目前，对于任何一个启发式优化算法的性能分析都是比较困难的。通常的性能分析方法有:最坏情形分析方法、概率分析方法和大规模计算分析方法。前两种方法都必须用理论方法分析，要求很强的数学基础和推演能力。目前研究者只对一些特定和简单问题采用上面两种方法分析，实际中的大量优化问题是采用大规模计算分析方法,也就是通过大量的实例计算评价算法的效果。在大规模计算分析中一般对一个优化算法做多次重复实验，我们采用以下几个指标作为评价的标准。平均优化值:在可接受的有限时间内优化算法所得到解的平均值，平均值越接近全局最优解，算法的基本性能就越好。如果为最小优化问题，则解的平均值越小越好。一般而言，“可接受的有限时间”用算法循环次数或评价函数的调用次数来衡量，因为评价函数计算占用了迭代运算的绝大多数时间，尤其是高维的复杂函数。标准差:在给定的有限时间内优化算法所得到解的标准差，这个指标反映了算法的稳定性。稳定的算法每次优化的结果差异很小，在工程实际中使用起来就更放心。解的质量由平均优化值和标准差反映。成功率:在可接受的有限时间内算法能搜索到可接受解的概率。在实际工程应用中优化一个问题通常采用在有限时间内多次优化，然后选取其中最优结果的方法。若算法成功率高就意味着在通过多次优化能找到可接受解的概率高，或者说能找到可接受解所需要的计算次数少。平均优化值、标准差和成功率一起反映了算法的寻优能力。平均成功循环次数(评价次数):在指定的最大循环次数范围内搜索到可接受解的平均循环次数(评价次数)。收敛速度一般表示在无限时间内算法搜索到可接受解的时间，通常时间是用评价函数的调用次数或算法循环次数来衡量的。在实际中，“无限时间”一般用一个充分大的评价函数调用次数(评价次数)或循环次数表示。本文采用平均成功循环次数(评价次数)来衡量算法的收敛速度，平均成功循环次数(评价次数)越小，算法收敛速度越快。若多次在最大循环次数范围内算法均无法搜索到可接受解，则可认为算法不收敛。期望循环次数(评价次数):考察算法的寻优能力与寻优速度的综合指标。上述成功率和收敛速度是衡量优化算法的重要指标，然而这两者在一定程度上相互制约，尤其是对于多模问题。为了综合评价和比较算法的性能，本文采用了期望循环次数(评价次数):期望循环次数(评价次数)=平均成功循环次数(评价次数)/成功率，该值越小则说明相对应的算法具有较平衡的性能，即该算法具有较高的成功率和少的平均成功循环次数(评价次数)。