随机性优化算法有效性定量对比评价方法

李鹏飞，石正军

中国工程物理研究院计算机应用研究所，四川绵阳621900

1 引言

实际工程优化问题往往具有大规模、非线性、多极值、多目标、不连续等特点。传统优化算法，特别是基于梯度的优化方法往往不适用于上述情形或得不到满意解。近年来，随机性优化算法，特别是群体智能优化算法由于其优秀的问题适应性，良好的全局寻优能力，自然的并行性等特点成为优化算法领域的研究与应用热点。新的随机性优化算法以及已有算法的改进版本被不断提出。

随机性优化算法需要在寻优搜索过程中对搜索方向引入随机变化，从而降低搜索陷入局部最优的风险。然而，随机性的引入也使得算法寻优路径和最终结果具有不可重复性和不确定性，单次寻优结果无法真实反映算法的有效性（本文所指寻优结果均为算法求得的最优目标函数值）。因此，随机性优化算法的有效性，即算法（下文所指算法均为随机性优化算法）在一定计算开销下获得理想解或满意近似解的能力，应该是算法多次求解结果表现出的宏观性质。鉴于求解结果的不确定性，不同算法之间的有效性优劣关系应是概率意义上的关系。

一种简单易行的对比评价不同算法有效性的方法是比较不同算法针对一个或一组算例的成功率，即获得满意解的求解次数占总求解次数的比例[1]。这种方法需要已知算例的理论最优解及人为设定“满意解”的标准。另一种直观方法是比较不同算法针对同一算例多次求解结果的均值[2]，或者综合考虑均值和成功率[3]，但上述方法均为确定性的对比评价方法。

一种基于概率意义的对比评价方法是“t检验[4]”，该方法对总体符合正态分布的多个个体（即算法多次求解结果）进行针对总体分布的均值是否满足既定假设范围的假设检验[5]。在“t检验”中，需要已知算例的理论最优解，需要人为设定零假设中的总体正态分布的均值与理论最优解的接近程度（即假设的均值取值范围），最后由不同算法满足假设的显著性高低来判断不同算法的有效性高低。该方法操作较复杂，且最终不能得到一个概率来定量反映一种算法较另一种算法有效的可能性大小。

本文方法对两种算法多次寻优结果进行统计分析，最终得到一个因子反映一种算法比另一种算法更有效的可能性大小。该方法理论简单，易于操作，且不需要已知算例理论最优值，是一种概率意义上的有效性定量对比评价方法。

最后，本文给出以该方法对比评价采用同步或异步更新全局最优粒子信息模式的两种标准粒子群优化算法版本，在求解无约束单目标连续变量优化问题时的有效性相对关系的实例。

2 基于概率均值的有效性对比评价方法

2.1 针对单个算例的评价方法

2.1.1 定义

定义2.1.1设A、B为两种随机性优化算法，对单个算例（本文所指算例均为最小化优化问题），在既定的同等计算开销下，A、B算法多次寻优得到的目标函数值满足的总体分布为分别为DA、DB，x、y为随机变量。定义

为A算法相对B算法在该算例上的相对有效概率，其中p(x＜y)表示x小于y的概率。

定义2.1.2 如果

EAB＞0.5

则称A算法比B算法在该算例上更有效。

2.1.2 计算公式

针对某特定算例，在既定的同等计算开销下，由A、B两种算法分别进行na、nb次独立寻优求解，获得相应的优化结果样本集合XA及XB。“独立”即指各次求解过程中的伪随机数序列无关。

与t检验类似，需假设

根据大数定理知

实际情况不可能对一种算法执行无限多次，往往综合考虑算法开销和评价精度设定执行次数。根据所获得的样本集合XA及XB求得样本的均值与方差后，即可由式（1）得到对应的总体正态分布DA及DB的均值与方差。

在分布DB中随机选取一个随机变量y，其值大于（即劣于）给定值x0的概率如下：

将x0视为变量，设函数P(x)表示B算法单次求得解的值劣于变量x的概率，则有

进一步地，设x～DA，则P(x)在分布DA上的均值表示如下：

将式（2）代入式（3），结合定义2.1.1，可知相对有效概率的计算公式为：

由此可知，EAB的统计意义即为从分布DA与DB中分别单次随机抽样x与y，x小于y（即A算法单次寻优结果较B算法更准确）的概率平均值。

2.1.3 示例

设XA、XB分别为A、B算法多次求解某最小化优化算例最优目标函数值的样本集合，不妨设XA～N(0，1)，XB～N(0.2，0.25)，xa∈XA，xb∈XB。xa与xb满足的概率密度函数如图1所示。

由式（4）易得EAB≈0.571。由定义2.1.2可知，A算法较B算法在求解该算例时更有效，这是得益于XA的均值较小。但是，由于XA的方差较大，A算法的有效性优势并不显著。

2.1.4 相对有效概率与均值和方差的关系

（1）与均值的关系

图1 N(0，1)与N(0.2，0.5)概率密度函数

由于式（4）不涉及被测试算例的理论最优值，在固定DA与DB方差的前提下，相对有效概率EAB由DA与DB的相对位置决定，即EAB只与二者的均值差(μB-μA)有关。由图2可知，EAB与均值差的关系有如下特点：

（i）EAB随(μB-μA)单调上升。DA的均值比DB的均值越小，A算法相对B算法越有效。

（ii）在(μB-μA)～EAB平面上，(μB-μA)与EAB关于点（0，0.5）中心对称。特别地，A算法比B算法有效的充要条件即是μA＜μB，这与t检验类似。

图2 相对有效概率与均值差关系

（2）与方差的关系

固定DB的方差，图3反映了在不同DA方差条件下相对有效概率与均值差关系曲线的变化。

图3 不同DA方差条件下的相对有效概率与均值差关系

由图3可以看出，当μA<μB时，随着σA增大，同等均值差条件下，A算法对B算法的有效性逐渐减小。意味着采用该方法评价，即使A算法求得的解分布的均值占优，如果其方差变大，即算法的稳定性变差，A算法的相对有效性优势会下降。反之，当μA＞μB时，随着σA增大，同等均值差条件下，A算法对B算法的有效性逐渐增大。即寻优结果的均值处于劣势的算法，若求解结果的分散性变大，算法有效性的劣势会减小，这是因为有更多的均值劣势算法的解有机会落在均值优势算法解分布的主体区间内。

从式（4）可以推断，如果两个解分布的方差相对均值差极大，那么，二者所满足的正态分布将退化为均匀分布。按照定义2.1.1，此时EAB应恒为0.5。反之，若两个解分布的方差相对均值差极小，此时正态分布退化为狄拉克δ分布，只在二者的均值附近存在概率密度，此时相对有效概率应该满足如下的分段函数：

如图4印证了上述推断。

图4 极端方差情形下的相对有效概率与均值差关系

2.1.5 替代评价值

采用上述有效性对比评价方法，必须首先根据算法多次寻优结果计算出总体分布的均值和方差。然而，在实际优化问题中，特别是在目标函数高度非线性以及存在多极值点的情形，同一算法不同次优化同一问题的结果可能相差若干量级。

表1表示用标准粒子群算法（PSO）在一定计算开销前提下10次独立求解二维Rosenbrock函数最小值的结果，该函数的理论最优值为0，由表1可认为有8次求解结果有效。

表1 PSO算法求解Rosenbrock函数最小值10次结果

由表1直接计算出优化结果的均值约为1.80，显然，这个均值并不能真实反映这10组解与理论解接近程度的平均水平。这是由于量级差异巨大，多数相对极小的有效解被少数相对极大的错误解覆盖。要解决这一问题，需要对真实的目标函数值做一定变换再进行有效性评价。

对每一个优化结果f，定义其替代评价值falt：

其中，fopt为算例函数的理论最优值，如果理论值未知，则令

其中，fbest为需对比的两种算法多次求解该问题所有结果的最佳值，ε为一个小量，不妨设为10-20。

经过以上变换后，10次求解结果的替代评价值的均值约为－9.7，表示10次求解结果与理论最优值或实测最佳值的差距平均数量级约为－9.7，较真实地反映了10组解的有效水平。

2.2 针对算例集的评价方法

比较两种算法有效性的优劣并不能只针对一个算例，而要针对一个算例集，且这个算例集应尽可能包含该算法可能遇到的所有实际优化问题类型。

如果一种算法相对另一种算法在一个近似代表某类优化问题的算例集上综合表现出的有效性更高，就可以认为该算法在该类实际优化问题中较后者更有效。

定义2.2设S为包含n个测试算例的集合，si∈S，i=1，2，…，n，为A算法相对B算法针对算例si的相对有效概率，如果，则称A算法相对B算法在求解算例集S上更有效。

3 粒子群优化算法有效性对比评价实例

Eberhart与Kennedy提出的粒子群优化算法（PSO）是一种典型的基于群体智能的随机性优化算法[6-7]。PSO算法具有概念简单，容易实现，调节参数少等优点，已经成为智能优化算法的研究热点。

标准PSO算法中各个粒子的位置更新公式如下：其中，vk、xk分别为在第k次迭代过程中该粒子的速度和位置矢量，pb、pg分别为该粒子的历史最优位置和整个粒子群的全局最优位置矢量，ω、c1、c2为算法控制参数，rand1、rand2为随机数。

根据pg更新方式的不同，可将标准PSO算法分为同步更新和异步更新两种模式。在同步更新模式中，同一代的所有粒子适应度计算完毕后再更新pg；在异步更新模式中，任一粒子完成适应度计算后即与当前pg比较，实时更新pg。同步模式算法的早熟风险较小，但收敛速度较慢；异步模式的算法收敛速度快，并行性能好，但是早熟风险较大。在求解多数优化问题时，异步模式更为有效[8]。

作为第2章方法的实例，本章以10个无约束单目标函数优化算例组成的算例集为测试对象，对采用同步或异步全局最优粒子信息更新模式的两种标准PSO算法版本进行有效性对比评价。该测试算例集包含了单极值、多极值、周期性、间断梯度、病态梯度、含奇异点、罚函数形式、超平面解集、m in（max）等多种函数形态，大致代表无约束单目标连续变量优化这一类问题。

两种算法模式在同等计算开销前提下（最大进化代数均为150），对上述算例集中各个算例各自独立求解100次的结果如表2、表3所示。

设异步模式PSO算法为A算法，同步模式PSO算法为B算法，由式（4）可计算出A算法相对B算法在各个算例与整个算例集上的相对有效概率，如表4所示。

通过表4可以看出，按照定义2.1.2，异步模式PSO算法对同步模式PSO算法在所有测试算例上更有效。按照定义2.2，前者比后者在该算例集上更有效，且相对有效概率约为0.709。如果假设该算例集能够较好地近似代表无约束单目标优化问题，则可以认为对于某典型无约束单目标连续变量优化问题，异步模式PSO算法相比同步模式PSO算法求得更有效解的可能性为70.9%左右，这也印证了文献[8]的观点。

表2 异步更新模式PSO算法针对算例集的求解结果

表3 同步更新模式PSO算法针对算例集的求解结果

表4 异步模式对同步模式的相对有效概率列表

4 结论

提出了一种基于概率均值的随机性优化算法有效性定量对比评价方法，定义了一个因子，定量反映一种算法相对另一种算法在求解单个算例上更有效的可能性大小。对该因子的理论基础、计算公式进行了说明，讨论了该因子与两种算法多次求解结果的均值和方差之间的关系。进一步将该方法推广到针对一个算例集，以代表在一类实际优化问题上对两种算法进行有效性对比评价。

以同步更新PSO算法和异步更新PSO算法为对比评价对象，将上述方法实例化。针对无约束单目标连续变量优化函数算例集的评价结果表明，异步更新模式PSO算法在该类问题上综合有效性较高，与早期研究观点一致。

[1]Ali M M，Törn A.Population set-based global optimization algorithms：some modifications and numerical studies[J].Computers and Operations Research，2004，31（10）：1703-1725.

[2]Zaharaa E，Kao Y T.Hybrid Nelder-Mead simplex search and particle swarm optimization for constrained engineering design problem s[J].Expert Systems with Applications，2009，36（2）：3880-3886.

[3]Qin A K，Huang V L，Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Trans on Evolutionary Computation，2009，13（2）：398-417.

[4]Harnett D.Statistical methods[M].3rd ed.Reading：Addison-Wesley，1982：247-297.

[5]Hassan R，Cohanim B，De Weck O，et al.A comparison of particle swarm optimization and the genetic algorithm[C]//Proceedings of the 46th A IAA/ASME/ASCE/AHS/ASC Structures，Structural Dynamics and Materials Conference，Austin，TX，2005：1-13.

[6]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks，Piscataway，NJ，1995：1942-1948.

[7]Shi Yuhui，Eberhart R C.A modified particle swarm optimizer[C]//Proceedings of the IEEE Congress on Evolutionary Computation（CEC 1998），Piscataway，NJ，1998：69-73.

[8]Kennedy J.Methods of agreement：inference among the eleMentals[C]//Proceedings of the 1998 International Symposium on Intelligent Control，Piscataway，NJ，1998：883-887.