Two-stage updating pheromone for invariant ant colony optimization algorithm

Ant colony optimization (ACO) is a metaheuristic approach for combinatorial optimization problems. With the introduction of hypercube framework, invariance property of ACO algorithms draws more attention. In this paper, we propose a novel two-stage updating pheromone for invariant ant colony optimization (TSIACO) algorithm. Compared with standard ACO algorithms, TSIACO algorithm uses solution order other than solution itself as independent variable for quality function. In addition, the pheromone trail is updated with two stages: in one stage, the first r iterative optimal solutions are employed to enhance search capability, and in another stage, only optimal solution is used to accelerate the speed of convergence. And besides, the pheromone value is limited to an interval. We prove that TSIACO not only has the property of linear transformational invariance but also has translational invariance. We also prove that the pheromone trail can limit to the interval (0, 1]. Computational results on the traveling salesman problem show the effectiveness of TSIACO algorithm.     

On the Invariance of Ant Colony Optimization

Ant colony optimization (ACO) is a promising metaheuristic and a great amount of research has been devoted to its empirical and theoretical analysis. Recently, with the introduction of the hypercube framework, Blum and Dorigo have explicitly raised the issue of the invariance of ACO algorithms to transformation of units. They state (Blum and Dorigo, 2004) that the performance of ACO depends on the scale of the problem instance under analysis. In this paper, we show that the ACO internal state - commonly referred to as the pheromone - indeed depends on the scale of the problem at hand. Nonetheless, we formally prove that this does not affect the sequence of solutions produced by the three most widely adopted algorithms belonging to the ACO family: ant system, MAX-MIN ant system, and ant colony system. For these algorithms, the sequence of solutions does not depend on the scale of the problem instance under analysis. Moreover, we introduce three new ACO algorithms, the internal state of which is independent of the scale of the problem instance considered. These algorithms are obtained as minor variations of ant system, MAX-MIN ant system, and ant colony system. We formally show that these algorithms are functionally equivalent to their original counterparts. That is, for any given instance, these algorithms produce the same sequence of solutions as the original ones.     

Population declining ant colony optimization algorithm and its applications

Population declining ant colony optimization (PDACO) algorithm is proposed and applied to the traveling salesman problem (TSP) and multiuser detection in this paper. Ant colony optimization (ACO) algorithms have already successfully been used in combinatorial optimization, however, as the pheromone accumulates, we may not get a global optimum because it stops searching early. PDACO can enlarge searching range through increasing the initial population of the ant colony, and the population declines in successive iterations. So, the performance of PDACO is superior with the same computational complexity. PDACO is applied to TSP and multiuser detection. Via computer simulations it is shown that PDACO has better performance in solving these two problems than ACO algorithms.     

The hyper-cube framework for ant colony optimization.

Ant colony optimization is a metaheuristic approach belonging to the class of model-based search algorithms. In this paper, we propose a new framework for implementing ant colony optimization algorithms called the hyper-cube framework for ant colony optimization. In contrast to the usual way of implementing ant colony optimization algorithms, this framework limits the pheromone values to the interval [0,1]. This is obtained by introducing changes in the pheromone value update rule. These changes can in general be applied to any pheromone value update rule used in ant colony optimization. We discuss the benefits coming with this new framework. The benefits are twofold. On the theoretical side, the new framework allows us to prove that in Ant System, the ancestor of all ant colony optimization algorithms, the average quality of the solutions produced increases in expectation over time when applied to unconstrained problems. On the practical side, the new framework automatically handles the scaling of the objective function values. We experimentally show that this leads on average to a more robust behavior of ant colony optimization algorithms.     

Multi-satellite control resource scheduling based on ant colony optimization

The multi-satellite control resource scheduling problem (MSCRSP) is a kind of large-scale combinatorial optimization problem. As the solution space of the problem is sparse, the optimization process is very complicated. Ant colony optimization as one of heuristic method is wildly used by other researchers to solve many practical problems. An algorithm of multi-satellite control resource scheduling problem based on ant colony optimization (MSCRSP–ACO) is presented in this paper. The main idea of MSCRSP–ACO is that pheromone trail update by two stages to avoid algorithm trapping into local optima. The main procedures of this algorithm contain three processes. Firstly, the data get by satellite control center should be preprocessed according to visible arcs. Secondly, aiming to minimize the working burden as optimization objective, the optimization model of MSCRSP, called complex independent set model (CISM), is developed based on visible arcs and working periods. Ant colony algorithm can be used directly to solve CISM. Lastly, a novel ant colony algorithm, called MSCRSP–ACO, is applied to CISM. From the definition of pheromone and heuristic information to the updating strategy of pheromone is described detailed. The effect of parameters on the algorithm performance is also studied by experimental method. The experiment results demonstrate that the global exploration ability and solution quality of the MSCRSP–ACO is superior to existed algorithms such as genetic algorithm, iterative repair algorithm and max–min ant system.     

Modeling the dynamics of ant colony optimization

The dynamics of Ant Colony Optimization (ACO) algorithms is studied using a deterministic model that assumes an average expected behavior of the algorithms. The ACO optimization metaheuristic is an iterative approach, where in every iteration, artificial ants construct solutions randomly but guided by pheromone information stemming from former ants that found good solutions. The behavior of ACO algorithms and the ACO model are analyzed for certain types of permutation problems. It is shown analytically that the decisions of an ant are influenced in an intriguing way by the use of the pheromone information and the properties of the pheromone matrix. This explains why ACO algorithms can show a complex dynamic behavior even when there is only one ant per iteration and no competition occurs. The ACO model is used to describe the algorithm behavior as a combination of situations with different degrees of competition between the ants. This helps to better understand the dynamics of the algorithm when there are several ants per iteration as is always the case when using ACO algorithms for optimization. Simulations are done to compare the behavior of the ACO model with the ACO algorithm. Results show that the deterministic model describes essential features of the dynamics of ACO algorithms quite accurately, while other aspects of the algorithms behavior cannot be found in the model.     

多维背包问题的一个蚁群优化算法

蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.实验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在实验中,文中的新算法获得了ORLIB中测试算例5.250-22的两个"新"解.     

Ant colony optimization

Swarm intelligence is a relatively new approach to problem solving that takes inspiration from the social behaviors of insects and of other animals. In particular, ants have inspired a number of methods and techniques among which the most studied and the most successful is the general purpose optimization technique known as ant colony optimization. Ant colony optimization (ACO) takes inspiration from the foraging behavior of some ant species. These ants deposit pheromone on the ground in order to mark some favorable path that should be followed by other members of the colony. Ant colony optimization exploits a similar mechanism for solving optimization problems. 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. The goal of this article is to introduce ant colony optimization and to survey its most notable applications     

一种快速求解旅行商问题的蚁群算法

蚁群优化是一种元启发式的随机搜索技术,是目前解决组合优化问题最有效的工具之一.将信息素更新和随机搜索机制的改进相结合,提出一种快速求解旅行商问题的蚁群算法.首先给出了一种新的信息素增量模型,以体现蚂蚁在不同路径上行走时所产生的信息素差异;然后以蚂蚁经过的路径(直线段)作为信息素扩散浓度场的信源,改进了信息素扩散模型,强化了蚂蚁间的协作和交流;最后采用较低复杂度的变异策略对迭代的结果进行优化.在大量通用数据集上的实验表明,该算法不仅能获得更好的最优解,而且收敛速度有显著的提高.     

A hybrid ant colony optimization algorithm for optimal multiuser detection in DS-UWB system

A hybrid ant colony optimization algorithm is proposed by introducing extremal optimization local-search algorithm to the ant colony optimization (ACO) algorithm, and is applied to multiuser detection in direct sequence ultra wideband (DS-UWB) communication system in this paper. ACO algorithms have already successfully been applied to combinatorial optimization; however, as the pheromone accumulates, we may not get a global optimum because it can get stuck in a local minimum resulting in a bad steady state. Extremal optimization (EO) is a recently developed local-search heuristic method and has been successfully applied to a wide variety of optimization problems. Hence in this paper, a hybrid ACO algorithm, named ACO-EO algorithm, is proposed by introducing EO to ACO to improve the local-search ability of the algorithm. The ACO-EO algorithm is applied to multiuser detection in DS-UWB communication system, and via computer simulations it is shown that the proposed hybrid ACO algorithm has much better performance than other ACO algorithms and even equal to the optimal multiuser detector.     

High speed ant colony optimization CMOS chip

Ant colony optimization (ACO) is an optimization computation inspired by the study of the ant colonies’ behavior. This paper presents design and CMOS implementation of the ant colony optimization based algorithm for solving the TSP problem. In order to implement ant colony optimization algorithm in CMOS, we will present a new algorithm. This algorithm is based on the original ant colony optimization but it can be implemented in CMOS. Briefly, pheromone matrix is transformed on the chip area and ants move up-down through the pheromone matrix and they make their decisions. Finally ants select a global path. In previous researches only pheromone values is used, but select the next city in this paper is based on heuristics value and pheromone value. In definition of problem, we use heuristics value as a matrix. Previous researches could not be used for wide type of optimization problem but our chip gives heuristics value initially and we can change initial value of heuristics value according to the optimization problem so this capability increases the flexibility of ACO chip. Simple circuit is used in blocks of our chip to increase the speed of convergence of ACO chip. We use Linear Feedback Shift Register (LSFR) circuit for random number generator in ACO chip. ACO chip has capability of solving the big TSP problem. ACO chip is simulated by HSPICE software and simulation results show the good performance of final chip.     

基于变异和信息素扩散的多维背包问题的蚁群算法

针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足,提出一种新的高性能的蚁群求解算法.算法将信息素更新和随机搜索机制的改进相融合.首先,基于对较优解的偏爱,采用Top-k策略从每次迭代的k个解中挖掘出对象间的关联距离;其次,以对象为信源借助关联距离建立信息素的扩散模型,通过信息素扩散的耦合补偿,强化了蚂蚁间的协作和交流;最后,利用一种简单的变异策略对迭代的结果进行优化.在通用数据集上的大量实验表明:与最新的蚁群算法相比,新算法不仅能获得更好的最优解,而且收敛速度有显著的提高.     

Binary-coding-based ant colony optimization and its convergence

Ant colony optimization (ACO for short) is a meta-heuristics for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. In this paper, genetic algorithm's (GA for short) ideas are introduced into ACO to present a new binary-coding based ant colony optimization. Compared with the typical ACO, the algorithm is intended to replace the problem's parameter-space with coding-space, which links ACO with GA so that the fruits of GA can be applied to ACO directly. Furthermore, it can not only solve general combinatorial optimization problems, but also other problems such as function optimization. Based on the algorithm, it is proved that if the pheromone remainder factor ρ is under the condition of ρ≥1, the algorithm can promise to converge at the optimal, whereas if 0<ρ<1, it does not. This work is supported by the Science Foundation of Shanghai Municipal Commission of Science and Technology under Grant No.00JC14052. Tian-Ming Bu received the M.S. degree in computer software and theory from Shanghai University, China, in 2003. And now he is a Ph.D. candidate of Fudan University in the same area of theory computer science. His research interests include algorithms, especially, heuristic algorithms and heuristic algorithms and parallel algorithms, quantum computing and computational complexity. Song-Nian Yu received the B.S. degree in mathematics from Xi'an University of Science and Technology, Xi'an, China, in 1981, the Ph.D. degree under Prof. L. Lovasz's guidance and from Lorand University, Budapest, Hungary, in 1990. Dr. Yu is a professor in the School of Computer Engineering and Science at Shanghai University. He was a visiting professor as a faculty member in Department of Computer Science at Nelson College of Engineering, West Virginia University, from 1998 to 1999. His current research interests include parallel algorithms' design and analyses, graph theory, combinatorial optimization, wavelet analyses, and grid computing. Hui-Wei Guan received the B.S. degree in electronic engineering from Shanghai University, China, in 1982, the M.S. degree in computer engineering from China Textile University, China, in 1989, and the Ph.D. degree in computer science and engineering from Shanghai Jiaotong University, China, in 1993. He is an associate professor in the Department of Computer Science at North Shore Community College, USA. He is a member of IEEE. His current research interests are parallel and distributed computing, high performance computing, distributed database, massively parallel processing system, and intelligent control.     

一种求解TSP问题的相遇蚁群算法

蚁群算法是由意大利学者M．Dorigo等人首先提出的一种新型的仿生算法。蚁群算法与其他算法同样存在搜索速度慢，易于陷于局部最优。该文提出一种改进的相遇算法克服了以上的缺陷。通过对TSP问题的仿真结果表明，提出的相遇算法与基本蚁群算法相比搜索速度和性能都有一定的提高。     

Fast Ant Colony Optimization on Runtime Reconfigurable Processor Arrays

Ant Colony Optimization (ACO) is a metaheuristic used to solve combinatorial optimization problems. As with other metaheuristics, like evolutionary methods, ACO algorithms often show good optimization behavior but are slow when compared to classical heuristics. Hence, there is a need to find fast implementations for ACO algorithms. In order to allow a fast parallel implementation, we propose several changes to a standard form of ACO algorithms. The main new features are the non-generational approach and the use of a threshold based decision function for the ants. We show that the new algorithm has a good optimization behavior and also allows a fast implementation on reconfigurable processor arrays. This is the first implementation of the ACO approach on a reconfigurable architecture. The running time of the algorithm is quasi-linear in the problem size n and the number of ants on a reconfigurable mesh with n ² processors, each provided with only a constant number of memory words.     

增强型的蚁群优化算法

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

Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling

Ant colony optimization (ACO) is a metaheuristic approach to tackle hard combinatorial optimization problems. The basic component of ACO is a probabilistic solution construction mechanism. Due to its constructive nature, ACO can be regarded as a tree search method. Based on this observation, we hybridize the solution construction mechanism of ACO with beam search, which is a well-known tree search method. We call this approach Beam-ACO. The usefulness of Beam-ACO is demonstrated by its application to open shop scheduling (OSS). We experimentally show that Beam-ACO is a state-of-the-art method for OSS by comparing the obtained results to the best available methods on a wide range of benchmark instances.     

Search bias in ant colony optimization: on the role of competition-balanced systems

One of the problems encountered when applying ant colony optimization (ACO) to combinatorial optimization problems is that the search process is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Sometimes this bias is harmful and results in a decrease in algorithm performance over time, which is called second-order deception. In this work, we study the reasons for the occurrence of second-order deception. In this context, we introduce the concept of competition-balanced system (CBS), which is a property of the combination of an ACO algorithm with a problem instance. We show by means of an example that combinations of ACO algorithms with problem instances that are not CBSs may suffer from a bias that leads to second-order deception. Finally, we show that the choice of an appropriate pheromone model is crucial for the success of the ACO algorithm, and it can help avoid second-order deception.     

Ant colony optimization for routing and load-balancing: survey and new directions

Although an ant is a simple creature, collectively a colony of ants performs useful tasks such as finding the shortest path to a food source and sharing this information with other ants by depositing pheromone. In the field of ant colony optimization (ACO), models of collective intelligence of ants are transformed into useful optimization techniques that find applications in computer networking. In this survey, the problem-solving paradigm of ACO is explicated and compared to traditional routing algorithms along the issues of routing information, routing overhead and adaptivity. The contributions of this survey include 1) providing a comparison and critique of the state-of-the-art approaches for mitigating stagnation (a major problem in many ACO algorithms), 2) surveying and comparing three major research in applying ACO in routing and load-balancing, and 3) discussing new directions and identifying open problems. The approaches for mitigating stagnation discussed include: evaporation, aging, pheromone smoothing and limiting, privileged pheromone laying and pheromone-heuristic control. The survey on ACO in routing/load-balancing includes comparison and critique of ant-based control and its ramifications, AntNet and its extensions, as well as ASGA and SynthECA. Discussions on new directions include an ongoing work of the authors in applying multiple ant colony optimization in load-balancing.     

一个蚁群优化模型的期望性能分析

用蚁群优化求解组合优化问题时, 信息素模型及其规则可能使问题的各组件之间的竞争失衡, 从而有可能使蚁群搜索停滞在最差解。 研究了蚁群优化求解k-最小生成树问题时的信息素模型及其更新规则对性能的影响,对原有的信息素模型作出了新的解释:直接表示k-最小生成树问题的边被选择的概率。基于新的信息素模型设计了一种新的解的构造过程,这种过程不仅产生可行解, 也产生不可行解;同时研究了使用可行解和全部解更新信息素模型时算法的迭代期望质量随时间的增减情况,其结果表明, 只使用可行解时迭代期望质量随时间连续降低, 而使用全