Solving the traveling salesman problem using cooperative genetic ant systems

The travelling salesman problem (TSP) is a classic problem of combinatorial optimization and has applications in planning, scheduling, and searching in many scientific and engineering fields. Ant colony optimization (ACO) has been successfully used to solve TSPs and many associated applications in the last two decades. However, ACO has problem in regularly reaching the global optimal solutions for TSPs due to enormity of the search space and numerous local optima within the space. In this paper, we propose a new hybrid algorithm, cooperative genetic ant system (CGAS) to deal with this problem. Unlike other previous studies that regarded GA as a sequential part of the whole searching process and only used the result from GA as the input to subsequent ACO iterations, this new approach combines both GA and ACO together in a cooperative manner to improve the performance of ACO for solving TSPs. The mutual information exchange between ACO and GA in the end of the current iteration ensures the selection of the best solutions for next iteration. This cooperative approach creates a better chance in reaching the global optimal solution because independent running of GA maintains a high level of diversity in next generation of solutions. Compared with results from other GA/ACO algorithms, our simulation shows that CGAS has superior performance over other GA and ACO algorithms for solving TSPs in terms of capability and consistency of achieving the global optimal solution, and quality of average optimal solutions, particularly for small TSPs.     

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.     

A novel multiple rule sets data classification algorithm based on ant colony algorithm

Ant colony optimization (ACO) algorithms have been successfully applied in data classification, which aim at discovering a list of classification rules. However, due to the essentially random search in ACO algorithms, the lists of classification rules constructed by ACO-based classification algorithms are not fixed and may be distinctly different even using the same training set. Those differences are generally ignored and some beneficial information cannot be dug from the different data sets, which may lower the predictive accuracy. To overcome this shortcoming, this paper proposes a novel classification rule discovery algorithm based on ACO, named AntMiner_mbc, in which a new model of multiple rule sets is presented to produce multiple lists of rules. Multiple base classifiers are built in AntMiner_mbc, and each base classifier is expected to remedy the weakness of other base classifiers, which can improve the predictive accuracy by exploiting the useful information from various base classifiers. A new heuristic function for ACO is also designed in our algorithm, which considers both of the correlation and coverage for the purpose to avoid deceptive high accuracy. The performance of our algorithm is studied experimentally on 19 publicly available data sets and further compared to several state-of-the-art classification approaches. The experimental results show that the predictive accuracy obtained by our algorithm is statistically higher than that of the compared targets.     

Inducing decision trees with an ant colony optimization algorithm

Decision trees have been widely used in data mining and machine learning as a comprehensible knowledge representation. While ant colony optimization (ACO) algorithms have been successfully applied to extract classification rules, decision tree induction with ACO algorithms remains an almost unexplored research area. In this paper we propose a novel ACO algorithm to induce decision trees, combining commonly used strategies from both traditional decision tree induction algorithms and ACO. The proposed algorithm is compared against three decision tree induction algorithms, namely C4.5, CART and cACDT, in 22 publicly available data sets. The results show that the predictive accuracy of the proposed algorithm is statistically significantly higher than the accuracy of both C4.5 and CART, which are well-known conventional algorithms for decision tree induction, and the accuracy of the ACO-based cACDT decision tree algorithm.     

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

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

A Pheromone-Rate-Based Analysis on the Convergence Time of ACO Algorithm

Ant colony optimization (ACO) has widely been applied to solve combinatorial optimization problems in recent years. There are few studies, however, on its convergence time, which reflects how many iteration times ACO algorithms spend in converging to the optimal solution. Based on the absorbing Markov chain model, we analyze the ACO convergence time in this paper. First, we present a general result for the estimation of convergence time to reveal the relationship between convergence time and pheromone rate. This general result is then extended to a two-step analysis of the convergence time, which includes the following: 1) the iteration time that the pheromone rate spends on reaching the objective value and 2) the convergence time that is calculated with the objective pheromone rate in expectation. Furthermore, four brief ACO algorithms are investigated by using the proposed theoretical results as case studies. Finally, the conclusions of the case studies that the pheromone rate and its deviation determine the expected convergence time are numerically verified with the experiment results of four one-ant ACO algorithms and four ten-ant ACO algorithms.      

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.     

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.     

基于蚂蚁系统的数据流分类算法

数据流分类是数据挖掘中的重要问题,各种针对数据流分类的算法的提出,丰富了数据流挖掘的知识。而蚁群算法是模仿真实蚂蚁觅食行为而提出的一种具有高度创新性的启发元算法,随着其算法设计的不断改进,蚁群优化已成为组合优化领域最具潜力的算法之一。但是,很少有文章将两者联系在一起。本文提出了一种针对数据流分类的蚁群算法,很好地解决了数据流挖掘中的不确定性问题,给出了算法框架,并实现了分类生成、更新、合并和删除算法。在公共数据集上的验证证明算法具有较强的鲁棒性。     

A memetic ant colony optimization algorithm for the dynamic travelling salesman problem

Ant colony optimization (ACO) has been successfully applied for combinatorial optimization problems, e.g., the travelling salesman problem (TSP), under stationary environments. In this paper, we consider the dynamic TSP (DTSP), where cities are replaced by new ones during the execution of the algorithm. Under such environments, traditional ACO algorithms face a serious challenge: once they converge, they cannot adapt efficiently to environmental changes. To improve the performance of ACO on the DTSP, we investigate a hybridized ACO with local search (LS), called Memetic ACO (M-ACO) algorithm, which is based on the population-based ACO (P-ACO) framework and an adaptive inver-over operator, to solve the DTSP. Moreover, to address premature convergence, we introduce random immigrants to the population of M-ACO when identical ants are stored. The simulation experiments on a series of dynamic environments generated from a set of benchmark TSP instances show that LS is beneficial for ACO algorithms when applied on the DTSP, since it achieves better performance than other traditional ACO and P-ACO algorithms.     

Efficient exploitation of the Xeon Phi architecture for the Ant Colony Optimization (ACO) metaheuristic

In recent years, the use of compute-intensive coprocessors has been widely studied in the field of Parallel Computing to accelerate sequential processes through a Graphic Processing Unit (GPU). Intel has recently released a GPU-type coprocessor, the Intel Xeon Phi. It is composed up to 72 cores connected by a bidirectional ring network with a Vector Process Unit (VPU) on large vector registers. In this work, we present novel parallel algorithms of the well-known Ant Colony Optimization (ACO) on the recent many-core platform Intel Xeon Phi coprocessor. ACO is a popular metaheuristic algorithm applied to a wide range of NP-hard problems. To show the efficiency of our approaches, we test our algorithms solving the Traveling Salesman Problem. Our results confirm the potential of our proposed algorithms which led to distinct improvements of performance over previous state-of-the-art approaches in GPU. We implement and compare a set of algorithms to deal with the different steps of ACO. The matrices calculation in the proposed algorithms efficiently exploit the VPU and cache in Xeon Phi. We also show a novel implementation of the roulette wheel selection algorithm, named as UV-Roulette (unique random value roulette). We compare our results in Xeon Phi to state-of-the-art GPU methods, achieving higher performance with large size problems. We also exposed the difficulties and key hardware performance factors to deal with the ACO algorithm on a Xeon Phi coprocessor.     

蚁群算法解决CSAHLP问题时的修正因子的研究

优化蚁群算法是一种基于种群的模拟进化算法,其高效的仿生过程在各类组合问题中有了广泛的应用。CSAHLP经常被用来描述物流在大范围运输时所产生的问题。在CSAHLP问题中,枢流点和节点都是未知参变量,这使得此问题归类于典型的NP问题。ACO作为高效解决NP问题的算法之一,在CSAHLP上有了越来越多的研究应用。但是,蚁群算法也有其自身缺点,受容量约束的条件作为外部约束使得蚁群有时无法得出正确的解。文中详细讨论了蚁群产生非可行解的原因及其处理方法,并通过实验证明方法的有效性。     

Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment

Multiple sequence alignment, known as NP-complete problem, is among the most important and challenging tasks in computational biology. For multiple sequence alignment, it is difficult to solve this type of problems directly and always results in exponential complexity. In this paper, we present a novel algorithm of genetic algorithm with ant colony optimization for multiple sequence alignment. The proposed GA-ACO algorithm is to enhance the performance of genetic algorithm (GA) by incorporating local search, ant colony optimization (ACO), for multiple sequence alignment. In the proposed GA-ACO algorithm, genetic algorithm is conducted to provide the diversity of alignments. Thereafter, ant colony optimization is performed to move out of local optima. From simulation results, it is shown that the proposed GA-ACO algorithm has superior performance when compared to other existing algorithms.     

Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors

Traditional ant colony optimization (ACO) algorithms have difficulty in addressing dynamic optimization problems (DOPs). This is because once the algorithm converges to a solution and a dynamic change occurs, it is difficult for the population to adapt to a new environment since high levels of pheromone will be generated to a single trail and force the ants to follow it even after a dynamic change. A good solution to address this problem is to increase the diversity via transferring knowledge from previous environments to the pheromone trails using immigrants schemes. In this paper, an ACO framework for dynamic environments is proposed where different immigrants schemes, including random immigrants, elitism-based immigrants, and memory-based immigrants, are integrated into ACO algorithms for solving DOPs. From this framework, three ACO algorithms, where immigrant ants are generated using the aforementioned immigrants schemes and replace existing ants in the current population, are proposed and investigated. Moreover, two novel types of dynamic travelling salesman problems (DTSPs) with traffic factors, i.e., under random and cyclic dynamic environments, are proposed for the experimental study. The experimental results based on different DTSP test cases show that each proposed algorithm performs well on different environmental cases and that the proposed algorithms outperform several other peer ACO algorithms.     

An efficient hybrid algorithm for resource-constrained project scheduling

We propose an efficient hybrid algorithm, known as ACOSS, for solving resource-constrained project scheduling problems (RCPSP) in real-time. The ACOSS algorithm combines a local search strategy, ant colony optimization (ACO), and a scatter search (SS) in an iterative process. In this process, ACO first searches the solution space and generates activity lists to provide the initial population for the SS algorithm. Then, the SS algorithm builds a reference set from the pheromone trails of the ACO, and improves these to obtain better solutions. Thereafter, the ACO uses the improved solutions to update the pheromone set. Finally in this iteration, the ACO searches the solution set using the new pheromone trails after the SS has terminated. In ACOSS, ACO and the SS share the solution space for efficient exchange of the solution set. The ACOSS algorithm is compared with state-of-the-art algorithms using a set of standard problems available in the literature. The experimental results validate the efficiency of the proposed algorithm.     

Runtime analysis of the 1-ANT ant colony optimizer

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. First runtime analyses of ant colony optimization (ACO) have been conducted only recently. In these studies simple ACO algorithms such as the 1-ANT are investigated. The influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w.r.t. the runtime behavior have been determined for the example function OneMax.This work puts forward the rigorous runtime analysis of the 1-ANT on the example functions LeadingOnes and BinVal. With respect to Evolutionary Algorithms (EAs), such analyses were essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice has a crucial impact on the runtime. Moreover, the analyses provide insight into the working principles of ACO algorithms. Our theoretical results are accompanied by experimental results that give us a more detailed impression of the 1-ANT’s performance. Furthermore, the experiments also deal with the question whether using many ant solutions in one iteration can decrease the total runtime.     

基于蚁群优化分类规则挖掘的遥感图像分类研究

蚁群优化算法作为群智能理论的主要算法之一,已经成功应用在众多研究领域的优化问题上,但是在遥感数据处理领域还是一个新的研究课题。蚁群优化具有自组织、合作、通信等智能化优点,对数据无需统计分布参数的先验知识,因此在遥感数据处理领域具有很大的潜在优势。介绍了将蚁群优化分类规则挖掘算法应用到遥感图像分类研究领域的理论与算法流程。并采用北京地区的CBERS遥感数据作为实验数据,通过蚁群优化算法构造分类规则,对选择的遥感数据进行了分类实验,并和最大似然分类方法进行对比,实验结果表明,蚁群优化分类规则挖掘算法为遥感图像的分类提供了一种新方法。     

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.     

A bio-inspired distributed algorithm to improve scheduling performance of multi-broker grids

The scheduling in grids is known to be a NP-hard problem. The distributed deployment of nodes, their heterogeneity and their fluctuations in terms of workload and availability make the design of an effective scheduling algorithm a very complex issue. The scientific literature has proposed several heuristics able to tackle this kind of optimization problem using techniques and strategies inspired by nature. The algorithms belonging to ant colony optimization (ACO) paradigm represent an example of these techniques: each one of these algorithms uses strategies inspired by the self-organization ability of real ants for building effective grid schedulers. In this paper, the authors propose an on line, non-clairvoyant, distributed scheduling solution for multi-broker grid based on the alienated ant algorithm (AAA), a new ACO inspired technique exploiting a “non natural” behavior of ants and an inverse interpretation of pheromone trails. The paper introduces the proposed algorithm, explains the differences with other classical ACO approaches, and compares AAA with two different algorithms. The results of simulations show that the AAA guarantees good performance in terms of makespan, average queue waiting time and load balancing capability.     

Ant colony algorithms in MANETs: A review

Mobile ad-hoc networks (MANETs) consist of special kind of wireless mobile nodes which form a temporary network without using any infrastructure or centralized administration. MANETs can be used in wide range of future applications as they have the capability to establish networks at anytime, anywhere without aid of any established infrastructure. It is a challenging task to find most efficient routing due to the changing topology and the dynamic behavior of the nodes in MANET. It has been found that ant colony optimization (ACO) algorithms can give better results as they are having characterization of Swarm Intelligence (SI) which is highly suitable for finding the adaptive routing for such type of volatile network. ACO algorithms are inspired by a foraging behavior of group of ants which are able to find optimal path based upon some defined metric which is evaluated during the motion of ants. ACO routing algorithms use simple agents called artificial ants which establish optimum paths between source and destination that communicate indirectly with each other by means of stigmergy. Keeping in view of the above, in this paper we provide a taxonomy of various ant colony algorithms with advantages and disadvantages of each others with respect to various metrics.