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.     

一种基于改进蚁群优化的QoS路由算法

蚁群优化（Ant Colony Optimization,AC0）是一种新型的分布式仿生优化算法,可有效地用来解决组合优化问题,而网络路由优化问题则正是组合优化问题当中的一种。因此,本文首先分析了常用路由算法与蚁群优化的基本原理,根据网络路由优化问题与蚁群优化算法的许多匹配特性,提出了一种基于改进蚁群优化的QoS路由算法（Route Algorithm based on Improved Ant Colony Optimlzation,RAIAC0）。最后,通过实验分析,对其可行性进行了证明。     

增强型的蚁群优化算法

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

蚁群算法中参数设置对其性能影响的研究

蚁群算法是一种新型的仿生智能算法,但由于算法中参数众多,各种参数值的设置对蚁群算法的性能影响很大。因此。蚁群算法中各参数的合理设置是十分关键的,这也是蚁群算法研究的一个难点问题。对蚁群算法的基本原理进行详细介绍,对蚁群算法中各参数对其性能的影响以及各参数的合理设置进行分析研究。     

变尺度混沌蚁群优化算法

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

基于蚁群算法的网格资源发现模型研究

本文通过对传统的网格资源发现存在的问题进行分析,针对其不足,引入蚁群算法,提出基于蚁群算法的网格资源发现模型（AA_GRRM）,设计并分析AA_GRRM的体系结构,并对其关键模块分析设计,以提高网格资源发现效率。     

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.     

基于生命周期的二元蚁群优化算法

将自然生态系统中生物生命周期的思想引入二元蚁群优化算法中,通过对蚂蚁设置相应的营养阈值而执行繁殖、迁徙、死亡操作,从而保持种群的动态多样性,进而克服二元蚁群优化算法易陷入局部最优的缺陷,然后结合分形维数将该算法应用于属性约简问题中,通过UCI中的6个数据集进行测试,结果表明该算法具有较好的可行性和有效性.     

蚁群优化算法及其应用

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

Ant-Tree: an ant colony optimization approach to the generalized minimum spanning tree problem

The ant colony optimization is a meta-heuristic inspired by knowledge sharing amongst ants using pheromone, which serves as a kind of collective memory. Since the past few years, there have been several successful applications of this new approach for finding approximate solutions for computationally difficult problems in reasonable times. In this paper, we study the generalized minimum spanning tree problem that involves the design of a minimum weight connected network spanning at least one node out of every disjoint subset of the nodes in a graph. This problem has a wealth of pertinence to a wide range of applications in different areas. As the problem is known as computationally challenging, we adopt the ant colony optimization strategy and present a new solution method, called Ant-Tree, to develop approximate solutions. As an initial attempt, our study aims to provide an investigation of the ant colony optimization approach for coping with tree optimization problems. Through computational experiments, we compare the performances of our approach and the method available in the literature. Numerical results indicate that the proposed method is effective in producing quality approximate solutions.     

基于渐进蚁群算法的DNA多序列比对

DNA多序列比对是生物信息学中的最重要的任务之一。本文针对多序列比对的特点,提出一种渐进蚁群算法,即将渐进比对算法和蚁群算法相结合。在渐进蚁群算法中,既能克服蚁群算法易于陷入局部最优解、收敛速度慢的特点,又能充分发挥渐进比对算法的优点。     

Savings based ant colony optimization for the capacitated minimum spanning tree problem

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.     

Pattern Matching based Classification using Ant Colony Optimization based Feature Selection

Classification is a method of accurately predicting the target class for an unlabelled sample by learning from instances described by a set of attributes and a class label. Instance based classifiers are attractive due to their simplicity and performance. However, many of these are susceptible to noise and become unsuitable for real world problems. This paper proposes a novel instance based classification algorithm called Pattern Matching based Classification (PMC). The underlying principle of PMC is that it classifies unlabelled samples by matching for patterns in the training dataset. The advantage of PMC in comparison with other instance based methods is its simple classification procedure together with high performance. To improve the classification accuracy of PMC, an Ant Colony Optimization based Feature Selection algorithm based on the idea of PMC has been proposed. The classifier is evaluated on 35 datasets. Experimental results demonstrate that PMC is competent with many instance based classifiers. The results are also validated using nonparametric statistical tests. Also, the evaluation time of PMC is less when compared to the gravitation based methods used for classification.     

应用蚁群算法求解TSP

介绍了一种求解复杂TSP的蚁群算法,阐述了该算法的基本原理、模型以及实现过程,并介绍了蚁群算法在旅行商问题(TSP)中的应用思路。     

蚁群算法的优化及在TSP问题上的应用

蚁群算法是一种模仿真实蚂蚁群集体行为的全局启发式随机搜索算法．目前蚁群算法存在易陷入局部最优、搜索时间长等问题。提出一种改进的蚁群算法,加入扰动策略、挥发因子动态调整策略以避免算法陷入局部最优值．采用奖励策略提高搜索效率。通过在旅行商问题上验证得知,改进后的算法可以获得已知最优值,与最大最小蚁群算法相比,解的平均值、出现最优值的概率都有提高。     

基于量子蚁群算法的数据库连接查询优化

连接查询优化是提高数据库性能的关键技术,针对数据库连接查询优化效率低的难题,提出一种量子蚁群算法的数据库连接查询优化方法（QACA）.首先,将数据库连接查询计划左深树看作一个蚂蚁,然后,利用量子旋转门更新各路径信息素,并利用混沌变异策略保持种群多样性,通过蚂蚁之间的信息交流找到数据库连接查询最优计划,最后,进行数据库连接查询优化实例分析.结果表明,QACA是解决数据库连接查询优化的有效途径,获得理想的数据库连接查询计划,具有实际意义.     

能量有效的无线传感器网络蚁群路由协议

本文提出了一种能量有效的无线传感器网络路由协议EEACR。协议针对无线传感器网络的传感器节点能量有限性,低存储性和低处理性能,着重修改了蚁群算法的信息素计算公式,增加了对节点能量的判断,并提出了数据分组机制和信息素全局更新规则。最后,仿真实验验证了EEACR的有效性。     

基于改进蚁群算法的方向过电流保护整定优化

本文提出了基于蚁群优化算法的方向过电流保护整定配合的优化模型.首先说明了方向过电流保护的时间特性,然后建立了方向过电流整定优化模型.优化目标是所有主保护动作时间之和最小,考虑了主后备保护配合约束、保护动作时间约束、启动电流约束等.本文所提方向过电流保护为非线性优化问题,提出利用改进蚁群优化算法来求解该模型.最后本文利用...     

A survey: Ant Colony Optimization based recent research and implementation on several engineering domain

Ant Colony Optimization (ACO) is a Swarm Intelligence technique which inspired from the foraging behaviour of real ant colonies. The ants deposit pheromone on the ground in order to mark the route for identification of their routes from the nest to food that should be followed by other members of the colony. This ACO exploits an optimization mechanism for solving discrete optimization problems in various engineering domain. From the early nineties, when the first Ant Colony Optimization algorithm was proposed, ACO attracted the attention of increasing numbers of researchers and many successful applications are now available. Moreover, a substantial corpus of theoretical results is becoming available that provides useful guidelines to researchers and practitioners in further applications of ACO. This paper review varies recent research and implementation of ACO, and proposed a modified ACO model which is applied for network routing problem and compared with existing traditional routing algorithms.     

– Ant System

Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned algorithms, was rather poor for large instances of traditional benchmark problems like the Traveling Salesman Problem. To show that Ant Colony Optimization algorithms could be good alternatives to existing algorithms for hard combinatorial optimization problems, recent research in this area has mainly focused on the development of algorithmic variants which achieve better performance than Ant System.In this paper, we present – Ant System ( ), an Ant Colony Optimization algorithm derived from Ant System. differs from Ant System in several important aspects, whose usefulness we demonstrate by means of an experimental study. Additionally, we relate one of the characteristics specific to — that of using a greedier search than Ant System — to results from the search space analysis of the combinatorial optimization problems attacked in this paper. Our computational results on the Traveling Salesman Problem and the Quadratic Assignment Problem show that is currently among the best performing algorithms for these problems.