基于DS/AHP的決策方法改進(jìn)

賀 彥， 熊才權(quán)

(湖北工業(yè)大學(xué)計算機學(xué)院， 湖北 武漢 430068)

由于客觀事物的復(fù)雜性、不確定性以及人類思維的模糊性，對不確定信息下多屬性決策(Multi-attribute decision making, MADM)問題研究已引起了人們的極大關(guān)注．多屬性決策問題通常需要決策者在若干不同的屬性上對決策方案表達(dá)偏好信息, 常用的分析方法有多屬性效用理論[1](Multi-attribute utility theory)和層次分析法[2](Analytic Hierarchy Process, AHP)等．而對于不確定性問題的處理, 證據(jù)理論(Dempster-Shafter Theory)能夠通過信任函數(shù)和似然函數(shù)很好地進(jìn)行解決，顯示出了很好的應(yīng)用前景．Beynon等[3,4]將證據(jù)理論與層次分析法相結(jié)合，提出了一種DS/AHP的多屬性決策方法，給解決不確定多屬性決策問題提供了一種新的思路．但是其對基本概率分配函數(shù)(BPA)進(jìn)行計算和合成時比較復(fù)雜，為此本文在Beynon等人提出的DS/AHP方法之上提出了一種新的基本概率分配函數(shù)的計算和合成方法，此方法能降低原有方法的時間復(fù)雜度，其最終合成結(jié)果也具有直觀性，最后給出一個算例來證明此方法是有效的．

1 基本證據(jù)理論

證據(jù)理論(又稱D-S證據(jù)理論)由Dempster于1967年提出[5]，并由他的學(xué)生Shafer對其進(jìn)行推廣和完善[6]．該理論除了可以表達(dá)由隨機性引起的不確定性外，還可以描述由不確切知道和信息不完全所導(dǎo)致的不確定性．下面給出幾個證據(jù)理論的主要定義.

基本概率分配(basic probability assignment)函數(shù)，即Mass函數(shù)，該函數(shù)映射冪集合中的每一個元素成為區(qū)間[0,1]的一個實數(shù)．函數(shù)的形式化描述為：M：2[0,1]，一般滿足下列關(guān)系：

1)空集合的Mass通常被定義為0(zero)，M()=0．

其中對于任何一個集合A∈2，如果M(A)≠0，則A稱為焦元(focal element)．

信任函數(shù)Bel(A)表示對命題A為真的信任程度，且

似真函數(shù)Pl(A)表示A為非假的信任程度，且

信任函數(shù)Bel(A)和似真函數(shù)Pl(A)也可稱為上下界函數(shù)，由它們組成的區(qū)間[Bel(A)，Pl(A)]叫做證據(jù)區(qū)間EI(Evidence Interval)．

在實際的問題中，往往可能同樣的證據(jù)得到了不同的概率分配函數(shù)，我們希望組合所有概率分配函數(shù)以產(chǎn)生一個更好的信任評價．假設(shè)M1和M2是同一證據(jù)的兩個概率分配函數(shù)，其證據(jù)組合為M=M1?M2，則有

M() = 0

當(dāng)合成證據(jù)的概率分配函數(shù)為多個時，例如：M1,M2, …,Mn，同理，可以根據(jù)合成規(guī)則M=M1?M2?…?Mn合成如下：

M()=0，

其中

2 DS/AHP方法

DS/AHP方法是Beynon等人利用證據(jù)理論組合規(guī)則,將AHP方法改造成適應(yīng)于解決不確定信息問題的方法,以減少計算量,其方法同AHP方法有相似之處．Beynon針對不同屬性下有限方案的部分偏好信息集結(jié)問題，將證據(jù)理論和層次分析法相結(jié)合，提出了DS/AHP方法，很好的解決了AHP方法中的問題．Beynon的方法計算過程如下：

步驟1 針對需要解決的問題，把它細(xì)分為目標(biāo)、屬性和方案，不過這里與AHP方法不同的是，最底層的方案層不是單個元素，而是決策者對某個屬性的方案和方案集的列舉．

步驟2 求出各層次上的權(quán)重系數(shù)，一般從高層到低層．假設(shè)某個屬性S的權(quán)重為P，相關(guān)的下一層的方案為F1,F2, … ,Fn，針對這個屬性S，每一個方案與識別框架Θ上的方案進(jìn)行比較，比較的結(jié)果構(gòu)成了一個判斷矩陣，判斷矩陣的取值用0-6標(biāo)度值表示．這樣可以求出判斷A的最大特征值λmax，λmax的標(biāo)準(zhǔn)化特征向量為w=[w1,w2,…,wn]T，即為各個方案相對應(yīng)的屬性S的重要性排序．

其中ɑin是第i個方案與識別框架Θ的方案比較值．1表示與自己本身比較的結(jié)果；0表示無法區(qū)分焦元之間的相對重要程度．

步驟3 把S屬性的權(quán)重影響加入矩陣中得到新的判斷矩陣A’．具體的方法就是與各個權(quán)重值相乘．對修改后的判斷矩陣A’求出最大的特征值λmax的特征向量，w=[w1,w2,…,wn]T，這里的特征向量w即是各個方案的基本概率分配函數(shù)BPA．

步驟4 將上一步求出的各個基本概率分配函數(shù)用經(jīng)典的證據(jù)理論合成法則合成，會得到一個總的BPA函數(shù)m，再求出各個方案的不確定性區(qū)間[Bel(X),Pl(X)]，則決策者可選取信任函數(shù)值最高和似然函數(shù)值最高的方案作為備選，再根據(jù)給出的決策規(guī)則，選出最佳方案．

3 DS/AHP方法的改進(jìn)

3.1 BPA計算的改進(jìn)

對于已經(jīng)構(gòu)造出的判斷矩陣，由于它的對角線、最后一行和最后一列才具有方案與識別框架的比較數(shù)值，那么對于這個特殊的矩陣，可以根據(jù)矩陣初等變換的性質(zhì)，直接得到一個一般結(jié)果的公式，而不用一步步計算，推導(dǎo)出的結(jié)果公式是：

對于一個有n-1個方案正實數(shù)的矩陣A，其與識別框架Θ構(gòu)成一個n階判斷矩陣An+1，那么可以根據(jù)矩陣的初等變換有：

當(dāng)屬性的權(quán)重值已知時，那么這個屬性的基本概率分配函數(shù)值

3.2 BPA合成的改進(jìn)

本文提出一種按權(quán)重比例轉(zhuǎn)化的方法，對BPA的合成方法進(jìn)行了修改，使之能和DS/AHP方法一樣進(jìn)行決策，還能大大減少計算量．此方法的步驟是：在求出BPA之前的步驟和DS/AHP相同，求出各個屬性的每個方案的BPA之后，按權(quán)重比例對每個方案的BPA進(jìn)行轉(zhuǎn)化，轉(zhuǎn)化方法就是每個方案中的元素占識別框架Θ的元素的比例再乘以每個方案中包含這個元素的BPA，結(jié)果即是這個焦元的BPA．具體的形式化表述為：

設(shè)有一個識別框架Θ={A1,A2,…,An}，對于某個屬性下的方案集，其BPA分別為m1,m2, …,mi,mΘ，第k個元素Ak(1≤k≤n)的BPA轉(zhuǎn)化公式為

mP({Ak})=a1m1+a2m2+…

當(dāng)有n個屬性和m個方案的時候，Dempster合成要對每兩兩屬性下的方案的BPA進(jìn)行合成，合成的時間復(fù)雜度為O(mn)，而本文改進(jìn)的方法不論方案集Θ有多大，只用對每個方案所占權(quán)重比例進(jìn)行分配，時間復(fù)雜度始終是O(n)．可以看出這種轉(zhuǎn)化合成BPA方法比用Dempster合成方法在計算量上要少了很多．具體的時間復(fù)雜度比較見圖1.

圖 1 時間復(fù)雜度比較圖

3.3 合成結(jié)果的改進(jìn)

從DS/AHP方法的最后一個步驟可以看出，雖然DS/AHP方法在一定程度上解決了AHP方法的兩兩方案比較次數(shù)過多的問題，但是它的合成結(jié)果不能直接給出最優(yōu)的決策方案，而只是給出了一個初步的篩選．針對這一點，在原有的BPA合成方法之上，提出了一種新的處理方法．

由上節(jié)計算出按權(quán)重比例進(jìn)行轉(zhuǎn)化的BPA值，這些值能構(gòu)成一個m×n階BPA矩陣，然后與已知的每個屬性的權(quán)重組成的1×m階權(quán)重矩陣做矩陣乘法運算即可得到最終每個方案的支持度．具體計算過程如下：

4 算例分析

問題描述：設(shè)有一個對公司綜合評估選取各項綜合評估值最高的決策問題，下面有四家公司，要對四個公司的員工薪水、工作時間、公司環(huán)境、發(fā)展前景四個角度進(jìn)行衡量．

對給出的問題進(jìn)行形式化建模，設(shè)有識別框架上的所有的方案集，集合為Θ={A,B,C,D},代表了A,B,C,D四家公司，決策的屬性集S={S1,S2,S3,S4}分別代表了考慮的角度，其中S1=薪水,S2=工作時間,S3=公司環(huán)境,S4=發(fā)展前景．然后根據(jù)各個公司的員工對心目中各個屬性的重要程度給出了屬性的判斷矩陣(表1，表2).

表1 決策合適程度量化表

表2 屬性S的判斷矩陣

根據(jù)矩陣?yán)碚摰某醯茸兓梢郧蟮米畲筇卣髦郸薽ax=4.102，對應(yīng)這個特征值的特征向量即為各個屬性的權(quán)重(表3).

表3 屬性的權(quán)重值

由公式進(jìn)行一致性檢驗，求得CR=0.034<0.1，所以滿足屬性間的一致性．然后根據(jù)各個公司的員工對每個公司各項屬性的了解，給出了公司選擇問題的決策矩陣，接著構(gòu)建每個屬性中的方案的集合(表4).由層次結(jié)構(gòu)模型(圖2)，再加上決策者對應(yīng)的偏好可以得表5.

表4 公司各屬性的描述

*表示不知道

圖 2 層次結(jié)構(gòu)模型

表5 不同屬性下的表現(xiàn)度

根據(jù)不同屬性下的表現(xiàn)度可以構(gòu)造相應(yīng)的知識矩陣(表6-9)．

表6 薪金的判斷矩陣

表7 工作時間的判斷矩陣

表8 公司環(huán)境的判斷矩陣

表9 發(fā)展前景的判斷矩陣

構(gòu)造知識矩陣，首先計算各知識矩陣的特征向量，并把不同影響因素的影響因子看作是相互獨立的證據(jù)源，把不同影響因素下知識矩陣的特征向量求歸一化作為決策的基本概率分配，經(jīng)過本文改進(jìn)了的BPA的計算方法處理，計算結(jié)果見表10.

表10 各知識矩陣的BPA

對各個屬性下的方案按權(quán)重比例轉(zhuǎn)化，轉(zhuǎn)化結(jié)果為：

根據(jù)上節(jié)的各個BPA值和各個屬性權(quán)重進(jìn)行矩陣運算得表11.由此可見4個公司的排序為：D > C > B > A．表示D公司的員工對公司的評價最高．如果按照原有的DS/AHP算法，用Dempster的合成規(guī)則進(jìn)行合成，得表12.

表11 Beynon方法計算得BPA

表12 BPA函數(shù)

從表12可以看出，{D}獲得了最多的權(quán)重指派，其次是{C}，再是{AC}，{B}，{Θ}和{A}．排序表為{D}>{C}> {AC}>{B}>{Θ}>{A}，可見若不加入更多的信息，傾向于D公司的員工對自己的公司評價最高，這與之前使用本文改進(jìn)的方法得出的結(jié)論一致．而本文的方法時間復(fù)雜度卻降低了．

5 結(jié)束語

本文對原有的DS/AHP方法改進(jìn)只是修改了BPA合成的計算步驟，直接根據(jù)決策者給出的偏好信息求出了最后的決策結(jié)果，可能從某些方面加大了決策風(fēng)險．而原有的DS/AHP方法根據(jù)備選方案集和對應(yīng)的偏好信息，一步步對這些方案的影響程度進(jìn)行更新，最終求出各個方案的影響程度，這樣可以有效降低決策風(fēng)險．決策者應(yīng)審慎思考這一風(fēng)險因素,根據(jù)實際情況采用不同的方法．

[參考文獻(xiàn)]

[1] 徐志新, 奚樹人, 曲靜原. 核事故應(yīng)急決策的多屬性效用分析法[J]. 清華大學(xué)學(xué)報(自然科學(xué)版),2007(3): 448-451.

[2] Saaty T L. The analytic hierarchy process[M]. New York: McGraw-Hill, 1980.

[3] Beynon M J, Bruce Curry, Peter Morgan. The Dempster-Shafer theory of evidence: An alternative approach tomulti-criteria decision modeling[J]. Omega, 2000, 28(1): 37-50.

[4] Beynon M J. DS/AHP method: A mathematical analysis, including an understanding of uncertainty[J]. European J of Operational Research, 2002, 140(1): 148-164.

[5] Dempster A P. A generalization of bayesian inference (with discussion)[J]. Journal of the Royal Statistical Society Series B, 1968, 30 (2): 205-247.

[6] Shafer G. A mathematical theory of evidence[M]. Princeton: Princeton University Press, 1976.