Research And Implementation Of Chaotic Ant Colony Optimization Based On Spark Platform

Combinatorial Optimization problem is to find the optimal solution from all feasible solutions, but the solution process of Combinatorial Optimization problem requires very big storage space and extremely long run time by traditional way. In the era of Big Data, the amount of data in each area generated in exponential growth, which makes the computing model of Spark widely used in parallel computing, so using the parallel computing model of Spark to solve "Combinatorial Explosion" problem is a quite feasible scheme. People tend to use Meta Heuristic algorithm to solve Combinatorial Optimization problem. For example the Ant Colony Optimization is one of Meta Heuristic algorithm which is based on ant foraging behavior. This algorithm has the advantage of robustness, distributed operation, and easily integration with other algorithms. At present, the Ant Colony Optimization algorithm has been widely applied to solute Combinatorial Optimization problem and also achieved good results, but it also has some issues such as easily falling into local optimal solution and slow convergence. According to the parallel characteristics of ant colony in building feasible solution and the distribution features of Cloud Computing platform, the paper proposed Chaotic Ant Colony Optimization algorithm based on Spark platform. The researches are as follows:1. When processing large-scale Traveling Salesman Problem, the basic Ant Colony Optimization more easily falls into local optimal solution and convergences slowly. In order to expand the search space of ant colony, the paper uses Roulette Strategy to randomly select the next city from several candidate cities when the ants select path. Then according to the Chaos Theory, the proposed algorithm dynamically adjusts the pheromone evaporation coefficient, which method avoids algorithm falling into local optimal solution. Then the paper uses Mutation Operators to process each iteration path, expecting to get the most optimal path. Finally, in order to improve the algorithm efficiency, the proposed algorithm was implemented by MapReduce parallel computing model, and deployed on Hadoop platform.2. Basic on the full study of Spark platform, the paper uses the Spark parallel computing model to implement the improved Ant Colony Optimization. Firstly, the proposed algorithm packages ant colony into a Resilient Distributed Dataset, and divided the dataset into some same scale populations. Then the proposed algorithm shares the pheromone matrix in the cluster nodes by broadcast mechanism provided by Spark. With fully using of the memory computing features of Spark platform, the algorithm realizes the parallelism of ant colony to build feasible solution. This method can make the large-scale Combinatorial Optimization problem to be processed much faster.3. Experiments show that, for specific scale of ant colony, the computing speed of the Ant Colony Optimization does not continuously improve along with increasing the number of cluster nodes. The paper selects some different examples of Traveling Salesman Problem from TSPLIB library to verify the feasible of the proposed algorithm. The results show that, with the increase of ant colony scale, the run time of the Chaotic Ant Colony Optimization based on MapReduce was greatly shorter than that of the basic Ant Colony Optimization, and the run time of Chaotic Ant Colony Optimization based on Spark is faster than that of the first two algorithms. In addition, the path optimal solution of the proposed algorithm had greatly improved than that of the basic Ant Colony Optimization.