Hybridization of population -based ant colony optimization via data mining />

Abstract

We propose a hybrid application of Population Based Ant Colony Optimization that uses a data mining procedure to wisely initialize the pheromone entries. Hybridization of metaheuristics with data mining techniques has been studied by several researchers in recent years. In this line of research, frequent patterns in a number of initial high-quality solutions are extracted to guide the subsequent iterations of an algorithm, which results in an improvement in solution quality and computational time. Our proposal possesses certain differences from and contributions to existing literature. Instead of one single run that incorporates both the main metaheuristic and the data mining module inside, we propose to carry out independent runs and collect elite sets over these trials. Another contribution is the way we use the knowledge gained from the application of the data mining module. The extracted knowledge is used to initialize the memory model in the algorithm rather than to construct new initial solutions. One additional contribution is the use of a path mining algorithm (a specific sequence mining algorithm) rather than Apriori-like association mining algorithms. Computational experiments, conducted both on symmetric Travelling Salesman Problem and symmetric/asymmetric Quadratic Assignment Problem instances, showed that our proposal produces significantly better results, and is more robust than pure applications of population-based ant colony optimization.