{'fraction_non_alphanumeric': 0.0234366068366297, 'fraction_numerical': 0.0090316680004573, 'mean_word_length': 5.253037884203002, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Overview and Applications of GPGPU Based Parallel Ant Colony Optimization

Ant Colony Optimization algorithm is a magnificent heuristics technique based on the behavior of ants. Parallel computing is a means to achieve the desired results in commensurable execution time. Parallelization of Ant Colony Optimization is utilized to solve large and complex problems. This paper discusses a review of different parallelization approaches for Ant Colony Optimization and its various applications. Parallel Ant Colony Optimization has proved to be a successful approach for highly constrained problems such as routing, scheduling, timetabling, etc. Parallelization of Ant Colony Optimization reduces the execution time, increases the size of the problem, etc.


Introduction
Ant colony optimization (ACO) is a population-based search method inspired by the behavior of real ants. ACO was proposed by Dorigo and colleagues (2006) for solving hard combinatorial optimization problems.
Ants search for food, in the vicinity of their nest. During their mission, ants deposit a chemical substance called pheromone on the ground. The objectives of such activity are, to allow ants to find their way back to the nest and also it allows other ants to know the way they have taken, so that they can follow them (Dorigo and Stutzle, 2010). ACO has proved to be a successful approach for highly constrained problems in different areas. Marta et al. (2012) has provided a wide literature survey on ACO.
As ACO algorithm is population-based, it is a collection of agents working in team to find an optimal solution. ACO usually converge to near optimal solution in a certain number of iterations with considerable computational resources and time. To improve performance of ACO, parallel implementation is an excellent thought (Dorigo and Stutzle, 2001).
In this paper, section 2 outlines the working of ACO and GPGPU computing. Section 3 gives details about different approaches for parallelizing ACO found in literature. In section 4, few applications of parallel ant colony optimizations are discussed. Conclusion of study with future research direction is presented in section 5.

GPGPU Computing And Ant Colony Optimization
The GPGPU computing is advanced from the early 1980s to the late 1990s. The Fig.1 shows the CPU and GPU architecture. There is a large performance gap between many-threads GPUs and general-purpose multicore CPUs. It is discussed in Kirk and Hwu (2010) as; design of CPU is optimized for sequential code performance. It makes use of sophisticated control logic to allow instructions from a single thread of execution to execute in parallel or even out of their sequential order while maintaining the appearance of sequential execution; large cache memories are provided to reduce the instruction and data access latencies of large complex applications (Kirk and Hwu, 2010). The need of performance improvement in highly computational problems has made the GPGPU computing as emerging research area. GPGPU computing is an attraction of many researchers because of the low-cost, high availability and its SIMD (Single Instruction, Multiple Data) nature, which are inherently data-parallel.
In the CUDA framework, the GPU is viewed as a co-processor to the CPU. The GPU has its own device memory, and execute a very high number of threads in parallel. A kernel executes the data-parallel portions of an application on the GPGPU device using threads. CUDA organizes threads in execution into different blocks, which are mapped onto a multiprocessor in the GPU (NVIDIA, 2010). All the threads in one block are synchronized together and communicate with each other. The thread organization is as shown in Fig. 2 (Kirk and Hwu, 2010). The ACO algorithm has four main steps, taken from Dorigo et al. (2006) and represented as:

Initialization:
Initial population is generated randomly, where initial population of the colony and the pheromone trail are set randomly. The starting node for all ants set randomly.

Solution construction
Ant selects the next node by observing the problem-dependent heuristic information and the trail intensity of the path. This step is repeated until all complete solution is constructed.

Trail update
Solution and deposited pheromone on the solution path are evaluated. If the greater amount of pheromone is deposited on the solution path, then better the solution.

Pheromone evaporation
The pheromone trail of all solution paths is decreased by some constant factor at the end of an iteration of building completed solutions.

Different Approaches for Parallelizing Ant Colony Optimization
Parallel implementations became popular with the intention of improving the efficiency of population-based search methods for solving complex optimization problems (Delisle 2012). In parallel implementations, the population is divided into several independent clusters and computing resources are assigned to process it. It benefits to heuristic techniques to obtain high quality results in a reasonable execution time, though optimization problems are hard-to solve (Dawson and Stewart, 2013). Parallel implementation of heuristic introduces a new exploration pattern useful to improve the result quality of the sequential implementations (Dorigo and Stutzle, 2010). The metric used to measure performance of parallel algorithms are speedup and efficiency (Randall and Lewis, 2009;Kothapalli et al., 2009). The speedup evaluates how much faster a parallel algorithm is than a corresponding sequential version.
To improve the results quality and the computational efficiency, in literature different approaches for parallel implementations of ACO are proposed.
To parallelize evolutionary algorithms, the traditional parallelization strategies are Master-slave model, cellular model, island model, and hybrid model. The master-slave model has subcategories as, Coarse-grain, Medium-grain and Fine-grain master-slave model. These models are used by researchers to parallelize ACO. Few other strategies are also proposed by researchers to parallelize ACO. In independent runs model communication between numerous sequential algorithms is absent. In multi-colony model, number of ant colonies is working independently but after some time interval colonies share information among them to achieve cooperation among colonies. The hybrid model is combination of other models ( The parallelization strategy to be used depends on the particular problem one has to solve and the available hardware. Most parallelization strategies can be classified into fine-grained and coarse-grained approaches. Characteristic of fine-grained approaches is that very few, often only one, individuals are assigned to one processors and individuals are connected by a population-structure. In coarse-grained approaches, larger subpopulations are assigned to single processors and information exchange is rather rare (Dorigo et al., 2006;Delevacq, 2013).

Applications of Parallel Ant Colony Optimization on GPGPU
The parallel ACO is used to solve problems in the combinatorial optimization, real-life routing and planning, industrial design. Bioinformatics, Telecommunications, other scientific problems, theoretical works. Day by day applications developed using parallel ACO and its variants on GPGPU, OpenMP or MPICH are increasing. Few applications developed using parallel ACO and its variants are summarized in Table 1

Conclusion And Research Scope
Ant Colony Optimization (ACO) belongs to the family of population-based search method that has been successfully applied to many NP-hard problems. As a population based algorithm, it is intrinsically parallel, and thus well suited for implementation on parallel architectures. This paper, gives review of parallel ACO with different applications of Parallel ACO. Parallel implementations of heuristic techniques allow reaching high quality results in a reasonable execution time. The scalability of the GPU is excellent for parallel problems such as optimization problems. Overall, this shows that it is possible to significantly reduce the execution time of ACO on GPU. Though, the GPU has improved significantly both in terms of programmability and performance, It performs particularly well on data parallel applications. Thus an argument can be made that, a GPU as a whole is a good candidate for general purpose computing.
GPGPU is good option to improve speedup while solving optimization problems using Ant Colony Optimization. The speed-up obtainable through parallelization should be highly important for solving larger problem instances in real time. In future the constraint satisfaction problems, employee scheduling problems can be solved with parallelization of ACO on GPGPU.