Heurísticas e algoritmos evolutivos para formulações mono e multiobjetivo do problema do roteamento multicast

Abstract

In this work, we investigate evolutionary models applied to the Multicast Routing Problem (MRP), in which we want to calculate multicast trees from a connected weighted graph, optimizing one or more objective functions related to Quality of Service and Trac Engineering requirements. MRP can be seen as an extension of the well-known Steiner Tree Problem, which is in the NP-hard class of problems. Thus, starting from models based on Canonical and Multiobjective Genetic Algorithms from the literature, we propose three heuristics to be used in crossover and mutation operators of the resultant evolutionary model, which are based on more determinists strategies (using Dijkstra's algorithm), more random ones or a combination of these. The usage of such heuristic occurs in a crossover/mutation phase known as subtrees reconnection, which guides the generation of new solutions combining common parts of parents and new parts added by such reconnection algorithm. MRP was considered under several formulations (one mono-objective and seven multiobjective ones under Pareto dominance), aiming to achieve a comprehensive experimental evaluation of the proposed methods. Three well-known algorithms (NSGA-II, SPEA and SPEA2) were used as underlying search mechanism, in which two variations of a mating selection of parents based on neighborhood (Neighborhood Crossover) were also evaluated. From a set of eight instances taken from Routing and Steiner problems literature, the experimental results indicated that besides xing a heuristic that could potentially generate invalid individuals, the new heuristics returned good results in the considered convergence and diversity metrics. More specically, the combined heuristic provided the best results in most cases, showing that the strategy of combining a shortest path with randomness along the reconnections was benecial. The use of Neighborhood Crossover, in turn, was more noticeable on the MRP formulation in which the network instances had larger Pareto-optimal sets. Statistical signicance tests were performed, supporting the evidences showed by punctual and interval estimations.