Metaheurísticas para o problema da mochila multidimensional

• Ano de defesa: 2016
• Autor(a) principal: Dantas, Bianca de Almeida
• Orientador(a): Cáceres, Edson Norberto
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Programação Paralela (Computação); Algorítmos Genéticos; Redes Neurais (Computação); Parallel Programming (Computer science); Genetic Algorithms; Neural Networks (Computer Science)
• Link de acesso: https://repositorio.ufms.br/handle/123456789/2970

O problema da mochila multidimensional ´e amplamente conhecido na área de otimização combinatória e possui diversas aplicações práticas, tais como, dimensionamento de cargas, orçamento de capital, alocação de recursos em sistemas distribuídos, entre outros. Apesar de sua popularidade, sua solução não é trivial, de fato, ele pertence a uma classe de problemas conhecidos como NP-difíceis, para os quais não são conhecidos algoritmos polinomiais capazes de obter uma solução exata para todas as instancias. Essa situação motiva a busca por técnicas alternativas para obter soluções em menor tempo, ainda que aproximadas e, nesse cenário, as metaheurısticas têm se mostrado de especial interesse, pois são capazes de alcançar soluções de boa qualidade para uma ampla variedade de problemas. Entretanto, mesmo as metaheurısticas podem ser relativamente demoradas, em especial para instâncias de tamanho grande, o que encoraja a aplicação de t´técnicas, como as estratégias de paralelização, para reduzir os seus tempos de execução ou, ainda, melhorar a qualidade das soluções. Neste trabalho, apresenta-se o estudo, implementação e análise de um conjunto de metaheurısticas para a solução do problema da mochila multidimensional. São apresentadas e avaliadas diferentes alternativas para a paralelização e os resultados obtidos são comparados com os de outros trabalhos da literatura pesquisada. Para comprovar que os bons resultados possibilitados pelo uso das metaheurısticas estudadas não foram obtidos ao acaso, as soluções foram validadas com a utilização de testes estatísticos.