Dynamic Flying Ant Colony Optimization (DFACO) for Solving the Traveling Salesman Problem

Area of Science:

• Artificial Intelligence
• Optimization Algorithms
• Computational Science

Background:

• The traveling salesman problem (TSP) is a well-known combinatorial optimization challenge.
• Existing algorithms often suffer from stagnation, limiting their effectiveness.
• The flying ant colony optimization (FACO) algorithm, initially for QoS-aware web service selection, offers a novel approach to pheromone deposition.

Purpose of the Study:

• To adapt and enhance the FACO algorithm for solving the TSP.
• To develop a dynamic version of FACO (DFACO) that mitigates stagnation and improves solution quality.
• To evaluate the performance of DFACO against established algorithms on benchmark TSP datasets.

Main Methods:

• Modification of FACO to incorporate dynamic pheromone distribution based on solution quality.
• Integration of the 3-Opt algorithm to refine solutions and combat stagnation.
• Hybridization of regular and flying ants within the colony structure.
• Comparative analysis of DFACO against Ant Colony Optimization (ACO) and parallel ACO (PACO)-3Opt.

Main Results:

• DFACO significantly outperformed ACO and five other methods on 23 out of 24 TSP datasets in solution quality.
• DFACO demonstrated superior performance compared to PACO-3Opt on 20 out of 21 datasets, excelling in both solution quality and execution time.
• The modifications successfully balanced exploration and exploitation strategies, reducing the likelihood of getting trapped in local minima.

Conclusions:

• The proposed dynamic flying ant colony optimization (DFACO) algorithm is a highly effective method for solving the traveling salesman problem.
• DFACO offers a robust solution that overcomes the stagnation issues prevalent in many TSP algorithms.
• The algorithm achieves superior results in terms of solution quality and processing efficiency, making it a valuable advancement in optimization techniques.