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.

I. Introduction

Genetic Algorithm, Ant Colony Optimisation and Particle Swarm Optimisation algorithms are widely used in Machine learning to address Optimisation problems such as hyper-parameter tuning, feature selection, training neural nets and others. These algorithms identify the optimal solution from a set of all feasible solutions. Metaheuristic algorithms are the answer to solving optimisation problems. They are algorithms that specialise in finding the best possible solution in an appropriate time frame. This is done by applying various heuristic techniques. Heuristic is the finding of a solution through trial and error or discovering something on its own. These are algorithms that can solve a problem without knowing the nature of the problem, by finding the solution themselves. They do this by guiding the search process using general strategies and principles that they can apply across various sets of problems. This involves a random iterative search process where solutions are generated, evaluated, and modified based on specific benchmarks. Another characteristic of metaheuris-tic algorithms is that they can escape a local optimum when solving a problem. This means that they can jump through search spaces to find a better solution. The outright advantage of metaheuristic algorithms is that they can solve NP-hard optimisation problems through their self-exploration.