An algorithm based on ant colony optimization for the minimum connected dominating set problem

Ant colony optimization is a well established metaheuristic from the swarm intelligence field for solving difficult optimization problems. In this work we present an application of ant colony optimization to the minimum connected dominating set problem, which is an NP-hard combinatorial optimization problem. Given an input graph, valid solutions are connected subgraphs of the given input graph. Due to the involved connectivity constraints, out-of-the-box integer linear programming solvers do not perform well for this problem. The developed ant colony optimization algorithm uses reduced variable neighborhood search as a sub-routine. Moreover, it can be applied to the weighted and to the non-weighted problem variants. An extensive experimental evaluation presents the comparison of our algorithm with the respective state-of-the-art techniques from the literature. It is shown that the proposed algorithm outperforms the current state of the art for both problem variants. For comparison purposes we also develop a constraint programming approach based on graph variables. Even though its performance deteriorates with growing instance size, it performs surprisingly well, solving 315 out of 481 considered problem instances to optimality.     

A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem

This paper presents a new variant of Ant Colony Optimization (ACO) for the Traveling Salesman Problem (TSP). ACO has been successfully used in many combinatorial optimization problems. However, ACO has a problem in reaching the global optimal solutions for TSPs, and the algorithmic performance of ACO tends to deteriorate significantly as the problem size increases. In the proposed modification, adaptive tour construction and pheromone updating strategies are embedded into the conventional Ant System (AS), to achieve better balance between intensification and diversification in the search process. The performance of the proposed algorithm is tested on randomly generated data and well-known existing data. The computational results indicate the proposed modification is effective and efficient for the TSP and competitive with Ant Colony System (ACS), Max-Min Ant System (MMAS), and Artificial Bee Colony (ABC) Meta-Heuristic.     

Countering the negative search bias of ant colony optimization in subset selection problems

In their quest to find a good solution to a given optimization problem, metaheuristic search algorithms intend to explore the search space in a useful and efficient manner. Starting from an initial state or solution(s), they are supposed to evolve towards high-quality solutions. For some types of genetic algorithms (GAs), it has been shown that the population of chromosomes can converge to very bad solutions, even for trivial problems. These so-called deceptive effects have been studied intensively in the field of GAs and several solutions to these problems have been proposed. Recently, similar problems have been noticed for ant colony optimization (ACO) as well. As for GAs, ACO's search can get biased towards low-quality regions in the search space, probably resulting in bad solutions. Some methods have been proposed to investigate the presence and strength of this negative bias in ACO. We present a framework that is capable of eliminating the negative bias in subset selection problems. The basic Ant System algorithm is modified to make it more robust to the presence of negative bias. A profound simulation study indicates that the modified Ant System outperforms the original version in problems that are susceptible to bias. Additionally, the proposed methodology is incorporated in the Max–Min AS and applied to a real-life subset selection problem.     

PASCP在大规模TSP中的应用

蚂蚁系统是由M．Dorigo等人首先提出的一种新型的模拟进化算法，初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力，但同时也存在收敛速度慢等缺点。该文提出了一种带聚类处理的并行蚂蚁系统，该算法首先将大规模TSP问题通过聚类处理分解成一些小规模，ISP问题，然后对每一个小规模TSP问题分别使用蚂蚁系统并行求解，最后将所有小规模TSP问题的解合并成TSP问题的解。对带聚类特征的大规模TSP问题的仿真实验表明该算法极大地提高了蚂蚁系统的收敛速度。     

THE COMBINATORIAL ANT SYSTEM

This paper presents a new distributed algorithm based on Ant System (AS) concepts called Combinatorial Ant System (CAS). It is oriented to solve static discrete-state combinatorial optimization problems. Our approach consists of mapping the solution space of the combinatorial optimization problem in the space where the ants will walk, and defining the transition probability and the pheromone update formula of the Ant System, according to the objective function of the Combinatorial Optimization Problem. We test our approach on the graph partitioning, graph coloring and traveling salesman problems.     

求解可满足问题的改进的蚁群算法

可满足问题(SAT)是一个NP-hard问题,将SAT问题转换为无约束的离散优化(最小值)问题。并根据MDorigo提出的蚁群算法,给出了一种求解SAT问题的新方法:改进的最大最小蚁群系统(MMAS-SAT)。在改进的算法中,给出了SAT问题的构造图,指出了启发式信息值的求法,对衰变系数进行了动态调整。测试问题的数值实验表明,采用MMAS-SAT的结果优于Gwsat、Walksat、Novelty等局部搜索算法,因此该算法是求解SAT问题的一种可行高效的算法。     

一种求解异构DAG调度问题的置换蚁群

减少分布式程序的执行时间,是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。提出的置换调度蚁群PSACS(Permutation Scheduling Ant Colony System)将DAG调度方案表示为任务置换列表,使用标准蚁群搜索技术探索解空间。实验表明,该算法明显优于遗传算法和粒子群算法,能够一次求出大部分(65%)同构DAG调度问题的最优解并获得非常好的异构DAG调度方案。     

– 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.     

A Max–Min Ant System algorithm to solve the Software Project Scheduling Problem

The Software Project Scheduling Problem is a specific Project Scheduling Problem present in many industrial and academic areas. This problem consists in making the appropriate worker-task assignment in a software project so the cost and duration of the project are minimized. We present the design of a Max–Min Ant System algorithm using the Hyper-Cube framework to solve it. This framework improves the performance of the algorithm. We illustrate experimental results and compare with other techniques demonstrating the feasibility and robustness of the approach, while reaching competitive solutions.     

蚁群算法在物化视图选择问题中的应用

提出用蚁群算法来解决物理空间约束下的物化视图选择问题，算法中应用信息素的局部和全局更新，并对每次迭代的最优解进行局部搜索，最终得出合理的解决方案。实验结果表明，应用蚁群算法可以有效地解决物化视图选择问题，并且其求解性能优于遗传算法。