Title: Um método baseado em estratégia evolutiva e Variable Neighborhood Descent para o problema quadrático de alocação.
Authors: Oliveira, Kelly Márcia de
Citation: OLIVEIRA, 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.
Abstract: O 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.
metadata.dc.description.abstracten: The 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.
URI: http://www.monografias.ufop.br/handle/35400000/1104
metadata.dc.rights.license: Autorizaçã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.