AHP-层次分析法(C++源码,附详细注释和样例)
2023-09-14 09:02:09 时间
AHP-层次分析法是数学建模中的常用算法,其适用于一批非常广泛的问题,综合来说,它是一个“层次权重决策分析方法”。客观地讲,它适用于一些有限制条件的决策选择问题:
1. 决策有限,且只从有限的候选决策里选择。
2. 决策的影响因素已知,因素的关系(包括隶属关系和优先级关系)已知
3. 因素的关系不论客观与否,要通过合理性校验,即必须
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的比值。显然,一致阵是最合理的成对比较矩阵。一致阵的例子:
ω:
先考虑这种情况,如果我们已知一致阵,但不知道权值向量,我们怎么通过矩阵求权向量?答案很简单,就是求该一致阵的最大特征根(等于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 Δ,就认为通过了综合情况的一致性检验。 一致性检验:如果通不过一致性检验 如果构造的成对比较矩阵通过了一致性检验,那么可以直接用决策层的到达“概率”,取出值最大的决策就可以了。如果通不过一致性检验,则应该考虑重新统计每个成对比较矩阵了。不合理的优先级关系导出的最优决策是不适合作为最优决策的。
得出决策 由于是树形层次结构,我们只要从目标层广度遍历所有点,求出决策层的到达“概率”就可以了。理论上我们应该选择到达“概率”最大的决策作为目标决策。
printf("第%d层%d号元素 name: %s 的成对比较矩阵无法通过校验,请重新设计",
printf("最优方案为 %s , 权重为 %.5lf \n", Node[maxPlace].name, Node[maxPlace].value);
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的比值。显然,一致阵是最合理的成对比较矩阵。一致阵的例子:
ω:
先考虑这种情况,如果我们已知一致阵,但不知道权值向量,我们怎么通过矩阵求权向量?答案很简单,就是求该一致阵的最大特征根(等于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 Δ,就认为通过了综合情况的一致性检验。 一致性检验:如果通不过一致性检验 如果构造的成对比较矩阵通过了一致性检验,那么可以直接用决策层的到达“概率”,取出值最大的决策就可以了。如果通不过一致性检验,则应该考虑重新统计每个成对比较矩阵了。不合理的优先级关系导出的最优决策是不适合作为最优决策的。
得出决策 由于是树形层次结构,我们只要从目标层广度遍历所有点,求出决策层的到达“概率”就可以了。理论上我们应该选择到达“概率”最大的决策作为目标决策。
printf("第%d层%d号元素 name: %s 的成对比较矩阵无法通过校验,请重新设计",
printf("最优方案为 %s , 权重为 %.5lf \n", Node[maxPlace].name, Node[maxPlace].value);
相关文章
- C++设计模式2-原型模式Prototype
- (C++)关于拷贝构造函数 Copy Constructor
- C++编程技巧(长期更新)
- C++ code:数值计算之矩形法求解积分问题
- 《安富莱嵌入式周报》第293期:SEGGER开源其C/C++库源码emRun,丰富EMC电磁兼容资,OTA开源组件,2022 Github全球报告,内存安全指南
- Matlab与C++混合编程 编写独立外部应用程序时出现“无法定位序数3906于动态链接库LIBEAY32.dll上”错误
- c++模板学习11之类模板与友元
- AHP-层次分析法(C++源码,附详细注释和样例)
- 【华为OD机试 2023最新 】 探索地块建立(C++ 100%)
- 【Android 内存优化】Android 原生 API 图片压缩原理 ( 图片质量压缩方法 | 查找 Java 源码中的 native 方法对应的 C++ 源码 )
- Microsoft Visual C++ Runtime Library Runtime Error的解决的方法
- C++11使用using定义别名(替代typedef)
- AI模型设计:配置C++版本pytorch(libtorch 1.12)开发环境以及demo源码的实现
- VC++几种加载图片方法的讨论(附源码)
- VC++详解Base64编解码原理以及Base64编解码接口实现(附源码)
- VC++获取Windows操作系统的语言版本(附源码)
- VC++调用PostThreadMessage给线程发消息,实现线程间的通信(附源码)
- VC++将位图中保存的图像灰化(附源码)
- VC++屏幕捕获并保存成图片(附源码)
- VC++ 功能强大的API函数FindFirstFile使用介绍(附源码)
- VC++托盘图标实现类封装及使用(附源码)
- VC++ 获取CPU的型号、主频和核数(附源码)
- VC++年月日时间和64位时间的使用及相互转换(附源码)
- VC++两万字总结Windows系统中的Layered分层窗口技术(附源码)
- BDB c++例子,从源码编译到运行
- PAT 1122 C++ 版
- PAT 1150 C++ 版
- C/C++学习笔记 dlib中的base64编码源码分析
- 比较C++中的4种类型转换方式