无决策属性的多属性决策权重融合方法

毕 业 设 计（论 文）题 目： 无决策属性的多属性决策权重融合方法 毕业设计(论文)任务书题目无决策属性的多属性决策权重融合方法任务与要求预期达到的技术目标:能够运用粗糙集理论对权重融合目标建立一个规划方程，并给出一个解决方法，该方法要可用于实际问题模型中，解决实际问题。最后，应给出一个实例。预期解决的技术方面的问题及解决方法：针对多属性决策中属性权重的两种确定方法，建立了一个权重融合目标规划方程，给出了一种智能化的权重融合解决方法，该方法避免了在权重融合是引入认为偏重系数影响，是多属性决策属性权重的融合或集成合理化。毕 业 设 计 (论文) 工 作 计 划 题目 无决策属性的多属性决策权重融合方法 工作进程： 起 止 时 间工 作 内 容3月10日至3月20日 查阅粗糙集理论的相关资料3月21日至3月28日 对粗糙集理论的理解与掌握3月29日至4月11日 对粗糙集理论进行更深层的理解与掌握4月12日至4月25日 学习遗传算法，并运用粗糙集理论进行问题论证4月26日至5月09日 对问题进行数学建模，并求解5月10日至5月23日 对整体进行进一步修改5月24日至6月04日 撰写论文6月05日至6月10日 准备论文答辩主要参考书目(资料)(1)安利平.基于粗集理论的多属性决策分析M.北京:科学出版社，2008,14-15.(2)李荣钧.模糊多准则决策理论与应用M.北京:科学出版社，2002,143-147.(3)元昌安，邓松，李文敬，刘海涛等.数据挖掘原理与SPSS应用宝典M.北京:电子工业出版社，2009,221-228,268-277.。主要参考书目(资料)1、林成龙，孙即祥。粗糙集理论在决策判断中的应用。国防科技大2、孟祥萍，鞠传香，王贤勇，任纪川。粗糙集理论程学院、东北电力大学。3、余扬。基于粗糙集理论的决策分析。广东工业大学应用数学学院。主要仪器设备及材料微型计算机一台微型计算机一台论文(设计)过程中教师的指导安排每周1-2次地点：2号实验楼133每周1-2次地点：教研室对计划的说明无毕业设计(论文)开题报告课题名称：无决策属性的多属性决策权重融合方法 1 本课题所涉及的问题及应用现状综述多属性决策研究是决策理论研究的重点内容之一。目前确定多属性权重分配的方法主要有两类，第一类为主观赋权法，如特征向量法，最小平方和法和Delphi法；第二类为客观赋权法，如主成分分析法，熵法和多目标最优法。客观赋权法依据当前收集的信息来确定各属性的权重分配，其所依据的事实清楚，理论充足，具有较强的说服力。但其缺点是没有充分利用人类对所考察的系统多年研究成果的积累。主观赋权法反映了人类对于所考察的系统多年来在综合认识上的成果积累，其缺点是忽视了客观系统当前的情况，所确定的权重分配不能反映客观系统当前的实际情况，同时理论论据不够充分，而且各个专家对同一系统的评价往往因认为偏好不同而产生不同的判断结果。所以，将主观权重与客观权重进行融合或集成是必要的。目前，有关这两类权重的融合方法已经一起了重视，并且得到了一些初步的研究成果。但是目前的方法在进行主观权重融合是往往又会引入一个偏好系数，这又在权重融合中添加了认为影响。在多属性决策研究中，根据研究的对象属性特点不同（连续属性、离散属性、是否具有明确的决策性属性等）而呈现不同的组合情况。国内的文献对系统属性是连续属性且没有明确决策属性的多属性决策系统的客观权重分配进行了讨论，但可能出现的组合爆炸现象。针对这一现象，有文献提出了一种基于客观重要性的多因素权重分配方法，但对于如何将客观权重与主观权重融合并未涉及。针对这一问题进行讨论并提出一种无主观偏好的权重融合方法是必要的。2本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析关键问题：第一，是利用粗集理论确定属性的客观重要性权重。粗糙集中处理的通常是一些决策表，在决策表中，不同属性的重要性不同。为了考察多属性中各个属性的重要性，采用的方法是从属性表中去掉一个属性，再来考察没有该属性后分类情况发生的变化。若去掉该属性相应分类变化比较大，则说明该属性的强度大，即重要性高；反之，说明该属性的强度小，即重要性低。第二，是基于遗传算法的权重融合。其中，遗传算法适应度函数的确定和遗传算法的运行参数的确定是关键。运行参数主要有个体编码串的长度L，初始群体的大小M，交叉概率，变异概率和终止代数T。解决思路： 针对多属性决策中属性权重的两种确定方法，建立了一个权重融合目标规划方程，给出了一种智能化的权重融合解决方法，该方法避免了在权重融合是引入认为偏重系数影响，是多属性决策属性权重的融合或集成合理化。可行性分析： 此研究是多属性分析的结果同时反映了主观权重和客观权重，并且为其他类型的决策知识系统的权重融合集成提供了一个有益的思路。3完成本课题的工作方案3月10日至3月20日 查阅粗糙集理论的相关资料3月21日至3月28日 对粗糙集理论的理解与掌握3月29日至4月11日 对粗糙集理论进行更深层的理解与掌握4月12日至4月25日 学习遗传算法，并运用粗糙集理论进行问题论证4月26日至5月09日 对问题进行数学建模，并求解5月10日至5月23日 对整体进行进一步修改5月24日至6月04日 撰写论文6月05日至6月10日 准备论文答辩4指导教师审阅意见该课题立题明确，具有一定的理论性和使用性，查阅资料较详实，方案较合理，望进一步查阅相关资料，对方案进一步完善和细化，同意开题。指导教师(签字)： 2010 年 3 月 22 日说明：本报告必须由承担毕业论文(设计)课题任务的学生在毕业论文(设计) 正式开始的第1周周五之前独立撰写完成，并交指导教师审阅。成绩评定表课题任务完成情况论 文 27.115 (千字)； 设计、计算说 明书 (千字)； 图纸 (张)；其它(含附 件)：指导教师意见分项得分：开题调研论证 分； 课题质量（论文内容） 分； 创新 分；论文撰写（规范） 分； 学习态度 分； 外文翻译 分指导教师审阅成绩： 指导教师(签字)： 年 月 日评阅教师意见分项得分：选题 分； 开题调研论证 分； 课题质量（论文内容） 分； 创新 分；论文撰写（规范） 分； 外文翻译 分评阅成绩： 评阅教师(签字)： 年 月 日验收小组意见分项得分：准备情况 分； 毕业设计（论文）质量 分； （操作）回答问题 分验收成绩： 验收教师(组长)(签字)： 年 月 日答辩小组意见分项得分：准备情况 分； 陈述情况 分； 回答问题 分； 仪表 分答辩成绩： 答辩小组组长(签字)： 年 月 日成绩计算方法(填写本系实用比例)指导教师成绩 () 评阅成绩 () 验收成绩 () 答辩成绩 ()学生实得成绩(百分制)指导教师成绩 评阅成绩 验收成绩 答辩成绩 总评 答辩委员会意见毕业论文(设计)总评成绩(等级)： 系答辩委员会主任(签字)： 系(签章) 年 月 日备注目录摘 要IABSTRACTII1概述12经典粗糙集理论的基本概念22.1信息表和不可分辨关系22.1.1信息表和决策表22.1.2不可分辨关系32.2上、下近似集32.3知识表达42.3.1知识表达系统42.3.2属性约简、核集的求取52.3.3属性值约简62.3.4基于可辨识矩阵属性约简算法62.4属性约简的方法73模糊等价矩阵的构造103.1模糊相似矩阵103.1.1模糊相似矩阵的概念103.1.2模糊相似矩阵的构造方法103.2模糊等价矩阵113.2.1模糊等价矩阵的概念113.2.2模糊等价矩阵的构造方法124属性权重的分配144.1特征向量法144.2熵法154.3基于粗集理论的属性权重确定方法164.3.1知识的依赖度164.3.2粗集中属性的重要度164.3.3属性权重确定方法及实例165遗传算法185.1遗传算法概述185.1.1遗传算法的基本理论185.1.2遗传算法的原理195.1.3遗传算法的基本操作195.2基本遗传算法215.2.1基本遗传算法的流程215.2.2 SGA染色体的编码和解码方式215.2.3产生初始种群225.2.4计算适应度225.2.5选择操作235.2.6一点交叉操作245.2.7变异操作246无决策属性的多属性权重融合方法256.1基于粗集理论的属性权重重要性的确定方法256.2基于遗传算法的权重融合256.2.1遗传算法适应度函数的确定256.2.2遗传算法运行参数的确定267实例分析27结论32致谢33参考文献34摘要粗糙集理论的应用现在被广泛的重视，粗糙集理论与多属性的决策分析也吸引了大批学者的注意。属性的权重是属性重要性的表示，粗集中的处理方法是从属性表中去掉一个属性，再来考察没有该属性后分类情况发生的变化。若去掉该属性相应分类变化比较大，则说明该属性的强度大，即重要性高；反之，说明该属性的强度小，即重要性低。针对无决策属性的多属性决策系统的2种属性权重分配方法（主观赋权法和客观赋权法）的缺陷，提出了一种新的权重融合方法。该方法通过建立数学规划模型，用遗传算法寻求其全局最优解，以确定最佳的主客观权重融合方案，从而可以避免权重融合是人为偏好的影响。最后，给出了一个实例，说明如何进行属性权重的融合。关键词：属性权重；遗传算法；融合ABSTRACTApplication of rough set theory is widely appreciated now, rough set theory and multi-attribute decision-making analysis have attracted the attention of a large number of scholars. Attributes weight is the expression of attribute importance, the method in rough set is to remove one attribute from the attribute table,then,inspection the change of the classification without the attribute. After remove the attribute,if the classification changes large, it indicates the attribute of high-intensity, that is of high importance; the other hand, shows that the attribute of low-intensity, that is low importance. A syncretized weight allocation method was proposed to overcome the limitations of two weight allocation methods of multiattribute decision-making without decision attribute, i. e.,the impersonal method and the subjective method.To obtain the optimal weight integration between subjective weights and objective ones with this method,a mathematical planning model was set up and the genetic algorithm was used to gain the global optimal solution.As a result,subjective factors in weigh syncretizing can be avoided with this method.At last,an instance was given out to illustrate how to syncretiz subjective weights and objective ones.Keywords:attribute weight; genetic algorithm; syncretiz34无决策属性的多属性权重融合方法1概述许多决策问题可以归结为由一组属性描述的决策对象或方案的集合。根据决策目的和问题性质不同，这类问题可以通过四种方式进行处理以提供决策支持，其中分类问题和分级问题在现实世界中广泛存在，应用于多个领域，包括金融、环境、能源政策、计划、市场营销、医学、机器人等。如根据症状判断病人的疾病、根据某些评价指标决定录用哪些应聘者、通过分析顾客特征制定市场战略、预测具有哪些特征的企业更易破产、利用某些指标进行股票投资分析等。多属性决策研究是决策理论研究的重点内容之一。目前确定多属性权重分配的方法主要有两类，第一类为主观赋权法，如特征向量法，最小平方和法和Delphi法；第二类为客观赋权法，如主成分分析法，熵法和多目标最优法。客观赋权法依据当前收集的信息来确定各属性的权重分配，其所依据的事实清楚，理论充足，具有较强的说服力。但其缺点是没有充分利用人类对所考察的系统多年研究成果的积累。主观赋权法反映了啦人类对于所考察的系统多年来在综合认识上的成果积累，其缺点是忽视了客观系统当前的情况，所确定的权重分配不能反映客观系统当前的实际情况，同时理论论据不够充分，而且各个专家对同一系统的评价往往因认为偏好不同而产生不同的判断结果。所以，将主观权重与客观权重进行融合或集成是必要的。目前，有关这两类权重的融合方法已经一起了重视，并且得到了一些初步的研究成果。但是目前的方法在进行主观权重融合是往往又会引入一个偏好系数，这又在权重融合中添加了认为影响。在多属性决策研究中，根据研究的对象属性特点不同（连续属性、离散属性、是否具有明确的决策性属性等）而呈现不同的组合情况。国内的文献对系统属性是连续属性且没有明确决策属性的多属性决策系统的客观权重分配进行了讨论，但可能出现的组合爆炸现象。针对这一现象，有文献提出了一种基于客观重要性的多因素权重分配方法，但对于如何将客观权重与主观权重融合并未涉及。针对这一问题进行讨论并提出一种无主观偏好的权重融合方法是必要的。2经典粗糙集理论的基本概念2.1信息表和不可分辨关系2.1.1信息表和决策表粗集理论利用信息表来描述论域中的对象，它是一个二维表，每一行表示一个对象，每一列表示对象的一个属性。定义2.1 称为一个信息表，其中U为论域，是一非空有限对象集，即，是非空有限的属性集合，是属性a的值域，即，f：UAV称为信息函数，使得对每一,有。在粗集理论中，信息表也称为信息系统、属性值表、数据表，可简记为或。利用信息表，论域中的对象被描述为向量 ，称为对象关于属性集的描述，表示关于的可用信息。在信息表S中，如果属性集由条件属性集C和决策属性集D组成,并且满足空集，则称S为决策表，记为。一般的，决策属性只有一个，即，其中不属于为决策属性。例如，表2.1所示的决策表中，论域，条件属性集，决策属性，其中，。，为信息函数的两个例子。表2.1 决策表 U 条件属性C 决策属性D a b c dX1X2X3X4X5X63 2 12 1 1 2 1 11 1 1 2 2 23 1 2 2 1 2 1 1 2 2.1.2不可分辨关系定义 2.2 设为一信息表，定义在上的不可分辨关系为。如果 ，则和称为B不可分辨。不可分辨关系是二元关系，满足自反性（即对象和它本身的关系）、对称性（如果，则）和传递性（如果小且，则）。显然，不可分辨关系是一等价关系。的所有等价类族，即由决定的划分，用表示，或简记为，包含元素的等价类用表示。的等价类或划分的块称为基本集。表2.1中，各条件属性子集的等价类族为, , ,。决策类划分 。各条件等价类分别为 , , , , , 。 2.2上、下近似集 给定论域，一族等价关系将划分为互不相交的基本等价类。令为上的一个等价关系。当能表达成某些基本等价类的并集时，称为可定义的；否则称为不可定义的。可定义集能在这个知识库中被精确地定义，所以又称为精确集。不可定义集不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称为粗糙集（Rouhgset）。可以使用两个精确集，即粗糙集的上近似集（UpperAproximation）和下近似集（LowerApproximation）来近似地定义粗糙集。粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性。定义 2.3 设集合, 是一个等价关系，称为集合的下近似集；称为集合的上近似集；称集合为的边界域；称为的正域；称为的负域。设论域,上的一族等价关系,和是两个等价关系。根据这两个等价关系可以将论域进行划分：和。中的，代表的等价类。论域被划分的基本等价类为：集合是上的一个子集，则无法用基本等价类的并集精确表示，所以是上的一个粗糙集合。故有：的下近似集为：=；的上近似集为：；的负区域：=。2.3知识表达知识表达在智能数据处理中占有十分重要的地位。在智能系统中，经常会碰到要处理的对象可能是用语言方式表达，也可能使用数据表达；可能是精确的数据，可能会有一些默认的信息或者相互矛盾的信息。为了处理这些数据，需要进行知识的表达，即知识表达系统。决策表是特殊的知识表达系统。2.3.1知识表达系统知识表达系统的基本成分是研究对象的集合，关于这些对象的知识是通过指定对象的基本特征（属性）和它们的特征值（属性值）来描述的。定义 2.4 一个知识表达系统可以定义为,其中为对象的集合，称为论域；为属性集合；子集和分别称为条件属性和决策属性；为属性值的集合；表示了属性的属性值范围；是一个信息函数，它指定了中每一对象的属性值。知识表达系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表达的。如表2.2是一个轿车信息决策表，条件属性集为分别代表价格、油耗、速度和安全性，决策属性为d，表示质量。表2.2 轿车信息决策表车型U1高低快好高2低高中差低3中中慢一般低4中高慢一般中5低高中差低6高低快好高2.3.2属性约简、核集的求取所谓属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。一个属性集合可能有多个约简。属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即和所有条件属性相对于决策属性有相同的分类能力。属性集合的所有约简的交集定义为的核，记作，核是表达知识必不可少的重要属性集。核的概念具有两方面的意义：因为核包含于所有约简之中，所以核可以作为所有约简的计算基础；核在知识约简中是不能消去的特征集合。直接由分辨矩阵来求取系统的核集。不失一般性，假定系统对于属性集是可分辨的，则系统的核集由定理2.1确定。定理 2.1 中任意属性，充要条件为：中至少存在一个元素，满足。其中，元素都是属性集的一个子集，元素定义如下： 其中。命题2.1 从信息系统的决策表中将属性集P中逐一移去，每移去一个属性即刻检查其决策表，如果不出现新的不一致，则属性是可被约去的；否则属性不能约去。命题 2.2 全体不可约去属性集称为核集。属性集合的约简和核的关系如下：式中表示P的所有约简。含有的全部约简中共同的等价关系，是属性集合中不可缺少的重要属性集。2.3.3属性值约简属性值约简只是在一定程度上去掉了决策表中冗余属性，还是没有充分去掉决策表中的冗余信息。在判断某个对象属于某类时，其属性的取值不同，对分类产生的影响也不同。例如，判断人的体形（瘦、中、胖）时，体重是主要属性。但若体重属性值为75时，此人的体形要结合其身高、性别等属性才能确定。如果体重属性值为160时，几乎可以肯定其体形为胖，这时身高、性别已不重要。也就是说在这一条记录（对应一个论域对象）中，身高、性别属性是不必要的，是冗余的。属性值约简的目标即是去除冗余的属性值。与属性约简时的属性核一样，属性值约简中也可以定义相应的属性值核。命题 2.3 设是决策表上的一条决策规则，属性值v是一可被约去当且仅当，其中和均为决策表上的逻辑公式。2.3.4基于可辨识矩阵属性约简算法可辨识矩阵（也称分明矩阵）是由波兰数学家Skowron.A教授提出的。定义 2.5 设相容决策表，和分别为条件属性和决策属性集，是论域，是样本在属性上的取值。表示可辨识矩阵中第行列的对象，则可辨识矩阵定义为： 由上述定义可以看出，可辨识矩阵是一个对称矩阵。当两个样本的决策属性取相同时，对象值为0；当两个样本的决策属性不同且可以通过某些条件属性的取值加以区分时，对象值为这两个样本属性值不同的条件属性集合。由可辨识矩阵定义知道，矩阵中属性组合数为1表明，除该属性外其余属性无法将决策表中的记录区分，即为决策表的核属性。一个数据集的所有约简可以通过构造可辨识并且化简由可辨识矩阵导出的区分函数而得到，在使用吸收律化简区分函数成式后，所有的蕴含式包含的属性就是决策表的所有约简集合。算法 可辨识矩阵属性约简算法。输入：相容决策表，是属性集合；输出：约简的属性集。方法：计算决策表的可辨识矩阵；根据分辨矩阵的定义求元素；对于可辨识矩阵中所有取值为非空集合的对象，建立相应的析取逻辑表达式，；将所有的析取逻辑表达式进行合取运算，得一个合取范式T，即；将合取范式L转换为析取范式的形式，得；输出属性约简结果。基于可辨识矩阵和逻辑运算的属性约简算法可以得到决策表的所有可能的属性约简结果，它实际上是将对属性组合情况的搜索演变成为逻辑公式的简化。2.4属性约简的方法分辨矩阵求核约简方法设是一个阶矩阵，其中每一个元素都是的一个子集，元素定义如下： 说明：和表示决策表中第i行和第j列两个属性的值；k表示决策表的研究对象的个数，分辨矩阵D是一个对角线为0的对称矩阵。直接求核集方法用命题2.1和命题2.2就可以直接求核集。下面通过例子来说明具体的求解方法。如决策表2.3给出了一个 医疗数据记录表，通过测量人的体温、咳嗽、头痛、周身痛等症状来确定是否患了流感。表2.3 医疗记录表U体温咳嗽头痛周身痛流感1正常无无有无2正常无有无无3偏高无有无有4高有有无有5高有无无有6偏高有有无有其中属性及属性值的含义为：体温a，正常0，偏高1，高2；咳嗽b，无0，有1；头痛c，无0，有1；周身痛d，无0，有1；流感e，无0，有1。通过对决策表2.3进行处理后，得到离散形式的决策表如表2.4所示。表2.4 医疗决策表Uabcdee100010e200100e310101e421101e521001e611101其中，条件属性集为a,b,c,d,决策属性集为e。a.条件属性约简求核有两种属性约简求核的方法：分辨矩阵直接求核约简法和用命题2.1、命题2.2求核约简法。首先用分辨矩阵直接求核集。用以下举例说明分辨矩阵求核约简的方法，如表2.5医疗决策表所示是一个知识系统，U=U1,U2,，Un是论域，C=a,b,c,d是条件属性集，D=e是决策属性集，P=C+D，则其相应的分辨矩阵为：从上述分辨矩阵中可以得出：由于D=e是决策集，不需要约简，约简的是条件集合C，由定理2.1求出该知识系统的核集为a,b,c。该约简求核集的方法便于计算机实现。然后用方法二直接求核集。还是以决策表2.5作为知识系统的例子，求核集的步骤为：Step1去掉属性a，对比每一行属性值，第4、6行发生冲突，则属性a不可约。Step2去掉属性b，对比每一行属性值，第4、6行发生冲突，则属性b不可约。Step3去掉属性c，对比每一行属性值，第4、5行发生冲突，则属性c不可约。Step4去掉属性d，对比每一行属性值，没有发生冲突，则属性d可约。若还有条件属性，则依此类推。经过约简后得到的核集为a,b,c。比较两种求核集的方法，对于数据量大，采用分辨矩阵来求核集，方便计算机来实现；第二种方法简单易行，方便人工处理。3模糊等价矩阵的构造在第七章的实例分析中，应用到了模糊等价矩阵和模糊相似矩阵，故在这里做简单的介绍。3.1模糊相似矩阵模糊相似矩阵体现的是各个对象间的相似程度。3.1.1模糊相似矩阵的概念笛卡尔XY的模糊关系R可用模糊矩阵（当X、Y均为可列时或有限时）表示，式中：表示集合X中第i个元素和集合Y中第j个元素从属于模糊关系R的程度，。若矩阵中左上角至右下角对角线元素全为1，即，则称R具有自反性（或反身性）。当矩阵中元素关于上述对角线对称，即时称R具有对称性，若同时具有自反性及对称性，则称模糊关系R具有相似性（相容性）。若对任意的均有则称模糊关系R具有传递性。当模糊关系满足自反性和对称性时，称为模糊相似关系，对有限论域，相应的模糊矩阵称为模糊相似矩阵。显然的，模糊相似矩阵具有自反性和对称性，因其对角线上元素全为1，而且元素关于对角线对称。3.1.2模糊相似矩阵的构造方法在模糊聚类的计算中，有数种常用的规格化方法，有10余种常用的样本间相似性度量方法，因而对同一问题，可以形成几十种计算结果。所以，选择一种有效的方法是关键。通过查找各种文献，笔者了解到在众多的模糊相似矩阵构造方法中，绝对值倒数法、最大最小法和算术平均最小法相对其它方法比较可靠。在此，采用最大最小法构造模糊相似矩阵。最大最小法是一种规格化方法，由于m个指标的量纲和数量级都不同，直接利用原始数据进行计算，就可能突出某些数量级特别大的特性指标对分类的作用，而降低甚至排斥某些数量级较小的特性的作用，导致一个指标只要改变一下单位，也会改变分类结果。所以，必须对原始数据进行无量纲化处理，使每一指标统一于某种共同的数据特性范围。最大最小法方法如下： （I）其中，m为样本属性个数，X为样本对象。此公式描述的是对象之间的依赖程度，01。若样本个数为n，则依据此方法构造出来的模糊相似矩阵为nn阶矩阵。其原始数据可放在一个nm矩阵中：。通过式（I）可知，时，；时，故只需计算上三角或下三角矩阵即可。例如，有如下一个对象-属性特征值矩阵，根据公式（I）可得：，同理可得：。所得模糊相似矩阵为。可见，模糊相似矩阵满足自反性和对称性。3.2模糊等价矩阵模糊等价矩阵可通过模糊相似矩阵的模糊自乘得到。3.2.1模糊等价矩阵的概念定义3.1 设R是论域X中的模糊关系，R，RF（XX），如果满足：RR；R具有传递性；如果，具有传递性，并且，那么，则R具有传递性。这个定义表明，如果传递闭包，它是唯一的，当且仅当时，R具有传递性。由模糊关系推广到模糊矩阵，则可得如下定义，设模糊关系R对应的模糊矩阵为R，t（R）的模糊矩阵即为包含R的最小模糊传递矩阵，称为R的传递闭包，记为t（R）。定理3.1对任意的nn模糊矩阵R，存在k=n，使R的传递闭包t（R）有定理3.2一个二元模糊相似关系的传递闭包是模糊等价关系。定理3.3设R是一个nn模糊相似矩阵，则存在一个最小的自然数k=n，使得传递闭包，且对于一切大于k的自然数，此时，为模糊等价矩阵。由定理3.3可得如下结论，将模糊相似矩阵R进行多次合成，,直到得到数k，使得一切大于k的自然数，有，即可得出模糊等价矩阵。可见，模糊等价矩阵具有自反性、对称性和传递性。3.2.2模糊等价矩阵的构造方法由模糊相似矩阵到模糊等价矩阵需要进行合成运算。合成运算是一种模糊矩阵运算方式，与普通矩阵运算方式相似，所不同的是将阵元元素相乘与相加分别改为取小和取大。以上节的数据为例说明由模糊相似矩阵得到模糊等价矩阵。 =这时，找到了一个自然数4，使得大于4 的一切自然数k，。所以，求得的模糊等价矩阵即为。4属性权重的分配4.1特征向量法特征向量法适用于决策矩阵未知的情况。该方法由Saaty于1977年提出。设多属性决策问题中的权重矢量为，根据属性Ci，Cj的权重比，可构造下面的权重比矩阵M： 其中，矩阵元素且 M被称为相容矩阵。将权重矢量w右乘M，则有.由矩阵理论可知，n是M的唯一非零的也是最大的特征根，记为，而w是n所对应的特征矢量。虽然权重矢量w是未知的，但可以通过两两比较的方法得到M的一个估计矩阵，也被称为判断矩阵。然后求解的最大特征根，即求解满足以下用行列式形式表示的联立方程的最大解：将求出的最大特征根代入齐次线性方程组：从而解出的特征矢量如果判断矩阵是相容矩阵，则特征矢量也就是属性的权重矢量。但一般来说，未必是相容矩阵。为了度量判断矩阵的相容性，Saaty定义了下面的不相容度指标：当时，认为判断矩阵的相容性好，可令否则，需要对估计矩阵重新调整。由于特征根对应的特征矢量一般不是唯一的，为了确切起见，可采用归一化的特征矢量作为权重矢量，即4.2熵法熵法适用于决策矩阵已知的情况。熵是社会科学和物理科学中的一个重要概念，它在信息理论中作为不确定性和信息量的量度而由Shannon定义为式中k是一个正的常数，pi是一个离散的概率分布。沿用统计力学的术语，上式被称为概率分布pi的熵。并认为一个宽广的分布比一个狭窄的分布表现出更多的不确定性，而当所有的pi都互相相等时，即达到它的最大值。决策矩阵显然是一种信息的载体，故熵的概念也可作为评价属性相对重要程度的一个工具。其基本原理可以被解释为：就某一属性来说，如果不同策略在这一属性上的表现完全相同，则该属性对于方案的比较便没有意义而可以被剔除。故属性指标间的差异越大，则提供的信息越多，该属性也就显得越重要。在含有m个方案和n个属性的决策矩阵中，属性j的几何映射影pij可被定义为其熵Ej则按下面的公式计算：式中以保证。因为权重与熵的关系是互反的，我们将采用来代替，并使之归一化以保证和。如果决策者没有其他理由偏重于某些或某个特定的属性，则此种情况下最合理的权重分配应该是如果决策者主观上对属性j已经有一个先验的权重，则可以将两者结合起来形成一个新的权重，或称为后验权重。其结合方式为4.3基于粗集理论的属性权重确定方法按模糊等价关系R，可对X的元素进行分类。这由其自反性、对称性、传递性加以保证。因为对于X中的元素，具有自反性才能保证其上任一样本不能同时属于不同的类，否则自己不属于自己岂不可笑；并且对称性使得X中样本A与样本B同类时，样本B与样本A一定同类。在两者基础上的相似关系也不能用于分类，因为它没有考虑样本元素间的间接关系，需进一步矩阵合成。使模糊关系R具有传递性，它保证样本A若与样本B同类，同时样本B若与样本C同类，则样本A定与样本C同类。对已建立起的模糊等价关系R，取定阀值，若则将与归为一类。可根据需要，调整阀值以得到适当分类，且不必事先准确计算好分得的类数。不可分辨关系和上下近似集的概念在前面已经介绍过了，下面介绍一下知识依赖度。4.3.1知识的依赖度知识的依赖性定义如下：对于近似空间，且：当，知识Q依赖于知识P。知识Q对P的依赖度定义为其中表示集合的基数。4.3.2粗集中属性的重要度为了找出某些属性核属性集的重要性，需要从表中去掉另外一些属性，再来考察没有该属性后分类怎样变化。若去掉该属性会相应地改变分类，则说明该属性的强度大，即重要性高；反之说明该属性的强度小，即重要性低。这一点可以用粗集中的正域来描述。对于属性集C导出的分类属性子集的重要性，我们用两者的依赖程度的差来度量，即。这表示当从集合B中去掉某些属性子集对对象分类时，分类U/C的正域受到怎样的影响。4.3.3属性权重确定方法及实例这里介绍的是一种属性权重的确定方法，这不是唯一的方法。通常情况下，决策者会拥有对各个条件属性的先验知识，权重用来衡量属性的相对重要性。在不同的决策环境下，相同的属性对决策输出会有不同的影响，即权重对环境敏感。粗集理论中的属性重要度即表达了当前数据环境下属性对决策的影响，但它不能反映决策者的先验知识。因此，将二者结合起来确定属性的权重可以得到比较理想的结果。我们假设系统中的条件属性为C，决策属性为D。在C中有n个属性。由决策者先验知识给定的权重分别为。然后，收集大量的评价样本，由这些样本数据来考察所有条件属性将样本划分为决策类的分类能力，并由决策属性对条件属性的依赖度表示。然后我们去掉条件属性i后，再重新考察分类情况，得到属性i的重要度，在此基础上将各个属性的重要度进行归一化处理并把处理后的结果作为属性i的客观权重。即。显然在0和1之间取值。由于客观权重是由历史数据处理后得到的，故赋予其较大的权60%，相应地，赋予主观确定的权重较小的权40%，并由此确定综合权重如下：。例：某知识表达系统条件属性集C=a,b,c,d,决策属性集D=e。U/ind(a,b,c,d)=1,2,3,4,5,U/ind(e)=1,2,3,4,5,=5/5=1。去掉属性a后，U/ind(b,c,d)=1,4,2,3,5, =3/5=0.6。去掉属性b后，U/ind(a,c,d)=1,3,2,4,5,=3/5=0.6。去掉属性c后，U/ind(a,b,d)= 1,2,3,4,5,=5/5=1。去掉属性d后，U/ind(a,b,c)=1,5，2,3，4，=4，=1/5=0.2。可见，属性d最重要，它将U/D的正域改变得最多，属性a和b次之。而属性c则是冗余属性。假设专家给定各个属性的权重分别为=0.3，=0.2，=0.1，=0.4。根据的计算公式可得： =0.25，=0.25，=0，=0.5。各属性的综合权重为：=0.60.25+0.40.3=0.27，同理，=0.23，=0.04，=0.46。至此得到了各个属性的主客观相结合的综合权重。在这里介绍这个方法的主要目的是，对属性权重的确定做简单的说明及求解示范，为以后的求解算法打基础。5遗传算法遗传算法（Genetic Algorithm-GA）,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。由于遗传算法在机器学习、过程控制、经济预测、工程优化等领域取得的成功，已引起了包括数学、物理学、化学、计算机科学、社会科学、经济学及工程应用领域科学家们的极大兴趣。5.1遗传算法概述遗传算法的两大主要特点是群体搜索策略和群体中个体之间的信息交换，它实际上是模拟由个体组成群体的整体学习过程，其中每个个体都是给定问题搜索空间的一个解点。遗传算法从任一初始化群体出发，通过选择、交叉和变异等遗传操作使得种群一代一代地进入到搜索空间中越来越好的区域，直至得到最优解。5.1.1遗传算法的基本理论遗传算法的基本理论只要就是模式理论、积木块假设以及隐并行性。.模式定理定义5.1模式（Schema）是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性，因此也可以解释为相同的构形，它描述的是一个串的子集。例如，模式*1*0描述四个字的字符集0100,0110,1100,1110。对于二进制编码串，当串长为1时，共有21个不同模式。遗传算法串的运算实质为模式运算。定义5.2模式H中确定位置的个数称为H模式阶，记为O（H）。如O（0*1*01）=4。模式阶用来反映不同模式间确定性差异，模式阶数越高，其样本数就越少，因而确定性越高。定义5.3模式H中第一个确定位置和最后一个确定位置之间距离称为定义距，记作。例如：。b.积木块假设具有低阶，短定义距及高适应度的模式称做积木块（Building block）。正如搭积木一样，这些“好”的模式在遗传操作中，相互拼搭，结合产生适应度更高的串，从而找到更优的可行解，这正是积木块假设所揭示的内容。积木块假设（building block hypothesis）是指低阶、短距、高平均适应度的模式（积木块）在遗传算子作用下，相互结合，能生成高阶，长距，高平均适应度模式，可最终生成全局最优解。积木块假设指出，遗传算法具备寻找到全局最优解的能力，即积木块在遗传算子作用下，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解或近似最优解。遗憾的是上述结论没有得到证明，所以称之为假设，但很多实践支持积木块假设，在许多领域内应用都取得成功。5.1.2遗传算法的原理在自然界，由于组成生物群体中各个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存、优胜劣汰,将要淘汰那些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化，遗传算法是真实