Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2017-04-17T22:15:28Z
No. of bitstreams: 1
AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-26T12:14:12Z (GMT) No. of bitstreams: 1
AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-26T12:16:44Z (GMT) No. of bitstreams: 1
AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Made available in DSpace on 2017-04-26T12:19:14Z (GMT). No. of bitstreams: 1
AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5)
Previous issue date: 2016-07-20 / The use of metaheuristics for solving combinatorial optimization problems belong to NP-Hard class is becoming increasingly common, and second Temponi (2007 apud RIBEIRO, 1996) a metaheurist should be modeled according to the problem she was designed to solve. This most often requires many changes when you have to apply the same metaheuristic to various types of combinatorial optimization problems. In this work we propose a framework for use of a hybrid metaheuristic proposed by Almeida (2014) who used the GRASP Reactive along with a reinforcement learning technique (called GR-learning). Specifically, the Q-learning algorithm that was used to learn over which the iterations value for the parameter α (alpha) used during the construction phase of GRASP. The GR-Learning was used to solve the problem of p-centers applied to Public Security in the city of Mossoró/RN. To validate the effectiveness of the framework proposed it was used to solve two classical problems of combinatorial optimi-zation: The Hub Location Problem (HLP), and the Cutting Stock Problem (CSP). To validate the results obtained we used instances with results known in the literature and in addition has created an instance with data from the Brazilian airline industry. The results showed that the proposed framework was quite competitive when compared to other results of different algo-rithms known in the literature as got great value in almost all instances of HLP as well as new values (better than those obtained with other algorithms known in the literature) for some ins-tances of CSP / A utilização de metaheurísticas para resolução de problemas de otimização combinatória per-tencentes à classe NP-Difícil vem se tornando cada vez mais comum, e segundo Temponi (2007 apud RIBEIRO, 1996) uma metaheurística deve ser modelada de acordo com o proble-ma que ela foi projetada para resolver. Isto na maioria vezes requer muitas alterações quando se tem que aplicar uma mesma metaheurística a diversos tipos de problemas de otimização combinatória. Neste trabalho foi proposto um framework para utilização de uma metaheurísti-ca híbrida proposta por Almeida (2014) que utilizou a metaheurística GRASP Reativo junta-mente com uma técnica de aprendizagem por reforço (denominada GR-Learning). Especifi-camente, o algoritmo Q-learning, que foi utilizado para aprender com o passar das iterações qual valor para o parâmetro α (alfa) utilizar durante a fase de construção da GRASP. O GR-Learning foi utilizado para resolver o problema dos p-Centros aplicado a Segurança Pública na Cidade de Mossoró/RN. Para validar a eficácia do framework proposto o mesmo foi utili-zado para resolver dois problemas clássicos de otimização combinatória: O Problema de Lo-calização de Hubs (do inglês Hub Location Problem - HLP) e o Problema de Corte e Estoque – PCE (do inglês Cutting Stock Problem - CSP). Para validação dos resultados obtidos foram utilizadas instâncias com resultados já conhecidos na literatura e adicionalmente foi criada uma instância com dados do setor aeroviário Brasileiro. Os resultados obtidos mostraram que o framework proposto foi bastante competitivo quando comparado a outros resultados de di-versos algoritmos já conhecidos na literatura, pois obteve o valor ótimo em quase todas as instâncias do HLP como também novos valores (melhores que os obtidos com outros algorit-mos já conhecido na literatura) para algumas instâncias do CSP / 2017-04-17
| Identifer | oai:union.ndltd.org:IBICT/oai:bdtd.ufersa.edu.br:tede/675 |
| Date | 20 July 2016 |
| Creators | Silva, Alexsandro Trindade Sales da |
| Contributors | http://lattes.cnpq.br/9342041276186254, Lima Júnior, Francisco Chagas de, Liberalino, Carlos Heitor Pereira, Aloise, Dario José, Medeiros Neto, Francisco Dantas de, Medeiros, João Paulo de Souza |
| Publisher | Universidade Federal Rural do Semi-Árido, Programa de Pós-graduação em Ciência da Computação, UFERSA, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFERSA, instname:Universidade Federal Rural do Semi-Árido, instacron:UFERSA |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds