A new ant colony optimization model for complex graph-based problems

Resumo

Nowadays, there is a huge number of problems that due to their complexity have employed heuristic-based algorithms to search for near-to-optimal (or even optimal) solutions. These problems are usually NP-complete, so classical algorithms are not the best candidates to address these problems because they need a large amount of computational resources, or they simply cannot find any solution when the problem grows. Some classical examples of these kind of problems are the Travelling Salesman Problem (TSP) or the N-Queens problem. It is also possible to find examples in real and industrial domains related to the optimization of complex problems, like planning, scheduling, Vehicle Routing Problems (VRP), WiFi network Design Problem (WiFiDP) or behavioral pattern identification, among others. This thesis has been focused on the analysis of classical graph-based representations and its application in ACO algorithms into complex problems, and the development of a new ACO model that tries to take a step forward in this kind of algorithms. A complete empirical study of these algorithms (one of the Swarm Intelligence algorithms), and its comparison against other ¿population based¿ algorithms, such as Genetic Algorithms (GA) and Coral Reef Optimization (CRO) algorithm has been carried out. In this new model, the problem is represented using a reduced graph that affects to the ants behavior, which becomes more complex. Also, this size reduction generates a fast growth in the number of pheromones created. For this reason, a new metaheuristic (called Oblivion Rate) has been designed to control the number of pheromones stored in the graph. Both the theoretical model and the metaheursitcs designed have been experimentally validated in several domains (Constraint-Satisfaction Problems, video games, RCPSP, classical problems like N-Queens, etc.).