Implementing a GPUbased parallel MAXMIN Ant System Abstract   The MAXMIN Ant System (MMAS) is one of the bestknown Ant Colony Optimization (ACO) algorithms proven to be efficient at finding satisfactory solutions to many difficult combinatorial optimization problems. The slowdown in Moorexe2x80x99s law, and the availability of graphics processing units (GPUs) capable of conducting generalpurpose computations at high speed, has sparked considerable research efforts into the development of GPUbased ACO implementations. In this paper, we discuss a range of novel ideas for improving the GPUbased parallel MMAS implementation, allowing it to better utilize the computing power offered by two subsequent Nvidia GPU architectures. Specifically, based on the weighted reservoir sampling algorithm we propose a novel parallel implementation of the node selection procedure, which is at the heart of the MMAS and other ACO algorithms. We also present a memoryefficient implementation of another keycomponent xe2x80x93 the tabu list structure xe2x80x93 which is used in the ACOxe2x80x99s solution construction stage. The proposed implementations, combined with the existing approaches, lead to a total of six MMAS variants, which are evaluated on a set of Traveling Salesman Problem (TSP) instances ranging from 198 to 3,795 cities. The results show that our MMAS implementation is competitive with stateoftheart GPUbased and multicore CPUbased parallel ACO implementations: in fact, the times obtained for the Nvidia V100 Volta GPU were up to 7.18x and 21.79x smaller, respectively. The fastest of the proposed MMAS variants is able to generate over 1 million candidate solutions per second when solving a 1,002city instance. Moreover, we show that, combined with the 2opt local search heuristic, the proposed parallel MMAS finds highquality solutions for the TSP instances with up to 18,512 nodes.

Ant Colony Optimization Parameters Control Based on Evolutionary Strength Ant Colony Optimization (ACO) was developed to be a metaheuristic and widely used for combinatorial optimization problems. It is confirmed that the parameters setting is of vital importance for performance of ACO. This paper proposed a strategy to perform ACO Parameters Control based on Evolutionary Strength (ACOP_ES). First, we transform four parameters setting problem to decision making problem. Then, by learning the evolutionary strength curve, we set sum, peak, and kurtosis of evolutionary strength curve as the objective function, such that the continuous ant colony algorithm can be used to optimize this decision problem. Further, via characterizing an excellent evolutionary curve, a relatively optimal parameters setting can be found. Compared with existing methods, our proposed method focuses on the performance of the running process rather than the results only. To the best of our knowledge, we are among the first to introduce process performance evaluation of ACO to guide parameters control, and determine the relatively optimal parameters of ACO. At last, we apply our method to Multidimensional Knapsack Problem (MKP), the results look promising that parameters returned by ACOP_ES are better than the ones returned by other methods on datasets: WEISH*.DAT and WEING*.DAT.