基于PSO算法的权的最小平方法

The Least Square Method of Weight Based on PSO Algorithm

摘要: 基于互反判断矩阵的决策中，权的最小平方法是确定决策变量权重的一种重要方法，通常借用拉格朗日函数去求解该模型的最优解。本文主要采用粒子群优化算法(PSO)去求解权的最小平方模型，并通过实例与拉格朗日函数法进行对比分析，说明了该算法的可行性。

Abstract: In the decision making based on reciprocal judgment matrix, the least square method of weights is an important method to determine the weight of decision variables, and Lagrange function is often used to solve the optimal solution of the model. In this paper, particle swarm optimization (PSO) is mainly used to solve the least-square model of weights, and the feasibility of the algorithm is illustrated by the comparison and analysis between an example and Lagrange function method.

1. 引言

20世纪70年代，美国匹兹堡大学T.L. Satty教授提出了层次分析法(AHP) [1]，它为解决社会日益复杂的决策问题提供了一个新的方法。层次分析法的思想是通过把复杂的问题层次化，然后对方案进行两两比较并构造相应的判定矩阵，最后通过对判定矩阵的求解，获得方案权重的优先级。目前，许多学者对求解方案权重的方法进行了研究，并提出了许多求解方法，如Crawford和Williams [2] 提出了最小二乘法，Chu等 [3] 提出了加权最小二乘法，徐泽水 [4] 提出了权的最小平方法等等。在文献 [4] 中，徐泽水借用了拉格朗日函数求解权的最小平方模型的最优解，该方法的计算过程比较复杂，特别是对于大群体决策问题比较耗时。因此，本文进一步研究求解权的最小平方模型的方法，并通过仿真实例说明所用算法的可行性。

2. 基础知识

定义2.1 [5] 设矩阵 $A={\left(a_{ij}\right)}_{n\times n}$，如果 $\forall a_{ij}>0,a_{ij}=1/a_{ji}\left(i,j\in N\right)$ 则称A为互反判断矩阵。

定义2.2 [5] 设判断矩阵 $A={\left(a_{ij}\right)}_{n\times n}$，其权重向量为 $W={\left(w_1,w_2,\cdots ,w_n\right)}^{\text{T}}$，若满足：

$a_{ij}=a_{ik}/a_{jk}\left(i,j,k\in N\right)$ (2-1)

则称A为完全一致的互反判断矩阵，且有

$a_{ij}=\frac{w_i}{w_j}$. (2-2)

然而，在实际应用中，由于决策问题的复杂性和专家受知识水平和经验的限制，专家的主观判断与事实存在一定的误差，从而导致了专家给出的互反判断矩阵很难能满足完全一致性。因此，通常情况下(2-2)式是不成立的。由 $a_{ij}\approx \frac{w_i}{w_j}$，引入一个偏差项 ${\epsilon }_{ij}$，则有 ${\epsilon }_{ij}=a_{ij}{w}_j-w_i$，构造偏差函数为：

$FW={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\left(a_{ij}{w}_j-w_i\right)}^2}}$ (2-3)

显然，为了得到合理的属性权重W，上述偏差越小越好，此方法称为权的最小平方法。由权重的约束条件，建立权重的数学优化模型如下：

$\{\begin{array}{l}\min FW={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\left(a_{ij}{w}_j-w_i\right)}^2}}\\ \text{s}\text{.t}\text{.}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_j=1}\end{array}$ (2-4)

3. 标准PSO算法

3.1. 算法的基本思想

PSO算法是由J. Kennedy和R.C. Eberhart [6] 于1995年首次被提出，它是一种基于群体的优化技术，是通过一组初始化的群体在搜索空间并行搜索。它是根据鸟群、鱼群和人类社会行为规律的模拟提出来的。在1998年，Shi Y.和Eberhart R.C.通过引入了一个惯性权重w来协调PSO算法的全局和局部寻优能力，称此方法为标准PSO算法。

粒子群算法首先是通过引入一个适应度函数来确定初始粒子的优先级，然后通过局部和全局的逐步搜素寻找粒子的最优解。如假设一个粒子群体中有M个粒子在D维空间中搜素，假定第i个粒子在t时刻的状态属性为：位置坐标为 $X_i^t={\left(x_{i1}^t,x_{i2}^t,\cdots ,x_{in}^t\right)}^{\text{T}}$，飞行速度为 $V_i^t={\left(v_{i1},v_{i2},\cdots ,v_{in}\right)}^{\text{T}}$，其中 $v_{id}\in \left[v_{\min ,d},v_{\max ,d}\right]$， $v_{\min },v_{\max }$ 分别为最小和最大的速度，个体最优位置为 $P_i^t={\left(p_{i1},p_{i2},\cdots ,p_{in}\right)}^{\text{T}}$，全局最优位置为 $P_g^t={\left(p_{g1},p_{g2},\cdots ,p_{gn}\right)}^{\text{T}}$，且 $1\le d\le D,1\le i\le M$。则粒子在t + 1时刻的位置通过如下公式进行更新：

$v_{id}^{t+1}=w{v}_{id}^t+c_1{r}_1\left(p_{id}^t-x_{id}^t\right)+c_2{r}_2\left(p_{gd}^t-x_{id}^t\right)$ (3-1)

$x_{id}^{t+1}=x_{id}^t+v_{id}^{t+1}$ (3-2)

为了提高算法的性能，在(3-1)中关于w的取值，Shi Y.采用从0.9线性递减到0.4的策略，具体计算如下：

$w=w_{\text{start}}-\frac{w_{\text{start}}-w_{\text{end}}}{t_{\max }}\times t$ (3-3)

其中， $t_{\max }$ 为当前迭代次数， $w_{\text{start}},w_{\text{end}}$ 分别为初始惯性权重和终止惯性权重。

3.2. 算法步骤

为了利用PSO方法求解(2-4)的优化模型，下面给出它的算法步骤如下：

步骤1：假定决策者给出的判断矩阵为 $R={\left(r_{ij}\right)}_{n\times n}$，并对种群N个权重向量 $W_i=\left(w_1,w_2,\cdots ,w_n\right),i=1,2,\cdots ,N$ 进行初始化，其中 $W_i\in \left[0,1\right]$。设学习因子 $c_1=2,c_2=2$，迭代次数： $T_{\max }$，惯性权重 ${\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_i}=1$， $w_{\text{start}}=0.9$， $w_{\text{end}}=0.4$， $V_{\max }=0.1$， $V_{\min }=-0.1$。初始化N个对应的速度向量 $V_i=\left(v_1,v_2,\cdots ,v_n\right)$， $i=1,2,\cdots ,N$ ；

步骤2：评价每一个粒子。对 $W_i,i=1,2,\cdots ,N$，通过(2-3)式算出 $FW\left(i\right)$ 的值，然后对群体中各个粒子与 $W\left(i\right)$ 的适应值 $FW\left(i\right)$ 做比较，并把当前最优位置的粒子 $W_i$ 设置为最好适应值所对应的位置。再与全局最好的位置 $W_g$ 做比较，最后选出最好适的应值 $W_i$ 作为当前全局最优位置 $W_g$ ；

步骤3：利用(3-1)、(3-2)和(3-3)式对粒子的速度和位置进行更新。如果

$v_i>v_{\text{max}}$ 将其设置为 $v_{\max }$，如果 $v_i<v_{\min }$ 将其设置为 $v_{\min }$ ；

步骤4：结束条件的检验.如果当前的迭代次数达到了预先设定的最大次数 $T_{\max }$，则停止迭代，否则转到步骤(2)；

步骤5：输出最优FW的值及其排序权重。

3.3. 拉格朗日乘数法

对(2-4)式引入一个拉格朗日乘子 $\lambda$，构造相应的拉格朗日函数 $L\left(W,\lambda \right)$ 如下：

$L\left(W,\lambda \right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\left(a_{ij}{w}_j-w_i\right)}^2}}-2\lambda \left({\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_j-1}\right)$ (3-4)

根据函数极值点存在的必要条件：一阶偏导数等于0。即：

$\{\begin{array}{l}\frac{\partial FW}{\partial W}={\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(a_{ik}{w}_k-w_i\right)\ast a_{ik}-{\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(a_{kj}{w}_j-w_k\right)-\lambda =0}}\\ \frac{\partial L}{\partial \lambda }={\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_j}-1=0\left(k=1,2,\cdots ,n\right)\end{array}$ (3-5)

其中 $W={\left(w_1,w_2,\cdots ,w_n,\lambda \right)}^{\text{T}}$， $m={\left(0,0,\cdots ,0,1\right)}^{\text{T}}$， $C={\left(c_{ij}\right)}_{\left(n+1\right)\times \left(n+1\right)}$

$c_{ij}=-\left(a_{ij}+a_{ji}\right),\left(i,j=1,2,\cdots ,n,i\ne j\right)$， $c_{ii}=\left(n-2\right)+{\displaystyle \underset{j=1}{\overset{n}{\sum }}{a}_{ji}^2}\left(i,j=1,2,\cdots ,n\right)$

$c_{k,n+1}=-1\left(k=1,2,\cdots ,n\right)$， $c_{n+1,k}=1\left(k=1,2,\cdots ,n\right)$， $c_{n+1,n+1}=0$

运用克莱姆法则可以求解线性方程组 $CW=m$，得到判定矩阵A的权重向量W。

4. 仿真实例及其分析

假如决策者在决策中给出的互反判定矩阵如下：

$A=\left[\begin{array}{ccccc}1& 3& 5& 4& 7\\ 1/3& 1& 3& 2& 5\\ 1/5& 1/3& 1& 1/2& 3\\ 1/4& 1/2& 2& 1& 3\\ 1/7& 1/5& 1/3& 1/3& 1\end{array}\right]$

采用拉格朗日乘数法进行求解，根据(3-4)和(3-5)式，在结合 $CW=m$，由克莱姆法解得：

$W^0={\left(0.5158,0.2025,0.0934,0.1306,0.0577,0.0564\right)}^{\text{T}}$

其中权重向量 $W=\left(0.5158,0.2025,0.0934,0.1306,0.0577\right)$，拉格朗日乘子 $\lambda =0.0564$。

把权重向量带入偏差函数(2-3)式可得 $FW=0.0564$，即最优解为0.0564。

采用PSO算法进行求解，设仿真实验参数：种群 $N=100$，维数为5维，迭代次数为200次.根据SPO的算法步骤，可求得优化模型(2-4)式的最优解为： $FW=0.0564$，权重向量： $W={\left(0.5156,0.2025,0.0932,0.1313,0.0574\right)}^{\text{T}}$。得到迭代的仿真示意图如图1所示：

Figure 1. Relation between FM and iteration

图1. FM与迭代关系

从上图可以看出，开始时FW的值随着迭代次数的增加而迅速下降，当迭代到40次时，它的值趋于平稳，之后FW的值基本不变。

5. 结果分析

对于上述两种方法求解模型(2-4)的最优解均为FW = 0.0564，得到的权重向量优先级相似，因此，说明了利用PSO算法求解权的最小平方的方法是可行的，并且它是通过一种迭代方式进行求解，对于求解大的群体决策问题，该算法更加高效。