（计算机软件与理论专业论文）求解tsp问题的遗传算法的改进和并行化研究.pdf

独创性声明 删i f f i | 叫| f i 川 y 18 2 4 8 5 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重麽由电态堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学雠文储躲嘶签字魄叫年碉洳 学位论文版权使用授权书 本学位论文作者完全了解重庞自g 电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权 重迭自e 电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：懈 导师签名： 矽伯秽 签字日期卅年跏。日签字日期叩年f 月哆日 重庆邮电大学硕七论文摘要 摘要 旅行商问题( t r a v e ls a l e s m a np r o b l e m ，t s p ) 是一个具有广泛应用价值 和重要理论意义的组合优化难题，目前被广泛地应用到工业、农业、国防、 商业，特别是交通等领域，引起了数学、物理、计算机等诸多研究者的关 注，而用遗传算法解决t s p 问题成为当前研究热点问题之一。 用遗传算法求解t s p 问题的基本思想是在一个大的空间范围内搜索 和产生较优个体，这就产生了巨大时间复杂度和空间复杂度，而且收敛速 度也受到巨大的影响。本文针对算法中这两个缺陷，用以下两种方法解决： 一是用并行化以加速遗传算法的求解速度和加快收敛速度；二是提高算法 搜索空间的能力。 首先，针对遗传算法中初始化种群操作的不确定性，提出一种基于经 典遗传算法的初始化种群的方法。该方法按照随机搜索和启发式搜索相结 合的方式，保证对空间搜索能力和种群中个体收敛速度。实验证明，该方 法比传统遗传算法空间搜索能力更好，用以解决t s p 问题得到的解更优。 其次，针对传统并行遗传算法通信时间较大，提出一种改进并行遗传 算法模型。该模型通过主处理器接收从处理器中部分较优解作为初始化种 群的部分个体，然后再进行遗传操作；减少了经典算法中每次迭代的通信 时间，并通过迁移较优解确保了算法的收敛性并加速了最优解的产生。 最后，在改进遗传算法基础上，设计三种并行遗传算法求解t s p 问题。 该实验基于主从式模型、粗粒度模型、改进模型，利用实验室机群环境， 利用消息传递接口( m e s s a g ep a s s i n gi n t e r f a c e ，m p i ) ，通过给出不同实验参 数，验证在不同处理器数目下，改进模型的并行遗传算法的运行时间、收 敛性、加速比和效率较之经典并行模型更优。 型 关键词：并行计算，遗传算法，旅行商问题，m p i ，并行遗传算法模 重庆邮电大学硕士论文abstract a b s t r a c t 1 r a v e l i n gs a l e s m a i lp r o b l e m ( t s p ) i sac o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mw i t h w i d e l y 印p l i c a t i o nv a l u ea i l di m p o r t a n ta c a d e m i cv a l u e ， i t s w i d e l y 印p l i c a t i o n si n i n d u s t r y a 鲥c u l t l l r e ，d e f i e n s e ，c o m m e r c i a l ，e s p e c i a l l yi l l a r e a ss u c ha st r a i l s p o nh a s c a u s e di n t e r c s to fr e s e a r c h e r si nm a n ya r e a ss u c ha sm a t h e m a t i c s ，p h ”i c sa i l dc o m p u t e r e t c ，u s i n gg e n e t i ca l g o r i t st os o l v et s pp r o b l e mh a sb e c o m e o n eo ft h eh o t t e s ts p o t s o fc u r r e n tr e s e a r c h g e n e t i ca l g o r i t h mf o rt s ps e a r c h i n gi na1 2 l r g er a l l g eo fs p a c e w h i c hc a l lc a u s ea 铲e a tt i m ec o m p l e x 时a n ds p a c ec o m p l e x i t y ，a i l da l s ot h e c o n v e 唱e n c er a t ew i l lb ee n o 眦o u si n n u e n c e d 1 1 1t h i sp a p e r ，w ew i l lo v e r c o m e 觚o s h o r t c o m i n g so ft h et w ow a y s ：o n ew a y i sp 2 l r a l l e l i n gm e g e n e t i ca l g o r i t | l i i lt os p e e du p s o l v i n gs p e e da n di m p r o v et h ec o n v e 唱e n c er a t e ；m eo t h e ri si m p r 0 “n gt h ec 印a c i t yo f t h es e a r c hs p a c ea l g o r i t h m f i r s t l y ，f o rt h eu n c e r t a i n t yo fi n i t i a l i z a t i o np o p u l a t i o no p e r a t i o ni nt h eg e n e t i c a l g o r i m m ，ac l a s s i cg e n e t i ca l g o r i t b a s e d0 nt h ep 叩u l a t i o ni n i t i “z a t i o nh a sb e e n p r o p o s e d t h em e t h o dc o m b i n i n gt h er a i l d o ms e a r c ha l l dh e u r i s t i cs e a r c hm e t h o dt o e n s u r et h es e a r c hc 印a b i l i t i e so fs p a c ea n dt h ec o n v e 唱e n c er a t eo fi n d i v i d u a l p o p u l a t i o n s t h ee x p e r i m e n t a lr e s u l t ss h o wm a tt h em e t h o d c a ng e tb e t t e rs p a c es e a r c h c a p a b i l i t i e sa i l ds o i u t i o nm a i lt h et r a d i t i o n a lg e n e t i ca l g o r i t s e c o n d l y ， f o r t h el a 略ec o m m u i l i c a t i o nt i m eo ft r a d i t i o n a l p a r a l l e lg e n e t i c a l g o r i t l l i i l ，a i li m p r o v e dm o d e lo fp a r a l l e lg e n e t i ca l g o r i m m sh a sb e e np r o p o s e d t h e m o d e lt a ：k e sp a r to fb e t t e rs o l u t i o n s 嬲i n d i v i d u a lo fi n i t i a l i z a t i o ns t o c k sb yt h em a s t e r p r o c e s s o rt or e c e i v e 矗o mt h es l a v ep r o c e s s o ra i l dm e n t oc a r r yo u tg e n e t i cm a n i p u l a t i o n ； t h j sm e t h o dc a i lr e d u c em ec o m m u l l i c a t i o nt i m ep e ri t e r a t i o nc o m p a r i n gw i m 也e c l a s s i c a la l g o r i t l l i i l ，a i l de n s u r eab e t t e ra l g o r i t h mc o n v e r g e n c ea i l dt h es e l e c t i o no ft h e o p t i m a ls o l u t i o nb ym i 伊a t i o ns 0 1 u t i o n s f i n a l l y b a s e do nt h er e f o 彻e dg e n e t i ca l g o 打t 1 1 i l l ，t l l r e em o d e l so fp a u r a l l e lg e n e t i c a l g o d t h mt 0s o l v et s pp r o b l e mh a v eb e e nd e s i g n e d t h ee x p e r i m e n tb a s i n go nt h e m a s t e r - s l a v em o d e l ，c o a r s e 一孕a i n e dm o d e l ，i m p r 0 v e dm o d e l ，u s i n g 也el a b o r a t o r yc l u s t e r e n v i r o n m e n t ，w i mt h em e c h a n i s mw 1 1 i c hi sm p i ( m e s s a g ep a s s i n gi n t e r f a c e ) ，a n d a d o p t i n g d i f r e r e n te x p e r i m e i l t a lp a r 锄e t e r s ，a l lt h e s e sa r et ov e r i f yi nd i f r e r e n tn u m b e r o fp r o c e s s o r s ，t h ei r n p r o v e dm o d e lo ft h ep a r a l l e lg e n e t i ca l g o r i t h mi sb e t t e ri nm n n i n g t i m e ，c o n v e r g e n c e ，s p e e d u pr a t i oa n de 伍c i c i l c yt h a l lt h ec l a s s i cp a r a l l e lm o d e lb yt h e d i f f e r e n tp a r 锄e t e l i i 重庆邮电大学硕十论文a b s t r a c t k e yw o r d s ： p a r a l l e lc o m p u t i n g ，g e n e t i ca l g o r i t h n l ，t s p ，m p i ，t h em o d e lo ft h e p a r a l l e lg e n e t i ca l g o r i t l l i l l i 重庆邮电大学硕士论文目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究背景1 1 2 国内外研究现状2 1 3 开发平台5 1 4 论文结构5 第二章并行计算和遗传算法的基本理论一6 2 1 基于m p i 的并行计算技术简介6 2 1 1 并行计算6 2 1 2 并行算法基本设计技术9 2 1 3 并行算法的基本实现方法1 1 2 1 4 并行算法的性能评估1 3 2 1 5 消息传递接口j 1 4 2 2 遗传算法基本理论和并行化介绍1 5 2 2 1 遗传算法基本流程1 5 2 2 2 模式1 7 2 2 3 积木块假设1 7 2 2 4 基本遗传算法的收敛性分析1 8 2 2 5 遗传算法的并行性1 8 2 3 本章小结1 9 第三章经典遗传算法解决t s p 问题实现和改进2 0 3 1 t s p 问题概述2 0 3 1 1 t s p 的数学描述和数学模型2 0 3 1 2 t s p 的复杂性分析2 0 3 1 3 t s p 的研究价值2 1 3 2 基本遗传算法实现以及算法的改进2 l 3 2 1 基本遗传算法求解t s p 问题实现2 2 3 2 2 经典遗传算法解决t s p 问题的局限性2 8 v 重庆邮电大学硕士论文目录 3 2 3 改进基本遗传算法求解t s p 问题2 9 3 2 4 改进遗传算法操作流程3 1 3 2 5 改进算法群体个体中模式在遗传算法中的影响31 3 2 6 实验结果和分析3 2 3 3 本章小结3 4 第四章改进模型的并行遗传算法和应用3 5 4 1 传统并行遗传算法概述3 5 4 2 改进的并行遗传算法模型4 0 4 3 基于m p i 的并行遗传算法解决t s p 问题4 0 4 4 改进遗传算法的理论分析4 2 4 5 实验结果和分析4 3 4 6 本章小结4 7 第五章结论及未来工作4 8 5 1 结论4 8 5 2 未来工作4 9 致 射5 0 攻读硕士期间从事的科研工作及取得的研究成果5 l 参考文献5 2 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 遗传算法作为一种基于自然选择和遗传的搜索过程，具有的强壮性和 适用范围广等特性，自l9 7 5 年由美国h o l l a n d 教授提出以来，成功的应用 于各类工程问题。在8 0 年代g 0 1 d b e r g 归纳出基本遗传算法模型，即经过 一个反复迭代的进化计算过程，通过对一个种群中个体进行选择、交叉、 变异等操作，计算适应度，产生新一代的个体，这个迭代过程直到满足某 个条件为止。般来说，遗传算法中适应度的计算最费时间，再加上需要 不断产生新一代，而每一代又有若干个体，所以如何提高遗传算法的运行 速度显得尤为突出。由于遗传算法的内在并行机制，将其并行处理是很自 然的解决途径。 在遗传算法领域中，有不少问题需要在复杂而庞大的搜索空间中寻找 最优解或准最优解，典型的n p 完全问题就是一例。在求此类问题时，若 不能利用问题的固有知识来缩小搜索空间，很容易产生搜索的组合爆炸。 因此研究在搜索过程中缩小搜索空间，加快算法的运行速度和收敛速度， 从而得到最优解或准最优解的通用搜索算法一直是令人瞩目的课题。遗传 算法就是这种特别有效的算法。它的主要特点是简单、通用、鲁棒性强， 适用于并行分布处理，应用范围广。尽管遗传算法本身在理论上和应用方 面仍有待进一步地研究，但它在组合优化问题求解、自适应控制、规划设 计和人工生命等领域的应用中已展现出了自身的特色。 国内对于遗传算法研究，从2 0 世纪9 0 年代以来一直处于不断上升的时 期。特别是近年来，遗传算法、进化算法的应用在许多领域取得了令人瞩 目的成果。现阶段研究主要在以下几个方面：1 、优化搜索方向的研究；2 、 学习系统的遗传算法的研究；3 、生物进化与遗传算法的研究；4 、算法的 分布并行处理。 旅行商问题作为n p 难题，是由美国r a n d 公司于19 4 8 年引入，该公司 的声誉以及线性规划这一新方法的出现使得t s p 成为一个知名且流行的问 题。t s p 问题从应用上来说，可以在如印制电路板的电路设计、连锁店的 货物配送路线等。因此对于t s p 的问题自然成为不可避免的问题。从理论 上来说，它的计算复杂性研究在形成n p 完全理论中起到奠基作用。在当代 重庆邮电人学硕士论文第一章绪论 计算机科学技术的迅速发展，给求解t s p 问题又注入了新的活力，这为求 解该问题提供了新思路、新方法、新成果，促进n p 完全理论的发展。 1 2 国内外研究现状 当今并行编成语言环境主要分为两种，分布存储编程环境和共享式存 储编程环境。 分布存储编程环境主要使用多地址空间的消息传递编程模型，这类模 型以消息传递接口【1 1 ( m a s s a g ep a s s i n gi n t e r f a c e ，m p i ) 、并行虚拟机【2 】 ( p a r a l l e lv i n u a lm a c h i n e ，p v m ) 为代表。 共享存储器并行编程有多种实现方式【3 】，如p o s i x 线程的简化版本 p t h r e a d s ，在学术界应用广泛的高性能f o n r a n ，o p e n m p 等。其中，o p e n m p 是1 9 9 7 年由s i l i c o ng r a p h i c s 领导的工业协会，在精简了p c f x 3 h 5 标准 后提出的。目前已经完成了f o r t r a n 7 7 、f o r t r a n 9 0 、c c + + 语言的实现规范。 许多硬件和软件的供应商提供对o p e n m pa p i 从编译器到硬件平台的支 持，这些供应商包括d e c 、i n t e l 、i b m 、c o m p a q 、h p 、m i c r o s o f t 等，实 际上，o p e n m p 已经成为工业界的事实标准。 早期的有基于s o c k e t 的d g e n e s i s 【4 1 、和基于p v m ( 并行虚拟机) 的 g a l o p p s f 5 j ，p o o g a l 【6 】等，基于s o c k e t 的并行程序，复杂性高、移植性 较差；而p v m 虽然曾经是引领消息传递并行程序设计的中间件，但现在已 经逐渐被开放的可移植的m p i 所代替。p g a p a c k 【7 】是一个并行遗传算法程 序库，它可以被f o r t r a n 或者c 语言编写的程序调用，构成并行遗传算法， 但只支持类u n i x 的操作系统，而且只提供对主从式模式的并行遗传算法 的支持。p a r a d i s e o 【8 j 是一个支持p v m 和m p i 的c + + 演化程序框架，它提 供了灵活的参数配置和广泛的体系结构支持，但同样也只支持类u n i x 的 操作系统。国内在此方面的研究只有一个基于p v m 的并行遗传算法c + + 类库p a r a g a 的实现。因此基于m p i 的并行遗传算法研究是非常有意义。 进入9 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是 应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活 跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能 力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理 论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添 了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多 2 重庆邮电大学硕士论文第一章绪论 更新、更工程化的应用方面。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动 向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来 离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新 的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识 优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊 推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓2 l 世 纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研 究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能 计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工 生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然晃 丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命 的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算 法和进化规划( e v o l u t i o np r o g r a m m i n g ，e p ) 以及进化策略( e v o l u t i o n s t r a t e g y ，e s ) 等进化计算理论日益结合。e p 和e s 几乎是和遗传算法同 时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制 的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前， 这三者之间的比较研究和彼此结合的探讨正形成热点。 1 9 9 1 年d w h i t e y 在他的论文中提出了基于领域交叉的交叉算子 ( a d j a c e n c yb a s e dc r o s s o v e r ) 【引，这个算子是特别针对用序号表示基因的 个体的交叉，并将其应用到了t s p 问题中，通过实验对其进行了验证。 d h a c k l e y 等提出了随即迭代遗传爬山法【l o 】( s t o c h a s t i ci t e r a t e dg e n e t i c h i l l c l i m b i n g ，s i g h ) 采用了一种复杂的概率选举机制，此机制中由m 个 “投票者”来共同决定新个体的值( m 表示群体的大小) 。实验结果表明， s i g h 与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中 有四个表现出更好的性能，而且总体来讲，s i g h 比现存的许多算法在求 解速度方面更有竞争力。h b e r s i n i 和g s e r o n t 将遗传算法与单一方法【1 1 1 ( s i m p l e xm e t h o d ) 结合起来，形成了一种叫单一操作的多亲交叉算子 ( s i m p l e xc r o s s o v e r ) ，该算子在根据两个母体以及一个额外的个体产生新 个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同 时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三 者交叉算子比其余两个有更好的性能。 国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2 0 0 2 年，戴晓明l l2 】等应用多种群遗传并行进化的思想，对不同种群基于不同的 重庆邮电人学硕士论文第一章绪论 遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群 间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优 值问题。2 0 0 4 年，赵宏立等针对简单遗传算法在较大规模组合优化问题上 搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法【l 3 】 ( b u i l d i n g - b l o c kc o d e dp a r a l l e lg a ，b c p g a ) 求解t s p 问题。该方法以 粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块， 然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色 体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。 2 0 0 5 年，江雷等针对并行遗传算法求解t s p 问题，探讨了使用弹性策略来 维持群体的多样性，使得算法跨过局部收敛的障碍，向全局最优解方向进 化。2 0 0 7 年，莫海芳【1 4 】等提出了一个混合遗传算法求解t s p 问题，结合 了机遇领域的l k 算法和采用i n v e r o v e r 算子的遗传算法，并在算法中增 加一些控制策略，加快算法的收敛速度，维持种群的多样性。 1 9 9 2 年a b r a m s o n i ”】在共享存储的并行计算机上实现了主从式并行遗 传算法，用于时间表的优化。主从式方法在适应度评价很费时且远远超过 通信时间的情况下才有效，否则通信时间超过计算时间，反而会降低速度。 而且这种方法要求同步机制，这就会导致主进程忙而子进程闲或反之，引 起负载不平衡，效率不高。关于粗粒度模型的研究，目前主要有：p e t t y ，l e u z e 和g r e f e n s t e t t e 将一个适应度计算很费时的遗传算法并行化【1 6 】，t a n e s e 【 】 采用四维超立方体结构和固定的迁移间隔，研究并行遗传算法的加速比和 解的质量，c o n o o n ，m a r t i n 和r i c h a r d s l l 8j 分析了在并行计算机i n t e l l 8 6 0 上解图划分问题的多种群遗传算法的性能。关于细粒度的模型研究主要 有：m a n d e r i c k 和s p i e s s e n s l 】基于二维网络拓扑结构开发了一种大规模并 行遗传算法，用于研究同类群大小及染色体长度对于算法性能的影 响；m u h l e n b e i n 【2 0 j 提出了一种异步通信模式并将它应用到复杂组合问题 上；k o s a k 【2 1 】将群体中个体映射到一个连接机的处理单元，并指出这种方法 对网络图设计的有效性。v s g o r d o n 【2 2 】等在特定的多处理机上使用并行 编程语言来实现并行遗传算法，他们在数据流计算机上实现并行遗传算 法，虽然这种方法允许用户开发一个不依赖于具体机器的并行遗传算法程 序，但是由于共享存储器访问冲突的限制，其性能不尽人意。在m a r u a y a m a 等所开发的算法中，虽然也把群体中的每个个体分配在不同的处理机上， 但它并不是基于群体分组为并行遗传算法，因为其交叉操作方法并不是局 部进行的，而是在全局环境中进行的，它基于对全部群体的进化计算来产 生新的个体。另外，它还使用了一些缓冲区来进行异步进化操作，以获得 4 重庆邮电大学硕士论文第一章绪论 最大的并行性。p h u s b a n d s 等将待求解的问题划分成一些子问题，对各个 子问题采用不同结构的遗传算法，使用模拟共同进化的概念来形成并行遗 传算法。 1 3 开发平台 本文算法的开发与实现是基于i n t e lt 5 5 5 0 双核处理器平台，使用 m i c r o s o f t 公司v i s u a ls t u d i 0 2 0 0 8 作为开发工具，在m p i 基础上，并行算 法实现的程序设计模型。 1 4 论文结构 论文主要章节安排如下： 第一章前言，介绍了本文的课题背景、研究现状和本文结构； 第二章简要说明并行算法的设计理论和遗传算法的基本理论。包括 常见的并行计算法硬件平台、并行性的判断方法、并行算法设计常用模型、 选择实现方式与开发平台的条件和方法，以及并行算法性能评价方式；同 时介绍了遗传算法一些基本理论一一遗传算法的基本流程、模式、积木块 假设和算法收敛性的证明，以及遗传算法并行性介绍； 第三章通过对经典遗传算法中基本操作的研究，针对经典遗传算法 中初始化种群的不确定性，改进了传统遗传算法，通过获取的较优基因块 组合成初始化种群个体，使得优化种群的效果，实验证明了该算法相对于 传统遗传算法空间搜索能力更强，收敛速度更快； 第四章通过对经典并行遗传算法模型的研究，针对传统并行遗传算 法中的处理器之间通信时间较大和粗粒度模型中全局监控能力的不足，改 进并行遗传算法模型，通过从处理器中独立运行遗传算法，将得到的较优 解传递到主处理器中构成主处理器中初始化种群的部分个体，进一步深入 遗传操作，实验证明该算法模型相较于传统算法模型算法运行速度更快， 收敛性更好。 第五章对本文进行了总结，提出下一步的研究计划。 重庆邮电大学硕士论文第二章并行计算和遗传算法的基本理论 第二章并行计算和遗传算法的基本理论 实现并行遗传算法，主要包括三个方面的内容，遗传算法算子选择、 并行算法模型的选择、并行遗传算法的平台使用。本章主要是并行计算简 介和遗传算法理论介绍。 2 1 基于m p i 的并行计算技术简介 2 1 1 并行计算 随着电子管，晶体管和集成电路的出现，元器件技术的不断进步，计 算机的速度不断提高，性能不断增强，但是由于电子信号的最大传输速度 是有限的，仅提高电子部件的速度来改善计算机的性能以满足用户对计算 机愈来愈高的要求是不可能的。提高计算机性能的另一重要途径就是采用 并行处理技术。 定义：并行处理是一种有效的强调开发计算过程中并行事件的信息处 理方式【23 1 。 图2 1 四种处理 定义中的信息处理具有通常数据处理、信息处理、知识处理和智能处 理等多种含义。从计算机处理的角度来看，这四种处理的领域如图2 1 所 示。数据是客观对象的表示，数据处理空间最大，它包括不同格式的数字 处理和字符处理。数据空间中的数据对象相互没有联系。数据处理是计算 机的主要任务。信息是数据及其含意。一个信息项是一个通过语法特征相 联系的数据对象的集合。随着越来越多的数据结构被研制成功，计算机用 6 t 黜上t 上一l 上 重庆邮电大学硕士论文 第二章并行计算和遗传算法的基本理论 于信息处理的范围不断扩大。信息处理是数据处理的一个子空间，但它不 包含规律性的处理。知识是人们对客观对象规律性的认识，它是一个加上 了一些语义的信息项组成的。知识处理包括知识表示、知识获取和处理规 则。智能处理包括定理、逻辑推理、创造性思维等。 并行性有三种含义：一是同时性，指两个或多个事件中同一时刻发生 在多个资源中；二是并发性，指两个或多个事件中同一时间间隔内发生在 多个资源中；三是流水线，指两个或多个事件发生在可能重叠的时间段内。 开发问题中的并行性是为了设法予以并行处理，提高并行处理计算机的使 用效率。一般说来，有计算并行性、搜索并行性和逻辑并行性等三类性质 不同的并行性。计算并行性与算法设计及算法的表示密切相关。在数值计 算中，经常使用的计算模式有表达式求值和递归两种。例如求如下两个向 量的内积： 巧= 五，五，以 ( 2 1 ) 圪= z ，艺，e ( 2 2 ) 可以用表达式求值模式： 尺= 匕宰匕= ( 置k + 置蔓+ + 以) ( 2 3 ) 也可以采用线性递归模式： f z ：0 肚1 z ：置i + 毛，1 姚，z ( 2 4 ) 【z j = 置i + 互一l ， 1 f ，z 、7 这两种不同的计算模式，分别揭示了两种不同的计算并行性。第一种模式 提供了按树状结构进行处理的可能性，如图2 2 所示；第二种模式则可以 用流水线方式来处理，如图2 3 所示。 五托k墨e以一。一。以艺 图2 2 树形结构 7 重庆邮电人学硕士论文 第二章并行计算和遗传算法的基本理论 z 0 i 千 ； 干 亍 i 干 i 若n 为奇数，令x 。+ 。= k + 。= 0 ，则乙+ 。= 乙 图2 3 流水线结构 所谓搜索是指按给定键值( 或模式) 从存储空间检索出与键值匹配的有 关内容。对于线性存储空间最自然的搜索算法是顺序查找。为了提高按地 址访问存储空间的检索效率，配合各种不同的文件结构设计了许多不同的 搜索算法，如分块、二分法、索引法等。然而，从本质上讲，由于按地址 访问的单端口存储结构只能一个单元一个单元的顺序访问，因此上述所有 的改进搜索算法只是为了缩小搜索范围，减少或避免不必要的测试性检 索，而不是着眼于如何开发搜索的并行性。为了实现真正的并行搜索，必 须从根本上改变存储结构。关联存储器就是这样的一种存储结构，搜索键 并行的与所有记录键进行比较，同时给出所有匹配信号，一次检索出所有 其键值与搜索匹配的记录，实现并行检索。逻辑并行性主要是指对问题空 间或状态空间进行搜索时存在各种并行性，特别是a n d 并行性和o r 并 行性。 并行时间可以在计算机系统中的不同处理级获得。按照程序概念有四 个处理级【2 4 l ：一是作业或程序级；二是任务或进程级；三是指令级，它涉 及数据相关、循环语句和向量等；四是指令内部操作级，由计算机硬件实 现。前两者需要开发并行处理算法( 简称并行算法) ，它们的实现依赖于解 大型问题的多个程序所需要的硬件和软件资源的有效安排，以便多个程序 并行执行，所以并行算法不仅仅是一个数学问题。 并行处理系统是由n 台处理机或n 台等效处理机组成的，受同一的操 作系统控制，解一个问题，系统硬件的价格不能大于单个处理机硬件价格 的n 倍，系统的运算速度不能远小于单个处理机速度的n 倍。这体现了定 重庆邮电大学硕士论文第二章并行计算和遗传算法的基本理论 义中“有效”的含义。 并行处理是一门综合性较强的学科，它涉及到算法、语言、操作系统 和系统结构等方面的知识，这些方面相互联系，互为条件，互为保证。 2 1 2 并行算法基本设计技术 按照传统计算数学的一般概念，数值计算方法和程序设计是两门密切 相关的不同学科。算法是解题方法的精确描述，它是一组有穷的规则，这 些规则确定了在计算机上求解某一问题的一系列运算。于是，根据算法可 以直接地进行程序设计。我们指出，在人们利用计算机解算一个问题时， 对于串行机而言，数值方法( 简称为解法) 与算法的关系比较简单，解法一 旦确定，有效的串行算法和计算程序也随之产生，它们可能在任何一种串 行机上得到实现。但是，在并行计算系统出现以后，区别解法和算法这两 个概念的重要性增加了，同样一个解法针对不同类型的并行机可以有着差 异甚大的算法和程序设计。在实现算法时，需要考虑到机器的类型和特点。 是并行机还是向量机，是共享存储类型还是局部存储类型，并行机的处理 器个数有多少，各处理器之间的负载平衡等问题。 如图2 4 所示提供了一个简单的并行算法设计的说明框架，虚线所界 定的内容构成了一个与并行算法直接相关的相当广泛的研究领域。我们看 到，为了在并行机上实现给定问题的求解，需要完成图中所示任务的一个 大循环。其中，我们特别强调，对于所要解算的数学问题，如果传统数值 方法己具备良好的和明显的并行性，则可直接进入并行算法设计，不需要 从数值分析的角度进行并行化的工作；相反，倘若传统方法并没有良好的 并行性，则应对其进行并行性改造和创新。 图2 4 简单的并行算法设计说明框架 9 重庆邮电人学硕士论文第二章并行计算和遗传算法的基本理论 设计并行算法的基本方法大体可分为三类【2 5 】： 1 、检测和开拓现有串行算法中的固有并行性而直接将其并行化； 2 、修改已有的并行算法使其可求解另一类相似问题； 3 、从问题本身的描述出发，从头开始设计一个全新的并行算法。 对一类具有内在顺序性的串行算法难于并行化；修改己有的并行算法 有赖于特定的一类问题；设计全新的并行算法，尽管技术上尚不成熟且似 乎又有些技巧，但也不是无章可循。本节将简单介绍目前普遍使用的几种 并行算法的设计技术，包括平衡树方法、倍增技术、分治策略、流水线技 术以及加速级联策略等。 分治策略【2 6 1 ( d i v i d e a n d c o n q u e rt e c h n i q u e ) ，即分而治之策略，其思 想是将原问题分解成若干个特征相同的子问题分而治之，将计算负载分摊 在各计算结点上，以减少单个结点的计算量，从而达到加速整体运行效率 的目的。若所得的子问题规模仍嫌太大，可反复使用分治策略直至很易求 解诸子问题为止。使用分治法时，子问题的类型通常和原问题的类型相同， 因此很自然地导致递归过程。该策略在不少并行算法文献中已被公认是设 计并行算法的根本准则，常见的分治方法有以下两种： l 、数据分割：数据分割是指各结点基本执行相同的任务，只是数据 不同。此方法常用在计算的各数据之间具有对称性的情况。例如对于向量 的加法，可以分割为各个分量的加法； 2 、任务分割：任务分割是指总任务由自然的多个子任务组成，将其 分摊在各个结点上。例如对于连续的数据处理任务，可以将其分割成数据 采集、数据计算和结果输出三个子任务。 平衡树方法( b a l a n c i n g t r e et e c h n i q u e ) 是将输入元素作为叶节点构筑 一棵平衡二叉树，然后自叶结点向根结点遍历。此法成功的部分原因是在 树中能快速地存取所需要的信息。平衡二叉树方法可推广到内节点的子节 点的数目不只两个的任意平衡树。这种方法对数据播送、压缩、抽取和前 缀计算等甚为有效。 倍增技术( d o u b l i n gt e c h n i q u e ) 又叫指针跳跃技术( p o i n t e rj u m p i n g t e c h n i q u e ) ，特别适合处理以链表、有图或有根树之类表示的数据结构， 在图论和链表算法中有着广泛的应用。每当递归调用时，所要处理的数据 之间的距离将逐步加倍，经过尼步后就可完成距离2 的所有数据的计算。 流水线技术( p i p e l i n i n gt e c h n i q u e ) 是一项重要的并行算法的设计技术， 它在v l s i 并行算法中表现得尤为突出。其基本思想是将一个计算任务f ， 分成一系列子任务毛，乞，乙，使得一旦完成，后继的子任务就可立即开始， l o 重庆邮电入学硕士论文 第二章并行计算和遗传算法的基本理论 并以同样的速率进行计算。 加速级联策略( a c c e l e r a t e dc a s c a d i n gt e c h n i q u e ) ，为了获得一个快速 最优的算法，我们可以将一个最优但相对不快的算法与另一个非常快但不 是最优的算法级联( 或串联) 起来，形成一个加速级联算法。具体做法是： 1 、开始使用最优算法，直到求解问题规模减到某一阀值； 2 、接着使用快而非最优的算法，继续完成问题的求解。 加速级联算法的一个重要特例是： 1 、将输入划分成一些不相交的子输入： 2 、使用最优串行算法并发求解子问题； 3 、使用一个快速的并行算法归并子问题的解。 2 1 3 并行算法的基本实现方法 并行算法的实现强烈地依赖于并行机的软硬件环境。并行算法实现所 涉及的内容十分广泛，需要考虑很多方面的问题，主要有：整体修正、粒 度调整、超级步的划分、通信模式、负载平衡、同步开销、数据依赖和并 行调试，下面作简单介绍。 1 、整体修正 对于许多实际问题，只强调“分而治之”是不够的。在考虑并行程序设 计的分割问题时，还应做“整体修正”，即在计算的关键部位进行必要的结 点间通信。尽管此部分的工作量的比例很小，却是决定并行算法效率的关 键部位。 2 、粒度调整 粒度【2 5 1 ( g r a n u l a r i t y ) 可定义为任务计算量的平均值与任务间通信量的 平均值之比，它是各个结点可独立并行执行的任务大小的量度。粒度大小 的选择对并行程序的效率有重大的影响。目前对粒度的划分并没有一