Made available in DSpace on 2014-12-17T15:48:07Z (GMT). No. of bitstreams: 1
RomeritoCA_DISSERT.pdf: 1649773 bytes, checksum: 9a9fd0e3782657fe6d014020cdc8fb90 (MD5)
Previous issue date: 2013-02-01 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / 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 / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/18078 |
| Date | 01 February 2013 |
| Creators | Andrade, Romerito Campos de |
| Contributors | CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Thom?, Ant?nio Carlos Gay, CPF:23336048753, http://lattes.cnpq.br/9282046098909851, Gouv?a, Elizabeth Ferreira, CPF:81652011749, http://lattes.cnpq.br/2888641121265608, Goldbarg, Marco C?sar |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Sistemas e Computa??o, UFRN, BR, Ci?ncia da Computa??o |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds