problema da mochila
361 palavras
2 páginas
Algoritmos Genéticos para o Problema da MochilaEstéfane G. M. de Lacerda
UFRN/DCA
Setembro/2008
O Problema da Mochila
O Problema da Mochila
●
Dados um conjunto de n objetos e uma mochila com:
●
●
wj = peso do objeto j
●
●
cj = benefício do objeto j b = capacidade da mochila
Determinar quais objetos devem ser colocados na mochila para maximizar o benefício total de tal forma que o peso da mochila não ultrapasse sua capacidade. O Problema da Mochila zero-um
(do inglês, 0-1 knapsack problem) n Maximizar z =∑ c j s j j=1 Sujeita a
n
∑ w j s jb j=1 s j ∈{0,1}
Uma solução s é um vetor de uns e zeros.
Se o objeto j está mochila então sj = 1, caso contrário sj = 0.
Algoritmo Genético
●
Cromossomo
●
●
A solução s (um vetor de uns e zeros) é naturalmente representada por um cromossomo binário.
Operadores binários padrão
●
Crossover de 1-ponto (ou 2-pontos, etc)
●
Mutação (invertendo os bits)
Uma Instância do Problema da Mochila
Objet o (j)
Benefício (c j )
Peso (w j )
1
3
5
Capacidade da mochila:
2
3
4
3
2
7
b = 25
11001110 (cromossomo válido) peso = 5+4+4+4+6 = 23 25 função objetivo = 3+3+2+3+5 = 16
11111001 (inválido) peso = 36 > 25
Função objetivo = 16
4
4
8
5
2
4
6
3
4
7
5
6
8
2
8
Como Lidar com Indivíduos Inválidos?
●
Solução 1 – reparar o indivíduo
●
Solução 2 – penalizar a função objetivo
Reparando o Indivíduo
●
Indivíduo inválido
●
11111001
●
peso = 36 > 25
●
●
Função objetivo = 16
Indivíduo “reparado”
●
11110000
●
Peso = 24 (ok!)
●
Função objetivo = 12
1 1 1 1 1 0 0 1 desprezar visitar cada bit da esquerda para a direita e desprezar os bits que invalidam a solução.
Reparando o Indivíduo
●
Por qual ordem dos bits devem ser visitados?
●
●
No sentido oposto?
●
●
Da esquerda para direita?
Aleatoriamente?
Algoritmo