CONVITE PARA DEFESA DE DISSERTAÇÃO

TÍTULO:

“Algoritmos heurísticos para a solução do Problema da Cadeia de Caracteres Mais Próxima”

TITULARES:

Prof. Dr. Marcone Jamilson Freitas Souza

UFOP

Prof. Dr. Sérgio Ricardo de Souza

CEFET-MG

Prof. Dr. Vitor Nazário Coelho

UFF

Profª. Drª. Elisângela Martins de Sá

CEFET-MG

LOCAL:

Prédio anexo à Biblioteca, Sala 'B', Campus II, CEFET-MG

Av. Amazonas, 7675 - Nova Gameleira

DIA:

13 de agosto de 2018 - Segunda-feira

HORA:

14 horas

RESUMO: O presente trabalho tem seu foco no Problema da Cadeia de Caracteres Mais Próxima (PCCP) – Closest String Problem (CSP). O objetivo deste problema é o de encontrar uma sequência de caracteres que mais se aproxime, segundo uma dada métrica, de um conjunto de cadeias de caracteres de mesma dimensão. Sendo o CSP da classe NP-difícil, justifica-se a utilização de métodos heurísticos para solucioná-lo. Propõe-se a implementação de três metaheurísticas, a saber: Simulated Annealing (SA), Variable Neighborhood Search (VNS) e Discrete Particle Swarm Optimization (DPSO). Todos os métodos foram implementados com características híbridas, combinados com um método de busca local, que é aplicado cada vez que é atualizada a melhor solução corrente. Para testá-los, foram utilizados conjuntos de problemas-teste amplamente usados na literatura. Os experimentos computacionais realizados indicaram que o método híbrido Hybrid Discrete Particle Swarm Optimization for Closest String Problem (HDPSO CSP ) obteve bom desempenho e, em alguns casos, chegou a encontrar as soluções ótimas.

Palavras-Chave: Problema da Cadeia de Caracteres Mais Próxima. Simulated Annealing. Variable Neighborhood Search. Particle Swarm Optimization. Busca Local.