（电子科学与技术专业论文）基于规则模型的多目标分布估计算法研究.pdf

a bs t r a c t u s i n ge v o l u t i o n a 巧a l g o r i t h m st os o l v em u l t i o b j e c t i v eo p t i m i z a t i o n p r o b l e m s ( m o p s ) h a sb e c o m eah o tt o p i ci nt l l ea r e ao fc o m p u t a t i o n a l i n t e l l i g e n c e b a s e do nt h er e g u l a r i t yo ft h es t r u c t u r eo fc o n t i n u o u s m u l t i o b ie c t i v eo p t i m i z a t i o np r o b l e m s p 2 u r e t o s e t ， s o m er e s e a r c h e r s p r o p o s e d a r e g u l a “t y m o d e l _ b a s e d m u l t i o b je c t i v e e s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m ( r m m 哐d a ) i n2 0 0 9 e x p e r i m e n tr e s u l t si n d i c a t e t h a tr m 匝d ai sv e we f ! f 、e c t i v et od e a lw i t hc o n t i n u o u sm u l t i - o b j e c t i v e o p t i m i z a t i o np r o b l e m sw i t hv 撕a b l el i n k a g e s h o w e v e r ，i t m - m e d a m a i n l yh a st h ef o l l o w i n gt w od r a w b a c k s ：1 ) d u r i n g t h em o d e l i n gp r o c e s s ， m ep r o b a b i l i t ym o d e l i sn o ta c c u r a c ye n o u 曲s i n c erm m e d ad o e sn o t 如1 1 ye x p l o i tt h er e g u l a r 埘o fd i 虢r e n tk i n do fm o p s ；a n d2 ) t h eg l o b a l s e a r c ha b i l i t yo fi 己m m 匣d ai ss ow e a kt h a ti th a sd i 衢c u l t yt os o l v e m u l t i m o d a lo b i e c t i v e 如n c t i o n s t h i sp a p e ra i m sa to v e r c o m i n gt h ea b o v et w od r a w b a c k s ，t h em a i n w o r ko fw h i c hc o u l db es u m m a r i z e da sf o l l o w s ： f o rp r o b l e mo ft h ea c c u r a c yo fm o d e l i n g ，a ni m p r o v e dv e r s i o no f i t m m e d ai s 。p r o p o s e d ，c a l l e di t m m e d a r r c o i t m m e d au s e sa c l u s t e r i n go p e r a t o rw h i c h i sb a s e do nl o c a lp r m c i p a lc o m p o n e n ta n a l y s i s t ob u i l dm o d e l e x p e r i m e n t a lr e s u l t ss h o wt h a tm en u m b e ro fc l u s t e r si s p r o b l e m d e p e n d e n ta n dh a sas i 昏1 i f i c a n te 日e c to nt h ep e r f o n n a n c eo ft h e a l g o r i t h n h o w e v e r ，r m n 匝d ar e c o m m e n d e dt h ef i x e dn u m b e ro f c l u s t e r sw h e ns o l v i n gd i n b r e n t 锣p e so fp r o b l e m s e v i d e n t l y ，t h i ss t r a t e g y i sn o tv e r yr e a s o n a b l e t h eb a s i ci d e ao fi m m 匣d a r f t c os h o w sa s f o l l o w s d u r i n ge a c hg e n e r a t i o n ，f i r s t l yw ej u d g e sw h e t h e rt h e r ee x i s t r e d u n ( 1 a n tc l u s t e r so rn o ta c c o r d i n gt 0t l l ec l u s t e r i n gr e s u l t s ，a n dt h e n r e d u c er e d u n d a n tc l u s t e r st oa 幽u s tt 1 1 ec l u s t e r i n gn u m b e r e x p e r i m e n t a l r e s u l t ss u g g e s tt h a tm ep r o p o s e da l g o r i t h mo u t p e r f o 咖si m i m e d ai n t e m so fe 仔萏c t i v e n e s sa n de f j e i c i e n c y f o rt l l ew e a kg l o b a ls e a r c ha b i l i 田o fi t m m 匣d a ，ag 1 0 b a l 砌订m e d ai sp r o p o s e d i 之m m e d ao n l ya p p l i e st h em a c r od i s t r i b u t i o n i n f o m a t i o no fi n d i v i d u a l st ob u i l dm o d e l ，h o w e v e rt 1 1 el o c a li n f o m l a t i o n o fm ei n d i v i d u a l si su s u a l l yi 9 1 1 0 r e d t h e r e f o r e ，i td o e sn o tu t i l i z et 1 1 e i n f o m l a t i o no fi n d i v i d u a l se 矗f e c t i v e l y i na d d i t i o n ，r m m e d ag e n e r a t e s n e wi n d i v i d u a l sb a s e do ng a u s ss a m p l i n go p e r a t o r i ti sn e c e s s 摊yt on o t e t h a tg a u s ss a m p l i n go p e r a t o ri sal o c a ls e a r c ho p e r a t o r a sar e s u l t ，m e g l o b a ls e a r c ha b i l i t yo fi t m m e d ai sw e a k i no r d e rt om a k em uu s eo f t h ei n f o n n a t i o no fi n d i v i d u a l sa n di m p r o v et h eg l o b a ls e a r c ha b i l i t y ，t h e g l o b a lr m m e d ai n c o r p o r a t e sd i 腩r e n t i a le v o l u t i o nw h i c hh a ss t r o n g 9 1 0 b a ls e a r c ha b i l i t yt oi t m m 匣d a f i n a l l y ，e x p e r i m e n t a lr e s u l t ss h o w t h a tt h ep r o p o s e da l g o r i t h mi se f j f e c t i v e k e yw o r d sm u l t i o b j e c t i v eo p t i m i z a t i o n ，e s t i m a t i o no fd i s t r i b u t i o n a l g o r i t h m ，m o d e l i n g ，g l o b a ls e a r c ha b i l i t y m 硕七学位论文 第一章绪论 1 1 多目标优化问题 第一章绪论 无论是科学研究还是工程应用中多目标优化都是非常重要的研究课题【l 】，例 如企业生产中追求的最大效益和最低成本问题就是一个典型的多目标优化问题 ( m o p s ：m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s ) 。类似的领域还包括i t 软硬件 系统的设计、生产管理、经济规划、工业制造、政府决策、和军事国防等。然而 这些实际问题的求解非常复杂、困难，科研人员往往需要投入大量的精力才能很 好地解决这类优化问题。因此，求解多目标优化问题是一个非常具有实际意义和 科研价值的课题。 求解多目标优化问题与单目标优化问题有本质的区别，它没有唯一的最优 解，而是在各目标之间进行协调权衡和折衷处理，使各个目标尽可能达到最优， 最终寻找一个最优折衷解集。为了不失一般性，多目标优化问题的描述如下： 定义1 1多目标优化问题( m o p s ) ： 最小化问题：厂( i ) = ( 石( i ) ，以( 王) ，厶( 膏) ) s t x q( 1 】) 其中x q 为决策空间，i = ( 而，x 。) xcr ”代表决策变量矢量。 尹：xj 尺”为具有聊个子目标的多目标优化问题。例如，朋= 2 时，是双目标优化 问题。 定义1 2p 删。支配：给定两个向量厅= ( 口l ，口埘) ，6 = ( 6 l ，6 埘) r ”，如果满 足下列条件： 1 ) 对于所有的子目标云不比6 差，即：q 匆，扣1 ，2 ，刀，。 2 ) 至少存在一个子目标，使历比6 好，即j 1 ，朋 ，使口， 6 ，。那么称 云支配6 ，表示成历 6 。其中，云是非支配的，6 是被支配的。 定义1 3p 蹦知最优解：若i x 为某个给定的多目标优化问题的一个解，如果 不存在其它的i x ，使厂( i ) - 艺，最+ l 中的解集直接受最的解集支配( 七= 1 ，2 ，聊一1 ) 。 笼统的说，e 就是最优秀的非支配前沿，e 是次优秀的非支配前沿，其余 的子种群可以此类推。 为了保持种群的分布性和多样性，需要计算个体的聚集距离【，通常将优秀 的并且聚集密度小的个体保留参与下一代进化，个体的聚集距离是通过计算与其 相邻的两个个体在每个子目标上的距离差之和来求得。如图2 5 所示，求解双目 标极小化问题，z 和五表示这两个子目标，个体z 的聚集距离为图中虚线矩形的 长与宽的和，令饥刁为个体f 的聚集距离，矿阶肌表示个体f 在子目标朋上的适 1 6 硕上学位论文 第二章基于规则模型的多目标分布估计算法 应值，那么可按公式( 2 1 2 ) 计算个体f 的聚集距离。 d 力= ( y f + 1 】彳一矿 f 一1 】z ) + ( y 【f + 1 六一y f l 】石) ( 2 一1 2 ) 在通常情况下，有朋个子目标时，个体f 的聚集距离计算方法如公式( 2 1 3 ) 所示： 引f 】= ( y f + 1 】五一叫f l 】五) ( 2 - 1 3 ) 七= l i 蝴- m e d a 选择操作从种群p ( f ) u q 选取个优秀的个体组成下一代进化群 体尸( r + 1 ) 。算法的具体过程如下： s t e p1 构造群体p o ) uq 的偏序关系鼻 - 疋 - 吒，且设p u + 1 ) = o ，肛o 。 d o 后= 七+ 1 ： p o + 1 ) = p ( f + 1 ) u e ； u n t ni 尸o + 1 ) ； 该步骤是精英选择机制，选择前几个最好的非支配前沿个体加入到 下一代种群p ( f + 1 ) ，直到p o + 1 ) 的规模大于种群规模。 s t e p2 w h n el 尸9 + 1 ) l ，d o ： a )计算种群尸u + 1 ) n 最中所有个体的聚集距离。 b )然后从群体p o + 1 ) n e 中移除具有最小聚集距离的个体，若 存在多个个体具有相同的最小聚集距离则随机的删掉其中一个。 e n d w h i i e 子代种群p ( f + 1 ) 的规模大于时，需要从最后进入p p + 1 ) 的前沿 面e 删除聚集密度高的个体，从而限定种群规模为，并较好的保证其 多样性。算法每次只移除一个聚集密度最高的个体，然后重新计算修剪 后种群的个体的聚集距离。这种方式可以更好的确保算法的分布性和多 样性。 2 4 本章小结 本章详细介绍了i 己m m e d a 的建模，采样以及选择等过程。传统的m o e a s 均采用交叉，变异等遗传操作来产生新个体，而这些遗传操作虽然具有较强的搜 索能力，能有效的驱动算法的运行，但是很大程度上破坏了决策变量的相关性。 因此传统的m o e a s 很难处理变量相关的m o p s 。r m m e d a 是一种基于分布估 硕l ：学位论文 第二章基于规则模型的多目标分布估计算法 计算法的新型m o e a ，可以有效求解变量相关的连续m o p s ，它主要包括建立概 率模型和随机采样两个过程。大量的实验表明求解变量相关的连续m o p s 时 i 之m m e d a 优于常见的其它m o e a s ，如n s g a i i ，m o e d ，g d e 3 以及m i d e a 等，然而i 洲m e d a 也存在以下缺点： ( 1 ) 实时性较差：基于数学统计方法的建模过程计算复杂，算法的总运行 时间长。 ( 2 ) 算法参数敏感：聚类数目k 的取值具有问题依赖性，因此k 的取值较 大的影响算法性能。 ( 3 ) 全局搜索能力弱：i 蝴m e d a 本质上是一种局部搜索算法，极难求解 多模优化问题。 针对上述不足，根据i 己m m e d a 算法的特征，未来的研究工作可以从下列 几个方面入手： ( 1 ) 用机器学习的方法来建立概率模型以降低计算复杂度，例如混合概率 主成分分析法。 ( 2 ) 采用自适应动态的方式调整参数k 值，消除算法参数对刚m e d a 性 能的影响。 ( 3 ) 为了提高全局搜索能力，考虑结合个体的局部信息和全局统计信息， 例如采用引导变异的方式实现二者的结合。 ( 4 ) 结合元模型技术来减少算法的评估次数。 ( 5 ) 将i 洲m e d a 应用到约束或者动态多目标优化问题中去。 1 8 硕十学位论文 第三章带删除冗余聚类算子的r m m e d a 3 1 引言 第三章带删除冗余聚类算子的i w m e d a 第二章详细地介绍了r m m e d a 的算法流程，可知建模过程是r m m e d a 算法至关重要的步骤。基于良好的概率模型，采样过程可以产生大量更加优秀的 新个体，从而有利于算法快速收敛。 根据前面的分析，l 洲m e d a 适合求解变量相关的连续m o p s 。这些连续 m o p s 的p s 结构在决策空间呈分段连续的流形分布。r m m e d a 利用聚类后的 子种群宏观统计信息来估算相应的一段p s 流形结构。它首先采用局部主分量分 析法将种群尸( f ) 聚类成k 个相互独立的子种群c 1 ，c r ，然后每个聚类g 分别 建立相应的一段p s 流形结构的模型。现在关键的问题是：如何确定参数k 的 取值( k 表示聚类数目) ? 然而在求解任何优化问题时，i 洲e m d a 都将k 值 设定为一个固定值。显然这一处理方法存在合理性。因为不同形状的p s 分布结 构需要被划分成数目不同的流形片段，从而需要不同数目的聚类子种群，也就是 不同的聚类数目k 。 如图3 1 所示，假定一个连续m o p s 的p s 分布结构如图中所示。显而易见， 如果将k 的值设定为3 ，那么由局部主分量分析法建模得到的每个，均可很好 地拟合相应的一段p s 流形结构。但若k 的取值不等于3 ，肯定会出现不同的结 果。下一节将以实验为基础着重讨论k 的取值对建模效果的影响。 图3 1 聚类和建模结果( 肛3 ) 硕十学位论文第三章带删除j c 余聚类算子的r m m e d a 3 2 带删除冗余聚类算子的r m m e d a i 蝴m e d a 采用基于局部主成分分析法的聚类操作建立p s 的概率模型。实 验结果表明，聚类数目的取值具有问题依赖性，而且对算法建模的精确性具有显 著影响。然而，在求解各种类型的多目标优化问题时，r m m e d a 均使用固定的 聚类数目，显然具有不合理性。针对i 洲m e d a 建模过程的缺陷，提出一种带 删除冗余聚类算子的r m m e d a ，即r m m e d a r r c o 。 3 2 1r m m e d a 建模精确性 本小节主要通过实验的方法来分析研究聚类数目的取值对r m m e d a 算法 性能的影响。如图3 2 所示，假定某个优化问题的p s 结构是一维连续的正弦曲 线，满足： 薯= s i n ( 2 p f 五) ，薯= s i n ( 2 p f 鼍) ，0 两1 ( 3 - 1 ) 其中，刀表示决策空间的维数，为了方便起见，实验中，设定：玎= 2 。图中 黑色曲线代表p s 分布结构，其周围均匀分布的圆点表示个体。 图3 2 正弦曲线分布的p s 结构 实验中，使用局部主分量法对种群进行聚类，然后计算出p s 流形结构的概 率模型，即模拟i 洲一m e d a 的建模过程。实验设定不同的k 值分别观察建模结 果，并分析比较k 的取值对r m m e d a 性能的影响。 显然，处理图3 2 所示的情况只需要三条线段，缈：和即可有效的估计 p s 流形结构，因此聚类数目取为3 是非常合适的，即这个问题实际所需要的聚 类数目为3 。 2 皿 硕上学位论文第三章带删除) 余聚类算了的r m m e d a 图3 3 ( a ) 显示了k 为3 时的聚类结果，图3 3 ( b ) 是根据公式( 2 - 7 ) 计算得到 的概率模型，少：和。然而值得注意的是：因为局部主分量分析法以随机选 择的k 个初始点为基础，且最终的聚类结果在一定程度上由这几个初始点决定， 所以局部主分量分析法的聚类操作具有一定的随机性，每次聚类得到结果可能不 同。，图3 3 是k 设为3 时最常见的聚类结果。 ( a ) 聚类结果( b ) 建模结果 图3 3 聚类和建模结果( 肛3 ) 现在将k 设为2 ，此时聚类数目少于实际所需( 肛3 ) 。实验得到两种最常 见的建模( 聚类) 结果如图3 4 ( a ) 和图3 4 ( b ) 所示。图3 - 4 表明建立的概率模型 和并不能较好地估计出实际的p s 流形结构。特别是基于图3 4 ( b ) 的概率模型 采样几乎无法产生更加优秀的新个体。所以这种情况下算法的收敛速度非常地缓 慢，甚至可能造成种群无法进化，算法不能收敛到真实的p a r e t o 前沿。 因此，当聚类数目少于实际所需要时，不能建立正确的概率模型，从而影响 了i 己m m e d a 的收敛性，甚至导致算法无法收敛。 图3 - 4 建模结果( 肛2 ) 2 l ( b ) 硕七学位论文第三章带删除兀余聚类算子的r m m e d a 图3 5 聚类和建模结果( ，- 5 ) ( b ) 接下来，进一步讨论聚类数目多于实际所需时，聚类数目对算法性能的影响。 图3 5 显示出了k 设置为5 时，两种最常见的建模结果。图3 5 ( a ) 和图3 5 ( b ) 中 都存在三个线段( 模型) 能很好地拟合p s 的流形结构，但还存在两个冗余或错 误的模型，例如，图3 5 ( a ) 的模型和y ，。通常来说，基于冗余或者错误的模型 采样产生的新个体往往是劣等的，这些较劣等的个体很难进入下一代参与进化， 因此，它们消耗了函数评估次数( 缸1 c t i o ne v a l u a t i o n s ) 却毫无价值。如果每代 产生越多的劣等个体，就会浪费越多的函数评估次数，从而增加了算法成本或者 说降低了算法的收敛速度。此外，图3 5 ( a ) 中模型，y ，和认都是用于估计p s 结构的同一段流形结构，他们对应的三个聚类子种群可以合并为一个聚类种群， 而且不难发现想象这个合并的聚类可以更好地估计出这一段p s 流形结构。图 3 5 ( b ) 中，还有一个非常有意义的现象：第二个聚类种群仅由一个个体构成。实 际上这个聚类并不是一个有效的聚类，它的出现完全是由于聚类数目多于实际所 需的聚类数目。 因此，当聚类数目多余实际所需时，p s 的结构模型可以很好的估计出来， 但是产生的冗余或错误的模型同样会影响i 蝴m e d a 的收敛速度。 根据上面的实验分析，可知如果i 洲m e d a 算法中使用的聚类数目与实际 问题所需要的不符合，那么它在一定程度上影响了蹦m e d a 的算法性能。尤 其是，当算法中采用的聚类数目少于实际所需时，算法建立的概率模型通常是不 准确的，从而导致了算法收敛速度缓慢，甚至无法收敛到真实的p a r e t o 前沿。另 一方面，聚类数目大于实际需要，会出现冗余或错误的模型，这些冗余或者错误 的模型也会减慢算法的收敛速度。但是总体而言，i 蝴m e d a 的聚类数目多于实 际所需时比少于实际所需时要优秀得多。也许这就是求解论文【2 3 】中所有的测试 0 o ， 硕十学位论文第三章带删除冗余聚类算子的i t m m e d a 函数( 这些测试函数实际所需的聚类数目为l 或者2 ) r m m e d a 将聚类数目固 定成一个较大值5 的原因。 3 2 2 删除冗余聚类算子 i w m e d a 求解任何m o p s 时都将聚类数目k 固定为一个较大的值。然而 聚类数目的取值具有问题依赖性，聚类数目k 设置为较大的值对算法的性能有 一定的负面影响。所以r m m e d a 采用静态固定的聚类数目k 求解任何m o p s 是不合理并且需要改进的。针对r m m e d a 算法的这一缺陷，设计出了一个删 除冗余聚类算子( r r c o ：r e d u c i n gr e d u n d a n tc l u s t e r so p e r a t o r ) ，本质是一种根 据问题特征自适应动态地调整聚类数目的操作。接下来详细地介绍r r c o 算子。 从3 3 小节的实验分析中，可知算法中如果存在冗余的聚类，可以观察到两 种特殊的现象： 1 ) 出现仅包含一个孤立个体的聚类，如图3 5 ( b ) 中的第二个聚类子种群。 2 ) 出现重叠在一起的概率流形，它们都可以用来拟合同一段p s 流形结 构，如图3 - 5 ( a ) 中的，和。 根据这两个现象设计出了r r c o 算子。在局部主分量分析法执行完毕后， 可以得到k 个模型，缈r 。r r c o 算子根据这些模型之间的相互关系来动态 地调整聚类数目k ，它的伪代码如下： s t e p1 s e t 么= y ，杪k ) ； s t e p 2 f o r f _ l ：k s t e p 3 i fc 只包含一个孤立的个体，n l e n 么= 彳、弘； s t e p 4 e n d f o r s t e p 5 三= o ； s t e p 6 w h 订e 么i 0 d o s t e p7 从彳中选取第一个模型标记为：y 。并且从彳中移除少，即么= 彳少； s t e p8 f o r 卢1 ：i4 s t e p9 i f 彳中第f 个模型与满足条件l 和条件2 ( 条件1 和条件2 后面有详 细说明) ，t i l e n 将彳中第f 个模型储存到集合b ； s t e p1 0 e n df o r s t e p1 1 彳= 彳、曰； s t e p1 2 = 三+ 1 ； s t e p1 3 e n d 、n e s t e p1 4 蜃屯算法结束。 硕上学位论文第三章带删除冗余聚类算了的i t m m e d a 图3 6r r c o 算子分析示意图 在r r c o 操作中，采用夹角法进行识别重叠在一起的模型。假定m o p s 具 有加个目标，那么需要计算( 朋1 ) 维超矩形之间的夹角。例如求解双目标优化 问题时，夹角指线段间的夹角，当处理三目标优化问题时，表示矩形间的夹角。 依此类推，r r c o 可处理任意维的m o p s 。 一般情况下，如果两个模型之间的夹角小于某个预先设置的阈值，即可判断 两个模型是重叠的。然而，必须指出的是两个非重叠但平行的模型的夹角也非常 小。如图3 6 所示：线段( 模型) 和是相互重叠的，它们的夹角非常小；奶 与认是相互平行的模型，它们之间的夹角也非常小。 因此，仅仅凭借夹角的大小来识别重叠的模型会导致错误产生。接下来，以 图3 6 为例来阐明如何区分相互重叠的模型和相互平行的模型。图中，点a 与点 6 分别为第二个聚类种群和第三个聚类种群的中心点。可以发现，线段动与帆或 者沙的夹角也非常小。但是类似的情况，点c 与点d 分别为第一个聚类种群和 第五个聚类种群的中心点，线段耐与或者愀的夹角却比较大。基于上面的分 析可以设定下列两个条件来识别两个模型是否是相互重叠的： 条件1 ) ( ，少，) 口：模型与y ，的夹角小于某个阈值秒。 条件2 ) ( 喁，) ( ，) ，其中c e 与c 弓分别表示聚类e 与q 的中心 点，叱代表c 只和c e 的连线。即线段c 弓与或者y f 的夹角小于与y ，的夹 角。 论文中将这个预定的阈值秒设置为3 。当且仅当条件1 ) 和条件2 ) 都满足 时，算法判定帆与y ，是相互重叠的，若只满足条件1 ) 而不满足条件2 ) 时，这 两个模型是相互平行的。附录给出了计算欧几里得空间任意维超平面间的夹角计 算方法。 硕十学位论文第三章带删除冗余聚类算了的r m m e d a 3 2 3r m m e d a r r c 0 算法流程 本章将r r c o 算子融入r m m e d a 算法提出一种改进r m m e d a 算法，即 带删除冗余聚类算子的r m m e d a ( r m m e d a r r c o ：r m m e d aw i t h r e d u c i n gr e d u n d a n tc l u s t e r so p e r a t o r ) 。i 己m m e d a r r c o 的算法框架与原 r m m e d a 大致相似，不同点在于它嵌入了一个新的r r c o 算子。在进化过程 中，原i 洲一m e d a 的聚类数目是静态固定的而i 洲m e d a 。r r c o 根据每代聚类 结果动态地调整聚类数目，蹦m e d a r r c o 的算法步骤大致如下。 s t e pl 初始化：均匀随机的方式产生一个初始种群只= 氍，i ：，霸) ，并且初始 化聚类数目k 值。 s t e p2 建立模型：使用( m 1 ) dl o c a lp c a 建立概率模型。 s t e p3 更新聚类数目：采用r r c o 算子调整k 值。 s t e p4 采样：基于s t 印2 建立的概率模型采样产生一个新的后代种群9 。 s t e p5 选择：从种群p f 和q f 选取个优秀个体作为下一代进化种群尸，+ 1 。 s t e p6 结束条件：如果满足算法结束条件则输出最终得到的非支配解集的 厂v a l u e ，并且算法结束。否则，跳转至s t e p2 。 r m m e d a - r r c o 算法中初始化，建模，采样以及选择等过程与i 己m m e d a 算法完全一样，所以不再详细描述。 3 3 实验设计与结果 3 3 1 测试函数 由前面的分析可知聚类数目k 的选取是依赖于具体优化问题的，确切的说 它由连续m o p s 的p s 流形结构所决定。o 算子的目的是通过在进化过程中 修正聚类数目k 值，使k 值尽可能的接近实际问题所需，从而加快算法的收敛 并且确保较好的分布性。鉴于此，本文基于常用的多目标测试函数集z d t 【5 1 巧3 】 设计了具有不同p s 流形结构的十个多目标测试函数。下面给出这十个测试函数： f u l l c t i o n1 ： x 【0 ，1 】 刀= 3 0 硕士学位论文 第三章带删除冗余聚类算子的i 巩i m e d a i i l i n 石( x ) = 五 m i n 六( x ) = g ( x ) 1 一以丽】 g ( x ) = l + 9 ( ( x ，一五) 2 ) ( 以一1 ) f = 2 f u l l c t i o n2 ： x 0 ，1 】 挖= 3 0 商n 彳 ) = 五 m i n 五( x ) = g ( x ) 1 一( 彳( x ) g ( x ) ) 2 】 g ( x ) = l + 9 ( ( 葺一西) 2 ) 坳一1 ) 扛2 f u l l c t i o nl 和f u l l c t i o n2 这两个测试问题都是双目标优化问题。它们的决策 变量线性相关满足= 恐= ，薯【0 ，l 】，p s 流形结构在决策空间是一维的线 段。这两个优化问题所需的理想聚类数目为1 。 f u n c t i o n3 ： x 0 ，1 】 胛= 3 0 i n i n 彳( x ) = l i l i n 厶( x ) = g ( x ) 1 一以丽】 g ( x ) = 1 + 9 ( ( 薯2 一五) 2 ) ( 刀一1 ) f = 2 f u l l c t i o n4 ： x 0 ，1 】 刀= 3 0 i n i n 彳( x ) = 而 n l i n 五( x ) = g ( x ) 1 一( 石( x ) g ( x ) ) 2 】 g ( x ) = 1 + 9 ( ( 而2 一_ ) 2 ) o 一1 ) f = 2 f u i l c t i o n3 和f u n c t i o n4 这两个测试问题都是双目标优化问题。它们的决策 变量非线性相关满足吒= 而= 五，薯【o ，1 】，p s 流形结构在决策空间是一维 的二次曲线。这两个优化问题所需的理想聚类数目为2 。 f u r l c t i o n5 ： x 【o ，1 】1 卜1 ，1 r - 1 刀= 3 0 硕j 二学位论文第三章带删除冗余聚类算了的r m m e d a m i n 石( x ) = 五 m i n 厶( x ) = g ( x ) 【1 一以丽 g ( x ) = l + 9 ( ( 薯一c o s ( 2 万一) ) 2 ) 恸一1 ) f = 2 f u n c t i o n6 ： x 【o ，1 】1 一1 ，1 】”一1 力= 3 0 幽肫一+ 击州。( _ 一c o s ( 2 圳2 ) m i n 胁) _ 1 一历+ 南：( p o s ( 2 硼2 ) 以= i 括。砌捌2 ，疗) 口聆d 以= i 歹妇p w 力册d2 门) f u i l c t i o n5 和f u l l m i o n6 这两个测试问题都是双目标优化问题，它们的决策 变量非线性相关满足毛= 恐= c o s ( 2 万一) ，p s 流形结构在决策空间是一维的余弦 曲线。这两个优化问题所需的理想聚类数目为2 。 f u n c t i o n7 ： x o ，1 】1 卜l ，1 】”_ 1 甩= 3 0 础石( x ) = _ + 号m ( 一“n ( 2 刀五) 2 ) 血n 胁m 一以( 卅南m ( _ _ s 砒2 圳2 ) 以= 眇西蒯删2 疗) 删以= 括p w 刀删2 刀) f u n c t i o n8 ： x 0 ，1 】1 卜1 ，l 】”一珂= 3 0 i i l i n 石( x ) = 而 幽石( x ) = g ( z ) 【l 一拓而】 g ( x ) = l + 9 ( ( 为一s i n ( 2 石毛) ) 2 ) 坳一1 ) l = 2 f u l l c t i o n7 和f u l l c t i o n8 这两个测试问题都是双目标优化问题。它们的决策 变量非线性相关满足吒= 恐= s i n ( 2 万一) ，p s 流形结构在决策空间是一维的正弦 曲线。这两个优化问题所需的理想聚类数目为3 。 硕l ：学位论文第二章带删除冗余聚类算子的r m m e d a f u n c t i o n9 ： x 【u ，l j 刀= j u m i n 石( x ) = c 。s ( 三五) c 。s ( 三而) ( 1 十g ( x ) ) m i n 胁) = 咧和s i n ( 三碳1 + g ( 砌 m i n 六( x ) = s i n ( 要五) ( 1 + g ( x ) ) g ( x ) = ( 葺一葺) 2 f u n c t i o n1 0o x 【0 ，1 】 刀= 3 0 m i n 石( x ) = c o s ( 等而) c o s ( 詈而) ( 1 + g ( x ) ) m i n 厶( x ) = c o s ( 等_ ) s i n ( 等吃) ( 1 + g ( x ) ) m i n 六( x ) = s i n ( 詈) ( 1 + g ( x ) ) 二 g ( x ) = ( 薯2 一而) 2 - 3 f u i l c t i o n9 和f u n c t i o n1 0 这两个测试问题都是三目标优化问题。f u n c t i o n9 的p s 流形结构在决策空间是二维矩形，所需的理想聚类数目为1 。f u i l c t i o n1 0 的p s 流形结构是二维曲面，所需的理想聚类数目为2 。 3 3 2 性能评价标准 多目标优化算法的评价方式是一个重要而复杂的问题，可以从两个方面进行 分析【l 】：1 ) 从理论上，用建立数学模型对其进行性能分析。2 ) 采用实验的方法 对算法进行测试和比较分析。进化算法是一种启发式优化算法，故而很难从理论 上分析比较，大多数学者都采用实验的方法进行比较分析。 多目标算法的性能通常可以从收敛性，解集分布性以及算法鲁棒性等三个方 面来评价。为了验证提出蹦m e d a r r c 0 在收敛性和分布性均优于 r m m e d a ，本章采用实验验证的方法，将提出的新算法与i 己m m e d a 进行比 较。实验中，采用了h v ( h y p e r v o l u m e ) 和i g d ( i n v e r t e dg e n e r a t i o n a ld i s t a n c e ) 两个m o e a s 常用的性能衡量指标【5 4 弼】。这两个指标都可以同时衡量算法的收敛 性和分布性。 硕士学位论文 第三章带删除冗余聚类算子的r m m e d a 设，为真实p a r e t o 前沿上均匀分布的解集，试验中对双目标和三目标优化 问题解集，的规模分别设为3 0 0 和8 0 0 ，p 为算法最终得到的非支配最优解集前 沿估计解集。 则h v 性能指标的计算方法如公式( 3 2 ) 所示： 坚婴9 8 ( 3 2 ) h v 妒) 其中h v ( q ) 表示解集q 和固定参考点构成的超体积，具体的计算方法可以 参考文献【5 6 1 ，c o l l ec o l l e 等指出如果算法得到的最终非支配解集h v 值占真实 p a r e t o 前沿解集h v 值百分之九十八以上，即可认为算法收敛。因此可将h v 性 能指标作为m o p s 被成功求解的准则，以此来估计算法收敛所需要的平均函数评 估次数。 i g d 是m o e a s 性能评价应用最广泛的衡量指标，公式( 3 3 ) 给出了i g d 值的计算方法： d ( ，尸) 1 0 肚钉 o 。3 其中，d ( ，p ) 表示点v 与点集p 中所有的点的最小欧几里得距离。假如i 尸i 足够大，那么集合j p 能较好地表示出p f 的分布，由公式( 3 3 ) 可知，i g d 值 为集合尸的每个点与最优解集p 中最近点的距离的平均值，它能够在一定程度 上同时衡量非支配解集的收敛性和分布性。i g d 值越小，则最优解集p 越逼近整 个p a r e t o 前沿。若i g d 值为o ，表明所有的解集非常均匀的分布在整个p a r e t o 前沿上。 3 3 3 实验结果与分析 本小节将i 己m m e d a i 汛c o 与r m m e d a 进行对比实验，来说明i 汛c 0 算 子的有效性。为了公平比较，两个算法均采用相同的参数，如表3 1 所示： 表3 1 算法参数设置 堡土堂垡堡壅 箜三童萱型堕! ! 金鏊耋笺王堕垦坚：坚垦旦垒 _ _ _ _ - - _ - _ _ _ - _ _ _ _ _ _ _ - _ - - _ _ _ _ _ - _ _ - _ _ _ _ - _ l _ _ i _ _ - _ _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ - _ _ - _ _ _ _ _ _ - - 。_ _ i - 。- - _ _ _ i _ _ 。_ - 。_ p 1 。一。一 表3 2l t m m e d a r r c o 与r m m e d a 的h v 值比较 测试函数 r m - m e d a r r c o r e m e d a 加速率 测试函数 加速翠 m e a i le r r o 仕s t dd e vm e 锄e r r o 肚s t dd e v “+ ”表示i t m m e d a i u 屺0 相对r m m e d a 在对应的测试问题上效果显著提高 表3 3i t m m e d a r r c o 与r m m e d a 的i g d 值比较 测试函数函数评估次数 r m - m e d a r r c 0 m e 锄e r r o 性s t dd e v r e m 匝d a m e 锄e r r 0 1 士s t dd e v 5 8 5 1 6 e0 3 士1 3 1 7 4 枷3 +1 0 7 9 0 e 0 2 士3 0 7 1 4 e - 0 3 7 骶e o 融3 4 7 1 1 曲3 +1 7 5 8 3 e 0 2 士1 0 8 1 7 e 0 2 1 2 5 7 8 枷2 士6 7 5 0 5 e - 0 3 +2 4 6 3 0 e 0 2 士1 4 5 3 4 e 0 2 8 0 4 1 8 e _ 0 3 士1 5 7 2 3 曲3 +2 8 7 6 4 e 0 2 士1 7 6 6 3 e - 0 2 8 1 l o l e 0 3 士3 7 1 9 8 e - 0 3 +3 3 0 8 3 e - 0 2 士2 1 2 3 l e - 0 2 77 9 1 6 8 e0 3 圭2 7 7 铷蝴+2 8 9 8 2 c - 0 2 士1 8 3 3 7