Seminário de Teoria da Computação


                   Busca Tabu Probabilística para
                Projeto de Redes de Telecomunicações

                       Nilton S. Volpato Filho

         Sexta-feira, 25 de outubro de 2002, Sala 96  13:00hs


Iremos apresentar resultados do estudo de Jiefeng Xu, Steve Y. Chiu, e
Fred  Glover  sobre um  problema  de projeto  de  redes  que surge  na
indústria  de telecomunicações.  O  objetivo pode  ser formulado  como
encontrar uma  árvore de  Steiner de grau  restrito em um  grafo cujos
vértices  e  arestas  têm  custos  atribuídos.  Foi  desenvolvido  uma
heurística de Busca Tabu  probabilística para esse problema envolvendo
assuntos como  avaliações dos movimentos, correção  de erros, memórias
tabu,   estratégias  de   listas  de   candidatos  e   estratégias  de
intensificação  baseadas  em  recuperação  de soluções  de  elite.  Os
resultados  computacionais para  um conjunto  de testes  de instâncias
difíceis para o  problema mostram que a nova  heurística gera soluções
ótimas  para  todos  os  problemas  que  puderam  ser  resolvidos  por
algoritmos exatos,  enquanto foi requerida somente um  fração do tempo
da solução.  Além disso, para  problemas maiores e mais  realistas, os
quais  os  métodos  exatos  foram incapazes  de  resolver,  resultados
computacionais  mostram  que esse  método  também  supera as  melhores
heurísticas de busca local atualmente disponíveis.