賀 彥， 熊才權(quán)

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

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

1 基本證據(jù)理論

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

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

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

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

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

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

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

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

M() = 0

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

M()=0，

其中

2 DS/AHP方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算例分析

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

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

表1 決策合適程度量化表

表2 屬性S的判斷矩陣

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

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

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

表4 公司各屬性的描述

*表示不知道

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

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

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

表6 薪金的判斷矩陣

表7 工作時(shí)間的判斷矩陣

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

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

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

表10 各知識(shí)矩陣的BPA

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

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

表11 Beynon方法計(jì)算得BPA

表12 BPA函數(shù)

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

5 結(jié)束語

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

[參考文獻(xiàn)]

[1] 徐志新, 奚樹人, 曲靜原. 核事故應(yīng)急決策的多屬性效用分析法[J]. 清華大學(xué)學(xué)報(bào)(自然科學(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.