بررسی موازی بهینه سازی کلونی مورچه ها

Ant colony optimization (ACO) is a well-known swarm intelligence method, inspired in the social behavior of ant colonies for solving optimization problems. When facing large and complex problem instances, parallel computing techniques are usually applied to improve the efficiency, allowing ACO algorithms to achieve high quality results in reasonable execution times, even when tackling hard-to-solve optimization problems. This work introduces a new taxonomy for classifying software-based parallel ACO algorithms and also presents a systematic and comprehensive survey of the current state-of-the-art on parallel ACO implementations. Each parallel model reviewed is categorized in the new taxonomy proposed, and an insight on trends and perspectives in the field of parallel ACO implementations is provided

In the last twenty years, the research community has been searching for new optimization techniques that are able to improve over the traditional exact ones, whose large computational requirements often make them useless for solving complex real-life optimization problems in acceptable times. In this context, nature-inspired metaheuristic methods have emerged as flexible and robust tools for solving NP-hard optimization problems, exploiting their ability to compute accurate solutions in moderate execution times [13] and [49]. Ant colony optimization (ACO) is a swarm intelligence population-based metaheuristic inspired in the social behavior of ant colonies, which applies the key concepts of distributed collaboration, self-organization, adaptation, and distribution found in ant communities, in order to efficiently solve real-life optimization problems [41]. Parallel implementations became popular in the last decade in order to improve the efficiency of population-based metaheuristics. By splitting the population into several processing elements, parallel implementations of metaheuristics allow reaching high quality results in a reasonable execution time, even when facing hard-to-solve optimization problems [2]. Parallel algorithms not only take benefit of using several computing elements to speed up the search, they also introduce a new exploration pattern that is often useful to improve over the result quality of the sequential implementations. Many papers can be found in the related literature stating that parallel implementations are useful to improve the ACO exploration pattern; Fig. 1 shows the number of publications per year in this area. However, researchers often lack a generalized point of view, since they usually tackle a unique implementation to solve a specific problem.Dorigo [39] and [40] first suggested the application of parallel computing techniques to enhance both the ACO search and its computational efficiency, while Randall and Lewis [84] proposed the first classification of ACO parallelization strategies. The book chapter by Janson et al. [57] and the article by Ellabib et al. [46] are the only previous works that have collected bibliography of published papers proposing parallel ACO implementations. Janson et al. reviewed parallel ACO proposals published up to 2002, focusing on comparing “parallelized” standard ACO algorithms, specific parallel ACO methods, and hardware parallelization; although they did not include an explicit algorithmic taxonomy. Ellabib et al. briefly commented parallel ACO implementations up to 2004, focusing in describing the applications, and they only distinguished between coarse-grain and fine-grain models for parallel ACO. The classic proposals of parallel ACOs focused on traditional supercomputers and clusters of workstations. Nowadays, the novel emergent parallel computing architectures such as multicore processors, graphics processing units (GPUs), and grid environments provide new opportunities to apply parallel computing techniques to improve the ACO search results and to lower the required computation times. In this line of work, the main contributions of this article are: (i) to introduce a new taxonomy to classify software-based parallel ACO algorithms, (ii) to present a systematic and comprehensive survey of the current state-of-the-art on parallel ACO implementations, and (iii) to provide an insight of the current trends and perspectives in the field. The survey focuses mainly on the parallel models, addressing the principal characteristics of each proposal, the experimental analysis – including the optimization problems faced, the test cases and the parallel platform used in the experiments, and the reported results –, and the main contributions of the reviewed works. Each parallel ACO proposal is categorized in the new taxonomy proposed. The manuscript is structured as follows. Next section describes the research methodology used in the review. Section 3 describes the main features of the ACO technique and briefly introduces the most popular ACO variants. Section 4 presents the generic concepts of the strategies for ACO parallelization and comments previous classification criteria. It also describes the new taxonomy proposed in this work to categorize parallel ACOs. Section 5 reviews the previous work on parallel ACO implementations and categorizes each proposal using the new taxonomy. A comparative analysis regarding the computational efficiency and quality of results is offered in Section 6. Section 7 presents the trends and perspectives in the field of parallel ACO implementations, before stating the conclusions of the survey in Section 8.

This article presents a general overview of parallel ant colony optimization and an exhaustive survey of the proposed implementations. It includes a conceptual discussion of these methods, looking at different classification criteria and previous efforts to develop categories for parallel ACO algorithms. The survey has been the basis to develop a proposal for a new taxonomy, which is a helpful conceptual tool to both understand and organize the existing work, and to identify possible areas for future research. The work also includes an exhaustive review of the literature in the area, starting from the pioneering works in parallel ACO, up to the most recent proposals (up to December 31, 2010). The reviewed papers are organized according to the new taxonomy, and the main characteristics of the methods employed, as well as the application problems and results obtained, are presented. The discussion of each class concludes with a summary presenting its main features and a list of general conclusions about the efficacy of the corresponding methods. A comparative analysis regarding the computational efficiency and quality of results is also presented. The final section of the paper discusses some trends and perspectives about parallel ACO, including recommendations about the most effective parallel models and implementations. It also provides observations about the software issues and libraries, the employed parallel platforms and the application domains, which can be a source of inspiration for future research in the field.