多目标决策理论及方法 曾凤华Word下载.doc
《多目标决策理论及方法 曾凤华Word下载.doc》由会员分享,可在线阅读,更多相关《多目标决策理论及方法 曾凤华Word下载.doc(18页珍藏版)》请在冰点文库上搜索。
1.1.2多目标决策过程
多目标决策过程即解决多目标决策问题的程序步骤和总体轮廓,对问题有一个清晰的认识和总体的把握才能使问题的解决方法得以快捷、简便和正确的使用,才不致以使问题偏离解决的方向,因此,掌握多目标决策过程对多目标决策问题至关重要。
一般求解多目标决策问题的过程可归纳为以下4步:
第1步,判明系统建立(或改变)与诊断的需要,即当问题出现或情况发生变化时,决策者觉察到需要建立或改变系统趋向,从而需要诊断系统存在的问题和态势,并提出总体目标。
第2步,确定或提出问题。
将第1部中不太明确阐述的总体目标转换为适合计算的特定多目标集,并清晰明确地说明系统全部的基本要素、目标或属性的测度、系统边界和系统环境等。
第3步,建立模型和估算参数。
根据目标集和系统环境构建适宜的模型,以表示系统关键变量的组成及它们之间的逻辑关系,并进行方便有效的综合分析。
第4步,分析和评价系统方案。
根据预定的决策规则,对各个方案进行评价,选取较高效用的方案进行实施。
1.1.3多目标决策问题的关键要素
多目标决策过程的实现取决于构成决策问题的5个关键要素,它们分别为:
决策单元——是个体还是群体决策;
决策态势——是离散的还是连续的,是确定的还是非确定的;
问题的目标;
问题的属性——问题的特征及两两之间的关系和性质;
决策规则——是满意的还是最优的规则。
1.1.4多目标决策的基本理论
任何方法和途径都是建立在一定的理论基础之上的,多目标决策的理论基础就是向量优化理论与效用理论,这是由多目标决策问题的特点和性质所决定的。
在多目标问题中,决策的目的在于使决策者获得最满意的方案,而多个目标的存在使得问题复杂化,不能像单个目标那样,只要比较目标函数值的大小就能得出目标的解。
多目标问题的解往往不是唯一的,存在非劣解集,究竟谁优谁劣,一般很难做出判断,这就提出了一个向量优化的问题,即需要应用到向量优化理论。
与此同时,如何从非劣解中选出最终解,在很大程度上取决于决策者对方案的偏好和对风险的态度,即人的主观作用。
不同的决策者有不同的偏好,对同一个决策问题会作出不同的决策,这就要用到效用理论。
向量优化理论这部分内容主要介绍了有关向量优化问题的基本概念,如非劣解概念、最佳均衡解概念,单目标规划和多目标规划非劣性的Kuhn-Tucker条件;
效用理论主要介绍了序关系与偏好序的概念、期望效用理论及期望效用的存在性、效用函数的不同形式。
这部分内容大多是概念性和介绍性的内容,在此不再赘述。
1.2非劣解生成技术
多目标优化问题一般没有唯一的最优解,而是在非劣解集中选择一个最佳均衡解作为最终的解,从这个角度出发,我们可以知道,非劣解的生成是求解多目标问题的基础,只有生成非劣解集,才有可能从中选择最佳均衡解,最大限度地满足各个目标的要求。
1.2.1权重法
权重法是对不同的目标给予相应的权重,把各目标函数的加权和(或加权平均)作为总的、单一的目标函数,求得问题的最优解,这个最优解是非劣解集中的一点。
根据不同权重组合求得不同的最优解,就生成了非劣解集。
需要注意的是权重应该标准化,使其总和等于1。
设多目标优化问题
(1.1)
采用权重法则问题可转化为:
(1.2)
其中,权重行向量
(1.3)
当给定权重向量,求解可得最优解;
若是的唯一解,或每个是严格的正值,即,则可以证明是向量优化问题的一个非劣解。
不断地选择一些不同的,求解,则可得到多目标问题的若干个非劣解,形成非劣解集。
1.2.2约束法
约束法是从全体目标中选择一个作为主目标,把其余的目标函数都作为约束条件,由主目标函数和原约束条件及新增加的约束条件建立一个单目标最优化模型,通过求解这个模型得到一个最优解。
将各个目标依次选为基本目标,并不断地变换作为约束条件的目标的上限值,这样就可得到多个最优解,生成非劣解集。
1.2.3多目标线性规划的单纯形法
这种方法的计算过程类似于单目标单纯形法,在单纯形表上进行,但它的目标是多个,计算迭代程序是在极点非劣解之间转换,直到获得整个非劣解集为止。
这种方法只适用于由线性目标函数和线性约束组成的多目标问题。
除了上面3种求解非劣解的方法外,还有多目标动态规划,这一内容主要介绍了一维和多维决策变量的多目标动态规划模型、多维决策变量的动态规划模型解法以及多目标动态规划迭代算法,侧重的是一种动态的规划。
以上4种方法各有特点和使用条件以及适用的情形,在具体应用的过程中,我们应该针对不同问题选用不同的方法,充分利用各个方法的优点,避开缺点,使求解方便、快捷、准确。
1.3离散和连续多目标决策技术
之前的内容都没有考虑到决策者的偏好,从这部分开始讲的多目标决策技术都要完全依赖于决策者偏好的明确表示,决策是建立在决策者偏好的基础上作出的。
从反映多目标问题的特性来看,决策变量有离散和连续两种可能,因此多目标决策技术也可分为结合偏好的离散多目标决策技术和连续多目标决策技术。
1.3.1离散多目标决策技术
离散多目标决策技术属于方案有限和决策变量离散的决策技术,这种决策技术在现实问题中还是很常用的,因为方案有限的问题是很多的。
在学习这部分内容之前,我们先要了解两个概念:
决策矩阵、属性的规范化。
决策矩阵为决策分析提供基本信息,是各种评价分析方法的基础。
不同的目标函数一般具有不同的量纲,往往难以对各自目标的相对重要性作出比较,为了便于对具有不同量纲的多目标问题作决策分析需要将各目标(各属性)都无量纲化和归一化,常用方法有:
向量规范化方法、比例变换法以及非比例变换法。
离散多目标决策技术主要包括方案初选方法、加权决策方法、基于权重的决策方法和基于理想点的决策方法。
1.方案初选方法
对于离散多目标决策问题而言,行动方案是已知的,但并非都是非劣的,因此,应发现并剔除那些明显劣的方案,以减轻决策分析的负担。
常用的方案初选方法有优选法、连接法、分离法和字典编辑法。
每种方法都有其优点和片面性,使用时要根据具体问题选用。
2.加权决策法
加权决策法是对方案经过初选以后的被保留的方案进行决策分析,以最终得到一个满意解,它主要有层次分析法和权重调查法。
层次分析法的基本原理是首先将复杂问题层次化,构造一个递阶分析的结构模型,建立模型后,问题即转化为层次中的排序计算问题。
将每层的排序计算问题简化为一系列成对因素的判断比较,并根据一定的比率标度将判断定量化,形成比较判断矩阵。
通过判断矩阵的最大特征值及其特征向量,可计算出某层次因素相对于上一层中某一因素的相对重要性权重。
依次沿递阶层次结构由上而下逐层计算,即可计算出最低层次元素相对于最高层次的相对重要性权值,供决策者使用。
在多目标决策中,各目标相对权重的确定是多目标决策的关键,而权重的类型主要有价值权重和影响权重。
3.基于权重的决策方法和基于理想点的决策方法
基于权重的决策方法是假定各目标的权重是已知的,只要求根据这些权重和决策矩阵的信息进行决策分析,给方案排序。
课本上主要介绍了线性分配法、方案成对比较法、ELECTRE法。
每个方法都有不同的原理和计算步骤。
基于理想点的决策方法是决策者先定义一个理想方案,再定义一个距离测度,并度量方案集中的每一个方案与理想方案的偏差程度,选取一组最接近于理想方案的可行方案作为最终决策。
它主要有TOPSIS法和LINMAP法。
1.3.2连续多目标决策技术
连续多目标决策技术属于方案无限和决策变量连续的决策技术。
1.基于整体偏好的方法
基于整体偏好的方法是一种非交互式方法,主要有理想点法、目的规划法和替代价值权衡法。
理想点法可根据几种常用的模构造相应的评价函数:
距离模评价函数、带权L模评价函数、带权极大模评价函数,不同的模评价函数有不同的形式和求解方法步骤。
目的规划法是根据决策问题建立数学模型,通过模型的求解来进行决策。
替代价值权衡法是通过导出的权衡函数,在决策者与数学模型之间建立一个替代价值函数,作为两者联系的纽带,使决策者便于分析比较,从而选出合理的爱好解。
2.交互式方法
交互式方法用各种不同的迭代方式进行人机交互式问题求解,在决策者的直接或间接引导下从一个非劣解移动到另一个非劣解。
当决策者对当前求解得非劣解满意,或按方法提供的求解过程不能继续迭代时,过程结束。
这类方法有逐步法、均衡规划以及概率权重法等方法。
1.4发展中的多目标决策方法
近年来,随着社会经济的发展,决策问题越来越复杂。
为适应社会需求,出现了很多新兴的多目标决策方法,这些方法优点突出,运用范围广泛、效果佳。
1.4.1模糊综合评判法
该方法是对受多种因素影响的事物作出全面评价,评价结果不是绝对的肯定或否定,而是以一个模糊集合来表示,其模型的建立步骤如下:
(1)确定因素集,其中表示影响事物评价值得第个因素;
(2)确定因素评价集,其中表示影响事物评价值得第个等级;
(3)单因素评判,定出每个因素对于各评价等级的隶属度;
(4)确定各因素的权重,其中;
(5)综合评判。
1.4.2物元分析法
物元分析法的基本模型:
(1.4)
其中,R为n维物元,N为事物,为事物N的特征,为关于特征的量值。
物元分析法的计算步骤:
(1)建立物元矩阵;
(2)经典域与结域物元;
(3)关联函数及关联度的计算;
(4)确定各特征(评价指标)的权重;
(5)确定待评估单元对于各等级的综合关联度;
(6)待评单元的等级评定。
1.4.3模糊优选法
模糊优选法的基本思想是确定方案集关于目标集隶属于模糊概念“优”的隶属度,再根据模糊优选公式求解各方案关于优的相对隶属度,从而等到方案的优劣顺序。
它主要由以下两步:
第一步是建立相对优属度矩阵;
第二步是求解各对象的相对优属度,确定最佳方案。
模糊优选法步骤简单,方法原理容易理解,运用方便、简单、广泛。
1.4.4熵权理想点法
在没有专家权重的情况下,该方法根据被评价对象的评价指标构成的特征值矩阵来确定指标权重的方法。
当各被评价方案在指标上的值完全相同时,熵值达到最大值1的熵权为0,这说明该指标没有向决策者提供有用信息,可以考虑取消该指标;
当各被评价方案在指标上的熵值较小、熵权较大时,说明该指标向决策者提供了较多的信息,同时还说明在该问题中,各方案在该指标上具有明显的差距。
1.4.5遗传算法
遗传算法将问题域中的可能解看成是群体的一个个体或染色体,并将每个个体编码成符号串的形式,模拟达尔文的遗传选择和自然淘汰的生物进化过程,对群体反复进行基于遗传学的操作。
根据预定的目标适应度函数对每个个体进行评价,依据适者生存、优胜劣汰的进化规则,不断得到更有的群体,同时以全局并行搜索方式来搜索优化群体中的最优个体,以求得满足要求的最优解。
遗传算法运算过程包括参数的编码、初始群体的设定、适应度函数的设计、遗传操作(选择、交叉、变异)等。
基于遗传算法的基本原理,发展出了多种求解多目标优化问题的方法,如权重系数变换法、并列选择法、排列选择法、共享函数法以及混合法。
每种方法的计算步骤不尽相同,适用情形也不同,要根据具体问题选择合适的方法,尽量充分利用优点,避开缺点。
1.5多目标决策方法的实际运用
通过上述内容的学习,我们已经初步了解了一些多目标决策的方法,这一部分的内容就是通过两个运用实例来说明多目标决策技术在我们现实生活中的运用。
区域水资源开发利用涉及内容多、影响因素也多,如何合理地开发区域的水资源,使得既满足社会生产、生活对水资源的需求,又不损害水资源环境和生态平衡,这就要用到多目标区域水资源规划。
多目标区域水资源规划首先要多水资源开发次序进行决策,评价区域水资源的承载能力,再对区域的水资源进行优化配置。
对于大规模的水电站水库,水库调度至关重要。
水库调度有兴利调度、防洪调度和生态调度。
各种调度之间均存在一定的矛盾,而运用多目标决策技术、建立相应的数学模型,可以解决这些矛盾、协调好各部门之间的利益。
2微粒群算法及其在工程项目质量、费用和工期综合优化运用专题研究
工程项目管理是为使项目实现所要求的质量、所规定的时限、所批准的费用预算而进行的全过程、全方位的规划、组织、控制与协调。
在工程项目管理过程中,为了实现工程项目的经济效益和社会效益,通常研究如何在工程项目预算限度内实现工程项目的质量要求和工期要求。
许多专家希望引入最优化技术来研究工程项目多目标优化问题。
文献[1-2]将遗传算法引入工程项目优化问题,将工程项目优化变量编码,通过选择、交叉、变异等操作,实现工程项目多目标优化。
文献[3]则采用动态规划(DP)法引入工程项目优化问题,应用DP法进行工期优化。
文献[4]则应用模糊数学和遗传算法来解决工程项目资源均衡优化问题。
网络计划中引用了优化技术后,工程项目多目标优化的求解简便性都得到不同程度的提高。
但是,这些算法实现步骤大都相当烦琐,即使是备受优化技术领域推崇的遗传算法,也需要复杂的交叉、变异以及选择操作,使得这些优化技术很难满足实际优化需要,而且大多数优化技术都容易陷于局部最优,这就使解决优化问题的准确性大打折扣。
微粒群算法(ParticleSwarmOptimization,简称PSO)就是新近出现的一种仿生算法。
算法简单,容易实现,而且随机搜索的本质,使得搜索不易陷于局部最优。
下面简单介绍PSO在工程项目质量、费用和工期综合优化中的应用。
2.1微粒群算法简介
微粒群算法(PSO)是通过对简化社会模型的模拟而建立起来的。
PSO最早是由Kennedy和Eberhart于1995年提出的。
PSO算法[5]中,每个优化问题的潜在最优解都是搜索空间的一颗粒子,所有粒子都有一个由优化函数决定的适应值,每个粒子还有一个速度决定他们的飞行方向和距离。
然后粒子们就追随当前的最优粒子在解空间中搜索。
PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。
在每一次迭代中,粒子通过跟踪两个“极值”来更新自己,第一个就是粒子本身所能找到的最优解,这个解称之为个体极值;
另一个极值是整个种群目前找到的最优解,称之为全局极值。
PSO算法采用下列公式对粒子操作,也即粒子将根据如下的公式来更新自己的速度和新的位置[6,8-10]:
(2.1)
(2.2)
式中:
、为加速常数,通常;
和为随机函数值域[0,1];
为第d维度微粒搜索,速度,,如果,限定。
另外,PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置:
粒子数一般取20~40。
对于比较难的问题或者特定类别的问题,粒子数可以取到100或200。
粒子的长度由优化问题决定,即问题解的长度。
而粒子的范围由优化问题决定,每一维度可设定不同的范围。
中止条件可以按最大循环数以及最小错误要求确定[9]。
Kennedy和Eberhart提出微粒群算法后,国内外学者在研究应用这一算法过程中对该初始版本进行了不同改进,比较著名的有加入惯性权重的标准算法[7,11],引入收缩性因子的改进算法[7,8],杂交PSO算法[8],协同PSO算法[11]。
2.2微粒群算法流程
标准PSO的算法流程如图1所示[12]。
图1PSO的算法流程
2.3工程项目多目标优化
进度、费用和质量称为工程项目的三大控制目标,三者之间相互依存、相互影响,形成一个辩证的统一体。
工程费用和进度会影响工程项目的质量,反过来,工程质量目标又会对工程进度和费用有要求;
工程项目的费用会影响工程的质量和进度,反过来,工程的进度和质量目标会决定工程的费用;
工程项目的进度要求会影响工程费用和质量,反过来,工程费用预算和质量目标会影响工程进度。
工程项目控制的理想状态是同时实现合理的工期、较低的费用和较高的质量,而且资源得到均衡充分使用。
工程项目的进度、费用和质量三大目标之间的关系[13],如图2所示。
图2质量、进度与费用关系图
2.3.1工程项目进度
在工程项目实施过程中,工期历来是工程发包和承包方关注的焦点。
对工期优化即求优化模型[14]
(2.3)
为通过网络的工期优化所得的计算工期;
为用户或业主所要求的工期。
2.3.2工程项目费用
工程项目的费用优化问题是最为关注的,费用优化即要求
(2.4)
为工程费用计算值;
为工程费用计划值。
工程项目费用和工作持续时间关系[14]为:
(2.5)
为工序正常持续时间下的直接成本;
为工序持续时间压缩时费用增加率;
为工序的正常持续时间;
为工序的当前持续时间;
为奖罚系数;
为间接费用系数。
从而可根据上式优化工程项目费用。
2.3.3工程项目质量
目前国内工程项目管理相关专家在研究工程质量的量化时,为简便起见,假设单项工作的实际质量Qi是实际持续时间的线性函数,且呈正比关系,即实际持续时间越短,实际质量Qi越低。
在此基础上从而建立模型进行研究。
还有专家采用0~1的连续数值来表示一项工程的质量要求的严格程度,来简化研究工程质量的量化。
但是,应该看到,实际上这些假设虽然使得质量目标得以量化,理论和现实仍然有许多出入,如工程质量和工期的长短实际上可能并不是线性关系,质量应该还会和项目的费用有关系。
业主对不同的工程工期会有不同的质量要求,一般而言,工期改变,会引起承包商的工程费用相应改变,同时,项目工期的长短和工程费用的多少也反过来会影响工程各工序的质量,从而使工程总质量发生变化。
换句话说,工程项目费用和工程项目工期可以影响工程项目的质量。
为了研究质量的量化方程,借鉴工程费用和工程工期的函数关系,通过利用社会科学统计软件包(StatisticalPackagefortheSocialScience,简称SPSS)分析软件分析工程质量对工程工期的回归,从而建立工程质量对工程费用和工程工期的方程。
根据工程质量和工程工期、工程费用的量化关系,从而可以研究工程质量的优化。
2.3.4多目标优化模型的建立
当施工项目同时对工期、质量、费用都有要求,那么需要建立多目标规划模型。
模型建立设定条件:
(1)用户首先要确定目标,工期目标,质量目标,费用目标;
(2)用户要对三个目标设定优先等级。
从而,建立工程项目多目标优化模型如下:
2.4应用PSO解决项目优化方法
根据业主对工程项目质量、工期和费用的要求建立优化模型,实际上就是应用目标规划的思想,将多目标的问题转化为单目标问题。
在MATLAB环境中,微粒群中粒子及其速度我们都采用实数编码[15]。
粒子参数编码格式如图3所示。
其中,dimsize表示参数维度。
粒子群编码格式参见图4,其中popsize表示种群。
粒子位置各维的表示粒子速度各维的表示适应度
图3粒子参数编码格式
图4微粒群编码格式
对于PSO算法的参数,一般给定学习因子为,惯性权重w[16]从0.9线性减少到0.4,为第d维度粒子最大速度,也即搜索空间的宽度,同时根据实例确定算法微粒规模数。
按照PSO流程应用MATLAB编程。
2.5应用实例
有某工程实例,通过前期统计分析,建立了初始表1,业主要求工程在19单位时间内(月)完成,并且要求质量保证率在93%以上。
如果20个月完成,则要求质量保证率在94%以上。
施工单位要求保证工程工期和费用条件下,工程费用尽可能最低。
表1工程前期初始数据统计分析表
工序
tnij
tcij
βij
工日
紧前工作
A
8
4
3
160
/
B
7
70
C
6
180
D
5
E
2
120
F
G
150
CD
H
I
收尾
1
GHI
(1)建立模型
为了建立多目标模型,首先研究质量的量化方程。
SPSS是通过对一组观察值使用“最小二乘法”拟合,进行线性或者非线性回归分析。
本工具可用来分析单个因变量是如何受一个或几个自变量影响的。
如表2所示,表中数据为根据相似工程的工程质量、工期和费用的相互关系,由专家对该工程不同工期和费用下工程质量的评估量化。
另外,需要说明的是,在表2数据中,假设正常完工情况下,工程的质量设为100。
表2工程质量、工期和费用资料表
序号
工程质量
工程工期(月)
工程费用(千万元)
100
22
5.8
99
21.5
5.6
98
21
5.3