my picture

Anthony Awuley Machine Learning and Software Engineer

12 Mar

A Comparative Study of Ant Colony Optimization and Genetic Algorithms on a TSP


Population-based stochastic search algorithms have been applied on several NP-hard combinatorial problems. Due to their parallel nature, multiple solutions are evolved at the same time. Such evolutionary algorithms have their strengths in different problem areas thus the “no free launch” theory holds for algorithms in this domain. This work seeks to compare performance of a swarm intelligence algorithm (Ant Colony Optimization (ACO)) and a Genetic Algorithm on a Traveling Salesman Problem (TSP). It was discovered that, ACO produced better results within a shorter time frame as opposed to GA. GA performed best for datasets with minimal number of nodes however needed more generations to produce results that are competitive to ACO for larger datasets. Statistical test (t-test) for the observed difference is significant at 90% confidence level and insignificant at 95% confidence level.

Entire system was developed in java See https://www.github.com/aawuley/evolutionary-computation

Leave a Comment