Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/325550
Type: TESE DIGITAL
Title: Meta-heurísticas GRASP e BRKGA aplicadas ao problema da diversidade máxima
Title Alternative: GRASP and BRKGA metaheuristics applied to the maximum diversity problem
Author: Moro, Marcel Alves, 1992-
Advisor: Ruggiero, Márcia Aparecida Gomes, 1956-
Abstract: Resumo: Neste trabalho estudamos o Problema da Diversidade Máxima (PDM), que consiste em selecionar entre um conjunto de elementos, um subconjunto que seja o mais diverso possível. O problema é classificado como NP-difícil. Apresentamos as formulações quadrática e a linear inteira mista, aplicações e exemplo numérico. Resolvemos problemas pequenos de maneira exata e notamos que para problemas maiores é necessário o uso de heurísticas ou meta-heurísticas em sua resolução. Sendo assim, escolhemos as meta-heurísticas Greedy Randomized Adaptive Search Procedure (GRASP) e Biased Random-Key Genetic Algorithm (BRKGA) para serem aplicadas ao PDM. No GRASP, adotamos uma construção de solução selecionando o elemento de acordo com a correspondente contribuição do mesmo ao valor da função objetivo. Após a construção de cada solução, aplicamos uma busca local e em seguida acionamos a técnica path relinking. No procedimento de busca local, empregamos uma busca do tipo exaustiva, realizando a melhor troca entre um elemento pertencente a solução e outro não pertencente. Geradas as soluções, aplicamos o path relinking na expectativa que entre cada par de soluções, exista uma solução com melhor valor para a função objetivo. Já no BRKGA, implementamos uma função fitness e um decodificador de soluções adaptados ao Problema da Diversidade Máxima. A função fitness adotada é a soma das diversidades entre os elementos selecionados e a decodificação de soluções é baseada na ordenação das chaves aleatórias. O objetivo deste trabalho é analisar e comparar os resultados obtidos pelas meta-heurísticas GRASP e BRKGA, tendo como referência os melhores resultados da literatura. Os problemas analisados nos testes computacionais foram extraídos da biblioteca MDPLIB. Observamos que as duas meta-heurísticas apresentam bons resultados na resolução do PDM, sendo que para problemas de pequeno e médio porte BRKGA obteve melhor desempenho que GRASP, enquanto que para problemas de grande porte, GRASP supera o desempenho do BRKGA

Abstract: In this work we study the Maximum Diversity Problem (MDP), which consists of selecting among a set of elements, a subset as diverse as possible. The problem is classified as NP-hard. We present the quadratic and mixed integer linear formulations, applications and numerical example. We solve small problems exactly and we note that for larger problems it is necessary to use heuristics or metaheuristics on its resolution. Therefore, we chose Greedy Randomized Adaptive Search Procedure (GRASP) and Biased Random-Key Genetic Algorithm (BRKGA) metaheuristics to be applied to the MDP. In GRASP, we adopted a solution construction by selecting the element according to its corresponding contribution to the objective function value. After the construction of each solution, we apply a local search and then we activate the path relinking technique. In the local search procedure, we used a exhaustive search, making the best exchange between an element which belongs to solution and another element that does not belong. Once the solutions were generated, we apply path relinking in the expectation that between each pair of solutions, there is a solution with better objective function value. In BRKGA, we implemented a fitness function and a solution decoder adapted to the Maximum Diversity Problem. The fitness function adopted is the sum of diversities between selected elements e the decoding of solutions is based on sorting random-keys. The objective of this work is to analyze and compare the results obtained by GRASP and BRKGA metaheuristics, having as reference the best results in the literature. The problems analyzed in the computational tests were extracted from the MDPLIB library. We observed that the two metaheuristics showed good results on MDP's resolution, moreover for small and medium sized problems BRKGA obtained better performance than GRASP, while for large problems, GRASP outperforms BRKGA
Subject: Meta-heurística
GRASP (Meta-heurística)
Problema de diversidade máxima
Algoritmos genéticos
Editor: [s.n.]
Date Issue: 2017
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Moro_MarcelAlves_M.pdf834.4 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.