基于优劣解距离法的群智能优化算法性能排序

郭恩铭，方洋旺,2，彭维仕，杜泽弘

(1.西安邮电大学计算机学院，陕西 西安 710121；2.西北工业大学无人系统技术研究院， 陕西 西安 710072；3.武警工程大学装备管理与保障学院，陕西 西安 710086； 4.上海机电工程研究所，上海 201109)

0 引言

群智能是指自然界智能行为特征和生物现象，适应性、自我学习、健壮性和效率使生物媒介(如昆虫和鸟类)能够承担复杂的任务[1]。人们根据这些群智能行为特征[2]，提出了群智能优化算法。例如：哈里斯鹰优化算法(Harris hawk optimization，HHO)[3]、松鼠搜索算法(squirrel search algorithm，SSA)[4]、海洋捕食者算法(marine predators algorithm，MPA)[5]、被囊群优化算法(tunicate swarm algorithm，TSA)[6]等。

但是工程实际中，如何选择合理的群智能优化算法，则需要对算法的性能进行分析和比较。其中，文献[7]针对机器人群学习的性能分别对蝙蝠算法(bat algorithm，BA)、粒子群算法(particle swarm optimization，PSO)、灰狼优化器(grey wolf optimization，GWO)进行了分析，研究中使用避障基准任务通过t检测法对三种算法的性能对比在不同的机械手的数量(NR)和通讯范围(CR)条件下机器人的社交学习能力，但t检测法要求数据是来自正态分布且不能用于多组比较，最后结果是针对机器人系统选择算法的建议。文献[8]提出人像散度模型，来评价猫群算法(cat swarm algorithm，CSO)与粒子群和人工蜂群算法的性能。相关改进算法和原算法比较中[9-10]用的都是算法的标准差、平均值等单个指标来评估算法性能的优劣。如何综合地评估算法的性能对于算法的应用非常重要。

针对传统评估指标不能合理评估算法性能的问题，提出基于逼近理想解排序法(technique for order preference by similarity to ideal solution，TOPSIS)的评估方法，逼近理想解排序法又简称优劣解距离法。

1 TOPSIS方法原理

TOPSIS方法是一种用于许多实际问题的简单的MCDA技术[11-12]。由于其使用的简便性，被广泛应用于解决多标准问题[11]。采用TOPSIS方法能够在极大保留原始数据特点信息的基础上清晰地反映不同方案之间的差距。

TOPSIS方法是由Hwang和Yoon[13]提出，设有m个方案P={p1,p2,…,pm}，每个方案pi(i=1,2,…,m)由n个评价属性{ai1,ai2,…,ain}构成，即n个属性决定一个方案。

TOPSIS方法的步骤如下：

1) 设多属性决策矩阵A=(aij)m×n，之后对多属性决策矩阵进行规范化得到规范化矩阵B=(bij)m×n，规范化方法为：

(1)

2) 对B进行加权得到加权矩阵C=(cij)m×n，设属性的权重W={w1,w2,…,wn}，则加权矩阵的计算公式为：

cij=wj·bij。

(2)

3) 计算正理想解P*和负理想解P0，P*中每个属性值都为最优值；P0中每个属性都为最差值，公式如下：

(3)

(4)

4) 计算每个备选方案pi到正理想解和负理想解的距离

(5)

(6)

5) 计算m个方案P对应的排序指标，计算公式：

(7)

6) 得到排序指标之后按其大小进行排序，该顺序就是每个方案的优劣排序。

2 基于TOPSIS法的群智能优化算法 性能排序方法

本章主要介绍用于构建TOPSIS综合评估指标的7种属性指标，说明7种属性数据在TOPSIS法中的处理过程以及对结果的排序。

2.1 群智能优化算法评估属性指标

在研究和实验中不同问题选用哪种算法来解决，这涉及到重点考虑算法的哪种特性，实际中需要考虑算法的计算时间、精度、寻优能力和成功率等性能。若从单一性能指标，可能会给出不合理的决策结果，因此需要综合评估群体智能算法性能。

2.1.1平均计算时间

为了评估算法的收敛速度，定义算法的平均计算时间。令算法循环运行N次，算法的N次运行时间为t={t1,t2,…,tn}，则平均计算时间S为：

(8)

2.1.2计算精度

为了评估算法的寻优能力，定义算法的计算精度。令N次循环运行的结果为C={c1,c2,…,cn}，理论最优值为Z，则计算精度X为：

X=|min{C}-Z|，

(9)

测试的函数都是求最小值函数，因此在公式中的min{C}就是使用N次循环结果中实际取得的最优值。

2.1.3算法覆盖度

为了评估算法的全局搜索能力，定义算法的覆盖度。覆盖度越大所得结果越可能是全局最优，结果的可靠性越强。

首先要得到所有搜索粒子的位置，如图1和图2分别对应两次迭代的粒子位置，需要将两次迭代的所有搜索位置都记录下来。

图1 第一次粒子迭代位置Fig.1 The first particle iteration position

图2 第二次粒子迭代位置Fig.2 The second particle iteration position

之后对自变量范围[bl,bu]进行区间划分，自变量x中所有xi(i=1,2,…,n)都在同一范围[bl,bu]内的随机取值，通过计算得到在维度为dim的时候能划分为多少区间并确定每个区间的标志。如图1和图2中设bl和bu分别为0和15，划分步长大小为1，故每个维度可分为15个小区间，因此共有15×15=225个区间。

使用一维数组下标来表示每个区间的序号，通过相应的转换公式将粒子所在高维度坐标转换为十进制整数，该整数就是粒子所在区间的序号，即一维数组的下标。如图3所示为图1和图2转化为一维数组存储，数字为每个区间的序号。

图3 一维存储数组Fig.3 One-dimensional storage array

找到区间之后对该区间进行判断：是否已经被搜索过，若该区间未被搜索过，则将对应一维数组元素变为1，通过对数组求和得到粒子搜索的空间，计算搜索空间占所有空间的比例得到覆盖度。

设自变量范围[bl,bu]按划分步长α进行区间划分，自变量x={xi}(i=1,2,…,n)都是在同一范围[bl,bu]内的随机取值，区间的总数量n为自变量区间划分数量m的维度dim次方，则总自变量空间大小的计算为：

(10)

n=mdim。

(11)

使用一维零数组A来存储所有区间，通过式(5)和式(6)将粒子向量x={x1,x2,…,xn}转换为一个十进制整数j，该整数就是粒子所在区间的编号。

(12)

(13)

最终得到的数组A中为1的位置就是所有粒子所搜索的区域，之后计算占比，则覆盖度F为：

(14)

2.1.4覆盖速率

为了评估算法的搜索速度，定义算法的覆盖速率。上述定义的覆盖度是在所有迭代中的所有粒子搜索空间占整个空间的比例，且知道了每个算法的平均计算时间，则覆盖速率为覆盖度F除以平均计算时间S得出

(15)

2.1.5最优与最差值

为了评估算法的收敛精度和鲁棒性，定义算法的最优与最差值。令n次循环值中找到其中的更优为Xbest和更差值为Xworst，则最优与最差值为：

(16)

2.1.6寻优成功率

为了评估算法的稳定性，定义算法的寻优成功率。设寻优成功的精度条件为y，数组C={c1,c2,…,cn}用来存储每次寻优是否成功，初始化C为零数组，若成功则将对应位置的数组元素修改为1，则数组中元素值为：

(17)

之后C中元素的和除以循环次数n，则寻优成功率L为：

(18)

2.2 TOPSIS法综合指标构建

2.2.1构建群体智能优化算法的多属性决策矩阵

同一个算法在不同属性上以及不同算法在同一属性值上的数值存在差距，因此对相关数据进行处理，方法如下：

1) 计算精度和最优值处理，两者的值都是小数，在Matlab中当数值过小放入矩阵中会直接变为0，因此不能直接进行传参，在对值的处理上首先为三种算法创建三个计数器，初始计数器值为0，之后对属性值进行放大处理，循环放大10倍，直到属性值大于1，之后将计数器的值作为该属性的值放入矩阵中。

2) 覆盖度和覆盖速率处理，两者的值不是非常小的小数，且不同算法的同一属性值的差距并不是很大，使用计数器方法只适合两个值相差很大的情况，进行计数之后两种算法在同一属性上的差距会有所缩小，因此不使用上述计数器方法，在此不断对三种算法同时放大，每次放大10倍，直到所有的值都大于1的时候结束。

3) 其他值不作处理直接使用。

对数据值进行了上述处理，由于不同属性数据存在不同的特性，可能有的数据越大越好，有的越小越好，因此我们要统一属性值类型，使所有属性数据变为越大越好。

预处理之后计算精度和最优值由越小越好变为越大越好；覆盖度、覆盖速率、最差值和寻优成功率类型为越大越好；平均计算时间属于越小越好的类型，在此对其作倒数处理，使其变为越大越好。

使用处理结果构建多属性决策矩阵。在算法评估中共有3种算法，因此有3种方案，即m=3；算法共有7种评估属性，即n=7。算法原始多属性决策矩阵A如式(19)所示：

GWO ABC PSO

(19)

2.2.2归一化群体智能优化算法的多属性决策矩阵

已经得到算法的多属性决策矩阵A，之后计算每种属性数据的平方和sum_square，对得到的平方和求根号sum_square_root，最后求每种算法的属性在相应的sum_square_root中所占比例得到归一化矩阵B中的对应元素数据bij，在此以最优值属性的计算为例给出归一化计算的公式，则最优值属性的归一化数据b11、b12、b13计算为：

sum_square=GWO最优值+ABC最优值+ PSO最优值，

(20)

(21)

(22)

GWO ABC PSO

(23)

式(23)为归一化矩阵B，B中的其他元素的归一化计算与最优值相同，只需将属性数据值替换。

2.2.3确定正负理想解

权重不同产生的综合评估结果也不一样，这里考虑等权，认为在实际过程中7个评价指标同等重要。因此权重相同均为1/7，即：权重W中的任意元素wi(i=1,2,…,7)=1/7，在算法评估中权重矩阵C=(1/7)·B，如式(24)。目的是验证评估方法的正确性。当然，权重的确定决策者可以通过专家打分的方法获得，或者通过数据计算权重也可以根据实际需要设置指标的权重，然后再利用本文的方法评估算法的性能。

(24)

之后需要确定正、负理想解P*和P0，正理想解矩阵如式(25)，负理想解矩阵如式(26)。之前已经将所有属性都统一为越大越好的类型，属性评估每个属性的最大数据作为正理想解中的元素；每个属性的最小数据作为负理想解，计算如式(27)和式(28)。

(25)

(26)

(27)

(28)

2.2.4计算群智能优化算法到正负理想解的距离以及综合指标

根据正、负理想解以及权重矩阵可以通过式(5)和式(6)计算得到每种算法的各属性值到正、负理想解的距离，根据式(7)计算得到每种算法的综合指标大小，并通过综合指标进行排序。

在综合性能指标计算中分子部分使用的是负理想解的距离，但是也可以使用正理想解距离，二者的不同之处在于若使用负理想解，则综合指标越大越好；使用正理想解，则综合指标越小越好，最后的综合指标排序上方案的排名顺序是不变的。

3 仿真验证

3.1 三种典型群体智能优化算法概述

为了验证本文所提方法的正确性，我们选取群体智能算法中三种典型的算法：灰狼算法、人工蜂群算法和粒子群算法。

灰狼算法于2014年提出，其原理是利用灰狼寻找猎物的最佳方式[14]搜索目标，该算法搜索能力强、灵活性好、算法实现简单[15]。

人工蜂群算法[16]于2005年提出，主要利用蜜蜂寻找食物的原理搜索目标，该算法具有操作简单、控制参数少、搜索精度高、鲁棒性强[17]等优点。

粒子群算法是一种基于群的搜索过程，其中每个个体称为一个粒子，它可以记住群体和自身的最佳位置，以及速度[18]。算法具有步骤简洁、收敛速度较快、收敛精度高等优点，过早收敛、易陷入局部最优等缺点。

3.2 设置测试函数

测试函数使用的是标准测试函数，将函数分为单峰U(Unimodal)、多峰M(Multimodal)、可分S(Separable)和不可分N(Non-Separable)函数。测试中使用单峰可分函数US：Step、Shpere；单峰不可分函数UN：Rosenbrock、Schwefel绝对值；多峰可分函数MS：Rastrigin；多峰不可分函数MN：Griewank、Ackley。US和UN归于单峰函数中测试，MS和MN归于多峰函数中测试。

3.3 单峰函数下的群体智能优化算法性能排序

3.3.1三种典型算法的性能指标计算

单峰可分测试函数的可接受精度为10-17(寻优成功条件)，单峰不可分函数可接受精度中Rosenbrock为10-4，Schwefel绝对值为10-10。数值是根据提前运行4个单峰测试函数，观测三种算法的最优值而确定的数值。

三种算法循环运行100次，每个算法的种群数为50，维度为3，每个算法迭代300次，保存每次循环三种算法的7个属性值。表3为单峰测试函数的运行结果。

表3 单峰测试函数结果Tab.3 Unimodal test function results

3.3.2三种典型算法的综合排序结果

表4是三种算法在4个单峰函数上的TOPSIS数据，通过观察综合评价指标可以得出算法由7种属性构成的综合性能在不同测试函数上的性能优劣，并根据综合性能给出算法的性能排序。

表4 单峰函数正、负理想解以及综合评价指标Tab.4 The positive ideal solution and negative ideal solution of unimodal function and the comprehensive evaluation index

3.3.3仿真结果分析

表3中Step和Rosenbrock函数的平均计算时间T、计算精度A、覆盖度C、覆盖速率R、最优值B、最差值W、寻优成功率F属性中算法排序如式(29)和式(30)：

(29)

(30)

通过上述表述，单从一个属性上来说，每个属性可以得出三种算法的排名，但若多个属性一起，例如：Rosenbrock函数要求7个属性排名最好时，ABC、GWO和PSO无法比较，因为7种属性的算法排名不同，此时就很难判断ABC、GWO和PSO两种算法哪个最好。

此时，通过TOPSIS方法可以对多属性值进行计算从而得出综合评估指标，为研究者提供7种属性同时最优的选择建议。如表4中的数据排名可以得出PSO算法最好，GWO算法次之，ABC算法最差。

3.4 多峰函数下的群体智能优化算法性能排序

3.4.1三种典型算法的性能指标计算

多峰可分和多峰不可分测试函数的可接受精度为10-10，通过提前运行3个多峰测试函数观测三种算法的最优值而确定的数值。表5为三种算法在3个多峰函数上的测试数据。

3.4.2三种典型算法的综合排序结果

多峰函数的TOPSIS综合评价指标的计算过程和单峰函数相同，在此不再重复展示。表6是三种算法在多峰可分与多峰不可分函数上的TOPSIS数据。

3.4.3仿真结果分析

分析表5和表6中数据可以得出在单属性比较中可以通过单属性数据对三种算法进行排序，若多属性评估则可以通过TOPSIS方法得出综合评价指标，得出算法的排序，多峰函数中PSO算法最好，GWO算法次之，ABC算法最差。

通过上述分析可以得出TOPSIS方法是可行的，使用TOPSIS方法对多种属性进行综合评估就可以提供一种解决思路。

从表4和表6的综合指标可以得出在循环运行C=100次，每个算法的种群数为N=50，维度为D=3，每个算法迭代I=300次的条件下，4种类型的函数中PSO算法综合指标最好，GWO算法次之，ABC最差。

现在改变公共参数，观察使用TOPSIS方法评估算法的排序是否会改变，参数改变主要从以下两个方面：改变种群数量、改变迭代次数。设置C=50、N=100、D=3、I=100，增加种群数量，直接给出在单峰函数和多峰函数下的综合指标，如表7所示。

观察表7中的数据可以看出：10个函数中PSO算法最好、GWO算法次之、ABC算法最差。

表7 N=100的综合评价指标Tab.7 N=100 comprehensive evaluation index

再次改变种群数量，设置C=50、N=200、D=3、I=100，单峰函数和多峰函数下的综合指标如表8。

通过观察表8的数据可以看出在Sphere函数中GWO算法已经超过PSO算法，其他函数中PSO算法优于GWO算法，但和表7相比Rosenbrock函数中二者之间的差距变小，其他函数二者差距变大，ABC算法依旧最差。

表8 N=200的综合评价指标Tab.8 N=200 comprehensive evaluation index

改变种群数量，设置N=300，单峰函数和多峰函数下的综合指标如表9。

表9 N=300的综合评价指标Tab.9 N=300 comprehensive evaluation index

观察表9得出在Sphere函数上GWO算法优于PSO算法，在Step、Griewank和Schwefel绝对值中依旧是PSO优于GWO，但和表8相比二者之间的差值再次变小，其他函数差值变大。

通过比对表7、表8和表9的数据可以得出在种群数量在不断增大的时候GWO算法的性能越来越好，而PSO算法的性能在下降，开始出现GWO算法的综合性能优于PSO算法，虽然有部分函数PSO和GWO之间的差值变大，但是对比表8和表9，表8中有4个函数差值变大，而表9中有2个函数差值变大。ABC算法的综合性能也在增加，虽然增加的幅度不大。

改变迭代次数，增加迭代次数I=150，单峰和多峰函数下的综合指标如表10。

表10 I=150的综合评价指标Tab.10 I=150 comprehensive evaluation index

对比表7和表10的数据得出Step、Griewank、Ackley、Rosenbrock函数中PSO算法和GWO算法之间的差值减小，其他函数差值变大。

改变迭代次数I=250，函数的运行结果如表11。

对比表10和表11的数据可以看出除Rosenbrock函数外其他函数上PSO和GWO的差值在变大，且PSO的综合指标的值比表10的值要大，而GWO的值要小。

通过比对表7、表10和表11的数据可以看出在其他参数不变，迭代次数增大的情况下，PSO算法的综合指标越来越好，而GWO算法的综合指标越来越差，二者之间的差值在不断变大。

4 结论

本文提出一种基于优劣解距离法(TOPSIS)法的评估算法综合性能的方法。该方法定义了7项表示群体智能算法性能的指标，给出了指标的计算模型。通过对数据的分析可以得出三种算法在不同测试函数中每个单属性下的排名，不同的排名反映了算法的不同性能上的优劣。为了综合评估群体智能算法的性能，利用TOPSIS方法对不同算法综合性能进行排序，结合数据进行分析可以得出：

1) 在其他条件不变，种群数量不断增大的时候，GWO算法的综合性能会越来越好，PSO算法的综合性能会变差。在种群数量大到一定值的时候，GWO算法的性能会优于PSO算法，三种算法的综合性能排序会变为GWO最优、PSO次之、ABC最差。

2) 在其他条件不变，迭代次数不断增大的时候，PSO算法的综合性能会越来好，GWO算法的性能会变差，二者之间的差值会不断加大，PSO算法的性能会越来越优于GWO算法。

仿真结果表明，本文所提方法的正确性以及适用性，不仅适用于GWO、PSO和ABC三种算法的测试及排名，还能应用于其他不同算法的评估。