利用粒子群算法計算AHP判斷矩陣排序權重

張建華，李富萍

(1.中北大學電子與計算機科學技術學院，太原030051;2.太原科技大學計算機學院，太原030024)

層次分析法(AHP)是一種定性與定量相結合的多目標決策分析方法，它將人的主觀判斷為主的定性分析定量化，幫助人們在對復雜系統的思維過程中保持一致性[1-3]。在AHP中，如何合理地計算判斷矩陣的排序權重是整個處理過程的關鍵，目前常用的計算方法大多使用近似算法，例如特征值法(EM)、最小偏差(LDM)、最小平方法(GLSM)等[4]。

根據判斷矩陣的基本性質，可以將其排序權重計算歸結為一個使一致性指標最小化的最小優化問題，文獻[4]中提出檢驗判斷矩陣一致性的遺傳層次分析法(AGA-AHP)。AGA-AHP利用加速遺傳算法，在檢驗判斷矩陣的一致性的同時計算判斷矩陣的排序權重，具有較高的求解精度[5]。因為遺傳算法并不是一個連鎖學習算法，在進化過程中，由于交叉和變異操作可能破壞構造塊，從而影響計算結果的準確性。粒子群優化算法不存在連鎖學習的問題，所以對于這類復雜的優化問題，粒子群優化算法更適合。

粒子群優化算法(Particle Swarm Optimization，PSO)是一種全局優化進化算法，該算法源于對鳥群捕食行為的研究。與遺傳算法類似，PSO也是一種基于迭代的算法，它的基本思路是隨機初始化一個群體(粒子群)，然后通過迭代過程對群體中各個個體(粒子)的速度和位置進行修正，直到算法結束。在PSO中，沒有交叉和變異操作，群體中的粒子在迭代過程中追隨解空間中的最優個體進行搜索，最終找到最優解。與遺傳算法相比，不存在構造塊破壞的問題，而且PSO更容易實現、需要調整的算法參數也很少[6-8]。

本文首先分析判斷矩陣性質并對排序權重計算問題進行描述，接著介紹帶慣性權重的粒子群優化算法，然后對判斷矩陣排序權重計算進行討論，最后給出仿真實驗結果并對其進行分析。

1 排序權重計算

給定一個判斷矩陣A=(aij)n×n，如果對應的排序權重為wk，k=1，2，…，n，那么wi＞0，且:

1)單位性，aii=wi/wi=1;

2)倒數性，aji=wj/wi=1/aij;

3)一致性，aijajk=(wi/wj)(wj/wk)=wi/wk=aik.

從以上性質可以得到:

滿足式(2)的判斷矩陣是完全一致的。在實際應用當中，由于人的主觀判斷并不是完全精確的，并不能保證所有問題中的每個判斷矩陣都具有完全一致性，只需要滿足滿意的一致性就可以接受。從式(2)可以看出，等號左邊的值越小判斷矩陣的一致性程度就越高。所以，判斷矩陣的排序權重計算可以歸結為一個由式(3)所描述的最小優化問題[1]:

目前一般以判斷矩陣階數和判斷矩陣最大特征值的差異程度作為度量判斷矩陣一致性的指標。本文方法直接從判斷矩陣的性質出發，更加直觀合理。

2 帶慣性權重的粒子群優化算法

用帶慣性權重的粒子群優化算法處理式(3)所描述的最小優化問題。此算法在標準粒子群優化算法的基礎上，通過改變慣性權重隨進化過程的變化曲線來提高算法全局尋優性能[9]。

2.1 粒子群優化算法

在粒子群優化算法中，將每個個體看作在搜索空間中的一個粒子，各個粒子沒有重量和體積，并在搜索空間中以一定的速度飛行。每個粒子的飛行速度根據自身的飛行經驗和整個群體的飛行經驗動態調整[9]。

設:

Xi=(xi1，xi2，…，xin):第i個粒子的位置;

Vi=(vi1，vi2，…，vin):第i個粒子的飛行速度;

其中，f(X)為一個最小優化問題的目標函數。

假設群體中共有s個粒子，全局最優位置Pg(t)，也即群體中所有粒子所經歷過的最好位置為:Pg(t)∈ {P0(t)，P1(t)，…，Ps(t)}|f(Pg(t))=min{f(P0(t))，f(P1(t))，…，f(Ps(t))}

式(5)和式(6)描述了基本粒子群優化算法的進化方程。

式(5)和式(6)中，t代表進化過程的迭代數，j代表粒子的第j維，i代表第i個粒子，c1、c2是在0～2之間取值的加速常數，r1～U(0，1)和r2～U(0，1)分別為兩個相互獨立的取值0到1之間的隨機數。

從式(5)和式(6)的進化方程可以看出，c1的作用是調整粒子向其最優位置飛行的步長，c2用來調整粒子飛向全局最優位置的步長。vij∈[－vmax，vmax]，其中vmax=k·xmax，0.1 ≤k≤ 1.0，[－xmax，xmax]是問題的搜索空間。限制vij的取值范圍是為了降低粒子在進化過程中飛離搜索空間的可能性。

1998年，Shi Y和Eberhart R C在基本粒子群優化算法基礎上，引入慣性權重到速度進化方程中[10]，用來改善基本 PSO算法的收斂性能，如式(7)所示。

式(7)中w稱為慣性權重。慣性權重w使粒子的運動保持一定的慣性，使粒子能夠探索搜索空間中的新區域。

因為慣性權重w本身具有平衡全局和局部搜索能力的作用，所以引入慣性權重w可以去除基本

Pi=(pi1，pi2，…，pin):第i個粒子飛行路徑上的最好位置，即粒子i飛行路徑上，適應值最好的位置，稱這個位置為個體最優位置。對于最小優化問題，如果一個位置的目標函數值越小，那么該位置的適應值就越好。

粒子i的當前最優位置可用式(4)確定:PSO算法對vmax的限制。當vmax增加時，可以通過減小w來平衡搜索過程，而減小w又可以減少進化過程的迭代次數。這樣，可以將各維變量的變化范圍作為vmax的取值范圍，通過對w的調節達到相同的目的。

目前，PSO算法的相關研究大部分是在帶慣性權重PSO算法的基礎上進行擴展和修正，在很多文獻中將帶慣性權重PSO算法稱為PSO算法的標準版本，簡稱為標準PSO算法，而基本的PSO算法被稱為PSO的初始版本[9]。可以看出，當慣性權重w=1時就是PSO算法的初始版本。

2.2 改進全局尋優性能

為了改進算法的全局尋優性能，一個好的方法是在進化前期提高群體的多樣性，從而得到合適的種子，在進化后期提高算法局部尋優性能以提高計算精度。慣性權重w類似于模擬退火算法中的溫度參數，如果希望算法全局尋優能力強，那么w應取較大的值;如果希望算法具有較強的局部尋優能力，應當選擇較小的w.一般來說，在進化算法的迭代初期應當使探索范圍盡量的大，也就是強調全局尋優能力;在進化迭代的后期為了提高尋優的精度，要求算法在此階段應該具有較好的局部尋優能力。從這個角度來看，慣性權重w應該隨迭代次數的增加不斷地減少。在文獻[7]中，慣性權重w用式(8)來計算:

其中，Gmax是最大進化迭代次數，根據當前的進化迭代數確定慣性權重w[11].

本文算法中采用式(8)計算慣性權重。

2.3 完整PSO算法描述

1)為群體中的各個粒子設定隨機位置和速度進行初始值;

2)為群體中各個粒子計算適應值;

3)對群體中各個粒子，根據式(4)，確定它的當前最優位置;

4)設置當前的全局最優位置Pg為所有粒子中具有最優適應值的粒子位置;

5)對群體中各個粒子，利用式(7)和式(6)計算其速度和位置;

6)如果未達到算法結束條件，轉到2);否則結束算法。

3 判斷矩陣排序權重計算算法描述

下面給出用于解決式(3)所描述的最小優化問題的算法PSO-AHP.

1)給定一個判斷矩陣A=(aij)n×n，初始化N個向量為種群規模各分量為[0，d]上的均勻隨機數，d是一個常數，用來控制各權重的上限，取2，…，N為第一代群體;初始化N個對應的速度向量各分量為[－vmax，vmax]上均勻隨機數，算法中vmax=0.1，控制粒子一次迭代中最大的速度變化值;

3)對群體中的各個粒子，與Wi的適應值做比較，當前最優位置Wi設置為其中最好適應值對應的位置;

4)比較全局最好位置Wg以及上一步得到的Wi，i=1，2，…，N的適應值，選擇其中具有最好適應值的Wi作為當前全局最優位置Wg;

5)對群體中的各個粒子，利用式(7)和式(6)計算得到下一次迭代的

6)如果未達到算法結束條件，轉到2);否則轉到7);

7)輸出排序權重Wg=(w1，w2，…，wn)以及一致性指標CI=CIF(n，wg).

4 仿真實驗結果及分析

4.1 仿真實驗結果

仿真實驗中，使用EM方法和PSO-AHP算法計算下列兩個判斷矩陣B1和B2.

仿真實驗結果如表1所示。

從表1可以看出，對于判斷矩陣B1和B2，EM方法的計算結果表示它們是不一致的，但是PSOAHP計算卻得到一致的結論，而且一致性指標較好。在AHP中，如果一個判斷矩陣不一致，一般的做法是要求決策者重新考慮其決策數據，使判斷矩陣滿足一致性指標然后再進行計算。如果給決策者提供了錯誤的一致性信息，決策者就不得不對已經做出的正確決策進行改動，導致決策上的誤差。PSO-AHP給出準確的一致性指標能夠避免這種情況發生。

表1 仿真實驗結果Tab.1 The simulation results

4.2 與其他方法的仿真實驗計算結果對比

為了與其他算法的計算結果進行比較，用下面三個判斷矩陣進行仿真實驗，其中判斷矩陣B3具有完全一致性。

仿真實驗參數:種群規模:B3∶75，B4/B5∶150;最大代數:100.

表2是本文算法與其他幾種算法的仿真實驗結果比較，EM、LDM、GLSM以及AGA-AHP的數據來源于文獻[1]。與其他幾種算法相比，本文算法的精度最高。

表3是使用PSO-AHP進行100次獨立仿真實驗的統計數據。從表3可以看出，統計數據的均值和方差很小，說明算法的穩定性很好。

5 結論

根據判斷矩陣的基本性質，計算判斷矩陣的排序權重可以轉換為尋找最小的判斷矩陣一致性指標所對應的各指標權重。本文采用改進的粒子群優化算法對這個優化問題進行處理，通過算法的進化迭代能夠找到一致性指標的全局最優，全局最優一致性指標對應的粒子位置即為判斷矩陣的排序權重。從仿真實驗結果可以看出，本文所描述的算法具有很高的精度，并且算法的穩定性也很好。

表2 與其他方法的計算結果比較Tab.2 Comparison with other algorithms

表3 100次實驗測試結果Tab.3 The results of 100 experiments

[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]ZIA M J，AZAM F，ALLAUDDIN M.A Survey of Enterprise Architecture Analysis Using Multi Criteria Decision Making Models(MCDM)[J].Intelligent Computing and Information Science，2011，135:631-637.

[4]徐澤水.層次分析中判斷矩陣排序的新方法——廣義最小平方法[J].系統工程理論與實踐，1998，18:38-43.

[5]金菊良，魏一鳴，付強.計算層次分析法中排序權值的加速遺傳算法[J].系統工程理論與實踐，2002，22:39-43.

[6]王小平，曹立明.遺傳算法理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.

[7]ADLEMAN L M.Molecular Computation of Solutions to Combinatorial Problems[J].Science，1994，266(5187):1021-1024.

[8]SRINIVASAN，D，LOO W H，CHEU R L.Traffic incident detection using particle swarm optimization[C]∥2003 IEEE，Swarm Intelligence Symposium，2003:144-151.

[9]曾建潮，介婧，崔志華.微粒群算法[M].北京:科學出版社，2004.

[10]SHI Y，EBERHART R C.A modified particle swarm optimizer[C]∥IEEE World Congress on Computational Intelligence，Piscataway，NJ，IEEE Press，1998:69-73.

[11]SHI Y，EBERHART R C.Empirical study of particle swarm optimization[C]∥1999 Congress on Evolutionary Computation，Piscataway，NJ，IEEE Service Center.1999:1945-1950.