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

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

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

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

Parallel multi-objective Ant Programming for classification using GPUs

Classification using Ant Programming is a challenging data mining task which demands a great deal of computational resources when handling data sets of high dimensionality. This paper presents a new parallelization approach of an existing multi-objective Ant Programming model for classification, using GPUs and the NVIDIA CUDA programming model. The computational costs of the different steps of the algorithm are evaluated and it is discussed how best to parallelize them. The features of both the CPU parallel and GPU versions of the algorithm are presented. An experimental study is carried out to evaluate the performance and efficiency of the interpreter of the rules, and reports the execution times and speedups regarding variable population size, complexity of the rules mined and dimensionality of the data sets. Experiments measure the original single-threaded and the new multi-threaded CPU and GPU times with different number of GPU devices. The results are reported in terms of the number of Giga GP operations per second of the interpreter (up to 10 billion GPops/s) and the speedup achieved (up to 834× vs CPU, 212× vs 4-threaded CPU). The proposed GPU model is demonstrated to scale efficiently to larger datasets and to multiple GPU devices, which allows the expansion of its applicability to significantly more complicated data sets, previously unmanageable by the original algorithm in reasonable time.     

自适应的并行蚁群算法

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

Computing resultants on Graphics Processing Units: Towards GPU-accelerated computer algebra

In this article we report on our experience in computing resultants of bivariate polynomials on Graphics Processing Units (GPU). Following the outline of Collins’ modular approach [6], our algorithm starts by mapping the input polynomials to a finite field for sufficiently many primes m$m$. Next, the GPU algorithm evaluates the polynomials at a number of fixed points x∈_Zm$x\in {\mathbb{Z}}_m$, and computes a set of univariate resultants for each modular image. Afterwards, the resultant is reconstructed using polynomial interpolation and Chinese remaindering. The GPU returns resultant coefficients in the form of Mixed Radix (MR) digits. Finally, large integer coefficients are recovered from the MR representation on the CPU. All computations performed by the algorithm (except for, partly, Chinese remaindering) are outsourced to the graphics processor thereby minimizing the amount of work to be done on the host machine. The main theoretical contribution of this work is the modification of Collins’ modular algorithm using the methods of matrix algebra to make an efficient realization on the GPU feasible. According to the benchmarks, our algorithm outperforms a CPU-based resultant algorithm from 64-bit Maple 14 by a factor of 100.     

以蚁群优化为基础的组播路由算法优化

分析组播路由算法和蚁群优化算法,并通过仿真实验评价了以蚁群优化为基础的组播路由算法的优化方法。当路由计算的规模较大时,信息中未搜索到的数量能够减少并趋近0,将路由算法的全局搜索能力降低。蚁群算法中,蚂蚁的数量与算法的全局搜索能力呈正相关,但蚂蚁的数量在增加的过程中会影响其收敛速度。通过蚁群优化组播路由算法,能够在规模的限定下,提高算法的搜索能力。     

基于改进蚁群优化算法的分布式多播路由算法

蚁群优化算法在优化计算特别是在多播路由问题中得到了广泛应用,但在进行大规模优化时,蚁群算法与其它随机优化算法一样,存在着收敛速度慢易于限于局部最小点等缺点。为此,该文提出了一种新的改进蚁群算法。仿真实验表明,应用这种改进型蚁群算法于多播路由问题,可以得到比现有启发式算法更好的结果。     

蚁群优化算法及其应用

蚂蚁算法是由意大利学者M．Dorigo等人提出的一种新型的模拟进化算法。该算法首先应用于旅行商问题并获得了极大的成功,其后,又被用于求解指派问题、Job—shop调度问题、图着色问题和网络路由问题等。实践证明,蚂蚁算法是一种鲁棒性强、收敛性好、实用性广的优化算法,但同时也存在一些不足,如收敛速度慢和容易出现停滞现象等。     

Runtime Analysis of a Simple Ant Colony Optimization Algorithm

Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in finite time. We present the first runtime analysis of an ACO algorithm, which transfers many rigorous results with respect to the runtime of a simple evolutionary algorithm to our algorithm. Moreover, we examine the choice of the evaporation factor, a crucial parameter in ACO algorithms, in detail. By deriving new lower bounds on the tails of sums of independent Poisson trials, we determine the effect of the evaporation factor almost completely and prove a phase transition from exponential to polynomial runtime. A preliminary version of this paper appeared in the Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), volume 4288 of LNCS, pp. 618–627, Springer. Financial support for C. Witt by the Deutsche Forschungsgemeinschaft (SFB) in terms of the Collaborative Research Center “Computational Intelligence” (SFB 531) is gratefully acknowledged.     

基于并行多种群自适应蚁群算法的聚类分析

数据聚类是数据挖掘中的一个重要课题。聚类问题可以归结为一个优化问题。蚁群算法作为一种鲁棒性很强的优化算法具有很强的全局优化能力。该文给出了一种并行多种群自适应蚁群算法。该算法采用多种群并行搜索,并在种群中采用基于目标函数值的启发式信息素分配策略和根据目标函数自动调整蚂蚁搜索路径的行为。理论分析和仿真实验表明,该算法是非常有效的。     

基于改进蚁群算法的计算机网络路由优化研究

计算机网络规模的逐渐扩大使数据传输时的延时、丢包等现象日益明显.为了提高网络数据传输的稳定性,降低网络消耗,研究使用蚁群算法解决计算机网络的路由优化问题.同时,为了提高蚁群算法的性能,提出了状态转移规则和信息素更新规则的改进策略,使蚁群算法的收敛速度得到明显提升.仿真结果表明,上述改进蚁群算法可以在较短时间内计算出路由优化的结果,优化成功率较高,非常适合实际应用.     

蚁群算法物流配送中心选址优化仿真研究

研究物流配送选址优化调度问题。为了有效节约车辆运输成本,应选择最优路径。城市车辆调度路径选择,存在路网复杂性,参数设置较多,传统的调度算法存在计算复杂度高,不利于实际应用。为解决优化选址问题,提出了一种改进的蚁群优化物流配送选址方法。算法把求得的解首先分解为解对,然后通过改进的蚁群优化算法将解对从不确定性转变成确定性问题,可以大大的降低求解过程。通过仿真表明,提出的优化算法不但降低了计算的复杂度,优化了选址模型,而且为解决物流选址问题提供了新的有效途径。     

自适应蚁群算法在序列比对中的应用

序列比对是生物信息学的重要研究工具。蚁群算法是一种新型的模拟进化算法,并被成功地应用于旅行商问题(TSP)等组合优化问题中。该文将蚁群算法应用于序列比对,并提出基于自适应调整信息素的改进算法。仿真结果表明这种新的比对算法是有效的,而它的改进算法的效果更为理想。     

基于自适应蚁群算法的多受限网络QoS路由优化

高速多媒体网络中的路由问题是有QoS约束的路由问题,多受限的路由问题是一个NP-完全问题。该文提出了一种解决多受限QoS路由问题的自适应蚁群算法。该算法采用基于目标函数值的信息素分配策略和根据目标函数值自适应调整蚂蚁的搜索行为,从而保证搜索的快速有效性,使多受限QoS路由优化问题得到很好地解决。     

一种连续域函数优化蚁群算法的改进设计

本文在一种连续域函数优化蚁群算法基础上,对该算法做了进一步的改进,引入了自动判断收敛条件方法,同时,也改进了蚁群初始化方法、全局搜索策略以防止早熟和停滞现象。通过与其他连续域函数优化算法的比较结果证明,改进后的算法稳定性较好。     

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

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

Enhancing data parallelism for Ant Colony Optimization on GPUs

Graphics Processing Units (GPUs) have evolved into highly parallel and fully programmable architecture over the past five years, and the advent of CUDA has facilitated their application to many real-world applications. In this paper, we deal with a GPU implementation of Ant Colony Optimization (ACO), a population-based optimization method which comprises two major stages: tour construction and pheromone update. Because of its inherently parallel nature, ACO is well-suited to GPU implementation, but it also poses significant challenges due to irregular memory access patterns. Our contribution within this context is threefold: (1) a data parallelism scheme for tour construction tailored to GPUs, (2) novel GPU programming strategies for the pheromone update stage, and (3) a new mechanism called I-Roulette to replicate the classic roulette wheel while improving GPU parallelism. Our implementation leads to factor gains exceeding 20x for any of the two stages of the ACO algorithm as applied to the TSP when compared to its sequential counterpart version running on a similar single-threaded high-end CPU. Moreover, an extensive discussion focused on different implementation paths on GPUs shows the way to deal with parallel graph connected components. This, in turn, suggests a broader area of inquiry, where algorithm designers may learn to adapt similar optimization methods to GPU architecture.     

基于蚁群算法的泊位调度优化与仿真

在全球贸易经济聚焦在中国的同时,港口的吞吐能力成为目前港口业的主要矛盾。提高泊位这个环节的运作能力,减少船舶在港时间,增加港口的吞吐能力成为主要研究对象。本文采取仿真模型与优化算法相结合的研究方法,把泊位调度问题转化为旅行商问题,建立了一个泊位岸桥协调调度,通过蚁群算法建立数学模型,使船舶在港时间最短为目标建立函数,求得最佳调度方案。用ProModel建立船舶到港停泊及离港仿真模型。验证泊位调度优化的有效性,以便指导港口实际的泊位调度。     

变尺度混沌蚁群优化算法

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

蚁群优化算法求解TSP问题研究

介绍了信息素混合更新的蚁群优化算法,并用来求解TSP问题。混合信息素更新的蚁群优化算法是在蚁群系统（ACS）的基础上改进而成的,它在演化过程中,通过改变信息素的迭代最优更新规则和全局最优更新规则的使用频率,逐渐增加全局最优更新规则的使用频率,从而提高系统收敛的速度和减少系统搜索的导向性,并以Oliver30和att48为例给出了实验结果,说明了该混合算法的有效性。