概率并行粒子群优化（共4篇）
概率并行粒子群优化 篇1
点云数据配准是逆向工程[1]的重要环节，它实现同一物体不同角度点云的坐标配准，配准精度直接影响后续建立完整三维模型的精确性。点云配准算法就是为了确立两个点集之间的对应点的映射关系，目前的方法中Besl等提出的迭代最近点算法(Iterative Closest Point,ICP)[2]及其改进算法[3,4,5]最具代表性。
ICP算法以粗配准后的两片点云为基础，迭代求解两片点云之间的距离最短对应点及相对位置变换参数，直到对应点距离的误差值满足设定的收敛值。它具有较好的精度，简单而且被广泛应用。但当两片点云初始相对位置相差过大时，收敛方向容易出现错误。且当出现噪声以及外点的情况时也容易造成配准失败。ICP的改进算法从不同程度上提高了原始算法的抗噪能力和配准效率，但也依然无法从根本上解决其对初始位置要求过高的局限。
为了克服ICP算法对初始位置要求高的局限，Chow[6]等提出基于遗传算法的点云配准算法，以平移和旋转角度组成的六维变量以及使用对应点距离最短为适应度函数求解点云的变换矩阵。Santamaria[7,8],Silva[9]以及Garcia-Torres[10]也分别从自适应进化、表面渗透向量以及和声搜索等角度提出了基于进化算法的点云配准方法。进化算法使用群体方式在解空间内进行全局搜索，克服了ICP算法对初始位置要求过高的弊端。但随着三维点云数据规模的扩大，单片点云的点数不断增加，进化配准算法的全局搜索时间成倍增长，由此导致的计算效率大幅降低已经无法满足目前点云配准的发展需求。
针对以上问题，本文提出一种受初始位置状态影响小且效率高的并行粒子群三维点云配准算法。粒子群优化[11](Particle Swarm Optimization,PSO)算法是一种典型的群智能优化方法，基于PSO的配准算法具有逻辑结构简单、变量参数少和易于程序实现等优点。与ICP算法相比，PSO配准算法有着优秀的全局搜索能力，且受点云相对初始位置和噪声干扰影响小。尽管如此，将PSO算法用于点云配准也仍存在处理大规模点云时速度缓慢效率不高的问题。随着GPU并行计算技术的快速发展，由NVIDIA公司提出的基于GPU的并行计算架构———统一计算设备架构[12](Compute Unified Device Architecture,CUDA)已开始在通用计算领域广泛应用。本文利用粒子群算法的天然并行性配合通用GPU技术，在基于CUDA并行计算环境中，以对应点距离最小为适应度函数，将并行PSO算法作为寻优策略实现点云的配准，最终得到一种速度快、精度高、受初始位置影响小的点云配准算法。
1 基于改进粒子群算法的点云配准
本文方法是使用粒子群算法以对应点距离平方和最小为准则，在六维空间(平移变量x,y,z和旋转变量α，β，γ)内搜索寻优，最终得到两片点云的相对旋转平移矩阵，经过空间变换使两片不同坐标系下的点云配准到同一坐标系。
1.1 粒子群优化算法及其改进
在基本粒子群算法中，单个个体可以理解为在n维变量空间中重量和体积忽略不计的粒子，每个粒子在n维搜索空间中运动，由给定的速度参数决定其运动的方向和距离。受这个速度参数的影响，粒子会朝着位置最优的粒子方向移动，并不断发现新的最优位置，经过一代代搜寻最后找到最优解的位置。在每一代搜索中，粒子将追踪两个最优位置，一个是粒子本身到当前为止找到的最优位置pbest，另一个为全种群的所有粒子当前找到的最优位置gbest。
设在D维搜索空间里，有一个规模大小为M的种群，第i个粒子在空间中的位置可以表示为xi=(xi1,xi2，…，xiD)，第i个粒子所经历过的当前最好位置(最优的适应度)可记为Pi=(pi1,pi2，…，piD)，每个粒子自己的飞行速度记为Vi=(vi1,vi2，…，viD),i=1,2，…，M。在整个群体中，所有粒子经历过的最好位置为Pg=(pg1,pg2，…，pgD)，每一代粒子根据式(1)和(2)更新自己的速度和位置
这里引入了Shi和Eberhart[13]的惯性权重方案，可以动态控制前一速度对当前速度的影响。其中，w为惯性权重;c1和c1为学习因子;r1和r2为[0,1]之间的随机数。Tmax为最大迭代次数，wini为开始时惯性权重值，wfin为最终惯性权重值。PSO算法在搜索后期会趋于聚集到同一个或多个位置上，种群多样性被减弱，可在式(1)后端加上一个扰动项，以增强粒子的多样性[14]。
式中:r为扰动项，是[0,1]之间的随机数，取值大小遵循标准正态分布。结合式(2)～(4)就是本文粒子速度与位置更新规则。
为了保证粒子能在规定的搜索空间内寻优，同时又避免粒子向边界聚集，陷入范围边界上的局部最优，改进算法对越界的粒子采用重新初始化的方案:当xid>xdmax或者xid<xdmin时，则xid=ximin+r(ximax-ximin)。粒子群算法因此获得兼顾全局和局部的搜索能力。
1.2 三维点云的配准
点云配准的过程是将不同坐标系下的两片点云经过坐标变换使两片点云对应的部分相互重合，判断配准效果的标准即粒子群算法的适应度函数至关重要。
点对点距离最近法的基本原理是:对于原始点集中一点，在目标点集中寻找与之对应的最近点。最近点搜索的实现通常是使用kd-tree[15]，它可以缩短最近点集搜索的速度，极大地减少运算量，大幅提高运算的效率。
对于原始点云S1={Pi}，目标点云中与其相对应点S2={Qi}，目的是求两片点云的旋转平移变化T。假设S2是由S1经过变换矩阵T转变而来，那么对于所有点i来说，T(Pi)与Qi距离应该为0。然而由于点云是经过激光扫描采集而来的，必然会存在测量误差和量化误差，所以T(Pi)与Qi距离差不为0。这个距离差越接近于0，则表示配准效果越精确。可以把点云配准问题转化为关于求T(Pi)与Qi距离最小的优化问题[如式(5)]。而粒子群算法对于这种离散优化问题具有非常高的寻优效率和精度。因此把对应点距离最短作为粒子群算法的寻优准则，找到最优值对应的旋转平移矩阵，按照这个矩阵将两片点云的相对位置重合在一起，从而实现点云的配准。
变换矩阵T包含6个元素:平移向量x,y,z以及旋转矩阵α，β，γ。这是一个六维函数的优化问题。当两片点云最大限度重合时，sum(min Ei)的值最小。
在未确定对应点时，对于给出S1(大小为N1)中的点Pi和S2(大小为N2)中的点Qj,Ei是T(Pi)到S2所有点的距离最小值[6]，由此可得到
式中:F(T)表示对应点的距离平方和，利用粒子群算法在六维空间内找到F(T)最小值，就能得到对应的旋转平移矩阵T，从而达到配准两片点云的目的。
2 基于CUDA的PSO配准算法
为了能让粒子群配准算法能有更高效的计算效率以适应目前大规模点云配准的需求，本文采用GPU加速技术在CUDA的环境中将PSO配准的运算过程分配到GPU各个线程当中去执行，把多路运算的时间缩短到跟单路运算的时间相似，从而大幅提高运算效率。
2.1 CUDA编程模型
CUDA(Compute Unified Device Architecture)，是一种将GPU作为数据并行计算设备的软硬件体系，它能够利用GPU的并行处理单元比CPU更高效地解决复杂的计算任务[16]。在使用CUDA对PSO算法加速时，先要在CPU上提前做好各项准备，例如复制点云据到GPU设备的内存中，线程的规划分配等。然后，CPU开始调用Kernel入口函数，程序会自动跳转到GPU上运行，多路线程同时开始并行执行。CUDA编程模型如图1所示。
图1中CPU在调用Kernel函数程序时需要向设备输出两个参数，使GPU能确定要分配Grid和Block的数目。在CUDA编程架构下，一个Grid中包含若干个Block块，一个Block块又包含若干个thread(线程)，thread是GPU设备中最小的执行单位，能够并行执行的最大线程数取决于设备显卡配置和显卡上的处理器数目。
2.2 基于CUDA的并行PSO配准算法实现
粒子群配准算法和其他进化类配准算法一样，都是基于群体模型的优化搜索算法。由1.2节可知，其高效的全局寻优能力非常适合解决点云配准问题。
基于粒子群的点云配准算法中要计算点与点在三维空间中的距离，由于点云中所含点的数目庞大，在寻找最近点的过程中会产生非常大的计算量。假设两片点云规模都是30 000个数据点，每个点都是一个三维坐标，则每寻找一次对应点就会产生至少3×30 000×30 000次的平方差计算，而这仅仅是迭代一次计算量中的一小部分。如果配准程序放在CPU中串行执行，即使使用高频率多核心的处理器仍然会显得运行时间过长，效率不高。而GPU上有着比CPU多数十倍的运算执行单元，蕴含非常强大的计算能力。
在粒子群配准算法中每个粒子六维变量T和其速度的更新是互不干扰的，每个粒子计算最优距离F(T)的过程是相互独立的，粒子个体六维变量最优位置的更新也是可并行的。算法中蕴含的这种并行性可以使笔者借助CUDA并行架构调动GPU中庞大的运算单元并行的执行点云配准中大量数据计算。
因此笔者在GPU中建立与粒子数相同的线程，每个粒子与每个线程一一对应，将本来需要在CPU中轮流执行每个粒子的计算转变为在GPU中所有粒子多路同时执行的计算。在每个线程中单独执行一个粒子的六维变量和最小距离的更新与计算，利用GPU计算的并行性，把多个粒子的总计算时间缩短到接近一个粒子的计算时间，从而大幅提高计算速度，缩短PSO配准算法的运行时间。算法流程如图2所示。
3 实验与分析
为了验证本文算法的可行性和通用性，实验采用了斯坦福大学计算机图形学实验室[17]提供的不同大小不同形状的点云数据进行配准。
3.1 实验设计
实验以点云数据库中的Stanford bunny00和Stanford bunny45两片点云为例进行配准验证。浅色点云(bunny000)含有40 256个数据点，深色点云(bunny045)含有40 097个数据点。实验所采用的计算环境配置如表1所示。配准中PSO算法以F(T)为适应度函数，在六维空间内搜索(平移变量x,y,z以及旋转变量α，β，γ。)设置平移变量的搜索范围为两片点云最大距离的2倍，旋转变量搜索范围-45°～45°。CUDA环境中，在CPU设置PSO初始种群为1 000，在变量范围内随机初始化粒子位置和速度，GPU调用一个Block块内含1 000个thread线程与每个粒子一一对应并分配合适的空间。
程序开始时，CPU完成初始化PSO的各项参数并调用内核模块，程序跳转到GPU上并行执行。此时每个粒子互不干扰的同时依次执行计算适应度函数，更新自身个体最佳位置，计算全局最佳位置和更新自身位置和速度。并依此循环直至满足PSO算法所设定的收敛条件。
3.2 实验结果
程序运行结果如图3～6所示，可以看出不同角度的兔子点云相同部分重叠在一起，交错有致，达到较好的配准效果。
3.3 GPU加速前后运算时间对比
为了进一步说明GPU并行计算对PSO配准算法速度的增幅，将之与传统CPU上串行的PSO配准算法做对比，针对点云Stanford Bunny,Dragon,Happy Buddha，以bun000(40 256个点)，dragon UpRight＿0(42 641)和happy StandRight＿0(78 056)作为源点集，bun000(40 097),dragon UpRight＿24(35 774)和happy StandRight＿24(75 582)作为目标点集在相同的硬件条件下进行配准，都设置粒子数为1 000，进行30次迭代，此时3组点云的配准误差相似，配准效果都良好。耗时对比结果如表2所示(保留5位有效数字)。由于GPU并行环境中所有粒子同时执行计算，而CPU中每个粒子轮流串行的执行计算过程，从表中可以看出前者要比后者节约大量的计算时间。
3.4 本文算法与ICP算法受初始位置影响对比
为了验证两片点云初始位置变化时对本算法的影响，以Stanford Bunny为例，人工的对源点集bun000进行旋转平移，再与目标点集bun045进行配准。分别使用ICP算法和本文算法进行配准，不考虑时间的情况下，只看最终能否配准成功。在误差(对应点距离平方和)都趋于收敛基本不变时，对比两种方法的配准结果。通过多次显示试验，当误差在0.018及以下时两片点云已经达到很好的配准效果，当误差高于0.1则表示完全无法配准。如表3所示。
3.5 结果分析
综合以上实验，受限于硬件配置和对CUDA编程优化有限，基于GPU并行加速的PSO配准算法已经比未经GPU加速的PSO配准时间缩短10倍左右，如若使用专业的计算显卡或提高对CUDA编程优化，则能带来更大幅度的速度提升。而表3也表明本文算法在点云初始相对位置不断改变时仍能达到较好的配准效果。受点云初始位置影响小，克服了ICP算法受初始位置限制大的弊端，具有较高的通用性和稳定性。
4 结语
本文以对应点距离最小为适应度函数将点云配准转过程变为粒子群优化算法搜索变换矩阵最优参数的过程，并通过CUDA架构平台对PSO算法进行GPU上的并行加速，充分利用了粒子群算法的全局搜索寻优能力和GPU高速并行的浮点计算能力。经过不同的对比试验，验证了本文算法的可行性、高效性和稳定性，并且有效降低了配准效果受点云初始位置的影响，具有更强的适应性和通用性。
概率并行粒子群优化 篇2
混沌是存在于非线性系统中的一种较为普遍的现象.混沌运动宏观上无序无律, 具有内在的随机性、非周期性和局部不稳定性;微观上有序有律, 并不是完全的随机运动, 具有无穷嵌套的自相似几何结构、存在普适性规律, 并不是杂乱无章的.利用混沌运动的这些性质进行优化搜索能较好地避免粒子群算法陷入局部解.目前利用混沌优化的粒子群算法大都采用Logistic映射, 然而Logistic映射所产生的序列极不均匀, 因此较大地浪费了计算时间, 使得算法收敛速度慢.并行计算是实现高性能、高可用计算机的主要途径.采用并行方式, 将粒子群的追踪过程在各个相对独立的进程内完成, 能较大提高粒子收敛速度, 同时能保证各个种群的多样性, 不易陷入局部解.
1. BSP并行计算模型
BSP模型 (Bulk Synchroneous Parallel) 是由Valiant提出的“块”同步模型, 是一种分布存储的MIMD计算模型, 支持消息传递系统, 块内异步并行, 块间显式同步.
在BSP模型中, 计算由一系列全局同步分开的长度至少为L的超步组成.在每个超步中, 每个处理器均执行局部计算, 并通过网络接收和发送至多h条消息 (称为h-relation) , 然后作同步检查, 以确定该超步是否完成.在每个超步开始时, 处理器仅对已经有效的局部数据进行操作, 若数据未准备好, 则推迟到下一个超步开始时再进行计算.BSP模型主要由3个参数表示, 分别是:p为处理单元的数目;g为整个系统的计算能力与网络传送消息的通信能力的比值;L为路障同步时间.
2. 粒子群算法
2.1 标准粒子群算法
PSO初始化为一群随机粒子 (随机解) , 速度vi= (vi1, vi2, …, vid) 决定粒子在搜索空间单位迭代次数的位移, 其中第i个粒子在d维解空间的位置表示为xi= (xi1, xi2, …, xid) , 然后通过迭代找到最优解.在每一次迭代中, 粒子通过动态跟踪两个“极值”来更新其速度和位置, 第一个就是粒子本身所找到的最优解, 这个解叫做个体极值pi= (pi1, pi2, …, pid) , 另一个极值是整个种群目前找到的最优解, 这个极值是全局极值pg= (pi1, pi2, …, pid) .另外也可以不用整个种群而只是用其中一部分作为粒子的邻居, 那么在所有邻居中的极值就是局部极值.粒子在找到上述两个极值后, 就根据如下公式来更新其速度和位置:
其中c1, c2称为学习因子, 通常取c1=c2=2, rand1, rand2是均匀分布在0和1之间的随机函数, w是加权系数, 取值在0.1至0.9之间.
2.2 混沌粒子群算法
假定粒子群优化算法目前在迭代的第n步, 现在算法中有如上的三个参数x1=w, x2=c1=c2待优化, 利用混沌搜寻来得到这三个参数的合适的值, 然后再更新粒子的速度和位置, 进入到下一步迭代.假定群体的第 (n-1) 步迭代中所有的结果已知, 现在利用两个混沌变量独立运行m步, 得到m组参数的值, 分别计算这m组参数值对应的群体更新后的速度和位置变量, 产生新的第n步的粒子群.为了评估这m组参数的优劣, 需要计算每组参数对应的粒子群优化得到的当前全局最优解, 以此作为每组参数的适应值函数, 取其中最优的解对应的参数作为第n步的参数值, 然后开始第 (n+1) 步迭代, 所有步骤和上面一样.在计算的过程中, 如果有一组参数得到的最优适应值在可接受的范围内, 则可以立即结束程序.
3. BSP混沌粒子群算法
步骤1:初始化整个种群.对每个粒子的随机位置和速度进行初始设定.每个粒子由计算得到初始的适应值和初始的个体最好位置pi及初始的群体最好位置pg.
步骤2:将整个种群分为几个子群体, 各个子群体用混沌算子优化粒子群.
(1) 设定初始参数xr0, r=1, 2, 并对其实施变换
(2) 利用混沌搜索得到M个tr, 反变换为xr.
(3) 计算每组参数对应的适应值, 取其中最优的一组作为当前步的参数.
步骤3各个子群体相互交换信息, 用新的参数不断更新全局最好位置.若某个子群体中粒子的适应值比全局最好位置pg的适应值好, 则它作为当前的全局最好位置pg.其他子群体依据该pg值继续进化, 直到进化最慢的子群体更新完全局最好位置pg.
步骤4进行粒子群优化, 更新粒子群速度和位置.若未达到结束条件, 则返回步骤2.2, 各子群体继续循环迭代, 直到满足条件.
4. 仿真实验
为了测试算法的有效性, 选用了标准PSO与本文算法BSPCPSO进行比较实验, 测试函数为Rosenbrock函数和Rastrigrin函数, 算法的初始参数为:w=0.9, 学习因子c1=c2=1.1, 种群规模90, 每个子群体有30个粒子.对每种测试函数连续进行30次实验, 实验环境VC++6.0.表2为函数寻优的实验结果.
概率并行粒子群优化 篇3
这些研究表明粒子群算法的收敛过程是通过粒子向收敛目标点的移动实现的。粒子向目标点的移动即可以按一定的轨道实现,也可以按给定的概率密度随机移动实现。本文从分析粒子随机移动时所遵循的概率密度函数的性质入手,首先给出算法收敛时粒子的概率密度函数所应该满足的条件,并构造出符合要求的几种概率密度函数,进而通过概率密度函数构造新的粒子群算法,最后通过标准测试函数的计算,对算法进行了验证。
1 粒子群算法
粒子群算法是一种基于群体智能的优化进化算法[8,9,10]8—10[8,9,10],它将解空间中的备选解称为“粒子”,每个粒子根据自身的认知和群体信息来决定他们移动的方向和距离,通过简单的速度位移模型,实现对解空间的搜索,具有较强的全局搜索能力和鲁棒性,由于不需要借助问题的特征信息,因此适合于复杂优化问题的求解。
粒子群算法可以描述为:设有数量为N的粒子组成一个种群在q维的搜索空间搜索,其中第i粒子可以表示为:Xi=(Xi1,Xi2,…,Xiq),其对应的速度表示为Vi=(Vi1,Vi2,…,Viq),粒子i搜索到的历史最优位置记为Pi=(pi1,pi2,…,piq),所有粒子搜索到的最优位置记为Pg=(pg1,pg2,…,pgq)。
算法的位置和速度更新公式:
式中k为当前的进化代数;ω称为惯性权重;c1、c2称为权重系数,它表示粒子对自身知识与群体知识的认知;r1,r2∈[0,1]为均匀分布的随机数。
Clerc证明粒子群算法中任意第i粒子的移动是以Gi=(gi1,gi2,…,giq)为目标点,其中gij(t)=φijpij(t)+(1-φij)pgj(t),φij=c1r1/(c1r1+c2r2)。
即随着迭代的过程,粒子逐渐收敛到Gi。标准的粒子群算法中粒子的收敛是以轨道的形式实现的,因此粒子只会出现在解空间的有限区域,不能覆盖整个空间。这是粒子群算法的缺陷。为保证全局性,更好的移动方式应该是粒子以一定的概率分布向Gi聚集。在聚集过程中,粒子仍会以一定的概率出现空间任何一点。
2 概率密度函数的构造
粒子群算法中如果改变粒子向目标点的移动方式,在保证收敛的条件下,使得粒子可以以一定的概率密度出现在空间任何一点,设此时粒子所服从的概率密度函数为f(x),则函数f(x)满足:
(1)非负性:f(x)≥0。
(2)正则性:
满足条件(1)、(2)使得f(x)能够成为概率密度函数。而要使得粒子能够实现全局收敛,f(x)还应该满足如下条件:
(3)f(x)满足对称性。
(4)f(x)在对称点左侧严格递增,右侧严格递减,在对称点取得最大值。
条件(3)使得在距离Gi相同的位置上粒子出现的概率相同;条件(4)保证粒子在Gi的聚集性,即在Gi出现的概率最大,距离Gi越远概率越小;条件(5)保证全局性,即粒子可以出现在整个解空间。
通过这些条件的分析,可以大致勾画出粒子所服从的概率密度函数的形式,从而进一步构造出这些函数。
2.1 构造第一类概率密度函数
构造如下函数:
式中μ,λ,k为常数。
显然函数f(x)满足条件(1)、(3)~(5),根据条件(2)函数f(x)需要在整个实数区间可积。下面就k取值的不同分别给出函数的具体形式:
2.1.1 当k=1时
由于,故
根据条件∫+∞-∞f(x)dx=1,可得μ=λ/2,即当k=1时,
2.1.2 当k=2时
由于,故
则
即当k=2时,
2.1.3 当k=1/n(n为大于1的自然数)时
令x=tn,则
则μ=λn/2(n!)。即当时,
2.2 构造第二类概率密度函数
构造如下函数:
式中μ,λ,k为常数。
易证函数g(x)满足条件(1)、(3)~(5),根据条件(2)函数函数g(x)在整个实数区间可积,故有:
由于
根据条件∫+∞-∞g(x)dx=1,可得
即当k>1时,
参数a在函数中只起到了一个平移的作用,保证函数能够在零点有有限值。故参数a的取值可以是任意大于零的常数,为简化运算,在后面的实现中将其设定为1,即
3 参数λ需要满足的条件
上面对两类概率密度函数的构造给出四个具体函数形式:
式中,λ>0,k>1,n为大于1的自然数。
为保证粒子群算法经过迭代后能够收敛,每个粒子经过迭代后都应该能够聚集到其目标点,即要保证对于第i粒子,当进化时间(或迭代次数)t→+∞时,Xi→Gi。
定理3.1如果Xi-Gi服从上面的概率密度函数式(1)~式(4)之一,当进化时间(或迭代次数)t→+∞时,如果λ→+∞,则第i粒子以概率1收敛到Gi,即对任意小的正数ε,成立
证明:设随机变量Xi-Gi的概率密度函数为f(x),f(x)取式(1)~式(4)中的一个,无论f(x)取那个函数,都有:
δ(x)即为狄拉克函数,除零点外其他点取值均为0,且满足
如果t→+∞时,λ→+∞,则
结论成立。
由定理3.1可知,在构造算法时,为保证算法收敛参数λ应设置成迭代次数的函数,且随迭代次数的增大而趋于无穷。
4 使用随机模拟方法构造粒子移动方程
对于式(1)~式(4)这四个概率密度函数,函数式(3)由于形式复杂,难以使用随机模拟的方法构造粒子移动方程。故选取函数式(1)、式(2)、式(4)构造方程。对函数式(1)与式(4)蒙特卡洛法进行模拟,即使用(0,1)区间的均匀分布产生的随机数来模拟概率的发生。而对函数式(2)由于其为正态分布的概率密度函数,可使用标准正态分布产生随机数来模拟。在此定义两个产生随机数:u表示(0,1)区间的均匀分布随机数。v表示标准正态分布的随机数。下面对这三种函数分别生成粒子移动方程。
4.1 对函数式(1)构造粒子移动方程
设随机变量Xi-Gi的概率密度函数为
则分布函数
当x<0时,
当x>0时,
产生服从均匀分布的随机数u进行模拟:
即当u≤1/2时,
当u≥1/2时,。则
故
从而得到粒子移动方程:
通过与量子行为粒子群算法进行对照可知[7],粒子移动方程式(5)与量子行为粒子群算法中粒子的移动方程式等效的。
4.2 对函数式(2)构造粒子移动方程
设随机变量Xi-Gi的概率密度函数为
令,则概率密度函数可写为:
即Xi-Gi~N(0,σ2),故
产生标准正态分布的随机数v,同时令
从而得此时粒子移动方程为:
4.3 对函数式(4)构造粒子移动方程
当随机变量Xi-Gi的概率密度函数为
则分布函数
当x<0时,
当x>0时,
产生服从均匀分布的随机数u进行模拟:
可得:
从而得到粒子移动方程:
5 算法实现与测试
根据上面三种粒子移动方程,可给出三种粒子以概率向目标点移动的粒子群算法,依次定义为算法1、算法2、算法3,其中算法3中经过测试当k=3时效果最好,故算法3的粒子移动方程取k=3。
5.1 参数λ的确定
由定理3.1,参数λ应设置成迭代次数的函数,且随迭代次数的增大而趋于无穷。采用如下定义方式[11]:
式中为当前所有粒子历史最优位置的均值。参数α根据实际问题设置,在下面的测试中,经过计算比较,α统一设置为0.7。
5.2 算法测试
选取3个标准测试函数进行算法测试:
(1)Sphere函数
(2)Rastrigin函数
(3)Ackley函数
三个测试函数均为存在极小值的多维函数,其最优状态和最优值都是:min(hi(X*))=hi(0,0,…,0)=0;i=1,2,3.
与标准粒子群算法进行比较,种群规模统一为80,最大迭代次数设为1 000,对20维的函数进行优化,运算次数均为20次,粒子群算法中参数ω=0.7,c1=c2=2。计算结果见表1、表2。
由表1、表2可知,对于三个测试函数,除算法2外,本文所得其他两种算法运算结果均显著优于标准粒子群算法。算法2对Ackley函数的运算结果优于标准粒子群算法,算法1与算法3相比较,算法3收敛更加稳定。
6 结论
(1)给出了粒子群算法中粒子向目标点随机移动时,其概率密度函数所应遵循的条件,并构造了两大类共四种符合要求的概率密度函数。
(2)给出了算法收敛时,概率密度函数中的参数所需满足的条件,并通过随机模拟的方法,将其中三种转化成立粒子的移动方程,从而构造出不同于传统粒子群算法的三种算法。
(3)选择了三个标准测试函数对算法进行测试,在相同条件下进行了20次的优化运算,除算法2外,算法1与算法3表现均显著优于标准粒子群算法。
摘要：粒子群算法的收敛过程是通过粒子向收敛目标点的移动实现的。粒子向目标点的移动既可以按一定的轨道实现,也可以按给定的概率密度随机移动实现。通过分析随机移动时概率密度函数所应遵循的条件,给出了两大类共四种符合要求的概率密度函数,使用随机模拟的方法,将其中三种转化成为粒子的移动方程,从而给出了不同于传统粒子群算法的三种算法。经过在相同条件下对三个标准测试函数的优化运算,除算法2外,算法1与算法3表现均显著优于标准粒子群算法。
关键词：粒子群算法,概率密度函数,收敛性,随机模拟
参考文献
[1] Bergh F V D.An analysis of particle swarm optimizers.Pretoria:U-niversity of Pretoria,2001
[2] Bergh F V D,Engelbrecht A P.A new locally convergent particle swarm optimiser.IEEE International Conference on systems,Man and Cybernetics,2002
[3] Clerc M,Kennedy J.The particle swarm:explosion,stability and convergence in a multi-dimensional complex space.IEEE Transactions on Evolutionary Computation,2002;6(1):58-73
[4] Trelea L C.The particle swarm optimization algorithm:Convergence analysis and parameter selection.Information Processing Letters,2003;85(6):317-325
[5] Emara H M,Fattah H A A.Continuous swarm optimization technique with stability analysis.Proceedings of the American Control Conference,Boston,MA,2004:2811-2817
[6] Kadirkamanathan V,Selvarajah K,Fleming P J.Stability analysis of the particle dynamics in particle swarm optimizer.IEEE Transactions on Evolutionary Computation,2006;10(3):245-255
[7] Sun Jun,Feng Bin,Xu Wenbo.Particle swarm optimization with particles having quantum behavior.Proceedings of IEEE Congress on Evolutionary Computation,Portland,2004:325-331
[8] Eberhart R,Kennedy J.A new optimizer using particle swarm theory.Proceeding of the 6th International Symposium on Micro Machine and Human Science,NJ:EEECS,1995:39-43
[9] Shi Y,Eberhart R C.A modified particle swarm optimizer.Proceedings of the IEEE International Conference on Evolutionary Computation,1998:69-73
[10] Clerc M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization.Proceedings of Congress on Evolutionary Computation,1999:1951-1957
概率并行粒子群优化 篇4
基于以上现状,笔者针对更多的机器进行并行多机批调度问题,并提出了改进的粒子群优化算法。很多学者也提出了各种改进粒子群算法来求解调度问题,但大多改进的算法都只是考虑粒子群算法易早熟和易陷入局部最优的问题,忽略了在改善这些问题的同时也应关注算法的局部搜索能力及收敛速度等。如文献[11]将遗传算法中的交叉策略引入到粒子群算法中,只是改善了粒子群易陷入局部最优的缺陷,并没有考虑提高算法的局部寻优能力和收敛速度。文献[12]在基本粒子群算法的基础上,提出了一种二维粒子表示方法,并采用粒子位置向量多次交换的局部搜索方法使粒子有效地跳出局部最优,但这种改进方法对算法本身的收敛速度有一定的削弱影响。因此,针对上述提到的各方面问题,在文献[13,14]的基础上,笔者综合了几种改进的方法, 提出了一种较全面的改进粒子群优化算法。*
1并行多机批调度问题描述
并行多机批调度是研究工件在多台功能相同的机器上的加工过程,每个工件仅需在某一台机器上加工一次。加工时间相同的工件可以组批, 可同时在一台机器上加工。因此,对具有相同到达时间的并行多机批调度问题可描述为: 有n个相互独立的工件,m台完全相同的机器,每个机器的最大容量为B,每个工件都有确定的加工时间ti( i =1,…,n) ,且均可由m台机器中的任一台完成加工任务。Ci表示工件i的完成时间,Cmax表示所有工件的最大完工时间,即Cmax= max{ Ci} ; F表示批调度的优化目标———最小化最大完工时间,即F = min Cmax。需要满足的约束条件为: 每台机器在每一时刻加工的工件个数不能超过B, 一旦工件在机器上加工就不能中断直至其被加工完成。
2改进粒子群算法的设计
针对粒子群算法易产生早熟收敛及局部寻优能力差等缺点,笔者提出了一种基于二阶振荡和自然选择的随机权重混合粒子群算法,用于求解函数优化问题。并采用一种基于批序列的编码方式,将其运用于求解并行多机批调度的优化问题上。
2.1粒子二阶振荡
针对标准粒子群优化算法(PSO)易陷入局部最优,缺少粒子的多样性,将二阶振荡引入粒子的速度公式中,从而提高粒子群体的多样性,改善算法的全局收敛性。其速度公式更新为:
式中c1、c2———粒子个体的加速权重系数和粒子群体的加速权重系数;
r1、r2———两个在[0,1]上均匀分布的随机数;
w———惯性权重因子;
ξ1、ξ2———随机数。
另外,
在算法前期取:
在算法后期取:
从速度公式中可以看出,此时的速度不仅与当前位置相关,还与微粒位置的变化有关。这样, 粒子可更快地向有利的方向运动,增强了全局和局部收敛性,加快了收敛速度。
2. 2权重与速度的变化
多数粒子群算法都是采用线性递减权重的方法,但该方法有时会使算法陷入局部最优,而采用随机分布的w可以克服这种局面。w的计算公式为:
式中N( 0,1) ———标准正态分布的随机数;
rand( 0,1) ———0 ~ 1之间的随机数;
u———随机权重平均值;
umax、umin———随机权重平均值的最大值和最小值;
σ ———随机权重的方差。
为了提高算法的性能,对最大速度进行了线性递减操作,公式如下:
式中max、min———最大速度的最大值和最小值;
M———最大迭代步数;
t———当前迭代步数;
vmax———最大速度。
在对算法进行上述改进的同时,笔者还引入了自然选择的思想来加快算法的收敛速度,即用群体中适应值最好的前1/N粒子的速度和位置替换群体中适应值最差的1/N粒子的速度和位置。N的取值不能过小也不能过大,若过小,无法达到粒子多样性和较好的全局性;若过大,粒子易陷入局部最优。经算法测试表明,N取5效果较好,即算例中只替换10%的粒子。
3粒子编码及算法实现
3. 1基于批序列的编码方法
基于批序列的编码方法有两个过程: 一是将工件分批; 二是将批分配给机。工件分批: 先将相同加工时间的工件放入一个批,再看批中工件数是否超过机器的最大容量Bmax,若没有,这些工件就分一个批,否则,将这些工件分成( Bmax- m + 1) 批( m表示具有相同加工时间的工件数) 。最后将那些没有重复的加工时间的工件单独成为一批,直到所有的工件都分配到各自的批中。批的分配: 将所有的批按加工时间的降序进行排列,整个粒子编码是面向批的,即通过对粒子位置进行排序,从而间接地对批进行重新排序。最后,按照重新排列的批顺序依次将批分配给空闲的机器。 例如对于6个工件,加工时间分别为{ 5,9,2,7,9, 5} ,首先进行分批,可分成{ ( 9,9) ,( 7) ,( 5,5) , ( 2) } 4批,再将这4批按工件序列进行编码,编码过程见表1。
位置按降序排列得: 0. 63、0. 55、0. 28、0. 09, 对应的批次是1、4、3、2。因此,批将按{ 1、4、3、2} 的顺序依次在空闲的机器上进行加工。
3. 2混合粒子群算法的步骤
按上述方法将基本粒子群优化算法进行改进,得到基于批序列编码的二阶振荡和自然选择的随机权重混合粒子群算法( BSNRPSO) ,其具体步骤如下:
a. 按照基于批序列的编码方式对工件进行分批,并按加工时间的降序进行排列,得到n个批数。
b. 设定粒子种群数量和最大迭代次数,对粒子群中的粒子xi和vi进行初始化,并对粒子按照基于批序列的编码方式进行编码,从而得到批的排序。
c. 按照工件次序和机器的空闲状态,将批分配到各机器上,同时计算该粒子的适应值,确定个体最优粒子和全局最优粒子。
d. 根据式( 6) 对粒子更新速度的最大值进行线性递减,以保证收敛。
e. 根据式( 1) 、( 2) 对粒子的速度和位置进行更新,算法前期取式( 3) 的值,后期则取式( 4) 的值。
f. 根据式( 5) 更新权重系数w。
g. 对每个粒子将其适应值与其经历过的最好位置作比较,如果较好,则将其作为当前的最好位置pbest。并比较当前所有pbest和gbest的值,更新gbest。
h. 将整个粒子群按适应值进行排序,用群体中最好的前1/N粒子的速度和位置替换最差的1 / N粒子的速度和位置,保持pbest和gbest不变。
i. 若满足迭代次数,则搜索停止,输出结果; 否则返回步骤d继续搜索。
4仿真计算及分析
笔者采用随机算法来获得算例,算例的规模按机器台数m、工件数目n和加工时间t3个标准来划分。机器台数有m1、m2、m3、m4四类问题,依次对应3、5、7、10台机器; 工件数目有J1、J2、J3、J4四类问题,依次对应20、50、100、150个工件; 工件加工时间有t1、t2两类问题,分别为[1,10]和[1, 20]分布。总共可产生32种不同的算例,每种算例记为mkJktj( k =1,2,3,4; j =1,2) 。例如m1J1t1表示3台机器、20个工件、加工时间服从[1,10] 的离散均匀分布的实例。在所有实例中,每台机器的最大容量Bmax均为5。
笔者对32种算例分别进行了实验,将基于工件序列编码的混合粒子群算法( JSNRPSO) 和基于批序列编码的BSNRPSO算法与传统的遗传算法( GA) 进行了对比。3种算法中,种群规模、最大迭代次数都一致,分别为m = 50、max gen = 100。 JSNRPSO算法与BSNRPSO算法的粒子群参数为: 自身学习因子c1= 2、全局学习因子c2= 2、权重平均最大值为0. 9,权重平均最小值为0. 4,权重方差为0. 2,淘汰概率为0. 1,速度限制在[-4, 4]之间,边界限制在[0,4]之间。每个实例均连续优化30次,仿真结果见表2。
从表2中的数据可以看出,就算法的最优值、 最差值、平均值和标准差进行比较,JSNRPSO算法比GA算法要好,而BSNRPSO算法比JSNRPSO算法的效果更好,尤其表现在并行机少、工件多的算例中。而对于并行机较多,工件较少的算例,3种算法的性能都差不多。因为此时问题的运算量低,传统的GA算法就能在迭代次数内找到最优解。在一些算例中,例如m4J4t2算例,BSNRPSO算法的标准差比JSNRPSO算法的标准差要大,这表明利用BSNRPSO算法得到的数据波动范围大, 但BSNRPSO算法的最优值、最差值、平均值都比JSNRPSO算法的要好很多,这表明BSNRPSO算法在处理多工件时,能更快地跳出局部最优,增加种群的多样性,快速找到更好的解,具有更强的寻优能力。
为了更好地比较3种算法性能的优劣,采用相对改进率这一指标来评价,改进算法U相对GA算法的改进率为:
式( 7) 中U代表JSNRPSO算法和BSNRPSO算法。改进率的结果见表3。为了更直观地比较两种算法的优越性,绘制了对应的算法平均值改进率,如图1所示,横轴代表工件不同的加工情况,纵轴代表机器台数不同情况下对应的相同算例的改进率的平均值。
由图1可知,JSNRPSO算法相对GA算法有一定的改进,但BSNRPSO算法的改进度更大,尤其表现在大规模的算例中,如多工件且加工时间长的情况。这说明BSNRPSO算法更能胜任复杂的生产调度环境。在工件数目少的情况下,如20个工件,运算量比较小,传统的GA算法就能找到较好的解,改进的空间不大。在表3中,m4J3t1算例,BSNRPSO算法的平均值改进率没有JSNRPSO算法的好,但利用BSNRPSO算法找到的最优解还是比JSNRPSO算法找到的最优解要好。
5结束语
针对粒子群算法本身的缺点提出了改进的算法,笔者将这种新的算法运用于求解并行多机批调度的问题中。通过实验验证,这种改进的算法对求解调度问题是有效的。并且在改进的算法中采用基于批序列的编码,这使得进一步改进后的算法更适合求解大规模的并行机批调度问题,对实际的工业调度具有一定的指导意义。
摘要：针对调度目标为最小化最大完工时间的并行多机批调度问题,提出了改进的基于批序列编码的混合粒子群算法。在基本粒子群算法的基础上,引入了学习因子二阶振荡、随机权重、最大速度线性递减及自然选择等方法,改善了算法本身易陷入局部最优及早熟收敛等问题,并解决了因引入新的方法 造成算法收敛速度慢及寻优能力差等问题。由仿真结果可知:改进的算法均优于常规的粒子群算法,且根据批序列编码的改进算法更优于常规基于工件序列编码的改进算法。