Fine-grained Parallel Ant Colony System for Shared-Memory Architectures
Although Ant Colony Systems (ACS) have gained much attention in last two decades but slow execution and convergence speed are still two challenges for these meta-heuristic algorithms. Many parallel implementations have been proposed for faster execution. However, most of available implementations use coarse-grained synchronization mechanisms that are not efficient and scalable. In this paper, the authors have taken a fine-grained (ant-level) approach that is more efficient and scalable. They have used traveling salesman problem as a test case and have presented a parallel fine-grained implementation for shared-memory multi-core systems. Their experimental results show that the proposed parallel implementation can achieve considerably higher speedup values on modern multi-core processors.