paulohepimentel / genetic-knapsack

Implementation of a meta-heuristic based on genetic algorithms applied to the famous Knapsack problem 0/1

Projeto    |    Problema    |    Algoritmos Genéticos    |    Estrutura da entrada

✦ Projeto

O trabalho teve como objetivo a implementação prática de uma meta-heurística baseada em algoritmos genéticos, aplicada ao famoso problema da Mochila 0/1.

✦ Problema

O problema da Mochila 0/1 (0/1 Knapsack Problem) possui as algumas características interessantes, nesse famoso problema cada ítem pode ser escolhido no máximo uma vez. O objetivo é escolher a melhor combinação possível, ou seja, a que alcance o maior somatório de valor dos itens

✦ Algoritmos Genéticos

O funcionamento de algoritmos genéticos consiste em tratar as possíveis soluções de um problema como "indivíduos" de uma "população", que irá "evoluir" a cada iteração ou "geração". Para isso é necessário construir um modelo de evolução onde os indivíduos sejam soluções de um problema. Os passos do algoritmo são os seguintes:

• Representação das possíveis soluções do problema no formato de um código genético;
• População inicial que contenha uma diversidade de modo a permitir ao algoritmo combinar características e produzir novas soluções;
• Existência de um método para medir a qualidade de uma solução potencial;
• Um procedimento de combinação de soluções para gerar novos indivíduos na população;
• Um critério de escolha das soluções que permanecerão na população ou que serão retirados desta;
• Um procedimento para introduzir periodicamente alterações em algumas soluções da população.

O algoritmo é executado enquanto houver uma melhora da função objetivo (alcançar a melhor combinação de itens). Foi definido como critério de parada do algoritmo o encerramento após três iterações sem melhora de resultados.

✦ Estrutura da entrada

A estrutura do arquivo de entrada é a seguinte:

• Primeira linha: Número de itens | Capacidade da mochila
• Demais linhas do arquivo: Valores | pesos dos itens

---

O projeto foi desenvolvido, para fins didáticos, durante a disciplina de Meta-heurística do curso de Bacharelado em Ciência da Computação da UFV – Campus Florestal