PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA (PPGI)

UNIVERSIDADE FEDERAL DA PARAÍBA

Telefone/Ramal
Não informado

Notícias


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: 10:00
LOCAL: Auditório do CCEN
TÍTULO:

GRASP COM ALGORITMOS HÍBRIDOS APLICADO
AO PROBLEMA DA ÁRVORE GERADORA DE
CUSTO MÍNIMO CAPACITADA EM NÍVEIS
GRASP COM ALGORITMOS HÍBRIDOS APLICADOAO PROBLEMA DA ÁRVORE GERADORA DECUSTO MÍNIMO CAPACITADA EM NÍVEIS


PALAVRAS-CHAVES:

Metaheurística, GRASP, Projeto de redes, Árvore
geradora de custo mínimo capacitada em níveis.
Metaheurística, GRASP, Projeto de redes, Árvoregeradora de custo mínimo capacitada em níveis.


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:
Interno - 1545175 - IGUATEMI EDUARDO DA FONSECA
Presidente - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Externo à Instituição - MARCONE JAMILSON FREITAS SOUZA - UFOP