Seminário de Teoria da Computação

               Defesa de Mestrado

    Algoritmos Genéticos para o Problema de 
   Localização de Recursos em Rede Telefônica  

             Silvana Livramento

       Sexta-feira, 21 de maio de 2004
            Sala 301 às 16:00hs (NOTEM A MUDANÇA)


Desenvolvemos Algoritmos Genéticos (AGs) para resolver problemas
no projeto de redes de telecomunicações. Um problema consiste em
particionar uma grande área de projeto urbana em pequenas seções
de serviços, as quais são controladas por um único equipamento de
comunicação. O AG desenvolvido para este problema incorpora
informações geométricas e topológicas da área de projeto operando
diretamente com uma malha de pontos de demanda geograficamente
dispersos.  Dada uma seção de serviço, a outra fase deste projeto,
consiste em agrupar os pontos de demanda em grupos pequenos e
posicionar outros equipamentos em postes da rede elétrica, para
fazer a comunicação entre estes grupos e o equipamento de
comunicação da seção de serviço. Outro AG foi desenvolvido para
este problema, e também incorpora informações geométricas e
topológicas, pois trabalha diretamente sobre o grafo de vizinhança
dos postes existentes numa seção de serviço e a ligação destes com
os pontos de demanda. Os resultados computacionais mostraram que
os dois AGs são técnicas promissoras para projetar uma rede de
telecomunicações, obtendo resultados favoráveis em tempo
computacional razoável. Todos os testes foram realizados com
instâncias reais tomadas de grandes áreas da cidade de São Paulo.