Incorporating Labor Division into Ant Colony Optimization

Abstract

Ant colony optimization (ACO) is a constructivistic and population-based metaheuristic for solving combinatorial optimization problems inspired by how real ants use pheromones to find shortest paths. Like other metaheuristics ACO is prone to converge on local optima, also known as stagnation. Inspired by the collective behavior of real ants, this thesis incorporated labor division into ACO in order to avoid stagnation. Since there was little research that concern utilizing labor division in ACO, two original attempts at merging labor division models from biological science with ACO was performed. The two chosen labor division models were the seemingly popular Fixed-Threshold model and the Self-Reinforcement model.

The two resulting algorithms were applied to the minimum-cost flow problem domain with concave costs functions, which is a NP-hard problem. Max-Min Ant System, also an ACO algorithm, had previously been applied to concave minimum-cost flow problems and achieved good results. The performance and search behavior of the two proposed labor division algorithms were therefore compared to Max-Min Ant System on a set of 300 flow networks. The results indicated that both labor division algorithms performed comparable to Max-Min Ant System and avoided stagnation very well.