Bin Packing

Prévia do material em texto

Bin Packing com Algoritmo Genético
Rafael Moreti Santana 55998
 
Bin Packing
● Empacotar um conjunto de objetos no 
menor número possível de pacotes
● É um problema combinacional NP-Díficil
● Possui variações, como pacotes em 2D, 
em 3D
● Possui aplicações desde carregamento 
de containers a criação de backup de 
dispositivos remotos.
 
Bin Packing
● Exemplo: alocar vários itens em pacotes 
com capacidade máxima equivalente a 4
 
Algoritmo Genético
● Consiste em partindo de uma população, 
gerar descendentes promissores a partir 
do compartilhamento de dados.
● Calcular a taxa de aptidão da população e 
realizar o cruzamento baseado nela:
Roleta
– Torneio
● Gerar mutações na população.
 
Algoritmo Genético e o Bin 
Packing
● População: Conjunto de possíveis 
soluções do problema
● Função de Aptidão: Número de caixas 
utilizadas pela solução
● Reprodução: Combinação dos valores da 
população.
● Mutação: Swap de valores entre posições 
randômicas.
 
Função de Aptidão
I. Somar o número de caixas utilizadas por 
todas as soluções
II.Para cada solução, definir como taxa de 
aptidão o número de caixas utilizadas por 
ela dividido pelo total calculado
III.Realizar tais passos a cada geração
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6