Banca de DEFESA: EDISON LUIZ BONOTTO

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: EDISON LUIZ BONOTTO
DATA: 31/01/2017
HORA: 14:30
LOCAL: Auditório do CI
TÍTULO: Otimização por Nuvem de Partículas e Busca Tabu para o Problema 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
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Matemática da Computação
RESUMO: O Problema da Diversidade Maxima (MDP) e um problema da area de Otimizacao Combinatoria que tem por objetivo selecionar um numero pre-estabelecido de elementos de um dado conjunto de maneira tal que a soma das diversidades entre os elementos selecionados seja a maior possivel. O MDP pertence a classe de problemas NP-dificil, isto e, nao existe algoritmo conhecido que o resolva de forma exata em tempo polinomial. Por apresentarem uma complexidade de ordem exponencial, exigem heuristicas eficientes que fornecam resultados satisfatorios em tempos aceitaveis.Entretanto, as heuristicas nao garantem a melhor solucao. A abordagem Otimizacao por Nuvem de Particulas (PSO) simula o comportamento de um bando de passaros em voo com seu movimento localmente aleatorio, mas globalmente determinado, para encontrar maximos locais. No PSO, cada particula inicia um voo aleatorio e a cada iteracao o voo e ajustado de acordo com a sua propria experiencia e da experiencia de todas as outras particulas. Ja, a meta-heuristica Busca Tabu (TS) e um procedimento adaptativo auxiliar que utiliza uma estrutura de memoria para armazenar as solucoes geradas, ou caracteristicas destas, e guiar um algoritmo de busca local na exploracao continua dentro de um espaco de busca. A partir de uma solucao inicial, move-sede uma solucao para outra vizinha, ate que se satisfaca um determinado criterio deparada. Este trabalho propoe uma nova abordagem para a resolucao do Problema da Diversidade Maxima e esta baseada nas meta-heuristicas de Otimizacao por Nuvem de Particulas e Busca Tabu. Para a geracao das particulas iniciais utilizadas pelo PSO implementaremos uma heuristica de construcao gulosa e outra aleatoria. O algoritmo foi denominado PSO_TS. Para a validacao do metodo, os resultados encontrados sao comparados com os melhores existentes na literatura.
MEMBROS DA BANCA:
Presidente - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Interno - 1859144 - ANAND SUBRAMANIAN
Externo ao Programa - 337293 - ROBERTO QUIRINO DO NASCIMENTO
Externo à Instituição - MARCELO LISBOA ROCHA