A Coordenação do Programa de Pós-Graduação em Modelagem Matemática e Computacional tem o prazer de convidar a comunidade científica para a 252ª sessão pública de apresentação e defesa da dissertação de Mestrado:
CANDIDATO: AUGUSTO FLÁVIO MORAIS SANTOS
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. |