Banca de DEFESA: RENNAN NUNES TOSCANO
Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: RENNAN NUNES TOSCANO
DATA: 11/05/2012
HORA: 09:00
LOCAL: Auditório do CCEN
TÍTULO: GRASP COM ALGORITMOS HIBRIDOS APLICADOAO PROBLEMA DA ARVORE GERADORA DE CUSTO MINIMO CAPACITADA EM NIVEIS
PALAVRAS-CHAVES: Metaheuristica, GRASP, Projeto de redes, Arvore
PÁGINAS: 80
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Matemática da Computação
RESUMO:
Apresenta-se, nesta tese, um algoritmo híbrido, baseado na metaheurística
Greedy Randomized Adaptive Search (GRASP), para obter soluções
melhores e reduzir o custo computacional para o problema conhecido
como o Problema da Árvore Geradora de Custo Mínimo Capacitada
em Níveis (PAGCMCN). Este problema, normalmente encontrado ao
se projetar uma rede, consiste em determinar a melhor maneira de se
conectar vários terminais a um computador central, de forma a atender
suas demandas. As conexões podem envolver diferentes tipos de
linhas de transmissão, onde cada tipo possui uma capacidade máxima
de transmissão distinta. No algoritmo proposto, o otimizador CPLEX
12.2 é acionado, tanto na fase de construção quanto na de busca local,
com vistas a uma exploração mais efetiva do espaço de busca. Os
experimentos computacionais mostraram que o algoritmo proposto é
bastante competitivo, superando em várias instâncias os resultados da
literatura e obtendo resultados muito próximos nas demais.
Apresenta-se, nesta tese, um algoritmo híbrido, baseado na metaheurísticaGreedy Randomized Adaptive Search (GRASP), para obter soluçõesmelhores e reduzir o custo computacional para o problema conhecidocomo o Problema da Árvore Geradora de Custo Mínimo Capacitadaem Níveis (PAGCMCN). Este problema, normalmente encontrado aose projetar uma rede, consiste em determinar a melhor maneira de seconectar vários terminais a um computador central, de forma a atendersuas demandas. As conexões podem envolver diferentes tipos delinhas de transmissão, onde cada tipo possui uma capacidade máximade transmissão distinta. No algoritmo proposto, o otimizador CPLEX12.2 é acionado, tanto na fase de construção quanto na de busca local,com vistas a uma exploração mais efetiva do espaço de busca. Osexperimentos computacionais mostraram que o algoritmo proposto ébastante competitivo, superando em várias instâncias os resultados daliteratura e obtendo resultados muito próximos nas demais.
MEMBROS DA BANCA:
Presidente - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Interno - 1545175 - IGUATEMI EDUARDO DA FONSECA
Externo à Instituição - MARCONE JAMILSON FREITAS SOUZA - UFOP