Genéticos: Problema da Mochila em Python

Afluentes: Inteligência Artificial, Modelos Evolutivos e Tratamento de Incertezas

Definição do Problema

Para mostrar uma implementação de um Algoritmo Genético, iremos trabalhar com o Problema da Mochila.

Sobre o problema da mochila:

• Problema de otimização combinatória (NP-Completo)
• Estudado por mais de um século (desde ~1897)
• Resolvido por vários algoritmos

Podemos representar a aptidão de uma solução como a soma dos valores dos objetos e com uma penalidade para soluções que passam do limite de volume.

• Queremos o maior valor possível sem ultrapassar o limite da mochila.
• Vários itens que gostaria de levar em uma mochila
• Cada item tem um peso e um benefício, ou valor
• Existe uma capacidade limite de peso
• Deve-se carregar itens com o máximo valor total sem superar o limite de peso

Programa em Python

Coloquei o programa no github, fica mais fácil, fazer atualizações, de baixar e bom para visualizar. Vejam que o programa deu quase 300 linhas, mas é porque está todo comentado. Se tirar os comentários ele fica bem menor. É um algoritmo muito fácil e simples, talvez um dos mais fáceis de se implementar da Inteligência Artificial.

Link do github: https://github.com/saulopz/ia_genetico_mochila

Para baixar em seu computador, basta executar o comando:

git clone https://github.com/saulopz/ia_genetico_mochila

Eu estava fazendo procedural e estava tendo que fazer uns remendos, como encher de variáveis globais e outras coisas mais, e acho que isso estava permitindo um bug difícil de encontrar. Então decidi ir pra orientação a objetos que pra mim é mais fácil de entender e organizar. A ideia do algoritmo é a mesma que expliquei, mesmas funções, mesmaa funcionalidade, só está organizado como objetos. E, no final, era um bug bobo mesmo por causa de variáveis globais.

Solução

A solução encontrada para o algoritmo com os parâmetros e configuração acima fica:

SOLUÇÃO ------------------------------
Capacidade da mochila: 22
- tv valor: 8 gold - peso: 8
- colar valor: 7 gold - peso: 4
- videogame valor: 9 gold - peso: 6
- smarthone valor: 4 gold - peso: 4
Valor total: 28 gold
Peso total : 22
--------------------------------------

Alterações para novo teste

No arquivo config.json adicionei um item (impressora) no arquivo de configuração e aumentei a capacidade para 25. Também alterei as variáveis do algoritmo aumentando a população, gerações, etc.

 1{
 2  "population_size": "100",
 3  "selection_size": "40",
 4  "crossover_gene_size": "2",
 5  "mutation_individual_size": "20",
 6  "mutation_gene_size": "2",
 7  "generations": "500",
 8  "penality": "100",
 9
10  "capacity": "25",
11  "items": [
12    { "name": "notebook", "value": "5", "weight": "7" },
13    { "name": "tv", "value": "8", "weight": "8" },
14    { "name": "tablet", "value": "3", "weight": "4" },
15    { "name": "anel", "value": "2", "weight": "10" },
16    { "name": "colar", "value": "7", "weight": "4" },
17    { "name": "videogame", "value": "9", "weight": "6" },
18    { "name": "smarthone", "value": "4", "weight": "1" },
19    { "name": "impressora", "value": "2", "weight": "5" }
20  ]
21}

E obtive a seguinte solução:

SOLUÇÃO ------------------------------
Capacidade da mochila: 25
- notebook valor: 5 gold - peso: 7
- tv valor: 8 gold - peso: 8
- colar valor: 7 gold - peso: 4
- videogame valor: 9 gold - peso: 6
Valor total: 29 gold
Peso total : 25
--------------------------------------

A partir daí, dá para gente ir brincando com as configurações do algoritmo, informações do problema e outras variáveis para ver como os resultados vão se alterando.