层次分析法中权重向量的算法综述

层次分析法中权重向量的算法综述

1权重向量集计算单个标准下的权重向量算法可概括为三种类型：资源向量法、优化算法和其他算法。本文统记A=[aij]n×n为判断矩阵,A*=[wi/wj]n×n为待求权重矩阵;D={w|n∑i=1wi=1,wi>0,i=1,2,⋯,n}为权重向量集;e=(1,1,…,1)T∈Rn+。1.1求特征向量的一般法特征向量法是AHP的一种基本算法。下面的Perron定理为特征向量法奠定了理论基础。定理1(Perron)记A=[aij]n×n为正矩阵,即A中全部元aij>0,ρ(A)为其谱半径,则下列论断成立:(1)A的最大特征根λmax存在、唯一,且λmax=ρ(A);(2)与λmax对应的规范化特征向量w=(w1,w2,…,wn)T为正向量,即w中每个元wi>0。对于正矩阵,有一种求特征向量的简易算法——幂法。下面的定理为幂法提供了理论依据。定理2设A>0,x∈Rn,则limk→∞AkxxΤAkx=cv其中v为与A的最大特征根对应的特征向量,c是常数。如令x=e,就有limk→∞AkeeΤAke=w(1)其中w为与A的最大特征根对应的规范化特征向量,下称权重向量或排序向量。幂法的计算步骤如下:给定精度ε>0。①取x(0)=e,令k=0。②计算x(k+1)=Ax(k)=A(k+1)e。③令βk+1=eΤx(k+1)=n∑i=1xi(k+1),计算规范化向量y(k+1)=x(k+1)/βk+1。④如成立|yi(k+1)-yi(k)|<ε,i=1,2,⋯,n,则权重向量w=y(k+1),转⑤;否则令k=k+1,返回②。⑤计算A的最大特征根λmax=n∑i=1(Aw)i/nwi(2)1.2优化算法按照扰动函数的表示方式,优化算法可分成对数最小二乘法、最小二乘法、最小偏差法与χ2法等。(1)[aij]nk定义扰动矩阵E=[εij]n×n=A˚A*Τ=[aijwjwi],其中“。”为两个矩阵的Hadamard积。构建对数最小二乘模型:minf(w)=n∑i,j=1lg2εij=n∑i,j=1[lg(aijwjwi)]2(3)w∈D经过简单运算,便得wi=[n∏j=1aij]1nn∑k=1[n∏j=1akj]1ni=1,2,⋯,n(4)显见(4)式与根法的结果相同。梁梁等应用最优传递矩阵的概念,对判断矩阵A=[aij]n×n中元作变换cij=1nn∑k=1lg[aikajk]‚再令ˉaij=10cij,构造拟优一致性矩阵ˉA=[ˉaij]n×n,赖以求出权重wj=1n∑i=1ˉaijj=1,2,⋯,n。王应明等针对判断矩阵A=[aij]n×n,定义aij为i事物对j事物的直接判断元素,aik/ajk(k=1,2,…,n)为i事物对j事物的间接判断元素,再对后者取几何平均:ˉaij=[n∏k=1aikajk]1n‚构造一致性矩阵ˉA=[ˉaij],据以求出权重wj=1n∑i=1ˉaijj=1,2,⋯,n。(2)ata的规范化定义扰动矩阵E=[εij]n×n=A-A*=[aij-wi/wj],构建最小二乘模型:ming(w)=n∑i,j=1(aij-wi/wj)2‚(5)w∈DSaaty提出了当A满秩时的一种算法:①求AAT的主特征根λ1和规范化右主特征向量p1(各元平方和为1);②求ATA的规范化右主特征向量q1;③构造矩阵Τ1=p1λ112q1Τ,对T1作一致性检验,如通过则转④,否则采用他法;④将T1的任一列规范化,即得A的权重向量w。王应明等构建了一个典型的二次型问题:minJ=zTz,s.t.Aw=nw+z,eTw=1,w>0,其解为w=DeeΤDe。式中D=[(A-nI)T(A-nI)]-1。王应明等还构建了如下的二次型问题:minJ=wTBw,s.t.eTw=1,w≥0,其解为w=B-1eeΤB-1e。其中B=[n∑i=1a2i1+(n-2)-(a12+a21)⋯-(a1n+an1)-(a21+a12)n∑i=1a2i2+(n-2)⋯-(a2n+an2)⋯⋯-(an1+a1n)-(an2+a2n)⋯n∑i=1a2in+(n-2)]证明了w>0,给出了求权重向量的一种线性规划算法。(3)程组最小偏差算法仿照对数最小二乘法,定义扰动矩阵E=[aijwjwi],构建最小偏差模型:minh(w)=12n∑i,j=1(aijwjwi+ajiwiwj-2)(6)w∈D陈宝谦给出了下面的定理和算法。定理3函数h(w)存在唯一的最小解w*∈D,它也是方程组n∑j=1aijwjwi-n∑j=1ajiwiwj=0,i=1,2,⋯,n在D上的唯一解。最小偏差算法如下:记φi(w(k))=n∑j=1aijwj(k)wi(k)-n∑j=1ajiwi(k)wj(k),i=1,2,⋯,n给定精度ε>0,任取初始权重向量w(0)={w1(0),w2(0),…,wn(0)}∈D,令k=0。①计算φi(w(k)),i=1,2,…,n,如对∀i,成立|φi(w(k))|<ε,停止,w(k)是h(w)的最小解;否则转②。②设|φl(w(k))|=maxi|φi(w(k))|,求t(k)=[∑j≠laljwj(k)wl(k)/∑j≠lajlwl(k)wj(k)]12xi(k)={t(k)wl(k),i=lwi(k),i≠lwi(k+1)=xi(k)/n∑j=lxj(k),令k=k+1,返回①。(4)求解初始权重向量定义扰动矩阵E=[εij]n×n=[aijwjwi],构建χ2模型:minr(w)=n∑i,j=1(aij-wi/wj)2wi/wj(7)w∈Dχ2法的算法如下:记φi(w(k))=n∑j=1[(1+a2ij)wj(k)wi(k)-(1+a2ji)wi(k)wj(k)],i=1,2,⋯,n。给定精度ε>0,任选初始权重向量w(0)={w1(0),w2(0),…,wn(0)}T∈D,并令k=0。①计算φi(w(k)),i=1,2,…,n。如|φi(w(k))|<ε对∀i成立,则w(k)是r(w)的最小解,停止;否则转②。②设|φl(w(k))|=maxi|φi(w(k))|,求t(k)=[∑j≠l(1+a2lj)wj(k)wl(k)/∑j≠l(1+a2jl)wl(k)wj(k)]12‚xi(k)={t(k)wl(k),i=lwi(k),i≠lwi(k+1)=xi(k)/n∑j=1xj(k),i=1,2,⋯,n令k=k+1,返回①。1.3其他算法(1)构造矩阵的计算对判断矩阵A=[aij]n×n中元作如下变换:ˉaij={aij,i≤jwi/wj,i>ji,j=1,2,⋯,n构造矩阵ˉA=[ˉaij]n×n。经过简单运算,得到求权重向量的递推算式:wi=1n-i[n∑j=i+1aijwj],i=n-1,n-2,⋯,1王莲芬针对梯度特征向量法中存在问题,提出了改进梯度特征向量法。(2)相对熵的性质定义1设xi,yi≥0(i=1,2,…,n),且1≥n∑i=1xi≥n∑i=1yi,则称φ(x,y)=n∑i=1xilgxiyi为x对y的相对熵。相对熵的主要性质如下:①n∑i=1xilgxiyi≥0;②n∑i=1xilgxiyi=0的充分必要条件,是对∀i,xi=yi。雷功炎构建了如下的相对熵数学模型:minq(w)=n∑i,j=1[lgwi-lgaijn∑k=1akj]wi,(8)w∈D应用Lagrange乘子法,推出wi=n∏j=1[aijn∑k=1akj]1n/n∑i=1n∏j=1[aijn∑k=1akj]1n‚i=1,2,⋯,n(9)2等式和相似性两算法称做等价,是指两者权重向量的计算公式相同。两算法称做相似,意指两者求权重向量的理论和方法雷同。2.1数最小二乘法等价下列数种算法具等价性:(1)应用简单的对数知识,易证文献、中结果与文献中结果相同,且均可表示成(4)式,即它们都与对数最小二乘法等价。(2)在(1)式中如令k=1,可得wi=(Ae)ieΤAe=n∑j=1aijn∑k=1n∑j=1akj,i=1,2,⋯,n这正好是和法的表示式。可见和法与幂法的一次近似等价。(3)(9)式可简化成wi=n∏j=1(aij)1n/n∑k=1n∏j=1(akj)1n,i=1,2,⋯,n与(4)式同。因此,相对熵法与对数最小二乘法等价。2.2算法的平行性将(7)式展开,得r(w)=n∑i,j=1(aij-wi/wj)2wi/wj=n∑i,j=1aij[aijwjwi+ajiwiwj-2]。显见作为w的函数,r(w)与(6)式h(w)相比,除括弧前的系数外,括弧中的表达式全同。由此推知,两种算法在原理和方法上必有其平行的结果,详见文献、。由此可得结论:χ2法和最小偏差法相似。3优化算法的共同特征3种优化算法——对数最小二乘法、最小二乘法和最小偏差法,具有如下两个共同特征。(1)计算理想值a归纳起来,扰动函数有两种基本类型:①比值型:εij=aij/[wiwj],其理想值为εij=1;②差值型:εij=aij-wiwj,其理想值为εij=0,且两者的理想值都在判断矩阵A为一致时达到。因此,3种算法目标函数f(w),g(w),h(w)的结构形式,都是为了从总体上实现扰动