第３５卷第２期 ２０１ １年４月 南京理工大学学报 Ｊｏｕｒｎａｌ ｏｆ Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｖｏ１．３５ Ｎｏ．２ ＡＤｒ．２０１１ 一种基于模糊逻辑弓 偏好信息的多目标遗传算法 申晓宁，李 涛，张 敏 （南京信息工程大学信息与控制学院，江苏南京２１００４４） 摘 要：针对多目标优化存在多个非支配解、用户难以挑选的问题，该文提出一种交互式引入决 策者偏好信息的多目标遗传算法。该算法使用一种新型的九级标度赋值法把决策者通过语言 表达的偏好信息量化为各目标的重要性因子，采用模糊推理系统构造一种基于偏好信息的“强 度优于”关系替代常规的“Ｐａｒｅｔｏ支配”关系，以比较个体之间的优劣。对算法的计算复杂度进 行了理论分析。仿真实验表明，该算法具有实时处理偏好信息的能力，与２种经典多目标遗传 算法相比，该算法能够搜索到质量更优的解。 关键词：模糊逻辑；多目标优化；遗传算法；偏好 中图分类号：ＴＰ１８ 文章编号：１００５—９８３０（２０１１）０２－０２４５－０７ Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ Ｉｎｃｏｒｐｏｒａｔｉｎｇ Ｐｒｅｆｅｒｅｎｃｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｂａｓｅｄ ｏｎ Ｆｕｚｚｙ Ｌｏ ｇｌＣ ＳＨＥＮ Ｘｉａｏ—ｎｉｎｇ，ＬＩ Ｔａｏ，ＺＨＡＮＧ Ｍｉｎ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ，Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ ２１００４４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｄｉｆｉｃｕｌｔｙ ｆｏｒ ｕｓｅｒｓ ｔｆｏ ｓｅｌｅｃｔ ｆｒｏｍ ｍａｎｙ ｎｏｎ—ｄｏｍｉｎａｔｅｄ ｓｏｌｕｔｉｏｎｓ ｉｎ ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ，ａ ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎｃｏｒｐｏｒａｔｉｎｇ ｐｒｅｆｅｒｅｎｃｅ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｄｅｃｉｓｉｏｎ ｍａｋｅｒ ｉｎｔｅｒａｃｔｉｖｅｌｙ ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｍａｋｅｓ ｕｓｅ ｏｆ ａ ｎｅｗ ｎｉｎｅ－ｓｃａｌｅ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄ ｔｏ ｃｏｎｖｅｒｔ ｔｈｅ ｌｉｎｇｕｉｓｔｉｃ ｐｒｅｆｅｒｅｎｃｅｓ ｅｘｐｒｅｓｓｅｄ ｂｙ ｔｈｅ ｄｅｃｉｓｉｏｎ ｍａｋｅｒ ｔｏ ｉｍｐｏｒｔａｎｃｅ ｆａｃｔｏｒｓ ｏｆ ｏｂｊｅｃｔｉｖｅｓ．Ａ ｎｅｗ ｏｕｔｒａｎｋｉｎｇ ｒｅｌａｔｉｏｎ ｃａｌｌｅｄ“ｓｔｒｅｎｇｔｈ ｓｕｐｅｒｉｏｒ’’ｗｈｉｃｈ ｉｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｐｒｅｆｅｒｅｎｃｅ ｉｎｆｏｒｍａｔｉｏｎ ｉｓ ｃｏｎｓｔｒｕｃｔｅｄ ｖｉａ ａ ｆｕｚｚｙ ｉｎｆｅｒｅｎｃｅ ｓｙｓｔｅｍ ｔｏ ｃｏｍｐａｒｅ ｉｎｄｉｖｉｄｕａｌｓ ｉｎｓｔｅａｄ ｏｆ ｔｈｅ ｃｏｍｍｏｎｌｙ ｕｓｅｄ“Ｐａｒｅｔｏ ｄｏｍｉｎａｎｃｅ”ｒｅｌａｔｉｏｎ．Ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ａｎａｌｙｚｅｄ ｔｈｅｏｒｅｔｉｃａｌｌｙ，ａｎｄ ｉｔｓ ａｂｉｌｉｔｙ ｔｏ ｈａｎｄｌｅ ｐｒｅｆｅｒｅｎｃｅ ｉｎｆｏｒｍａｔｉｏｎ ｉｓ ｖａｌｉｄａｔｅｄ ｔｈｒｏｕｇｈ ｓｉｍｕｌａｔｉｏｎ．Ｃｏｍｐａｒｉｓｏｎｓ ｔｏ ｔｗｏ ｃｌａｓｓｉｃａｌ ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｓｅａｒｃｈ ｂｅｔｔｅｒ ｓｏｌｕｔｉｏｎｓ． Ｋｅｙ ｗｏｒｄｓ：ｆｕｚｚｙ ｌｏｇｉｃ；ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｐｒｅｆｅｒｅｎｃｅ 收稿日期：２００９—０２—２４ 修回日期：２００９—０４—２７ 基金项目：空间智能控制技术国家级重点实验室资助项目；江苏省高校自然科学研究计划项目（１０ＫｊＢ５１００１０）； 南京信息工程大学科研基金 作者简介：申晓宁（１９８１一），女，博士，讲师，主要研究方向：进化算法、多目标优化，Ｅ—ｍａｉｌ：ｓｘｎｙｓｔｓｙｔ＠ｓｉｎａ．ｃｏｎ。 ２４６ 南京理工大学学报 第３５卷第２期 遗传算法基于群体进行操作，它具有内在并 行性，能够在一次运行结束后进化求得一组解，因 此遗传算法非常适合于求解具有多个解的多目标 “强度优于”关系替代常规的“Ｐａｒｅｔｏ支配”关系 判断候选解之间的优劣；允许决策者周期性地改 变偏好，以调整算法的搜索方向，改变解的范围。 仿真算例表明了本文算法的有效性。 优化问题。多目标遗传算法的一个关键技术是适 应值评价和选择策略的选取，目前通用的方法是 基于“Ｐａｒｅｔｏ支配”概念对遗传算法的群体进行排 序，通过排序值计算每个个体的适应值，并依据适 应值对群体进行选择操作。由于“Ｐａｒｅｔｏ支配”概 １ 问题描述 以下给出多目标优化问题中的几个重要 念视所有目标具有相同的重要性，而未引人任何 偏好信息，且它是一种较强的排序关系，因此，该 算法往往在运行结束后会产生大量分布范围很 广、且无法比较优劣程度的Ｐａｒｅｔｏ非支配解。众 多的非支配解在实际工程设计中无法直接应用， 需要决策者从中挑选出一个满意解作为问题的最 终解，这一过程无疑大大增加了决策者的决策 负担。 为了解决上述问题，一些学者对“Ｐａｒｅｔｏ支 配”的概念进行了改进。文献［１］在常规的 “Ｐａｒｅｔｏ支配”概念中引入了各目标的指标（ｇｏａ１） 信息，定义了一种称为“ｐｒｅｆｅｒａｂｉｌｉｔｙ”的关系算子， 并基于该算子对群体进行排序，以缩小解的搜索 范围。该方法简单易行，但事先需消耗较多的计 算资源用于确定每个目标的变化范围；文献［２］ 建立了基于权重值的“Ｐａｒｅｔｏ支配”关系，以引导 算法搜索到偏好区域内的解，然而该方法有多个 待定参数，它们的取值对算法性能有较大的影响； 文献［３］使用多准则决策中ＥＬＥＣＴＲＥ法构造的 “级别不劣于”关系对进化群体进行排序，该方法 在一定程度上克服了“Ｐａｒｅｔｏ支配”关系难以处理 高维优化问题的缺点，但ＥＬＥＣＴＲＥ法中参数的 取值对解集的构成有显著影响，且构造和使用该 “级别不劣于”关系的过程也很复杂；文献［４］给 出了“模糊最优”的定义，通过调节参数可以对应 不同的模糊最优度求得不同的Ｐａｒｅｔｏ非支配解集 的子集；该方法解决了基于“Ｐａｒｅｔｏ支配”概念的 算法在高维问题中求得的解集规模过大的问题； 但由于未考虑偏好信息，决策者在算法运行结束 之后仍具有较大的决策负担。 为了利用偏好信息指导算法的搜索方向，使 得算法最终只求得期望区域内的若干解，本文提 出一种基于模糊逻辑引人偏好信息的多目标遗传 算法（ＦＬＭＯＧＡ）。ＦＬＭＯＧＡ通过一种新型的９级 标度赋值法把决策者给出的两两目标间的偏好信 息量化为各目标的重要性因子；构造一种新型的 定义。 定义１＿５ Ｊ—Ｐａｒｅｔｏ支配假设 为多目标优 化问题的可行参数空间，Ｆ（Ｘ）＝（ （ ）， （ ）， …， （ ））为目标向量。Ｘ ∈ ，Ｘｆ∈ ，称 Ｐａｒｅｔｏ支配Ｘ （记作Ｘ ＜ ）当且仅当 Ｖｉ∈｛１，２，…，ｍ｝ （ ）≤ （ ｆ） 且 ３ｊ∈｛１，２，…，，ｎ｝ （ ） （ １） （１） 定义２ｌ５ Ｊ—Ｐａｒｅｔｏ支配 如果在某一集合中 不存在任何其他解Ｘ Ｐａｒｅｔｏ支配Ｘ，则称Ｘ为该 集合中的非支配解；如果 为多目标优化问题整 个可行参数空间中的非支配解，则称 为该问题 的Ｐａｒｅｔｏ最优解。 由定义１可见，只有当解 在所有目标上均 不劣于，且至少在一个目标上优于解Ｘ 时，才能 认为 Ｐａｒｅｔｏ支配Ｘｊ，因此，“Ｐａｒｅｔｏ支配”是一种 较强的排序关系。当优化问题的维数较高（目标 较多）时，它将使得遗传算法有限规模的群体中 产生大量的非支配解，这些非支配解之间缺乏确 定的比较标准，难以从中进行选优操作，从而导致 算法出现停滞现象。为了克服“Ｐａｒｅｔｏ支配”概念 的上述局限性，本文将通过建立模糊推理系统，构 造一种基于偏好信息的“强度优于”关系替代 “Ｐａｒｅｔｏ支配”关系比较解之间的优劣，使得算法 在运行结束后只得到期望区域内的少量解，便于 决策者进行分析与决策。 ２基于模糊逻辑的“强度优于’’关系 由于客观事物的复杂性和人类思维的模糊 性，一般人们只能对目标间的偏好提供定性的语 言描述；同时，人们对２个解在各目标上的相互改 进程度也存在主观上的认识偏差。因此，通过模 糊逻辑在算法中引入偏好信息和解之间的改进幅 度对解进行比较，以克服“Ｐａｒｅｔｏ支配”概念的局 限性，是一个恰当的选择。 总第１７７期 申晓宁李涛张敏一种基于模糊逻辑引入偏好信息的多目标遗传算法 ２４７ ２．１ ９级标度赋值法 ２．２“强度优于”关系 决策者在表达偏好时，通常只能采用诸如 “目标Ａ比目标Ｂ重要得多”这样的语言表达两 两目标间的相对重要性。本文通过一种新型的９ 级标度赋值法把目标间的相对偏好量化为各目标 的重要性因子。 ２．２．１相对强度值的计算 构建Ｍａｍｄａｎｉ型模糊推理系统，记为Ｆ 。不 失一般性，考虑多目标最小化问题。在目标． （ｉ＝ １，２，…，ｍ）上对２个解Ｘ 和 进行比较时，把 的重要性因子Ｐ。和 对ｘ 在 上的改进幅值 Ｄ （ ， ）＝ （ ）－Ｚ（ ）作为模糊系统的２个输 入，系统输出为 值．ｓ （ ， ｚ）。 （１）输入输出变量的模糊化 （ａ）输入变量Ｐ ：Ｐ ∈［０，１］。将目标 的重 要性作为语言变量，定义模糊子集：｛不重要 对 在目标． 上的强度 把目标间的相对重要程度划分为９个等级， 为每个等级赋予一个适当的数值。设目标． 对． （ｉ，． ＝１，２，…，ｍ）相对重要性的９级标度赋值为 ｃ 则ｃ 的取值由表１确定，由此可得目标的赋值 矩阵Ｃ＝（Ｃ ） 。与表１中的“重要”相对的是 “次要”，例如目标 比 重要一点，则ｆｊ比 次 要一点。 表１ 目标间相对重要程度的９级标度赋值 （ＮＩ），一般重要（ＭＩ），很重要（ｗ）｝。采用三角 形隶属度函数，如图１（ａ）所示。 （ｂ）输入变量Ｄ （Ｘ ， ｆ）（简称Ｄ ）：将Ｘ 对 在． 上的改进程度作为语言变量，定义模糊子 集：｛负大（ＮＢ），负小（ＮＳ），零（ＺＥ），正小（ ）， 正大（Ｐ ）｝。隶属度函数如图１（ｂ）所示。Ｄ Ｅ ［一尺 ，Ｒ ］， 为当前所有候选解在 上的最大值 和最小值之差；Ａ 为阈值参数，它的值由决策者 预先指定。对于最小化问题，当，） ＞０时，说明 对 在 上有所改进，Ｄ 的值越大，则改进的程 度越大。反之亦然。 （ｃ）输出变量５ （ ， ）（简称ｓ ）：Ｓ ∈［一１， 由赋值矩阵Ｃ计算目标 的重要性因子Ｐ １］。将Ｘ 对 在 上的强度作为语言变量，定 义模糊子集：｛负大（ＮＢ），负小（ＮＳ），零（ＺＥ），正 小（Ｐ５），正大（ＰＢ）｝。隶属度函数如图１（ｃ）所 Ｐ ＝ＳＬ ／∑ｓ ＝１，２，…，ｍ ：１ （２） 示。当Ｓ。＞０，５ 的值越大，则 在 上优于ｘ 的 强度越大，当Ｓ ＜０，Ｓ 的值越小，则ｘ 在 上劣 于ｘ，的强度越大。 式中观 ＝∑ｃ 为目标 对其余所有目标的九 ｉ＝１ ｌ≠ｉ 标度优序数。 Ｒ －２ －２／２ ０ ２／２ Ａ， Ｒ （ａ）输入变量 的隶属度函数 （ｂ）输入变量Ｄ 的隶属度函数 （ｃ）输入变量 的隶属度函数 图１ 输入和输出变量的隶属度函数 （２）模糊推理 （３）反模糊化 依据表２给出的１５条规则进行模糊推理。 模糊规则制定的原则是：目标 越重要，解ｘ 对 改进（或 差于 ）的程度越大，则 在 上 优于（或劣于） ，的强度越大；反之亦然。 采用重心法 Ｊ，把输出变量ｓ，的模糊集进行 反模糊化，求出Ｘ 对Ｘ，在 上的强度清晰值 Ｓ （ ， ｆ）。 考虑所有ｍ个目标，则 对Ｘ 的相对强度 ２４８ 南京理工大学学报 第３５卷第２期 值为 程如下： ｓ（ｘ ，ｘｔ）＝∑Ｓ （ ，ｘｔ） （３） （１）设群体ｐｏｐ中有Ⅳ个个体，依据定义３ 计算每个个体Ｘ ∈ｐｏｐ（ｋ＝１，２，…，Ⅳ）的强度值 （ ）； 式中：当 在目标 上劣于Ｘｆ时，Ｓ （Ｘ ，Ｘｆ）＜Ｏ， 即对总和Ｓ（ｘ ，Ｘ ）进行惩罚；当Ｘ 在 上优于Ｘ （２）计算每个个体 排挤距离 ｄ ； ｐｏｐ（ｋ＝１，２，…，Ⅳ）的 时，Ｓｉ＊（Ｘ ，Ｘ ）＞０，即对总和．ｓ（ ，Ｘ１）进行奖励。 因此，Ｓ（Ｘ ，Ｘ ）的值可正可负。 表２模糊规则表 （３）记ｓ ＝ 艘ｎ．， （．ｓ （ ）），ｄｍ“ ｍ．２ａｌｘ…。 ：（ｄｋ），对Ｘ ∈ｐｏｐ（ｋ＝１，２，…，Ⅳ）计算适应值 ２．２．２“强度优于”关系 定义３设 为当前的候选解集，Ｘ ∈Ｘ ，则Ｘ 在 中的强度值ｓ （ ）定义为：Ｓ （ ）＝∑Ｓ（ｘ ， ＸｌＥ ｘｌ＃ｘｋ Ｘ１），强度值ｓ一（ ）定义为：ｓ～（ ）＝∑ｓ（ｘ ，Ｘ ）。 ｘｌＥ Ｘｌ＃Ｘｋ 强度值Ｊｓ （ ）度量Ｘ 优于其余所有候选解 的程度，强度值 一（ ）度量其余所有候选解优于 Ｘ 的程度。基于强度值ｓ （ ）和ｓ一（ ），给出４ 个体间“强度优于”关系的定义。 定义４设 为当前的候选解集，Ｘ ∈Ｘ ，Ｘ ＥＸ ， 为一个非负数。称 强度优于Ｘ，当且仅 当下述３个条件同时成立： （１）．ｓ （ ）一Ｓ （ ｆ）≥ ； （２）Ｓ一（ ）一 一（ ）≤一 ； （３）条件（１）和（２）中至少有一个等号不成立。 由定义４可见，如果某个候选解的强度值ｓ 越大，强度值Ｓ一越小，则该解越优。 定义５如果在某一集合中不存在任何其他 解Ｘ 强度优于 ，则称Ｘ为该集合中的强度非 劣解。’ ３引入偏好信息的多目标遗传算法 通过上述基于模糊逻辑的“强度优于”关系， 设计一种引入决策者偏好信息的多目标遗传 算法。 ３．１适应值评价 算法需要对个体进行适应值评价，以对进化 群体采用选择操作。ＦＬＭＯＧＡ的适应值评价过 如下： ，， ｉｆｔ（ｘ ）＝（Ｊｓ （ ）一Ｓｍｉｎ＋１）×（ ） （４） ｔ／，ｍａｘ 式（４）中，（ＩＳ （Ｘ ）一５ Ｉｎ十１）项把Ｘｋ的强度值 （ ）调整为大于１的数；（ｄｋ／ｄ一） 项的作用 是利用密度信息调整个体的适应值；个体 的适 应值越大，表示 的性能越优。 ３．２算法步骤 ＦＬＭＯＧＡ采用精英保留的策略，设置一个外 部存储器保存历代搜索到的强度非劣解。算法步 骤如下： 步骤１令进化代数ｔ＝１，随机产生一个规 模为Ⅳ的初始群体ｐｏｐ ，并创建一个空的外部存 储器ａｒｃｈｉｖｅ ： ；把决策者给出的目标间相对重 要程度量化为各目标的重要性因子；设最大进化 代数＝ ； 步骤２计算群体ｐｏｐ 中每个个体的目标向 量、强度值ｓ 和排挤距离，对它们进行适应值 评价； 步骤３采用二进制联赛法从ｐｏｐ 中选择一 些适应值较优的个体组成交配池； 步骤４对交配池中的个体依概率进行交叉 和变异操作，生成子代群体ｃｈｉｐｏｐ ； 步骤５求出并集ｃｈｉｐｏｐ，ｔ３ａｒｃｈｉｖｅ 中所有不 重复的强度非劣解并把它们更新为新一代的外部 集合ａｒｃｈｉｖｅ 。如果ａｒｃｈｉｖｅ川中解的个数超过其 最大容量 ，则依据密度信息（排挤距离）对其进 行裁减； 步骤６分别从ａｒｃｈｉｖｅｆ＋１和ｃｈｉｐｏｐ 中随机选 取若干个体（共取Ⅳ个），合并构成下一代的父代 群体ｐｏｐｆ＋Ｊ； 步骤７如果进化代数ｔ满足一定的条件，则 与决策者进行交互，否则，直接进入步骤８。交互 时算法通过图形用户界面显示当前搜索到的解的 信息，并允许决策者改变偏好； 总第１７７期 申晓宁李涛张敏一种基于模糊逻辑引入偏好信息的多目标遗传算法 ２４９ 步骤８如果ｔ≥Ｔ，则算法终止，把当前外部 存储器ａｒｃｈｉｖｅ…中保存的强度非劣解作为最终的 满意解集输出，否则，ｔ＝ ＋１，转到步骤２。 ３．３算法的计算复杂度 ３．３．１时间复杂度 设优化问题有ｍ个目标，模糊推理系统中的 规则条数为ｎ ，则在最坏情况下对影响ＦＬＭＯＧＡ 时间复杂度的各主要步骤分析如下： （１）更新外部集合：为了确定ｃｈｉｐｏｐ ｕａｒｃｈｉｖｅ 中所有的强度非劣解，最多需进行ｍｎ （Ⅳ＋ ）（ ＋ Ｍ一１）次模糊推理运算得到两两个体之间的相对强 度值，进行２×（Ⅳ＋ ）（Ⅳ＋ 一１）次加法运算求得各 个个体的强度值，并基于“强度优于”关系进行２ｘ （Ⅳ＋ ）（／Ｖ＋ 一１）次比较。由于ｍ１＞２，因此，该步 骤的时问复杂度为０（ｍｎ （Ⅳ＋Ｍ） ）； （２）对外部集合进行裁减：外部集合在更新 之后最多有Ⅳ＋ 个个体，把Ⅳ＋ 个个体分别依 ｍ个目标进行排序，以计算个体间的排挤距离。 采用快速排序法，该步骤的时间复杂度为０（ｍ（Ⅳ ＋ ）ｌｏｇ（Ⅳ＋ ））。 ＦＬＭＯＧＡ总的时间复杂度取上述分析结果 中的较大值Ｏ（ｍｎ．（Ⅳ＋ ） ）。 ３．３．２空间复杂度 ＦＬＭＯＧＡ的空间复杂度同样主要取决于对 外部集合的更新与裁减操作： （１）更新外部集合：ｃｈｉｐｏｐ，ｕ ａｒｃｈｉｖｅ 中最多 有Ⅳ＋ 个个体，保存其中两两个体之间的相对强 度值，该步骤的空间复杂度为０（（Ⅳ＋ ） ）； （２）对外部集合进行裁减：外部集合在更新 之后最多有Ⅳ＋ 个个体，保存它们的排挤距离， 该步骤的空间复杂度为Ｄ（，ｖ＋ ）。 ＦＬＭＯＧＡ总的空间复杂度取上述分析结果 中的较大值Ｏ（（．７ｖ＋Ｍ） ）。 ３．３．３与其他算法的比较 ＮＳＧＡ—Ｉ１ Ｉ ｓ］是一种经典的快速非支配排序多 目标遗传算法，设其群体规模为 ，则其时间复杂 度为Ｏ（ｍＬ ），空间复杂度为０（Ｌ ） 。 ＳＰＥＡ２［ｓｌ是另一种高效的多目标遗传算法，它基 于Ｐａｒｅｔｏ支配的概念评价个体的适应值，设其群 体规模为Ⅳ ，外部存储器大小固定为 ，则其时 间复杂度为Ｏ（（Ⅳ ＋ ） ），空问复杂度为Ｏ（（Ｎ ＋ ） ） 。在ＳＰＥＡ２中，令Ⅳ ＋ ＝ ，在 ＦＬＭＯＧＡ中，令Ｎ＋Ｍ＝Ｌ，则ＦＬＭＯＧＡ的空问复杂 度与ＮＳＧＡ—ＩＩ、ＳＰＥＡ２相同，时间复杂度是 ＮＳＧＡ一１Ｉ的ｎ 倍，是ＳＰＥＡ２的ｍｎ ／Ｌ倍。虽然与 ＮＳＧＡ一Ⅱ和ＳＰＥＡ２相比，当优化目标的个数较大 且模糊规则条数较多时，ＦＬＭＯＧＡ在最坏情况下 的时间复杂度较大，但由下文的仿真结果可见，它 搜索到的解的质量更优，且能够依据偏好的变化 及时地调整搜索的方向，直接求得期望区域内的 若干解，减轻了决策者的决策负担。 ４仿真实验及实现 ４．１优化问题描述 为了验证所提算法ＦＬＭＯＧＡ的有效性，把它 应用于一个机器人手臂驱动器的控制系统参数优 化问题中 Ｊ。该系统框图如图２所示，它的设计 目标是选取适当的控制器参数ＫＥ（０，６），以满足 如下性能指标： （１）ｆｌ：调节时间ｔ （２％准则）最小； （２） ：上升时间ｔ 最小； （３）． ：超调量 最小； （４） ：增益裕度ｈ最大； （５） ：相角裕度 最大； （６）ｆ６：对单位阶跃扰动的最大响应ｌ ｙ ｌ 最小； （７）ｆ７：速度误差常数 最大。 把上述问题转换为如下多目标最小化问题： Ｍｉｎｉｍｉｚｅ Ｆ（Ｋ）＝［ （Ｋ） （Ｋ） （Ｋ）， １ （Ｋ），１织（Ｋ），ｆ６（Ｋ），１／Ｌ（Ｋ）］ Ｓ．ｔ． Ｋ∈（０，６） （５） 图２机器人手臂驱动器的控制系统框图 ４．２参数的选取 ＦＬＭＯＧＡ采用实数编码，群体规模Ⅳ＝５０，外 部存储器最大容量 ＝５０，最大进化代数 ＝１００。 使用模拟二进制交叉算子和多项式变异算子 ， 交叉和变异概率分别为Ｐ ：０．９，Ｐ ＝１／２。在求 取强度非劣解时，参数 的值取为１０。在图１模 糊系统输入变量Ｄ （ｉ＝１，２，…，７）的隶属度函数 中，参数Ａ 的值分别指定为：ｔ 对应的Ａ。取为 ５ Ｓ，ｔ，对应的Ａ 取为１ Ｓ， 对应的Ａ 取为５，ｈ 南京理工大学学报 第３５卷第２期 对应的Ａ 取为５， 对应的Ａ 均取为２０。，Ｉ ｙ “ｌ 对应的Ａ６取为０．５，Ｋ，对应的Ａ 取为０．３ ｓ一。 偏好）时搜索到的强度非劣解的分布范围及对应 的目标值分布范围分别如表３和表４所示，各偏 好下解的分布情况分别如图３（ａ）、（ｂ）、（ｃ）所 示。从３种偏好下求得的解中各随机选取５个 解，图４（ａ）、（ｂ）、（Ｃ）分别给出了这些解的单位 阶跃响应曲线。 ４．３仿真结果 ４．３．１实时处理偏好信息的能力 在算法的初始阶段，认为所有目标的重要性 相同，相应的目标重要性因子为Ｐ，＝［０．１４２ ９， ０．１４２ ９，０．１４２ ９，０．１４２ ９，０．１４２ ９，０．１４２ ９， 由图３，４和表３，４可见，在偏好Ｐ，（各目标 同样重要）下，ＦＬＭＯＧＡ求得的强度非劣解的分 布范围较广，对应的各目标值范围也较广；在偏好 Ｐ。（增强了ｔ，的重要性，降低了ｈ、ｙ的重要性） ０．１４２ ９］；进化４０代之后，改变偏好，认为目标ｔ， 比ｔ 重要， 对ｔ 的重要性介于同样重要与次要 一点之间但比ｔ，次要，ｈ和ｙ均比ｔ 次要、比ｔ，次 要得多、对 介于次要一点与次要之间，Ｉ ｍａｘ ｌ和 下，强度非劣解转移到值相对较大的范围内，它们 在目标ｔ 、Ｉ “Ｊ、 ，上的性能较好，而在ｔｓ、 、ｈ、 与 同样重要，相应的目标重要性因子为Ｐ２： ［０．１５７ ７，０．２２６ ２，０．１３９ ９，０．０８０ ４，０．０８０ ４， ０．１５７ ７，０．１５７ ７］；继续进化２０代后，即进化代 数括６０时，再次改变偏好，认为￡，对ｔ 的重要性 介于次要一点和次要之间， 比ｔ 重要一点、比ｔ 重要，ｈ和 与ｔ 同样重要，Ｉｙ Ｉ和 均比ｔ 次 上的性能较差；在偏好尸３（增强了 的重要性， 降低了ｔ 、Ｉｙ Ｉ、 的重要性）下，强度非劣解集 中到值较小的范围内，它们在目标 、 、ｙ上的性 能较好，而在ｔ 、ｆｙ “Ｉ、Ｋ 上的性能较差。由此可 见，当用户偏好发生变化时，ＦＬＭＯＧＡ能够快速 做出响应，自适应地调整搜索的方向，从而得到期 望区域内的一组解。 表３ 各偏好下强度非劣解 的分布范围 要一点、对ｔ，介于同等重要与重要一点之间、对ｏｒ 介于次要一点与次要之间，相应的目标重要性因 子为Ｐ３＝［０．１５７ ７，０．０９８ ２，０．１９０ ５，０．１５７ ７， ０．１５７ ７，０．１ｌ９ ０，０．１１９ ０］，继续进化４０代，即 ｆ＝１００时终止算法。 ＦＬＭＯＧＡ在ｔ＝４０，６０，１００（对应３种不同的 表４各偏好下强度非劣解的目标值分布范围 强度非劣解序号 （ａ） 强度非劣解序号 （ｂ） 强度非劣解序号 （ｃ） 图３强度非劣解分布随偏好的变化 一 １．ｏ －－－一 Ｔ，总第１７７期 申晓宁李涛张敏一种基于模糊逻辑引入偏好信息的多目标遗传算法 ２５１ ４．３．２与其他算法的比较 把ＦＬＭＯＧＡ与基于“Ｐａｒｅｔｏ支配”概念排序 的多目标遗传算法ＮＳＧＡ一１１、ＳＰＥＡ２进行比较。 ＮＳＧＡ一１１的群体规模￡取１００；ＳＰＥＡ２中，取Ｎ ＝ ＝５０（满足Ⅳ ＋Ｍ ＝Ｌ）；ＦＬＭＯＧＡ中，取Ｎ＝Ｍ＝５０ （满足Ｎ＋Ｍ＝Ｌ）。ＦＬＭＯＧＡ始终保持初始的偏好 信息不变，不失一般性，设为Ｐ２＝［０．１５７ ７， ２２６ ２，ｏ．１３９ ９，Ｑ ０８０ ４，Ｑ ０８０ ４，Ｑ １５７ ７，ｏ．１５７ ７］。 把３种算法各运行１０次，每次的进化代数均取 １００。表５给出了３种算法的运行时间 、解的个 数ｎ、解的分布范围ｒ及收敛性测度 Ⅲ９ （度量算 法搜索到的解集到问题真实的Ｐａｒｅｔｏ最优解集在 目标空间上的平均最短距离， ．越小，则算法的 收敛性能越好）在１０次运行结果中的平均值。 虽然３．３．３节的分析指出，与ＮＳＧＡ－Ｉ１、 ＳＰＥＡ２相比，所提算法ＦＬＭＯＧＡ在最坏情况下 的时间复杂度较大，但由于ＦＬＭＯＧＡ和ＳＰＥＡ２ 的群体规模较小，因此由表５可见，它们实际消 耗的运行时间较短，而ＮＳＧＡ—Ｉ１的运行时间却较 长。此外，ＦＬＭＯＧＡ的收敛性能较优，它产生的 解的个数较少，解的分布范围也较小。由于 ＮＳＧＡ—Ｉ１、ＳＰＥＡ２的目标是求得均匀分布在整个 Ｐａｒｅｔｏ折衷曲面上的多个非支配解，这些解的优 劣程度相同，决策者需要根据问题的要求从这些 解中进行决策，挑选出满意解作为问题的最终 解，而ＦＬＭＯＧＡ却能够在算法运行过程中直接 依据偏好信息对期望区域进行小范围的集中搜 索，并且允许偏好发生变化，因此它求得的解的 质量更高（位于偏好区域且收敛性能好），决策 者的决策负担也较轻。 表５ ３种算法比较 ５ 结论 本文给出一种从定性到定量的偏好处理方 法，在分析常规的“Ｐａｒｅｔｏ支配”关系局限性的基 础上，基于模糊逻辑构造了一种引入偏好信息的 “强度优于”排序关系，并提出了一种与决策者 进行周期性交互的多目标遗传算法，对算法的计 算复杂度进行了理论分析。仿真实验表明所提 算法能够有效地依据偏好信息搜索到期望区域 内的折衷解，并能随着偏好的变化实时地调整搜 索的方向，改变解的范围。与２种经典的多目标 遗传算法的比较说明，本文算法能够求得质量更 高的解，可有效地减轻决策者的负担。 参考文献： ［１］ Ｆｏｎｓｅｃａ Ｃ Ｍ，Ｆｌｅｍｉｎｇ Ｐ Ｊ．Ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｇｅｎｅｔｉｃ ｌａｇｏ— ｒｉｔｈｍｓ ｍａｄｅ ｅａｓｙ：ｓｅｌｅｃｔｉｏｎ，ｓｈａｒｉｎｇ，ａｎｄ ｍａｔｉｎｇ ｒｅｓｔｒｉｃｔｉｏｎ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｒｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ ｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｙｓｔｅｍｓ：Ｉｎｎｏｖａｔｉｏｎｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］．Ｓｈｅ￣ｅｌｄ， ＵＫ：ＩＥＥ．１９９５：４２—５２． ［２］Ｃｖｅｔｋｏｖｉｅ Ｄ，Ｐａｒｍｅｅ Ｉ Ｃ．Ｐｒｅｆｅｒｅｎｃｅｓ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉ— ｃａｔｉｏｎ ｉｎ ｅｖｏｌｕｔｉｏｎａｒｙ ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｓａｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２ＯＯ２，６ （１）：４２—５７． ［３］ 崔逊学，林闯．一种基于偏好的多目标调和遗传算 法［Ｊ］．软件学报，２００５，１６（５）：７６１—７７０． ［４］ Ｆａｒｉｎａ Ｍ，Ａｍａｔｏ Ｐ．Ａ ｆｕｚｚｙ ｄｅｆｉｎｉｔｉｏｎ ｏｆ“ｏｐｔｉｍａｌｉｔｙ” ｆｏｒ ｍａｎｙ－ｃｒｉｔｅｒｉａ ｏｐｔｉｉｍｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ－－Ｐａｒｔ Ａ：Ｓｙｓｔｅｍｓ ａｎｄ Ｈｕｍａｎｓ，２００４，３４（３）：３１５－３２６． ［５］ Ｚｉｔｚｌｅｒ Ｅ，Ｔｈｉｅｌｅ Ｌ．Ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉ— ｔｈｉｎｓ：ａ ｃｏｍｐａｒａｔｉｖｅ ｅａｓｅ ｓｔｕｄｙ ａｎｄ ｔｈｅ ｓｔｒｅｎｇｔｈ ｐａｒｅｔｏ ａｐｐｒｏａｃｈ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，１９９９，３（４）：２５７—２７１． ［６］Ｌｅｅ Ｃ Ｃ．Ｆｕｚｚｙ ｌｏｇｉｃ ｉｎ ｃｏｎｔｒｏｌ ｓｙｓｔｅｍｓ：Ｆｕｚｚｙ ｌｏｇｉｃ ｃｏｎｔｒｏｌｌｅｒ．Ｐａｒｔ Ｉ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓ－ ｔｅｒｎｓ，Ｍａｎ，ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ，１９９０，ＳＭＣ－２０：４Ｏ４ —４１８． ［７］Ｄｅｂ Ｋ，Ｐｒａｔａｐ Ａ，Ａｇａｒｗａｌ Ｓ，ｅｔ ａ１．Ａ ｆａｓｔ ａｎｄ ｅｌｉｔｉｓｔ ｍｕｈｉｏｂｊｅｃｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ：ＮＳＧＡ—ｌＩ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６ （２）：１８２—１９７． ［８］ Ｚｉｔｚｌｅｒ Ｅ，Ｄｅｂ Ｋ，Ｔｈｉｅｌｅ Ｌ．Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｍｕｈｉｏ－ ｂｊｅｃｔｉｖｅ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ：Ｅｍｐｉｒｉｃａｌ ｒｅｓｕｌｔｓ ［Ｊ］．Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２０００，８（２）：１７３ —１９５． ［９］Ｄｏｒｆ Ｒ Ｃ，Ｂｉｓｈｏｐ Ｒ Ｈ．Ｍｏｄｅｎｒ ｃｏｎｔｒｏｌ ｓｙｓｔｅｍｓ（８ｔｈ ｅｄｉｔｉｏｎ）［Ｍ］．Ｂｏｓｔｏｎ，ＭＡ，ＵＳＡ：Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ Ｌｏｎｇｍａｎ，１９９８．