ahp-層次分析法是數學模組化中的常用算法,其适用于一批非常廣泛的問題,綜合來說,它是一個“層次權重決策分析方法”。客觀地講,它适用于一些有限制條件的決策選擇問題:
1. 決策有限,且隻從有限的候選決策裡選擇。
2. 決策的影響因素已知,因素的關系(包括隸屬關系和優先級關系)已知
3. 因素的關系不論客觀與否,要通過合理性校驗,即必須是合理的關系才能導出合理的決策。
以下例子以旅遊選地點為例。
步驟1.擷取目标層和決策層,對于旅遊問題來說,需要得到候選旅遊地點作為決策層,目标層為最後得出的決策。
步驟2.擷取中間層資訊。除決策層外的每一節點(包括中間層的所有節點和目标層節點),與影響它的節點相連,構造階梯層次結構,保證為一個有且僅有層與層之間連邊的分層圖。大概樣子如下(from維基):
當然,中間層可以不止一層,層與層之間也不一定是全連邊的,比如:
步驟3.構造成對比較矩陣,對每一個除最底層(決策層,所有的alternative)的節點,構造該點的成對比較矩陣。該點的成對比較矩陣的含義是所有影響它的因素兩兩之間的優先級關系。比如上圖中criterion的成對比較矩陣應是一個表示兩個subcriterion優先級關系的2x2矩陣;criterion2的成對比較矩陣則是4個藍色的subcriterion優先級關系的4x4矩陣。
而優先級關系,一般情況下隻用1~9的整數數值來表示。我想一個原因是這個關系通常是主觀得到的,過于精細或者過于大的數值都失去了意義;另一個原因在後面會提到,一般情況下設定為1~9已經足夠通過合理性(或者叫做一緻性檢驗)了。
一緻性檢驗是整個決策算法可以實施的最為重要的一步,無論你前面的元素關系和成對比較矩陣怎麼設定,如果檢驗結果很差,那麼說明優先級關系不太合理(比如a:b=3,b:c=3,a:c=1/9這種不合理的情況)。檢驗的結果主要依賴于單個矩陣的一緻性檢驗,和綜合情況的一緻性檢驗。
檢驗的目的主要是判定整個決策過程是否是基于某個近似“所有元素都有一個假想權值”的情況。該問題的本質,也就是求出這組假象的權值,使得我們可以根據這組權值輕松地作出決策。是以一緻性檢驗做的,并不是檢查是否有錯誤的優先級關系,而是檢查是否所有的優先級關系滿足或近似滿足上述“所有元素都有一個假想權值”的情況,越靠近這種情況,檢驗結果越好。
單個矩陣的檢驗的目的,就是為了定量得出該矩陣與“一緻陣”的“差距”。
所謂一緻陣a,定義上講,就是對任意i,j,k,成立aik*akj=aij。通俗地講,就是存在一組權值,a的每一個位aij都代表了權值i和權值j的比值。顯然,一緻陣是最合理的成對比較矩陣。一緻陣的例子:
ω:
ω1
ω2
ω3
ω4
ω5
a:
1
ω1/ω2
ω1/ω3
ω1/ω4
ω1/ω5
ω2/ω1
ω2/ω3
ω2/ω4
ω2/ω5
ω3/ω1
ω3/ω2
ω3/ω4
ω3/ω5
ω4/ω1
ω4/ω2
ω4/ω3
ω4/ω5
ω5/ω1
ω5/ω2
ω5/ω3
ω5/ω4
我們自己設定的矩陣一般都不是一緻陣,怎樣衡量它和一緻陣的“差距”?
先考慮這種情況,如果我們已知一緻陣,但不知道權值向量,我們怎麼通過矩陣求權向量?答案很簡單,就是求該一緻陣的最大特征根(等于n),然後求出該特征根對應的特征向量作為權值向量(各個行/列向量都對應特征根n),其實任意一行/列都能看出權向量的關系不是麼?
考慮矩陣不是一緻陣的情況,是以我們可以類似地先求出矩陣的最大特征根λ,再求出λ對應的歸一化權向量ω(以後統稱權向量)就可以了,則有aω=λω,這個稱為特征根法。歸一化的目的是為了計算每個點的實際選擇權值(每層實際和值為1),或稱到達“機率”。
可知λ≥n,在a不是一緻陣的情況下,有λ>n,是以我們可以用λ-n的數值來衡量a的與一緻陣的“差距”。由此可以定義一緻性名額:
接下來的問題是——如何判斷這個ci是合格的?
定義 随機一緻性名額ri,代表了在矩陣随機的情況下,矩陣的一緻性名額的ci的均值。當然我們不能枚舉所有可能的矩陣,是以用随機構造大量成對比較矩陣的方法來近似得到這個均值。
定義 一緻性合格比Δ,隻要我們構造的那個成對比較矩陣的ci<ri*Δ,就可以認為我們的矩陣是通過一緻性檢驗的,即它是合理的。一般取Δ=0.1。不太恰當但通俗地說,如果你構造的矩陣a,它與一緻性矩陣的“差距”比随機情況下的“差距”乘上Δ還要小,我們認為a是合格的成對比較矩陣。
我們已經可以判斷每一個成對比較矩陣是否是“合理”的了,那麼怎麼判斷它們綜合起來是否合理呢?
現在所有成對比較矩陣均是合理的,那麼對于目标層和第一中間層來說,已經可以求出第一層的到達“機率”,也就是我們求得的目标層權向量,它代表了第一層中間層的每一個元素對于目标層的“重要性”,那麼對于第二中間層來說,每個元素的“重要性”是通過目标層的權向量和第一層每個元素的權向量權重相乘得到的。我們要求的就是決策層的到達“機率”
另外一個考量就是,因為可以通過每層的權向量和層與層之間的連邊關系求出最後一層的到達“機率”了,是以最後一層(決策層)的到達“機率”就足以決定目标層的決策了。這也符合我們的預期:從決策層找到權值最大的一個最為目标層的決策。是以檢驗步驟最後的最後,就是檢驗決策層的權向量是否“合理”。
利用已經計算出的一些ci、ri值,定義
其中這m個ci和ri值分别是最後一層中間層(決策層的上一層)的成對比較矩陣的ci和ri值。隻要cr <Δ,就認為通過了綜合情況的一緻性檢驗。
如果構造的成對比較矩陣通過了一緻性檢驗,那麼可以直接用決策層的到達“機率”,取出值最大的決策就可以了。如果通不過一緻性檢驗,則應該考慮重新統計每個成對比較矩陣了。不合理的優先級關系導出的最優決策是不适合作為最優決策的。
由于是樹形層次結構,我們隻要從目标層廣度周遊所有點,求出決策層的到達“機率”就可以了。理論上我們應該選擇到達“機率”最大的決策作為目标決策。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct node{
int child[256]; //每個節點的兒子數字,child[0]為兒子個數
char name[256]; //節點的名稱
double** comp; //該節點機率下的下一層成對比較矩陣
double ci; //ci值
double* w; //最大特征值對應的特征向量
double p; //到達該節點的機率
double value; //隻對方案層有效,選取該方案的權重
}* node;
struct level{
int num, start_id;//每一層的點數,和起始點的編号
}* l;
int n_level, n_node; //總層數,總點數
/*
* 初始化經驗ri數組
*/
double ri[12]={0,0,0.58,0.9,1.12,1.24,1.32,1.41,1.45,1.49,1.51};
* 尋找字元c在字元串s中的位置,不存在傳回-1
*/
int pos(char c, char* s){
int len = strlen(s);
for (int i = 0; i < len; i++){
if (s[i] == c) return i;
}
return -1;
}
* 讀入一個double或者分數形式的數字
void myscanf(double* p){
char value[256];
scanf("%s",value);
int place;
if ((place = pos('/', value))>0){
int f = 0, b = 0;
for (int i = 0; i < place; i++){
f = f * 10 + value[i] - '0';
}
for (int i = place + 1; i < strlen(value); i++){
b = b * 10 + value[i] - '0';
*p = 1.0 * f / b;
} else{
*p = 0;
for (int i = 0; i < strlen(value); i++){
*p = *p * 10 + value[i] - '0';
}
* 資料輸入過程
void input()
{
printf("輸入總層數,包括目标層和方案層:\n");
scanf("%d", &n_level);
printf("已輸入\n");
l = new level[n_level];
n_node = 0;
printf("從上往下,輸入每層個數:\n");
for (int i = 0; i < n_level; i++){
scanf("%d",&l[i].num);
l[i].start_id = n_node;
n_node += l[i].num;
}
node = new node[n_node];
printf("從上往下,輸入每層屬性名:\n");
for (int i = 0; i < n_node; i++){
node[i].child[0] = 0;
node[i].p = 0;
node[i].value = 0;
scanf("%s",node[i].name);
printf("從上往下,輸入層與層之間的關系矩陣:\n");
for (int i = 0; i < n_level - 1; i++){
for (int j = 0; j < l[i].num; j++)
for (int k = 0; k < l[i+1].num; k++){
int ifconnect;
scanf("%d",&ifconnect);
if (ifconnect){
int cur = l[i].start_id + j;
node[cur].child[0]++;
node[cur].child[node[cur].child[0]] = l[i+1].start_id + k;
}
}
printf("從上往下,輸入成對比較矩陣:\n");
for (int j = 0; j < l[i].num; j++){
int cur = l[i].start_id + j;
int size = node[cur].child[0];
node[cur].comp = new double*[size];
for (int k = 0; k < size; k++) node[cur].comp[k] = new double[size];
for (int li = 0; li < size; li++)
for (int lj = 0; lj < size; lj++)
myscanf(&node[cur].comp[li][lj]);
* 程式中止,并輸出原因
void alert(char* p){
printf("%s回車退出\n", p);
freopen("con", "r", stdin);
system("pause");
exit(0);
* n階矩陣matrix和w相乘,并歸一化w
* retdiv為歸一化的倍數,傳回歸一化後的矩陣
double* normalize(double** matrix, double* w, int n, double* retdiv){
double* ret = new double[n];
for (int i = 0; i < n; i++) ret[i] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
ret[i] += matrix[i][j] * w[j];
double sum = 0;
for (int i = 0; i < n; i++) sum += ret[i];
for (int i = 0; i < n; i++) ret[i]/=sum;
*retdiv = sum;
return ret;
* 檢查節點編号為id的節點的成對比較矩陣是否通過一緻性檢驗
bool checkcr(int id){
double** matrix = node[id].comp;
int n = node[id].child[0];
double *w = new double[n], *w_new = new double[n];
for (int i = 0; i < n; i++) w_new[i] = 1;
double eps = 1e-10;
double* retdiv = new double;
w_new = normalize(matrix, w_new, n, retdiv);
while (true){
w = w_new;
w_new = normalize(matrix, w, n, retdiv);
bool flag = true;
for (int i = 0; i < n; i++)
if (w[i] - w_new[i] > eps || w[i] - w_new[i] < -eps){
flag=false;
break;
}
if (flag) break;
node[id].w = w_new;
double ans= 0;
ans += w_new[i]/w[i];
ans = ans * (*retdiv) / n;
double ci = (ans - n)/(n-1);
node[id].ci = ci;
if (ci < 0.1 * ri[n]) return true;
return false;
* 所有單排序權向量的一緻性檢驗
void checksinglematrix(){
if (!checkcr(cur)) {
printf("第%d層%d号元素<name: %s>的成對比較矩陣無法通過校驗,請重新設計",
i, j, node[cur].name);
alert("");
* 總排序權向量的一緻性檢驗
void checktotal(){
double cr = 0;
node[0].p = 1;
/*
* 計算最後一層中間層的到達機率,即“重要性”
*/
for (int i = 0; i < n_level - 2; i++){
for (int k = 1; k <= node[cur].child[0]; k++){
int child = node[cur].child[k];
node[child].p += node[cur].p * node[cur].w[k-1];
int cl = n_level - 2;
double sumaci = 0, sumari = 0;
for (int j = 0; j < l[cl].num; j++){
int cur = l[cl].start_id + j;
sumaci += node[cur].p * node[cur].ci;
sumari += node[cur].p * ri[node[cur].child[0]];
cr = sumaci / sumari;
printf("cr值: %.5lf\n",cr);
if (cr >= 0.1){
alert("無法通過總排序權向量的一緻性檢驗,請重新設計\n");
printf("檢驗通過\n");
};
* 根據經檢驗後的權重,設計最終方案,比較并選擇最優解。
void design(){
for (int k = 1; k<= node[cur].child[0]; k++){
int child = node[cur].child[k];
node[child].value += node[cur].p * node[cur].w[k-1];
cl = n_level - 1;
double maxvalue = -1e10;
int maxplace = -1;
if (node[cur].value > maxvalue){
maxvalue = node[cur].value;
maxplace = cur;
printf("<%s>: %.5lf ", node[cur].name, node[cur].value);
printf("\n\n");
printf("最優方案為<%s>, 權重為<%.5lf>\n", node[maxplace].name, node[maxplace].value);
* 整個計算過程
void calc(){
printf("單排序權向量一緻性檢驗\n");
checksinglematrix();
printf("總排序權向量一緻性檢驗\n");
checktotal();
printf("計算方案權值\n");
design();
int main()
freopen("level_input.txt","r",stdin);
input();
calc();
3
1 5 3
決策
景色 費用 居住 飲食 旅途
蘇州 杭州 桂林
1 1 1 1 1
1 1 1
1 1/2 4 3 3
2 1 7 5 5
1/4 1/7 1 1/2 1/3
1/3 1/5 2 1 1
1/3 1/5 3 1 1
1 2 5
1/2 1 2
1/5 1/2 1
1 1/3 1/8
3 1 1/3
8 3 1
1 1 3
1/3 1/3 1
1 3 4
1/3 1 1
1/4 1 1
1 1 1/4
4 4 1