并行算法结构（精选十篇）
并行算法结构 篇1
1 并行遗传算法
遗传算法始于一个初始群体, 群体中的个体都要进行这三种运算。运算后的结果如自然选择一样, 比初始群体具有更好的适应性。并行遗传算法就是一种很好的选择, 它能很容易的实现并得到一个很好数值解。除此之外, 并行遗传算法比遗传算法运算速度更快, 并且能得到一个更优结果[2,3,4,5]。标准的遗传算法以群体集合为运算对象, 对个体所进行的各种遗传操作都有一定的相互独立性, 所以它具有一种天然的并行结构。由于遗传算法的天然并行性, 人们认识到了对其进行并行处理的可能性, 从而基于各种并行计算机或局域网开发了多种并行遗传算法 (Parallel Genetic Algorithm, 简称PGA) 。开发并行遗传算法的主要目的是为了提高遗传算法的运算速度[7,8]。
2 目标函数
损伤由刚度减小率βi表示, 定义为减小刚度与初始刚度的比值。损伤结构的刚度矩阵[Kd]表示所有单元矩阵乘以减小因数的和[4]:
βi=0表示结构未损伤, 0<βi<1表示结构部分或全部损伤。
频率变化:
式中:下标0———初始未损伤状态;
λi———第i个特征值;
ωi———第i个频率。
模态保证标准:
式中:φiu———未损伤的第i阶模态向量;
φid———损伤后的第i阶模态向量。
MAC是一个无量纲的量, 范围从0到1, 代表了两组模态向量之间的关联程度, 1指完全关联, 0指完全不关联。
目标函数:
Fλ, 0, FMAC, 0表示结构未损伤时的值 (β=0) 。FD表示损伤补偿函数。当损伤补偿函数加到目标函数中, 还要包括最小损伤。由此, 由计算误差引起的错误损伤检测就可以避免了。罚函数如下:
此等式由Meruance和Heylen提出, 补偿了全部的损伤, 常数γ取决于计算模型的精确度。
最优问题定义如下:
3 算例
3.1 计算模型及基本假定
用一跨预应力混凝土简支梁进行数值模拟, 为了更好地观察结果, 简支梁外伸形成悬臂梁。如图1所示, 该模型有30个单元, 31个节点, 弹性模量是3.0×1010Pa, 密度是2500kg/m3, 面积是0.06m2, 惯性矩是4.5×10-4m4。
模态观测数据用结构的有限元模型模拟获得, 损伤用弹性模量折减来模拟。损伤工况设计如下[5, 7, 10]:
工况一:10号单元10%损伤, 20号单元35%损伤;
工况二:10号单元20%损伤, 20号单元35%损伤;
工况三:10号单元35%损伤, 20号单元35%损伤。
3.2 初始参数的确定
为了提高收敛速度, 避免过早收敛, 遗传算法的参数和算子取值如下:种群大小:N=75;变异概率pm=0.02;交叉概率ps=0.8。初始种群值为1[5,6,7,8,9]。
3.3 计算结果与讨论
迁移时段如图2所示, 以敏感度分析定义。得到的最优迁移时段是70。图3示出的是通过并行遗传算法收敛率的提高。
并行遗传算法 (PGA) 求解最优解的时间是500多秒钟, 而遗传算法 (GA) 则需要1000多秒。并行遗传算法运算时间是遗传算法的0.5倍。
三种工况的下的损伤探测如图4所示。
从图中可以看出, 损伤检测结果已经达到了完美的程度, 和模拟的损伤很接近, 但并不能说明实际的应用当中也有很好的应用, 所以这方面的研究工作将在以后进行讨论。
4 结论
本文提出了并行遗传算法检测结构损伤的方法。数值模拟结果表明相比于遗传算法, 并行遗传算法在表现上更进一步, 在计算结果相同的条件下, 计算速度是遗传算法的1.5倍。因此, 对于明确问题的并行遗传算法可以使结果得到改进。
本文提出的方法只是针对于预应力简支梁桥模型的损伤识别进行了研究, 对于其他结构, 如高层结构、框架结构等的损伤识别同样有很好的表现。提出的并行遗传算法定位、定量的识别了模拟的损伤, 但是没有考虑损伤发生时刻的检测。其在实际结构损伤中的应用也未做具体的分析实验。这些将在以后进行研究分析, 在损伤识别领域中, 并行遗传算法会有更好的发展。
参考文献
[1]Mares, C.and Surace, C.An application of genetic algorithms to identify damage in elastic structures[J].Journal of Sound and Vibration, 1996, (195) :195-215.
[2]袁颖.遗传算法在结构损伤识别中的应用研究[J].防灾减灾工程学报, 2005, 25 (4) :114-116.
[3]曾国荪.并行遗传算法分析[J].计算机工程, 2001, 29 (9) :96-98.
[4]Meruane, V.and Heylen, W.Damage detection with Parallel Genetic Algorithms and Operational Modes[J].Structural Health Monitoring, 2010, (9) .
并行算法结构 篇2
二维自适应非结构网格DSMC并行算法研究
研究了二维自适应非结构网格DSMC并行算法实现的过程.首先提出了一类非结构网格自适应策略,有效降低了网格尺度对计算结果的影响,提高了流场的.分辨率;然后基于PC-CLUSTER群机并行体系结构与消息传递库MPI并行环境,利用分区并行思想,设计了非结构网格DSMC并行算法,节约了计算时间.利用For-tran90的动态分配内存技术编制了通用计算程序;最后对过渡流域高超声绕流进行了数值模拟,计算结果初步验证了算法的可行性与有效性.
作 者：王学德 伍贻兆 夏健 林晓宏 WANG Xue-de WU Yi-zhao XIA Jian LIN Xiao-hong 作者单位：王学德,林晓宏,WANG Xue-de,LIN Xiao-hong(南京理工大学动力工程学院,南京,210094)伍贻兆,夏健,WU Yi-zhao,XIA Jian(南京航空航天大学,航空宇航学院,南京,210016)
刊 名：计算力学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS 年，卷(期)：2009 26(2) 分类号：V211.3 关键词：自适应非结构网格 DSMC 并行算法 MPI并行算法结构 篇3
关 键 词：MOS器件；模型参数；参数提取；器件模型
1 引言
器件的模型和模型参数提取是电子设计自动化（EDA）领域的关键工作[1]。采用遗传算法进行半导体器件模型参数提取是近年来兴起并被广泛使用的一种参数提取方法[2-3]。遗传算法全局搜索能力强、不需进行繁琐的求导运算，不依赖参数初始值等特点，理论上来说只要有足够的迭代次数种能找到最优解[4]。但是，由于遗传算法是一种搜索类算法,较之传统的基于梯度进行迭代计算的解析算法, 每进行一次迭代所需要的时间较长，计算量有了显著增加, 而且对许多复杂问题而言，例如采用的全局优化策略提取复杂模型的大量参数时，标准遗传算法的求解效果往往不是解决这个问题的最有效的方法，必须对算法进行修改与优化，这些因素无疑大大增加了遗传算法的计算量，为此必须考虑算法的耗时问题。本文针对遗传算法自身的耗时问题，讨论了并行遗传算法的特点，并以主从式遗传算法为例，证实了并行计算在参数提取工作中的可行性。
2 并行遗传算法
为了有效的解决遗传算法（GA）在模型参数提取过程中的耗时问题, 提高GA的运行速度，采用并行遗传算法（PGA）是提高搜索效率的方法之一。并行遗传算法[5-6]主要有主从式并行遗传算法、粗粒度并行遗传算法和细粒度并行遗传算法。
2.1 全局PGA模型－主从式模型（master-slave model）
如图1所示，主从式模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器。
主从式模型的优点是简单，保留了串行GA 的搜索行为，对计算机体系结构没有严格要求，适合运行在共享存储和分布式存储的并行计算机上。如果适应度估值操作比其他遗传算子计算量大的多时，这是一种非常有效的并行化方法。
2.2 粗粒度PGA模型－分布式模型（distributed model）
该模型又称分布式、MIMD、岛屿模式遗传算法模型。在处理器个数较少的情况下，我们可以将群体分为若干个子群体，每个子群体包含一些个体，每个子群体分配一个处理器，让它们相互独立地并行执行进化。为了防止子群体早熟，每经过一定的间隔(即若干进化代)，各子群体间会交换部分个体以引入其他子群体的优秀基因，丰富各子群体的多样性。除了基本的遗传算子外，粗粒度模型引入了“迁移”算子，负责管理区域之间的个体交换。如图2所示，通常存在两种迁移实现:岛屿模型、踏脚石模型。
2.3 细粒度PGA模型－分散型 (fine-grained model)
细粒度模型又称为邻域模型(neighborhood model)或细胞模型(cellular model)模型。如果并行计算机系统的规模很大，理想情况下处理器多到可以与染色体一一对应，则我们可以将每个个体分配一个处理器，让它们相互独立地并行执行进化，这样就能获得并行遗传算法的最大可能的并发性。如图3所示，在细粒度模型中，通常处理器被连接成平面网格(grid)，每个处理器上仅分配一个个体，选择和交叉只在网格中相邻个体之间进行，所以网格上的邻域关系就限定了个体空间上的关系。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广。
3 基于MPI的主从式遗传算法的的实现
3.1 总体构想
我们采用的主从式并行模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器，其个体的分配过程是这样的：假设种群规模为N, 优化模型参数变量个数为M。适应度评估时，程序传给评价函数N个长度为M的向量。并行的任务是master处理器将这个N个长度为M的向量平均分配到各slaves处理器做适应度计算，计算结束后，评价函数返回N个适应度给master处理器。计算各处理器分得的染色体个数的方法是，首先计算出每个处理器至少分配到的染色体个数为AveNum=N/Size，如果处理器个数不能整除行数，这样将有部分处理器分得到（AveNum+1）个染色体，规定多余的染色体分配到编号小的处理器上。
3.2 并行中的消息传递机制
另外，需要注意的是，仅仅依靠例如C，C++，java等编程语言所编写的程序是无法实现上面叙述的染色体在各处理器之间的传递任务。因为，在并行计算环境中，每个进程均有自己独立的地址空间，一个进程不能直接访问其它进程中的数据，因而，在进行并行计算的任务之间进行的数据传输必须通过消息传递机制。消息传递机制，是指用户必须显式地通过发送和接收消息来实现处理器之间的数据交换。
本文采用的是MPI(Massage Passage Interface)消息传递接口。MPI是一个很好的数据传递软件平台，可以通过调用MPI库函数来进行进程调度以及任务间的通信。它实际上是一个消息传递函数库的标准说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一，其特点是通用性强(只要求网络支持TCP/IP网络协议)、系统规模小、技术比较成熟。本文通过调用MPI的库程序来达到程序员所要达到的并行目的，使异构的计算机群体作为一个紧凑、灵活、经济的计算机资源来使用的并行环境。
3.3 共享内存多处理器主从式并行环境搭建
全局并行化模型并不限定计算机体系结构，它可以在共享内存和分布式内存计算机中高效实现。现在简单介绍一下两种并行编程的方法：分布式内存方法和共享式内存方法。
对于分布式内存的并行计算机，各个处理器拥有自己独立的局部存储器，不存在公用的存储单元，显然，这种方法的问题就产生于分布式内存的组织。由于每个节点都只能访问自己的内存，如果其他节点需要访问这些内存中的数据，就必须对这些数据结构进行复制并通过网络进行传送，这会导致大量的网络负载。他的优点是拥有很好的扩展性，有利于快速构造超大型的计算系统。
在共享内存多处理器计算机中构成并行环境，在共享式内存方法中，内存对于所有的处理器来说都是通用的。这种方法并没有分布式内存方法中所提到的那些问题。而且对于这种系统进行编程要简单很多，因为所有的数据对于所有的处理器来说都是可以使用的，这与串行程序并没有太多区别。这些系统的一个大问题是扩展性差，不容易添加其他处理器。
为了在微机环境下使用MPI构成分布式内存并行环境，只要将PC机联接局域网，然后在每台PC机上安装相应操作系统，并安装MPI软件包即可。分布式内存即种群被一个处理器存储。这个主处理器负责将个体发送给其它从处理器进行评估，并收集计算结果，进行遗传操作来生成下一代。
对于本文所采用的在共享内存多处理器计算机中构成主从式并行环境就更为简单，只要在PC机上安装操作系统（本文安装linux操作系统）和MPI软件包就可以实现并行环境了。在共享内存多处理器计算机中，种群可以保存在共享内存中，每个处理器可以读取被分配到的个体信息并将适应度写回，不会有任何冲突。
4 实验结果分析
将以上方法实现的基于MPI的主从式遗传算法应用于1.2um SOI MOS器件的阈值电压模型参数提取工作中。如图4所示，实验结果表明曲线拟合的效果很好，转移特性曲线最大误差都低于5%。采用并行计算后，参数提取的速度提高了接近2.5倍。
5 结论
从实际的测试效果来看，以上方法实现的程序的简洁有效，智能化程度很高，且具有较高的精确度。因此，本文提出的基于MPI的主从式遗传算法可以解决遗传算法在器件参数提取过程中的耗时问题。该方法简单易用，适合推广使用。
参考文献
[1] J.Liou A,Analysis and Design of MOSFETS: Modeling,Simulation,and Parameter Extraction[M].KLUWER ACADEMIC PUBLISHERS,1998.
[2] Kondo M,Onodera H,Tamaru K.Model adaptable MOSFET parameter extraction method using an intermediate model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(5):400-405.
[3] Yang P, Chatterjee P K, An optimal parameter extraction program for MOSFET models[J].IEEE Transaction on Electron Devices,1983,30(9):1214-1219.
[4] Li Yiming. An automatic parameter extraction technique for advanced CMOS device modeling using genetic algorithm.Microelectronic Engineering,2006,41(4): 1309-1321.
[5] 康立山，非数值并行算法(第一册)-并行遗传算法[M].科学出版社,2003.
并行算法结构 篇4
关键词：蛋白质二级结构预测,并行遗传算法,模式,疏水序列
0 引言
随着生物信息学的迅速发展, 有关蛋白质序列和结构的信息正急剧增长, 但是由于蛋白质结构解析所要求的实验条件比序列测定要严格和困难, 使得越来越多的已测蛋白质序列没有相应的确定结构信息[1]。最新资料显示, 2008年2月5日 UniProtKB/TrEMBL PROTEIN DATABASE RELEASE 37.8中有5 329 119条蛋白质序列, 而蛋白质资料库 (PDB, protein data bank) 中只有44 820 (其中X-ray为38 541, NMR为6 080, Electron Microscopy为112, Other为87) 条蛋白质结构信息。因此, 若已知蛋白质序列但不知其结构时, 需利用一些预测方法, 从蛋白质序列预测蛋白质的结构显得尤为重要。蛋白质结构一共分为四级, 其中三级和四级结构的预测建立在二级结构预测的基础之上[2,3]。所以, 蛋白质二级结构的预测成为研究蛋白质结构及其功能的一个关键问题。
目前, 各种不同的蛋白质二级结构预测方法可以分为3类, 即基于统计学的方法[4,5]、基于机器学习的方法[6,7]以及使用多序列排列信息的方法[8,9]。这些方法中普遍存在着计算复杂度较高[10]、对同源性低或非同源蛋白质二级结构的预测准确率较低的问题[11], 没有考虑影响蛋白质二级结构的因素, 如蛋白质序列两端氨基酸对中间氨基酸结构的影响, 蛋白质疏水性对二级结构的影响等缺陷[12]。
另外, 大多数蛋白质二级结构预测方法都属于黑箱分析方法 (也就是说, 输入一个蛋白序列, 则输出相对应的二级结构) , 而对序列与二级结构之间的关系研究较少。2003年, Chu Y.W.和Yang J.M.提出模式的概念描述序列和二级结构的关系[13], 之后为了寻找到有用模式, Huang H.C., Chu Y.W.和邹先霞先后利用遗传算法及其改进提取有用模式[14,15,16,17]。利用有用模式预测蛋白质二级结构预测准确率虽然不理想, 但是在低同源序列预测中有较好的表现, 预测准确率达到58%左右。虽然提取有用模式的遗传算法不断改进, 但仍存在着初始种群多样性较差、并行处理能力较差、适应度函数设计使得个体代表性和区分度差、预测准确率不高以及过于依赖数据集的规模等缺点。
本文针对现行研究工作中的不足, 对数据集和遗传算法进行改进和优化, 将聚类分析、并行处理技术和遗传算法相结合, 提出基于混合并行遗传算法的蛋白质二级结构预测方法。实验结果表明, 预测准确率至少提高了5%。
1 目标蛋白数据集预处理
本文采用在2006年3月发布的相似性低于25%的非同源蛋白质序列集Pdbselect25%。通过DSSP在线程序对其计算, 以提取氨基酸序列及其对应二级结构。二级结构为Q8形式, 将Q8简化为Q3形式: Helices包括G, H, I等3类, 记为H;Sheets包括B和E两类, 记为E;Coils包括S, T和C等3类, 记为C[18]。对Pdbselect25%中的蛋白质1GO1进行上述转化后的结果如图1所示。
考虑到各个氨基酸位点处二级结构主要是由于序列上相邻的、残基的局部作用而产生的, 所以每个氨基酸位点上的二级结构类型应当与它两侧相邻近的氨基酸的类型及性质相关, 如图2所示。图2是指中间的氨基酸L受到其两侧的氨基酸A的影响, 使得氨基酸L在二级结构中形成H结构, 即氨基酸L只受到其两侧氨基酸A的影响, 与其它位置上的氨基酸无关, 这就是本文所提取的模式形式。对每条蛋白质结构序列采用滑动窗口技术进行切片处理[19], 本文采用切片长度为9。在每一蛋白质序列中, 如果含有未知结构的氨基酸位点, 则在处理时舍去空位记录, 不计入蛋白质结构序列切片数据库中。对蛋白质结构序列1GO1, 以长度为9进行切片处理, 所得氨基酸序列转化为疏水值序列的结果, 如表1所示。
考虑蛋白质亲疏水性对蛋白质结构的影响, 疏水值序列在一定程度上反映了氨基酸序列所折叠成二级结构所需的作用力规则。按照如下原则:将氨基酸R, N, D, Q, E, H和K归为0级;将氨基酸C, I, L, F和V归为1级;将氨基酸G, P, S, T, W和Y归为2级;将氨基酸A和M归为3级[20]。通过这种转化以后, 问题已经转变为在疏水值序列中发现某几个位点。这些位置的氨基酸对于其二级结构的形成起主导作用, 即这些位置的氨基酸在某个化学性质上有一定的规律, 而其他位置的氨基酸对于其二级结构的形式不起作用或者作用较小。将蛋白质氨基酸序列转化为疏水值序列, 可以降低遗传算法搜索空间, 提高遗传算法搜索效率, 更主要的是考虑蛋白质亲疏水性对蛋白质结构的影响, 能够有效提高蛋白质二级结构预测准确率。
2 蛋白质二级结构预测算法
2.1 混合并行遗传算法
2.1.1 并行处理技术
本文采用分解型并行方法的步进模型。并行遗传算法第一步主要考虑按照某种原则将种群分群。本文主要利用每个长度为L的蛋白质结构序列切片来预测该切片的中心位点的二级结构, 因此考虑按照中心位点疏水值将种群分群。如果蛋白质结构序列切片长度为9, 那么每个子群搜索空间大小从49降为48, 进一步降低了搜索空间, 提高了运算率, 达到降低计算复杂度的目的。以蛋白质结构序列1GO1为例, 按照蛋白质结构序列切片中心位点的疏水值将种群分群, 分群结果如表2所示。
2.1.2 群体初始化产生
本文的模式提取是基于一定样本数据的提取过程, 因此要有一定的先验知识。群体初始化产生方法主要是一部分从样本数据集中选取一定代表性样本, 另一部分随机产生, 这样做可以提高算法初始群体的多样性。从样本数据集中选取一定代表性样本作为种群的一部分, 主要通过聚类分析K-CLARANS方法对每个子群的二级结构所对应的样本集进行分类, 从每类中选取一个中心点, 作为初始种群。
2.1.3 编码
本文所采用样本序列是蛋白质疏水值序列, 因此要设计疏水值序列的编码方式。考虑氨基酸的疏水级别为4级, 可以用两位二进制编码表示各个疏水级别, 同样二级结构为3模式二级结构, 可以用两位二进制编码表示各个二级结构。在这里, 由于二进制编码对应4个不同数值, 在进行产生初始种群时直接将反映二级结构位置的编码为00的个体删除。蛋白质疏水级别和二级结构具体编码如表3所示。按照表3将蛋白质疏水值序列进行二进制编码, 例如“300210230 H”编码为110000100100101101。
2.1.4 适应度函数
利用遗传算法对蛋白质二级结构进行预测, 适应度函数的设计主要体现个体代表性强和区分度好等特点, 利用已知结构的蛋白质序列的信息, 确定蛋白质序列的适应度函数。
为了能够使得个体代表性强、区分度好, 设计适应度函数时考虑两个函数自信度函数
undefined
式中 nH, nE和nC—该染色体的邻近样本在其对应的H, E和C组中相似性较高的数量。
鉴别率函数:undefined
式中 nHighest—其定义和上式的nmax相同;
nSecond—nH, nE和nC之中次高的数量。
综合考虑自信度和鉴别率两个函数, 确定混合并行遗传算法的适应度函数为
fitness=confidence*DR
2.1.5 其他遗传算子的设计
本文算子选取基于精英保留策略的轮盘赌选择, 交叉算子选取多点交叉, 变异算子选取分层次变异, 终止条件选取最大迭代代数。
2.2 模式提取算法
Step1:将已转换为蛋白质疏水值序列的样本数据集, 按照中间位置疏水级别分为4个子群, 对每个子群进行独立遗传操作提取模式规则。
Step2:根据分群后样本数据集, 产生初始群体。
Step3:对种群轮盘赌选择, 产生新种群。
Step4:进行多点交叉和分层次变异, 产生新种群。
Step5:从新种群选取适应度最高的个体, 存储在模式规则集合中。
Step6:随机产生一个个体共同构成子代 (新种群) 。
Step7:若不满足终止条件, 转到Step3;若满足终止条件, 则输出模式规则集合。
2.3 蛋白质二级结构预测算法
利用模式提取算法提取模式后建立模式集, 以此为参照对未知结构蛋白质序列进行二级结构预测, 具体算法步骤如下:
Step1:将未知二级结构氨基酸序列转换为疏水值序列, 对其进行蛋白质序列切片处理形成长度为L的蛋白质疏水值序列切片。
Step2:根据每个切片序列中间疏水值, 去寻找对应的模式规则集合。
Step3:计算未知结构序列切片与对应的模式规则集合的各个模式规则的相似性, 取其最大值。若该最大值大于所给定阈值, 则认为此未知结构的序列切片中间氨基酸为其所比对模式的结构;否则, 认为此氨基酸结构未知。
2.4基于混合并行遗传算法的蛋白质二级结构预测系统架构图
模式提取算法和蛋白质二级结构预测算法共同构成基于混合并行遗传算法的蛋白质二级结构预测方法 (PSSP-HPGA, Protein Secondary Structure Prediction based on Hybrid Parallel Genetic Algorithm) 。基于HPGA的蛋白质二级结构预测系统架构图如图3所示。
3 实验结果分析
对Pdbselect25%数据集采用PSSP-HPGA与其他随机搜索算法对其二级结构预测。其他随机搜索算法分别为基于遗传算法的蛋白质二级结构预测 (PSSP-GA, Protein Secondary Structure Prediction based on Genetic Algorithm) 和基于混合遗传算法的蛋白质二级结构预测 (PSSP-HGA, Protein Secondary Structure Prediction based on Hybrid Genetic Algorithm) 以及基于关联规则与遗传算法的蛋白质二级结构预测 (PSSP-ARGA, Protein Secondary Structure Prediction based on Association Rules and Genetic Algorithm) 。笔者从计算量和二级结构预测准确率方面加以研究。4种算法参数设置、计算量和预测准确率如表4所示。
在表4第3列中代表组内分类, PSSP-GA 和PSSP-ARGA在组内未采用分类方法。第4列中, 代表氨基酸序列转为疏水值, PSSP-GA 和PSSP-HGA未采用此种操作。从表4中可以看出:4种算法搜索空间大小逐渐降低, PSSP-HPGA搜索空间大小为48, 计算量较小, 有效提高运算效率和搜索空间的效率及二级结构预测的准确率。从表4中看出:随着各种手段的运用, 二级结构预测准确率不断提高, PSSP-HPGA可以达到62.1%。由以此验证了PSSP-HPGA的有效性、正确性和可行性。
利用PSSP-HPGA对1G01预测, 预测结果如图4所示 (下划线位点错误) , 对1G01预测准确率达到70.3%, PSSP-HPGA方法平均准确率在62%左右。通过实例验证了PSSP-HPGA方法的有效性。
4 结论
1) 提出了基于混合并行遗传算法的蛋白质二级结构预测方法。该方法应用混合并行遗传算法提取有用模式, 能够利用模式集合来预测蛋白质二级结构, 充分考虑蛋白质序列两端氨基酸对中间氨基酸结构的影响以及蛋白质疏水性对二级结构的影响。
2) 在整合和改进前人算法的基础上, 使得计算复杂度降低1个数量级, 预测准确率达到62%左右。
并行算法结构 篇5
用自适应伪并行遗传算法求解双准则三维运输问题
采用并行计算的思想,在单台计算机上应用自适应的`伪并行遗传算法,求解了双准则三维运输问题,最后通过实验验证该方法可产生适合需求的解,同时体现了该算法有较快的收敛速度.
作 者：张春梅 武钧 梁治安 ZHANG Chun-mei Wu jun LIANG Zhi-an 作者单位：张春梅,武钧,ZHANG Chun-mei,Wu jun(内蒙古大学,理工学院,呼和浩特,010020)梁治安,LIANG Zhi-an(上海财经大学,应用数学系,上海,33)
刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY 年，卷(期)： 37(11) 分类号：O1 关键词：伪并行 自适应 遗传算法 运输双准则并行算法结构 篇6
数学形态学用具有一定形态的结构元素去量度和提取图像中的对应形状,从而实现对图像的分析和识别。数学形态学处理在边缘检测、特征提取、图像分割、细节去除、孔洞填充等图像处理以及计算机视觉领域有着非常广泛的应用[1]。
形态学处理一般算法是将一个结构元素在二值图像上逐点移动,对每个像素点进行若干次逻辑判断从而得到处理结果。为提高形态学处理的运算效率,杨琨等提出利用结构元素在运算过程中存在的大量的重复运算区域,通过在后一次运算中使用前一次运算的结果来缩短运算时间的算法[2]。该算法具有理论基础简单,实现方便的特点,但是对于比较小的结构元素,性能提高不明显。陆宗琪等提出采用线段编码的方式,将当前线段与其相邻的上下线段之间进行逻辑运算,从而实现膨胀腐蚀运算[3]。该算法由于需要对二值图像进行额外的线段编码工作,导致对单个膨胀腐蚀操作效果的改善大打折扣,没有较为广泛的适用性。Cheng等通过检测二值图像的边缘,对边缘像素点进行操作来实现膨胀腐蚀的快速运算[4],对于边界比较复杂的情况,该算法的优化效果不好。Matthew J. Thurley等利用图形处理器( GPU) 的并行计算优势,采用CUDA这一NVIDIA推出的并行计算架构进行性能优化[5]。该算法对于分辨率较高的图像会有较高的性能提升,但是对硬件的要求较高,适用性不强。
本文将4 连通或8 连通结构元素分解为不同方向上的一维结构元素,利用分步的移位操作实现形态学腐蚀膨胀。同时利用二值图像的特点,即其像素值为0或者1,采用分段的方式,将相邻的若干个像素看成一个整体,通过并行操作实现算法性能提升。算法的速度可以提高4 ~ 6 倍,具有易操作适用性广泛的特点。
2 膨胀与腐蚀
定义1,作为Z2中的集合A和B,B对A的膨胀定义为
该公式可以等价表示为
式中: z表示结构元素的位移;表示集合B的反射集合。由定义得出的膨胀算法为将给定的结构元素在二值图像上依次平移,若该结构元素覆盖的原二值图像上有一个或多个点像素值为1,则将结构元素中心点所在的二值图像像素值赋为1,否则将该点像素值赋为0,当结构元素走完整幅图像时,便可以得到膨胀结果。
定义2,作为Z2中的集合A和B,B对A的腐蚀定义为
该公式可以等价表示为
式中: Ac是A的补集; Ф 是空集。
同理,由定义得出的腐蚀算法为当结构元素覆盖的二值图像像素值全部为1 时,将结构元素中心点所在的二值图像像素值赋为1,否则赋为0。由定义得出的形态学处理算法效率较为低下,原因在于需要遍历整个图像的每个像素值,对于每个像素值,仍需要进行一系列的逻辑判断才能得到运算结果。当结构元素较为庞大或者二值图像分辨率较高时,处理速度会变得尤其慢。此外,由于结构元素在二值图像上依次滑动处理每个像素,因而会有大量重复的逻辑判断,当图像前景区域比较大时,这些重复判断会造成更加多的资源浪费。
结论1,由定义可知膨胀和腐蚀关于集合求补运算和反射运算是对偶的,即
因此,可以利用相同的结构元素,使用B膨胀图像的背景( 即膨胀Ac) ,并将结果求补即可得到B对该图像的腐蚀结果。
3 基于分解的膨胀腐蚀快速算法
3. 1 基于分解的膨胀快速算法
3. 1. 1 算法原理
对于一幅需要进行形态学操作的二值图像,不需要对每个像素进行单独处理,而是可以利用一个无符号整数( unsigned int) 来表示连续的若干个像素值,这个无符号整数的每一位均代表原图中的一个像素点的像素值。因此,一幅M × N的二值图像可以按行表示为M个整数,其中每个整数都是一个N位的无符号整数。同理,也可以按列表示为N个整数,其中每个整数都是一个M位无符号整数。
本文将讨论4 连通和8 连通的结构元素,如图1所示。
对于4 连通的结构元素,可以将其分解为( 1 1 1)和( 1 1 1) ’两个方向上的一维结构元素,其中( 1 1 1) ’表示矩阵( 1 1 1) 的转置。( 1 1 1) 对原始图像的膨胀结果可以表示为将图像中每个像素值为1 的点的左、右像素点均赋值为1,这一步也可以通过将按行构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。( 1 1 1) ’对原始图像的膨胀结果可以表示为将图像中每个像素值为1 的点的下、上像素点均赋值为1,这一步也可以通过将按列构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。最后,将上述两个步骤得到的两个整数按位取或即可得到最终膨胀结果。4 连通膨胀算法流程见图2 所示。
对于8 连通的结构元素,同样可以将其分解为( 1 11) 和( 1 1 1) ’两个方向上的一维结构元素。( 1 1 1) 对原始图像的膨胀结构可以表示为将图像中每个像素值为1 的点的左、右像素点均赋值为1,这一步也可以通过将按行构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。( 1 11) ’对原始图像的膨胀结构可以表示为将图像中每个像素值为1 的点的下、上像素点均赋值为1,与4 连通结构元素不同的是,这一步需要将( 1 1 1) 对原始图像膨胀的结果按列构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。8 连通膨胀算法流程见图3 所示。
3. 1. 2 算法流程
根据上述原理,可以通过对按行或者按列构造的若干个整数进行位操作来得到最终膨胀结果。将若干个相邻像素点视为一个整体使用并行的操作方式可以提升算法的效率。
在本文中,对于一幅大小为M × N的二值图像,将每一行连续的32 个像素值作为一个整数,当N/32 不等于0 时,即每行像素值个数不是32 的整数倍时,在每行末尾补充32 - N% 32 个值为0 的像素,这样便可以将原始的M × N的二值图像分段成一幅M × ? N%32」的新图,该图中每个“像素值”均为一个32 位的无符号整数。构造过程如图4 所示,图5 显示了构造之前的图像和对应分段图。
同理,若将原始图像矩阵转置后进行如上操作,可以得到图像按列构造出的分段图。构造完二值图像对应的分段图之后,形态学膨胀腐蚀便可以在分段图上进行操作。4 连通和8 连通的膨胀快速算法见图6 和图7。在进行移位操作时,需要考虑相邻两个整数的边界位,即当x的最后一位为1,而x右边的整数y第一位为0 时,若需要进行右移移位,则需要将y的第一位置为1; 同理,当x的第一位为1,而x左边的整数z最后一位为0 时,若需要进行左移移位,则需要将z的最后一位置为1。
3. 2 基于分解的腐蚀快速算法
根据结论1,可以知道形态学腐蚀和膨胀具有对偶性的特点,因此为得到4 连通或者8 连通结构元素对一幅二值图像的腐蚀结果,将二值图像取反,然后进行上述膨胀操作,最后将得到的结果再次取反即可。由于二值图像取反操作也可以在分段图上进行,因此腐蚀快速算法的流程仍是建立在分段图之上的。
3. 3 性能比较
在Intel Core i5 - 3470 CPU @ 3. 2 GHz,4 Gbyte RAM,Windows8 32 位操作系统的硬件环境下进行实验。对不同分辨率以及不同纹理复杂度的二值图像进行了实验,采用的结构元素为8 连通结构元素,进行膨胀实验的原始图像以及最后结果见图8,性能比较见表1。由于运行时间与计算机速度、负载有关,因此本文中的数据取的是平均值。由于本文的快速算法只是对32 bit整数操作,并不关心整数的具体内容,因此二值图像的纹理复杂程度并不会对本算法的性能有较大影响。
4 结论
本文提出了一种基于结构元素分解的二值形态学并行快速算法。将结构元素分解为不同方向的一维结构元素,通过分步的移位操作实现形态学腐蚀膨胀。最后利用二值图像的特性,构造出32 bit整数形成的分段图,在该分段图上进行并行的位操作来实现算法的性能提升。该算法相比于传统的形态学处理操作,在性能上有了大幅提升。二值图像分辨率越大,本算法的性能提升越明显。同时,由于本算法只是对整数操作,并不关心整数的具体内容,因此,二值图像本身的纹理复杂程度并不会影响本算法的性能,这也是对一些需要首先进行边界检测的形态学处理方法的提升。
参考文献
[1]RAFAEL C.数字图像处理[M].3版.北京:电子工业出版社,2013.
[2]杨琨,曾立波,王殿成.数学形态学腐蚀膨胀运算的快速算法[J].计算机工程与应用,2005(34):54-56.
[3]陆宗琪,朱煜.数学形态学腐蚀膨胀运算的快速算法[C]//第十三届全国图象图形学学术会议.北京:清华大学出版社,2006:15-20.
[4]CHENG Xinyu.Fast binary dilation/erosion algorithm using reference points[C]//Proc.International Conference on Networking and Digital Society.[S.l.]:IEEE Press,2009:87-90.
并行算法结构 篇7
具有星上交换功能的卫星ATM系统是未来卫星通信发展的必然趋势。其宽带、高比特率、可灵活分配带宽等特点能够满足多媒体业务需求。在设计星上ATM交换结构时, 需要考虑卫星通信所具有的带宽有限、时延受限、信道误码率高等特点。同时, 随着组播业务的广泛应用, 卫星必须具备单组播并行交换能力。目前星上组播交换结构大多采用共享总线交换结构[1], 对处理速度要求很高且不具备阻塞规避特性。为此, 本文提出一种基于蚁群算法的星上ATM单组播并行交换结构。该结构是在Benes网络[2,3,4]中采用一种基于蚁群算法具有阻塞规避特性的单组播并行路由算法, 这种算法迅速探索并建立一个输入端口到一个或者多个输出端口之间的最优路径, 同时能够预测交换单元的阻塞状态, 快速探索新路径, 将流量分散, 达到减少内部阻塞的目的。
1 星上ATM交换结构简介
本文选用Benes网络作为星上交换结构是由于它具有多路径、交换单元数量少、容易操作且可扩展等特点。一个N×N Benes网络记作B (n) , 它有N个输入和N个输出, 共有2n-1级, 其中n=lg2N。如果采用2×2交换单元, 用2n-1位二进制数便可确定信元的整个路由。对于N×N Benes交换网络任一输入/输出端口之间有N/2条路径可供选择。交换单元采用带缓存交叉开关, 其中的交叉节点缓存可降低信元的阻塞率。文献[5]提出了一种组播复制Benes网络, 利用复制网络来完成组播信元的复制, 其组播复制算法比较复杂。本文所提出的星上ATM交换结构是在Benes网络中采用一种蚁群路由算法, 选择时延最小的无阻塞路径。
2 基于蚁群算法的单组播并行路由算法
算法的目标是快速找到最短时延路径和避免内部阻塞。前一目标是基于蚁群算法的泛滥技术以及一个相应的概率更新计算公式来实现的, 后一目标则通过对交换单元阻塞状态的预测来完成。算法的单组播并行处理是由交换单元中的信元复制功能来实现的。
2.1 蚁群算法简介
研究表明[6], 自然界的蚁群总能够在蚁巢和食物源之间找到一条最短的路径。当蚁群爬行时, 会在经过的路径上留下一种具有挥发性的物质——信息素。当一条路径上经过的蚁群越多, 留下的信息素就越强;而路径上的信息素越强, 吸引的蚁群也越多。这就形成了一种正反馈效应, 使得蚁群能够探索出一条最短路径。
蚁群算法是模仿蚁群寻路方式的一种启发式算法:网络中的每个节点将路由表以一张概率表替换, 表中记录着到达每个可能的目标节点下一跳选择各个相邻节点的概率。概率值相当于信息素的强度, 按照某种规律动态的调整。把概率表称为信息素表。当需要转发数据包时, 总是根据表中与数据包目标地址相对应的一条记录选择概率值最大的相邻节点作为下一跳, 对应到Benes网络中, 交换单元即为网络中的节点。
2.2 蚁群泛滥和概率更新
在Benes网络中, 称输入端口为源节点, 输出端口为目的节点。探索两节点之间的最优路径, 采用蚁群泛滥机制。一个源节点发送探测包——蚁群时, 将向它所有的相邻节点发送蚁群。相邻节点收到蚁群后将在所有的输出支路上复制发送蚁群。为了防止蚁群总数无限制的增长, 一个源节点发送的蚁群以及由它复制得到的所有蚁群都有一个相同的标识号, 这些具有相同标识号的蚁群称为同一批蚁群。每个节点第一次收到一批蚁群中的一只时, 将记录它的标识号, 并在所有链路上复制发送蚁群。当该节点再次接收到同一批蚁群时, 将不再对它进行复制。通过蚁群泛滥, 每个节点都能够收到蚁群, 并且到达同一节点的多只蚁群必然是沿不同路径到达的。
蚁群的作用是收集所经历节点的状态信息。每到达一个节点, 探测蚁群将更新该节点信息素表中目标地址为该蚁群目标地址的这一条记录中的概率值, 即增大选择该蚁群经历前一节点的概率, 而减小选择其他节点的概率。在初始化时, 信息素表中对于每个目标节点, 选择各个相邻节点的概率是相等的。蚁群行进中总是根据信息素表中记录的概率值随机选择一条路径。
概率更新计算公式要体现出寻路准则——最短时延路径。
信息素表中增大概率的计算公式为
减小概率的计算公式为
式中p
(3) 式中, f (d) 表示蚁群从源节点到当前节点所经历的时延d的增函数。当蚁群所经历时延越短, Δp的取值也越大, 选择这条路径的概率值增长越快, 或者选择其他路径的概率值减小越快。总之是使得路由选择更偏向于时延小的路径。
2.3 阻塞规避方案
在带缓存交叉节点交换单元里, 对阻塞状态的判定采用RED[7]相同的方法, 计算节点内缓存队列的平均长度, 并与上限和下限阈值比较。当一个节点发生阻塞时, 立即向所有路径经过该节点的源节点发送阻塞通告信息, 要求其探索新的路径。源节点接收到信息后, 开始进行新一轮的蚁群泛滥, 并避开所有阻塞节点, 实现流量的分散, 减缓阻塞状态。当阻塞节点变为空闲, 再通知源节点切回原来的路径。一旦某节点因发生严重阻塞而不得不丢弃信元时, 先丢弃低优先级信元, 再丢弃高优先级信元。
2.4 单组播并行机制
对于单播路由, 蚁群搜索的是一个输入端口对一个输出端口之间的最优路径;而对于组播路由, 蚁群搜索的是一个输入端口对多个输出端口之间的最优路径。在交换网络的输入端口, 当输入信元为单播信元时, 该信元按照蚁群路由表里的最优路径进行路由;当输入信元为组播信元时, 先根据组播路由表确定出组播输出端口号, 然后在蚁群路由表里选择前m个最优路由 (m为组播扇出系数) , 并根据该路由表在基本交换单元中对组播信元进行复制。
3 仿真结果
对本文提出的基于蚂蚁算法的单组播并行交换结构, 从两个方面来进行评价:信元平均时延和信元丢失率。交换结构的信元丢失率定义为交换中丢失的信元数与到达交换结构所有输入端口的信元总数的比值。信元平均时延定义为某业务的所有信元从交换结构输入端口到输出端口经历的时延平均值, 单位为时隙。交换网络负载定义为平均到信元数与时隙数的比值。
仿真时采用8×8 Benes网络, 该网络如图1所示, 其基本交换单元大小为2×2带缓存交叉开关。Benes网络由分配网DN和反向榕树网RBN组成。DN网负责蚁群泛滥和寻找最优路径。RBN具有自路由特性, 蚁群探测包在经过RBN网时可直接按照输出端口号进行路由, 不必进行复制。各交换单元的容量为4个信元单位, 即4×53×8 bits。组播扇出系数为2。
在仿真业务信源时, 采用了ON/OFF突发业务源来模拟两种实时业务:高优先级的CBR业务和低优先级的rtVBR业务, 其中突发业务的突发长度为10。每个输入信元的输出端口分布采用diagonal分布。组播扇出系数为4。
将本文的基于蚁群算法的Benes网络记为BABN, 将文献[5]中的组播复制Benes网络记为CBCN。比较在不同负载下的信元平均时延、总体信元丢失率性能和不同组播比例下的平均时延特性。图2是在组播比例为30%的前提下, BABN和CBCN中CBR业务与rtVBR业务在不同负载下的平均时延曲线。从图2中可以看到, 基于蚁群算法的星上交换结构由于具有动态寻找最短时延路径功能, 使CBR和rtVBR两种业务流的平均时延大大降低。图3是在组播比例为30%的前提下, BABN和CBCN中CBR业务与rtVBR业务在不同负载下的信元丢失率曲线。从图3中的结果可以看出, 基于蚁群算法的星上交换结构由于采用了阻塞规避机制, 使得阻塞概率降低, 从而减少了信元丢失率。
4 结论
本文提出一种基于蚁群算法的星上ATM单组播并行交换结构。该交换结构利用Benes网络的多路径特点, 采用蚁群路由算法快速寻找一个输入端到一个或者多个输出端口之间的最小时延路径, 同时能够预测到交换单元的阻塞状态, 迅速探索新路径, 分散流量, 达到减小内部阻塞的目的。通过仿真, 结果表明该交换结构可以有效的利用蚁群寻路机制来进行拥塞规避, 使其在信元平均时延和和信元丢失率性能方面比组播复制Benes网络具有明显的优越性, 非常适合应用到卫星上。
摘要：由于卫星通信具有带宽有限、时延受限、信道误码率高等特点, 因而设计星上交换结构时必须尽可能降低交换时延, 减少内部阻塞。同时, 组播业务的广泛应用使得星上交换需要具备单组播并行处理能力。为此, 提出一种基于蚁群算法的星上异步传输方式 (ATM) 单组播并行交换结构, 并对此方案进行了分析和仿真。结果表明, 该结构由于采用了蚁群算法和阻塞规避方案, 实现了单组播并行处理, 并有效改善了信元时延和信元丢失率等性能。
关键词：星上交换,单组播并行交换结构,蚁群算法,拥塞规避
参考文献
[1]Wassal A G, Hasan M A.Prioritised ATM switches on board satel-lites:architectural analysis and design.Communications IEE Proceed-ings, 2000;5 (147) :277—284
[2]顾沈明, 叶其宏.Benes网络中路径特性的探讨.浙江海洋学院学报 (自然科学版) , 2000;7 (19) :168—171
[3]顾尚杰.一种基于Benes网络的自选路无阻塞置换网络.上海交通大学学报, 1994;3 (28) :80—88
[4]Minzer S.Broadband ISDN and asynchronous transfer mode (ATM) .IEEE COM.Magazine, 1989;9 (27) :17—57
[5]Yun Deng, Lee T T.Crosstalk-free conjugate networks for optical multicast switching.Journal of Lightwave Technology, 2006;24 (10) :3635—3645
[6]Bonabeau E, Theraulaz G.Swarm smart.Scientific American.2000;6 (2) :74—79
并行算法结构 篇8
有限元网格生成是工程科学与计算科学相交叉的重要研究领域，在计算机辅助设计、科学计算可视化、计算机图形学、生物医学和有限元分析等领域有着广泛的应用。网格剖分做为有限元计算的前置处理技术，其运算的工作量在有限元计算分析过程中所占的比重非常大，此过程是否成功对后续的工作成果有重大的影响。本文中在保证网格质量的情况下，实现了基于三角形索引的Bowyer-Watson[1]三角剖分算法、基于Quad-Edge[2]结构下的三角剖分分治算法以及基于Map-Reduce[3,4,5]编程模型实现的三角剖分并行化并在大数据量的情况下进行测试，结果表明基于Map-Reduce编程模型实现的三角剖分并行化效率明显高于另外两个并且具有很好的弹性计算能力。
1 Delaunay三角剖分算法
在数值分析、图形学以及有限元分析中，三角剖分都是极其重要的一项预处理技术。而Delaunay[6,7]三角剖分是运用最多的三角剖分方法。其中Delaunay三角剖分必须符合两个重要的准则：第一，空外接圆特性，即在Delaunay三角网格中任意四个点不能共圆，同时任一三角形的外接圆范围内不能有其他的点存在；第二，最小内角最大，即在散点集形成的三角剖分中，所形成的三角形的最小角最大。在两个相邻的三角形构成凸四边形的对角线中，在相互交换后，六个内角的最小角不再增大。
2 基于三角形边索引Bowyer-Watson算法
基于逐点插入法[8]的Bowyer-Watson算法是基于Bowyer算法与Watson算法并在两者的基础之上进行改进而来的，因其简单易于实现而得到广泛的应用。此算法的思想是首先构建包含所有散乱点集的超级大三角形，然后选择其他未处理的离散点插入进来，在已经构成的三角形中查找这些三角形的外接圆包含这个新加入的散乱点的三角形，并把这些三角形删除掉，那么会形成一个包含这个新插入点的多边形，然后把这个点与多边形的各个顶点进行连接，从而构成多个新的三角形网格，重复这样的处理直到所有的点都处理完为止。此算法的相当大的时间损耗在了对空腔的查找，原始的算法要对形成的三角形进行遍历查找，而基于三角形边索引的方式则大大减少了对待插入点进行空腔查找的时间，此三角形边索引的结构如图1所示。
在对查找到的三角形进行保存的时候同时保存三角形的三个邻边三角形。如图1所示，在对Tri1的三角形进行保存的时候同时保存其三个邻边三角形，保存其边13的邻边三角形为Tri2,12边的临边三角形为Tri4,23边的邻边三角形为Tri3。这样在进行新点的插入寻找空腔时，只需要判断插入点与三角形链表中第一个三角形的关系，判断是在三角形内还是在某条边的一侧，如果在某条边的一侧那么对该边的邻接三角形再进行同样判断，如果在三角形内，那么对该三角形的三个边的邻边三角形依次判断待插入点是否在这些三角形的外接圆内，这样就会形成一个包围该点的空腔，将该插入点连接空腔的各个点形成新的三角形并做基于Delaunay优化准则的调整。
基于改进后的Bowyer-Watson大大提高了对包围待插入点的空腔的寻找速度，从而提高了三角网格剖分的速度。
3 基于Map-Reduce实现的三角剖分并行化
3.1 Quad-Edge结构介绍
Quad-Edge结构是由Guibas提出的一种处理点与Voronoi[9,10]图关系的数据结构，这种结构保存了Delau nay边与Voronoi边的对偶关系，使得基于Delaunay的三角剖分操作也相对容易得多，这种结构如图2所示。
在Quan-Edge结构中边next为以点origin为起点并且对与e(0)边的下一个边可以以逆时针方向找到，同时由于存储了Voronoi图的两边e(1)与e(3)，因此可以很容易从Delaunay三角网格图转换为Voronoi图。在本程序中，主要是用来对Delaunay边进行求解，所有都是为了简化处理去除了对应的Voronoi边。
3.2 Map-Reduce并行计算模型
Map-Reduce是一种目前在云计算平台上广泛使用的并行编程模型，主要用于对大规模数据集的并行计算，Map（映射）和Reduce（归并）是他的主要思想。Map Reduce主要是通过启动多个Task（任务），对不同的数据集进行处理返回相应Task的处理结果，然后对返回的结果集进行Reduce处理，从而得到最终的结果。从上可以看出，通过启动不同的Task数量可以很轻松地实现并行计算能力的提升，具有很高的弹性计算能力。
3.3 三角剖分算法基于Map-Reduce思想的实现
基于Map-Reduce并行编程思想的Delaunay三角剖分算法处理步骤如下：
第一步：输入散乱点集的坐标，记录相应点的坐标并根据x值将散乱点基于快速排序算法进行排序；
第二步：启动多个Task（任务）并对数据进行分块后分配给每个Task进行处理，在每个子集进行三角剖分的处理过程中使用Quad-Edge结构存储剖分的数据，对于剖分的子过程可以使用改进后的Bowyer-Watson算法也可以使用分治算法[11]，此程序在实现时使用的分治算法，并返回相应的剖分后的结果；
第三步：对返回的结果进行Reduce操作。对数据集进行合并时对于上下边切线的查找使用Zig-Zag[2]算法，当Reduce处理完成后返回结果即为三角剖分的网格。该程序通过基于Map-Reduce进行处理的流程图如图3所示。
该程序中使用的主要数据结构及算法简介如下：
/*定义边的关系，基于Quad-Edge进行改进，去除对应的Voronoi边关系*/
4 结果验证及分析
在本测试算法中采用C++分别对基于三角形索引的Bowyer-Watson三角剖分算法、基于Quad-Edge结构下的三角剖分分治算法以及基于Map-Reduce编程模型实现的三角剖分并行化进行实现。其中对Map-Reduce并行实现启动四个Task。通过随机获取散乱点集点数50～1 000 000个，分别通过以上三个程序进行处理的结果如表1所示。
通过表1看出，在对少量点集的运算时由于改进后的Bowyer-Watson算法处理完插点后要遍历三角形链表，对含有初始构建大三角形顶点的三角形进行删除操作，所以相对要慢些，同时由于Map-Reduce过程需要进行任务拆分合并需要消耗时间，效果也不会好于基于Quad-Edge结构的分治算法，但是当点集数量非常大时，基于Map-Reduce编程模型实现的三角剖分并行化要明显优于其他两个算法，在点数100万的时候速度是改进后Bowyer-Watson算法效率的7倍，同时也要比QuadEdge分治算法快得多，通过增加Task数量还可以进一步提高剖分效率。
图4是对含有1万个点的圆通过基于Map-Reduce编程模型实现的三角剖分并行化的剖分结果，从图四可以看出剖分后的网格很好的符合了Delaunay三角剖分的优化准则。
5 结语
本文通过使用Quad-Edge结构进行剖分结果的存储，并将Map-Reduce编程模型应用到三角网格剖分中，通过与其他两个方法对比证明此方法能够很好地提高三角网格剖分的效率，同时由于此编程模型具有很好的弹性计算能力，可以很轻松地通过增加task数量来进一步提高剖分的效率。如何将此并行编程模型应用到三维散乱点集中进行剖分处理，这将是要进一步研究的问题。
参考文献
[1]REBAY S.Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer-Watson algorithm[J].Journal of Computational Physics,1993,106(1):125-138.
[2]GUIBAS L,STOLFI J.Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams[J].ACM Transactions on Graphics,1985,4(2):75-123.
[3]YANG H,DASDAN A,HSIAO R L,et al.Map-reducemerge:simplified relational data processing on large clusters[C]//Proceedings of the 2007 ACM SIGMOD international conference on Management of data.[S.l.]:ACM,2007:1029-1040.
[4]DEAN J,GHEMAWAT S.Map Reduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
[5]CHEN S,SCHLOSSER S W.Map-reduce meets wider varieties of applications,IRP-TR-08-05[R].Pittsburgh:IRP,2008.
[6]武晓波,王世新,肖春生.Delaunay三角网的生成算法研究[J].测绘学报,1999,28(1):28-35.
[7]余杰,吕品,郑昌文.Delaunay三角网构建方法比较研究[J].中国图象图形学报,2010,15(8):1158-1167.
[8]刘云,夏兴东,黄北生.基于分治算法与逐点插入法的Delaunay三角网建立算法的改进[J].现代测绘,2010(4):14-16.
[9]FORTUNE S.A sweepline algorithm for Voronoi diagrams[J].Algorithmica,1987,2(1/4):153-174.
[10]HUANG Y,QIN H,WANG D,et al.Convergent adaptive finite element method based on centroidal Voronoi tessellations and super convergence[J].Communications in Computational Physics,2011,10(2):339-370.
并行谱聚类算法 篇9
关键词：谱聚类,相似性矩阵,并行
0 引言
聚类分析作为机器学习领域最为重要的一个研究方向, 在近30年间得到了快速的发展。在解决了各个领域的难题的同时, 聚类算法也发展出不同的算法家族。谱聚类算法因为其优点成为聚类算法中发展较快的一种, 并得到了学者们的极大关注。
谱聚类算法是一种点对聚类算法。其将数据看作图中的顶点, 数据间的某种关系看作图中的边, 从而将原始的聚类学习问题转化为图划分的最优化问题, 并依据谱图理论构建相似性图的拉普拉斯矩阵, 将原始的划分问题松弛为计算数据拉普拉斯矩阵的前k大的特征值及其对应的特征向量的问题, 从而简化了聚类求解的过程, 优化了聚类的质量[1,2,3]。
谱聚类算法最大的问题在于计算复杂度过高, 尤其在计算相似性矩阵及求取拉普拉斯矩阵的特征值、特征向量时, 消耗的时间最多。采用抽样的方法可以降低计算的复杂度, 但是当数据是海量的时候, 这种方法依然面临着计算的瓶颈, 因此本文采用并行的方法将计算分配到网络的计算机上, 从而加速谱聚类算法的收敛[4]。
1 并行计算
并行计算是指通过运行在多个通过某种网络连接起来的计算、存储部件上的较小任务的合作求解规模较大的计算问题的一种计算方法。这是一种随着技术进步及性能要求而发展起来的一种用于解决大规模数据计算和存储的技术。并行计算可以大大降低问题求解的规模及求解时间, 并且容错性更高、可用性更好、吞吐率更高, 因此并行计算的概念从刚刚提出即成为研究的热点。
并行计算的基本思想是分而治之[5]。分而治之是计算机算法中最古老最实用的一种算法, 其基本想法是将类似的工作划分为不同的子任务, 每次完成单个子任务, 从而降低计算的复杂度。在并行计算的系统中, 同样利用了这种思想, 其可分为两个部分:
任务并行。根据问题的特性, 把问题分解为类似的子问题, 分配到不同的处理器或者其他计算资源上处理, 从而提高计算资源的利用率。
数据并行。根据数据的存储结构, 把海量的数据分散到不同的存储设备上存储, 形成多个独立的数据存储区域, 实现数据的并行处理。
1.1 并行计算系统
根据弗林分类法 (Flynn’s Taxonomy) , 计算机按照其指令和数据的执行访问方式可以分为4类:单指令单数据计算机 (single instruction single data, SISD) , 单指令多数据计算机 (single instruction multiple data, SIMD) , 多指令单数据计算机 (multiple instruction single data, MISD) 和多指令多数据计算机 (multiple instruction multiple data, MIMD) 。其中SISD为串行计算方式, MISD仅是为了分类的完整提出的一种架构, 在实际中并不存在, SIMD具有部分的并行能力, 主要用在向量机中, MIMD结构中每个计算单元均有独立的指令及数据, 现行的并行计算系统均可归为此类。
在实际的应用中, MIMD结构按照系统内存的结构又可以分为两大类:共享内存和消息驱动[6]。共享内存方式对于内存空间进行统一的编址, 所有的计算单元均可以访问相同的内存, 不同的计算单元通过读写内存共享数据处理结果, 这种结构的通信机制简单, 但是不同的计算单元访问共享内存时需要加锁, 因此可能降低系统处理数据的速率。消息驱动的方式各个计算单元独享内存空间, 不同的计算单元通过某种网络结构连接, 通过发送消息的方式实现计算结果的共享, 这种结构对于内存的压力远远小于共享内存结构, 并且易于动态的改变整个网络的结构, 具有很好可扩展性, 但是整个系统的效率严重依赖于网络的通信能力, 并且系统的负载均衡及结构的设计均需要开发者完成, 导致设计这种结构的并行系统较困难。当前比较流行的共享内存式的并行计算系统有共享存储对称式多处理机系统 (Symmetrical Multi-Processing System, SMP) 、分布共享存储多处理机系统 (Distributed Shared Memory Multi-Processing System, DSM) , 消息驱动的并行计算系统有大规模并行计算机系统 (Massive Parallel Processing System, MPP) 、集群系统 (cluster system) , 下面对其特点一一分析。
SMP。在SMP结构中, 所有的计算单元共享相同的内存地址空间, 所有的计算单元可以直接访问内存的任意地址, 并且对于任意的计算单元, 其访问延迟、访存带宽均是相同的, 因此这种结构又被称为统一内存访问 (uniform memory access, UMA) 。SMP系统的特点是系统中的计算单元的总线结构是相同的, 并且地址空间编码一致, 不同计算单元间通信仅通过读写内存即可以完成, 因此SMP系统的通信延迟很小, 访存带宽较高, 同时SMP系统往往仅运行一个操作系统的实例, 因此易于根据不同计算单元的繁忙程度实现系统的负载均衡。公用访存总线和内存空间虽然带来了通信开销较低的好处, 但是这种方式的可用性较差, 易于导致内存访问的竞争, 并且一旦存储器或者访存总线出现问题, 将导致整个系统无法使用, 并且当扩展系统规模时, 难以设计交叉开关, 因此导致系统的可扩展性较弱, 一般情况下SMP系统中计算单元的数目不超过64个, 这也决定了SMP系统仅适用于计算规模较小的环境。在实际中, SMP系统常见于小规模并行计算机中, 如IBM50, 曙光一号。
DSM。DSM结构中内存在物理上属于不同的计算单元, 但是在逻辑上共享相同的地址编码空间。在这种结构中计算单元对于不同的内存空间的访问速度是不同的, 计算单元通过本地总线访问本地内存, 通过系统总线访问其他地址空间上的内存, 因此导致访存的速度不同, 所以这种结构也被称为非一致内存访问 (non-uniform memory access, NUMA) 。DSM结构屏蔽了系统中计算单元同非本地内存间通过网络的物理结构, 提供统一的编程模式, 大大降低了DSM系统开发的难度。同时系统可以通过网络接入更多的计算单元, 具有较高的可扩展性。DSM系统兼具共享存储结构和消息驱动结构的优点, 因此具有极高的使用价值。
DSM系统通过系统总线访问非本地内存, 其速度严重依赖于共享总线的带宽, 这也导致不同位置内存访问速度的不同, 一种可行的解决办法是加入一致性高速缓存 (cache-coherent) , 采用基于目录的方法维护缓存的一致性, 这是一种常用的DSM结构。
MPP。MPP结构往往包括成百上千的计算单元, 每个计算单元均有自己独立的总线及内存空间, 不同的计算单元间通过专用的网络连接, 计算单元间通过消息共享计算结果和数据。MPP结构的系统具有很强的计算能力和存储能力, 并且可扩展性很高, 容错性能很强, 某个计算单元发生故障不会导致整个系统失效。但是MPP系统采用专用的网络连接, 需要提供专用的通信部件才能实现较高的通信效能, 导致这种系统的研发、维护和使用的开销极高, 因此MPP结构的并行计算系统往往为国家主持开发和使用的。比较著名的MPP系统有IBM SP2和曙光1000。
集群系统。集群系统中每一个计算单元均是一个独立的计算机, 每个计算单元均有独立的CPU、内存和总线系统, 不同的计算单元通过互联网连接, 每一个计算单元均可以独立工作, 也可以协同完成比较复杂的工作。集群系统的结构灵活, 可扩展性极强, 易于更换或者增加节点, 并且集群系统中每一个节点均是独立的计算机, 因此单个节点的失效不会导致整个系统的失效, 具有极高的鲁棒性和恢复能力。相比于MMP系统采用专用通信网络和专用计算机, 集群系统采用互联网通信和普通的计算机, 因此其具有很高的性价比。
集群系统最大的瓶颈为通信开销过高, 并且系统效率严重依赖网络的吞吐率, 如何设计高效低价的通信系统是所有集群系统必须考虑的问题。其次集群系统需要合理的调度计算资源, 因此严重依赖于负载均衡算法的调度。
1.2 并行计算编程模型
上小节中介绍的是并行计算不可或缺的底层的硬件平台, 本节分析当前比较流行的并行计算编程模型。
当前最重要的并行编程模型共有两种, 其一为消息传递, 其二为数据并行。数据并行编程模型编程较为简单, 这种编程模型提供了一种全局的地址空间, 通过指定并行操作的对象即可以实现并行化的编程, 但是这种模型仅仅适用于特定的并行计算系统, 因而应用的范围并不广泛, 常用的有Open MP (Open Multi-Processing) 。消息传递并行编程模型编程较为复杂, 需要开发者控制不同进程间的消息的传递、协调进程的执行, 但是可用于的并行系统极多, 不仅仅可以用于消息传递的并行系统, 也可以用于共享内存的并行系统, 因此得到了更多的关注, 常用的消息传递编程模型有MPI (Message Passing Interface) 、MAP/REDUCE等[6]。下面对这些编程模型进行详细的讨论。
Open MP。Open MP是用于共享内存并行计算系统的一种并行计算编程模型, 它支持在多处理机上编写并行程序, 利用共享内存结构的共享内存空间地址的特性, 高效的实现了程序的并行化。Open MP编程模型包括三部分:运行库 (runtime library) 、环境变量 (environment variable) 和编译器指令 (compiler directive) 。Open MP通过环境变量及编译器指令指示编译器如何并行化程序, 并提供了运行库支撑并行系统的运行。
Open MP编程模型简化了并行编程的难度, 开发人员仅需很小的学习曲线即可以掌握高质量的并行算法设计方法, 并且Open MP的库函数对开发人员屏蔽了底层的并行粒度、负载均衡等并行系统需要解决的难题, 因此可以使得开发人员将精力投入到算法设计本身, 降低开发的代价。同时Open MP作为一种开放的并行计算模型得到主流的计算机硬件软件厂商的支持, 因此采用Open MP的并行程序具有极好的可移植性。但是Open MP编程模型仅仅支持共享内存结构的并行计算系统, 这限制了它的使用范围。
MPI。MPI是一种基于消息传递的并行化编程模型, 是用于非共享式内存并行计算系统的编程接口的标准定义。MPI以较低级的消息传递的方式同步不同计算单元的计算结果, 协调计算单元的负载, 编程形制较Open PM灵活, 并且MPI在当前流行的PC系统中都有相应的实现, 因此具有很好的可移植性和广泛的适用性。此外MPI提供了语言无关的编程接口, 通过函数库的方式实现相应的功能, 因此不需要编译器的直接支持, 这使得MPI程序具有很好的跨平台的特点, 简化了开发人员的学习过程, 因此MPI并行编程模型成为当前最为流行的并行编程模型之一。
虽然MPI编程模型具有非常广泛的适应性, 但是其仍然存在不少的问题。MPI需要开发人员自行解决通信和资源调度的问题, 增大了开发的难度, 并且对MPI程序的调试比较困难, 当系统中某个进程失败时, 将导致系统的崩溃, 鲁棒性不如Open MP模型。
MAP/REDUCE。MAP/REDUCE并行编程模型是谷歌公司最早提出的, 用于解决海量数据环境中大规模计算的问题。MAP/REDUCE编程模型将计算过程分解为了MAP和REDUCE两个阶段[7], MAP阶段根据数据键值归类成不同的分组数据, 经过调度和洗牌后, 不同的分组交由不同的REDUCE程序进行处理, 并通过合并得到最终的结果。MAP/REDUCE并行编程模型将负载均衡、联网通信等复杂的底层实现隐藏在系统的内部, 对外部提供了统一的编程接口, 开发人员只需要实现Map函数和Reduce函数即可完成并行计算的任务。
MAP/REDUCE并行编程模型适用于内部松耦合的任务, 对于这种任务可以高度的并行化, 现在已经实现的云计算平台多采用这种编程模型, 并且模型对于异构的集群系统具有很好的适用性, 部署的代价极低, 因此MAP/REDUCE并行编程模型成为当前最为流行的并行编程方式。但是MAP/REDUCE并行编程模型对于紧耦合的任务无法很好的处理, 计算过程相当繁琐, 并且由于计算过程中需要对中间结果进行归并分组, 因此系统对于通信网络的依赖极重, 其通信效率严重影响系统的性能。图5.3展示了MAP/REDUCE的一般流程。
2 并行谱聚类算法
本节讨论如何利用MAP/REDUCE框架在集群上实现并行化的谱聚类算法, 并通过在图片数据集上的实验验证算法的有效性。
整个计算过程在Hadoop环境下实现, Hadoop是MAP/REDUCE框架的一个开源的java语言实现。
Hadoop框架将计算同数据分离, 底层为分布式文件系统Hadoop Distributed File System (HDFS) , 它负责存储系统中所有的数据, 上层为MAP/REDUCE计算引擎, 负责计算任务的执行。HDFS系统及计算引擎均采用主从结构, 在HDFS系统中主节点被称为Name Node, 负责决定文件块由那些节点存储以及跟踪整个系统中文件存储的整体情况, Data Node节点负责系统中真正的文件的读写以及存储工作。计算引擎通过Job Tracker进程分配计算任务给集群中的节点, 而Task Tracker负责节点中计算任务的执行。Hadoop框架的典型架构如图4所示:
谱聚类算法可以分为三个阶段:预处理阶段, 特征分解阶段和聚类阶段。预处理阶段主要实现计算相似性矩阵和拉普拉斯矩阵, 特征分解阶段主要实现特征值及特征向量的计算并拣选前k小的特征值对应的特征向量作为最终降维后的数据集表征, 聚类阶段利用k-means算法实现最终的聚类。因此, 并行算法的设计可以从这三个阶段着手。
预处理阶段。当数据量规模较大时, 单个计算机的内存很难将所有内容装入内存, 因此可以利用MAP/REDUCE框架将计算分布到不同的机器上去。假定集群中机器的数量为m, 首先将整个数据集平均的分配到m台机器上, 每台机器计算N/un个数据的相似性关系, 并计算相应的度矩阵及最终的拉普拉斯矩阵。基本思想如图5所示:
在每台机器上均有一份完整的数据备份, 这可以减少计算时网络中数据的交换流量。每台机器中完整的数据文件并没有完全装入内存, 而是分片读入的, 这样可以减少计算所需要的内存空间。
计算相似性矩阵的过程实际上分解为两个阶段:第一个阶段为计算相似性值阶段, 第二个阶段为对称化相似性矩阵阶段。
首先进行的是第一个阶段。由于文件中的每行数据表示一个数据点, 因此按照MAP/REDUCE的思想, 首先MAP阶段根据数据行在文件中的偏移将数据读入内存中, 然后根据数据所处行号的不同映射到不同的机器上。在REDUCE阶段, 对每行数据分别计算其同其他数据间的欧氏距离, 并按照其大小关系选择最小的k个保留下来, 这一步为了减少内存空间的使用, 可以仅仅预留前k小的数据的一个有序序列及其所对应的下标, 然后对这前k小的数据计算其相似性, 并在写入文件时将同其他数据间相似性值置为0, 并写入文件中, 写入文件的格式为 (相似矩阵行号, 列号, 值) , 同时为了将其对称化, 每个非零行交换行号、列号后写入两次, 这个阶段完成了基本相似性矩阵的计算, 但是这样得到的相似性矩阵并非对称的, 因此在第二阶段将相似性矩阵对称化。
第二阶段以计算相似性矩阵第一段的输出作为输入, 在MAP阶段以输入文件中的相似性矩阵的行号及列号域作为key值, 相似性值作为值域进行映射, 在REDUCE阶段key域同MAP阶段, 值域为MAP阶段值域的均值, 然后写入文件, 写入文件的格式为 (相似矩阵行号, 列号, 值) , 在完成这两个阶段后得到相似性矩阵即是一个对称的稀疏相似性矩阵, 最终的输出存在不同的节点上。
特征分解阶段。由于预处理阶段得到拉普拉斯矩阵为稀疏对称半正定阵, 因此可以利用Lanczos方法计算特征值及特征向量。Lanczos方法是一种迭代的算法, 首先通过Lanczos迭代计算出一个对称的三对角矩阵T=CTLC, 其中C为迭代过程中得到转移矩阵, L为拉普拉斯矩阵。通过QR方法求解T的特征向量ui, 那么L矩阵的特征向量vi可以通过下式得到:
由于T矩阵的规模远远小于L的规模, 因此整个求解过程计算量最大的是Lanczos迭代过程, 并行化的重点也在这一阶段。
Lanczos迭代过程如算法1所示:
算法1 Lanczos迭代过程
在预处理阶段得到的拉普拉斯矩阵是分布存储在集群上不同的节点, 因此只需要将初始化步骤中得到C0、C1按照预处理阶段数据的分布方案分配到节点去, 然后在每个节点上计算Step 2中的步骤a和b, 最后将各个节点上对部分的aj值的计算加起来, 即可以得到aj, 按照相同的原理计算βj+1, 并在主节点生成CT, 这样即可以完成迭代过程的并行化, 在得到T矩阵后, 然后利用QR分解得到T的特征矩阵, 并将其分配到不同的节点计算L矩阵的特征向量, 并存储在各自的节点上。
聚类阶段。此处采用与计算相似性矩阵时相同的策略, 首先将特征分解阶段得到的前k小的特征值对应的特征向量通过网络传播到每个节点, 然后分割计算任务到各个节点, 每次迭代产生新的聚类中心通过Job Tracker传播到整个网络, 并参与下一轮的计算直到计算过程收敛。
下面分析并行算法的计算复杂度。计算相似性矩阵的第一个阶段的计算复杂度为O (n2) , 其中n为数据点的个数, 对称化阶段的计算复杂度同样为O (n2) , 因此整个阶段的计算复杂度为O (n2) , 整个计算非配到m台机器上去, 因此该阶段的计算复杂度为
采用Lanczos方法计算特征向量所需的时间复杂度为O (k·n2) , 但是由于相似性矩阵及转移向量均是分布在不同的机器上, 因此最终的计算复杂度为:
k-means聚类阶段同样是分布在不同机器上进行的, 因此其计算复杂度为:
因此整个算法的计算复杂度为:
3 实验
实验环境为hadoop集群, 集群中共有三台机器, 每台机器的内存为512MB, CPU为1GHZ、单核, 集群中有一台机器作为中心节点, 并且其本身也参与计算与数据的存储。
实验数据集为来自Corel图像数据集中的5000幅图像, 这些图像共分为35类。每幅图像的色度表示分成了12个格, 并在其上分别计算其颜色直方图、均值、方差等9种颜色特征, 得到一个108维颜色特征向量, 此外将图像纹理通过DWT滤波得到9种子图组合, 并计算每种组合的均值、方差等特征, 得到一个36维的纹理特征向量, 并将二者组合起来表示一幅图像, 因此每幅图像采用一个144维的特征向量表示。
下面为并行谱聚类算法加速的对比:
(单位:秒)
上表的计算结果为3次实验的平均值, 近邻数设置为10, 高斯函数的调节参数设置为5, 类别数设置为35, 特征分解阶段Lanczos生成的转移矩阵的秩同聚类数, k-means聚类阶段迭代次数最大设置为1000。
从表中可以看出, 当增加集群中机器的数目时, 程序整体运行的时间将会减少。但是由于存在网络通信以及Hadoop系统本身会带来一些时间开销, 因此算法计算复杂度的减少并不像理想情况下为线性减少的。同时由于在构建相似性矩阵的阶段job划分较小, 导致Hadoop系统开销过大, 因此使得其加速的效果并不是那么理想。
图6展示采用一台slave与两台slave消耗的时间对比及加速比。图中左侧子图为程序消耗的时间, 左侧图中第一组数据位slave为1台时的结果;右侧子图为加速比, 依次为相似矩阵构建、特征分解、kmeas和总时间的加速比, 加速比的计算方式为:
从图6中可以看出采用更多的机器时可以很好的提高算法的计算速度。
4 结论
本章首先介绍了并行计算的硬件环境以及常用的并行计算模型, 然后在MAP/REDUCE环境下实现了谱聚类算法的并行化, 验证了并行环境对于解决大规模数据处理的有效性和可行性。
在Hadoop环境中构建相似矩阵的过程较为耗时, 因此希望在未来的研究中找到一种较好的映射方法, 改善算法的效率, 提高算法的性能。
参考文献
[1]Donath, Hoffman.Lower bounds for the partitioning of graphs[J].Res Develop, 1973, 17:420-425.
[2]M.Fiedler.Algebraic connectivity of graphs[J].Czechoslovak Math, 1973, 98 (23) :298-305.
[3]Wu, Leahy.An optimal graph theoretic approach to data clustering:theory and its application to image segmentation[J].IEEE Trans on PAMI, 1993, 15 (11) :1101—1113.
[4]Luxburg.A tutorial on spectral clustering[J].Statistics and Computing, 2007, 17 (4) :395-416.
[5]孙世新, 卢光耀, 张艳.并行算法及其应用[M].北京:机械工业出版社, 2005:5-10.
[6]李建江, 薛巍, 张武生, 张卫华.并行计算机及编程基础[M].北京:清华大学出版社, 2011:6-9.
并行机调度遗传算法研究 篇10
并行多机调度问题是NP-Hard问题，它既有丰富的研究内容，同时在生产调度，机械制造等方面有广泛的实际应用价值。但是在实际操作中，人们常常按经验法则 (如处理时间短优先调度或到期日早优先调度) 进行调度，这样得到的调度结果一般不能满足实际环境的需求，而且当并行机数和工件数增加时，问题的复杂度成指数增加，传统方法不适合解决此类问题。目前的并行机调度问题研究大部分是集中于简化问题，然后寻找最优解或次优解。
如何使并行机调度问题更接近实际生产状况并找到次优解成为本问题研究热点之一。遗传算法由于其固有的全局搜索与收敛特性，能够较好地解决此类优化组合问题。用遗传算法解决并行机调度问题已经有相关研究，其中Cheng提出一套方案，利用特殊符号 (*) 和工件号组成染色体，特殊符号为分隔符，将工件分成不同的组，每个工件组指派到不同的并行机中。本文对Cheng的方案进行了改进，并且把工件延迟与提前完成成本、机器闲置时间成本和机器设备启动成本等列入考虑因素，使多机调度问题的解决更接近实际的生产状况，目的在于求得考虑实际因素下的次优调度结果，以降低存货存储、交货延迟的违约、设备及人力等成本。
（二）遗传算法与并行机调度问题
1. 遗传算法
遗传算法是一种模仿自然界中优胜劣汰自然选择规则的随机搜索方法，该算法是从一系列的初始点 (被称为初始种群) 开始，通过循环执行选择、交叉和变异等遗传操作，逐步得到问题接近全局的最优解。
2. 并行机调度问题
考虑并行机调度中的实际需求定义如下并行机调度问题：设有m (m>1) 台并行机M1, M2, …Mm，需要加工n个工件，F时调度工作结束，每个工件订单零时刻到达，可在任一台机器上完成加工。工件一旦分配给某机器加工就必须加工完毕，不许中断。工件i在机器j上加工前准备时间为Zij，加工时间为Tij，工件i的到期时间为Qi，机器j一天的工作时间为Wj，启动成本为Sj，闲置成本权重比例为Rj，则工件i的完成日期Ci为本身加工前准备时间Zij (j为工件i的加工机器) 、加工时间Tij与机器j中i工件之前所有工件消耗时间之和，提前完成时间Bi为max (0, Qi-Ci) ，延迟时间Di为max (0, Ci-Qi) ，机器j的闲置时间为Ij (F减j上最后一个工件完工时间) 。问如何安排每台机器上所加工的工件及加工顺序使成本最小。
（三）算法设计
在Cheng的方案基础上，提出了一个染色体的改进的编码组成方式，重新设计了适应度函数和进化机制。
1. 染色体编码与适应度函数设计
并行机调度问题的染色体必须表示两个方面的信息：一方面确定工件加工所在的机器，另一方面确定每台机器上工件的加工顺序。本算法中染色体编码时用自然数序列表示工件排列，用含数字下标的分隔符*i (0
遗传算法演化过程的目的在于使适应度函数最小化，如果用B, D, S, I分别表示提前、延迟、重启和闲置成本，则演化的目的是要找到最好的排列使得：
F (B*, D*, S*, I*) =min{F (B, D, S, I) }, 适应度函数为F,
Bi, Di, Sj, Rj, Ij意义同上，α (Bi) , β (Di) 分别为提前和延迟完工成本函数，γj的值在机器j上有工件分配时等于1，否则为0。
2. 种群初始化
初始种群的个体分为两类，第一类个体随机生成;另一类个体可以按一定经验法则生成，比如可以把处理时间作为考虑因素，处理时间越短越先安排，确保在最短的时间里做尽可能多的工件，或者按到期日期为标准，越早到期的工件越早安排，可以使大部分工件如期完成。
3. 选择
选择过程的目的是为了从当前群体中选出优良个体，使他们有机会作为父代将其优良的个体信息传递给下一代，使子代向最优解逼近[1]。判断个体优良与否的标准是各自的适应值。每个个体的选择概率采用基于排序的适应度分配 (rank-based fitness assignment) 方法，种群按适应度进行排序，个体的生存概率使用Baker提出的线性排序计算公式求得：其中i为个体排序序号，N为种群大小，1<=η+<=2, η–=2–η+。然后用轮盘赌选择法 (roulette wheel selection) 来决定每个个体的选择份数，选择后的N个个体送到配对库，以备配对繁殖。
4. 交叉
交叉是结合来自父代种群的信息产生新的个体，依据个体基因编码表示方法的不同有多种交叉算法。这里采用两点顺序交叉 (OX) ，顺序交叉能够保留排列并融合不同排列的有序结构单元。如有下面两个父个体，交叉操作步骤如下：
(1) 随机选择两个交叉点”|”，保留交叉点之间的中间段不变。
(2) 把父个体2从第2个交叉点作排列，到达表尾时返回表头继续，得到排列*3 2 7*4 8 4 1*2 5*1 3 6，减去父个体1中已有基因部分4 5*1*3 2得到排列顺序7*4 8 1*2 36，再将这个顺序从第2个交叉点开始复制给子个体1，以此决定子个体1对应位置的未知码x，生成子个体1即q1: (3 64 5*1*3 2 7*4 8 1*2) ，同样产生子个体q2: (*3 2*2 5*13 6 7*4 8 1 4) 。
5. 变异
变异是子代基因按小概率产生的变化。同样可以采用多种方法实现基因变异，如可以采用交换两个基因位置实现变异，但是这种方法个体变异较小，不利于新个体的生成，特别是当交换的两个基因都是数字时，新个体只是改变了两个工件的加工位置。这里使用另外一种方法实现变异操作即首先随机选取父代中的某优秀染色体，对照染色体基因个数 (m+n) 随机生成一个二进制序列，将染色体中对应0的基因选为一组，对应1的基因选为另一组，两组基因重新组合得到子个体。变异操作如下：
6. 种群进化与停止准则
标准遗传算法若在群体选择前 (或后) 保留当前最优值，则最终能收敛到全局最优值。本算法通过改进标准遗传算法，在群体选择作用前保留当前最优解，则保证本算法在某些情况下收敛到全局最优解。
停止准则一般预先设定一个最大的繁殖代数Nmax，在繁殖过程中进行到最大的繁殖代数则停止运行。
综上所述，本并机行排序问题的遗传算法伪码如下：
（四）结果
设有45个工件要在3台机器上加工。在工作提早与延迟完成成本方面，按照工件的重要性将提前与延迟完成成本公式分为三类：
对重要性不高的工件成本公式为：
对重要性一般的工件成本公式为：
对优先权高的工作成本公式为：
工件在不同机器上的加工时间，加工前准备时间，机器启动和闲置成本表略。种群大小为50，最大遗传代数为80，交叉概率为0.6，变异概率为0.01。按本文与Cheng所提算法分别演算，所得结果如表1所示：
由表1可知，本文算法有助于使最后解答的染色体之间的差异性小，每次运算后的解接近最优解。
（五）结束语
本文重新设计了染色体的组成方式，问题的解空间表示得更明确，设计了算法进化机制，求解效率得到提升，考虑了并行机调度问题中的更多实际因素，本算法有一定的实用价值。然而实际影响并行机调度的因素并不限于本文所讨论的范围，另外适应度函数中的权重比例，也需要根据不同工厂的需求做适当的调整。今后将研究影响并行机调度的其它一些因素，使并行机调度问题与实际应用紧密结合，并且考虑把遗传算法与其它算法结合，使遗传算法收敛更快更高效。
摘要：为解决接近实际生产状况的并行机调度问题, 将工件延迟与提前完成成本、机器闲置时间成本、机器启动成本列入考虑因素。在遗传算法的设计上, 提出了一套染色体的组成方式, 设计了适应度函数和进化机制, 使其能较好地表示问题的解空间并提升求解效率, 具有一定的实用价值。
关键词：并行机调度,遗传算法,适应度
参考文献
[1]何军辉, 周泓.求解含调整时间并行机排序问题的遗传算法[J].系统工程理论方法应用, 2002, 12.
[2]欧锦文, 施保昌.平行机排序邻域搜索算法设计[J].计算机工程与应用, 2003, 18.
[3]Cheng, Runwei.Minmax Earliness/Tardiness Scheduling in Identical Parallel Machine System Using Genetic Algorithms[J].International Conference on computers and industrial Engineering, 1995:29:513-517.
[4]张聚, 李平.基于演化算法的车间作业调度问题的求解方法[J].浙江大学学报, 2004, 12.
