【毕业学位论文】（Word原稿）基于语言偏好关系多目标群组决策的研究与应用-计算机软件与理论

西 华 大 学 硕 士 学 位（毕 业）论 文 题目： 基于 语言偏好关系多目标群组决策的研究与应用 研究 生： 秦 丽 指导教 师 ： 裴 峥 专 业： 计算机 软件与理论 研究方 向 ： 智能信息处理 培养单 位 ： 西 华 大 学 论文起止日期： 2008 年 1 月至 2009 年 5 月西华大学硕士学位论文 I 基于 语言 偏好关系多目标群组决策的研究与应用 计算机软件与理论 研究生 秦丽 指导教师 裴峥 多目 标决策是指为达到多种目的或目标而在众多的可行方案中进行选择的过程 。 在现实生活中，我们经常会遇到需要 进行 多目标决策 的问题 ，其 核心思想是寻找满意解 ，而不是最优解。这是因为 在复杂的决策环境中， 目标 之 间往往是 相互冲突和不可公度 的 ， 从而 导致 了 最优方案 的不存在 。 当前基于 偏好关系 的多目标决策模型并不多见，与群组决策相关的模型更是少之又少。 而 在做重大决策的时候， 一个人的智慧是远远不够的。因此， 在本文中， 我们 探讨了 一个基于 语言 偏好关系的多目标群组决策模型。 该模型有 下面 四个特点： 1、 基于语言偏好关系。 在作决策时，人们很难用 精确的数值描述偏好度。 为 此，我们引入语言偏好关系，决策者将 以一种非常自然的方式表达对方案的 偏好 。 2、 基于 由于 念很符合多目标问题本身的特点， 因此 ，在优化算法的选择上，我们采用 具有 。 目前比较流行的 算法是 改进的非劣分层遗传算 法 运用 该算法，可以得到分布均匀 且散布较好的近似 3、 基于目标满意度 我们引入目标满意度的概念， 是为了将大 量的 集缩小到只有决策者满意的 解 的集合 ， 从而减轻决策器的负担 。 4、 基于群组决策 西华大学硕士学位论文 为多人决策更符合现实需要，所以我们的模型是在群组决策的基础上提出来的。 运用聚合算子可以非常方便地聚合决策者 们的观点。在模型中， 我们采用 聚合决策者的语言偏好。 此外， 我 们 用 法 解决具有 离散性的 问题 ，扩大了它的应用范围，提高了它的实用价值。 我们还充分开发了诱导变量的新作用 , 使它不但 具有排序 和 计 算 W 权重 的任务，同时还用它来计算语言距离，处理 联结 的 为了减轻决策器的负担，提高决策速度，我们还 研究 了该模型的一些属性并 给予 了证明 。 在文章的最后，我们应用 该模型解决了复杂零件协同制造中的资源优化配置问题，并得到了良好 结果。 关键词 ： 多目标群组决策， 优解， 子， 西华大学硕士学位论文 i is a to in a of In we is to a in of At a a s is we a as 1. In it is to a we be a to of 2. is in of In of we 华大学硕士学位论文 IV 3. we is to so of of 4. is in so we of we to of in In we to to of to We a of We it to it to WA In to of we of a At we to a of of in 华大学硕士学位论文 V 目 录 1 绪论 . 1 目标决策简介 . 1 内外研究现状和发展趋势 . 1 文内容安排及意义 . 4 2 多目标决策的预备知识 . 6 目标优化的基本概念 . 6 目标遗传算法 . 8 糊群组决策的基本概念 . 13 3 多目标群组决策模型 . 21 化器的设计 . 21 选器的设计 . 24 策器的设计 . 28 结 . 35 4 多目标群组决策模型的应用 . 36 源优化配置问题 . 36 化器的设计 . 41 选器的设计 . 44 策器的设计 . 47 结 . 49 5 总结与展望 . 50 结 . 50 要研究成果 . 51 望 . 52 6 参考文献 . 53 7 作者在读期间科研成果 . 58 8 声明 . 59 9 授权书 . 60 10 致谢 . 61 西华大学硕士学位论文 . 1 . 1 . 1 . 4 2 . 6 . 6 . 8 . 13 3 . 21 . 21 . 24 . 28 . 35 4 . 36 . 36 . 41 . 44 . 47 . 49 5 . 50 . 50 . 51 . 52 6 . 53 7 . 58 8 . 59 9 . 60 10 . 61 西华大学硕士学位论文 1 1 绪论 目标决策简介 决策是指为达到某种目的或目标，而在众多的可行方案中进行选择的过程。它是日常生活的一部分。不论是对个人、企业、或是大型的工程系统和社会经济系统，几乎都存在决策问题。在社会瞬息万变的今天，面对国计民生、企业前途等重大的决策，一个人的智慧是远远不够的，它需要相关人员的群体智慧。如何解决决策者之间的分歧，并最终得到一致的决定是群组决策研究的一个重点，也是本文的一个研究方向。 人们所面临的决策问题可分为两种：单目标决策和多目标决策。所谓单目标决策即从众多的可行方案中，根 据一个标准选择最好的或满意的方案；如果需按多个标准来选择的话，就是多目标决策。多目标决策问题有许多共同的特点，其中最显著的是 :目标间的不可公度性和矛盾性 1。所谓目标间的不可公度性是指各个目标没有统一的度量标准，因而难以进行比较。目标间的矛盾性是指如果采用某一种方案去改进某一目标值，可能会使另一目标的值变好或变坏。由于多个目标之间的矛盾性和不可公度性，因此，不能 简单地把多个目标归并为单个目标，并使用单目标决策方法去解决多目标决策问题。 但是，在现实生活中，我们遇到的决策问题大部分又都属于后者。由于它的普遍性及复杂性，对多目标决策的研究显得尤为重要。 多目标决策问题的另外一个显著特点是无最优解。因此，在解决这类问题时，我们寻找得是令决策者满意的解。由于问题的复杂性及决策者对问题认识的模糊性，要想准确的表达偏好是不可能的事情，但是决策者可以轻松得给出类似于某目标比某目标重要或是某方案比某方案略好的具有模糊语言偏好的二元比较关系式即偏好信息。针对有不同类型偏好和不同性质 的优化问题，存在着不同形式的模型和算法。目前还没有统一、系统的最佳方法。因此对具有偏好信息的多目标优化问题设计相应的优化模型是本文的研究方向。 内外研究现状和发展趋势 多目标优化的思想可以说是萌芽于 1776 年经济学中的效用理论。 1896 年，西华大学硕士学位论文 2 经济学家 先在经济平衡的研究中提出了多目标优化问题，引进了被称为 优的概念。 1947 年，数学家 对策论的著作中提及多目标决策问题，引起人们对多目标优化研究的重视。 1951 年，数理经济学家 生产和分配的效率分析中考虑了多目标优化问题，引入有效解的定义并得到某些基本结果，他的工作为多目标优化学科奠定了初步的基础。 20 世纪 60 年代以来，人们设计了不少求解多目标优化问题的处理方法，并运用它们去解决各种实际问题，取得了一定效果。关于多目标优化的研究，不论在理论或应用方面都迅速、蓬勃地开展起来 2 按照优化过程和决策过程的先后顺序，多目标优化问题被分为三大类：先验偏好多目标优化、局部偏好多目标优化和后验偏好多目标优 化 2。 1、先验偏好多目标优 化是指在求解优化问题前，决策者事先提供足够的偏好信息。优化者根据这些信息构造优化评价函数或优化规则，将多目标优化问题转化为单目标优化问题，从而求得最优解。其求解过程如图 验偏好模型 先验偏好多目标优化在多目标优化方法的发展初期得到了广泛的研究和应用。 和 提出加权和法，该方法通过加权函数将多目标优化问题转换为以下形式的单目标问题进行求解（ n 为目标函数个数）： 1M i n i m i z e ( x )S u b j e c t t o (1其中权系数 0i，用来表示各个目标的相对重要程度，一般满足11n 。 加权和法是经典的有效的方法，根据单目标函数形式的不同，大致分为全偏好信息 决策器 优化器 优化规则 结果 西华大学硕士学位论文 3 局加权法 7简单加权和法 10加权最大最小法 14此类方法的优点是简单有效，缺点是需要决策者给出 权重。当决策者对问题的认识不充分时，所给的权重会有很大的偏差 。 目标规划法是由 9等人提出的一种方法。该方法中决策者必须根据待求问题的情况给出每个目标的期望值，并将这些值作为附加约束条件加入原问题，从而使原问题转化为求目标函数值到期望值绝对偏差最小的问题 20，即 1M i n i m i z e ( x )S u b j e c t t o (1其中，对第 i 个目标的期望值。如果设定的期望值在可行域内，这种方法可以得到 优解，且求解效率较高，其缺点主要是需要决策者事先给出各目标函数的期望值，并需要对搜索空间的形状很了解。而且，这种方法对线性目标函数优化问题较为有效，但求解非线性优化问题的效率却不高。 此外还有层次分析法、字典排序法、模糊逻辑法、多属性效用理论等。 2、局部偏好多目标优化又叫交互式多目标优化，即人们通过优化者的求解和决策者的决择相结合的人机对话方式，采用优化阶段和决策阶段反复交替进行，使决策者对目标结果的偏好逐渐清晰的方法来获得 最终的满意解。其求解过程如图： 部偏好模型 交互式优化方法只搜索决策人关心的区域，具有计算量小，决策相对简单等优点。缺点是它要求决策者必须始终参与优化过程，对优化进行控制，这对于许多决策者来说无疑是不现实的。比较有名的交互式优化方法有 决策器 优化器 优化规则 结果 优化结果 西华大学硕士学位论文 4 等人提出的 、移动理想点法、基于目标间权衡的多目标决策方法等等。 3、后验偏好多目标优化是在决策者无法给出先验偏好信息和局部偏好信息下提出的一种算法。一 般是先利用某种优化算法对多目标优化问题进行求解，然后，在 优解的解集中，根据决策者的偏好挑选满意结果。其求解过程如图 验偏好模型 由于决策者是在优化器给出的优化结果中选择满意解，这就使得优化器的设计非常重要。如果没有有效的算法生成能覆盖整个优化问题全部特性的解，那么就有可能遗漏令决策者满意的解。近几年许多的研究者在这方面进行研究，并涌现出大量的有效的多目标优化算法。其中，多目 标进化算法具有不依赖于问题模型、全局最优性、隐含并行性及解决非线性问题的鲁棒性强等特点，被广泛应用于多目标决策领域。 比较典型的算法有多目标遗传算法 (21、小生境 传算法(22、非支配排序遗传算法 (3、 4)、强度 化算法 (5、 6)、 档进化策略 (27、多目标蚁群算法 28、多目标粒子群算法 29等等。 文内容安排及意义 本文研究的主要内容如下 : 第一章是绪论。首先叙述了多目标决策所涉及到的基本概念及多目标决策的特点。根据优化和决策的顺序，分别从三个方面综述了多目标决策的研究现状和发展趋势。并且总结了本文研究的主要内容及意义。 偏好信息 优化器 决策器 优化结果 结果 西华大学硕士学位论文 5 第二章是对 多目标决策基本知识的介绍。主要从优化和决策这两个方面介绍本文所涉及 到的基本知识。在优化方面，给出了多目标优化问题模型 和 的定义；对遗传算法和多目标遗传算法做 了简单的介绍。从决策方面，主要介绍了语言偏好关系、聚合算子和语言 量词。 第三章提出多目标群 组决策模型。分别设计了优化器、筛选器、决策器。 第四章将该模型应用于复杂零件 的网络化制造中 。 第五章是对全文的总结与展望。给出了全文总结以及本文的研究成果，并提出了进一步 的研究 设想。 本文研究的意义表现在以下两个方面： 一是理论上的意义：以往的多目标决策研究多集中在优化器的设计，对整体的解决方案则很少有人涉及。就算提起，也只是文字上的简单介绍。没有一个具体的步骤和例子，而且也仅局限在单人决策上。对于实际问题可操作性不强。本文 探讨 了基于群组决策的多目标优化完整模型，使得目前的多目标决策方法的研究进一步完善。 二是实践上的意义：本文用给出的模型处理了复杂零件协同制造中制造资源优化配置问题，得到了令人满意的结果。该模型可以作为决策部门在决策中的辅助工具，从而促进了科学管理水平的提高。 西华大学硕士学位论文 6 2 多目标决策的预备知识 多目标决策的研究最早可追溯 到 18世纪。 772年 提出了 对 多目标问题如何协调的问题 。 836年从经济 学角度提出了多目标问题的模型。 896年首次 从数 学角度提出了多目标最优决策问题。多目标决策问题越来越受到人们的关注。 多目标决策问题一般 由下 面 5个基本要 素 1组成： 1、 决策变量 , , , )nx x x x L。 2、 目标函数 ) ( ( ) , ( ) , , ( ) ) , 2mx f x f x f x m 3、 可行解集 , ( ) 0 , 1, 2 , , , ( ) 0 , 1, 2 , , n x g x i p h x r q 。 4、 偏好关系。在像集 ( ) ( ) X x x X有某个二元关系反映决策者的偏好。 5、 解的定义。如何在已知的偏好关系下定义 f 在 X 上的最好解。 其中前三个要素属于优化部分，后两个要素属于决策部分。 目标优化的基本概念 一般地，多目标优化问题 1可描述如下： 定义 目标优化问题） 12m i n / m a x ( ) ( ( ) , ( ) , , ( ) )( ) 0 , 1 , 2 , , ,s . t . ( ) 0 , 1 , 2 , , ,f x f x f xg x i ph x r q f (2其中 x 为 n 维决策向量，其可行域为 ( ) 0 , 1, 2 , , , ( ) 0 , 1, 2 , , n x g x i p h x r q 与传统的单目标决策不同，在多目标决策问题中，通常不存在能使所有目标函数同时得到优化的最优解。这是由目标之间相互冲突所导致的结果。此时，需要考虑的是另一种形式的解 有效解（或非劣解）。下面是对有效解的定西华大学硕士学位论文 7 义 20。 定义 行解集） 可行解集 X 定义为满足 公 式 ( ) 0 , 1, 2 , , , ( ) 0 , 1, 2 , , n x g x i p h x r q 定义 对于任意两个决策向量 ,a b X （这里讨论最小化问题，最大化问题类似）： 1) ( ) 1 , 2 , , : ( ) ( )b a i m f a f b 占 优 b 当 且 仅 当 2) ( ) 1 , 2 , , : ( ) ( )b a i m f a f b 弱 占 优 b 当 且 仅 当 1 , 2 , , : ( ) ( )m f a f b 且 3) ()a b a b a b b a与 无 差 别 当 且 仅 当 且: p p。 定义 决策向量 对于集合 来说为占优的（也称非劣的、有效的或满意的）当且仅当： :x A x x p 。如果 x 对于可行解集 称 x 为 x 不能再改善任何指标性能，否则就会引起其它至少一项指标性能的下降。所有 定义 设集合 ， () A 中非支配解的集合： ( ) , p A x A x A x x p 则称集合 () A 的非支配解集，其对应的目标向量组成的集合 ( ( )f p A 被称为 A 的非支配前端。对于 X 来说，如果 ()pX p X是 称其对应的目标向量组成的集合 ()f X为 曲面（简称 由上述定义可知，多个目标之间的冲突或竞争导致多目标优化问题不存在单一的最优解，而是一个 于实际的应用问题，决策者需要根据对问题的了解程度和对目标函数的偏好，从 而形成最后的决策方案。因此，求解多目标优化问题的关键之一就是如 何有效地获取 前，多目标进化算法被广泛应用于求解 获得了很好的效果。 西华大学硕士学位论文 8 目标遗传算法 传算法概述 遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体，从而求得问题的 最优解 30。 遗传算法的一般流程如下 ： 传算法流程图 编码 初始种群 计算适应值 选择、交叉、变异 终止 ? 解码 结束 实际问题参数 华大学硕士学位论文 9 1) 编码与解码 编码是应用遗传算法时要解决的首要问题。在遗传算法中，对不同的具体问题进行编码，其编码的好坏将直接影响选择、交叉、变异等遗传运算。所谓编码就是把问题的可行解从解空间转换到遗传算法处理的搜索空间的转化方法。而由遗传算法解空间向问题空间的转换称为解码。 针对一个具体问题，如何设计一种完美的编码方案一直是遗传算法的应用难点。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的 编码方法，如二进制编码、格雷码编码、浮点数编码、多参数级联编码等等。 2) 适应值计算 在遗传算法中使用适应度这个概念来度量群体中个体的好坏。适用度较高的个体遗传到下一代中的概率就较大；而适应度较低的个体遗传到下一代的概率就相对较小。度量个体适应度的函数称为适应度函数，由目标函数所确定。适应度函数是非负的，任何情况下都希望其值越大越好。而目标函数有可能有正有负，即有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之间进 行变换。有时为了计算方便，也需要对适用度函数进行变换。因此，适用 度函数在大部分情况 下都不等于目标函数。 3) 选择 选择又称复制，是在群体中选择生命力强的个体产生新的群体的过程。遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作。适应度高的个体被遗传到下一代的概率大，适宜度低的个体被遗传到下一代的概率小。选择操作的主要目的是为了避免有用遗传信息的丢失，提高全局收敛性和计算效率。 选择算子的好坏将直接影响遗传算子的计算结果。选择算子选择不当，会使遗传算法过早的收敛于局部最优解。在遗传算法的研究中，选择算子是一个很重要的研究方向。目前常用的选择算子有轮盘赌选择、随机竞争选择、最佳保留选择、 均匀排序、最优保存策略、锦标赛选择、排挤选择等等。 4) 交叉 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个西华大学硕士学位论文 10 主要环节。模仿这个环节，遗传算法中使用交叉运算来产生新的个体。所谓的交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。 遗传算法中，在进行交叉之前要先对群体中的父辈个体进行配对。目前常用的配对策略是随机配对。交叉算子的设计和实现与具体问题密切相关。目前比较常用的交叉算子有单点交叉 、两点及多点交叉、均匀交叉、随机交叉、算术交叉等等。 5) 变异 模仿生物遗传和进化过程中的变异环节，遗传算法中的变异是指以较小的概率对个体编码串上的某个或某些位置上的值进行改变，从而生成新个体。变异本身是一种随机算法，但与选择、交叉算子结合后，能够避免由于选择和交叉运算而造成的某些信息丢失，保证遗传算法的有效性。 交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力。交叉算子与变异算子相互配合，共同完成对搜索空间的全局搜索和局部搜 索。变异算子除了改善遗传算法的局部搜索能力外，还维持群体的多样性，防止出现早熟现象。常用的交叉运算有基本位变异、均匀变异、边界变异、高斯近似变异等等。 目标优化 算法 概述 对于求解多目标优化问 题的 解，目前已有多种基于遗传算法的求解方法。下面介绍五种常 用的方法 30。 1) 权重系数变换法 对于一个多目标优化问题，若给其每个子目标函数 ( ) ( 1 , 2 , , )if x i n赋予权重 ( 1, 2 , , )iw i n，其中)各个子目标函数 ()1()n w f x (2西华大学硕士学位论文 11 若将 u 作为多目标优化问题的评价函数，则多目标优化问题就可转化为单目标优化问题，即可以利用单目标优化的遗传算法求解多目标优化问题。 2) 并列选择法 并列选择法的基本思想是，先将群体中的全部个体按子目标函数的数目均等地划分为一些子群体，对每个子群体分配一个子目标函数，各个子目标函数在相应的子群体中独立地进行选择运算，各自选择出一些适应度高的个体组成一个新的子群体，然后再将所有这些新生成的子群体合并成一个完整的群体，在这个群体中进行交叉和变异运算，从而生成下一代的完整群体，如此不断的进行“分割 并列选择 合并”操作，最终可求出多目标优 化问题的 解。 3) 排列选择法 排列选择法的基本思想是 ，基于 体，对群 体中的各个个体进行排序，依据这个排序次序来进行进化过程中的选择运算，从而使得排在前面的最优个体将有更多的机会遗传到下一代群体中。如此这样经过一定代数的循环之后，最终就可求出多目标 优化问题的 4) 共享函数法 求解多目标最优化问题时，一般希望所得到的解能够尽可能地分散在整个解集合内，而不是集 中在其