Banca de QUALIFICAÇÃO: EDISON LUIZ BONOTTO

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE: EDISON LUIZ BONOTTO
DATA: 01/07/2016
HORA: 14:00
LOCAL: Auditório do CI
TÍTULO: Otimização por Nuvem de Partículas e Busca Tabu para oProblema da Diversidade Máxima
PALAVRAS-CHAVES: Análise Combinatória, Problema da Diversidade Máxima (MDP),Otimização por Nuvem de Partículas (PSO), Busca Tabu (TS)
PÁGINAS: 47
RESUMO: O Problema da Diversidade Máxima (MDP) é um problema da área de Otimização Combinatória que tem por objetivo selecionar um número pré-estabelecido de elementos de um dado conjunto de maneira tal que a soma das diversidades entre os elementos selecionados seja a maior possível. O MDP pertence a classe de problemas NP-difícil, isto é, não existe algoritmo conhecido que o resolva de forma exata em tempo polinomial. Por apresentarem uma complexidade de ordem exponencial, exigem heurísticas eficientes que forneçam resultados satisfatórios em tempos aceitáveis.Entretanto, as heurísticas não garantem a melhor solução. A abordagem Otimização por Nuvem de Partículas (PSO) simula o comportamento de um bando de pássaros em voo com seu movimento localmente aleatório, mas globalmente determinado, para encontrar máximos locais. No PSO, cada partícula inicia um voo aleatório e a cada iteração o voo é ajustado de acordo com a sua própria experiência e da experiência de todas as outras partículas. Já, a meta-heurística Busca Tabu (TS) é um procedimento adaptativo auxiliar que utiliza uma estrutura de memória para armazenar as soluções geradas, ou características destas, e guiar um algoritmo de busca local na exploração contínua dentro de um espaço de busca. A partir de uma solução inicial, move-sede uma solução para outra vizinha, até que se satisfaça um determinado critério deparada. Este trabalho propõe uma nova abordagem para a resolução do Problema da Diversidade Máxima e esta baseada nas meta-heurísticas de Otimização por Nuvem de Partículas e Busca Tabu. Para a geração das partículas iniciais utilizadas pelo PSO implementaremos uma heurística de construção gulosa e outra aleatória. O algoritmo foi denominado PSO_TS. Para a validação do método, os resultados encontrados são comparados com os melhores existentes na literatura.
MEMBROS DA BANCA:
Presidente - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Interno - 1859144 - ANAND SUBRAMANIAN
Interno - 337293 - ROBERTO QUIRINO DO NASCIMENTO