Dissertação
Resolução de Problemas da Mochila Multicritério através de técnicas Metaheurísticas: Modelos, Implementações e Resultados Modelos, Implementações e Resultados EVALUATED
Nesta dissertação propõe-se uma metodologia híbrida para resolução de um problema de optimização combinatória muito conhecido na literatura, o problema da mochila. A metodologia implementada é utilizada para resolver duas variantes multicritério deste problema, o problema da mochila multicritério com uma restrição e o problema da mochila multicritério com várias restrições. Este problema está presente em muitas situações práticas, como por exemplo, na selecção de projectos de investimento e no controlo orçamental. Além disso, o problema em estudo pode ser visto como um subproblema em diversos modelos, como por exemplo, na partição e concepção de circuitos electrónicos e na constituição de tripulações de um voo. Tipicamente, para resolver este problema, utilizam-se os algoritmos exactos, que permitem obter soluções exactas, ou as técnicas metaheurísticas/heurísticas, que não garantem a obtenção das soluções exactas, mas que em geral, permitem obter ?boas? soluções aproximadas. Apesar dos métodos exactos garantirem a obtenção de soluções exactas, a sua aplicação é limitada, dada à dimensão das instâncias do problema e os recursos computacionais. Em geral, tal não se verifica nas metaheurísticas, dado que estas permitem obter soluções de ?qualidade? utilizando recursos computacionais razoáveis para instâncias de grande dimensão. A metodologia proposta neste trabalho consiste em combinar duas técnicas metaheurísticas, que têm revelado bons desempenhos em diversos problemas de natureza combinatória: a optimização através das colónias de formigas e a pesquisa por dispersão. Para avaliar o desempenho deste método, comparam-se os resultados obtidos com outros calculados por alguns métodos da literatura. O modelo proposto revelou-se claramente superior.
junho 2, 2010, 16:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
