基于空间划分树的多目标粒子群优化算法

第４９卷第４期　吉林大学学报（理学版）　Ｖｏ１．４９　Ｎｏ．４　２０１１年７月　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｊｕｌｙ　２０１１　基于空间划分树的多目标粒子群优化算法　刘华蓥　，王静　，许少华　，孙毅　（１．东北石油大学计算机与信息技术学院，黑龙江大庆１６３３１８；２．吉林大学数学学院，长春１３００１２）　摘要：提出一种基于空间划分树的多目标粒子群优化算法，该算法采用网格拥挤距离与网格　密度相结合的策略选取全局极值，能加速算法收敛，保持种群多样性，在提高全局极值选取　准确度的同时使最终解保持了较好的分布性．　关键词：多目标优化；粒子群算法；Ｍ维空间划分；空间划分树　中图分类号：ＴＰ３０１．６　文献标志码：Ａ　文章编号：１６７１－５４８９（２０１１）０４－０６９６－０７　Ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｓｐａｔｉａｌ　Ｐａｒｔｉｔｉｏｎ　Ｔｒｅｅ　ＬＩＵ　Ｈｕａ．ｙｉｎｇ　，ＷＡＮＧ　Ｊｉｎｇ　，ＸＵ　Ｓｈａｏ—ｈｕａ　，ＳＵＮ　Ｙｉ　（１．Ｃｏｌｌｅｇｅ　ｏｆＣｏｍｐｕｗｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎｏｒｔｈｅａｓｔ　Ｐｅｔｒｏｌｅｕｍ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ　１６３３１８，　Ｈｅｉｌｏｎｇｆｉａｎｇ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ；２．Ｃｏｌｌｅｇｅ　ｏｆＭａｔｈｅｍａｔｉｃｓ，Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ　１３００１２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｓｐａｔｉａｌ　ｐａｒｔｉｔｉｏｎ　ｔｒｅｅ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ．　Ｔｈｅ　ｓｔｒａｔｅｇｙ　ｏｆ　ｕｓｉｎｇ　ｃｒｏｗｄｉｎｇ　ｄｉｓｔａｎｃｅ　ａｎｄ　ｇｒｉｄ　ｄｅｎｓｉｔｙ　ｔｏ　ｓｅｌｅｃｔ　ｇｌｏｂａｌ　ｂｅｓｔ　ｉｓ　ａｂｌｅ　ｔｏ　ｓｐｅｅｄ　ｕｐ　ｃｏｎｖｅｒｇｅｎｃｅ，　ａｎｄ　ｍａｉｎｔａｉｎｓ　ｔｈｅ　ｐｏｐｕｌａｔｉｏｎ　ｄｉｖｅｒｓｉｔｙ．Ｔｈｉｓ　ｓｔｒａｔｅｇｙ　ｃａｎ　ｉｍｐｒｏｖｅ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｓｅｌｅｃｔｉｎｇ　ｇｌｏｂａｌ　ｂｅｓｔ　ａｎｄ　ｋｅｅｐｓ　ｔｈｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｓｏｌｕｔｉｏｎｓ　ｅｆｆｅｃｔｉｖｅｌｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｍｕｈｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ａｌｇｏｒｉｔｈｍ；Ｍ—ｄｉｍｅｎｓｉｏｎ　ｓｐａｔｉａｌ　ｐａｒｔｉｔｉｏｎ；ｓｐａｔｉａｌ　ｐａｒｔｉｔｉｏｎ　ｔｒｅｅ　粒子群优化算法（ＰＳＯ）　以其易于实现、参数设置较少等优点，广泛应用于多目标优化　。　和其　他优化问题　刮中．多目标粒子群优化算法（ＭＯＰＳＯ）主要分为聚集函数法、基于目标函数排序法、子　群法、基于Ｐａｒｅｔｏ支配法等，目前研究者主要集中于基于Ｐａｒｅｔｏ支配的多目标粒子群优化算法　．　自从Ｃｏｅｌｌｏ等　首次提出用一个外部集保存每次迭代得到的非支配解后，大多数多目标粒子群优　化算法都采用了外部存档策略．张利彪等　的算法采用新的全局极值和个体极值选取方式，提高了算　法的有效性；孙小强等　采用聚类算法裁剪非支配解，提高了解的分布性．但这些算法在收敛性和分　布性方面，特别是解决高维多目标问题上仍需做进一步改进．在多目标条件下，可能存在很多彼此不　受支配的全局最优解，个体的密度信息是选取全局最优解的主要因素之一．典型的基于密度方法有非　劣分层遗传算法（ＮＳＧＡ２）　１０］和Ｋ一近邻密度估值法（ＳＰＥＡ２）¨　，这两种方法能对个体密度进行准确地　估计，但其计算复杂度偏高．ＣＭＯＰＳＯ算法　和自适应网格的多目标粒子群算法（ＡＧＡＭＯＰＳＯ）¨　使　用Ｐａｒｅｔｏ存档进化策略（ＰＡＥＳ）　１３］中自适应网格法维护外部集（Ａｒｃｈｉｖｅ，简称Ａｒｃ），用网格中的粒子　数作为网格密度定义网格适应度值，其网格密度计算性能较好，但其估值还存在一定误差．　收稿日期：２０１０—１１．２２．　作者简介：刘华蓥（１９６９一），女，汉族，硕士，教授，从事群体智能优化算法的研究，Ｅ－ｍａｉｌ：ｄｑｐｉｌｈｙ＠１６３．ＣＯＩＩ１．　基金项目：国家自然科学基金（批准号：６０４７３０５１）、中国石油科技创新基金（批准号：２０１０Ｄ－５００６－０３０２）、黑龙江省自然科学基金　（批准号：ＺＡ２００６一ｌ１）和黑龙江省科技攻关项目（批准号：ＧＺ０７Ａ１０３）．　第４期　刘华蓥，等：基于空间划分树的多目标粒子群优化算法　本文提出一种基于空间划分树的多目标粒子群优化算法（ＳＰＴＭＯＰＳＯ），用网格把目标空间划分为　多个体积相等的单元格，用空间划分树建立非空单元格的索引，采用拥挤距离和网格密度相结合的策　略选取全局极值，进一步提高了解集的分布性．　１　多目标优化问题及粒子群优化算法　多目标优化问题可以表示如下：　ｍｉｎ　Ｙ＝　Ｘ）＝（　（Ｘ），　（　），…，ｆＭ（Ｘ）），　ｓ．ｔ．ｇ　（Ｘ）≤０（ｉ＝１，２，…，Ｐ），　其中：决策向量Ｘ∈Ｒ　；目标向量Ｙ∈　；ｆ／（Ｘ）（ｉ＝１，２，…，　）是目标函数；ｇ　（Ｘ）≤０（ｉ＝１，２，…，Ｐ）　是约束条件．　大多数情况下各目标函数之间是相互冲突的，某目标的改善可能引起其他目标性能的降低，同时　使多个目标均达到最优很难实现，只能在各目标之间进行协调权衡和折中处理，使所有目标函数尽可　能达到最优．不同于单目标优化，多目标优化中使用Ｐａｒｅｔｏ支配　评价最优解，相关概念如下：　定义１若　（Ｘ　）　（Ｘ）（ｉ＝１，２，…，　），且　ｋ∈｛１，２，…，　｝，使得　（Ｘ　）＜　（Ｘ），则称解　Ｘ　Ｐａｒｅｔｏ支配Ｘ，记作Ｘ　＞　．　定义２若　］Ｘ：Ｘ＞　，则称解Ｘ　是Ｐａｒｅｔｏ最优解或非支配解．　定义３所有Ｐａｒｅｔｏ最优解的集合Ｐ　＝｛Ｘ　１］］Ｘ＞　｝称为Ｐａｒｅｔｏ最优解集或非支配解集．　定义４所有Ｐａｒｅｔｏ最优解对应的目标函数值所形成的区域　Ｐ，＝｛　Ｘ）＝（　（Ｘ），　（Ｘ），…，ｆＭ（Ｘ））ｌ　Ｘ∈Ｐ　｝　称为Ｐａｒｅｔｏ最优前端．　标准粒子群优化算法使用一群粒子表示特定问题的潜在解．给定一个ｄ维搜索空问，第ｉ个粒子　在ｔ时刻的位置为Ｘｉ（ｔ），速度为ｌ，　（ｔ），它经历过的最好位置记为ｐｂｅｓｔ　，整个粒子群经历过的最好位　置记为ｇｂｅｓｔ．ＰＳＯ算法通过不断更新粒子速度与位置使粒子向最优解飞行．第ｉ个粒子的速度与位置　更新公式如下：　（ｔ＋１）＝ＷＰ　（ｔ）＋ｃ１ｒ１（ｐｂｅｓｔ　一Ｘ　（ｔ））＋ｃ２ｒ２（ｇｂｅｓｔ—Ｘ　（ｔ）），　（１）　Ｘ　（ｔ＋１）＝Ｘ　（ｔ）＋ｌ，　（ｔ＋１），　（２）　其中：Ｗ为惯性权重；Ｃ　和Ｃ　为常数，称为学习因子；ｒ　和ｒ２是［０，１］上的随机数．式（１）中的　Ｃ１ｒ　（ｐｂｅｓｔｉ—Ｘｉ（ｔ））为认知部分，ｃ：ｒ：（ｇｂｅｓｔ—Ｘ　（ｔ））为社会部分，认知部分和粒子的个体经验相关，社　会部分则表示粒子间的交互．　２基于空间划分树的多目标粒子群优化算法　外部集维护和全局最优位置的选取是多目标粒子群优化算法的两个重要步骤．维护外部集的主要　目的是为群体的演化提供多样化的全局最优位置，而为每个粒子选择适当的全局最优位置能保持或进　一步增加外部集中解的多样性，两者相互配合，使算法获得更多均匀分布在目标空间上的非支配解，　逼近Ｐａｒｅｔｏ最优前端．本文使用空间划分树¨　对目标空间进行划分．　２．１外部集的空间划分树索引　给定　维目标空间Ｓ＝Ｄ　×Ｄ　×…Ｘ　ＤＭ，其中Ｄ　为５中第ｉ维的数据域．　定义５将外部集所对应的　维目标空间ｓ的每一维平均分为ｋ个相等的间隔段，则ｓ被划分为　ｋ　个互不相交的超矩形单元，它们覆盖整个　维目标空间ｓ．每个单元ｃ的空间位置表示为　（Ｃ　，ｃ　，…，ｃ肘），其中ｌ≤ｃ　≤后，对应于第ｉ维的第ｃ　个左闭右开的间隔段．这ｋ　个单元在划分目标空　问．ｓ的同时也划分了外部集，称为外部集的Ｍ维空间划分．　图１为一个外部集对应的２维空间划分结果．每维划分为５个间隔段，编号为１～５，外部集空间　被划分为２５个子空间．其中Ｃ（１，４），Ｃ（１，５），Ｃ（２，３），Ｃ（２，４），ｃ（３，２），Ｃ（３，３），Ｃ（５，１）为非空单元．　吉林大学学报（理学版）　第４９卷　在对外部集进行划分后，需要为其建立高效索引，以便对其进行有效管理本文采用空间划分树索引　外部集的　维空间划分．由于　维空间划分的规模与　为指数增长关系，为了以最小的代价存储有　效信息，空间划分树仅索引非空单元．　定义６　外部集在　维空间划分下的空间划分树（ｓｐａｔｉａｌ　ｐａｒｔｉｔｉｏｎ　ｔｒｅｅ，简称ＳＩＴ）结构定义如下：　１）它有一个根节点，共有　＋１层；　２）ＳＰＴ的第ｉ层对应外部集的第ｉ维（ｉ＝１，２，…，　），第　＋１层存储所有非空单元中的粒子数；　３）除了第Ｍ＋ｌ层，第ｉ层（非叶节点层）包含形如（ｄｉｍ，ｎｅｘｔ）的节点，其中ｄｉｍ表示该单元在第ｉ　维上的间隔号，ｎｅｘｔ为指向下一层节点的指针，所指向节点包含与本单元对应的下一维的所有相异非　空单元；　４）第　层节点指向叶节点：叶节点形如（ｎｕｎ，ｓｏｌｕｔｉｏｎｓ），其中ｎｕｎ为叶节点中包含的非支配解　个数，ｓｏｌｕｔｉｏｎｓ为叶节点中保存的非支配解集；　５）从根节点到叶节点的一条路径对应一个非空单元．　图２为对图１中外部集的２维空间划分结果进行索引建立的ＳＰＴ，该ＳＰＴ共３层，第１层有４个节　点，分别表示非空单元在　维的间隔号．例如根节点中的节点１指向第２层节点４和节点５，说明与　维第１个间隔号对应的非空单元在，２维的间隔段编号分别为４和５．叶节点存储从根节点到该叶节点　经过的路径所对应非空单元中的非支配解数目及非支配解．如图２中第３层最后一个节点表示非空单　元ｃ（５，１）中有２个非支配解＿，和ｋ．　１　２　３　４　５　图１外部集对应的２维空间划分示意图　Ｆｉｇ．１　２－Ｄｉｍｅｎｓｉｏｎ　ｓｐａｔｉａｌ　ｐａｒｔｉｔｉｏｎ　ｏｆ　ａｒｃｈｉｖｅ　ｓｅｔ　图２空间划分树　Ｆｉｇ．２　Ｓｐａｔｉａｌ　ｐａｒｔｉｔｉｏｎ　ｔｒｅｅ　２．２非支配解的ＳＰＴ存储　非支配解的存储过程即建立ＳＰＴ的过程，也即把非支配解插入ＳＰＴ的过程．例如，把　维目标空　间每维划分为ｋ个相等的间隔段，非支配解Ｘ　的插入过程即依次由Ｘ　所在网格各维间隔段号　（ｃ。，ｃ：，…，ｃ　）查找其存储网格的过程．其中　：ｒ　］（ｉ－ｌ，２，…，　），ｍａｘ（／＝）和　ｍｉｎ（ｆ￣）分别为目标函数．　的最大值和最小值．　２．３全局极值的选取　直接采用ＮＳＧＡ２中方法计算拥挤距离的计算代价太高．采用基于自适应网格的ＭＯＰＳＯ方法直接　根据网格密度决定全局极值的选取，可降低计算代价，但该方法未考虑相邻网格对网格密度的影响．　如图１所示，若只考虑单个网格密度会得出Ｄｅｎ（Ｃ（３，３））：Ｄｅｎ（ｃ（３，２））的结论，但由于与ｃ（３，３）　相邻的ｃ（２，３）的网格密度较高，所以事实上ｈ的密度高于ｉ的密度，即可直观得出Ｄｅｎ（ｃ（３，２））＜　Ｄｅｎ（Ｃ（３，３））的结论．　考虑到相邻网格对网格密度的影响，本文采用网格拥挤距离与网格密度相结合的策略选择全局极　值．本文计算网格拥挤距离与ＮＳＧＡ２中方法不同之处在于网格拥挤距离的计算基于ＳＰＴ进行，由于　ＳＰＴ从根节点到网格节点之间各层节点本身包含了计算拥挤距离所需信息，因此在ＳＰＴ上计算所有网　格的拥挤距离只需遍历一次ＳＰＴ，其计算复杂度比ＮＳＧＡ２降低了一个量级．　定义７　网格单元Ｃ对应的第　维拥挤距离为Ｃｒｏｗ　（ｃ）＝Ａｖｇ（∑Ｉ　ｃ　啦　．ｃ　一ｃ．ｃ　ｌ），其中　第４期　刘华蓥，等：基于空间划分树的多目标粒子群优化算法　６９９　　ｌＣ　ｉｇｌＩｂ０　・ｃ　—ｃ・ｃ　１为网格ｃ在第ｉ维上与其最近邻ｃ　ｇｌＩｂｃ　的距离，Ｃｎｅｉｇｈｂｏｒ最多可能有２个，也可能有　１个（处在该维边界上）或０个（只有一个网格）．Ａｖｇ（）计算ｃ在第ｉ维上与所有Ｃｎｅｉｇｈｂｏｒ的平均距离．　Ｍ　定义８网格ｃ的拥挤距离为Ｃｒｏｗ（Ｃ）＝∑Ｃｒｏｗ　（ｃ）．　网格拥挤距离的计算从根节点开始在每层非叶节点上进行．计算所有网格的拥挤距离只需从根节　点开始遍历一次ＳＰＴ．不同网格如果有公共祖先，则它们在公共祖先对应各维的拥挤距离相同，如图２　中的网格ｃ（３，２）和ｃ（３，３），它们的公共祖先是ＳＰＴ第ｌ层间隔段号为３的节点，故有　Ｃｒｏｗ　（Ｃ（３，２））＝Ｃｒｏｗ　（ｃ（３，３））．为了避免公共部分拥挤距离的重复计算，ＳＰＴＭＯＰＳＯ使用栈　Ｓｔａｃｋ　保存计算各维拥挤距离的中间结果，当算法遍历到一个叶节点时，Ｓｔａｃｋ　中依次保存了该叶　节点对应各维的拥挤距离，求和即可得到其拥挤距离．当计算相邻节点时，只需执行Ｐｏｐ（Ｓｔａｃｋ　）操　作，然后把相邻节点在该维的拥挤距离人栈Ｐｕｓｈ（Ｓｔａｃｋ　～）．网格的拥挤距离越大，其中的非支配解　作为ｇｂｅｓｔ进行搜索的潜力越大．　为了维持解集分布的均匀性，规定每个网格ｃ中保存非支配解的最大个数为ｎｕｍ　．　定义９网格密度Ｄｅｎ（Ｃ）＝Ｃ．ｎｕｍ／ｎｕｍ．￣．　Ｄｅｎ（Ｃ）越小，其中非支配解的局部搜索能力越强．　定义１０拥挤距离密度比Ｋ　。＝Ｃｒｏｗ（Ｃ）／Ｄｅｎ（Ｃ）．　ｇｂｅｓｔ优先从Ｋ　。最大的网格中选取．　２．４外部集的更新　设＿Ⅳ为Ａｒｃ的规模．如果非支配解　插入网格Ｃ时其中非支配解数目已达到ｎｕｍ一，则从ｃ中　随机删除一个粒子，然后把　插入ｃ．若　插入外部集时，外部集中非支配解数目已经达到　，则优　先从　ｃ，Ｄ值最小的网格中随机删除一个非支配解．若网格中非支配解已被全部删除，则从ＳＰＴ中删除　对该网格的索引．　２．５算法　下面给出基于空间划分树的多目标粒子群优化算法．　设Ⅳ为粒子群Ｐ的规模，Ｐ　为第ｉ次迭代后得到的非支配解集，ｌＰ　ｌ为Ｐ　中非支配解个数．　ｍａｘ＿ｉｔ为最大迭代次数，函数Ｒａｎｄｏｍ｛　，Ｙ｝从集合｛　，Ｙ｝中随机选择一个．粒子搜索时有速度限制　，当粒子飞出搜索空间时，令粒子的位置在边界上，其速度＝一　／２．　Ｓ　ＭＯＰＳＯ算法描述如下：　Ｉｎｉｔｉａｌ（Ｐ）；／／初始化粒子群Ｐ　Ｐａｒｔｉｔｉｏｎ（ｋ），Ｃｒｅａｔｅ（ＳＰＴ）；／／划分目标空间网格，建立ＳＰＴ　Ｆｏｒ　ｉ＝１　ｔｏ　ｆ　Ｐ０　ｌ　执行Ｉｎｓｅｒｔ（ＳＰＴ，　）把非支配解　加入Ａｒｃ并对其建立ＳＰＴ索引；／／ｘ　∈Ｐｏ　Ｅｎｄ　Ｆｏｒ　Ｗｈｉｌｅ　ｉ＜ｍａｘｉｔ　—Ｆｏｒ　ｊ＝１　ｔｏ　Ｎ　Ｉｆｘｊ＞ｐｂｅｓｔｊ　ｐｂｅｓｔｉ＝ｘｊ　Ｅｌｓｅ　Ｉｆ！（ｐｂｅｓｔ￣＞ｘｓ）　ｐｂｅｓｔｓ＝Ｒａｎｄｏｍ｛　，ｐｂｅｓｔｊ｝；　Ｅｎｄ　Ｉｆ　Ｅｎｄ　ｌｆ　Ｅｎｄ　Ｆｏｒ　通过Ｔｒａｖｅｒｓａｌ（ＳＰＴ）计算ＳＰＴ索引的每个网格ｃ的Ｃｒｏｗ（Ｃ）与Ｄｅｎ（Ｃ）；　从Ｋ　。值最大的网格中随机选择一个粒子作为ｇｂｅｓｔ；　７００　吉林大学学报（理学版）　第４９卷　用式（１），（２）更新Ｐ中所有粒子的速度和位置；　Ｆｏｒｊ＝１　ｔｏ　Ｉ尸　ｌ　执行Ｕｐｄａｔｅ（ＳＰＴ，　）；／／ｘ　∈Ｐ　Ｅｎｄ　Ｆｏｒ　Ｅｎｄ　Ｗｈｉｌｅ　使用ＳＰＴ索引划分后的目标空间网格不仅能有效保存数据的空间位置信息，而且能保存单元的相　对空间位置信息．计算任意网格ｃ密度Ｄｅｎ（Ｃ）即为查找网格ｃ的过程，最差情况下ＳＰＴ中有ｋ个非　叶节点，ＳＰＴ共　＋１层，查找网格在某层的间隔段号需要进行ｌｏｇ：ｋ次比较，查找一个网格共需　Ｍｌｏｇ　ｋ次比较．ＳＰＴ从根节点到网格节点之间各层节点本身包含了计算拥挤距离所需信息，在ｓＰｒ上　计算所有网格的拥挤距离只需遍历一次ＳＰＴ，最差情况下ＳＰＴ索引　个非空网格（此时每个非空网格　中只落入一个非支配解），遍历ＳＰＴ需要　ｏｇ：ｋ次比较．对于不同问题，规模ｋ为常数，因此　ＳＰＴＭＯＰＳＯ算法确定ｇｂｅｓｔ的时间复杂度为０（ＭＮ）．由于Ａｒｃ规模＿Ⅳ的设置采用与ＮＳＧＡ２相同的方　法，即与种群规模Ⅳ呈线性关系，于是确定ｇｂｅｓｔ的时间复杂度为Ｏ（ＭＮ），而ＮＳＧＡ２为Ｏ（ＭＮｌｏｇ：Ｎ）．　ＳＰＴ仅索引非空网格，一般情况下非空网格数量远小于空网格数量，因此实际计算量要小得多．　３实验结果与分析　・　多目标优化算法的性能评价指标很多，主要分为三类：收敛性能、分布性能（多样性能）和综合性　能．本文选用其中两个指标评价算法的性能．　定义ｌ１　ｌ叫算法所获得的解与Ｐａｒｅｔｏ最优前端的趋近程度ｇｅｎｅｒａｔｉｏｎａｌ　ｄｉｓｔａｎｃｅ（ＧＤ）定义为　ＧＤ＝　，其中：ｒｔ表示算法最终获得的解个数；ｄ　为第ｉ个解到最优前端的最短距离．　ＧＤ值越小，表明算法所获得的解越趋近最优前端．　定义１２［１　］　Ｓｐａｃｉｎｇ（ＳＰ）用于描述算法获得的解在目标空间上的分布是否均匀，定义为ＳＰ＝　√　厂　——　———一　（　一　）　，其中：ｄ　均值．　，：Ｍ　噬　，　（　Ｊ／　一　Ｊ）；凡表示算法最终获得的解个数；　是ｄ　的平　ｓＰ值越小，表明该算法获得的解分布越均匀．　本文使用ＳＣＨ，ＺＤＴＩ，ＺＤＴ２和ＺＤＴ３四个测试函数¨　验证ＳＰＴＭＯＰＳＯ算法．这些测试函数的最优　前端有凸的、非凸的和不连续的．对这些具有不同形状最优前端的函数进行测试，并把实验结果与　ＮＳＧＡ２和ＰＡＥＳ的结果进行对比．ＳＰＴＭＯＰＳＯ算法参数设置如下：粒子群初始规模为２００；最大迭代次　数为２００；学习因子Ｃ。＝ｃ２＝０．５；　从０．９随迭代线性变化到０．４；ｋ＝３０；ｎｕｍ　：１０；ｎ＝３０．ＮＳＧＡ２　和ＰＡＥＳ的参数设置如下：种群大小１００，外部集合大小为ＩＯ０，交叉概率为０．８，二元锦标赛选择和二　进制编码，变异概率为染色体长度的倒数．ＰＡＥＳ的每维目标被划分的数量为ｌ０．３种算法分别对每个　函数独立运行３０次．图３～图６为本文算法所得的近似Ｐａｒｅｔｏ最优前端．表１列出了３种算法的计算　结果．　由表１可见，ＳＰＴＭＯＰＳＯ算法具有较好的收敛性能，在４个测试函数上都优于ＰＡＥＳ，在ＺＤＴ１，　ＺＤＴ２和ＺＤＴ３三个函数上优于ＮＳＧＡ２．这是由于ＳＰＴＭＯＰＳＯ算法的全局极值选取策略更合理，而且基　于空间划分树的全局极值选择算法具有更高的计算效率．　表１的计算结果也验证了在空间划分树上使用拥挤距离和网格密度相结合策略维护外部种群的有　效性．由于考虑了相邻网格对网格密度的影响，所以ＳＰＴＭＯＰＳＯ算法对４个测试函数产生的非支配解　在最优前端的分布都比ＰＡＥＳ更广、更均匀，在ＳＣＨ和ＺＤＴ２上分布性能略差于ＮＳＧＡ２，而在ＺＤＴ１和　ＺＤＴ３上比ＮＳＧＡ２具有更好的分布性．　第４期　刘华蓥，等：基于空间划分树的多目标粒子群优化算法　７０１　图３　ＳＣＨ的近似Ｐａｒｅｔｏ最优前端　图４　ＺＤＴＩ的近似Ｐａｒｅｔｏ最优前端　Ｆｉｇ．３　Ａｐｐｒｏｘｉｍａｔｅ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｆｒｏｎｔ　ｏｆ　ＳＣＨ　Ｆｉｇ．４　Ａｐｐｒｏｘｉｍａｔｅ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｆｒｏｎｔ　ｏｆ　ＺＤＴＩ　图５　ＺＤＴ２的近似Ｐａｒｅｔｏ最优前端　图６　ＺＤＴ３的近似Ｐａｒｅｔｏ最优前端　Ｆｉｇ．５　Ａｐｐｒｏｘｉｍａｔｅ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｆｒｏｎｔ　ｏｆ　ＺＤＴ２　Ｆｉｇ．６　Ａｐｐｒｏｘｉｍａｔｅ　Ｐａｒｅｔｏ　ｏｐｔｉｍａｌ　ｆｒｏｎｔ　ｏｆ　ＺＤＴ３　表１　３种算法的计算结果对比　Ｔａｂｌｅ　１　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｃａｌｃｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｏｆ　３　ａｌｇｏｒｉｔｈｍｓ　由于ＳＰＴＭＯＰＳＯ算法中全局极值的选取不仅考虑了个体网格的密度信息，而且综合了个体网格与　相邻网格问的拥挤距离信息，使得选取全局极值时的估值更准确、分布更均匀，能够较好地逼近Ｐａｒｅｔｏ　最优前端．所以，与其他两种算法相比，ＳＰＴＭＯＰＳＯ算法具有一定的优势．　综上可见，ＳＰＴＭＯＰＳＯ算法使用网格对多维目标空间进行划分，网格保存数据空间位置信息，空　间划分树在索引存储非支配解的非空网格的同时记录非空网格的相对空间位置信息，为外部集维护提　供了高效的数据结构支持，能有效提高ｇｂｅｓｔ的计算性能；ＳＰＴＭＯＰＳＯ算法用ＮＳＧＡ２中拥挤距离的概　念重新定义网格拥挤距离并结合网格密度选取全局极值，使算法能较好地逼近Ｐａｒｅｔｏ最优前端，并且　可使Ｐａｒｅｔｏ最优解分布较均匀．　７Ｏ２　吉林大学学报（理学版）　第４９卷　参考文献　Ｋｅｎｎｅｄｙ　Ｊ，Ｅｂｅｒｈａｒｔ　Ｒ　Ｃ．Ｐａｒｔｉｃａｌ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　１９９５　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｓｅｒｖｉｃｅ　Ｃｅｎｔｅｒ，１９９５：１９４２—１９４８．　［２］　ＺＨＡＮＧ　Ｌｉ．ｂｉａｏ，ＺＨＯＵ　Ｃｈｕｎ—ｇｕａｎｇ，ＬＩＵ　Ｘｉａｏ—ｈｕａ，ｅｔ　ａ１．Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒ　Ｓｏｌｖｉｎｇ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ：Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ，２００５，２３（４）：３８５—３８９．　（张利彪，周春光，刘小华，等．粒子群算法在求解优化问题中的应用［Ｊ］．吉林大学学报：信息科学版，２００５，　２３（４）：３８５—３８９．）　［３］　ＹＵ　Ｆａｎ－ｈｕａ，ＬＩＵ　Ｈａｎ—ｂｉｎｇ．Ｓｔｒｕｃｔｕｒａｌ　Ｄａｍａｇｅ　Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ　ｂｙ　Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅ　ａｎｄ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ａｌｇｏｒｉｔｈｍ　［４］　［５］　［６］　［７］　［８］　［９］　［１０］　［１２］［１　３］　［１４］　［１５］　［１６］　［１７］　［１８］　［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ：Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｅｄｉｔｉｏｎ，２００８，３８（２）：４３４４３８．（于繁华，刘寒冰．　基于支持向量机和粒子群算法的结构损伤识别［Ｊ］．吉林大学学报：工学版，２００８，３８（２）：４３４４３８．）　ｕＵ　Ｓｈｕ—ｈｕａ，ＺＨＡＮＧ　Ｙｕ．Ｍｕｌｔｉ—ｒｏｂｏｔ　Ｔａｓｋ　Ａｌｌｏｃａｔｉｏｎ　Ｂａｓｅｄ　ＯＨ　Ｓｗａｒｍ　Ｉｎｔｅｌｌｉｇｅｎｃｅ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｎｏｒｔｈｅａｓｔ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ：Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ，２００９，４１（４）：６８－７２．（刘淑华，张嵛．基于粒子群蚁群算法的多机器人任务　分配方法［Ｊ］．东北师大学报：自然科学版，２００９，４１（４）：６８－７２．）　ＬＩ　Ｘｉｕ—ｙｉｎｇ，ＨＡＮ　Ｚｈｉ—ｇａｎｇ．Ａ　Ｃｏｎｔｒｏｌｌｅｒ　ｏｆ　Ｔ—Ｓ　Ｍｏｄｅｌ　Ｆｕｚｚｙ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ　Ｂａｓｅｄ　ｏｎ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｎｆｉｚａｔｉｏｎ　［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　ｏｆ　Ｈｅｉｌｏｎｇｊｉｎａｇ　Ｕｎｉｖｅｒｓｉｔｙ，２０１０，２７（２）：２７２—２７６．（李秀英，韩志刚．基＿ｆ粒子群　算法优化的Ｔ．Ｓ型模糊神经网络控制器［Ｊ］．黑龙江大学自然科学学报，２０１０，２７（２）：２７２－２７６．）　ＷＡＮＧ　Ｙａｎ，ＺＥＮＧ　Ｊｉａｎ—ｃｈａｏ．Ａ　Ｓｕｒｖｅｙ　ｏｆ　ａ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ『．１］．ＣＡＡＩ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｓｙｓｔｅｍｓ，２０１０，５（５）：３７７．３８４．（王艳，曾建潮．多目标微粒群优化算法综述［Ｊ］．智能　系统学报，２０１０，５（５）：３７７—３８４．）　Ｃｏｅｌｌｏ　Ｃ　Ａ　Ｃ，Ｐｕｌｉｄｏ　Ｇ　Ｔ，Ｌｅｃｈｕｇａ　Ｍ　Ｓ．Ｈａｎｄｌｉｎｇ　Ｍｕｌｔｉｐｌｅ　Ｏｂｊｅｃｔｉｖｅｓ　ｗｉｔｈ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２００４，８（３）：２５６－２７９．　ＺＨＡＮＧ　Ｌｉ—ｂｉａｏ，ＺＨＯＵ　Ｃｈｕｎ—ｇｕａｎｇ，ＭＡ　Ｍｉｎｇ，ｅｔ　ａ１．Ｓｏｌｕｔｉｏｎｓ　ｏｆ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍｓ　Ｂａｓｅｄ　ｏｎ　Ｐａｔｒｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００４，４１（７）：１２８６—１２９１．　（张利彪，周春光，马铭，等．基于粒子群算法求解多目标优化问题［Ｊ］．计算机研究与发展，２００４，４１（７）：　１２８６—１２９１．）　ＳＵＮ　Ｘｉａｏ—ｑｉａｎｇ，ＺＨＡＮＧ　Ｑｉｕ—ｍｉｎｇ．Ａ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｌ　Ｊ　ｊ．　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００６，１８：４０４２．（孙小强，张求明．一种基于粒子群优化的多目标优化算　法［Ｊ］．计算机工程与应用，２００６，１８：４０４２．）　Ｄｅｂ　Ｋ，Ｐｒａｔａｐ　Ａ，Ａｑａｒｗａｌ　Ｓ，ｅｔ　ａ１．Ａ　Ｆａｓｔ　ａｎｄ　Ｅｌｉｔｉｓｔ　Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ：ＮＳＧＡ一１Ｉ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｅ—　ｔｉｏｎｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（２）：１８２—１９７．　Ｚｉｔｚｌｅｒ　Ｅ，Ｔｈｉｅｌｅ　Ｉ．．Ｍｕｌｔｉｏｂｊｅｅｔｉｖｅ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍｓ：Ａ　Ｃｏｍｐａｒａｔｉｖｅ　Ｃａｓｅ　Ｓｔｕｄｙ　ａｎｄ　ｔｈｅ　Ｓｔｒｅｎｇｔｈ　Ｐａｒｅｔｏ　Ａｐｐｒｏａｃｈ　『Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，１９９９，３（４）：２５７—２７　１．　ＹＡＮＧ　Ｊｕｎ－ｊｉｅ，ＺＨＯＵ　Ｊｉａｎ—ｚｈｏｎｇ，ＦＡＮＧ　Ｒｅｎｇ—ｃｕｎ，ｅｔ　ａ１．Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ａｄａｐｔｉｖｅ　Ｇｒｉｄ　Ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｙｓｔｅｍ　Ｓｉｍｕｌａｔｉｏｎ，２００８，２０（２１）：５８４３—５８４７．（杨俊杰，周建中，方仍存，　等．基于自适应网格的多目标粒子群优化算法［Ｊ］．系统仿真学报，２００８，２０（２１）：５８４３—５８４７．）　Ｋｎｏｗｌｅｓ　Ｊ　Ｄ．Ｃｏｒｎｅ　Ｄ　Ｗ．Ａｐｐｒｏｘｉｍａｔｉｎｇ　ｔｈｅ　Ｎｏｎｄｏｍｉｎａｔｅｄ　Ｆｒｏｎｔ　Ｕｓｉｎｇ　ｔｈｅ　Ｐａｒｅｔｏ　Ａｒｃｈｉｖｅｄ　Ｅｖｏｌｕｔｉｏｎ　Ｓｔｒａｔｅｇｙ　ｌ　Ｊ　Ｊ．　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，２０００，８（２）：１４９—１７２．　Ｃｏｅｌｌｏ　Ｃ　Ａ　Ｃ，Ｌａｍｏｎｔ　Ｇ　Ｂ，Ｖｅｌｄｈｕｉｚｅｎ　Ｄ　Ａ，Ｖａｎ．Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍｓ　ｏｆｒ　Ｓｏｌｖｉｎｇ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｐｒｏｈｌｅｍｓ　ｌ　Ｍ］．　Ｎｅｗ　Ｙｏｒｋ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００７．　Ｖａｎ￣ｃｅｋ　Ｇ，Ｊｒ．ＢＲＥＰ—Ｉｎｄｅｘ：Ａ　Ｍｕｈｉｄｉｍｅｎｓｉｏｎａｌ　Ｓｐａｃｅ　Ｐａｒｔｉｔｉｏｎｉｎｇ　Ｔｒｅｅ［Ｍ］．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，１９９　１．　Ｖｅｌｄｈｕｉｚｅｎ　Ｄ　Ａ，Ｖａｎ，Ｌａｍｏｎｔ　Ｇ　Ｂ．Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ　Ｒｅｓｅａｒｃｈ：Ａ　Ｈｉｓｔｏｒｙ　ａｎｄ　Ａｎａｌｙｓｉｓ［Ｒ／ＯＬ　Ｊ．　１９９８—１０－１４．ｈｔｔｐ：／／ｗｗｗ．１ａｎｉａ．ｍｘ／～ｃｃｏｅｌｌｏ／ＥＭｏｏ／ｃｏｅｌｌｏｏ３ａ．ｐｄｆ．ｇｚ．　Ｓｃｈｏｔｔ　Ｊ　Ｒ．Ｆａｕｈ　Ｔｏｌｅｒａｎｔ　Ｄｅｓｉｇｎ　Ｕｓｉｎｇ　Ｓｉｎｇｌｅ　ａｎｄ　Ｍｕｈｉｃｒｉｔｅｒｉａ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｍ］．Ｍａｓｓａｃｈｕｓｅｔｔｓ：　Ｍａｓｓａｃｈｕｓｅｔｔｓ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，１９９５．　ＧＯＮＧ　Ｍａｏ—ｇｕｏ，ＪＩＡＯ　Ｌｉ—ｃｈｅｎｇ，ＹＡＮＧ　Ｄａｎｇ—ｄｏｎｇ，ｅｔ　ａ１．Ｒｅｓｅａｒｃｈ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，２００９，２０（２）：２７１－２８９．（公茂果，焦李成，杨咚咚，等．进化多目标优化算法　研究［Ｊ］．软件学报，２００９，２０（２）：２７１－２８９．）