（电机与电器专业论文）并行遗传算法及其在mri永磁主磁体优化设计中的应用.pdf

沈阳工业大学硕士学位论文 p a r a l l e lg e n e t i ca l g o r i t h m sa n di t sa p p l i c a t i o nt ot h eo p t i m i z a t i o n d e s i g no f m a i nm a g n e ta s s e m b l yo f m r i a b s t r a c t n u c l e a rm a g n e t i cl e s o n a n c ei n l a g i n go rm a g n e t i cr e s o n a n c ei m a g i n g0 v i r i ) i sak i n do f i m a g i n gt e c h n o l o g yo fb i o l o g i c a lm a g n e t i cn u c l e a rs p i na n dt h em o s td e v e l o p i n gi m a g i n g t e c h n o l o g y , w h i c hd e p e n d e do nt h ed e v e l o p m e n to fc o m p u t e r ，e l e c 缸oa n ds u p e r c o n d u c t i v i t y m a i nm a g n e tb o d yi so n eo ft h em a i np a r t so fm r i rc a np r o d u c tm a g n e t i cf i e l dn e e d e db y m r i t h ed e v i c eo f m r l a d o p t sp e r m a n e n tm a g n e tm a i nm a g n e ti nt h i sp a p e r o p t i m i z a t i o nd e s i g no fm a i nm a g n e tb e l o n g st oi n v e r s i o np r o b l e mo fe l e c t r o m a g n e t i s m f i e l d t h ec a l c u l a t i n gt i m eo f i n v e r s i o np r o b l e mo f e l e c t r o m a g n e t i s mf i e l di sv e r yl o n g u s i n g p a r a l l e ld i s p o s a lt e c h n o l o g yc a l lr e d u c ec o m p u t i n gt i m ee f f e c t i v e l y w i t ht h ed e v e l o p m e n t o f p a r a l l e ld i s p o s a lt e c h n o l o g y , p a r a l l e l w o r k s t a t i o nh a db c c ：0 m em a i n s t r e a mo fp a r a l l e l c a l c u l a t i n g i n h e r e n tp a r a l l e ln a t u l eo fg e n e t i ca l g o r i t h ma n df a s td e v e l o p m e n to fp a r a l l e l c o m p u t e r s ，s om a n y s c i e n t i s t sb e g i ns t u d y i n gp a r a l l e lp r o b l e mo f g e n e t i ca l g o r i t h m t h i sp a p e ri n t r o d u c e sp a r a l l e lg e n e t i ca l g o r i t h mt oo p t i m i z et h em a i nm a g n e to fm r i f i r s t , s i m p l ya n a l y z eg e n e t i ca l g o r i t h ma n di t sr u n n i n gm e c h a n i s m c h n n g m gg e n e t i c a l g o r i t h mt op a r a l l e lm o d ea n df o r m i n gp a r a l l e lg e n e t i ca l g o r i t h m i n t r o d u c em o d e so f p a r a l l e lg e n e t i ca l g o r i t h m b e c a u s et h i sp a p e ra d o p t st h i c kg r a n u l a r i t ym o d e ，m t r o d l l c et l l i c k g r a n u l a r i t ym o d em o s t l y s e c o n d , a n a l y z i n gb a s i ct h e o r yo f m r i a n d a n a l y z i n g t h ei n f l u e n c eo f p o l es h a p eo f m r i i ni m a g i n ga r e a t h i sp a p e ro p t i m i z e st h es i z eo fp o l es h a p e u s i n gp a r a l l e lg e n e t i c a l g o r i t h ma n d f i n i t ee l e m e n ta n a l y s i s ，m a k eo p t i m i z a t i o nr e a l i z eb yo n ec o m p u t e r 1 1 l i r d i n t r o d u d n gp a r a l l e ls o f t w a r ec a l l e dp v m ，w h i c hc a nh e l pa c t u a l i z i n gp a r a l l e l g e n e t i ca l g o r i t h m p a r a l l e lv i r t u a lm a c h i n ea l s oc a l l e dp v i v lc a nd i s t r i b u t ec o m p u t i n g i ti sa s o f t w - ep a c k a g e u s i n gi t 锄c h a n g ec o m p u t e r st oab i gp a r a l l e lc o m p u t e rb yn e t w o r k i f d o i n gt h i s ，w ec a l ls p e n dl i t t l et i m ec o m p l e t i n gt a s ko fp a r a l l e lo p t i m i z a t i o n , t h i sp a p e r a d o p t sp v m t or e a l i z ep a r a l l e lg e n e t i ca l g o r i t h m s p a r a l l e lf l a tr o o fi sm a d el 巾o fp a r a l l e l v i r t u a lm a c h i n eo , v r v oa n dr e m o t es h e l ld a e m o n ( r s h d 烈t ) b a s i n gt h i sp a r a l l e lf l a tr o o f , i i i 并行遗传算法及其在m r i 永磁主磁体优化设计中的应用 w ec a na c c o m p l i s ht h et a s ko f p a r a l l e lo p t i m i z a t i o nb yu s i n gp r o g r a mo f g e n e t i ca l g o r i t h m s r e s u l t si n d i c a t et h a tu s i n gp a r a l l e lg e n e t i ca l g o r i t h mc a ne n h a n c ec a l c u l a t i n gs p e e da n d r e d u c ec a l c u l a t i n gt i m e a tl a s t ，d e f i c i e n c yi s g i v e na b o u tt h ew h o l ep a p e ra n dt h ef u r t h e rr e s e a r c h e sa r e p r o p o s e d k e yw o r d s ：n u c l e a rm a g n e t i cr e s o n a n c ei m a g i n g ( m r i ) ，m a i nm a g n e t ，p a r a l l e lg e n e t i c a l g o r i t h m s ，p a r a l l e lv i r t u a lm a c h i n e i v 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：豇纽 导师签名： 牲日期： 沈阳工业大学硕士学位论文 1 绪论 1 1 课题的来源与意义 早在3 0 多年前，一些研究者们便产生了模拟生物进化的思想，这样就出现了各种 用于优化问题的算法。三十多年来的研究和应用证明了这些算法的鲁棒性【1 1 和有效性。 这一类基于生物进化机制的随机搜索算法就是进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称 e a s ) 。 进化计算历史上有四个主要的分支：遗传算法、进化策略、进化程序设计和遗传程 序设计【。虽然这几个分支在算法实现方面具有一些细微的差别，但它们都是借助生物 进化的思想和原理来解决问题的。 遗传算法( g e n e t i ca l g o r i t h m ) ，简称g a 算法，是美国密西根大学教授j o l l i lh o l l a n d 在7 0 年代提出的【3 1 。传统的优化搜索算法通常采用梯度技术，使搜索朝着梯度下降最快 的方向进行。但是对于多峰优化问题，通常只能得到局部极值，而不能求到全局最优解。 遗传算法是一种与传统优化算法完全不同的优化搜索算法。该算法是从一个种群开始， 利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。理论己 证明，对于每代中保留当代最优解的g a 是收敛的算法，即随着g a 中遗传代数不断增 加，目前保留的最好解将逐渐接近全局最优解1 4 。 虽然遗传算法通常能取得较好的计算结果，但是在对电磁场计算的逆问题等计算时 间冗长的计算问题通常会花费大量的计算时间。为了提高计算速度。减少计算时间。很 多学者开始利用并行计算的方法来解决问题。 众所周知，有诸多因素导致了并行处理技术的发展，如高性价比、可伸缩性、以及 容错功能等等。在过去由于处理器价格昂贵，通信技术不成熟，以及并行软件的不完善， 使得并行处理技术进展缓慢。然而，随着八十年代初各种1 6 位、3 2 位、“位甚至目前 的1 2 8 位微处理器的不断问世、高速网络通信技术的不断成熟、以及软件工具的改善， 给并行处理技术注入了迅速发展的活力，人们已认识到并行处理技术是实现高性能计算 的必由之路 5 1 。经过三十多年的研究与发展，并行处理技术已牢牢地确定了它在高科技 关键技术中的地位。 并行遗传算法及其在m r i 永磁主磁体优化设计中的应用 随着并行处理技术的发展，在并行领域中，并行体系结构、并行软件和并行算法三 者缺一不可，而并行算法则是其中的核心和瓶颈技术【6 1 。 随着现代科学技术的发展，大规模数据处理向人们提出了新的挑战。为了解决诸如 此类的问题，大规模巨型机的研制被提上了日程。并行计算机的出现为成功地解决这些 问题开辟了一个可行的途径嘲。 今天，大规模并行计算机已经被用在国防、航天和科学研究等各个领域。除了用于 数学计算以外，在复杂的事务处理、逻辑推理和符号处理中也得到了广泛的应用。而且， 后面几种应用比单纯的数学计算还要广泛。大规模并行计算机的具体应用有地震数据处 理、数值天气预报、c a d 图像处理等。 在研制上述并行和分布计算系统的过程中，人们逐渐认识到，系统的规模可伸缩性 ( s e a a b i l i t y ) 和可编程性( p r o g r a m m a b i l i t y ) 已成为促使这两者进一步发展的关键问题。 系统规模只有在具有可伸缩性的前提下，并行计算机系统才可能以尽可能低的成本向用 户提供尽可能高的性能。虽然专用的m p p 系统一般都是基于市场上的微处理器，但支 持通信和同步的机制却是高性能超级计算机专用的部件，这使得m p p 系统性能非常卓 越但价格也十分昂贵。另外，由于高性能工作站和高性能网络设旌的出现，为工作站机 群的发展提供了新的契机。并行工作站机群已经进入并行计算和分布式计算技术发展的 主流。 由于遗传算法固有的并行性和大规模并行计算机的快速发展，促使许多研究者开始 研究遗传算法的并行化问题。用多台计算机计算不同个体的适应值，再通过计算机之间 的相互通讯，使适应值高的个体保留到下一代而除去下一代中适应值低的个体，这样就 可以使收敛的速度加快。 核磁共振( n u c l e a rm a g n e t i cr e s o n a n c e ，n m r ) 成像，现称为磁共振成像( m a g n e t i c l e x o n a n c ei m a g i n g ，m r i ) 。从原理的发现到目前临床各种先进成像技术的应用，是基 于科学家们对原子结构的不断认识。1 9 2 4 年p a u l i 发现电子除对原子核绕行外，还可高 速自旋，有角动量和磁矩。核磁共振现象在1 9 4 6 年被美国斯福坦大学f b l o c h 和哈佛大 学em p u r c e l l 分别发现，到7 0 年代初期由r d a m a d i a n 和p l a u t e r b u r 提出核磁共 振成像方法，应用到医用断层和分光测上用。早期m r i 的实验及8 0 年代磁共振在医学 一2 一 沈阳工业大学硕士学位论文 上的应用，使m r 成为一个具有高级诊断技术标准的现代化诊断系统。磁共振成像技 术是随着计算机、电子、超导技术发展起来的一种生物磁学和白旋成像技术。它可以作 为一种对人体无创、无电离辐射的诊断工具，是目前公认的最具有发展空间的成像技术 嘲。 主磁体是磁共振成像装置的主要部件之一。对主磁体的设计要求是，它在成像区产 生的磁场应具有很高的均匀度。主磁体的优化设计属于电磁场的逆问题，对于这类问题， 通常要进行几千次甚至几万次的目标函数评价，而每一次的目标函数评价都需要进行一 次高精度的电磁场分析。因此，电磁场逆问题的计算时间是很冗长的。采用并行遗传算 法进行计算无疑是一个很好的解决方法，它可以有效地缩短电磁场逆问题的计算时间。 1 2 遗传算法的发展状况 自从系统地提出遗传算法的完整结构和理论以来，众多学者一直致力于推动遗传算法 的发展，对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探索，引入 了动态策略和自适应策略以改善遗产算法的性能，提出了各种变形的遗产算法。其基本途 径概括起来有一下几个方面： ( 1 ) 传算法的组成成分或使用技术，如选用优化控制参数、适合问题特性的编码 技术等； ( 2 ) 混合遗产算法； ( 3 ) 动态自适应技术，在迸化过程中调整算法控制参数和编码粒度： ( 4 ) 非标准的遗传操作算子： ( 5 ) 并行遗传算法网。 遗传算法是人们对自然进化过程的机器模拟，它分别使用选择、交叉和变异等遗传 操作来模拟自然进化过程中的自然选择、交配和基因突变以达到求解组合搜索、优化和 机器学习等问题的目的。 由于遗传算法的迅猛发展，它将发展并应用在许多领域上。目前遗传算法所涉及的 主要领域有函数优化、组合优化、信号处理、生产调度问题、自动控制、机器人智能控 制、图像处理和模式识别、人工生命、遗传程序设计、机器学习等 4 1 。 并行遗传算法及其在m r 永磁主磁体优化设计中的应用 1 3 并行遗传算法的国内外发展状况 虽然在许多领域成功地应用遗传算法，通常能在合理的时间内找到满意解，但随着 求解问题的复杂性及难度的增加，提高g a 的运行速度便显得尤为突出，采用并行遗传 算法( p g a ) 是提高搜索效率的方法之一。 近年来，对于并行遗传算法( p a r a l l e lg e n e t i ca l g o r i t h m ，简称p g a ) 的理论研究和应 用研究，许多计算机科学家做了大量的工作并取得了一定的成果。 在国外，许多科学家的研究工作都是在大型计算机的基础上展开的研究工作。 g - r c f e n s t e t t e 全面研究了g a 并行实现的结构问题，提出把p g a 按结构形式分为同步主 从式、半同步主从式、非同步分布式及网络式等；m u h l e n b e i 等用p o a 在由6 4 个处理 器构成的并行机上求出了4 0 0 维r a s t d g i n 多模型函数的全局最小解 t 0 1 ；s p i e s s e n s 等也 实现了g a 的大规模并行【l l 】；p o t h s 等提出了基于迁移和人工选择的g a ，利用四组群体 进行并行进化等等【1 2 1 。 在国内，也有许多计算机学者从事p g a 的研究，对p g a 的深入研究和应用做了大 量工作。由于国内广大的科研机构和用户没有大型机而只有网络环境这特点，因而基 于网络的分布式p g a 的研究是国内p g a 研究的主要方向 1 3 1 。本文的研究内容就是基于 网络的分布式p g a 的优化问题。 尽管并行g a 的研究已经取得了很大进步，然而，还有大量的前沿方向需要我们进 一步去研究。例如，如何处理动态函数优化问题，并行g a 的理论研究，并行g a 的主 要参数对结果的影响，并行o a 的收敛性如何，并行g a 与其他优化算法的比较，所有 这些都要我们今后去解决。总的来说，并行g a 有着良好的发展和应用前景。 1 4g r i 的国内外发展状况 m r j 技术的发展与其它医学新技术的发展一样也经历了一个漫长的发展过程。 在1 9 4 6 年美国科学家f e l i xb l o t c h 等发现物质磁共振现象之后，1 9 7 2 年美国科学家 d a m a d i a n 申请了磁共振扫描用于人体思路的专利 1 4 , 1 5 l ，1 9 7 4 年英国科学家研制成功 组织内磁共振光谱仪，1 9 8 6 年第一台磁共振扫描仪研制成功，1 9 8 7 年实现心脏循环 磁共振实时成像，1 9 9 3 年用于研究与测量人类大脑的磁共振功能成像仪f m r i 问世， 1 9 9 9 年移动式m 砌扫描仪投入商业生产。耳前医用磁共振成像设备由于其高分辨率 4 一 沈阳工业大学硕士学位论文 和对人体无刨伤、无电离辐射，已作为诊断工具广泛应用于临床，在发达国家已成为人 群体检的首选工具 1 6 , 1 7 】。 主磁体可以采用常规磁体、超导磁体，也可以采用永磁磁体。常规磁体需要消耗较 大电能来产生磁场，其运行费用高，稳定性也不太好，正逐渐被淘汰。超导磁体具有高 磁场强度、高磁场均匀度、高磁场稳定性等一系列特点，虽然造价很高，而且较难维护。 永磁磁体价格相对便宜、维护简便、无需激磁电源且杂散场较弱，但产生磁场的场强有 限，磁场均匀度较差，相对均匀区域也较小。 目前我国m 市场被美国、荷兰、德国和日本几家外资企业占据了大部分，国内 虽有若干m r i 生产企业，但总体实力远不如国外公司。随着我国经济建设和科技事业 的发展，面对严峻的市场竞争形势，我国需要通过自主研制包括m r i 在内的精密医疗 仪器来带动中国医疗器械行业的振兴和满足日益发展的社会需要。 1 。5 磁体优化设计的研究状况 磁体设计问题属于计算电磁学的逆问题，是一种特殊形式的优化设计，它是从上世 纪9 0 年代发展起来的，目前是计算电磁学研究的热点问题之一。 这种逆问题需要两个工具，其一是分析的工具，即方案评价工具；其二是搜索最优 方案的工具，即恰当的优化方法。 目前，在电磁场逆问题数值计算中，一般采用的优化方法有模拟退火算法 ( s i m u l a t e da n n e a l i n g 简称s a ) ，遗传算法( g e n e t i ca l g o r i t h m 简称g a ) 和禁忌搜索算 法( t a b u ) 【l 羽等，其中，遗传算法显示了突出的优点。模拟退火算法和禁忌搜索法算法 属于串行算法，而在遗传算法中，种群内部的选择、交叉、变异等操作都是并行进行的。 因此遗传算法自身具有并行性。遗传算法更适合于全局寻优。 鉴于随机性算法中的遗传算法( g a ) 属于进化计算的一种，它可以稳定收敛，而并 行遗传算法可以在不改变其搜索效能的基础上提高其收敛速度，减少计算时间。因此， 本文采用并行遗传算法来对相应的目标进行优化设计，计算结果证明其效果是显著的。 为了评价设计方案的优劣，需要进行电磁场分析。分析电磁场通常采用解析解法和 数值解、法【1 ”1 1 。解析解法在一定条件下能获得精确解，但只能应用于比较特殊的边界情 况，对于复杂边界的电磁场问题却无能为力或收效甚微，并且所得的解冗长复杂，较难 并行遗传算法及其在m r i 永磁主磁体优化设计中的应用 计算，因此，它的应用范围受到一定的限制。随着计算机技术的飞速发展，数值解法用 得越来越广泛，常用的数值解法有差分法和有限元法。差分法适用于边界比较规则的电 磁场问题；有限元法可适应边界不规则的情况，是目前广泛应用的数值算法。有限元法 的计算精度取决于单元插值函数的阶数、网格自适应技术等问题，因此提高有限元计算 精度问题，也是研究的热点。数值解法存在数据前处理繁琐复杂，计算精度不易提高的 缺点，目前也有将数值解法与解析解法相结合的趋势。 1 6 论文的主要内容 遗传算法的迅速发展，为m r i 永磁主磁体的优化设计提供了新的方法。并行遗传算 法可以提高遗传算法的运行速度，减少在电磁场逆问题计算过程中所用的时间。因此本 课题采用并行遗传算法对m r j 永磁主磁体进行优化。 实现本课题进行的步骤： ( 1 ) 利用动态连接，使c + + 语言和f o r t r a n 语言可以互相动态的连接。在此两种编 程环境下完成并行遗传算法的计算。 ( 2 ) 调试电磁场有限元分析程序，并将并行遗传算法的程序和电磁场有限元分析 的程序相耦合，使得并行遗传算法的串行计算成为可能。 ( 3 ) 在p v m 软件的辅助下，在多台计算机上完成并行遗传算法的优化计算。 实现并行遗传算法的要求： ( 1 ) 并行虚拟机( p a r a l l e lv i r t u a lm a c h i n e ) ，简称p v m ，用来分配计算。本文将用 p v m 来实现并行遗传算法。 ( 2 ) 由于要在同构机上进行联机计算，所以还要安装w i n s o c kr s h d n t 。r s h ( r e m o t o s h e l l ) 是一个在本地启动远程宿主机上应用程序的一个实用命令。 ( 3 ) 为了使得计算尽量同步，减少互相等待时间，提高c p u 的利用率，要使参与 计算的各个计算机的计算量尽量均等。 1 7 小结 本章着重说明了遗传算法、并行遗传算法及m r j 的背景和发展现状。指出了课题 的意义，并提出了课题的主要内容。 一6 一 沈阳工业大学硕士学位论文 2 遗传算法及并行遗传算法简述 2 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) ，简称g a 算法，它建立在达尔文适者生存的自然 选择法则的基础之上。它是一种完全不同于以往算法、模拟生命进化机制的搜索和优化 算法。遗传算法最好地适应自然环境，这是自然界生物遗传与进化的结果。这一进化过 程虽然用了很长时间，但从进化的结果来评价，可以看作一种高效率的优化过程。因而 j o l l nh o l l a n d 和他的学生主要进行了两方面的研究工作： ( 1 ) 抽象并严格解释自然系统中的自适应机制； ( 2 ) 设计具有这种机制的人工系统。 由此形成了一套优化算法，即遗传算法。经过几十年的发展，遗传算法本身不断地 成熟，因此，遗传算法的应用无论是用来解决实际问题还是建模，其范围都在不断的扩 大。 遗传算法是一种基于自然选择和群体遗传机理的搜索算法。简单遗传算法的基本流 程图如图2 1 所示。在利用遗传算法求解问题时，首先通过编码操作将问题空间映射到 编码空间，而问题的每个可能的解都被编码成一个“染色体”，即个体，若干个个体构 成了群体( 所有可能解) 。在遗传算法开始时，总是随机地产生一些个体( 即初始解) ，根 据预定的目标函数对每个个体进行评价，给出了一个适应值。基于此适应值，选择个体 用来复制下一代。然后在编码空间内进行选择、交叉、变异三种遗传操作及其循环迭代 操作，模拟生物遗传进化机制，搜索编码空间的最优解，最后映射到原问题空间，从而 得到原问题的最优解。选择操作模拟了个体之间和个体与环境之间的生存竞争，优良个 体有更多的生存繁殖机会，体现了“适者生存”原理，“好”的个体被选择用来复制， 而“坏”的个体则被淘汰。在这种选择压力作用下，个体之间通过交叉变异遗传操作进 行基因重组，期望得到更优秀的后代个体，在这场竞争中胜出。新个体由于继承了上一 代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化。从 这里可以看出遗传算法是一种不同于传统搜索方法的随机性搜索算法。遗传算法通过交 并行遗传算法及其在m r 永磁主磁体优化设计中的应用 叉算：f ( c r o s s o v e ro p e r a t o r ) 和变异算子( m u t a t i o no p e r a t o r ) 的协同作用确保状态空间，在 选择算子( s e l e c t i o no p e r a t o r ) 的作用下保证迭代进程的方向性【4 】。 其中： 适应值一与般优化问题的目标函数相对应，可以等于、也可以不等于目标函数。 适应值越大，越接近最优点。 种群一编码后的参数集集合，一个参数集又称为一个个体，表示一个可行解。 繁殖一将已有的优良个体复制后添入新种群中，删除劣质个体，以产生新的种 群。 交叉一将选出的两个个体进行按位交叉，所产生的新个体添入新种群中。 变异一随机地改变某一个体的某个字符后添入新种群中。 遗传算法的成功应用涉及以下关键问题： 图2 1 简单遗传算法的基本流程图 f i g 2 1b a s i cf l o wc h a r to f s i m p l eg e n e t i ca l g o r i t h m ( 1 ) 表示结构 遗传算法的每一设计方案有多种表示方法，例如二进制向量、浮点向量和其它字符 向量表示法。使用二进制向量作为一个染色体来表示决策变量的真实值，向量的长度依 一8 一 沈阳工业大学硕士学位论文 赖于要求的精度，然而在求解复杂优化问题时使用二进制代码并不太方便，但目前应用 广泛。采用浮点向量表示染色体，其长度与解向量相同，最优化问题的解也用向量表示。 这种表示方法用在复杂优化问题上，比二进制方便得多。 ( 2 ) 初始化过程 应用伪随机数的生成方法随机产生n 个染色体。为了缩小搜索的范围，应先确定一 下其可行域，如果随机产生的染色体在可行域范围之内，则保留，否则去掉，再重新产 生新的染色体，直到可行染色体的数目为n 为止。由此产生的n 个染色体作为初始种 群。 ( 3 ) 评价函数 评价函数用来对种群中的每个染色体设定一个概率，以使该染色体被选择的可能性 与适应值的相对值( 某个体的适应值占适应值总值的百分比) 成比例，适应性强的染色 体被选择产生后代的机会较大。 ( 4 ) 选择过程 选择过程即从旧的种群中选择生命力强的个体以产生新种群的过程。这个选择过程 可以用旋转赌轮来模拟，每次旋转都为新的种群选择一个染色体，适应值越大的个体， 被选中的机会越多。其选择的次数应与种群的染色体数目相同。 ( 5 ) 交叉操作 首先，按一定的方式随机地从种群中取出一对个体，一般是根据适应值的大小来选 择被交叉的个体，然后随机地产生交叉的位置，最后进行交叉，对于较短的字符串，通 常采用一点交叉，如果字符较长，多采用两点交叉。 ( 6 ) 变异操作 通过所产生的小于1 的伪随机数与变异概率相比，决定是否进行变异，变异位随机 产生，并且变异位是否变异由即时产生的随机数的大小来决定( 如果随机数大于0 5 则 变异) 。 遗传算法的特点是算法简单，且不受搜索空间连续性、可微性、单峰值等条件的约 束，是一种求全局最优点的方法【4 】。它和传统的搜索和优化方法( 枚举法、启发式算法、 搜索算法) 的主要区别在于： 一9 一 并行遗传算法及其在m r 永磁主磁体优化设计中的应用 ( 1 ) 自组织、自适应、自学习性( 智能性) 。 ( 2 ) 遗传算法的本质并行性。 ( 3 ) 遗传算法不需要求导活其他辅助知识，而只需要影响搜索方向的目标函数和 相应的适应度函数。 ( 4 ) 遗传算法强调概率转换规则，而不是确定的转换规则。 ( 5 ) 遗传算法可以更加直接的应用。 ( 6 ) 遗传算法对给定问题，可以产生许多潜在解，最终选择可以由使用者确定。 在自然进化过程的任何时刻，总是同时有大量的物种在彼此独立地向前进化。在同 一物种内部，也是同时存在着大量的个体在通过自然选择、交配和基因突变而进化着。 显然，自然界的进化过程本身就是一个并行过程。遗传算法来源于自然进化，与自然进 化的密不可分的关系，很自然地也就继承了自然进化过程所固有的并行性。 遗传算法是人们对自然进化过程的机器模拟，它分别使用选择、交叉和变异等遗传 操作来模拟自然进化过程中的自然选择、交配和基因突变以达到求解组合搜索、优化和 机器学习等问题的目的。虽然在许多领域成功地应用遗传算法，通常能在合理的时间内 找到满意解，但随着求解问题的复杂性及难度的增加，提高g a 的运行速度便显得尤为 突出，采用并行遗传算法( p g a ) 是提高搜索效率的方法之一。 2 2 并行遗传算法 虽然在许多领域成功地应用遗传算法，通常能在合理的时间内找到满意解，但随着 求解问题的复杂性及难度的增加，提高g a 的运行速度便显得尤为突出，采用并行遗传 算法( p o a ) 是提高搜索效率的方法之一。 由于g a 从种群出发，所以具有天然的并行处理特性，非常适合于在大规模并行计 算机上实现，而大规模并行计算机的日益普及，为p g a 奠定了物质基础。特别是g a 中各个体适值计算可独立进行而彼此间无需任何通信，所以并行效率很高。实现p g a ， 不仅要把串行g a 等价地变换成一种并行方案，更重要的是要将g a 的结构修改成易于 并行化实现的形式，形成并行种群模型。 并行种群模型对传统g a 的修改涉及到两个方面：一是要把串行g a 的单一种群分 成多个子种群，分而治之；二是要控制、管理子种群之间的信息交换。不同的分治方法 沈阳工业大学硕士学位论文 产生不同的p g a 结构。这种结构上的差异导致了不同的p g a 模型：全局并行模型、粗 粒度模型、细粒度模型和混合模型。 ( 1 ) 全局p g a 模型 该模型又称主从p g a 模型，它是串行g a 的一种直接并行化方案，在计算机上以 m a s t e r - s l a v e 编程模式实现。它只有一个种群，所有个体的适应度都根据整个种群的适 应度计算，个体之间可以任意匹配，每个个体都有机会和其他个体杂交而竞争，因而在 种群上所作的选择和匹配是全局的。对于这个模型有多种实现方法：第一种方法是仅仅 对适值度函数计算进行并行处理；第二种方法是对遗传算子进行并行处理。全局模型易 于实现，如果计算时间主要用在评价上，这是一种非常有效的并行化方法。 它最大的优点是简单，保留了串行g a 的搜索行为，因而可直接应用g a 的理论 来预测一个具体问题能否映射到并行g a 上求解。对于适应度估值操作比其他遗传算子 计算量大的多时，它是很有效的，并且不需要专门的计算机系统结构。1 9 9 2 年a b t a m s o n 在共享存储的并行计算机上实现了主从式并行遗传算法，用于时间表的优化。主从式方 法在适应度评价很费时且远远超过通信时间的情况下才有效，否则通信时间超过计算时 间，反而会降低速度。而且这种方法要求有同步机制，这就会导致主进程忙而子进程闲 或反之，引起负载不平衡，效率不高。 ( 2 ) 细粒度p g a 模型 该模型又称领域模型或s i m dp g a 模型，对传统g a 作了修改。虽然细粒度模型也 只有一个种群在进化，但在种群平面网格细胞上，将种群划分成了多个非常小的予种群 ( 理想情况是每个处理单元上只有一个个体) ，子种群之间具有极强的通信能力，便于优 良解传播到整个种群。全局选择被领域选择取代，个体适应度的计算由局部领域中的个 体决定，重组操作中的配偶出自同一领域，且子代同其同一领域的亲本竞争空间，即选 择和重组只在网格中相邻个体之间进行。细粒度模型要解决的主要问题是领域结构和选 择策略。 领域结构既决定了种群中个体的空间位置，也确定了个体在种群中传播的路径。领 域结构主要受特定并行计算机的内存结构和通信结构影响。领域拓扑确定一个个体的邻 居，构成该个体的局部领域。通常，只有一个拓扑的直接领域才属于其局部领域，若把 并行遗传算法及其在m r i 永磁主磁体优化设计中的应用 某个固定步数内所能到达的所有个体也包含在内，则可以扩大领域半径。在确定选择策 略时，要考虑到选择压力的变化，而选择压力与领域结构有关。与全局匹配选择类似， 局部匹配选择可以采用局部适应度比例、排列比例选择，以及随机行走选择。局部生存 选择确定局部邻域中被替换的个体，如果子代自动替换邻域中心的那个个体，那么可以 直接使用代替换作为局部生存策略。 ( 3 ) 混合p g a 模型 该模型又称为多层并行p g a 模型，它结合不同p g a 模型的特性，不仅染色体竞争 求取最优解，而且在g a 结构上也引入了竞争以提供更好的环境便于进化。通常，混合 p g a 以层次结构组合，上层多采用粗粒度模型，下层既可采用粗粒度模型也可采用细粒 度模型。或者，种群可以按照粗粒度p g a 模型分裂，迁移操作可以采用细粒度p g a 模 型。 ( 4 ) 粗粒度p g a 模型 该模型又称分布式、m 1 m d 、孤岛模式遗传算法模型，它是对经典g a s 结构的扩 展。它将种群划分为多个子种群( 又称区域) ，每个区域独自运行一个g a 。此时，区域 选择取代了全局选择，配偶取自同一区域，子代与同一区域中的亲本竞争。除了基本的 遗传算子外，粗粒度模型引入了“迁移”算子，负责管理区域之间的个体交换。在粗粒 度模型的研究中，要解决的重要问题是参数选择，包括：迁移拓扑、迁移率、迁移周期 等。 在种群划分成子种群( 区域) 后，要为种群指定某种迁移拓扑。迁移拓扑确定了区域 之间个体的迁移路径，迁移拓扑与特定的并行机结构有着内在的对应关系。如果在顺序 计算机上实现粗粒度模型，则可以考虑采用任意结构。拓扑结构是影响p g a 性能的重 要方面，也是迁移成本的主要因素。区域之间的个体交换由两个参数控制：迁移率和迁 移周期。迁移基本上可以采用与匹配选择和生存选择相同的策略，迁移率常以绝对数或 以子种群大小的百分比形式给出，典型的迁移率是子种群数目的1 0 到2 0 之间。迁移 周期决定了个体迁移的时间间隔，一般是隔几代( 时期) 迁移一次，也可以在一代之后 迁移。通常，迁移率越高，则迁移周期就越长。 沈阳工业大学硕士学位论文 迁移策略包括迁移选择和迁移替换。迁移选择负责选出迁移个体，通常选择一个或 几个最优个体，也可与匹配选择一样，采用适应度比例或者排列比例来选择迁移个体， 也有采用随机选取和替换的。迁移替换是指把最差或者有限数目的最差个体替换掉。通 过迁移可以加快较好个体在群体中的传播，提高收敛速度和解的精度。迁移算子的采用， 使并行算法更适合于全局寻优，并且计算量较小。粗粒度模型的并行算法的迁移策略可 以分为一下两种： ( 1 ) 一传多；每个处理器对应有若干个相邻处理器，每个处理器产生新一代个体 后，都将自己最好的一个个体传送给其所有相邻处理器，并且接受来自相邻处理器的最 好的个体，将这些个体与自己的个体同时考虑，淘汰适应度差的个体，其程序流程见图 2 2 。 ( 2 ) 一传一：考虑到染色体的多样性，每个处理器都将自己最好的个体仅传给与 之相邻的一个处理器，同时增加两个参数：一是s e n d r a t e 决定处理器之间通讯的频率， 如s e n d m t 萨3 时表示当遗传代数是3 的倍数时，各处理器之间相互传送个体；二是 s e n d s t 决定每次传送给最好个体的数目，如s e n db e s t = 5 时表示每个处理器把最好的 前5 个个体传给各自的相邻处理器。其程序流程如图2 3 所示。 基于国内的现状，分布式p g a 为国内p g a 研究的主要方向。分布式p g a 作为p g a 的一种形式，一般实行粗粒度及全局级并行，各子种群间的相互关系较弱，主要靠一些 几乎串行g a 来加速搜索过程。采用分布式p g a 求解问题的一般步骤为： ( 1 ) 将一个大种群划分为一些小的子种群，子种群的数目与硬件环境有关； ( 2 ) 对这些子种群独立的进行串行g a 操作，经过一定周期后，从每个种群中选 择一部分个体迁移到另外的子种群。对于个体迁移存在多种方法，第一种方法，在执行 迁移操作时，每次从子种群中随机选择一部分染色体发送出去，接收的染色体数应该与 发出的染色体相同第二种方法，在执行迁移操作时，首先在每个子种群内只使用选择 而不使用其它遗传算子繁殖一些后代，这些后代的数目与迁移数相同。然后再将这些后 代的原子种群合并成一个大子种群并均匀随即地从该子种群中选择个体进行迁移。这 样，待迁移后子种群的规模便又恢复到正常状态。而当子种群接收到从其他子种群迁移 来的个体时则均匀随即地替换掉子种群内的个体。第三种方法，将其中一个子种群设置 为中心子种群，其他子种群与中心子种群通信。中心子种群始终保持着整个种群中当前 的最优个体，其他子种群通过“引进”中心予种群中的最优个体来引导其加快收敛速 度，改善个体特征。 广1 该r 图2 2 一传多程序流程 f i g 2 2p r o g r a mf l o wo f o n et om o r e g e n e r a t i o n = 0 皇一 初始化种群 鬃毫蛔 妙型 n 习藤 交叉、变异 ! 一 计算适应值 土! 将最好个体传送给 相邻处理器 接受来自相邻处理 器的最好个体 离 l 淘汰适应度差l l的个体 g e n e r a t i o n = g e n e r a t i o n + l 图2 3 一传一程序流程 f i g 2 3p r o g r a mf l o wo f o n et oo n e ( 5 ) 四种模型的比较 就现有的研究结果来看，很难分出各模型的高低。在评价并行模型的差异时，有时 还得深入到实现细节上，如问题的差异、种群大小、或者不同的局部搜索方法等。但有 沈阳工业大学硕士学位论文 一个结论是肯定的：不采用全局并行模型，而采用粗粒度模型或者细粒度模型通常能获 得更好的性能。粗粒度模型与细粒度模型孰优孰劣，尚是一个未知数。 目前，以粗粒度模型最为流行，因为一是其实现较容易，只需在串行g a 中增加迁 移予例程，在并行计算机的节点上各自运行一个副本，并定期交换几个个体即可；二是 在没有并行计算机时，也可在网络或单机系统上模拟实现。虽然并行g a 能有效地求解 许多困难的问题。也能在不同类型的并行计算机上有效地实现，但仍有一些基本的问题 需要解决。种群大小可能既影响大多数g a 的性能，也决定g a 找到解所需时间的主要因 素。在p g a 中，另一个重要问题是如何降低通信开销，包括迁移率的确定，使得区域的 行为象单个种群一样；确定通信拓扑，既能充分地组合优良解，又不导致过多的通信开 销；能否找到一个最优的区域数等。 另外，对不同的应用问题，混合模型难以设定基本g a 的参数，其节点的结构是动 态变化的，它比粗粒度和细粒度模型更具有一般性，算法更为复杂，实现代价更高。 2 3 并行遗传算法在本文中的应用 本文是分布式p g a 进行优化搜索的一个实例。本文采用粗粒度并行遗传算法作为 搜索工具，电磁场有限元分析计算作为分析工具，对m m 永磁主磁体中的极靴形状进 行优化 2 2 -