一种基于邻域的多目标进化算法

维普资讯 http://www.cqvip.com 第２８卷第６期　２００８年６月　计算机应用　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．２８　Ｎｏ．６　Ｊｕｎｅ　２００８　文章编号：１００１—９０８１（２００８）０６—１５７０—０５　一种基于邻域的多目标进化算法　李密青，郑金华，罗　彪，伍　军，文诗华　（湘潭大学信息工程学院，湖南湘潭４１１１０５）　（１ｉｍｉｔｌ００８＠１２６．ｃｏｉｎ）　　。摘要：种群维护是多目标进化算法的重要组成部分。针对维护方法和运行效率的矛盾，提出一种基于邻域的　多目标进化算法（ＮＭＯＥＡ）。定义了一个反映个体之间邻近程度的指标——邻域包含关系，利用此关系对个体进行　分布适应度分级的赋值，并用动态方法快速地对种群进行维护。通过７个测试问题和３个方面的测试标准，结果表明　新算法在较快速地接近真实的最优面的同时，拥有良好的分布性。　关键词：多目标进化算法；多目标优化问题；种群维护；分布适应度；邻域　中图分类号：ＴＰ１８　文献标志码：Ａ　Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　０ｎ　ｎｅｉｇｈｂｏｒｈｏｏｄ　Ｕ　Ｍｉ—ｑｉｎｇ，ＺＨＥＮＧ　Ｊｉｎ—ｈｕａ，ＬＵＯ　Ｂｉａｏ，ＷＵ　Ｊｕｎ，ＷＥＮ　Ｓｈｉ—ｈｕａ　（Ｉｎｓｔｉｔ￣ｅ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉａｎｇｔａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｔａｎ　Ｈｕｎａｎ　４１１１０５，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｐｏｐｕｌａｔｉｏｎ　ｍａｉｎｔｅｎａｎｃｅ　ｉｓ　ａｎ　ｉｍｐｏｒｔｎａｔ　ｉｓｓｕｅ　ｉｎ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｉｒｔｈｍｓ．Ｆｏｒ　ｔｈｅ　ｄｅｆｉｃｉｅｎｃｙ　ｔｈａｔ　ｔｈｅ　ｍａｉｎｔｅｎａｎｃｅ　ｍｅｔｈｏｄｓ　ｏｆ　ｇｏｏｄ　ｄｉｓｔｉｒｂｕｔｉｏｎ　ｕｓｕａｌｌｙ　ｈａｖｅ　ａ　ｈｉｇｈ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ，ａ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｌａｇｏｉｒｔｈｍ　ｂａｓｅｄ　ｏｎ　ｎｅｉｇｈｂｏｒｈｏｏｄ（ｎａｍｅｄ　ＮＭＯＥＡ）ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｉｓ　ｍｅａｓｕｒｅ　ｄｅｉｆｎｅｄ　ａ　ｃｒｉｔｅｉｒｏｎ—ｎｅｉｇｈｂｏｒｈｏｏｄ　ｃｏｎｔａｉｎｉｎｇ　ｒｅｌａｔｉｏｎ，　ｗｈｉｃｈ　ｒｅｐｒｅｓｅｎｔｅｄ　ｔｈｅ　ｃｌｏｓｅ　ｄｅｇｒｅｅ　ｏｆ　ｉｎｄｉｖｉｄｕａｌｓ．Ａｎｄ　ｉｔ　Ｗａｓ　ｕｓｅｄ　ｔｏ　ａｓｓｉｇｎ　ｄｉｖｅｒｓｉｔｙ　ｆｉｔｎｅｓｓ　ｉｎ　ａ　ｄｙｎａｍｉｃ　ｍｅｔｈｏｄ　ｔｈａｔ　ｍａｉｎｔａｉｎｅｄ　ｔｈｅ　ｐｏｐｕｌａｔｉｏｎ　ｒａｐｉｄｌｙ．Ｂｙ　ｅｘａｍｉｎｉｎｇ　ｔｈｒｅｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｍｅｔｒｉｃｓ　ｏｎ　ｓｅｖｅｎ　ｔｅｓｔ　ｐｒｏｂｌｅｍｓ，ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ａｐｐｒｏａｃｈ　ｔｈｅ　ｔｒｕｅ　Ｐａｒｅｔｏ　ｆｒｏｎｔ　ｆｓａｔ，ａｎｄ　ｈａｓ　ｇｏｏｄ　ｄｉｓｔｉｒｂｕｔｉｏｎ，　Ｋｅｙ　ｗｏｒｄｓ：ｍｕｌｔｉ－・ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉ－・ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍ；ｐｏｐｕｌａｔｉｏｎ　ｍａｉｎｔｅｎａｎｃｅ；　ｄｉｖｅｒｓｉｔｙ　ｒｎａｋ；ｎｅｉｈｇｂｏｒｈｏｏｄ　０　引言　［５—６］利用快速排序和擂台赛法构造非支配集；文献［７］用　占优树来减少个体的比较次数，提出了一种快速的基于占优　进化算法（Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｉｒｔｈｍ，ＥＡ）是一类模拟生物　树的多目标进化算法。以上这些方法都是围绕怎样构造非支　自然选择与自然进化的随机搜索算法，因其适用于求解高度　配集的，算法虽然在时间上得到了较大提高，但收敛性和分布　复杂的非线形问题而得到了非常广泛的应用。在解决只有单　性的改进并不明显。　个目标的复杂系统优化问题时，进化算法的优势得到了充分　为了在拥有较快速度的同时，取得好的收敛性和分布性　展现。然而，现实世界中的优化问题通常是多属性的，一般是　结果，本文提出一种基于邻域的多目标进化算法（ＮＭＯＥＡ）。　对多个目标的同时优化，且被同时优化的多个目标之间通常　该方法首先定义了一个反映个体邻近程度的指标——邻域包　是相互冲突的，如在企业生产活动中，产品质量与生产成本是　含关系，然后利用邻域包含关系对个体进行分布适应度分级　两个相互冲突的目标。为了达到总目标的最优化，通常需要　的赋值，并且用动态方法快速地对种群进行维护，最后通过进　对相互冲突的子目标进行综合考虑，即对各个子目标进行折　行多个函数实验，测试和讨论了算法的性能。实验结果表明　中。由此，针对多目标优化问题（Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　算法具有良好的收敛性、分布性和时间效率。　Ｐｒｏｂｌｅｍ，ＭＯＰ），出现了多目标进化算法（Ｍｕｌｔｉ￣Ｏｂｊｅｃｔｉｖｅ　Ｅｖｏｌｕｔｉｏｎａｒｙ　ｌＡｇｏｒｉｔｈｍ，ＭＯＥＡ）…。　１　基本概念　近年来，进化计算界相继提出了大量有效的多目标进化　算法。最有代表性的主要有：ＮＳＧＡ－ＩＩ　２　和ＳＰＥＡ２　３　Ｊ。ＮＳＧＡ—　最小化与最大化问题可以相互转化，因此，仅以最小化多　ＩＩ有很快的运行效率，但解集的分布性并不理想；ＳＰＥＡ２能很　目标问题为研究对象。多目标问题的一般描述为：　好地维持解集的分布性，但速度较慢。　给定决策向量Ｘ＝（　，，　：，…，　），它满足下列约束：　多目标进化算法的研究目标主要是使算法种群快速收　ｇ　（　）≥０；ｉ＝１，２，…，｜｝ｉ　（１）　敛，并且广泛而均匀分布于问题的非劣最优域。其中算法的　ｈ　（Ｘ）＝０；ｉ＝１，２，…ｌ　（２）　时间效率是一个重要的因素。国内学者在这方面进行了大量　设有ｒ个优化目标，且这ｒ个优化目标是相互冲突的，优　的研究：文献［４］提出了基于排序集合快速求解算法；文献　化目标可表示为：　收稿日期：２００７—１２—２１；修回日期：２００８—０２—２０。　基金项目：国家自然科学基金资助项目（６０７７３０４７）；国家８６３计划项目　（２００１ＡＡ１１４０６０）；留学回国人员科研启动基金资助项目（教外司留［２００５］５４６号）；湖南省自科基金资助项目（０５ＪＪ３０１２５）；湖南省教育厅重点　科研资助项目（０６Ａ０７４）。　作者简介：李密青（１９８１一），男，湖南常德人，硕士研究生，主要研究方向：进化计算；　郑金华（１９６３一），男，湖南邵阳人，教授，博士生导　师，主要研究方向：进化计算、智能科学；罗彪（１９８４一），男，湖南邵阳人，硕士研究生，主要研究方向：进化计算；伍军（１９８２一），男，湖南邵　阳人，硕士研究生，主要研究方向：进化计算；文诗华（１９８１一），男，湖南衡阳人，硕士研究生，主要研究方向：进化计算。　维普资讯 http://www.cqvip.com 第６期　／’（Ｘ）＝　（Ｘ），　（Ｘ），…，　李密青等：一种基于邻域的多目标进化算法　））　１５７１　行删除，算法时间复杂度为０（ｒ　）。该方法具有动态性，每　移出一个个体，外部种群中个体的分布情况都会发生变化，这　样算法虽能很好地维持解集的分布性，但具有很高的时间复　杂度。　．　寻求Ｘ　＝（　，　，…，　），使　念：　’）在满足约束（１）　和（２）的同时达到最小。ＭＯＥＡ经常用到如下几个基本概　定义１个体的Ｐａｒｅｔｏ支配关系。设Ｐ和ｑ是进化群体　Ｐｏｐ中的任意两个不同的个体，我们称Ｐ支配ｑ，则必须满足下　列２个条件：　１）对所有的子目标，Ｐ不比ｑ差，即　（Ｐ）≤　（ｑ）（ｋ＝１，　２，…，ｒ）；　３　基于邻域的多目标进化算法　首先我们定义一个反映个体邻近程度的指标——邻域包　含关系。　定义５　个体的邻域包含关系。设Ｐ和ｑ是进化群体Ｐｏｐ　中的任意两个不同的个体，对一距离ｒ，若ｑ在以Ｐ为圆心，以ｒ　２）至少存在一个子目标，使Ｐ比ｑ好。即ｊｌ　Ｅ｛１，２，…，　ｒ｝，使ｆＡｐ）＜　（ｑ）。　其中ｒ为子目标的数量。此时称Ｐ为非支配的，ｑ为被支配　的。表示为ｐ　ｑ，其中“　”是支配关系。　定义２　Ｐａｒｅｔｏ最优解。给定一个多目标优化问题ｍｉｎ　７（　），称Ｘ　ｎ是最优解，若ＶＸ　ｎ，满足下列条件之一：　１）＾　（Ｘ）＝ｆｉ（Ｘ　））；　２）至少存在一个　Ｅ，，，＝｛１，２，…，ｒ｝，使：　（Ｘ）＞　（　）。　其中ｎ是满足式（１）和式（２）的可行解集，即：　ｎ：｛Ｘ　Ｅ　Ｒ　ｌ　ｇ　（　）≥０，ｈ。（　）＝０；（ｉ：１，２，…，　；　＝　１，２，…，１）｝　定义３　Ｐａｒｅｔｏ最优面（边界）。给定一个多目标优化问题　ａｒｉｎｙ（Ｘ）和它的最优解集｛Ｘ　｝，它的Ｐａｒｅｔｏ最优面定义为：　ＰＦ　＝｛　（　）＝　（Ｘ）　（Ｘ），…　（　））ｆ　Ｅ　｛Ｘ　｝｝　（３）　定义４　非支配集。设有解集Ｐ，Ｐ中的个体ｑ不被任何其　他个体支配，则ｑ是Ｐ中的非支配个体；ＪＰ的非支配个体构成　的子集称为Ｐ的非支配集ＮＤｓｅｔ。即ＮＤｓｅｔ＝｛ｑ　ｌ　ｑ　Ｅ　Ｐ且　ｊｐ　ＥＰ，使ｐ　ｑ｝。　２　相关工作　在进化过程中，种群中的非支配个体数可能大于外部种　群的大小，此时需要对外部种群进行维护，通常的做法是根据　非支配个体的密度信息移出部分个体。维护方法的好坏不仅　决定着最终解集的分布情况，还很大程度上影响算法的搜索　能力　。对此，学者们提出了很多行之有效的方法，如　ＮＰＧＡ　采用了适应度共享机制来对种群进行修剪，它根据　小生境数目这一参数连续地更新适应度共享函数，以便获得　非支配边界上均匀分布的结果，但当共享适应度与锦标赛选　择相结合时，算法在执行过程中可能会出现混沌行为；　ＰＥＳＡ＿ｌ。。采用了一种超网格技术对种群进行维护，它将目标　空间分成若干个ｈｙｐｅｒ—ｂｏｘ，每个个体就与某个网格相关联，　网格里的个体数目称为挤压因子，在进入归档集的过程中，挤　压因子大的个体将被清除掉；ＮＳＧＡ—ＩＩ利用个体的聚集距离　来对种群进行维护，通过计算进化群体中每个个体的聚集距　离，构造了一个偏序集，对聚集距离较小的个体进行淘汰，其　时间复杂度为０（ｒＮｌｂ　Ｎ）。但随着维数的增大，构造的这种聚　集距离很难精确地反映个体的密度信息，并且由于构造方法　的静态性，没有考虑已经移出个体对种群分布情况的影响。　算法虽然有很好的时效性，但分布结果并不理想。ＳＰＥＡ２用　剪切方法对外部种群进行维护。选择第ｋ个最近邻的个体进　为半径的区域内，则称Ｐ邻域包含ｑ，记为ｐ　，ｑ。　容易发现邻域包含关系具有以下几个性质：　性质１　关系　，具有反自反性。　性质２关系　，具有对称性。　性质３　关系　，不具备传递性。　我们依据性质１，２，３就对个体进行分布适应度赋值，为　了能精确地表示个体的分布情况，我们把个体的分布适应度　分为两级（Ｄ　Ｄ　）。具体方法如下：　算法１计算个体的分布适应度　ｆｏｒ　ｅａｃｈ　｛ｉ．Ｄ　ｕ＝Ｏ；　ｉ．Ｄ　ｋ２：０；　｝　／／个体分布适应度初始化　ｆｏｒ　ｅａｃｈ　｛ｔｅｍｐ＝ｉｎｄ［ｉ］；　／／ｉｎｄ［　］为一存储个体邻域内信息的链表　ｆｏｒ　ｅａｃｈｊ　｛ｉｆ（ｉ！＝Ｊ＆＆ｄｉｓｔａｎｃｅ（ｉ　）＜ｒ）　／／若　在ｉ的邻域内，则调整ｉ的分布适应度　｛ｉｎｓｅｒｔ（ｔｅｍｐ，』）；　ｉ．Ｄ　ｋｌ＝ｉ．Ｄ　ｋｌ＋１；　／／为整型　ｉ．Ｄ　ｍ＝ｉ．Ｄ　越＋ｄｉｓｔａｎｃｅ（ｉｊ）；　／／为浮点型　Ｉｅ　ｐ　ｔｅｍｐ一＞ｃｈｉｌｄ；　｝　　｝从算法１中容易看出，ｉ．Ｄ　。为邻域内个体数，值小表明ｉ　周围个体比较稀少；　．Ｄ　为邻域内个体与ｉ的距离之和，对于　Ｄ　。相同的个体，其Ｄ　值大表明其距离周围个体相对较　远。在图１中，对于个体Ｂ与Ｅ，最Ｄｒｙ，　。＝３，五Ｄ　＝２，Ｅ周　围个体密度要低于Ｂ周围个体密度；对于个体Ｃ与，，它们有相　同的Ｄ　ｋ。值，ｅ　Ｄ　ｋ。＝　Ｄ　ｋ２＝３，但ｃ　Ｄ　ｋ２＜　Ｄ　ｋ２，表　明在其邻域内距离，的个体要远于距离Ｃ的个体。　图１　个体分布适应值示例　算法１对空间中的非支配个体进行了分布适应度赋值，　下面我们根据个体的分布适应值对种群进行维护，其具体方　维普资讯 http://www.cqvip.com

ｌ５７２　法如下：　计算机应用　第２８卷　名的ＭＯＥＡ（ＳＰＥＡ２　ｊ，ＮＳＧＡ．ＩＩ　，ＥＰＳ—ＭＯＥＡ　Ｌｌ　）相比较。　算法２种群维护　ｗｈｉｌｅ（Ｉ　Ｑ　Ｉ＞Ｍ）　／／当非支配个体数目大于归档集时　｛　＝ｆｉｎｄｍａｘ（），Ｙ＝ｆｉｎｄｓｅｅｍａｘ（）；　’　／／分别找出Ｄ　最大，次大的个体　ｉｆ（　．Ｄ，　ｋｌ＞　ＤｍｌＩｋ１）ｄｅｌｅｔｅ（　），　＝　；　实验运行在１．７　ＧＨｚ　ＣＰＵ　２５６　ＭＢ内存Ｗｉｎｄｏｗｓ　ＸＰ环境下，　选取了７个测试函数。ＳＣＨ”　被认为是在ＭＯＰ领域具有代　表性的测试函数，ＦＯＮ¨　是一个可变决策变量维数的测试函　数，ＺＤＴ是由文献［１４］提出来的一系列测试函数，这些函数　是具有代表性的测试函数，其中ＺＤＴ１、ＺＤＴ２较易收敛，ＺＤＴ３　为非连续的，ＺＤＴ４、ＺＤＴ６较难收敛且ＺＩＹＩ＇６为非均匀分布。　／／淘汰Ｄ　ｋｌ大的个体　ｅｌｓｅｉｆ（　．ＤｍｌＩｋｌ＝　Ｄ，　ｋｌ＆＆　．Ｂｒａｎｋ２＜　Ｄ舢ｋ２）　ｄｅｌｅｔｅ（　），　＝　；　／／若Ｄ　ｕ相同，淘汰Ｄ　ｋ２小的个体　ｅｌｓｅ　ｄｅｌｅｔｅ（Ｙ），ｊ　，，；　在实验中，四种算法都采用实数编码，交叉概率０．８，变异概　率０．０１，种群规模为１００，被评价个体的数目为２００００，算法的　运行代数为评价个体的数目除以种群规模。每种算法对各个　ｔｅｍｐ＝ｉｎｄ［　］；　ｗｈｉｌｅ（ｔｅｍｐ一＞ｃｈｉｌｄ！＝ＮＵＬＬ）　／／调整ｚ邻域内其他个体的分布度适应值　测试函数运行１Ｏ次，结果取平均值。　｛（ｔｅｍｐ一＞ｉｎｄｅｘ）．Ｄｒａ｜Ｉｋｌ：（ｔｅｍｐ一＞ｉｎｄｅｘ）．Ｄ　ｌ一１　多目标优化的三个基本目标为收敛性，分布性和运行时　（ｔｅｍｐ一＞ｉｎｄｅｘ）．Ｄｒａ　：（ｔｅｍｐ一＞ｉｎｄｅｘ）．Ｄ肿ｋ２一　间。在多目标优化中解集的评价方法也是一个重要而复杂的　ｄｉｓｔａｎｃｅ（　．ｔｅｍｐ一＞ｉｎｄｅｘ）　问题¨　，研究者们提出了很多有效的方法¨　－１６，１８－１９］。在这　ｔｅｍｐ　ｔｅｍｐ一＞ｃｈｉｌｄ：　里采用Ｇｅｎｅｒａｔｉｏｎａｌ　Ｄｉｓｄａｎｃｅ（ＧＤ）　来估计算法的最终边界　Ｑ　Ｉ＝Ｉ　Ｑ　Ｉ一１：　与全局非劣最优区域的趋近程度，计算如下：　｝　从算法２中可以看出，维护方法总是淘汰Ｄ　最大的个　体，若Ｄ　。相同，则淘汰Ｄ　小的个体。对于图１中的情况，　ＧＤ　√　／ｎ　（４）　ｎ是解集中个体的数目，ｄ　是每个个体到全局非劣最优解的　若归档集大小为５，种群维护过程如图２所示，个体Ｃ与Ｆ有　最小欧几里得距离。ＧＤ的值越小就说明解集越靠近全局非劣　相同的Ｄ　…但ｅ　Ｄ　小于　Ｄ　，所以淘汰Ｃ，并调整日，　Ｄ的分布适应值，得到图２（ａ）的情况，Ｂ、Ｄ的Ｄ　。降为２，此　最优区域，如果ＧＤ＝０就说明算法的解都在全局非劣最优区　时整个群体中Ｆ具有最大的Ｄ　Ｆ被淘汰，得到图２（ｂ）的　域上，这是最理想的情况。分布性评价采用Ｓｃｈｏｔｔ提出的方　情况。　法”　，其函数定义如下：　算法２采用动态的方法维护种群，虽然增加一定的时问　厂　—＝—　＿　开销，但种群分布性得到了较好的保持。算法１的时间复杂　ＳＰ＝√　Ｖ‘　‘●　１　（ｄ—ｄ１）　（５）　度为０（　ｆｖ２），算法２在最坏情况下时间复杂度为０（ｒ』ｖ２），所　ｄ。＝ｍｉｎ（Ｉｆ　（　）一　（　）Ｉ＋　（　）一　（　）Ｉ）（ｉ，Ｊ＝１，　以种群维护的总时问复杂度为０（ｒＮ２），逊于ＮＳＧＡ—ＩＩ，好于　２，…，ｎ），ｄ是所有ｄ　的平均值。当算法获得的非劣解完全均　ＳＰＥＡ２。下面我们给出整个算法的具体流程。　匀地分布在目标空问时，ＳＰ：０。　表１显示了四种算法在７个测试函数上的收敛度，分布　度，运行时问结果。在每个评价指标中，第一列为均值，第二　列为标准差，加粗数据为最优值。从表１中可以发现，在收敛　性方面，对较易收敛的测试函数ＳＣＨ，ＦＯＮ，ＺＤＴ１和ＺＤＴ２四　种算法性能相差不大，在ＳＣＨ，ＦＯＮ上ＮＭＯＥＡ要略优于其他　三种算法，在ＺＤＴ１，ＺＤＴ２上ＥＰＳ．ＭＯＥＡ，ＳＰＥＡ２分别拥有最　（ａ）淘汰Ｃ　～　（ｂ）淘汰Ｆ　图２种群维护过程　好的收敛度。对非连续或较难收敛的测试函数ＺＤＴ３，ＺＤＴ４　ＮＭＯＥＡ借鉴ＮＳＧＡ．和ＺＤＴ６，ＮＭＯＥＡ拥有较稳定的收敛度，特别对于其他两种算　．ＩＩ采用了分层构造非支配集的方　法　。　法很难收敛的测试函数ＺＤＴ４，ＮＭＯＥＡ能收敛到真实的最　１）算法参数设定。内部种群Ｒ规模为Ⅳ，外部种群Ｑ的最　优面。　．　大规模肘，中间种群Ｐ的规模　＋Ⅳ，交叉概率Ｐ　，变异概率　从表１中可以发现，在分布性方面，ＮＭＯＥＡ和ＳＰＥＡ２比　Ｐ　，算法搜索的最大代数　ｎ一，令进化代数ｇｅｎ＝１。　较接近，好于其他两种算法，ＮＭＯＥＡ在ＳＣＨ，ＺＤＴ３，ＺＤＴ４上　２）随机产生一个初始种群Ｒ，同时初始化外部种群Ｑ，并　有最好的分布性，ＳＰＥＡ２在ＦＯＮ，ＺＤＴ１，ＺＤＴ２，ＺＤＴ６上有最好　使之为空。　的分布性，但ＳＰＥＡ２对非连续函数ＺＤＴ３很难收敛真实的最　３）合并　、Ｑ　到Ｐ　，将Ｐ　中的个体按支配的关系　优面，这是由其基于密度的修剪方法决定的。图３～图５为　逐层加入到Ｑ　＋。中。当加入第ｉ层非支配集Ｓ后的总个体数　四种算法在部分测试函数上最终边界分布。　大于　时，按上面给出的方法对外部种群进行维护。若ｇｅｎ＋　１＝ｇｅｎ　，将Ｑ　＋。中的个体作为返回结果，程序结束。　四种算法在运行时间方面，ＥＰＳ—ＭＯＥＡ具有最快的速度，　４）对Ｑ　＋。执行锦标赛选择操作，对选中的个体执行交　ＮＳＧＡ—ＩＩ、ＮＭＯＥＡ次之，ＳＰＥＡ２最差。　叉和变异操作。并将结果保存到　＋，中，ｇｅｎ＝ｇｅｎ＋１，转　通过分析和比较发现：在趋近最优前沿方面和运行效率　３）。　方面，四种算法性能相差不大，ＮＭＯＥＡ的稳定性要略好于其　４实验与分析　他三种算法；在保持解集的分布性方面，ＮＭＯＥＡ与ＳＰＥＡ２相　当，优于其他两种算法；在运行时间方面ＥＰＳ．ＭＯＥＡ最快，　为了检验所提出ＮＭＯＥＡ的有效性，将其与另外３个著　ＮＳＧＡ—Ｉ１次之，ＨＯＭＥＡ要好于ＳＰＥＡ２。　维普资讯 http://www.cqvip.com 第６期　李密青等：一种基于邻域的多目标进化算法　１５７３　表１算法性能比较　１－０　０．８　０．６　０．４　０．２　０．０　０．０　０．２　０．４　０．６　０．８　１．０　０．０　０．２　０．４　０．６　０．８　１．０　０．０　０．２　０．４　０．６　０．８　１．０　０．０　０．２　０．４　０．６　０．８　１．０　｛　｛　（ａ）ＮＳＧＡ－Ｉ１　（ｂ）ＳＰＥＡ２　（ｃ）ＥＰＳ—ＭＯＥＡ　（ｄ）ＮＭＯＥＡ　图３　４种算法在ＦＯＮ上的最终边界　１．２　０．６　０．０　—０．６　０．０　０．２　０．４　０．６　０．８　１．０　０．０　０．２　０．４　０．６　０．８　１．０　０．０　０．２　０．４　０．６　０．８　１．０　０．０　０．２　０．４　０．６　０．８　１．０　｛　｛　ｆａ）ＮＳＧＡ－Ｉ１　（ｂ）ＳＰＥＡ２　（ｃ）ＥＰＳ—ＭＯＥＡ　（ｄ）ＮＭＯＥＡ　图４　４种算法在ＺＤＴ３上的最终边界　１．４　１．２　１．Ｏ　０．８　０．６　０．４　０．２　０．０　图５　４种算法在ＺＤＴ４上的最终边界　维普资讯 http://www.cqvip.com １５７４　计算机应用　第２８卷　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｐａｒａｌｌｅｌ　Ｐｒｏｂｌｅｍ　Ｓｏｌｖｉｎｇ　ｆｒｏｍ　Ｎａｔｕｒｅ　ＶＩ　Ｃｏｎｆｅｒ－　５　结语　ｅｎｃｅ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｄａｇ，２０００：８３９—８４８．　种群维护是多目标进化算法的重要组成部分，维护方法　【ｌ１】ＤＥＢ　Ｋ，ＭＯＨＡＮ　Ｍ，ＭＩＳＨＲＡ　Ｓ．Ａ　ｆａｓｔ　ｍｕｌｉｔ—ｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎ・　的好坏决定着最终解集的分布状况。针对维护方法和运行效　ａｒｙ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｉｆｎｄｉｎｇ　ｗｅｌｌ－ｓｐｒｅａｄ　ｐａｒｅｔｏ－ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎｓ，Ｋａｒｌ－　率的矛盾，本文设计了一种基于邻域的种群维护方法　ＧＡＬ　Ｒｅｐｏｒｔ　Ｎｏ．２￣３００２【Ｒ】．２００３．　ＮＭＯＥＡ。定义了一个反映个体邻近程度的指标——邻域包　【１２】　Ｖａｎ　ＶＥＬＤＨＵＩＺＥＮ　Ｄ　Ａ，ＬＡＭＯＮＴ　Ｇ　Ｂ．Ｍｕｈｉｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎ－　含关系，利用邻域包含关系对个体进行分布适应度分级的赋　ａｒｙ　ａｌ￣ｒｉｈｔｍ　ｔｅｓｔ　ｓｕｉｔｅｓ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆｔｈｅ　１９９９　ＡＣＭ　Ｓｙｍ－　ｐｏｓｉｕｍ　ｏｎ　Ａｐｐｌｉｅｄ　Ｃｏｍｐｕｔｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，１９９９：３５１　值，并且用动态方法快速地对种群进行维护。将其与　—３５７．　ＮＳＧＡ．ＩＩ，ＳＰＥＡ２和ＥＰＳ．ＭＯＥＡ进行比较实验，结果表明　【１３】　ＦＯＮＳＥＣＡ　Ｃ　Ｍ，ＦＬＥＭＩＮＧ　Ｐ　Ｊ．Ｍｕｌｔｉｏｂｊｃｅｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｏｇｒｉｔｈｍｓ　ＮＭＯＥＡ具有良好的搜索性能。　ｍａｄｅ　ｅａｓｙ：Ｓｅｌｅｃｔｉｏｎ，ｓｈａｒｉｎｇ，ａｎｄ　ｍａｔｉｎｇ　ｒｅｓｔｒｉｃｔｉｏｎ【Ｃ】／／Ｐｒｏ－　参考文献：　ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｆｉｒｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｏｇｒｉｔｈｍｓ　【１】郑金华．多目标进化算法及其应用【Ｍ】．北京：科学出版社，　ｉｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｓｙｓｔｅｍｓ：Ｉｎｎｏｖａｔｉｏｎｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．Ｗａｓｈｉｎｇ－　２ｏ０７．　ｔｏｎ：ＩＥＥＥ　Ｐｒｅｓｓ．１９９５：４２—５２．　【２】ＤＥＢ　Ｋ，ＰＲＡＴＡＰ　Ａ，ＡＧＡＲＷＡＬ　Ｓ，ｅｔ　ａ１．Ａ　ｆａｓｔ　ａｎｄ　ｅｌｉｔｉｓｔ　ｍｕｌ・　【１４】ＤＥＢ　Ｋ．Ｍｕｌｉｔ－ｏｂｊｅｃｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｈｔｍｓ：Ｐｒｏｂｌｅｍ　ｄｉｆｉｆｃｕｌｉｔｅｓ　ｔｉｏｂｊｅｃｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ：ＮＳＧＡ－ＩＩ【Ｊ】．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　ｎａｄ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｏｆ　ｔｅｓｔ　ｐｒｏｂｌｅｍｓ【Ｊ】．Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（２）：１８２—１９７．　１９９９，７（３）：２０５—２３０．　【３】　ＺＩＴＺＬＥＲ　Ｅ，ＬＡＵＭＡＮＮＳ　Ｍ，ＴＨＩＥＬＥ　Ｌ．ＳＰＥＡ２：Ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　【１５】　Ｖａｎ　ＶＥＬＤＨＵＩＺＥＮ　Ｄ　Ａ，ＬＡＭ０ＮＴ　Ｇ　Ｂ．Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｅｖｏｌｕｔｉｏｎ－　ｓｔｒｅｎｇｔｈ　Ｐａｒｅｔｏ　ｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｈｔｍ，ＴＩＫ—Ｒｅｐｏｒｔ１０３【Ｒ】．２００１．　【４】　曾三友，李晖，丁立新，等．基于排序的非劣集合快速求解算　ａｒｙ　ａｌｏｇｒｉｈｔｍ　ｔｅｓｔ　ｓｕｉｔｅｓ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆｔｈｅ　１９９９　ＡＣＭ　Ｓｙｍ－　ｏｐｓｉｕｍ　ｏｎ　Ａｐｐｌｉｅｄ　Ｃｏｍｐｕｔｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，１９９９：３５１　法【Ｊ】．计算机研究与发展，２００４，４１（９）：１５６５—１５７１．　—３５７．　【５】　郑金华，史忠植，谢勇．基于聚类的快速多目标遗传算法【Ｊ】．计　算机研究与发展，２００４，４１（７）：１０８１—１０８７．　【１６】ＤＥＢ　Ｋ．Ｍｕｌｉｔ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉａｚｔｉｏｎ．ｕｓｉｎｇ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　【６】　郑金华，蒋浩，邝达，等．擂台赛法则构造多目标Ｐａｒｅｔｏ最优解　【Ｍ】．Ｃｈｉｅｈｅｓｔｅｒ，Ｅｎｇｌｎａｄ：Ｊｏｈｎ　Ｗｉｌｅｙ＆Ｓｏｎｓ，２００１．　集的方法研究【Ｊ】．软件学报，２００７，１８（６）：１２８７—１２９７．　【１７】ＺＩＴＺＬＥＲ　Ｅ，ＬＡＵＭＡＮＮＳ　Ｍ，ＴＨＩＥＬＥ　Ｌ，ｅｔ　ａ１．Ｗｈｙ　ｑｕａｌｉｔｙ　ａｓ・　【７】　石川，李清勇，史忠植．一种快速的基于占优树的多目标进化算　ｓｅｓｓｍｅｎｔ　ｏｆ　ｍｕｈｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚｅｒｓ　ｉｓ　ｄｉｉｆｅｕｈ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　法【Ｊ】．软件学报，２００７，１８（３）：５０５—５１６．　ｏｆ　ｔｈｅ　Ｇｅｎｅｔｉｃ　ａｎｄ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ　Ｃｏｎｆｅｒｅｎｃｅ　【８】ＬＡＵＭＡＮＮＳ　Ｍ，ＴＨＩＥＬＥ　Ｌ，ＤＥＢ　Ｋ，ｅｔ　ａ１．Ｃｏｍｂｉｎｉｎｇ　ｃｏｎｖｅｒｇｅｎｃｅ　（ＧＥＣＣＯ＇２００２）．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，Ｃａｌｉｏｆｍｉａ：Ｍｏｒｇａｎ　Ｋａｎｆｍａｎｎ　ｎａｄ　ｄｉｖｅｒｓｉｔｙ　ｉｎ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ【Ｊ】．Ｅｖｏｌｕ－　Ｐｕｂｌｉｓｈｅｒｓ．２００２：６６６—６７３．　ｔｉｏｎａｒｙ　ｃｏｍｐｕｔａｔｉｏｎ，２００２，１０（３）：２６３—２８２．　【１８】　ＦＡＲＨＡＮＧ－ＭＥＨＲ　Ａ，ＡＺＡＲＭ　Ｓ．Ａｎ　ｉｆｎｏｒｍａｔｉｏｎ・ｔｈｅｏｒｅｔｉｃ　ｅｎｔｏｒ－　【９】ＨＯＲＮ　Ｊ，ＮＡＦＰＬＩＯＴＩＳ　Ｎ，ＧＯＬＤＢＥＲＧ　Ｄ　Ｅ．Ａ　ｎｉｃｈｅｄ　ｐａｒｅｔｏ　ｇｅ－　ＰＹ　ｍｅｔｒｉｃ　ｆｏｒ　ａｓｓｅｓｓｉｎｇ　ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉａｚｔｉｏｎ　ｓｏｌｕｔｉｏｎ　ｓｅｔ　ｎｅｔｉｃ　Ｍｇｏｒｉｈｔｍ　ｆｏｒ　ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉａｚｔｉｏｎ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｑｕａｌｉｔｙ【Ｊ】．Ｊｏｕｒｎａｌ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　Ｄｅｓｉｇｎ，２００３，１２５（４）：６５５—　ｈｔｅ　Ｆｉｒｓｔ　ＩＥＥＥ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，ＩＥＥＥ　６６３．　Ｗｏｒｌｄ　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ．Ｐｉｓｃａｔａｗａｙ，Ｎｅｗ　【１９】　ＺＨＥＮＧ　ＪＩＮ－ＨＵＡ，ＬＩ　ＭＩ－ＱＩＮＧ．Ａ　ｄｉｖｅｒｓｉｔｙ　ｍｅｔｒｉｃ　ｆｏｒ　ＭＯＥＡｓ　Ｊｅｒｓｅｙ：ＩＥＥＥ　Ｓｅｒｖｉｃｅ　Ｃｅｎｔｅｒ。１９９４，１：８２—８７．　【Ｃ】／／７ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｏｐｔｉｉｍｚａｔｉｏｎ：Ｔｅｃｈｎｉｑｕｅｓ　【１０】ＣＯＲＮＥＤＷ，ＫＮＯＷＬＥＳ　ＪＤ，ＯＡＴＥＳ　Ｍ　Ｊ．Ｔｈｅ　ｐａｒｅｔｏ　ｅｎｖｅｌｏｐｅ・　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ（ＩＣＯＴＡ７）．ＫｏｂｅＪａｐａｎ：Ｕｎｉｖｅｒｓａｌ　Ａｃａｄｅｍｙ　ｂａｓｅｄ　ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｈｔｍ　ｆｏｒ　ｍｕｌｔｉｏｂｊｅｅｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ【Ｃ】／／　Ｐｒｅｓｓ．２００７：４５１—４５２．　（上接第１５６９页）　表１　ＬＳＩ。ＰＬＳＩ。ＬＰＩ和ＦＬＰＩ的计算时间ｓ　参考文献：　［１】ＸＵ　Ｗ，ＬＩＵ　Ｘ，ＧＯＮＧ　Ｙ．Ｄｏｃｕｍｅｎｔ　ｃｌｕｓｔｅｒｉｎｇ　ｂａｓｅｄ　ｏｎ　ｎｏｎｎｅｇａ－　ｔｉｖｅ　ｍａｔｉｒｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　２００３　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　ｉｎ　Ｉｆｎｏｒｍａｔｉｏｎ　Ｒｅｔｒｉｅｖａｌ　（Ｓ１ＧＩＲ＇０３）．２００３：２６７—２７３．　【２】ＨＯＦＭＡＮＮ　Ｔ．Ｐｒｏｂａｂｉｌｉｓｔｉｅ　ｌａｔｅｎｔ　ｓｅｍａｎｔｉｃ　ｉｎｄｅｘｉｎｇ【Ｃ】／／Ｐｒｏ－　ｅｅｅｄｉｎｇｓ　ｏｆ　１９９９　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｒｅｓｅａｒｃｈ　ｎａｄ　Ｄｅｖｅｌｏｐ－　ｍｅｎｔ　ｉｎ　Ｉｆｎｏｒｍａｔｉｏｎ　Ｒｅｔｒｉｅｖａｌ（ＳＩＧＩＲ９９）．１９９９：５０—５７．　【３】　ＣＨＵＮＧ　Ｆ　Ｒ　Ｋ．Ｓｐｅｃｔｒａｌ　Ｇｒａｐｈ　Ｔｈｅｏｒｙ，ｖｏｌｕｍｅ　９２　ｏｆ　Ｒｅｇｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ｓｅｒｉｅｓ　ｉｎ　Ｍａｔｈｅｍａｔｉｃｓ．ＡＭＳ，１９９７．　注：｝表示由于内存ＬＰＩ不适用　【４】ＧＯＬＵＢ　Ｇ　Ｈ，ＬＯＡＮ　Ｃ　Ｆ　Ｖ．Ｍａｔｉｒｘ　ｃｏｍｐｕｔａｔｉｏｎｓ【Ｍ】．３ｒｄ　ｅｄ．　４　结语　Ｊｏｈｎｓ　Ｈｏｐｋｉｎｓ　Ｕｎｉｖｅｒｓｉｔｙ　Ｐｒｅｓｓ，１９９６．　【５】ＨＡＳＴＩＥ　Ｔ，ＴＩＢＳＨＩＲＡＮＩ　Ｒ，ＦＲＩＥＤＭＡＮ　Ｊ．Ｔｈｅ　ｅｌｅｍｅｎｔｓ　ｆｏ　ｓｔａｔｉｓ．　本文提出了一种基于ＬＰＩ的优化的局部保留索引算法　ｔｉｃａｌ　ｌｅａｒｎｉｎｇ：Ｄａｔａ　ｍｉｎｉｎｇ，ｉｆｎｅｒｅｎｃｅ，ａｎｄ　ｐｒｅｄｉｃｔｉｏｎ【Ｍ】．Ｎｅｗ　ＦＬＰＩ，其显著减少了ＬＰＩ的计算复杂性。理论分析显示，当　Ｙｏｒｋ：Ｓｐｒｉｎｇｅｒ・Ｖｅｒｌａｇ，２００１．　减小到０时，ＦＬＰＩ能给出和ＬＰＩ相同的解。对监督学习，当训　【６】ＰＥＮＲＯＳＥ　Ｒ．Ａ　ｇｅｎｅｒａｌｉｚｅｄ　ｉｎｖｅｒｓｅ　ｆｏｒ　ｍａｔｒｉｃｅｓ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　练集小时，通常倾向于选择一个更平滑的基函数，带有　（＞　ｏｆ　ｔｈｅ　Ｃａｍｂｒｉｄｇｅ　Ｐｈｉｌｏｓｏｐｈｉｃａｌ　Ｓｏｃｉｅｔｙ．１９５５，５１：４０６—４１３．　０）的ＦＬＰＩ能获得比ＬＰＩ更优的性能。然而，如何自动评价　［７】　ＣＨＡＮＧ　Ｃ－Ｃ，ＬＩＮ　Ｃ　Ｊ．ＬＩＢＳＶＭ：Ａ　ｌｉｂｒａｒｙ　ｆｏｒ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａ・　一个最优的　将是今后进一步研究的关键问题。　ｃｈｉｎｅｓ【ＥＢ／ＯＬ】．ｈｔｔｐ：／／ｗｗｗ．ｃｓｉｅ．ｎｔｕ．ｅｄｕ．ｔｗ／一ｃｊｌｉｎ／ｌｉｂｓｖｍ．