Supercolony: A Novel Ant Colony Optimization Algorithm for Solving the Traveling Salesman Problem

Overview

Objectives/Goals This study seeks to create a novel algorithm for producing superior solutions to the Traveling Salesman Problem by innovating upon Ant Colony Optimization techniques. A novel Ant Colony Optimization algorithm is developed that uses multiple, unique colonies in combination in order to produce superior solutions. It was hypothesized that the novel algorithm, "Multi-Colony System" (MCS), would perform 5% better than the "standard" ACO algorithm, Ant Colony System (ACS), at easy, moderate, and difficult TSP instances. Methods/Materials A quad-core Intel i5-3450 computer with 8 GB RAM was used for programming and running the experiment. Two variants of the novel algorithm, MCS, were coded by the researcher in Java; the researcher also implemented ACS for comparison purposes. MCS uses multiple colonies based on ACS with differing parameters to focus on exploration or exploitation. Each algorithm was run 10 times for 5040 seconds against TSP instances eil101, d198, pcb442, and pr1002. Results With the "easier" instances eil101 and d198, the two algorithms performed very similarly, with little difference in the mean tour lengths achieved by the algorithms. However, in the 442-city instance and 1002-city instance, the two variants of MCS outperformed ACS significantly, with Symmetric MCS outperforming ACS by as much as 20% in terms of mean tour length. Conclusions/Discussion ACS and MCS were comparable at "easier" instances with fewer cities, but MCS was a significant improvement when tested with the larger TSP instances of the study. More cities result in a greater number of possible solutions, which can increase the number of local maxima in the search space and thus the advantage MCS holds over ACS: diversity of tours. By pursuing multiple solutions at once, MCS can more efficiently avoid converging prematurely and search the solution space more quickly.

Competition history

• CSEF 2014 Mathematics & Software · Entry S1430

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2014 project