Please use this identifier to cite or link to this item: https://app.uff.br/riuff/handle/1/12490
Title: Optimistic: Um Framework para Implementação e Uso de Meta e Hiper-Heurísticas
Authors: Landes, Flávio Barreiro
metadata.dc.contributor.advisor: Semaan, Gustavo Silva
Issue Date: 2017
Abstract: Problemas de Otimização Combinatória são comumente encontrados no meio acadêmico e em empresas. Para resolver tais problemas, métodos exatos, heurísticos (incluindo meta-heurísticas e hiper-heurísticas) e abordagens híbridas são muito utilizados. Métodos exatos que encontram ótimo(s) global(ais) podem se enquadrar em soluções de custo exponencial ou fatorial, o que inviabiliza seu uso na prática. Por outro lado, abordagens heurísticas são rápidas e podem encontrar soluções próximas à ideal, porém estão sujeitas ao inconveniente de permanecerem próximas a ótimos locais. Uma alternativa para escapar desse inconveniente é recorrer as meta-heurísticas que empregam estratégias no sentido de escapar de ótimos locais para possivelmente encontrar o(s) ótimo(s) global(ais). Não obstante, meta-heurísticas precisam de alterações para serem aplicadas em problemas de otimização combinatória. Alternativamente, hiper-heurísticas podem ser aplicadas no contexto de otimização combinatória, com a desvantagem de requererem uma implementação complexa. O presente trabalho apresenta um novo framework para a resolução de meta e hiper heurísticas, denominado de OPTimistic. O objetivo é simplificar e aumentar a produtividade do processo de desenvolvimento e também uso de meta e hiper-heurísticas. A primeira versão, aqui relatada, possui um módulo meta-heurístico baseado no modelo de Iterated Local Search. Para avaliação do framework, são apresentados como estudos de caso soluções para o Problema da Mochila Binária. Por meio das soluções obtidas para o estudo de caso, mostramos que alguns dos métodos heurísticos são capazes de encontrar soluções ótimas globais para todas as instâncias consideradas.
metadata.dc.description.abstractother: Combinatorial Optimization Problems are usually employed for industrial and academic purposes. The solving of such problems include exact, heuristic (meta-heuristics and hyper-heuristics), and hybrid methods. Although exact methods enable the finding of global optima, they can be of either exponential or factorial complexity, which is prohibitive in practice. On the other hand, heuristics are fast and can find good enough solutions, but they are likely to stuck in local minima. An alternative to avoid such a problem is to resort to meta-heuristics. Nevertheless, the use of meta-heutistics for solving combinatorial optimization problems requires a complex parametrization. A viable option within this context is the use of hyper-heuristics that can easily handle several combinatorial optimization problems. Our study reports a meta-hyper-heuristic framework called OPTimistic, whose goal is to increase the productivity in the meta and hyper-heuristic design process as well as to simplify the use of such methods for particular problems. The first OPTimistic implementation include a meta-heuristic module based on the Iterated Local Search model. As for the evaluation of OPTimistic, we report a case study regarding the methods we discussed and the Binary Backpack Problem. The results indicate some of the heuristic methods have found the global optimum for all instances evaluated.
URI: https://app.uff.br/riuff/handle/1/12490
Appears in Collections:PCL - Trabalhos de Conclusão de Curso - Santo Antônio de Pádua

Files in This Item:
File Description SizeFormat 
TFC_Flavio.pdf1.33 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons