Multicast packing problem: abordagem multiobjetivo

This work presents a algorithmic study of Multicast Packing Problem considering a multiobjective approach. The first step realized was an extensive review about the problem. This review serverd as a reference point for the definition of the multiobjective mathematical model. Then, the instances used in the experimentation process were defined, this instances were created based on the main caracteristics from literature. Since both mathematical model and the instances were definined, then several algoritms were created. The algorithms were based on the classical approaches to multiobjective optimization: NSGA2 (3 versions), SPEA2 (3 versions). In addition, the GRASP procedures were adapted to work with multiples objectives, two vesions were created. These algorithms were composed by three recombination operators(C1, C2 e C3), two operator for build solution, a mutation operator and a local search procedure. Finally, a long experimentation process was performed. This process has three stages: the first consisted of adjusting the parameters; the second was perfomed to indentify the best version for each algorithm. After, the best versions for each algorithm were compared in order to identify the best algorithm among all. The algorithms were evaluated based on quality indicators and Hypervolume Multiplicative Epsilon

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

O presente trabalho apresenta um estudo algorítmico do Multicast Packing Problem levando em consideração uma abordagem multiobjetivo. Para tal, faz-se uma extensa revisão sobre o problema em questão. Esta revisão serviu como ponto de referência para definição de um modelo matemático multiobjetivo, tendo em vista que não há na literatura nenhum trabalho que tenha tratado o tema neste aspecto. Em seguida, define-se os casos de teste utilizados no processo de experimentação dos algoritmos. Uma vez que tanto modelo matemático multiobjetivo quanto os casos de teste foram criados, então desenvolve-se vários algoritmos com base nas abordagens clássicas para problemas de otimização multiobjetivo: NSGA2 (3 versões) e SPEA2 (3 versões). Além disso, adaptou-se a metaheurística GRASP (2 versões) para aplicação considerando o modelo proposto. Estes algoritmos foram compostos por três operadores de recombinação (C1, C2, C3), dois operadores de construção de solução, um operador de mutação e um operador de busca local. Por fim, um extenso processo de experimentação dos algoritmos é realizado. Este processo possui três etapas: a primeira etapa consistiu de ajustar os parâmetros que cada algoritmo necessita, neste caso o ajuste de parâmetro foi realizado para todas as versões do SPEA2, NSGA2 e GRASP; A segunda etapa consistiu de verificar, para cada algoritmo, qual a melhor versão. Por fim, as melhores versões de cada algoritmo, no total 3 versões, foram comparadas entre si visando identificar qual o melhor algoritmo dentre todos. Os algoritmos foram avaliados com base nos indicadores de qualidade Hypervolume e Epsilon Multiplicativo. Os resultados dos experimentos foram avaliados através de testes estatísticos não-paramétricos (teste de Mann-Whitney e teste de Friedman). A avaliação dos resultados foi favoráravel ao NSGA2-C2 segundo a metodologia de avaliação utilizada