基于粒子群优化算法的残缺判断矩阵修补

李富萍，张建华

(1.太原科技大学计算机学院，太原030024；2.中北大学电子与计算机科学技术学院，太原030051)

层次分析法(AHP)是定性与定量相结合的多目标决策分析方法，它将人的主观判断为主的定性分析定量化，帮助人们在对复杂系统的思维过程中保持一致性[1-2]。使用AHP进行决策时，经常有多位专家参与决策，专家根据自己的理解和评价标准对某个决策目标给出决策数据，最后集结多位专家的决策数据得出决策结果。在这个过程中，专家数据对决策结果起很大的作用。但是专家给出的数据有时并不是完全的，例如专家由于不确定或由于避嫌的原因不填写某项数据，这样就会导致根据专家数据得到的判断矩阵是不完整的，也就是存在残缺判断矩阵。在AHP中，只有完整的判断矩阵才能进行排序权重计算，所以必须对残缺判断矩阵进行修补，也就是根据专家对某个问题的其他决策数据，推测出残缺要素的数据。

对于存在残缺判断矩阵的决策，已经有不少学者进行了研究，Harker等利用等价判断矩阵的思路进行残缺判断矩阵排序权重的求解现在应用较为广泛，但是其方法并没有考虑不完全判断矩阵内含的不缺定性。文献[3]提出一种利用图论研究二元标度的不完全判断矩阵一致性度量的方法，胡培等针对1-9标度的判断矩阵，利用等价判断矩阵的思路对残缺判断矩阵一致性比例进行了研究[4]，文献[3]利用区间数的思路对不完全判断矩阵一致性和排序权重进行了分析，给出了一个权重求解模型[5-7]。

从随机优化的角度处理这个问题，根据残缺判断矩阵中已有的专家数据，在满足一致性比例条件下为残缺要素寻找最合适的值，修补后的完整判断矩阵一定满足已执行比例，可以进行进一步的排序权重计算[8]。

文中首先对残缺判断矩阵修补问题进行分析，简要介绍粒子群优化算法，然后给出基于粒子群优化算法的残缺判断矩阵修补的算法，最后给出实验结果及其分析。

1 残缺判断矩阵修补

残缺判断矩阵根据缺失要素的数量以及缺失要素在判断矩阵中的位置，可分为可接受的残缺判断矩阵和不可接受的残缺判断矩阵。如果残缺判断矩阵中任何一个缺失要素都可以通过已有的要素间接确定，那么称这个判断矩阵为可接受的残缺判断矩阵，否则为不可接受的残缺判断矩阵。一个残缺判断矩阵可接受的充分必要条件是其有向图是强连通的，也就是说，此判断矩阵去掉对角线要素的上三角矩阵中，各行和各列都至少存在一个确定要素[9]。

如果专家给出的判断矩阵不完整，同时这个残缺判断矩阵是可接受的，那么可以间接获得接受的残缺判断矩阵，可以采取计算残缺判断矩阵中残缺要素占判断矩阵要素总数的比例，如果残缺要素数量太多，那么就没有足够的专家原始数据作为调整的依据，无法进行修补。对于不可接受的残缺判断矩阵，可以设定一个最大比例，只有残缺要素数量占判断矩阵要素总数的比例小于这个最大比例才能进行调整。下面讨论满足修补条件的残缺判断矩阵修补方法。

残缺判断矩阵A是专家给出的数据不完全的判断矩阵，判断矩阵中存在缺失要素，根据1-9标度理论，缺失要素的取值应该在1/9～9之间。设缺失要素取值为 xi，xi∈[1/9，9]，i=1，2，…，n，n 为判断矩阵A中缺失的要素个数。将xi，i=1，2，…，n填入判断矩阵A中，可以得到一个特殊的判断矩阵～A.

判断矩阵 ～A的一致性比例是一个关于xi，i=1，2，…，n 的函数，

判断矩阵A中已经存在一些专家给定的数据，根据这些已有的数据，如果能够找到一组xi，i=1，2，…，n，使 f(x1，x2…xn)取最小值，那么按照 AHP判断矩阵的定义，这组 xi，i=1，2，…，n 可以作为在根据已有专家数据得到的缺失要素的取值。即，寻找一组 x1，x2…xn，使:

解决式(2)所描述的最小优化问题就可以得到缺失要素的一组最优解。

2 残缺判断矩阵修补算法

2.1 粒子群优化算法

粒子群优化算法(Particle Swarm Optimization，PSO)是一种受鸟类觅食行为启发而发展出的随机优化算法[10]。与其他随机优化算法相比，大部分随机优化问题PSO收敛速度更快，并且PSO算法简单易懂，需要调节的参数较少。

式(5)中，Gmax是最大进化迭代次数，根据当前的进化迭代数确定的惯性权重[11-12]。

2.2 残缺判断矩阵修补算法描述

1)给定一个残缺判断矩阵A，如果A可接受，转到3);

2)如果n/N ＞Rmax，其要素总数量为N，残缺要素数量为n，Rmax为残缺要素最大比例，修补失败，算法结束;

3)随机初始化 n个变量，x1，x2…xn=U(1/9，9)作为残缺要素初始值，也就是PSO算法的第一代种群，每个变量为算法中的一个粒子;相应地，初始化 n 个速度变量，控制粒子一次迭代中最大的速度变化值;

4)将x1，x2…xn填入残缺判断矩阵A中，得到完整判断矩阵，计算的一致性比例

5)对于每个粒子，将其适应值与所经历过的最好位置fi的适应值进行比较，若较好，则将其作为当前的最好位置;

6)对每个粒子，将其适应值与全局所经历的最好位置fg的适应值进行比较，若较好，则将其作为当前的全局最好位置;

7)对每个粒子，利用式(3)和式(4)对粒子的速度和位置进行计算，得到下一次迭代的x1，x2…xn;

8)算法如果达到结束条件，转到9);否则，转到4);

9)将全局最优位置fg对应的各变量填入残缺判断矩阵A中，得到修补后的判断矩阵。

基于以上原因，采用带惯性权重的 PSO算法[10]处理式(2)所描述的最小优化问题。文献[7]中给出的粒子速度和位置更新公式如下:

3 仿真实验结果及分析

判断矩阵M1和M2为完整判断矩阵，判断矩阵M1的一致性比例为0.019 9，判断矩阵M2的一致性比例为0.132 9.为了验证算法有效性，仿真实验以这两个判断矩阵为基础，删除其中一些要素然后用修补算法进行处理。

实验参数及计算结果比较如下。

算法参数:种群规模:100;最大代数:300;最大无进化代数:36.

3.1 缺失1对要素仿真实验结果

首先在两个判断矩阵中随机删除1对要素(判断矩阵为对角线互反矩阵)，得到判断矩阵 M3和M4.

3.2 缺失2对要素仿真实验结果

首先在两个判断矩阵中随机删除2对要素(判断矩阵为对角线互反矩阵)，得到判断矩阵 M5和M6.

3.3 缺失3对要素仿真实验结果

首先在两个判断矩阵中随机删除3对要素(判断矩阵为对角线互反矩阵)，得到判断矩阵 M7和M8.

3.4 仿真实验结果分析

从上面三组数据可以看出，如果专家给出的数据一致性较好，那么修补效果较好;如果专家给出的数据一致性较差，修补将按照最小化一致性比例的目标进行处理，所以得到的结果变化较大。另外，如果判断矩阵中缺失要素的数量越多，那么修补结果变化越大。

修补结果变化较大是由于PSO是一种随机优化算法，当缺失项较多或专家已有数据所能确定的一致性较差时，局部最优解的数量会增多，算法收敛到局部最优导致了这种现象发生。

4 结论

层次分析法中残缺判断矩阵的修补可以归结为一个在满足一致性比例条件下为残缺要素寻找最合适的值的优化问题。本文对残缺判断矩阵的修补进行了讨论，并对基于粒子群优化算法的残缺判断矩阵修补基本思路进行了介绍，然后给出了具体的算法描述，最后给出实验数据及其分析。仿真实验结果验证了此算法的有效性。

下一步的研究是进一步考虑残缺判断矩阵内含的不缺定性，并针对残缺判断矩阵修补问题进一步研究，增强算法全局收敛性，得到更好的修补效果。

[1]金菊良，魏一鸣.复杂系统广义智能评价方法与应用[M].北京:科学出版社，2008.

[2]SAATY T L.How to make a decision，The analytic hierarchy process[J].European Journal of Operational Research，1990，48:9-26.

[3]NISHIZAWA K.A method to find elements of cycles in an incomplete directed graph and its applications-binary AHP and Petri nets[J].Computers Math Applic，1997，33(9):33-46.

[4]胡培.不完全判断矩阵的决策方法[J].西安交通大学学报，1995，30(5):573-578.

[5]朱建军.层次分析法的若干问题研究及应用[D].沈阳:东北大学，2005.

[6]徐泽水.基于不同类型残缺判断矩阵的群决策方法[J].控制与决策，2006，21(1):28-33

[7]赵斐婓.离散互联模糊系统的分散控制及稳定性条件[J].工程数学学报，2011，28(1):37-42.

[8]王小平，曹立明.遗传算法理论、应用与软件实现[M].西安:西安交通大学出版社，2002.

[9]徐泽水.残缺互补判断矩阵[J].系统工程理论与实践，2004，24(6):93-133.

[10]曾建潮，介婧，崔志华.微粒群算法[M].北京:科学出版社，2004.

[11]SHI Y，EBERHART R C.Empirical study of particle swarm optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation，Piscataway，NJ，IEEE Service Center，1999:1945-1950.

[12]张建华，李富萍.利用粒子群算法计算AHP判断矩阵排序权重[J].太原科技大学学报，2012，33(2):149-153.