LANS Informal Seminar: Sabrina Oliveira

Seminar Title: The improvement and analysis of ACO algorithms for the DTSP by the use of different pheromone restructuring procedures and local searches
Speaker: Sabrina Oliveira , Capes Ph.D. fellow at IRIDIA, Universite Libre de Bruxelles, Belgium

Date/Time: 2012-05-02 15:00
Location: Building 240, 1404-1405

Description:
Ant Colony Optimization (ACO) is a metaheuristic inspired by the foraging behavior of real ants, proposed to tackle NP-hard combinatorial optimization problems (COPs). An ACO algorithm can be defined by the interplay of two main procedures. The first is construction, which manages a colony of ants to incrementally build solutions. The second is the pheromone update, the process by which the pheromone information is modified in order to guide the ants towards better solutions. Over the years, ACO algorithms have been successfully improved by the application of different ways to update the pheromone. However, when ACO is applied to dynamic COPs, additional modifications are necessary. As an example of dynamic COP, we use the dynamic traveling salesman problem (DTSP), where customers are replaced by new ones during the execution of the algorithm. In such a case, the pheromone information may not make sense from one change to another. Thus, after every change, a restructuring procedure should be adopted to adapt the pheromone information. Few proposals for such procedures be found in the literature and has not been a systematic evaluation of their impact on the algorithms’ performance. In this work, we introduce different ways to restructure the pheromone information and compare them with those that have been already proposed in the literature. We also investigate the impact of using different local searches to enhance algorithms’ performance. Finally, we propose a simple and uniform way to evaluate the algorithm’s solution quality. In our experiments, we analyzed the effects that different restructuring procedures and local searches have on different ACO algorithms. Furthermore, we defined an ACO algorithm that performs better than previous algorithms tested.