Dissertação
{pt=Resolução de Problemas da Mochila Multicritério através de técnicas Metaheurísticas: Modelos, Implementações e Resultados} {pt=Modelos, Implementações e Resultados} EVALUATED
{pt=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., en=In this thesis, we propose a hybrid methodology for solving a very well known combinatorial optimization problem, the knapsack problem. The implemented methodology is used to solve two multi-objective variants of this problem, the multi-objective knapsack problem with one constraint, and the multi-objective knapsack problem with more than one constraint. This problem appears in many practical situations, such as the selection of investment projects and budgetary control. Moreover, this problem can be seen as a subproblem in several models, such as the partition and design of electronic circuits or the choice of a flight crew. Typically, to solve this problem we can use exact algorithms, which give us exact solutions, or metaheuristic/heuristic techniques that do not guarantee exact solutions, but in general, allow us to obtain ?good? approximate solutions. However, the application of the exact methods is limited by the size of the instances of the problem and by the available computational resources, while on metaheuristics we can obtain ?quality? solutions for large instances using reasonable computational resources. The proposed methodology in this work consists of combining two metaheuristics techniques that have shown good performances in several problems of combinatorial nature: the ant colony optimization and the scatter search method. To evaluate the performance of this method, we compared the results with others calculated by some methods from literature, and the new model has been clearly superior.}
junho 2, 2010, 16:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
