Comparative analysis of genetic algorithm, ant colony optimisation and particle swarm optimisation on the travelling salesman problem and the 0/1 knapsack problem

The paper is a comprehensive comparative analysis of three widely recognised metaheuristic algorithms: Genetic Algorithm (GA), Ant Colony Optimization (ACO), and Particle Swarm Optimization (PSO), applied to two classic NP-hard optimisation problems - the Traveling Salesman Problem (TSP) and the 0/1 Knapsack Problem. Utilising standard benchmark datasets, the study analyses each algorithm's ability to approximate the optimal solutions for both problems. In the case of TSP, ACO demonstrates superior performance by effectively mimicking ant foraging behaviour to navigate complex routes, albeit with a slightly higher time consumption. GA shows moderate effectiveness, balancing resource usage with solution quality, while PSO lacks in performance, particularly challenged by the intricacies of TSP. Conversely, for the 0/1 Knapsack Problem, the performance gap narrows, with ACO still leading in efficiency and accuracy, closely followed by PSO, which shows a significant improvement over its TSP application. GA maintains a consistent performance, proving its robustness in finding near-optimal solutions with reasonable resource utilisation. This research contributes to the field by providing an updated and comprehensive comparison of these algorithms, enhancing the understanding of their strengths, weaknesses, and applicability. The findings highlight the necessity of algorithm selection based on specific problem characteristics and suggest potential areas for future research, including hybrid models and further algorithmic refinements for diverse applications. The study serves as a valuable reference for selecting appropriate optimisation techniques in various practical scenarios, contributing significantly to the optimisation and machine learning fields.