Data Parallel Algorithmic Skeletons with Accelerator Support

Hardware accelerators such as GPUs or Intel Xeon Phi comprise hundreds or thousands of cores on a single chip and promise to deliver high performance. They are widely used to boost the performance of highly parallel applications. However, because of their diverging architectures programmers are facing diverging programming paradigms. Programmers also have to deal with low-level concepts of parallel programming that make it a cumbersome task. In order to assist programmers in developing parallel applications Algorithmic Skeletons have been proposed. They encapsulate well-defined, frequently recurring parallel programming patterns, thereby shielding programmers from low-level aspects of parallel programming. The main contribution of this paper is a comparison of two skeleton library implementations, one in C++ and one in Java, in terms of library design and programmability. Besides, on the basis of four benchmark applications we evaluate the performance of the presented implementations on two test systems, a GPU cluster and a Xeon Phi system. The two implementations achieve comparable performance with a slight advantage for the C++ implementation. Xeon Phi performance ranges between CPU and GPU performance.     

自适应并行蚁群算法

蚁群算法是一种模拟进化算法,具有很强的全局搜索能力.本文提出一种自适应的并行蚁群算法(A-PACO),该算法可以根据不同的搜索阶段,自适应确定参数的最优组合,在一定程度上避免停滞现象的出现并加速算法收敛.而且自适应的迁移策略可以较大丰富系统多样性的同时也较大降低子蚁群间的通信量,有效提高算法的搜索质量和缩短算法的运行时间.最后选用中国CHN144问题对该算法进行检验,结果显示该算法具有较好的稳定性和较快的收敛速度.     

Parallel Ant Colony Optimization on Graphics Processing Units

The purpose of this paper is to propose effective parallelization strategies for the Ant Colony Optimization (ACO) metaheuristic on Graphics Processing Units (GPUs). The Max–Min Ant System (MMAS) algorithm augmented with 3-opt local search is used as a framework for the implementation of the parallel ants and multiple ant colonies general parallelization approaches. The four resulting GPU algorithms are extensively evaluated and compared on both speedup and solution quality on a state-of-the-art Fermi GPU architecture. A rigorous effort is made to keep parallel algorithms true to the original MMAS applied to the Traveling Salesman Problem. We report speedups of up to 23.60 with solution quality similar to the original sequential implementation. With the intent of providing a parallelization framework for ACO on GPUs, a comparative experimental study highlights the performance impact of ACO parameters, GPU technical configuration, memory structures and parallelization granularity.     

基于粗粒度模型的蚁群优化并行算法

为了改进蚁群优化算法的收敛速度,研究了一种基于粗粒度模型的并行蚁群优化算法,该算法将搜索任务划分给q个子群,由这些子群并行地完成搜索,可使搜索速度大幅度提高。实验结果表明,用该算法求解TSP问题,收敛速度比最新的改进算法快百倍以上。     

基于All-In-Roulette选择算法的GPU并行加速蚁群优化算法

蚁群优化算法应用于复杂问题的求解是非常耗时的。文章在MATLAB环境下实现了一个基于GPU＋CPU的并行MAX-MIN蚁群系统,并将其应用于旅行商问题的求解。让全部蚂蚁共享一个伪随机数矩阵,一个信息素矩阵,一个禁忌矩阵和一个概率矩阵,并运用了一个全新的基于这些矩阵的随机选择算法—AIR（All-In-Roulette）。文章还介绍了如何使用这些矩阵来构造并行蚁群优化算法,并与相应串行算法进行了比较。计算结果表明新的并行算法比相应串行算法要高效很多。     

并行二进制蚁群算法的多峰函数优化

针对已有蚁群算法在函数优化问题上存在的几个不足:如算法实现较难,占用过多的存储空间,需要记忆功能,不容易与其他算法结合等等,提出了二进制蚁群算法。实验证明该算法在处理单极值问题时有较好的表现,但是在处理多峰函数时存在着一定的缺陷,对此,论文对该算法进行了改进,将并行化引入算法。通过对几个函数的测试(包括多峰和单峰),结果表明该改进算法具有较好的稳定性和收敛速度,算法性能良好。     

自适应的并行蚁群算法

本文根据影响并行蚁群算法性能的关键因素，提出了一种自适应的并行蚁群算法．首先提出了基于适应度和基于距离选择的两种不同的信息交流策略，使得各处理机自适应地选择与之进行信息交换的处理机，然后采用自适应的更新策略进行信息素的更新．为了增强该算法的搜索能力，还根据解的多样性给出了自适应地调节处理机之间的信息交流周期的方法．在MPP处理机深腾1800上对TSP问题的实验结果表明了该算法在保证有效的加速比的同时，具有很好的收敛性．     

蚁群算法的并行性研究

并行计算作为现代计算机的一种重要的计算方法,在很大程度上优化了蚁群算法的计算过程.蚁群算法本身隐含着一定的并行性,从本质上来说,蚁群算法是以并行式的协同优化计算方式为特征,利用并行计算求出最优解.本文重点讨论蚁群算法的并行实现,并通过一个仿真实验验证并行优化蚁群算法在解决一个具有时变动态、连续、多输入、非线性系统的最优控制问题上的最优解决方法,得出蚁群算法在加速比上更具有优势.     

全局自适应蚁群优化算法

为解决蚁群算法存在的收敛速度慢和容易陷入局部最优等缺点,分析了其产生的主要原因,介绍了AS和MMAS算法的工作原理,并基于参数自适应思想,提出了全局自适应蚁群优化算法(GAO).对状态转移和信息素更新等规则做出改进,详尽给出了GAO的编程步骤.针对TSP问题,通过与AS和MMAS算法的数值实验结果比较分析,表明GAO算法具有优良的全局优化能力和适当的收敛时间.     

蚁群算法综述

群集智能作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点,其理论和应用得到了很大的发展。作为群集智能的代表方法之一,蚁群算法ACO(Ant Colony Optimization,简称ACO)以其实现简单、正反馈、分布式的优点得到广泛的应用。本文对蚁群算法的最新进展进行了综述和展望。     

Classification With Ant Colony Optimization

Ant colony optimization (ACO) can be applied to the data mining field to extract rule-based classifiers. The aim of this paper is twofold. On the one hand, we provide an overview of previous ant-based approaches to the classification task and compare them with state-of-the-art classification techniques, such as C4.5, RIPPER, and support vector machines in a benchmark study. On the other hand, a new ant-based classification technique is proposed, named AntMiner+. The key differences between the proposed AntMiner+ and previous AntMiner versions are the usage of the better performing MAX-MIN ant system, a clearly defined and augmented environment for the ants to walk through, with the inclusion of the class variable to handle multiclass problems, and the ability to include interval rules in the rule list. Furthermore, the commonly encountered problem in ACO of setting system parameters is dealt with in an automated, dynamic manner. Our benchmarking experiments show an AntMiner+ accuracy that is superior to that obtained by the other AntMiner versions, and competitive or better than the results achieved by the compared classification techniques.     

增强型的蚁群优化算法

旅行商问题是一个NP-Hard组合优化问题。根据蚁群优化算法和旅行商问题的特点,论文提出了对蚁群中具有优质解的蚂蚁个体所走路径上的信息素强度进行增强的方法,并同其他的优化算法进行了比较,仿真结果表明,对具有全局和局部最优解的个体所走路径上的信息素强度进行增强的蚁群优化算法比标准的蚁群优化算法和其他优化算法在执行效率和稳定性上要高。     

蚁群混沌混合优化算法

为了克服混沌搜索的盲目性,提出了一种蚁群算法和混沌优化算法相结合的混合优化算法,该算法利用蚁群算法中信息素正反馈的思想指导当前混沌搜索的区域。工作蚁群按照信息素的浓度高低,分别按照不同的概率搜索不同的搜索区域,从而可减少混沌盲目搜索的次数。仿真结果表明,该方法能够明显提高混沌优化算法的寻优效率,同时算法的通用性将有所提高。另外,对于含有多个全局最优解的函数,在一次寻优过程中,该算法可以找到全部最优解,这是通常混沌搜索算法所不具备的。     

变尺度混沌蚁群优化算法

将变尺度混沌搜索算法融合到蚁群算法中,并用于求解连续空间优化问题。蚁群算法每一次迭代结束时,就使用混沌搜索算子在当前全局最优解附近搜索更好的解。而随着蚁群算法的进行,混沌算子搜索范围逐渐缩小,这样,混沌算子在蚁群搜索的初期起到防止陷入局部最优的作用,在蚁群搜索后期起到提高搜索精度的作用。将变尺度混沌蚁群优化算法用于求解函数优化问题的实验结果表明,该算法在求解包括欺骗性函数和高维函数在内的多种测试函数优化问题方面具有很好的效果。     

一种并行蚁群Bayesian网络学习的算法

Bayesian网络学习的一种方法是根据输入数据集使用某种打分机制找到与数据集相拟合的候选网络.ACOB算法(蚁群优化B算法)是其中一种基于元启发引入蚂蚁机制来进行Bayesian网络学习的方法.本文在该算法基础之上提出一种改进算法--PACOB,并行进行Bayesian网络学习.实验结果表明,该并行算法相对于其串行算法具有一定的优势,提供了一种Bayesian网络学习问题的有效手段.     

蚁群算法优化策略综述

对于求解TSP问题,新型的启发式算法——蚁群算法,是成功解决此类问题核心的算法之一。本文简要介绍了几种启发式算法并引出蚁群算法,并对蚁群算法基本原理、常用算法进行了深入的研究,并介绍了一种新的优化策略。     

改进的重叠蚁群优化算法

针对蚁群优化算法在进行全局最优解搜索时容易陷入局部最优解和收敛速度缓慢等缺陷,提出了一种有效求解全局最优解搜索问题的重叠蚁群优化算法。该算法通过设置多个重叠的蚁群系统,并对每一个蚁群初始化不同的参数,之后在蚁群之间进行信息素的动态学习,增强了不同蚁群对最优解的开采能力,避免了算法出现早熟现象。仿真实验结果表明,重叠蚁群优化算法在避免陷入局部最优解方面具有良好的效果,是一种提高蚁群算法性能的有效的改进算法。