基于粒子群優化算法的殘缺判斷矩陣修補

李富萍，張建華

(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.