Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/325550
Full metadata record
DC FieldValueLanguage
dc.contributor.CRUESPUNIVERSIDADE ESTADUAL DE CAMPINASpt_BR
dc.descriptionOrientadores: Marcia Aparecida Gomes Ruggiero, Kelly Cristina Poldipt_BR
dc.descriptionDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científicapt_BR
dc.format.extent1 recurso online (55 p.) : il., digital, arquivo PDF.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.relation.requiresRequisitos do sistema: Software para leitura de arquivo em PDFpt_BR
dc.typeTESE DIGITALpt_BR
dc.titleMeta-heurísticas GRASP e BRKGA aplicadas ao problema da diversidade máximapt_BR
dc.title.alternativeGRASP and BRKGA metaheuristics applied to the maximum diversity problempt_BR
dc.contributor.authorMoro, Marcel Alves, 1992-pt_BR
dc.contributor.advisorRuggiero, Márcia Aparecida Gomes, 1956-pt_BR
dc.contributor.coadvisorPoldi, Kelly Cristina, 1979-pt_BR
dc.contributor.institutionUniversidade Estadual de Campinas. Instituto de Matemática, Estatística e Ciência da Computaçãopt_BR
dc.contributor.nameofprogramPrograma de Pós-Graduação em Matemática Aplicadapt_BR
dc.subjectMeta-heurísticapt_BR
dc.subjectGRASP (Meta-heurística)pt_BR
dc.subjectProblema de diversidade máximapt_BR
dc.subjectAlgoritmos genéticospt_BR
dc.subject.otherlanguageMetaheuristicen
dc.subject.otherlanguageGRASP (Metaheuristic)en
dc.subject.otherlanguageMaximum diversity problemen
dc.subject.otherlanguageGenetic algorithmsen
dc.description.abstractResumo: 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 BRKGApt
dc.description.abstractAbstract: 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 BRKGAen
dc.publisher[s.n.]pt_BR
dc.date.issued2017pt_BR
dc.identifier.citationMORO, Marcel Alves. Meta-heurísticas GRASP e BRKGA aplicadas ao problema da diversidade máxima. 2017. 1 recurso online (55 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica, Campinas, SP.pt_BR
dc.description.degreelevelMestradopt_BR
dc.description.degreedisciplineMatematica Aplicadapt_BR
dc.description.degreenameMestre em Matemática Aplicadapt_BR
dc.contributor.committeepersonalnameOliveira, Aurelio Ribeiro Leite dept_BR
dc.contributor.committeepersonalnameMiyazawa, Flávio Keidipt_BR
dc.date.defense2017-07-03T00:00:00Zpt_BR
dc.date.available2017-10-06T17:54:16Z-
dc.date.accessioned2017-10-06T17:54:16Z-
dc.description.provenanceMade available in DSpace on 2017-10-06T17:54:16Z (GMT). No. of bitstreams: 1 Moro_MarcelAlves_M.pdf: 854430 bytes, checksum: 55c496edc98347d27d159ac0fa3a5b51 (MD5) Previous issue date: 2017en
dc.identifier.urihttp://repositorio.unicamp.br/jspui/handle/REPOSIP/325550-
dc.description.sponsorCAPESpt_BR
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.