You are provided with the abstract of a scientific paper and the abstracts of the papers it references. Your task is to write a Related Work section for the main paper. This section should concisely summarize and integrate the key points from the cited abstracts, reflecting how they relate to the main paper's contributions and context. In your summary, use numerical citation markers like [1], [2], etc., to refer to the corresponding papers.

Main Abstract:
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.

Cited Abstract(s):
[1]: Ant Colony Optimization (ACO) is a new population oriented search metaphor that has been successfully applied to NP-hard combinatorial optimization problems. In this paper we discuss parallelization strategies for Ant Colony Optimization algorithms. We empirically test the most simple strategy, that of executing parallel independent runs of an algorithm. The empirical tests are performed applying MAX-MIN Ant System, one of the most efficient ACO algorithms, to the Traveling Salesman Problem and show that using parallel independent runs is very effective.

[2]: 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.

[3]: 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.

[4]: In this paper we introduce an Ant Colony Optimisation (ACO) algorithm for the Shortest Common Supersequence (SCS) problem, which has applications in production system planning, mechanical engineering and molecular biology. The ACO algorithm is used to find good parameters for a heuristic for the SCS problem. An island model with several populations of ants is used for the ACO algorithm. Besides we introduce a lookahead function which makes the decisions of the ants dependent on the state arrived after the decision.
St "uzle [1] 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 [4] present a solution based on this principle, whereby separate colonies exchange pheromone information. In more recent work, Chen [3] 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 [2] 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.