Ant Colony Optimisation (ACO) is an effective population-based meta-heuristic for the solution of a wide variety of problems. As a population-based algorithm, its computation is intrinsically massively parallel, and it is therefore theoretically well-suited for implementation on Graphics Processing Units (GPUs). The ACO algorithm comprises two main stages: textit Tour construction and textit Pheromone update . The former has been previously implemented on the GPU, using a task-based parallelism approach. However, up until now, the latter has always been implemented on the CPU. In this paper, we discuss several parallelisation strategies for it both stages of the ACO algorithm on the GPU. We propose an alternative it data-based parallelism scheme for textit Tour construction , which fits better on the GPU architecture. We also describe novel GPU programming strategies for the textit Pheromone update stage. Our results show a total speed-up exceeding 28x for the textit Tour construction stage, and 20x for textit Pheromone update , and suggest that ACO is a potentially fruitful area for future research in the GPU domain.
St "uzle @cite_16 describes the simplest case of ACO parallelisation, in which independently instances of the ACO algorithm are run on different processors. Parallel runs have no communication overhead, and the final solution is taken as the best-solution over all independent executions. Improvements over non-communicating parallel runs may be obtained by exchange information among processors. Michel and Middendorf @cite_2 present a solution based on this principle, whereby separate colonies exchange pheromone information. In more recent work, Chen @cite_12 divide the ant population into equally-sized sub-colonies, each assigned to a different processor. Each sub-colony searches for an optimal local solution, and information is exchanged between processors periodically. Lin @cite_20 propose dividing up the problem into subcomponents, with each subgraph assigned to a different processing unit. To explore a graph and find a complete solution, an ant moves from one processing unit to another, and messages are sent to update pheromone levels. The authors demonstrate that this approach reduces local complexity and memory requirements, thus improving overall efficiency.
@cite_16 @cite_20 @cite_12 @cite_2
2111042423 2166747012 2387603477 1978232925
An adaptive parallel ant colony algorithm (PACO) is presented. In the algorithm, we propose a strategy for information exchange between processors which make each processor choose its partner to communicate and update the pheromone adaptively. We also propose a method of adjusting the time interval of information exchange adaptively according to the diversity of the solutions so as to increase the ability of search and avoid early convergence. Experimental results show that our algorithm PACO has high convergence speed, high speedup and efficiency. This paper presents a pseudo parallel ant colony optimization (ACO) algorithm in continuous domain. The variables of a solution are optimized by two parallel cooperative ACO-based processes, either of which attacks a relatively-independent sub-component of the original problem. Both processes contain tunable and untunable solution vectors. The best tunable vector migrates into the other process as an untunable vector through a migration controller, in which the migration strategy is synchronously sprung or adaptively controlled according to the temporal stagnation situation. Implementation of this mechanism is suitable for hardware which supports parallel computation, resulting in decline of unit computational cost and improvement of training speed. Optimization to a set of benchmark functions is carried out to prove the feasibility and efficiency of this parallel ACO algorithm. An algorithm of fine-grained parallel ant colony optimization algorithm(ACO) based on graphics process unit(GPU) accelerated is proposed to improve the performance of ACO for application to large-scale TSP problems.The process of parallel ACO is convert into that of parallel compute unified device architecture(CUDA) thread blocks,which makes PACO speed up.The experimental results show that the algorithm improves the ability of global search,increases the ant population in the PACO,speeds up its running and provides ordinary user with a feasible PACO solution. In this paper an ant colony optimization (ACO) algorithm for the minimum connected dominating set problem (MCDSP) is presented. The MCDSP become increasingly important in recent years due to its applicability to the mobile ad hoc networks (MANETs) and sensor grids. We have implemented a one-step ACO algorithm based on a known simple greedy algorithm that has a significant drawback of being easily trapped in local optima. We have shown that by adding a pheromone correction strategy and dedicating special attention to the initial condition of the ACO algorithm this negative effect can be avoided. Using this approach it is possible to achieve good results without using the complex two-step ACO algorithm previously developed. We have tested our method on standard benchmark data and shown that it is competitive to the existing algorithms. [Projekat Ministarstva nauke Republike Srbije, br. III-44006]