Visual Feedback And Memory Behavior Based GPU Parallel Ant Colony Algorithm

Ant Colony Optimization algorithm (ACO) is an efficient heuristic algorithm which is widely used in data mining, routing and addressing, robot planning and other realms. However, slow in convergence and low searching performance still restrict the development of ant colony algorithm, make it not suitable for large scale optimization problems. Therefore, how to improve its performance has long been a hot topic in this area. Two strategies are mainly used:First, improve the model of ACO; second, using parallel method.Both of these two strategies are used in this paper:Firstly, Based on the analysis of existing Ant Colony Optimization (ACO) algorithms and the studies in visual perception and cognitive psychology, this paper proposes a new optimization strategy, the visual feedback and behavioral memory based Max-Min Ant Colony Optimization algorithm (VM-MMACO). The main idea is to enhance the ant's search ability by establishing the learning mechanism of visual feedback and behavioral memory. With artificial visual, memory and learning abilities, the ant can not only see the targets around, using visual perception to optimize the heuristic information produced by pheromone in order to improve the search quality, but also exploit the historical solutions, finding local best segments (called experience) to narrow the searching space smoothly so that it can accelerate the convergence process;Secondly, using CUDA (Computed Unified Device Architecture) in GPU environment to paralyze the new model. CUDA is proposed by NVIDIA Company and it can take the most advantage of GPU to implement parallel computing and substantially shorten the time. The parallel implementation and simulation are showed in this section.Comparisons of VM-MMACO and several existing optimization strategies within a given iteration number are performed and the results demonstrates that VM-MMACO really outperforms other optimization strategies. The results in GPU environment demonstrate that the new model can be highly paralyzed and can get a greater speedup.