Development of a Convolution-Based Multi-Directional and Parallel Ant Colony Algorithm Considering a Network with Dynamic Topology Changes

摘要

While network path generation has been one of the representative Non-deterministic Polynomial-time (NP)-hard problems, changes of network topology invalidate the effectiveness of the existing metaheuristic algorithms. This research proposes a new and efficient path generation framework that considers dynamic topology changes in a complex network. In order to overcome this issue, Multi-directional and Parallel Ant Colony Optimization (MPACO) is proposed. Ant agents are divided into several groups and start at different positions in parallel. Then, Gaussian Process Regression (GPR)-based pheromone update method makes the algorithm more efficient. While the proposed MPACO algorithm is more efficient than the existing ACO algorithm, it is limited in a network with topological changes. In order to overcome the issue, the MPACO algorithm is modified to the Convolution MPACO (CMPACO) algorithm. The proposed algorithm uses the pheromone convolution method using a discrete Gaussian distribution. The proposed pheromone updating method enables the generation of a more efficient network path with comparatively less influence from topological network changes. In order to show the effectiveness of CMPACO, numerical networks considering static and dynamic conditions are tested and compared. The proposed CMPACO algorithm is considered a new and efficient parallel metaheuristic method to consider a complex network with topological changes.