Trabalho de Conclusão de Curso

APLICANDO O ALGORITMO BRKGA PARA SOLUCIONAR DIFERENTES VERSÕES DO PROBLEMA DA MOCHILA

Trabalho de Conclusão de Curso submetido ao Curso de Tecnologia em Sistemas de Computação da Universidade Federal Fluminense como requisito parcial para obtenção do título de Tecnólogo em Sistemas de Computação.

Orientadora: Julliany Sales Brandão

RESUMO

O problema da mochila é um problema de otimização combinatória onde se objetiva preencher uma mochila com objetos de pesos e valores distintos, ocupando-a com o maior valor possível sem ultrapassar o limite de peso que ela suporta.

Esse modelo de problema pode ser aplicado em cenários como investimento de capital, empacotamento, carregamento de veículos, orçamento, alocação de máquinas virtuais em computação nas nuvens (Cloud Computing), entre outros.

Para encontrar as melhores soluções, ou pelo menos as mais próximas das soluções ótimas, este trabalho irá apresentar o algoritmo genético BRKGA.

Ele não é a única solução para este modelo de problema, existem outros trabalhos similares que também encontram bons resultados para o modelo.

Em vista disso, será feita uma análise comparativa da solução proposta com o método guloso, visando avaliar o desempenho de ambos.