Outro dia encontrei o meu caderno de uma disciplina de otimização que fiz no doutorado. Ao reler as anotações, encontrei o famoso problema da mochila (Knapsack Problem).

Esse era um problema muito interessante. Lembrei que tive que desenvolver um código em VBA (era o que eu usava na época) para resolver esse problema. Mas agora que eu sei R & Python, pensei em resolver o problema novamente com essas linguagens.

O meu primeiro pensamento foi desenvolver um pacote do R para resolver esse tipo de problema, mas ao pesquisar um pouco na web, percebi que já existiam pacotes para isso. Além disso, encontrei duas publicações em blogs que usam abordagens que eu nunca tinha pensado antes. Uma usa geoprocessamto e a outra usa algoritmo genético.

Assim, nessa publicação gostaria de apresentar o problema da mochila, bem como usar o R para resolver esse tipo de questão. No fim, vou tentar usar o método do Algoritmo Genético para resolver esse mesmo problema de uma forma diferente.

Para quem quiser dar uma olhada nessas duas referências, você pode ver o post do Julio Trecenti, do Curso-R sobre o problema da mochila aqui. Já sobre a integração do Algoritmo Genético com o problema da mochila pode ser vista aqui

O problema da mochila

Considere o seguinte contexto: você tem uma mochila com capacidade máxima de 25kg e precisa carregar a combinação de itens com maior valor possível , com cada item possuindo valores e pesos diferentes. Quais deles vocês escolheria? Provavelmente os item mais leves com valor maior.

Temos três elementos nesse problema: 1- Capacidade Máxima da mochila, 2- Peso dos itens, 3- Valor dos itens.

Desse modo, como exercício aplicado vamos pensar no estado do Rio de Janeiro como uma “mochila”. Neste exemplo aplicado, o objetivo é selecionar os municípios do estado do Rio de janeiro cuja soma seja igual ao PIB do Rio de Janeiro e ao mesmo tempo observar o tamanho (área em km2) do município como critério de seleção. Usando essa analogia temos:

  1. peso dos itens = área do municipio,
  2. valor dos itens = PIB,
  3. capacidade máxima = PIB do rio de janeiro.

Para resolver esse problema, em linguagem matemática, temos a seguinte tarefa:

\[\begin{aligned} & \text{maximizar } \sum_{i=1}^n v_i x_i \\ & \text{sujeito à } \sum_{i=1}^n w_i x_i \leq W, \text{ com } x_i \in\{0,1\}\\ \end{aligned}\]

onde:

. n é o número de municípios no estado (91). Foi excluído o município do Rio.
. vi é a área do município i
. wi é o PIB do município i
. W é o PIB do Rio de Janeiro (472 milhões).

Como funciona a função knapsack do pacote adagio

Para resolver o problema da mochila, podemos usar a função knapsack do pacote adagio. Vamos ver como ele funciona. Olhando o help do pacote, podemos ver que funciona de forma bem simples.

library(adagio)
# Example 1
p <- c(15, 100, 90, 60, 40, 15, 10,  1)
w <- c( 2,  20, 20, 30, 40, 30, 60, 10)
cap <- 102
(is <- knapsack(w, p, cap))
$capacity
[1] 102

$profit
[1] 280

$indices
[1] 1 2 3 4 6
# [1] 1 2 3 4 6 , capacity 102 and total profit 280

## Example 2
p <- c(70, 20, 39, 37, 7, 5, 10)
w <- c(31, 10, 20, 19, 4, 3,  6)
cap <- 50
(is <- knapsack(w, p, cap))
$capacity
[1] 50

$profit
[1] 107

$indices
[1] 1 4
# [1] 1 4 , capacity 50 and total profit 107

O pacote tem três parâmetros chamados de pesos w, valores p e máximo cap: 1. w integer vector of weights.
2. p integer vector of profits.
3. cap maximal capacity of the knapsack, integer too.

Resolvendo o problema da mochila usando algoritmo genético

Voltando ao problema de uma mochila com capacidade máxima de 25 quilos. O objetivo é maximizar a capacidade de mochila enquanto maximiza seus pontos de survival também. A partir do problema, podemos definir o peso dos itens como a função de restrição, enquanto os pontos survival acumulados dos itens na mochila como a função objetivo.

Para a implementação neste artigo, usamos aqui o pacote GA do R . Primeiro, precisamos inserir os dados e os parâmetros.

#0-1 Knapsack's Problem
library(GA)
item=c('capa de chuva','canivete','água mineral','luvas','saco de dormir','tenda','fogão portátil','comida enlatada','lanches')

weight=c(2,1,6,1,4,9,5,8,3)

survival=c(5,3,15,5,6,18,8,20,8)

data=data.frame(item,weight,survival)

max_weight=25

Para ter uma melhor compreensão do algoritmo genético neste problema, suponha que, inicialmente, levemos apenas um canivete, água mineral e lanches em sua mochila.

Podemos escrevê-lo como o “cromossomo”, e como o problema que queremos resolver é um problema de mochila 0–1, então, a partir dessas linhas de códigos abaixo, 1 significa que trouxemos o item, enquanto 0 significa que deixamos o item fora da mochila.

# 1 significa que trouxemos o item, enquanto 0 significa que deixamos o item fora da mochila
chromosomes=c(0,1,1,0,0,0,0,0,1)
data[chromosomes==1,]
          item weight survival
2     canivete      1        3
3 água mineral      6       15
9      lanches      3        8

Em seguida, criamos a função objetivo que queremos otimizar com a função de restrição escrevendo essas linhas de código abaixo. Preste atenção na função ga do pacote GA .

#create the function that we want to optimize
fitness=function(x){
  current_survpoint=x%*%data$survival
  current_weight=x%*%data$weight
  if(current_weight>max_weight)
  {
    return(0)
  }
  else
  {
    return(current_survpoint)
  }
}

Agora aqui está a parte interessante: o processo de otimização usando o algoritmo genético. Suponha que queremos criar no máximo 30 gerações e 50 indivíduos para o processo de otimização. Para reprodutibilidade, vamos escrever a semente (seed=1234) para guardar a melhor solução.

GA=ga(type='binary',fitness=fitness,nBits=nrow(data),maxiter=30,popSize=50,seed=1234,keepBest=TRUE)
summary(GA)
-- Genetic Algorithm ------------------- 

GA settings: 
Type                  =  binary 
Population size       =  50 
Number of generations =  30 
Elitism               =  2 
Crossover probability =  0.8 
Mutation probability  =  0.1 

GA results: 
Iterations             = 30 
Fitness function value = 61 
Solution = 
     x1 x2 x3 x4 x5 x6 x7 x8 x9
[1,]  1  0  1  1  0  0  1  1  1
plot(GA)