TJHSST Senior Research Project Proposal: Ant Colony Optimization 2006-2007
Ryan Ward November 3, 2006

1

Problem Statement

Ant Colony Optimization (ACO) is an algorithm that is used to find nearoptimal solutions to NP problems. This research aims to study the differences in strengths and weaknesses between various implementations of ACO (as applied to the Traveling Salesman Problem), suggest or conduct development into improving performance of ACO algorithms, and study the general application of ACO algorithms to the Traveling Salesman Problem.

2

Purpose

The main subjects of this research are the various implementations of the ACO algorithm. The algorithms are inspired by the natural system ants use to develop short paths between their colony and a food source. The implementations have subtle differences that change how quickly the algorithm runs or how close the solution found is to the optimal. The Traveling Salesman Problem (TSP) is: given a graph, find the quickest tour that visits all the nodes once. TSP is a well-studied NP-hard problem used as a standard to compare different approximation algorithms. TSP problems (or similar NP-hard problems) occur in industry and computing, so any information on improving the application of ACO algorithms to TSP problems is useful.

1

3

Scope of Study

This research only focuses on the application of ACO algorithms to TSP problems. The different algorithms to be studied include: Ant System (AS), Ant System Elitist (AS-E), Ant System Local Best Tour (AS-LBT), and MinMax Ant System (MinMax). This list can be expanded or contracted depending on time. Analysis of these different implementations of ACO will either lead to a direct improvement or suggested area or research for improvement of ACO algorithms. Different TSP problems can be tested as well depending on time, including on-line TSP and asymmetric TSP problems.

4

Background

The ACO algorithm was initially proposed in 1992 and accepted as a well defined metaheuristic in 1999. Since then ACO has been used to find nearoptimal solutions to multiple problems. Most of the research being done in the field currently either studies the appropriate variables to use for the different implementations or develops new implementations. TSP is currently studied as a test problem for approximation algorithms.

5
5.1

Procedure and Methodology
Plan and Resources

The time line for this research is to have a basic environment representing the TSP problem and the AS algorithm completed first quarter, create different implementations and compare them second quarter, and either suggest possible improvements or improve on the different implementations third quarter. This research will be coded in Java due to the programmer's familiarity with the language.

5.2

Outputs and Testing

The expected output for a running program is a near optimal solution to a given TSP problem. TSP problems with known solutions will be used in testing. Criteria for the implementations includes: how well the algorithm

2

is exploring the graph (standard deviation size in routes), how fast the algorithm is finding solutions (iteration time), and how good are the solutions found (difference between optimal route and solution route). Graphs can be made comparing different implementations based on these criteria. Aspects of the algorithm can be explained mathematically.

6

Expected Result and Value to Others

The expected result from this research is an insight on how to improve ACO algorithms based on viewing the strengths and weaknesses of the current different implementations. Improvements to the ACO algorithm are valued in any field encountering optimization problems.

3