Please use this identifier to cite or link to this item: http://www.monografias.ufop.br/handle/35400000/1104
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorOliveira, Fernando Bernardes dept_BR
dc.contributor.authorOliveira, Kelly Márcia de-
dc.date.accessioned2018-07-19T15:51:16Z-
dc.date.available2018-07-19T15:51:16Z-
dc.date.issued2017-
dc.identifier.citationOLIVEIRA, Kelly Márcia de. Um método baseado em estratégia evolutiva e Variable Neighborhood Descent para o problema quadrático de alocação. 2017. 40 f. Monografia (Graduação em Sistemas de Informação) - Instituto de Ciências Exatas e Aplicadas, Universidade Federal de Ouro Preto, João Monlevade, 2017.pt_BR
dc.identifier.urihttp://www.monografias.ufop.br/handle/35400000/1104-
dc.description.abstractO Problema Quadrático de Alocação (PQA) é bastante conhecido na área de otimização combinatória e possui ampla aplicação na indústria. O PQA faz parte da classe de problemas definidos na computação como NP-difícil, ou seja, para certas instâncias não é possível encontrar uma solução ótima em tempo computacional viável devido ao grande número de soluções a serem avaliadas. Assim, o uso de heurísticas torna-se fundamental, uma vez que essas indicam uma maneira de reduzir o número de avaliações necessárias para problemas com uma grande quantidade de soluções candidatas. O objetivo deste trabalho é o desenvolvimento de uma meta-heurística aplicável ao PQA por meio da Computação Evolucionária. Para isso, faz-se necessário o estudo do Problema Quadrático de Alocação, das estruturas de vizinhança, e algoritmos utilizados na resolução do problema. Este trabalho apresenta uma meta-heurística híbrida combinando Estratégias Evolutivas com a VND. Os resultados obtidos sugerem que não há diferença significativa entre as soluções do método proposto e da literatura, indicando que a meta-heurística proposta pode ser uma boa alternativa na busca pela melhor solução. Quando se compara a média das soluções obtidas, a literatura tende a apresentar um melhor resultado. Entretanto, a comparação dos valores médios do ES-VND com a literatura pode ser injusta, pois somente os melhores resultados estão disponíveis na literatura para comparação.pt_BR
dc.language.isopt_BRpt_BR
dc.rightsopen accesspt_BR
dc.subjectHeurísticapt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectSistemas de informaçãopt_BR
dc.titleUm método baseado em estratégia evolutiva e Variable Neighborhood Descent para o problema quadrático de alocação.pt_BR
dc.typeTCC-Graduaçãopt_BR
dc.rights.licenseAutorização concedida à Biblioteca Digital de TCC da UFOP pela autora em 18/07/2018, com as seguintes condições: disponível sob Licença Creative Commons 4.0, que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e licenciante. Não permite o uso para fins comerciais nem a adaptação.pt_BR
dc.contributor.refereeOliveira, Fernando Bernardes dept_BR
dc.contributor.refereeFonseca, George Henrique Godim dapt_BR
dc.contributor.refereeBrito, Samuel Souzapt_BR
dc.description.abstractenThe Quadratic Assignment Problem (QAP) is well known in the field of combinatorial optimization and it is widely applied in the industry. Although it has a wide application, the QAP is part of the class of problems defined in computing as NP-Hard. That is, for some instances it is not possible to find an optimal solution in viable computational time due to a large number of solutions to be evaluated. Thus, the use of heuristics becomes feasible, since these indicate a way to reduce the number of evaluations required for problems with a large number of candidate solutions. The objective of this work is the development of a metaheuristic applied to QAP by means of Evolutionary Computing. For this, it is necessary to study the Quadratic Assignment Problem, the neighborhood structures, and algorithms used to solve the problem. This paper presents a hybrid metaheuristic combining Evolution Strategies with Variable Neighborhood Descent method. The results suggest that there is no significant difference between the solutions of the proposed method and the literature, indicating that the proposed metaheuristic can be a good alternative in the search for the best solution. When the average of the obtained solutions is compared, the literature tends to present a better result. However, the comparison of mean values of ES-VND with the literature may be unfair, since only the best results are available in the literature for comparison.pt_BR
Appears in Collections:Sistema de Informação - JMV

Files in This Item:
File Description SizeFormat 
MONOGRAFIA_MétodoBaseadoEstratégia.pdf5,93 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons