（计算机应用技术专业论文）异步分层并行演化算法及其在模糊聚类分析中的应用.pdf

摘要 演化计算是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜 索算法，能够在不要求函数连续、可微、单峰的情况下，找到问题的近似全局最 优解。基于这些优点，演化计算被广泛地应用于n p 和n p c 难题求解、神经网 络优化、多目标优化问题求解及其它众多领域。然而，随着问题规模和复杂程度 的不断提高，串行演化算法的搜索过程将成倍地增长，由此，并行演化计算成为 一个重要的研究方向。c a t d - p a z 将并行演化计算划分为四种类型，分别是主从 模型、粗粒度模型、细粒度模型和分层模型。这些模型通常在m p i 、p v m 和 o p e n m p 等并行编程环境下实现。 为了避免传统并彳亍演化算法中常见的“征服问题”和“无效问题”，克服过早收 敛，提高算法运行效率，本文提出了异步分层并行演化算法( a s y n c h r o n o u s h i e r a r c h i c a lp a r a l l e le v o l u t i o n a r y a l g o r i t h m ，a h p e a ) 。在算法中，对扩展的模糊 交叉算子进行改进，加入了适应值信息，提出基于标准化适应值的模糊交叉算子 ( f u z z yr e c o m b i n a t i o no p e r a t o rb a s e do ns t a n d a r d i z e df i t n e s s ，s f - f r o ) ，提高算法 的收敛速度。并在此基础上提出异构模型，为各子种群的交叉操作应用不同的全 局局部搜索度，指定相异的种群拓扑，以获取适当的选择压力。最后将各子种 群充分连接，构建异步迁移模型。本文提出的a h p e a 算法有效地解决了“征服 问题”和“无效问题”，避免了算法的过早收敛，提高了算法效率。 在仿真研究中，基于一组被广泛使用的测试问题集，从交叉算子s f f r o 、 异构模型和异步迁移三个方面对a h p e a 算法进行性能测试。实验结果表明： ( 1 ) s f f r o 由于引入了适应值信息，为算法指明了潜在的搜索方向及范围，能够 有效地提高算法的收敛速度；( 2 ) a m e a 算法在求解大型多峰值问题时采用异构 模型比采用同构模型具有更优越的性能；( 3 ) 在a h p e a 算法的各子种群间进行异 步迁移，无论从理论分析还是仿真研究的角度来看，都极大地提高了算法的性能。 作为a h p e a 算法的实际应用，本文在最后部分研究了f k c n 聚类分析的理 论基础，并将f k c n 聚类问题抽象为一个优化模型，应用a h p e a 算法对其进行 优化。实验结果显示，基于a h p e a 算法的动态聚类方法不仅能够准确地探测出 最佳聚类个数，而且误判率明显降低，具有更准确、更稳定的聚类效果。 关键词：演化计算；异步分层并行演化；动态模糊聚类 a b s t r a c t e v o l u t i o n a r yc o m p u t a t i o ni sg l o b a ls t o c h a s t i cs e a r c ha l g o r i t h mb a s e do nb i o l o g y e v o l u t i o nm e c h a n i s m , s u c h 髂n a t u r a ls e l e c t i o n ，h e r e d i t y , m u t a t i o na n de t c i ti s c a p a b l eo ff m d i n gt h ea p p r o x i m a t eg l o b a lo p t i m a r ns o l u t i o nw i t h o u tr e q u i r i n g c o n t i n u o u s ，d i f f e r e n t i a b l ea n du n i m o d a l ，t h u si th a sb e e nw i d e l yu s e di nn 啪c p r o b l e m s ，n e u r a l n e t w o r k o p t i m i z a t i o np r o b l e m 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 n p r o b l e m sa n dm a n yo t h e rf i e l d s h o w e v e r , a st h es c a l ea n dc o m p l e x i t yo fp r o b l e m s g r o w , t h es e a r c hp r o c e s so fs e q u e n t i a le v o l u t i o n a r ya l g o r i t h mw i l lb ep r o l o n g e d g e m i n a t e l y t h u s ，p a r a l l e le v o l u t i o n a r yc o m p u t a t i o nb e c o m e si m p o r t a n t c a n t 6 一p a z c l a s s i f i e di ti n t of o u rc a t e g o r i e s ，i n c l u d i n gm a s t e r - s l a v em o d e l ，c o a r s e - g r a i n e dm o d e l ， f i n e - g r a i n e dm o d e la n dh i e r a r c h i c a lm o d e l t h e ya l eu s u a l l yi m p l e m e n t e di nt h e p a r a l l e lp r o g r a m m i n ge n v i r o n m e n t s ，s u c ha sm p i ，p v m ，o p e n m pa n de t c i no r d e rt oa v o i d c o n q u e s t a n dn o n e f f e c t p r o b l e m s ，o v e r c o m ep r e m a t u r e c o n v e r g e n c e ，a n di m p r o v ee f f i c i e n c y , a na s y n c h r o n o u s h i e r a r c h i c a l p a r a l l e l e v o l u t i o n a r ya l g o d t h m ( a h p e a ) i sp r e s e n t e di nt h et h e s i s i na h p e a ，i n f o r m a t i o no f f i t n e s si sa d d e di n t ot h ee x t e n d e df u z z yr e c o m b i n a t i o no p e r a t o r , a n dan e wf u z z y r e c o m b i n a t i o no p e r a t o rb a s e do ns t a n d a r d i z e df i t n e s s ( s f - f r o ) i sp r o p o s e dt o a c c e l e r a t et h ec o n v e r g e n c e t h e n ，ah e t e r o g e n e o u sm o d e li sc o n s t r u c t e d d i f f e r e n t e x p l o r a t i o n e x p l o i t a t i o nd e g r e ei sa s s i g n e dt os f f r oo fe a c hs u b p o p u l a t i o nw h i c h h a sd i s t i n c t t o p o l o g i c a l s t r u c t u r et o g e ta p p r o p r i a t e s e l e c t i o n p r e s s f i n a l l y , s u b p o p u l a t i o n sa r ea d e q u a t e l yc o n n e c t e da n da l la s y n c h r o n o u sm i g r a t i o nm o d e li s c o n s t r u c t e d t h u s ，t h ec o n q u e s ta n dn o n e f f e c tp r o b l e m sa r es o l v e d ，p r e m a t u r e c o n v e r g e n c ei sa v o i d e da n de f f i c i e n c yi si m p r o v e d i ns i m u l a t i o nr e s e a r c h ，t h ep e r f o r m a n c eo fa h p e ai st e s t e dw i t has e to f r e p r e s e n t a t i v ep r o b l e m s i ti sp r o c e e d e di nt h r e es t a g e s ，n a m e l y , a n a l y s i so fs f - f r o ， h e t e r o g e n e o u sm o d e la n da s y n c h r o n o u sm i g r a t i o n t h ee x p e r i m e n t a lr e s u l t sl e a dt o t h r e ec o n c l u s i o n s ( 1 ) s f - f r ow o r k sw e l li ns p e e d i n gu pt h ec o n v e r g e n c ef o ri t s i n f o r m a t i o no ff i t n e s si n d i c a t e st h ep o t e n t i a ls e a r c hd i r e c t i o na n dr a n g e ( 2 ) t h e h e t e r o g e n e o u sm o d e lo u t p e t f o r n l st h eh o m o g e n e o u sm o d e li ns o l v i n gm a s s i v e l y m u l t i m o d a lp r o b l e m s ( 3 ) t h ea s y n c h r o n o u sm i g r a t i o nm o d e lo b v i o u s l yi m p r o v e st h e p e r f o r m a n c eo f e v o l u f i o n a r ya l g o r i t h mt h e o r e t i c a l l ya n de x p e r i m e n t a l l y a sa p r a c t i c a la p p l i c a t i o n ，i nt h el a s tp a r to f t h et h e s i s ，t h et h e o r yf o u n d a t i o nf o r f u z z yc l u s t e r i n ga n a l y s i si ss t u d i e da n dt h eo p t i m i z a t i o nm o d e lo ff k c nc l u s t e r i n g a n a l y s i si so p t i m i z e db ya h p e a t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a td y n a m i c f u z z yc l u s t e r i n ga n a l y s i sb a s e d0 i la h p e an o to n l yd e t e c tt h eb e s tc l u s t e r i n gn u m b e r , b u ta l s od e c r e a s et h em i s j u d g m e n tr a t ea n dh a sa d v a n t a g e si nv a l i d i t ya n ds t a b i l i t y k e yw o r d s ：e v o l u t i o n a r yc o m p u t a t i o n ；a s y n c h r o n o u sh i e r a r c h i c a lp a r a l l e l e v o l u t i o n a r ym g o r i t h m ；d y n a m i cf u z z yc l u s t e r i n ga n a l y s i s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：锻籁 一2 。衫年月工日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 f - l x 学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( 4 ) ( 请在以上相应括号内打“4 ”) 作者签名：级数 导师签名： e t 期：工嘭年多月2 日 e t 期：r z ，1 年绢- e t 第1 章绪论 1 1 演化计算研究概况 1 1 1 演化计算的发展历程 第1 章绪论 演化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 是一种基于自然选择和遗传变异 等生物进化机制的全局性概率搜索算法。它从选定的初始解出发，通过不断地 迭代，逐步改进当前解，直至最后搜索到最优解或满意解为止。与其它搜索技术 相比，演化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 具有以下特点：( 1 ) 搜索过程始 于一群初始点，而非单一初始点，这意味着它可以有效地跳出局部极值点；( 2 ) 在搜索过程中使用基于目标函数值的评价信息，这使其成为具有良好普适性和可 规模化的优化方法；( 3 ) 具有显著的隐式并行性，非常适合于大规模并行计算， 可用于解决复杂的适应性系统模拟和优化问题；( 4 ) 具有很强的鲁棒性，b 口在有 噪声的情况下，对同一问题多次求解，得到的结果是相似的。演化计算的这些优 点，使其成为求解优化问题的主要工具。 尽管到目前为止，演化计算的发展不过1 0 余年但其思想可以追踪到2 0 世 纪5 0 年代。一般认为，演化计算包括三大分支：( 1 ) 由美国密歇根大学j o n e h h o l l a n d 教授提出的遗传算法( g e n e t i ca l g o r i t h m ，g a ) 埘嘲；( 2 ) 由美国科学 家l a w r e n c ej f o g e l 等人提出的演化规划( e v o l u t i o n a r yp r o g r a m m i n g ， e p ) 叫嘲旧；( 3 ) 由德国科学家i n g or e c h e n b e r g 和h a n s p a u ls c h e w e f e l 提出的 演化策略( e v o l u t i o n a r ys t r a t e g i e s ，e s ) 7 1 8 1o 后来，k o z a 在遗传算法的基础上 又开创性地发展了演化计算的另一个分支：遗传程序设计( g e n e t i cp r o g r a m m i n g 6 p ) 随着演化计算研究和应用的不断深入与发展，1 9 8 5 年，在美国召开了第一 届遗传算法国际会议( i c g a ) ，这是遗传算法发展的重要里程碑。从1 9 9 9 年起， i c g a 和g p ( g e n e t i cp r o g r a m m i n gs o c i e t y ) 的系列会议合并为每年一次的遗传和 进化国际会议( g e c c o ) 。 1 9 9 4 年1 月，i e e e 神经网络委员会出版了第一本“演化计算”专集；1 9 9 4 异步分层并行演化算法及其在模糊聚类分析中的应用 年6 月，i e e e 神经网络委员会召开第一届“演化计算”国际学术会议( i e e ei c e ) 。 1 9 9 7 年，该委员会创办了i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 杂 志。从1 9 9 9 年开始，i e e ei c e c 与e p 的年会合并为演化计算国际会议( c e c ) ，每 年召开一次。 另外，美国m i t 出版社从1 9 9 3 年开始出版e v o l u t i o n a r yc o m p u t a t i o n 和 a d a p t i v eb e h a v i o r 杂志。并且，随着i n t e r n e t 技术的发展和普及应用，遗传 算法的有关研究单位建立了大量的专题网站。其中最为著名的是由美国海军人工 智能应用研究中心建立的g a _ a r e h i v e s 检索网站，它包括了世界范围内开展遗传 算法和演化计算研究的大学与机构，历年来可公开发表的论文和报告，有关国际 会议消息，典型应用案例与程序等。 1 1 2 演化计算的应用研究 ( i ) n p 与n p c 难题求解 演化计算在求解n p 与n p c 难题上具有广泛的应用。文献 1 0 提出了一种改 进遗传算法，用于求解基于市场机制的q o s 控制模型( n p 难题) ，与传统遗传算 法相比，加入了自适应预测器，同时在遗传操作中采用自适应遗传因子指导搜索 过程，实验证明该算法是快速有效的。文献 1 1 以达到无线网络系统利润最大化 为目标，提出了一个基于遗传算法的带宽适应方案，在算法复杂度大大低于最优 算法的同时，获得近似最优利润值，从而解决了这个n p 问题。另外，随着多媒 体业务的发展，多播技术应用日益广泛，带度约束的多播路由问题是一个n p c 问 题，很难求解。对此，文献 1 2 提出了一种双层遗传算法用于求解带度约束多播 路由问题。 ( 2 ) 神经网络优化 将演化算法与神经网络相结合，利用演化算法设计和训练神经网络的方法称 为演化神经网络。这方面的工作可分为连接权演化、拓扑结构演化、学习规则演 化以及拓扑结构和学习规则同时演化。后来，对连接权的演化扩展成为参数演化， 即同时演化连接权和阈值，相应地，拓扑结构与连接权的同时演化转变成为拓扑 结构与参数的同时演化。 在这一领域的应用中，文献 1 3 提出了一种基于遗传算法的b a y e s i a n 网络 2 第1 章绪论 结构和参数的求精算法，较有效地从不完备数据中求精b a y e s i a n 网络，改善了 b a y e s i a n 网络的性能。文献 1 4 在借鉴生理学中“选择性注意力模型”的基础 上，将遗传算法与误差放大的b p 学习算法进行了有机的融合，提出了基于注意 力模型的快速混合学习算法，有效地解决了传统b p 算法中由于初始权值选择的 随机性造成的训练失败问题，以及饱和区域引起的后期训练缓慢问题，在不增加 网络隐层节点数的情况下，显著地提高了网络的收敛精度和泛化能力。文献 1 5 提出了一类求解最大独立集问题( m i s ) 的混合型神经演化算法。该算法基于空间 剖分与“排除”策略，有效综合了神经网络快速收敛及遗传算法稳健全局搜索的 优点，与标准遗传算法和神经网络算法相比，显示了极高的全局优化性能与计算 效率。 ( 3 ) 多目标优化问题求解 近年来，多目标优化问题求解已成为演化计算的一个重要研究方向“。文献 1 7 在多个指标之间引入偏好信息，提出多目标遗传算法，使进化种群按协调模 型进行偏好排序，改变了传统的基于p a r e t o 优于关系来比较个体的优劣，典型 算例的数学解析和实验验证了其具有较好的收敛性与收敛速度。文献 1 8 将满足 不同约束的多搔路由选择过程转化为一个多目标优化问题，然后使用一种基于多 目标遗传算法的新型多播树计算方法，同时优化时延、丢包率和带宽利用率等参 数。实验结果表明，该方法能在有限进化代数内产生一组有效的非劣多播路由解， 结合多目标优化的遗传算法，克服了单目标路由优化的缺陷。文献 1 9 提出一种 多目标调和遗传算法，该算法被证明为能收敛至全局最优，对于目标数目较多的 优化问题，测试实验结果表明了这种新算法的有效性。 ( 4 ) 图像检测与处理 在图像检测领域，文献 2 0 提出了一种实现自动检测图像目标的形态滤波器 参数优化设计遗传学习算法。文献 2 1 则针对目前网络安全系统对于图像信息监 测能力不足的问题，提出了一种基于图像内容的智能网络安全监测系统模型。该 模型采用了信息反馈与知识辅助机制，以基于轮廓特征抽取与多智能体技术的图 像检索算法作为图像内容监测与分析模型的核心，采用基于遗传算法的安全性审 计机制实现对历史监测数据及规则的智能挖掘与审计，从而准确、实时地监测网 络中的图像信息，提高了网络系统的运行可靠性和安全性。 异步分层并行演化算法及其在模糊聚类分析中的应用 ( 5 ) 经济工程领域的应用 在调度优化问题求解中，文献 2 2 提出了一种基于遗传算法的网格资源任务 调度算法，文献 2 3 提出了一种应用遗传算法解决柔性制造系统调度优化问题的 新方法。在文献 2 4 中针对次序约束和资源约束的多模式项目调度问题提出了一 种病毒协同进化遗传算法，理论分析和实验结果表明，算法的搜索性能优于一般 的遗传算法，对于不同优化目标的多模式项目调度问题，可以同时求得个满足 次序约束的项目活动最优调度顺序和满足资源约束的最优资源模式。 ( 6 ) 其它领域 文献 2 5 应用遗传算法对移动代理从服务提供商到内容提供商的路径进行 了最优化求解。文献 2 6 提出了种新的实现模拟集成电路模块布局的遗传算 法，多种电路的测试结果表明，该算法性能优于传统的模拟退火算法，布局结果 与手工布局相仿，设计效率得到显著提高。文献 2 7 提出了一个基于遗传算法的 二维不规则形状物体的自动最优布局问题求解方法，并将它应用到服装计算机辅 助设计中去，实验结果表明，所提出的方法能较好地解决最优布局问题。文献 2 8 提出了一种基于通孔数最小化的多层通道布线算法，克服了传统通孔优化算法中 原始布线对优化结果的不利影响，使通孔的优化达到很好的效果。文献 2 9 提出 了基于分布式遗传算法的共享树组播路由算法，利用它可以实现在给定网络和组 播需求的情况下，在组成员间寻找动态的组播树，使该树覆盖所有的成员，并约 束网络费用达到最小，进而解决树状路由的建立以及动态维护等问题。 1 2 并行演化计算研究现状 演化计算作为一种基于生物界自然选择和遗传原理的高效搜索技术，一般来 说，可以在合理的计算时间内发现问题的满意最优解，但是随着问题规模和复杂 程度的不断提高，串行演化算法( s e q u e n t i a le a ，s e a ) 的搜索过程将会成倍地延 长。因此，很多专家一直致力于提高演化算法的搜索速度，其中一个重要的研究 方向就是并行演化算法( p a r a l l e le a ，p e a ) 。 并行演化算法的基本思想是，将整个任务分解为若干子任务，并同时采用一 组处理器分别求解各个子任务。这种分治策略也可以应用于演化算法的并行化设 计。根据c a n t d p a z 的归纳，并行演化算法可分为四种类型，即主从式并行演 4 第1 章绪论 化算法( m a s t e r s l a v ep e a ，m s p e a ) 、粗粒度并行演化算法( c o a r s e g r a i n e dp e a c g p e a ) 、细粒度并行演化算法( f i n e g r a i n e dp e a ，f g - p e a ) 和分层并行演化算 法( h i e r a r c h i c a lp e a ，h p e a ) 。 1 2 1 主从式并行演化算法( m s - p e a ) m s p e a 可以广泛地适应于各种体系结构的计算机，如对称或非对称多处理 系统、集群系统、大规模并行处理系统和t r a n s p u t e r 并行处理机等。在演化过 程中，m s p e a 采用单一进化种群，主处理器负责存储种群和完成选择、交叉、 变异等操作，而从处理器负责个体适应值的计算，如图1 2 1 所示。由于每个个 体适应值的计算与其他个体无关，当这一计算过程比较复杂、费时的时候，主从 式并行演化算法可以取得良好的加速比。 主处理器 从处理器 图1 2 1m s - p e a 的拓扑结构 如果主处理器在获得从处理器端全部个体适应值之前处于等待状态，则称为 同步m s - p e a ，其搜索行为及性能与s e a 一样，只是计算速度加快了。若从处理 器的运行速率不完全一致，主处理器不必等待全部个体适应值计算完毕，接收到 部份个体适应值后即开始遗传操作并生成新的个体，则其行为与s e a 不同，称为 异步m s - p e a 。一般在不特别说明的情况下，m s p e a 即为同步运行方式。 f o g a r t y 和h u a n g 采用了面向并行计算的基于微处理器的一组t r a n s p u t e r ， 设计了各种互连拓扑结构，并针对特定问题进行了实验计算，取得了良好的加速 比，同时证明了m s - p e a 的性能与t r a n s p u t e r 的互连拓扑结构不存在强依赖。“。 a b r a m s o n 和a b e l a 在一台配置1 6 个c p u 的共享内存结构的e n c o r em u l t i m a x 计 算机上，对中学课程时间表进行了优化计算。”，由于关键计算程序的非并行化， m s p e a 的性能提高非常有限。而后，a b r a m s o n 等人采用一台配置了1 2 8 个c p u 异步分层并行演化算法及其在模糊聚类分析中的应用 的分布式内存结构的f u j i t s ua p l 0 0 0 ( 8 个结点) 计算机，计算实例改为火车时刻 表的优化，并重新改进了程序代码，从单结点到2 个结点的m s p e a 获得了显著 的加速比。随着结点数量的增多，通信任务负载增加，加速比的提高程度显著下 降啪3 。另外，h a u s e r 和m a n n e r 等人在各种体系结构的并行计算机上进行了大量 实验，对于特定问题，所获得的加速比不完全一致，主要是不同体系结构的并行 计算机在多任务管理的效率上存在着差异“1 。 1 2 2 粗粒度并行演化算法( o g p e a ) c 6 一p e a 可以视为s g a 的简单扩展，算法调整上非常简单，可以在较多计算环 境中实现，借助于m p i 或者p v m 在m p p 计算平台上就可以运行大型复杂多种群 p e a ，甚至在由若干台配置较高的p c 组成的局域网上，也可以完成一定规模优化 问题的多种群p e a 求解。 c 6 一p e a 的结构设计比较复杂，一般由若干个子种群组成，如图1 2 2 所示。 子种群进化过程中以某种方式交换个体，称为个体迁移，并由一组参数进行控制。 c g p e a 的应用比较多，具体结构形式多种多样，通常要求结点计算量与通信计 算量的比值很高，适应于内存分布式的m i m d 计算机，一般也称为分布式p e a 或 多种群p e a 。若子种群之间不存在个体迁移，在遗传学上称之为孤岛模型( i s l a n d m o d e l ) ，相应的p e a 称为孤岛p e a 。 g r o s s o 是最早专门从事c g p e a 研究学者之一。”，主要分析同时演化的子种 群间的交互影响。在研究中，g r o s s o 采用了双倍染色体位串，5 个子种群之间按 照固定的迁移率交换个体。研究发现，子种群平均适应值的提高速度远远高于 s g a 的单一大种群。这说明小种群中优良基因的传播速度快于大种群。然而，小 种群的收敛速度或演化停滞要早于大种群，当子种群间不进行个体迁移时，获得 的最优解劣于大种群。采用较小的个体迁移率，c g p e a 的性能与孤岛p e a 相比， 不存在显著改善。当个体迁移率提高到一定程度时，c 6 一p e a 的性能与s e a 基本 一致。因此，6 r o s s 认为关于c 6 一p e a 的个体迁移率存在一个阈值，并直接影响 c g p e a 的性能。 6 第1 章绪论 图1 2 2c g - p e a 的拓扑结构 p e t t y 、l e u z e 和g r e f e n s t e t t e 设计了这样一种迁移策略”，即将每一代 中某个子种群的最佳个体发送到邻接的子种群中，旨在实现各个子种群中最佳个 体的组合，同样发现该种迁移策略下的c g p e a 达到了单一种群s e a 的性能水平。 到目前为止，大多数关于c g p e a 的研究结论还是实验性的。s t a r k w e a t h e r 、 w h i t l e y 和m a t h i a s 认为，孤岛多种群p e a 可以同时搜索到多个局部最优解；若 适应值函数是线性可分离的，适当迁移率的多种群p e a 可以更快地发现全局最优 解，或者搜索到比单种群s g a 更好的解一。 c a n t 吐一p a z 和g o l d b e r g 对个体迁移策略进行了理论研究m ”1 ，采用完全互连 的多种群通信拓扑结构，针对特定函数的多种群p e a 求解，并给出了各代当前最 佳个体所代表的解质量的预测公式。当各子种群收敛以后，实施最佳个体的迁移， 使种群的多样性得以恢复，可以克服过早收敛问题。c a n t 吐一p a z 和g o l d b e r g 认 为，当个体迁移发生太早，所传播的仅仅是低阶的模式，对各个子种群的搜索影 响较小，而且浪费通信时间， m a r i n “4 等人在l a n + p v m 环境上设置了一个子种群，专门负责接收各子种群 发送的最佳个体，将它们广播到其它子种群，并替代各子种群中的最差个体。实 验结果表明，当结点数量比较少时，c g p e a 可以获得线性加速比。 多种群之间通信的拓扑结构也是一个重要的影响因素。若多种群之间完全互 连，即每个子种群的迁移个体均可以按广播方式发送到其它子种群；或者子种群 之间通信半径很小，优良个体可以快速充满全部子种群，这称为紧密互连。若多 种群之间非完全互连，每个子种群的迁移个体只能向其它邻接子种群发送，或者 7 异步分层并行演化算法及其在模糊聚类分析中的应用 子种群之间通信半径较大，优良个体难以快速充满全部予种群，整个种群往往可 以同时搜索到多个解，则称为松散互连。另外，该拓扑结构也直接关系到通信时 间开销。比如，紧密互连型拓扑结构也需要最大的通信成本。 一般来讲，c g p e a 在运行过程中采用固定的通信拓扑结构，该拓扑结构不 随着演化而改变，称为静态拓扑结构。同时，多种群的通信拓扑结构与计算平台 的拓扑体系结构相一致。然而，也有c g p e a 采用动态通信拓扑结构，即某子种 群迁移个体的接收地不是预先确定的，而是每代发送到满足特定条件的一些子种 群。这些条件可以是接收地子种群的多样性，或者是迁移个体源子种群与接收地 子种群之间，在编码空间上的平均h a m m i n g 距离。 c g p e a 在同构的并行硬件平台上运行时，同步与异步模型具有相似的数值 性能。文献 4 3 采用一整套实验比较分布式遗传算法的同步与异步模型，且在相 同问题上，采用相同参数分别运行同步与异步模型。结果显示，在实时方面，异 步模型的性能超越了其相应的同步模型。当大量处理器被使用时，异步实施无助 于降低通信负载“。根据a l b a 和t o m a s s i n i 的大量研究发现“：( 1 ) 异步模型所 需的执行时间较短，受迁移频率的影响较少；( 2 ) 异步模型更适合于复杂领域， 在分布式并行遗传算法应用上，性能优于其相应的同步模型；( 3 ) 对于所测试的 算法，异步模型无论从运行时间还是加速比上都优于同步模型。 文献：4 6 提出了一种新型、高效的函数优化异步并行演化算法，并应用超级 巨型并行计算机在p v m 平台上实现，解决了一些高难度的大型优化问题，其中包 括一个超高维的非线性规划问题b u m p 问题：文献 4 7 以常微分方程组的演 化建模问题为主要研究对象，设计了分布式异步并行演化算法，并以1 2 8 台 p i i l 5 0 0 微机通过l o m b p s 的以太网互联而成的机群系统作为模拟实验环境，进行 了大规模的并行实验，系统地测试了算法中一些重要的并行控制参数。 1 2 3 细粒度并行演化算法( f 奇- p e a ) f g p e a 在设计上与大规模并行计算机的体系结构相适应，通常在s i m d 机器 上并行实现，也可以在单处理器及m i m d 机器上实现。该模型采用符合特定空间 结构模式的单一种群，选择和交叉操作在由邻接处理器构成的邻域内的一组个体 上进行。由于不同邻域相互交叉，仍然可以实现整个种群上个体信息的交换。最 第1 章绪论 理想的模式是每个处理器仅处理一个个体。 在f g p e a 中，最常采用的种群拓扑结构是低维超环面栅格结构( 通常为二 维) ，所有个体均匀地分布在这些栅格中，各自占据一个栅格，如图1 2 3 所示。 因此这种模型也称为“细胞状模型” 4 8 e 算法在执行过程中，同步地评估所有个 体的适应值，而仅在邻域内进行选择、交叉等遗传操作。二维超环面栅格上定义 的邻域模型一般有5 种，如图1 _ 2 4 所示。 o o o o o o o o o o o o o o o o o o o o l i n e _ m l5 f = 5 l ooooo o o o o o o o o o o ooooo ooooo 图1 2 3f g - p e a 的拓扑结构 o o o o o o o o o o o o o o o o l e a r9 i 鸸 o o o o o o o o o o o o o o o o c o m p a c t9 ( = 9 l o o o o o o o o o o o o c o m p a c t l 3 ( n = 1 3 1 图1 2 4 邻居关系模型 c o m p a c t 2 5 ( n = 2 5 ) 线形( l i n e a r ) 邻居关系定义为从中心个体沿着固定轴方向( 东、西、南、北) n 步内能遍历的所有个体；而紧密( c o m p a c t ) 邻居关系定义为最靠近中心个体的n 1 个个体。通常在这些邻居关系模型中，每个邻域仅由少量个体构成，以减少在 s i 岫机器上的通信开销或单一处理器上的执行时间，其中以l i n e a r5 ，即n e w s ( n o r t h e a s t w e s t - s o u t h ) 模型最简单常用。根据s h a p i r o 和n a v e t t a 的测试结 果，n e w s 模型具有较好的性能“。 鉴于种群拓扑及邻居关系模型种类繁多，需要一种共同的量化标准来衡量， e m - i q u ea l b a 和j o s 6m t r o y a 在文献 4 5 中提出了以“半径”来量化这种拓扑 结构。认为这种拓扑结构的半径与n + 个点围绕着中心( x ，y ) 散布为环形结构的 半径是等价的，半径r a d 定义如下： 9 异步分层并行演化算法及其在模糊聚类分析中的应用 悟_ 二了_ 二 f ( t 一工) 2 + ( y 。一y ) 2 1 生产一 ，其中， 一y ， ，y = 牛 n 上式定义不仅描述了种群拓扑结构的半径，而且也能够求出邻域的半径，从 而将种群拓扑结构与邻域的关系量化为二者半径的比率r a t i o ，如下式所示： r ( 1 d 睁b o l , h o o d r a t i o = 二= 。一 r a d r o m l 。g ， 其中r a d n e i g h “为邻域半径，r a d r o m l 。，为种群拓扑半径。 文献 5 0 证明，邻域与种群拓扑之间的关系决定了f g p e a 的选择压力，即 优良个体在种群中的传播速度。因此，采用相同选择方法时，具有相似r a t i o 的 算法显示出了相似的选择压力；减小r a t i o ，则意味着减小种群的全局选择压力， 从而促进全局搜索。当采用同样的个体数量来解决同一问题时，栅格结构变得越 细长，拓扑半径就会越大。而如果邻域保持大小、形状不变，则它们的比率将随 之变小，从而提供更高的多样性，在复杂问题中改进解的质量。 虽然由于f g p e a 与其运行机器具有强相关性，且需要特殊硬件( 如连接机和 细胞状自动机) ，一直以来并没有受到与其它p e a 一样的重视，导致没有太多成 果可借鉴，但它的重要性在逐渐提高。究其原因有如下几点：首先，f g - p e a 被赋予了一个固有的空间结构，允许通过更多的迭代来获取适应性和基因型的多 样性；其次，研究证实，f g p e a 在处理复杂优化任务时优于其它的演化算法模 型。“1 ”3 ，如训练神经网络；最后，该模型与细胞自动机具有很大的相似性，其 潜在的应用，以及对局部搜索嵌入算法的适用性使得它极具研究价值。 1 2 4 分层并行演化算法( h p 队) 为了取得更好的并行计算效果，也可以将以上三种p e a 结合在一起，构成 f p e a ，也称为混合并行演化算法或层次性并行演化算法。h p e a 旨在将各种p e a 的优点集中在一起，同时也使得其搜索行为分析更为复杂。以两种相同或不同的 并行演化模型构成的两层p e a 为例，一般采用以下三种基本的拓扑结构。 ( 1 ) c g p e a 与f g p 队的结合 在这种混合模型中，上层为环形拓扑结构的c g p e a ，下层每个子种群采用 l o 。基告h = 一x 第1 章绪论 超环面栅格拓扑结构的f g - p e a ，如图1 2 5 所示。 图1 2 5 由c o p e a 与f g p e a 结合构成的l 珀e a g o r g e s s c h l e u t e r 设计了这种类型的h p e a ，称为a s p a r a g o s 9 6 ，用于求解 旅行商问题”1 。当子种群演化停滞时，向其它邻接子种群发送所获得的最佳个体， 或者接收来自邻接子种群的迁移个体。当全部子种群均收敛时，从各子种群中挑 选出最佳个体和次佳个体组成单一种群，实施s e a 演化，以期搜索到更好的全局 最优解。 l i n 、g o o d m a n 和p u n c h 以车间作业调度优化为基准测试问题，将上述h p e a 与s e a 、c g p e a 和f g p 队进行了详细的实验比较分析嘲1 。实验结果表明，s e a 性能最差；增加c g - p e a 中子种群的个数比增大种群规模更有利于算法性能的改 善；h p e a 的搜索性能优于f g - p e a 的性能。 ( 2 ) c g p e a 与m s - p e a 的结合 该h p e a 模型上层为环形拓扑结构的c g - p e a ，下层予种群采用m s - p e a 进行 演化，如图1 2 6 所示。 图1 2 6 由c g - p e a 和m s - p e a 结合构成的e i p e a b i a n c h i n i 和b r o w n 将这种h p e a 与m s p e a 、c g p e a 进行了实验比较分析陆1 ， 异步分层并行演化算法及其在模糊聚类分析中的应用 结果表明，对于目标函数计算需要花费较长时间的优化问题，在获得同样质量的 最优解的情况下，这种h p e a 比其他