CCE Theses and Dissertations
Date of Award
2021
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
College of Computing and Engineering
Advisor
Sumitra Mukherjee
Committee Member
Michael J. Laszlo
Committee Member
Francisco J. Mitropoulos
Keywords
ant colony optimization, ant system, sparse array, traveling salesman problem
Abstract
In search guided by meta-heuristics, a fundamental tradeoff exists between exploitation of good solutions (intensification) and exploration of the solution space for better solutions (diversification). Over-exploitation can limit the search to suboptimal solutions while over-exploration can reduce the efficiency of the overall search. Ant Colony Optimization (ACO) is a well-known meta-heuristic inspired by biological ants for solving NP-hard combinatorial search problems like the Traveling Salesman Problem (TSP). In nature, biological ant colonies navigate to find efficient paths around complex obstacles by depositing and following simple chemicals called pheromones. ACO algorithms model this behavior by implementing sets of artificial ants which iteratively explore a solution space, marking high quality solutions with “pheromone” values and biasing subsequent searches toward those values. TSP serves as a benchmark for evaluating ACO algorithms. Current implementations of ACO algorithms require the storage of distances and pheromone levels between all pairs of vertices.
This dissertation presents a variant that has significantly lower storage requirements, thus rendering it practical for use on larger problem instances. The tradeoff between memory use and solution quality is empirically investigated using benchmark TSP problem instances. MAX-MIN Ant System, one of the best available ACO variants, serves as a baseline method for comparison. The variant of ACO algorithm proposed in this dissertation provides memory savings in terms of both distances stored and pheromone levels stored. Instead of maintaining distances between all pairs of vertices, distances between each vertex its k nearest neighbors are maintained; k is chosen to be much smaller than the number of vertices in the graph. An efficient approximate algorithm is used to identify nearest neighbors. Observing that pheromone values between most pairs of vertices lie within a narrow range in an iteration, the ACO variant proposed in this study specifies a default pheromone value and uses a sparse matrix that only maintains values between a pair of vertices if it differs from the default value by more than a specified tolerance limit; the default pheromone level is updated in each iteration. The memory requirement for pheromone storage thus decreases with increasing tolerance limit, potentially at the cost of solution quality.
Experimental results on benchmark TSP instances indicate that with a judicious choice of tolerance level, the proposed approach consistently achieves solution quality that is comparable to those obtained by a MAX-MIN Ant System while using a fraction of the memory. Specifically, experimental ACO solution quality reached ranged between 10% and 25% of the standard solution quality and in the two of the largest TSP instances exceeded standard solution quality by 6% and 8%. Experimental memory usage showed a 95% to 99% reduction in required memory over the standard ACO algorithm.
NSUWorks Citation
Douglas Hale. 2021. Investigation of Ant Colony Optimization Implementation Strategies For Low-Memory Operating Environments. Doctoral dissertation. Nova Southeastern University. Retrieved from NSUWorks, College of Computing and Engineering. (1151)
https://nsuworks.nova.edu/gscis_etd/1151.