多核环境下并行粒子群算法

针对串行粒子群算法在解决大任务耗时过长的问题,提出一种共享并行粒子群(Shared-PSO)算法。充分利用多核处理能力缩短问题处理运行时间,设置共享区和采取粒子随机替换策略有效促进粒子信息的交流,其算法流程具有较好的通用性,允许利用多种串行粒子群算法完成粒子信息更新工作。在标准优化测试集CEC 2014上的实验结果显示新算法的执行时间是串行算法的1/4。新算法能够有效地改善串行粒子群的执行效率,扩展粒子群算法的应用范围。     

并行演化算法研究进展

并行计算与演化计算同为复杂问题寻优的现代技术.两者的结合不仅减少运行时间、提高解的质量,还增加计算能力,即增加应用领域.并行演化算法除了主从式、粗粒度、细粒度和分层四类并行化模型外,还有改进的并行演化算法.本文分析介绍加速比定义分类、迁移策略与并行演化算法的应用情况,总结前人对并行演化算法开展的理论分析与实践应用研究进展,并就该领域的进一步研究方向提出了一些看法,指出细胞状模型和并行遗传程序设计将成为两大研究热点.     

基于均匀设计的中心引力优化算法

中心引力优化（Central Force Optimization,CFO）算法是一种新型多维搜索确定型启发式优化算法,但由于它的初始探测器（Probe）计算复杂而导致CFO算法运行时间过长。针对初始探测器计算复杂问题,提出一种均匀设计方法,依此方法提出了基于均匀设计的CFO算法。将提出的CFO算法应用到典型测试函数中,并与CFO算法进行比较。数值结果表明,该算法保证寻优能力同时减少了CFO算法的运行时间,从而提高了CFO算法的效率。     

线云隐私攻击算法的并行加速研究

线云定位方法能保护场景隐私,但也存在被隐私攻击算法破解的风险。该攻击算法能从线云恢复近似点云,但其计算效率较低。针对该问题,提出了一种并行优化算法,并对其运行时间和加速比进行了分析。具体来说,分别采用SPMD模式和流水线模式实现了CPU多核并行和GPGPU并行。然后,进一步结合数据并行模式实现了异构计算,以达到最高的并行度。实验结果表明,并行优化算法加速比最大为15.11,最小为8.20;相比原算法,并行优化算法的还原点云相对误差控制在原误差的0.4%以内,保证了算法的精度。该研究对线云隐私攻击算法以及其他密度估计问题、不同场景下的线云隐私保护算法等有重要意义和参考价值。     

求解多维背包问题的MapReduce蚁群优化算法

应用MapReduce编程模式实现蚁群优化算法的并行化计算,提出基于MapReduce的改进背包问题蚁群算法.通过改进概率计算时机、轮盘赌、交叉、变异等技术,降低蚁群算法的计算复杂度.在云计算环境中应用该算法分布式并行地求解大规模多维背包问题,仿真实验结果表明,该算法能改善蚁群算法搜索时间长的缺陷,增强对大规模问题的处理能力.     

一种最小化安全多方计算任务的方法

安全多方计算（Secure multi-party computation：MPC）允许在不公开各参与方私有数据的情况下完成联合计算。然而,现有的计算任务往往涉及到多方海量数据集的分析与处理,使得MPC的实际可用性显著降低。提高MPC数据处理体量,是目前研究的主要方向之一。为提高MPC处理大规模数据的能力,将MPC算法与数据并行分析框架相结合,基于最小化多方计算任务的思想,提出安全多方计算效率优化技术。创建算法的有向无环图,标注MPC节点及非MPC节点,采用静态分析、查询重写转换和分区启发式等技术,最小化MPC计算量,提高计算的并发程度。以多方线性回归为例,讨论适应大数据分析的安全多方计算技术。实验结果表明提出的安全多方计算优化技术在确保计算精度的条件下能够显著降低计算耗时。算法提高了系统的效率,增强了MPC的实用能力。     

基于分层筛选和动态更新的并行选择集成算法

提出一种选择性集成学习算法,该算法利用多线程并行优化基分类器的参数,通过多层筛选和动态更新筛选信息获取最优的候选基分类器集合,解决了以往在集成学习中选择分类器效率低下的问题。集成分类器采用分解合并的策略进行加权投票,通过使用二分法将大数据集的投票任务递归分解成多个子任务,并行运行子任务后合并投票结果以缩短集成分类器的投票运行时间。实验结果表明, 相对于传统方法, 所提出的算法在平均精度、F1-Measure以及AUC指标上都有着显著提升。     

基于GPU的交叉相关外推并行化算法

为克服交叉相关外推算法时间复杂度高、运算时间过长的缺点,提出一种基于GPU的快速并行化算法,应用于地闪落点的外推预测。首先分析串行的算法流程,然后对算法进行并行化分析设计,再针对AMD系列GPU硬件架构特点,运用OpenCL技术从主存与设备内存之间的数据传输、显存访问模式等方面对算法进一步优化。最后将地闪监测实况数据与本算法外推计算结果进行比对,分析不同精度下串行与并行算法的计算效率。实验结果表明,该算法充分利用GPU强大的并行计算能力,计算速度提高了近17倍。     

遗传演化SPA流失预测算法及并行化

随着电信行业竞争日益激烈,基于数据挖掘的客户流失预测对于电信运营商提升客户服务质量具有重要意义。为提升客户流失预测效率和提高预测模型的泛化能力,引入人工智能的遗传演化思想改进了基于心理学扩散模型SPA(spreading activation)的流失预测算法,提出了基于遗传演化的流失预测算法GASPA(genetic algorithm basedSPA)。GASPA在演化中能自主学习和优化模型参数,通过在真实电话呼叫数据和短消息数据上实验,发现GASPA在精确度上性能优于固定步长方法,在Lift曲线值上性能优于SPA,显著提高了SPA的Lift曲线值,增强了SPA的流失预测效果。为处理海量电信数据,实现了在云计算平台上的并行化方案M-GASPA(MapReduce-GASPA),在提高GASPA可处理数据规模的同时降低了运行时间。     

基于SPMD的C4.5并行决策树加速分析

决策树分类方法是解决数据挖掘、模式识别中分类任务的有效方法,然而,在大规模的数据集上运行时,其运行效率受到严重影响。文中选取决策树的代表算法C4.5算法为研究对象,利用算法固有的并行性对其进行优化研究。文中利用MATLAB实现串行的C4.5决策树,并对构成该决策树的子函数进行运行时间分析,从而确定信息增益率计算的复杂性为限制算法速度的关键因素。针对此计算瓶颈,结合决策树算法在子节点分割以及最优分裂属性选择等方面的并行性,纵向划分数据,构建了并行的C4.5决策树,并利用MATLAB并行计算池功能以及SPMD设计实现。对并行后决策树运行时间验证结果表明,将C4.5决策树并行化后,并行决策树的构建时间显著缩短,实现了算法的加速。     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

Structured synthesis of MEMS using evolutionary approaches

In this paper, we discuss the hierarchy that is involved in a typical MEMS design and how evolutionary approaches can be used to automate the hierarchical synthesis process for MEMS. The paper first introduces the flow of a structured MEMS design process and emphasizes that system-level lumped-parameter model synthesis is the first step of the MEMS synthesis process. At the system level, an approach combining bond graphs and genetic programming can lead to satisfactory design candidates as system-level models that meet the predefined behavioral specifications for designers to trade off. Then at the physical layout synthesis level, the selection of geometric parameters for component devices and other design variables is formulated as a constrained optimization problem and addressed using a constrained genetic algorithm approach. A multiple-resonator microsystem design is used to illustrate the integrated design automation idea using these evolutionary approaches.     

正交演化算法在继电器体积优化设计中的应用

继电器产品的优化设计是在给定的负载条件或环境条件下,在对继电器产品的性态、几何尺寸关系或其他因素限制约束范围内,确定设计参数、目标函数、约束条件以形成优化设计模型,并选择恰当的优化方法以获得最佳设计方案的一系列工作。继电器的体积数学模型涉及到机、电、磁、热等方面,其目标函数和约束函数均是高度非线性的。传统演化算法求解问题时容易陷入局部极小值。在简单演化算法的基础上,结合正交实验法的基本思想,将其应用于演化算法的种群初始化、交叉算子,并引入自适应正交局部搜索来防止局部收敛,得到了一种新型的正交演化算法。通过一系列数值实验验证了该算法的高效性。     

基于多目标遗传算法的Σ-ΔMEMS加速度计优化设计

针对单目标遗传算法设计优化高阶Σ-Δ微机电系统(Σ-ΔMEMS)加速度计时易出现的稳定性问题,提出了基于多目标遗传算法的MEMS加速度计环路滤波器优化设计方法.对三阶非限定性Σ-ΔMEMS加速度计系统,采用多目标遗传算法,将∞—范数和信噪比作为设计目标对其环路滤波器参数进行优化设计.结果表明:相比只针对信噪比进行优化的传统单目标遗传算法,多目标遗传算法在确保高信噪比的同时,提高了系统的相位裕度,使得最大稳定输入信号范围增幅超过1倍,增强了系统对MEMS敏感元件工艺误差的鲁棒性.     

Modeling microwave behaviors of series cantilever MEMS switch

Simple and effective model is demanded which enables the design and structural optimization of the microwave MEMS switch efficiently. For this purpose the microwave behaviors of series metal cantilever MEMS switch have been modeled by “simple” circuit in this paper. The microwave characteristics have been calculated and compared with the experiment data based on the developed model. The results show that the microwave characteristics of series metal cantilever MEMS switch can be described very well with this model. Based on this model, the influences of the structural parameters of the switch on the microwave characteristics have been discussed extensively.     

常微分方程组并行演化建模的实验研究

以常微分方程组的演化建模问题为主要研究对象,设计了分布式异步并行演化算法,并以128台PIII 500微机通过10Mbps的以太网互联而成的机群系统作为模拟实验环境进行了大规模的并行实验,系统地测试了算法中的一些重要的并行控制参数,包括处理机间的连通度、个体的迁移率和迁移代频等对算法性能的影响,得到了一些崭新的实验结果,给出了一些结果分析,特别是对串行算法和并行算法的最好建模结果进行了比较.     

基于自适应机制的多宇宙并行量子衍生进化算法

进化参量的选取对量子衍生进化算法(QEA)的优化性能有极大的影响,传统QEA在选择进化参量时并未考虑种群中个体间的差异,种群中所有个体采用相同的进化参量完成更新,导致算法在解决组合优化问题中存在收敛速度慢、容易陷入局部最优解等问题。针对这一问题,采用自适应机制调整QEA的旋转角步长和量子变异概率,算法中任意一代的任一个体的进化参量均由该个体自身适应度确定,从而保证尽可能多的进化个体能够朝着最优解方向不断靠近。此外,由于自适应量子进化算法需要评估个体的适应度,导致运算时间较长,针对这一问题则采用多宇宙机制将算法分布于多个宇宙中并行实现,从而提高算法的执行效率。通过搜索多峰函数最优解和求解背包问题测试算法性能,结果表明,与传统QEA相比,所提出算法在收敛速度、搜索全局最优解及执行速度方面具有较好的表现。     

基于改进并行遗传算法的蜂窝网络信道分配

在蜂窝移动通信中,用户需求的不断增长使可用的频谱资源日益紧缺,采用较优的优化算法进行信道分配就显得非常重要。针对这一问题,首次提出了细粒度主从式并行遗传算法,其特点是在进化的过程中动态改变邻域单元,来维持进化过程中的种群多样性,防止算法进入局部最优而过早收敛,增强算法的全局搜索能力。实验仿真表明,该算法对信道分配问题有很强的最优解搜索能力,收敛速度也较快,具有一定的实用价值。     

基于微波无线传能的动态无线传能链路多目标规划问题

针对利用无线传能技术对移动无人单元进行动态传能的需求,选取微波无线传能作为传能方式.考虑在无线传能发射端与接收端之间设置中继传能节点的必要性,以及因无人单元连续移动所导致的无线传能链路的动态性,基于这类动态链路上采用不同中继传能节点部署方案所带来的在传能效率、系统成本等指标上的变化,构建一个包含发射端、接收端和可移动能量中继平台的动态无线传能链路多目标规划模型,在此基础上根据决策变量的特点,采用两种不同的进化算法对动态无线传能链路多目标规划模型进行双层迭代求解.求解结果验证了模型的有效性和微波能量中继传输对提高动态无线传能链路平均传能效率的作用.     

一种带混合进化机制的膜聚类算法

膜计算(也称为P系统或膜系统)是一种新颖的分布式、并行计算模型.为了处理数据聚类问题,提出了一种采用混合进化机制的膜聚类算法.它使用了一个由3个细胞组成的组织P系统,为一个待聚类的数据集发现最优的簇中心.其对象表示候选的簇中心,并且这3个细胞分别使用了3种不同的进化机制:遗传算子、速度-位移模型和差分进化机制.然而,所使用的速度-位移模型和差分进化机制是结合了这个特殊膜结构和转运机制所提出的改进版本.这种混合进化机制能够增强系统中对象的多样性和改善收敛性能.在混合进化机制和转运机制控制下,这种膜聚类算法能够确定一个数据集的良好划分.所提出的膜聚类算法在3个人工数据集和5个真实数据集上被评估,并与k-means和几种进化聚类算法进行比较.统计显著性测试建立了所提出的膜聚类算法的优势.