Comparative Analysis of Ant Colony Optimization and Genetic Algorithm in Solving the Traveling Salesman Problem

Abstract: Metaheuristics is a term for optimization procedures/algorithms that can be applied to a wide range of problems. These problems for which metaheuristics are used usually fall in the NP-hard category, meaning that they cannot be solved in polynomial time. This means that as the input dataset gets larger the time to solve increases exponentially. One such problem is the traveling salesman problem (TSP) which is and has been widely used as a benchmark problem to test optimization algorithms. This study focused on two such algorithms called ant colony optimization (ACO) and genetic algorithm (GA) respectively. Development of such optimization algorithms can have huge implications in several areas of business and industry. They can for example be used by delivery companies to optimize routing of delivery vehicles as well as in material science/industry where they can be used to calculate the most optimal mix of ingredients to produce materials with the desired characteristics. The approach taken in this study was to compare the performance of the two algorithms in three different programming languages (python, javascript and C#).  Previous studies comparing the two algorithms have reported conflicting results where some studies found that ACO yielded better results but was slower than GA, while others found that GA yielded better results than ACO. Results of this study suggested that both ACO and GA could find the benchmark solution, but  ACO did so much more consistently. Furthermore javascript was found to be the most efficient language with which to run the algorithms in the setup used in this study.