并行分析算法（精选九篇）
并行分析算法 篇1
在过去计算机并行处理技术发展缓慢, 主要原因是计算机电子设备处理器价格比较贵, 网络通信处于前期发展阶段不太成熟, 使用并行技术开发的软件功能和应用上不完善。在20 世纪后期, 随着网络通信技术的迅速发展, 高位数处理器的开发和应用, 给并行处理技术提供了很好的发展空间。在计算机产业中, 人们意识到计算机的处理计算的能力在高科技的技术发展中被人们越来越重视, 并行处理技术是高性能计算机处理技术未来主要技术, 并行处理技术可以大大提高计算机的整体性能。 现代科学技术和全球经济的发展都离不开计算机技术, 计算机技术已经改变了人们的生活方式, 存在各个领域, 计算机技术的发展比其他科学技术的发展要快, 对人类的影响比较深远。 工程领域对计算机计算的需求是无限的, 然而计算机的单机计算是有限的, 这两个关系决定了分布式并行计算方法必然称为计算机计算方法的主导。
2 研究现状
国内在国防和国家科技的建设上, 并行处理技术起着重要作用, 我国对高性能计算机的发展非常重视, 尤其在石油、气象、 航空等大范围领域的研究逐年增加, 我国在并行处理技术领域比其他领域发展显著主要是因为并行处理技术领域的高性能计算机。 国内的科技工作者正努力研究多种并行处理的计算方法, 软件发展的重心主要体现在算法能力上面, 我国研发的数据库并行处理系统处于世界同领域的领先地位, 并行体系结构、 并行系统软件、 并行算法是并行处理技术的3个方面, 我国在高性能计算机的研制方面投入多, 在系统开发方面投入较少, 低成本延迟高带宽、 并行应用软件和并行算法是我国研发的重点。
国外美国、 日本在并行计算方面发展出力领先水平, 美国在商业领域已经应用高性能计算, 并行检索技术, 在并行计算方面的研究资料国外设计的也比较全。 国内外差距大, 我国发展高性能计算机技术不能再等, 算法是研究的重要内容。
3 并行计算机分类和计算环境
3.1 并行计算机的分类
并行算法能够运行的基础主要是并行计算环境和并行计算机, 并行算法的设计和实现取决并行计算机环境和并行计算机, 并行计算机从最初的向量机, 如今并行计算机主要是机群系统, 并行计算机分为SIMD型并行计算机、 共享存储MIMD并行机、 分布式存储MIMD并行机、 分布共享存储MIDI。
SIMD型并行计算机是单指令流多数据流并行机, 在指令流执行的时候, 处理机对多组数据执行相同指令流, 也就是说SIMD并行机无论怎样运行它的指令只有一条, 同步性、 确定性是SIMD型并行计算机的特征, SIMD型并行机已经不能满足并行技术的发展, 是早期产品, 如今已经不被使用。
共享存储MIMD并行机是多指令流多数据, 所有处理机执行统一程序, MIMD并行机是现在并行算法中普遍使用的编码方式。
分布式存储MIMD并行多处理机解决了共享存储MIMD并行处理机的瓶颈问题, 在整个系统中, 每个节点都有自己的存储器, 在访问的时候只能自己访问自己的存储器, 不能互相访问, 各个节点通过网络作为传输介质连接到一起, 分布式存储扩展性强, 但是编程复杂, 在节点之间的信息传递不是通明的, 分不知存储MIDI并行处理机分两类, 大规模处理机和群集系统。
分布共享存储MIDI并行机在系统中每个处理机有自己的存储器, 共享地址空间由各个局部存储器连接组成。
3.2 并行计算机的计算环境
并行计算机体系结构, 并行算法的效率直接受并行计算机体系结构的影响, 在这个系统中处理机的连接方式构成并行计算机体系结构。 并行处理机互连方式主要是网络直径和等份宽度两个重要因素。 网络系统中两个距离较远的处理机之间的具体构成网络直径, 两个距离远的处理机在消息传递的时候出现时间的延迟用网络直径这个参数来衡量。 等份宽度是网络系统中两个相等距离所去掉的网络边的条数。 判断并行体系结构性能重要原则是小的网络直径和大的等份宽度。集群系统中处理机的连接方式用总线结构表示, 在总线结构中, 各处理机连接在一个总线上面, 靠一个总线进行传输, 在消息进行传输时要判断先后顺序, 总线结构图如图1 所示。
并行计算机的软件环境包括编码语言、 操作系统、 计算环境3 部分, 用于消息传递的并行环境常用的是PVM和MPI。PVM并行计算环境叫做并行虚拟机系统, 系统规模小通用性强, 在TCP/IP协议环境下也适用, PVM特点支持多用户同时执行多个应用程序, 提供通信原语, 多个进程组成一个进程组, 同一个进程可以属于多个进程组, 在不同的网络系统中可以使用, 兼容性强, 容错功能强。 MPI并行计算环境是消息传递界面的一种方式, MPI并行计算环境特点实现的开发工具方式多, 消息的发送和接收可以重叠, 对消息缓存区可以有效管理, 可靠地运行在集群系统中, 保证其他软件可以正常运行, 标准平台上也可以使用。
4 并行算法定义及分类
算法是解决某个特定类型问题的解题方法的一系列规则, 并行算法是在解决问题方面相互联系起协调作用的可以并行执行的过程的集合。 并行算法是在并行处理机上把多个问题和任务映射到多处理机进行求解的处理数据的一种方法。 传统的算法树是一维问题的串行算法, 靠算增加算法树的深度来进行大型计算机计算, 并行算法减少时间上的复杂性, 计算量增加, 算法步骤减少, 把时间上的复杂性转化为空间上的复杂性。
并行算法分类, 并行算法根据运算对象不同分为数值并行算法和非数值并行算法两类, 数值并行算法有线性方程组和多项式求解等, 非数值并行算法指排序、 选择、 分类等设计。 并行进程执行顺序不同分为同步并行算法、 异步并行算法、 独立并行算法, 同步并行算法指进程执行要等待其他进程的计算方法, 异步并行算法指进程在执行的时候彼此不用相互等待, 独立并行算法指进程在执行的时候是独立执行的。
5 并行算法设计
用并行处理机系统进行并行计算求解问题一般遵守需要解决的问题本身提出满足需要的特定的并行算法, 或者在相似的问题上把已有的并行算法改变下, 来解决问题原则。 常用的并行算法技术有流水线技术、 分治策略和加速级连策略等。
流水线技术是重要的并行计算技术, 在VLSI并行算法中, 基本设计是把一个任务设置为A, 然后分成几个小的子任务A1、 A2、 …AN, 在执行的时候按顺序执行, 先执行A1再执行后面子任务, 计算速度是一样的。
分治策略就是把问题分解多个特征相同的子问题, 计算机单个结点平均分摊计算机的负载提高工作效率, 子问题的类型和原问题的类型一样, 采用分而治之的原则。
加速级连策略是采用最优算法来解决问题, 开始使用最优算法, 当任务规模缩小到一个值的时候, 使用最快非最优的方式接续完成任务解决问题, 使用最优串行算法并发解决子问题。
并行计算模型把并行机的基本抽象特征表现出来, 从计算模型中可以看出来并行计算模型、 并行算法设计、 并行机三者关系, 并行算法映射到并行机上, 基于并行机进行算法的设计。 计算机模型为并行算法提供了框架和物理基础, 使用多种并行机。 并行计算模型如图2 所示。
并行算法评价标准是加速比和效率, 并行算法在并行机上求解实际问题,
并行算法的加速比
TA串行算法在单处理机上最优运行时间
TB并行算法使用B台处理机的计算时间
并行算法的效率定义
B为处理机台数
在处理台数规模不变的特定情况下并行算法加速比SB和处理机台数B成正比, 也叫算法线性加速比, 如果SB比B多, 那么该算法是超线性加速比。
设计高性能计算机并行算法要充分考虑到并行算法的扩展性, 这也是再设计并行算法结构时要充分考虑到的问题, 扩展性有3 种分别是资源扩展、 技术扩展和应用扩展, 扩展性主要是并行算法在对处理机数目的有效利用的一个度量, 并不是算法内在的通信和并行性需求。
加速比、 效率和扩展性是评价并行算法性能的3 个指标, 加速比是最优串行算法运行时间和B太处理机并行运行时间的比值, 效率是加速比与B的比值, 我们在设计并行算法的时候要充分考虑到加速比、 效率和扩展性3 个指标。
6 结语
从理论和设计方法两方面对分布式并行算法进行了简单的描述, 随着计算机技术的发展, 人们对计算机的数据处理性能有很高的要求, 最初的计算机处理能力已经不能满足计算机领域的发展, 并行处理技术可以提高计算机大数据的并行处理性能, 从国内外并行算法的应用上分析出我国对并行处理能力要加大投入, 才能追上技术领先国家。 分布式并行算法提高计算机的数据处理能力, 在计算机技术领域发挥着重要的作用。 并行处理技术分硬件技术和软件技术, 目前硬件方面有很大的提高, 但是在软件方面还存在问题需要解决, 算法是软件的核心, 要推动并行处理技术的发展, 必须要先重点研究并行算法。
摘要：计算机计算方法从单机技术发展到多机并行技术, 这是计算机计算模式适应未来科技发展的趋势, 国家的科技发展需要并行处理技术的推动, 并行处理技术能快速地发展, 源动力来自于人们对工程计算机能力的需求。在这几年, 并行处理技术得到很大的推动与发展, 并行算法处理技术的应用提高了计算机大数据处理的能力。介绍并行算法应用情况的背景和研究现状, 阐述了并行算法技术的分类及设计方法。
关键词：分布式,并行算法,计算机计算方法
参考文献
[1]许林.群智能算法可并行性分析及其FPGA实现[J].journal6, 2010, 46 (33) :54-57.
并行分析算法 篇2
基于PC-CLUSTER机群并行体系结构与消息传递库MPI并行环境,研究了三维非结构网格DSMC并行算法.提出一类基于结构背景网格上的非结构网格动态分区策略,保证各子区域的分子数量大致相等,实现计算进程间的动态负载平衡.利用MPI库函数构造了两类符合DSMC并行原理的.通讯法:单步通讯法与多步通讯法.采用单控制多数据流(SPMD)以及Master/Slave并行模式,设计了三维非结构网格DSMC整体并行算法.给出了跟踪模拟分子在四面体网格间迁移运动的详细计算过程.最后对全尺寸航天飞机高超声速绕流进行了并行模拟,验证并行算法的有效性.
作 者：王学德 伍贻兆 夏健 谭俊杰 WANG Xue-de WU Yi-zhao XIA Jian TAN Jun-jie 作者单位：王学德,谭俊杰,WANG Xue-de,TAN Jun-jie(南京理工大学动力工程学院,南京,210094)
伍贻兆,夏健,WU Yi-zhao,XIA Jian(南京航空航天大学航空宇航学院,南京,210016)
刊 名：宇航学报 ISTIC PKU英文刊名：JOURNAL OF ASTRONAUTICS 年，卷(期)： 28(6) 分类号：V311.4 关键词：非结构网格 直接物理模拟 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
关键词：北斗,捕获系统,FFT,并行频率搜索
0 引言
由于卫星和接收机存在相对运动, 接收机收到的卫星信号中会有一个多普勒频率偏移量。对于传统的顺序搜索的捕获方法而言, 由于多普勒频偏是未知的, 需要对每一个多普勒频移步进进行码相位搜索, 这就是所谓的二维搜索。假设多普勒频率搜索范围为±10 k Hz, 搜索步进为500 Hz, 这就意味着对一颗卫星的信号完成一次完整的搜索需要41次的频率搜索[1], 对于北斗二代B1频点I支路信号而言, 测距码长为2 046, 设步进1 2码片, 在每次频率搜索中又需要进行4 092次的测距码相位搜索。由此可见, 如果要确认一颗卫星的信号不存在, 需要花费41×4 092个单位时间, 考虑到存在虚警概率, 一次完整的搜索往往花费3~4 min。而采用FFT并行频率搜索, 只需要对每个码相位进行一次频率搜索就可以确定多普勒频率偏移量[2], 此外, 采用子相关器分段积分形式可减少FFT模块收集数据的时间开销, 大大缩短信号捕获所花费的时间。
1 捕获原理
1.1 捕获框架
并行频率捕获算法针对于一个码相位进行相关运算, 相关器采用多个子相关器集的结构, 将输出数据合理组合得到分段相关积分值后进行FFT变换, 确认测距码相位是否对齐并估计多普勒频偏。
如图1所示为单个通道的并行频率捕获框图结构, 输入中频信号通过与本机产生的正弦和余弦信号混频分别得到I, Q两个支路信号, 再和产生的测距码进行相关运算, 测距码周期为1 ms, 则设积分时间为1 mms, 之后送入M级的寄存器中[3]。
在一个测距码周期中相关积分值分别存放在m个寄存器中, 每个寄存器相当于一个子相关器, 本文中称该寄存器为子相关器, 其原理框图如图2所示。
在每次输入一个数据后, 寄存器中所有数据右移一位, 根据不同的参数设置输出端口OUTi的抽头位置对连续的几个子相关器求和。输出n个抽头 (不足n个用零作为输出补足) 后送入n点的FFT模块进行FFT变换。在完成一次变换后对FFT输出数据求模, 找到幅值最大的输出值和对应的k值, 将最大值与设定的阈值进行对比, 若小于阈值则认为测距码相位未对齐, 控制测距码发生器延时1 2个测距码相位;如果模值大于阈值则认为捕获到卫星信号且当前码相位就是卫星信号测距码相位, 并利用k值计算出多普勒频移后控制载波NCO进行精确捕获。
1.2 子相关器原理
北斗B1频点I支路信号在加入多普勒频移fd后形如式 (1) :
式中:A为幅度;D (t) 为数据码;C (t) 为测距码;fc为载波中心频率1 561.098 MHz, φ为初始相位, 不同卫星信号用上标j区分。
经过下变频后, 若不考虑初始相位, 并在测距码周期内数据码不会发生跳变, 则信号变为:
根据测距码的自相关特性得知, 当τ不为0时, 相关积分输出值很小认为无信号。当τ=0时, 表示测距码同步, 此时可以忽略测距码的影响, 针对一颗卫星分析, 相关积分结果为:
根据式 (3) 可以看出, 积分器结果是与fd相关的sinc函数有关, 随着fd增大, 积分器输出总体呈减小趋势, 且当积分时间T*fd为0.5的整数倍时, 积分器值为零。因此时域捕获的频率搜索范围很小, 只能对某一频率附近几百Hz的范围搜索。若T为测距码周期1 ms, 多普勒频偏在每个0.5 k Hz的整数倍附近时, 会使积分结果抵消;若减小积分时间, 使T′=T M, 在不考虑式 (3) 中分母fd的影响, 则同样出现上述现象的频率间隔变成M*0.5 k Hz。
那么, 在1 ms的积分时间中分出M个区间, 则每个区间积分时间大大缩短, 使信号无法从噪声中分辨出来, 因此提出通过不同抽头对子相关器求和的结构。如图2中所示, 设M值为8, 抽头数X=3, 则可以设OUT1的抽头为子相关器1~子相关器3, OUT2的抽头为子相关器2~子相关器4, OUT8的抽头为子相关器7、子相关器8和子相关器1。如此设置即可保证积分器的一定幅值又使每个输出都存在一个固定的间隔, 可作为FFT模块的输入数据。
1.3 频率并行搜索原理
同样考虑测距码已经同步的情况下, 不考虑数据跳变, 采样率fs, 测距码周期内采样点数L, 子相关器级数为M, 每段积分时间为1/Mms, 采用N点FFT变换, 第k点的归一化模值结果为[4,5,6]:
对FFT输出模值进行对比, 当其大小超过预设的门限值后, 说明当前的测距码相位和卫星信号的测距码相位是对齐的, 同时记录k值, 用公式 (5) 值估计卫星的多普勒频移[7]。
当k∈[0, N 2]区间内, 直接代入公式 (5) 计算多普勒频移;当k∈ (N 2, N) 区间内, 将k=k-N代入式 (5) 。由此可见, 对于该系统的最大频率搜索范围是[8]:
2 仿真与性能分析
2.1 子相关器性能
利用Matlab软件, 建立传统的分段积分模型和图1中相关器模型, 前者M值为8, 不采用抽头方式直接选取对应的M作为FFT输入;后者设置M值为8, 抽头数X=3, 抽头方式如1.2节所述。设置fd=1 k Hz, FFT点数N=1 024。如图3所示的FFT输出模值, 传统的相关器模型和改进后的相关器模型在多普勒频移点都有峰值输出, 但改进后的峰值更加明显的区别于其余k值所对应的输出, 这将有利于阈值设定, 降低虚警概率。
2.2 频率分辨率分析
由公式 (5) 得出该捕获系统的多普勒频率估计值的分辨率如公式 (7) , 其频率步进与积分分段数M成正比, 与总积分时间T和FFT点数成反比。
在fd=1 k Hz, T=1 ms的情况下, 分别对以下三组数据仿真:
仿真结果如图4所示, 第一组数据对应峰值在k=124处, 分辨率约为8.0 Hz;第二组数据对应的峰值在k=32处, 分辨率约为31.25 Hz;第三组数据峰值在k=63处, 分辨率约为15.87 Hz。和Δf的理论计算值基本吻合。
2.3 频率搜索范围分析
根据1.3节中的结论, 多普勒频移搜素范围跟子相关器数量M有关, 当总积分时间为1 ms时, 搜索范围为±M k Hz。设置参数M=8, N=1 024, 理论搜索范围为±4 k Hz。使fd以50 Hz的步进从0~10 k Hz递增, 记录FFT输出模值的最大值, 归一化后如图5所示, 当fd大于4 k Hz后输出模值都较小, 基本符合理论计算, 认为该参数下的截止频率为±4 k Hz。此外, 从图中可以看出在带内, 输出的最大模值也会因fd的不同呈现波动, 这种被称为扇贝损失的现象使得某些频点的峰值受到抑制, 造成信号漏补。为减小该损失的影响, 可以通过加窗等方式进行弥补[9,10], 有兴趣的读者可查阅相关资料, 本文不再说明。
3 关键模块的FPGA实现
捕获系统采用多通道并行处理方式, 每个通道原理框图如图1所示, 分为载波模块, 测距码生成模块, 混频模块, 相关器模块和FFT模块及其控制模块。
3.1 多级子相关器设计
上一节中提到的由多个子相关器组成的相关器结构, 在具体实现中每个通道都大量使用相关器, 造成硬件开销的成倍增长。考虑到资源因素, 在设计中采用一个传统相关器对总积分时间T分成M次积分, 每次输出结果输送给对应时刻的寄存器中。而FFT的输入端根据选择不同抽头的组合实现图1的结构。图6为M=8, X=2子相关器的部分RTL图, 积分区间被分为八段, 结果分别放在sub框内对应寄存器中, 8个OUT端口分别连接2个sub寄存器作为FFT的输入信号。
3.2 捕获控制模块
用QuartusⅡ11.0中的FFT变换IP核来完成该系统中的FFT运算。考虑到硬件资源消耗和时间开销, 参数设置为256点。需加入控制模块对FFT变换后的数据分析和处理。首先从FFT模块中读出所有k值对应的实部和虚部输出, 计算模值后对比找出该轮中的最大值并记录对应k值。完成一次变换后, 将记录的数据与预设的阈值对比, 确定是否存在信号, 若超过阈值则通过k值计算出fd值并控制载波NCO调整本机载波频率。需要注意的是, FFT模块中的输出为倒序输出, 计算fd时要调整k值。
4 结语
采用多级子相关形式分段积分, 减少了由于多普勒频移造成积分时间内相关能量相互抵消的可能性。不同段内的相关结果通过抽头重新组合, 提高了抗噪声性能, 充分利用相关器节约硬件资源, 减少数据采集的时间开销。利用FFT变换只需要执行一次计算就可以完成对设置的范围内所有频率的搜索。采用这种方法可以减少北斗接收机捕获过程中对多普勒频移搜索所花费的时间, 从而有效提高北斗接收机性能。
参考文献
[1]谢钢.GPS原理与接收机设计[M].北京:电子工业出版社, 2009.
[2]邓洪高, 王靖, 纪元法, 等.一种快速FFT捕获算法及其FPGA实现研究[J].电视技术, 2012, 36 (15) :100-103.
[3]LIU Gao-hui, CAO Jia-kun.Acquisition method and performance of high dynamic GPS signal[J].Computer Engineering and Applications, 2010, 46 (7) :142-144.
[4]ZHENG Yong-zhi, ZHANG Yong-xue.An improved segmented match filters with FFT approach for GNSS signal acquisition[C]//2nd International Conference on Computer Technology and Development.[S.l.]:[s.n.], 2010:425-428.
[5]QIU Lei, LI Lei.GPS signal acquisition based on FFT[C]//2010 Second International Conference on Information Technology and Computer.Kiev, Ukraine:IEEE, 2010:110-113.
[6]王凯.BD-2卫星信号快速捕获技术研究[D].西安:西安电子科技大学, 2013.
[7]LI Chuan-jun, YANG Shu-xing, JI Zhen.Performance analysis of fast GPS signal acquisition based on PMF and Window FFT[J].北京理工大学学报 (英文版) , 2012, 21 (3) :5-8.
[8]李菊, 陈禾, 金俊坤, 等.基于FFT的两种伪码快速捕获方案的研究与实现[J].电子与信息学报, 2006, 28 (10) :1778-1781.
[9]齐华, 蒋邦英, 冀乐, 等.PMF-FFT扇贝损失补偿方法的仿真与分析[J].中国新技术新产品, 2011 (4) :56-57.
并行分析算法 篇5
1 网络数据传输中问题描述
1.1 假设问题
假若计算机网络只有一条通道对节点上的多数信息进行传输, 这时可利用G= (N, L) 这一数学模型来描述被传输的信息;该通道的通信传输有较强的稳定性, 可对各节点间的数据进行有效传输;传输通道的网络可靠性和介质长度之间无需对数据进行直接交换。
1.2 问题模型
研究表明, 计算机网络节点间连线载体的成本数学模型公式如下:
其中, C为载体总有成本, N为总有交叉点数, Diaij是从i和j两个交叉点间逻辑连线最的载体数量, α和β为网络交叉点常数。gij=1, 说明i与j两个节点间存在直接的通讯连线;如gij=0, 说明i与j两个节点间没有直接的通讯连线。
在R最大化, 且C≤C0时, 计算机网络的整体可靠度模型如下所示:
其中, P (li) 表示第i条节点线路载体的可靠程度, Ω是网络中正常状态的总合, li表示第i条节点线路的载体。
2 并行遗传算法优化计算机网络可靠性过程
并行遗传算法可分为粗粒度、细粒度和主从式度三类模型。粗粒度模型十七中为有效的一种, 其有较强的适应能力, 被广泛应用于并行遗传算法模型中。其主要是将随机形成的初始群体利用处理器将其分割成为无数个子群体, 子群体在各个处理器上互相独立的进行并行操作, 只有经过指定的进化代, 子群体将会对无数个个体进行交换, 引进新型的优异基因, 是子群体更加多样化, 可有效避免基因在还未到达成熟期时开始收敛。该算法模型由于通信成本较小, 因此, 较适于实施在集群系统没有较高的通信网络时。
经研究表明, 以pop=m*pops群体规模保持不变为基础, 对子群体的数量进行适当增加, 可有效提升网络优化质量。利用同方这一探索技术, 其计算机网络有108个集群, 处理器为16个, 因此, 将m设置为16, 而pops设置为10.8。
2.1 初始化子群体
将所有独立的节点随机组合成为新的初始群体, 因其算法为并行法, 因此, 其比原有的算法要简单很多, 原来是将一个网络核心节点上构建形成一个较大的群体后, 将其随机分布于各个节点上。
2.2 连接拓扑
网络连接拓扑 (如图1所示) 包含各个子群体的单、双向环、无迁移状态的完全隔离以及网格等。据研究证明, 单相环连接拓扑可有效保障基因在优异状态下在群体范围内进行扩散, 同时, 又能够将群体进行隔离, 使群体多样性得到保障, 虽说其收敛速度过于缓慢, 但其解的质量非常高。
2.3 迁移计划
可利用粗粒度模型对子群体内的优异基因进行对外分离, 所选基因是随机产生的, 部分算法是利用迁入者对群体里差异较大个体进行替换;最为常用的是将优异个体进行迁移或进行取代。本文可是利用此法, 因此, nnew迁移的数量设为1。
根据研究可知, 如epoch迁移的间隔归于小, 将会使群体间的多样形态遭到破损, 影响解的质量, 针对这一问题, 本文利用仿真实验, 在保证其可靠性有效前提下, 使收敛速度到达最快。
3 仿真实验
为了检测网络拓扑并行遗传算法的性能, 节点以及载体皆选用3种, 数学模板为G= (N, L) , 其中N为60, L为61, 解群体空间区域为3121=5.39*1057, 其中, di为61条弧长。
成本公式如下所示:
第一类在并行情况下可靠性为0.84、预算成本为21.3、接质量值为37426.2;串行情况下可靠性为0.83、预算成本为124、接质量值为48642.7;
第二类在并行情况下可靠性为0.823、预算成本为31.9、接质量值为28268.7;串行情况下可靠性为0.826、预算成本为59.4、接质量值为35963.3;
第三类在并行情况下可靠性为0.836、预算成本为54.8、接质量值为21231.5;串行情况下可靠性为0.816、预算成本为65、接质量值为29971.4;
以上案例说明, 这三个方案, 不管是并行好事串行, 皆有较高的适应度, 虽三个方案所用成本不一, 并行的可靠性以及收敛度等皆优于串联算法, 因此, 并行遗传算法能优化计算机网络可靠性。
4 结束语
综上所述, 普通串联遗传的算法, 只是将计算机网络的节点存储以及通信等存在的问题进行简化, 使运行效率得到提高, 并不能达到最高效率, 但是并行遗传法不仅有效提高了计算机网络的速度与质量, 耗能保障可靠性较高。
摘要：本文分析了计算机网络运行中存在的问题, 阐述了当前形势下, 优化其可靠性的重要程度, 针对现今网络运行存在的问题进行分析研究。笔者通过研究, 结合总结和归纳自身多年工作经验, 提出利用粗粒度并行遗传算法对其可靠性进行优化。希望通过本文的分析研究, 希望能够在计算机网络在预算成本允许的情况下, 实现可靠性的优化工作, 使其运行质量与水平得到保障。
关键词：计算机网络,可靠性,优化,并行,遗传算法,应用
参考文献
[1]周环.计算机网络可靠度优化计算中遗传算法的应用分析[J].中国电子商务, 2013 (05) .
[2]周政.并行遗传算法在软件可靠性优化中的应用[J].华章, 2013 (19) .
并行分析算法 篇6
关键词：流体体积 (VOF) 方法,动网格,砰击,兴波,水下压力,自由表面,并行计算
结构物体从一定的高度落下以一定速度撞击水面, 根据物体撞击速度的不同物体表面在水的冲击作用下将受到不同程度的砰击力, 同时在物体撞击力的作用下也将会在水面激起波浪、引起水下压力场的变化。如何正确地评估与分析在这样一种砰击作用下具有自由表面的水域中流体动力的特征以及分析结构在砰击作用下的受力对于设计合理的施工方式、保证结构的安全具有重要的现实意义, 近年来不少的研究人员就如何正确地评估与分析砰击作用下结构的受力做了许多有意义的研究工作[1,2,3]。但是目前对结构物撞击水面引起的兴波以及水下压力场的变化研究较少, 尤其是考虑结构物与流体相互作用下所引起的具有自由表面效应的三维砰击问题研究较少。随着在限制或开放水域进行的大型港口工程、桥梁工程日渐增多, 对结构物砰击作用下具有自由表面的限制水域的所引起的流场动力特性变化以及对周围堤岸和水下其他结构物的影响的研究显得越来越重要。其中由于某种施工需要要求分析与观察水面平底物体从一定的高度落下砰击限制水道所造成的对结构的砰击力以及所引起的水面兴波与水下压力场突变的问题也已经引起了越来越多工程设计与施工部门的关注。本文以计算流体力学方法对大型平底结构从一定的高度以一定速度落下撞击一定水深水域的水面所引起的结构受力、三维水面波动和水下压力场变化进行了数值模拟, 以此分析与观察平底结构砰击水面所引起的流体动力现象。
1基本数学模型和主要数值方法
本计算通过求解平底结构以某一特定速度砰击自由表面条件下一定水深的限制水域内具有自由表面的流动控制方程来对所研究的问题进行数值模拟。以此分析平底结构从一定的高度落下撞击有限水深水域的水面所引起的结构受力、三维水面波动和水下压力场变化问题。研究中受砰击水域的流动控制方程由其流场中的Navier-Stokes方程来描述;方程的数值求解利用CFD商业软件Fluent来实现;平底结构的运动通过采用动网格方法来仿真, 砰击作用下自由表面的运动状态通过VOF (Volume of Fluid) 方法来模拟。
1.1控制方程、湍流模式[4,5]
计算域内的控制方程采用如下方程:
连续性方程
divu=0 (1)
动量方程
(1) 式和 (2) 式中u为流场的速度, F为流体的体积力, p为流场压强, ρ为流体密度, ν为流体运动黏性系数。计算中湍流模式采用标准的k-ε模型。
1.2运动平底结构和自由表面的处理方法
本文对运动平底结构采用动网格方法、自由表面的处理采用VOF方法。
动网格方法可以模拟计算区域随时间运动变化的流场、计算区域的运动和变形可以通过指定计算区域边界的运动或变形来实现, 也可以根据当前时刻计算结果, 求得相关的运动参数来实现。其基本思想是在每个计算时刻, 计算区域由于边界的运动或变形而发生变化, 在相应时刻的迭代计算过程中, 网格基于运动边界的新位置进行自动更新。
VOF方法的基本思想是通过构造一个函数跟踪每一个单元网格的流体流量, 并根据这个函数的函数值和导数值确定自由表面的形状。定义一个函数f (x, y, z, t) , 当该点被流体占用时就令f (x, y, z, t) =1;当该点没有被流体占用时就令f (x, y, z, t) =0。如果在一个单元网格内对f值进行平均就得到
(3) 式中δx, δy, δz为单元的边长。 (3) 式表明F值就等于单元内流体体积与单元体积之比。如果F=1表明该单元体充满了流体;如果F=0表明该单元体不含流体;如果0<F<1表明该单元体存在着自由表面。因此通过求解F值就可以确定自由表面位于那些单元内。F的值沿自由表面法线方向变化最快, 即F的导数值可以确定自由表面的方向和位置[6,7]。
对于自由表面的处理, 本计算采用有限体积方法离散控制方程, 这就需要计算通过控制体表面的对流扩散通量。这里采用几何重组方法计算VOF模型中的表面通量, 采用分段线性的方法表示两相流体间的分界面, 这种方法特别适用于通常的非结构化网格。假定在每一控制单元内流体间的界面存在一线性坡度, 用这一线性坡度来计算流经控制体表面的扩散通量。定义密度较小的空气为第一相, 将水指定为第二相, 同时必须考虑重力的影响, 利用patch工具将region指定区域全部定义为水, 其余部分为空气, 水和空气交界面则为自由表面。
1.3计算域的确定
本文数值模拟计算的计算域、平底结构及计算网格示意图如图1所示, 其中空气与未被扰动的水各占计算域上下体积的一半, 坐标原点取在静水面中心 (x=0, y=0, z=0) 处, x轴向右为正, y轴向上为正, z轴向外为正。长度为L为, 宽度为W, 高度为H, 大型平底结构的尺寸δL×δW×δH。
1.4网格划分与并行计算实现
网格划分模型采用前处理软件GAMBIT生成FLUENT求解器所需要的网格, 生成非结构化网格, 为了提高计算模拟精度, 增加计算内存、减少计算时间, 计算过程中采用并行计算方法。所谓并行计算就是在多个CPU上用多个进程处理计算任务。这多个进程既可以在同一台计算机的多个CPU上运行, 也可以在用网络连接的不同计算机上运行。
FLUENT中的并行处理过程包括FLUENT、一个主机进程和一套节点进程之间的交互作用。FLUENT通过一个叫CORTEX的模块与主机进程和各个节点进程进行信息传递。CORTEX主要用来管理FLUENT的用户界面和基本的图形功能。
FLUENT 并行求解器把网格和数据分成多个分区, 然后再把各个分区分配给计算节点进行计算。分区的数量应该等于可用计算节点数量的整数倍。大体上说, 计算节点数目越多, 并行计算的时间就越短。然而节点数量与计算效率之间并不是存在严格的正比关系。随着节点间数据通信量的增加, 并行效率将会降低, 所以在选择使用并行计算之前, 应该思考是否确实需要使用并行计算方式。
FLUENT的主机进程中没有任何网格数据, 而仅仅负责解释来自于CORTEX的命令。主机进程把接收到的命令通过指定计算节点上的数据通讯模块传递给其他节点, 这个被指定的节点称为“计算0节点”。其它计算节点在接收到主机进程传递过来的命令后, 在各自的数据集合上同时执行相同的程序。计算节点与主机进程之间的通讯工作仅当计算0节点和所有计算节点保持同步时才可以进行。
事实上每个计算节点和其它每一个计算节点是连接在一起的, 但是节点之间的数据传输、同步和执行全局任务则需要通过其数据通讯模块实现, 并通过数据通讯模块实现逻辑意义上的联通。FLUENT 的数据通讯模块是一个信息传送库, 而信息的传送机制则符合MPI (Message Passing Interface, 信息传送界面) 标准。
FLUENT的并行处理进程和串行处理进程一样, 均使用唯一的一个整数标志符加以识别。主机从计算0 节点收集信息, 然后执行关于所有数据的任务, 包括打印、信息显示和文件写入等等, 其方法与使用串行求解器时一样。
FLUENT并行求解器的使用流程如下:
(1) 启动并行求解器, 并在需要的时候生成附加的计算节点。
(2) 读取算例文件, 并让FLUENT 在加载文件时对网格进行分区。
(3) 仔细检查网格分区, 如果分区存在问题, 可以重新进行分区操作。
(4) 开始进行计算。
为了使用并行计算方法对所研究的问题进行计算, 本文的仿真计算将一台四核处理器计算机作为主机, 一台二核处理器计算机作为副机, 采用对分方法来建立新的网格分割, 将网格分割成六个小的分割, 分别分配给六个处理器。本计算中所使用的软件和硬件为:
主机:处理器 (Intel (R) Core (TM) 2 Q6600 2.40 GHz) ×4、内存2.00 G×2、硬盘500 G、内置网卡
副机:处理器 (Intel (R) Core (TM) 24 300 1.80 GHz) ×2、内存1.00 G×2、硬盘160 G、内置网卡
以上计算机均使用WINDOWS XP操作系统, 主机和副机连接成局域网, 在并行设置前, 这两台计算机都是可以在网络邻居里相互通讯、登陆到对方机器中。
1.5边界条件
如图1所示, 计算域的边界由大型平底结构动边界 (δL×δW×δH) 、进出口边界
1.6大型平底结构动边界
本文主要研究尺度为长╳宽╳高=δL×δW×δH (见图1) 的长方形平底结构在距离水面以上一定高度h、以一定速度v撞击具有自由水面的限制或开放水域所引起的水面兴波与水下压力场变化的水动力学问题。研究中假定平底结构在砰击过程中为不变形的刚性结构, 结构的动网格边界条件定义为刚体墙边界条件。平底结构的外表面被定义为流固耦合面, 采用任意拉格朗日-欧拉 (ALE) 耦合算法[8]。
2数值模拟与结果分析
本文利用上述提出的数值方法对平底结构以一定的速度从空气介质向开放或限制水域的水面砰击进而沉入水下的问题进行数值模拟, 以数值模拟手段观察和分析在考虑了结构物砰击过程中运动的动边界和自由表面边界条件下结构物撞击水面所引起的流体动力现象。本节数值计算中的砰击水域的水深为5 m, 水面宽度为20 m;结构从1 m的高度上匀速落下。计算中平底结构的尺度、结构物砰击速度以及计算域的其他参数见表3。
图2为在上述计算参数和第一类进出口边界条件下平底结构底面所受压力平均值的时间历程。其中t=0～0.1 s时间段描述了结构在原静水面以上匀速下落时结构底部压力变化的时间历程;t≥0.1 s则为结构物底面开始越过原静水面直到整个结构沉入水底时底部压力变化的时间历程。从图中可以看出, 在0.091 s (平底结构距水面大约9 cm位置) 时刻, 作用在结构底面上的压力逐渐增大, 在0.100 s (结构底面到达原静水面位置) 时刻达到峰值。作者认为:这一时段中压力峰值产生的主要原因是结构底部空气在高速砰击过程中没有及时逃逸受到水与结构的而产生一股高压气体所造成;而在0.125 s时刻所产生的第二个压力峰值则是由于高压气体排出以后水压直接作用在结构而产生。
图3为在本节所给定的计算参数和三类进出口边界条件下, 大型平底结构撞击自由水面在0.5 s时刻所引起的沿水域宽度方向波面扰动的数值模拟计算结果。从图3 (a) 和 (b) 可以看出当流场无流速的情况下 (表2中的第1和第2类进出口边界条件) , 砰击引起的波浪扰动呈现一种从脉冲压力中心向四周对称传播的趋势, 其自由表面波型大致类似。但是比较图3 (a) 和 (b) 的计算结果不难发现:在封闭水域中由于砰击作用而引起的波面扰动无论是横向 (x方向) 、纵向 (z方向) 还是其波动的影响距离以及波动的激烈程度都较之开放水域要大, 作者认为这主要是由于在封闭水域的条件下其砰击能量不像开放水域那样可以向域外传播, 因而同样的砰击力作用下封闭水域中其砰击能量相对比较集中, 从而表现出了一种更为强烈的兴波扰动。对比图3 (b) 和 (c) 还可以看出, 在开放水域中以同样大小的砰击力作用下, 不论是否存在水流的流动, 其波面扰动的激烈程度大致相似, 但是有流速的情况下抨击引起的波浪扰动表现出了一种非对称兴波、波动具有向水流下游传播的倾向。
图4描述了第1类进出口边界条件中沿计算域纵剖线 (z=0.0 m) 处平底结构砰击压力作用下引起的波面扰动的时间历程。该图的计算结果清晰地刻画了随着时间的推移砰击作用和流体粘性引起的能量消耗相互作用下自由表面波动从发展到衰减的演变过程。很明显在这样一类兴波问题中其波动也表现出从脉冲压力中心向两边对称传播的特征。
图5给出了在开放域进出口边界条件下由于平底结构撞击水面在距离静水面以下1 m (y=-1 m) 处引起的周围流场压力变化时间历程。从图5的计算结果可以看出在平底结构接近自由表面过程中, 流场压力逐渐增大, 当结构接触自由表面 (t=0.10 s) 时刻达到最大峰值, 但是随着砰击过程的结束, 流场压力也迅速回复到砰击前的水平。实际上当砰击发生后的0.05 s时刻 (即图5中t=0.15 s时刻) , 砰击引起的压力效应已经很小, 其峰值只相当于最大峰值的四分之一。图6为其它条件与图5一致但出口边界条件为封闭域的条件下原静水面以下1 m处引起的压力变化时间历程。比较图6与图5的结果可以看出:在其它条件相同的情况下, 开放域与封闭域的计算结果差别不大。
图7给出了在无流速的开放域条件中, 砰击发生后的0.02 s时刻 (即t=0.12 s时刻) 不同水深的压力分布。从图中的结果知道在脉冲砰击压力作用下越接近水面, 所受的砰击压力越大。当水深较大时, 例如水深3 m处所受的砰击压力仅为水深0.2 m处的三分之一, 水面脉冲砰击在3m水深处所造成的压力波动实际上已经很小。因此不难判定平底结构物的砰击作用主要对接近水面的水域影响较大, 对深水区域影响较小。图8给出的是在有流速 (u=2 m/s) 的开放域条件中, 其它条件与图7相同时砰击发生后的0.02 s时刻不同水深的压力分布。对比图8和图7可以发现:有流速与无流速对于砰击作用下水下的压力分布的差别不大。
3讨论与结论
1) 本文所采用的利用两台多核微型计算机对平底结构撞击自由水面所引起的砰击问题进行的并行算法, 以此手段来实现提高运算速度和扩大计算内存的目的。利用本文所提出的方法, 我们可以对大型结构物在三维的开放或限制海域的砰击问题进行分析和计算。为以数值方法分析此类砰击问题所产生的水动力现象提供了一种实用的手段。
2) 就本文所讨论的问题而言, 同样的脉冲砰击压力作用下, 不同的来流与进出口边界条件将会激发起相异的兴波特征。对于封闭水域, 由于砰击能量不能向外传播, 因而在这一边界条件下砰击所引起的兴波较开放水域要大;对于开放水域, 有无来流的情况下砰击引起的兴波波高大致接近, 有无来流的差异主要表现在砰击压力引起的兴波的波型是否对称这一点上。
3) 从本文的计算结果可以看出:在考虑了自由表面效应后作用在水面的平板结构脉冲砰击压力所造成的水下压力场影响区域有限, 随着离开水面砰击压力中心距离或深度的增加, 砰击压力所造成的水下压力场的扰动影响在逐渐地减少。在本文的算例中砰击压力的横向 (x方向) 作用长度δL为2 m, 从图4至图7的计算结果我们可以看出不论是什么样的进出口边界条件, 也不论是在什么样的水深或什么时刻, 在离开压力中心稍远的水域砰击压力对水下流场的影响已经很小。从图6和图7的计算结果我们还可以发现:当水深大于3 m后砰击压力的影响也已经很小。
参考文献
[1]Yettou E M, Desrochers A, Champoux Y.A new analytical model for pressure estimation of symmetrical water impact of a rigid wedge at variable velocities.Journal of Fluids and Structures, 2007;23:501—522
[2]Peseux B, Gornet L, Donguy B.Hydrodynamic impact:numerical and experimental investigations.Journal of Fluids and Structures, 2005;21:277—303
[3]Lin C M, Shieh L D.Simultaneous measurements of water impact on a two-dimensional body.Fluid Dynamics Research, 1997;19:125—148
[4]王福军.计算流体动力学分析———CFD软件原理与应用.北京:清华大学出版社, 2004:1—4
[5]韩占忠, 王敏, 兰小平.FLUENT流体工程仿真计算实例与应用.北京:北京理工大学出版社, 2004:15
[6]王志东, 汪德n.VOF方法中自由液面重构的方法研究.水动力学研究与进展, 2003; (1) :53—56
[7]吕江, 朱陆明, 翟洪刚.涌潮冲击丁坝时涌潮压力初步研究.科技通讯, 2005;21 (1) :34—40
并行机调度遗传算法研究 篇7
并行多机调度问题是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.
并行分析算法 篇8
近年来, 随着电子技术的快速发展, 电力系统暂态录波明显向高采样率、连续稳态记录和海量存储的趋势发展[1]。其中, 为了提高海量故障录波数据的传输效率和降低存储空间, 众多文献提出了各种各样的数据压缩算法[2,3], 但是, 随着电力通信网络的改善, 百兆、千兆以太网大规模安装, 通信效率已经不再是难以克服的瓶颈, 因此, 目前众多厂家已经开始放弃了原有复杂的压缩方案, 而直接在高速以太网上传输录波数据。目前, 这种录波数据海量化趋势已经给各种基于串行编程方式设计的分析软件[4,5,6,7]增加了不小的计算压力, 其中最明显的就是海量录波记录文件解析时间过长而导致的软件效率低下。而在计算机硬件技术发展方面, 目前已经进入多核计算时代, 原来传统的面向单核的串行编程技术被完全颠覆, 逐渐被基于多线程模式的并行编程技术所取代[8]。
针对这2个方面的发展趋势, 本文研究并实现了海量电力系统暂态数据交换通用格式 (COMTRADE) 数据文件的并行解析算法。算法可极大地提高面向海量故障录波数据、海量广域测量数据和海量电能质量录波数据的软件处理效率, 并可随着未来CPU核数的增加和COMTRADE数据文件的加大获得线性加速比[8]。
1 COMTRADE标准
为规范不同厂家的电力数字记录设备进行系统故障录波与暂态仿真的存储格式, 便于第三方的处理和分析, IEEE在1991年制定了COMTRADE标准 (IEEE Std C37.111—1991) [9]。最新修订的1999标准 (IEEE Std C37.111—1999) 规定与记录信息相关的文件有4个:头标文件、配置文件、数据文件和信息文件。其中对于第三方暂态数据分析软件而言最重要的是配置文件和数据文件, 其他文件是可选的。
数据文件记录着每个采样通道中的每个采样数值。数据文件可以是美国标准信息交换码 (ASCII) 格式或二进制格式。二进制数据文件与ASCII数据文件格式类似, 每一行应分为“TT+2”列, 其中TT代表配置文件中模拟量通道和状态量通道的总和, 另外2个是采样序号和时间标记。二进制文件以比特形式集中存放状态量通道数据, 各个数据之间没有分隔符, 每组采样值之间没有回车换行符隔开。各列的具体内容如下所示:第1列为采样序号;第2列为采样数据的时间标记;第3组的列为表示模拟量通道信息的采样数据值;第4组的列为表示状态量通道信息的采样数据值。
2 并行解析算法设计
2.1 二进制数据文件并行解析算法
二进制数据文件的并行解析算法原理如图1所示。
由图1可知, 二进制数据文件的并行解析算法被设计为2个阶段的并行流水线[10,11]结构:
1) 第1个阶段:由读取线程依次读取COMTRADE数据文件中的静态数据块Bs1～Bsn (块大小为LNOneRowBytes, L为算法预先设定的每次最多读取的采样次数, NOneRowBytes为每次采样所占字节数) , 进入共享解析队列DequeBinary中, 形成最大队列长度为m的待解析数据队列。
2) 第2个阶段:为每个CPU核启动J个线程, J个线程中有Z个可并发解析数据, 而剩余的J-Z个线程则必须等待, 并不断地向共享解析队列请求新的数据块。
此算法中解析结果作为已经被预先分配大小的全局向量组被全部的解析线程共享, 不同解析线程在解析时以序号信息为下标直接插入到不同向量对应的位置中, 线程之间的工作完全不相干, 解析阶段可彻底地并行执行。
2.1.1 关键数据结构
共享解析队列DequeBinary的接口定义如图2所示。
由于有多个线程同时访问此队列, 所以对出队列函数pop_front、入队列函数push_back和清空函数clear进行了同步处理, 加入了临界区变量m_lock。队列元素及其相关重要变量的定义如下:
2.1.2 并行解析算法的详细步骤
二进制格式数据文件并行解析算法的具体步骤如下:
步骤1:解析配置文件获取模拟量通道数NACount和状态量通道数NDCount, 计算出每次采样所占字节数NOneRowBytes和采样总数NSamples。建立时间数据向量Tv、NACount个模拟量数据向量Av、NDCount个状态量数据向量Dv。并将这些向量的大小设置为采样总数NSamples, 并分配相应的内存。
步骤2:创建共享解析队列DequeBinary。
步骤3:通过操作系统应用编程接口 (API) 获取到当前系统的CPU核数P。逐个创建解析线程, 为保证算法运行过程中每个核都处于最大工作状态, 为每个CPU核启动J个解析线程 (J≥2) , 总共PJ个解析线程。而后通过操作系统API为每组线程指定相应的CPU核。线程创建后被设置为挂起状态。
步骤4:启动读取数据线程, 使能各个被挂起的解析线程。动态分配一个队列元素BLOCK_BINARY, 按LNOneRowBytes大小读取数据文件, 并将数据指针保存到pBuffer中, 而后填入NRealSamples, 最后将队列元素指针压入队列中。持续此过程直到队列已经填充了m个动态分配的BLOCK_BINARY指针。假如发现队列元素个数小于m, 则重复以上程序, 持续此过程直到全部文件数据被读取完毕。
步骤5:被映射到同一CPU核的线程组同时向共享解析队列请求BLOCK_BINARY块指针, 其中只有固定数量的线程可被分配BLOCK_BINARY块指针, 其他线程必须等待。
步骤6:监视DequeBinary是否为空, 假如是就激活通知退出事件, 等待所有线程退出, 完成并行解析。
2.1.3 解析线程内的算法
解析线程在获取结构BLOCK_BINARY的有效指针pCB后, 根据其中自带的信息可快速解析pBuffer中的数据块, 解析线程内的算法伪码如下:
从上述伪码片段可知, 通过利用以往在串行解析中无用的采样序号信息, 实现了快速的信息解析和插入, 使得各个并行工作的解析线程完全不相干, 可独立地完成解析工作。
2.2 ASCII数据文件并行解析算法
ASCII数据文件并行解析算法原理如图3所示。
由图3可知, ASCII数据文件的并行解析算法被设计为3个阶段的并行流水线[10,11]结构。
1) 第1个阶段:
由读取线程依次读取COMTRADE数据文件中的静态数据块Bs1～Bsn (块大小为NBlockSize) , 进入共享解析队列DequeAscii中, 形成最大队列长度为m的待解析队列数据块Bw1～Bwm。由于ASCII数据文件中每次采样数据的保存长度各不相同, 所以读取线程每次获得的数据不可能像二进制文件一样对齐, 所以产生了如图4所示的不能被正确解析的上边缘数据和下边缘数据。
2) 第2个阶段:
为每个CPU核启动J个线程, J个线程中有Z个可并发解析数据, 而剩余的J-Z个线程则等待, 并不断向共享解析队列请求新的数据块。每个解析线程首先需寻找出ASCII数据块中的上边缘和下边缘数据, 经过整理后将其分别插入边缘数据向量Ev中。
3) 第3个阶段:
块边缘数据解析线程不断监测边缘数据向量Ev中是否有可被解析的边缘数据, 若有就将数据解析, 而后插入到不同的向量中。
2.2.1 关键数据结构
共享解析队列DequeAscii的接口定义与DequeBinary完全一样, 其队列元素、块边缘, 及其相关重要变量定义如下 (其他向量定义与2.1.1节一样, 此处就不赘述) :
2.2.2 并行解析算法的详细步骤
ASCII数据文件的并行解析算法具体步骤如下 (步骤1～步骤3与二进制数据文件算法所对应的步骤内容类似, 此处就不赘述) :
步骤4:通过数据文件大小和每次读取的NBlockSize计算出读取线程的最终读取次数M, 并将边缘数据向量Ev的大小设置为2M。
步骤5:启动读取数据线程, 使能各个被挂起的解析线程。动态分配一个队列元素BLOCK_ASCII, 按NBlockSize大小读取数据文件, 并将数据指针保存到pBuffer中, 然后填入NRealSize, NSequence和NBlockSize, 最后将队列元素指针压入队列中。持续此过程, 直到队列已经填充了m个动态分配的BLOCK_ASCII指针。假如发现队列元素个数小于m, 则重复以上程序, 持续此过程直到全部文件数据被读取完毕。
步骤6:被映射到同一CPU核的线程组同时向共享解析队列请求BLOCK_ASCII块指针, 其中只有固定数量的线程可被分配BLOCK_ASCII块指针, 其他线程必须等待。
步骤7:块边缘数据解析线程随时扫描边缘数据向量Ev, 发现有配对项就进行解析。当解析次数等于M-1 (读取线程的最终读取次数) 时, 线程就自动退出。
步骤8:监视DequeAscii是否为空, 若是就激活通知退出事件, 等待所有线程退出, 完成并行解析。
2.2.3 解析线程内的详细算法
解析线程在获取结构BLOCK_ASCII的有效指针pCB后, 根据其中自带的信息可快速解析pBuffer中的数据块, 解析线程内的算法伪码如下:
从上述片段可知, 通过利用以往在串行解析中无用的采样序号信息和多线程技术, 使得过去基于ASCII的串行文本流解析变成了并行文本流解析, 从而突破了海量ASCII文本数据解析的瓶颈。
2.2.4 块边缘解析线程内的算法
块边缘解析线程内伪码如下:
从以上伪码可见, 通过将连续2个数据块间的上边缘数据和下边缘数据连接起来就可还原一条完整的采样ASCII数据。块边缘解析线程由于解析工作量很小, 所以可每扫描一次适当休眠一段时间, 再进行新的扫描。
3 算法试验
算法试验计算机配置为:4核, 单核2.4 GHz, 内存2 GB, 硬盘7 200 r/s。分别采用403 MB的二进制格式数据文件和455 MB的ASCII数据文件进行试验, 这2个文件包含33个模拟量通道、64个状态通道。试验结果如表1所示。
从表1可见, 采用并行解析可获得相当高的加速比:在逐渐普及的4核CPU上, 二进制数据文件获得了至少3倍的加速比, 效率提升显著;而ASCII文件, 由于打破了原有的串行文件解析过程, 在4核CPU上获得10倍多的加速比, 效果非常显著。同时由表1推知, 2种并行解析算法都具有线性加速比, 可随着CPU核数的增加和COMTRADE数据文件的加大获得线性加速比。
4 结语
随着中国电力系统自动化的快速发展, 系统安全性的提升必然越来越依靠各种暂态监测数据, 而目前对海量暂态数据研究的着重点在前端压缩算法上, 忽略了后端直接面向海量暂态数据的处理算法。本文所提出的并行解析算法可以让后端处理软件适应多核并行化的硬件发展趋势, 极大地提升软件处理海量暂态数据的效率。
参考文献
[1]白青刚, 夏瑞华, 周海斌, 等.采用高性能集成芯片的故障录波故障设计.电力系统自动化, 2005, 29 (22) :94-96.BAI Qinggang, XI A Ruihua, ZHOU Haibin, et al.Design of fault wave recording device using high performance integrated microchip.Automation of Electric Power Systems, 2005, 29 (22) :94-96.
[2]乐全明, 郁惟墉, 柏传军, 等.基于提升算法的电力系统故障录波数据压缩新方案.电力系统自动化, 2005, 29 (5) :74-78.YUE Quanming, YU Weiyong, BAI Chuanjun, et al.Novel compression scheme of fault recording data in power systems based on lifting algorithm.Automation of Electric Power Systems, 2005, 29 (5) :74-78.
[3]周瑞, 鲍文, 于霄, 等.基于提升小波和混合熵编码的数据压缩方法.电力系统自动化, 2007, 31 (22) :65-69.ZHOU Rui, BAO Wen, YU Xiao, et al.Data compression method based on lifting wavelet transform and hybrid entropy coding.Automation of Electric Power Systems, 2007, 31 (22) :65-69.
[4]郑敏, 黄华林, 吕鹏, 等.故障录波数据通用分析与管理软件的设计.电网技术, 2001, 25 (2) :75-77.ZHENG Min, HUANG Hualin, L Peng, et al.Generalanalysis and management software for transient data from protective relaying and fault recorder.Power System Technology, 2001, 25 (2) :75-77.
[5]宋墩文, 蒋宜国, 许勇.波形数据通用分析系统的设计.电网技术, 2002, 26 (11) :77-79.SONG Dunwen, JI ANG Yiguo, XU Yong.Design of versatile analysis software for waveform data.Power System Technology, 2002, 26 (11) :77-79.
[6]桂勋, 郭凯, 谭永东, 等.基于网络的全图形化故障录波分析软件系统.继电器, 2004, 32 (24) :44-50.GUI Xun, GUO Kai, TANG Yongdong, et al.All-graphic software system for fault record analysis based on network.Relay, 2004, 32 (24) :44-50.
[7]桂勋, 刘志刚, 钱清泉.基于模式的电力系统通用可扩展故障分析软件系统.电力系统自动化, 2007, 31 (15) :99-102.GUI Xun, LI U Zhigang, QI AN Qingquan.General extensible fault analysis software for power system based on patterns.Automation of Electric Power Systems, 2007, 31 (15) :99-102.
[8]AKHTER S, ROBERTS J.多核程序设计技术.李宝峰, 富弘毅, 李韬, 译.北京:电子工业出版社, 2007.
[9]IEEE Std C37.111—1999IEEE standard common format for transient data exchange (COMTRADE) for power systems.New York, NY, USA:IEEE, 1999.
[10]MATTSON T, SANDERS B, MASSI NGILL B.Patterns for parallel programming.Upper Saddle River, NJ, USA:Addison-Wesley Professional, 2004.
并行量子进化算法的研究与实现 篇9
进化计算是一类模拟生物进化过程与机制求解问题的自组织、自适应人工智能技术,进化算法[1,3,5,6,8]是模拟自然进化过程而产生的一类随机搜索技术,已在人工智能、神经网络及众多的工程应用领域中显示了其解决复杂问题的特别能力。笔者也曾对算法进行改进,提出基于免疫原理的量子进化算法[2](MQEA),并基于Markov随机过程理论,证明了此算法的收敛性。
但无论如何对于大规模或超大规模的求解任务,串行进化算法显然力不从心。进化算法具有天然的并行性,非常适合于在大规模并行计算机上实现,而大规模并行计算机的日益普及,为并行进化算法PEA(Parallel Evolutionary Algorithm)奠定了物质基础。目前典型的并行进化算法主要有全局、粗粒度和细粒度等几种.近些年,许多学者在这方面做了大量研究[4,7]并取得了可喜的进展。然而,如何突破通信瓶颈,充分发挥硬件资源,提高算法性能以及如何使并行进化算法具有更好的可扩展性等问题依然困扰着并行进化算法的进一步发展。
本文分析讨论了并行进化模型理论及性能,将量子的多宇宙特性和进化算法相结合,提出了基于学习的多宇宙并行免疫量子进化算法,算法中将种群分成若干个独立的子群体,称为宇宙。并给出了多宇宙的并行拓扑结构,提出了宇宙内采用免疫量子进化算法,宇宙之间采用基于学习的移民和模拟量子纠缠的交互策略进行信息交换。即在多宇宙并行结构中,宇宙中个体向着各自的目标演化,宇宙之间采用基于学习机制的移民和模拟量子纠缠的交互策略交换不同进化环境下的优秀个体和优秀模式,这样能提高种群多样性有效克服早熟收敛现象,使得搜索效率和搜索能力得到更进一步提高。我们用典型的测试函数验证了算法的并行效果。
1 并行计算模型及理论
使用并行计算机解决一个应用问题时,并行算法的设计是非常重要的。而并行算法最终要成为一个由程序实现的结构依赖的算法,就特别需要一个抽象的并行计算机结构作为研究高效的结构依赖性算法的基础,以保证并行算法适应于广泛的并行计算机结构,并能够依照抽象的结构分析并行算法的效率,以及指导与并行机结构相匹配的并行算法的设计。并行计算模型就是为并行算法的设计、分析而研究出的并行计算机的抽象结构。
当前对进化计算所进行的理论研究工作主要包括如下几类:表示理论、操作子理论、结构化算法、收敛性理论、适应值景象理论、一致性理论、工作模型理论和物种形成理论与小生境,其中,结构化算法、一致性理论与工作模型理论和并行进化计算直接相关。无论是串行算法还是并行算法,计算复杂性都是算法效率的度量尺度,是评价算法优劣的重要依据。一个算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,算法的复杂性越高;反之,所需的资源越少,则算法的复杂性越低。下面我们介绍度量并行算法性能的一些基本概念:算法复杂度、加速比和效率等。
1) 运行时间
定义1 并行算法的运行时间是指算法在并行计算机上求解一个问题所需的时间。即表示算法开始执行到执行结束的这一段时间。如果多个处理机不能同时开始或同时结束时,则算法的运行时间定义为:从最早开始执行的处理机开始执行算起直到最后一台处理机执行完所经过的时间。
2) 加速比和效率
并行加速比是表示采用多个处理器计算速度所能得到的加速倍数。设tseq表示用串行机求解某个计算问题所需的时间,tp是用P个处理器求解该问题所需的时间。
定义2 并行加速比Sp=tseq/tp,这里tseq是表示用串行机求解该问题所需的时间。并行程序的效率定义为:Ep=Sp/p,其中P为处理器个数,加速比Sp接近P时,效率易接近于1,影响并行效率的因素很多。
2 并行免疫量子进化算法研究
MQEA引入了量子比特的概率描述和量子旋转门演化机制,通过应用免疫算子能有效地提高算法的运算效率,但MQEA并没有利用生物界物种演化的并行及小生境特点。本文提出了多宇宙并行免疫量子进化算法(MPMQEA)。MPMQEA采用多宇宙并行结构,不同的宇宙向着各自的目标演化,宇宙之间采用基于学习的移民和模拟量子纠缠的交互策略交换信息,具有比MQEA 更快的收敛速度。
2.1 多宇宙并行拓扑结构
并行算法的基本思想是将一个复杂任务分解为多个较简单的子任务,然后将各自任务分配给多个处理器并行执行求解.PEA的三种基本模型:全局并行模型、粗粒度模型和细粒度模型。MQEA 的内在并行性使得它特别适合粗粒度的并行计算。粗粒度模型又称作分布式模型或孤岛模型.是目前最流行的一种并行进化算法.它将整个种群划分为多个子种群,每个子种群独自运行一个串行进化算法。在每个子种群内部进行选择、交叉、变异等遗传操作,且每经过一定遗传代数再在各子种群间交换优秀个体(迁移算子)来丰富各子种群的多样性,减小了未成熟收敛的可能性。
在PEA中,一个重要问题是如何降低通信开销,包括:1)迁移率的确定;2)拓扑结构的确定;3)迁移间隔,表示两次迁移之间间隔的演化代数;4)迁移策略。这4个主要参量对迁移的效果和性能起到不同程度的作用,共同决定了迁移算子的行为特性。其中拓扑结构对并行遗传算法的整体性能是非常重要的,它控制着优质遗传信息在各个子种群中的传播方式和速度,也就影响了整个算法的收敛速度。许多学者试图通过比较在不同的拓扑结构上并行进化算法的实验结果寻求算法性能的提升[7]。粗粒度模型中,采用随机选择方式来进行岛屿之间的迁移缺乏一定的导向,不利于各岛屿向着自己最有利的方向发展。
本文采用改进的粗粒度模型,如图1所示。在各宇宙中选择一虚拟服务器,称为master种群,其余处理器称为slave种群,master种群保存各slave种群中的优秀个体。slave种群和master种群间迁移优秀个体,形成星状结构,而各宇宙的master服务器以环状相连,这样可以有效减少在各宇宙间的通信开销。特别是基于学习的个体迁移能引导各宇宙向着自己最有利的方向发展。
2.2 多宇宙之间信息的交换
本文采用基于学习的移民(图2)和模拟量子纠缠的交互两种策略来实现多宇宙之间信息的交换。 通过各宇宙之间的移民和交互,使得一个宇宙内的信息发生变化,能迅速引起其他宇宙的信息发生变化。
2.2.1 宇宙间学习算子
宇宙间学习算子是通过控制slave种群内部部分个体对master种群的全局最优模式的学习来实现的。基于学习的个体迁移策略,能根据种群的平均适应度调节学习频率。通过slave种群向master种群迁移最优个体以及低平均适应值的slave种群向master种群的优秀模式学习加快了算法的收敛进程。考虑到算法本身的仿生学特征,利用生物学的观点解决群间学习频率的选取问题。当一个种群的平均适应度较低时,该种群为了赶超其他种群,应更有必要向优秀模式学习,因此设定低平均适应度的种群的群间学习频率高。
宇宙间学习操作算法如下:
1) 生成[0,1]之间的随机数rand,如果rand<Ps(Ps为slave种群的学习频率),则执行下面的操作;
2) 向master发送宇宙间学习请求,在可能的情况下获取master上的全局最优模式;
3) 计算宇宙中个体的适应度,并调整Ps,Ps可如下计算:
maxfitness,minfitness,avefitness分别为宇宙中的最大适应度,最小适应度,平均适应度,μ为调整系数,一般取1.0。
2.2.2 种群交互
在MPMQEA 中最能体现各宇宙结构信息的是各宇宙的演化目标。于是我们提出了一种种群交互操作。通过在两宇宙之间暂时交换各自的演化目标,使得本宇宙的结构信息有效地传递给另一参加交互的宇宙,并对对方宇宙的演化方向产生影响,同时本宇宙也从对方宇宙的演化目标中获得对方的演化信息。具体实现如下:
(1) 按确定的选择概率从宇宙中选取若干个体;
(2) 再随机选取若干其他宇宙,分别以各宇宙的演化目标作为若干个体当前的演化目标,对个体进行一次量子旋转门演化操作;
(3) 重复(1)和(2) 操作,直至全部宇宙都进行量子纠缠交互操作。
移民操作和量子交互操作都可实现宇宙间信息的交互,但两者侧重点不同。前者是将最佳个体按确定的拓扑结构和移民策略,在各宇宙中传递;后者是将各宇宙的演化目标通过量子交互的方式进行交互。 两者相辅相成,使得整个系统的收敛速度加快,运算效率提高,且能有效地避免早熟收敛。
2.3 多宇宙并行免疫量子进化算法的算法流程
MPMQEA算法的具体步骤如下:
1.初始化各宇宙中的所有子种群:按照宇宙的数目将整个种群分成若干个子种群,并将所有的子种群进行初始化。
2.选择一master种群作为虚拟主服务器,其余种群为slave种群。
3.进入循环:
(1) 每个子种群单独进化若干代。
(2) 在master种群和slave种群之间执行基于学习的移民,在宇宙间执行模拟量子纠缠的交互。
(3) 重新循环,直至规定的遗传代数或演化目标。
MPMQEA所需的种群规模小,只需在master种群和slave种群间迁移最佳个体,从而通信开销很小,master种群能及时获得全局最佳个体。若计算规模大可以选择多个master种群,各master种群间以环形结构相连,master种群中可再选择一种群作为虚拟主服务器,以交换和保存各master种群中的最优个体。slave种群需要学习时可获取此master种群中的最优个体。
3 实验结果及分析
本文选取了Ackley函数f1,对多宇宙并行免疫量子进化算法(MPMQEA)的并行性能进行测试。
f1(x1,x2)
c1=20 c2=0.2 c3=20 e=2.71282
f1是一个多峰值函数具有许多的局部极小点,其中只有一个是全局极小点,全局极小值为f(0,0)=0。利用传统的优化方法往往容易陷人局部最优,因此该函数成为进化算法能否实现全局最优搜索的测试函数。局域网的普及为并行性能的测试提供了平台,我们将种群分成若干子群,每个子群在局域网的一台PC机上运行,表1为实验结果。
由表1 可以看出多个子群并行执行可显著减少执行时间,例如:3个结点比一个结点的总执行时间减少43秒,但是当子群数目继续增加时,执行时间几乎不再减少,例如:8个结点比4个结点的总执行时间仅仅减少2秒,因为子群数目太多则结点间的通信代价会急剧增加。实验表明子群数目一般为3至5个效率较高。
4 结束语
分析讨论并行进化模型理论及性能,结合笔者曾经提出的基于免疫原理的量子进化算法,又设计了多宇宙并行免疫量子进化算法(MPMQEA),MPMQEA所需的种群规模小、收敛速度快、运算效率高且能有效地避免早熟收敛,基于学习的移民和模拟量子纠缠的交互策略导致通信开销很小。我们用典型的测试函数验证了它的并行性能。接下来要进一步充分挖掘和利用量子的并行机制,探索更高效合理的并行进化模型,研究其中参数(包括子群数目)设置的合理性。
摘要：分析讨论并行进化模型理论及性能,提出了基于学习的多宇宙并行免疫量子进化算法,算法中将种群分成若干个独立的子群体,称为宇宙。并给出了多宇宙的并行拓扑结构,提出了宇宙内采用免疫量子进化算法,宇宙之间采用基于学习的移民和模拟量子纠缠的交互策略进行信息交换。这样能提高种群多样性,有效克服早熟收敛现象。算法综合了量子计算的天然并行性和免疫算法的充分自适应性,它比传统的进化算法具有更好的种群多样性,更快的收敛速度。通过并行实验验证了该算法的优越性。
关键词：并行进化模型,量子进化算法,免疫算子,交叉变异
参考文献
[1] Narayanan A,Moore M.Genetic quantum algorithm and its application to combinatorial optimization problem.In Proceedings of the 1996 IEEE International Conference on Evolutionary Computation,IEEE Press,1996:61-66
[2]You XM,Shuai DX,Liu S.Research and Implementation of QuantumEvolution Algorithm Based on Immune Theory.In Proceedings of the6th World Congress on Intelligent Control and Automation,2006,Ac-cepted for publication.
[3] Han K H,Kim J H.Quantum-Inspired Evolutionary Algorithms with a New Termination Criterion,Hε Gate,and Two-Phase Scheme.IEEE Transactions on Evolutionary Computation,IEEE Press,2004(8):156-169.
[4]Fukuda T,Mori K,Tsukiyama M.Parallel search for multi-modal func-tion optimization with diversity and learning of immune algorithm.Arti-ficial Immune Systems and Their Applications.Berlin:Spring-Verlag,1999:210-220.
[5]Mori K,Tsukiyama M,Fukuda T.Adaptive scheduling system inspiredby immune systems.In Proceedings of the IEEE International Confer-ence on Systems,Man,and Cybernetics,San Diego,CA,12-14 Octo-ber,1998:3833-3837.
[6]Ada G L,Nossal G J V.The clonal selection theory,Scientific Ameri-can,1987,25:50-57.
[7]Enrique A,Jose MT.Improving flexibility and efficiency by adding par-allelism to genetic algorithms,Statistics and Computing,2002(12):91-114.
【并行分析算法】相关文章：
并行化分析05-22
同步并行算法05-26
并行构造算法05-27
输油管道并行敷设间距设计分析与探讨09-10
论电力用户侧大数据分析与并行负荷预测09-10
基于多岛遗传算法的多状态动力学模型并行修正方法论文06-09
网络机群下多项式预处理EBE-PCG并行算法设计与实现06-27
并行检测05-01
双轨并行05-04
并行配置05-17