PROBLEMA DO
EMPACOTAMENTO
ALGORITMOS GENÉTICOS
Claudinei Costantin
Niarchos Pabalis Pombo
Samir Guilherme Zieger Merode
Objetivos



Estudar uma meta-heurística: Algoritmos
Genéticos;
Estudar o Problema do Empacotamento
(Bin Packing);
Implementar um programa capaz de gerar
boas soluções para o Problema do
Empacotamento utilizando Algoritmos
Genéticos.
Problema do Empacotamento
Acomodamento de uma lista de itens;
 Cada item tem um tamanho;
 As caixas têm uma capacidade fixa;
 Distribuir os itens nas caixas;
 Minimizar a quantidade de caixas.

Algoritmos Genéticos
Baseado na Teoria da Evolução Natural
das Espécies;
 Indivíduos mais aptos têm mais chance de
sobreviverem;
 Indivíduos são soluções potenciais;
 População é o conjunto de soluções.

Algoritmos Genéticos
Algoritmos Genéticos

Determinar:
 Representação
dos indivíduos (soluções);
 Função que gera a população inicial;
 Função de aptidão (fitness);
 Recombinação;
 Seleção;
 Mutação;
 Condição de Parada.
Implementação
Java J2EE;
 NetBeans 5.5.1;
 Programa que lê instância do problema;


Gera soluções através de Algoritmos
Genéticos;
Implementação

Representação de uma
solução:
 Classe
Solucao;
 Contém um array de inteiros;
 Cada alelo representa um
item;
 Ordem dos alelos = ordem
dos itens;
 Exemplo: [10, 7, 6, 6, 5, 2]
Implementação

Geração da população inicial:
 Classe
Populacao que contém um array de
Solucao;
 Soluções geradas aleatoriamente;
 O array é mantido ordenado pela qualidade
das soluções;
 Tamanho da população é constante e é dado
como entrada do programa;
 Opção: First Fit Decreasing para uma gerar
uma solução.
Implementação

Função de aptidão:
 Quantidade
de caixas que a solução ocupa;
 Quanto menos caixas, melhor a solução.
Implementação

Recombinação de indivíduos:
 Método
casa da classe Solucao;
 Crossover das representações com ponto de
quebra aleatório;
 Retorna um novo descendente.
Implementação

Seleção de Indivíduos:
O
indivíduo mais apto permanece para a
próxima geração;
 Método evolui da classe Populacao;
 84% de chance de seleção das 20%
melhores soluções;
 16% de chance de seleção das 80% piores
soluções.
Implementação

Mutação:
 Troca
aleatória da posições de dois itens;
 Realizada após a recombinação de duas
soluções;
 Freqüência de ocorrência dada como entrada
do programa.
Implementação

Condição de parada:
 Quantidade
de gerações dada como entrada
do programa.
Implementação

Entradas do programa:
 Arquivo
com a instância de um problema;
 Número de gerações;

Default: 50;
 Tamanho da população;
 Default: 1000;

 Probabilidade
 Default: 5%;
de mutação;
 Opção de uso
 Default: Sim.
de FFD;
Para os testes, foram utilizadas as entradas
default;
Implementação
Resultados

Instância N1C1W1_A (50 itens; caixa: 100; solução ótima: 25)

Com FFD: 25;
 Sem FFD: 27;

Instância N2C2W2_F (100 itens; caixa: 120; solução ótima: 48)



Instância N2C2W1_A (100 itens; caixa: 120; solução ótima: 42)



Com FFD: 48;
Sem FFD: 51;
Com FFD: 42;
Sem FFD: 44;
Instância N3C2W4_O: (200 itens; caixa: 120; solução ótima: 113)


Com FFD: 113;
Sem FFD: 124.
Resultados

Instância N4C3W4_R (500 itens; caixa: 150; solução ótima: 214)

Com FFD: 219;
 Sem FFD: 243;

Instância N1W1B1R0 (50 itens; caixa: 1000; solução ótima: 18)



Instância N2W2B2R2 (100 itens; caixa: 1000; solução ótima: 21)



Com FFD: 19;
Sem FFD: 19;
Com FFD: 21;
Sem FFD: 22;
Instância N2W3B2R6 (100 itens; caixa: 1000; solução ótima: 14)


Com FFD: 14;
Sem FFD: 15.
Resultados

Instância N3W3B3R4 (200 itens; caixa: 1000; solução ótima: 29)

Com FFD: 29;
 Sem FFD: 30;

Instância N4W4B1R6 (500 itens; caixa: 1000; solução ótima: 56)



Instância HARD2 (200 itens; caixa: 100000; solução ótima: 56)



Com FFD: 58;
Sem FFD: 58;
Com FFD: 58;
Sem FFD: 61;
Instância HARD7 (200 itens; caixa: 100000; solução ótima: 55)


Com FFD: 57;
Sem FFD: 59.
Conclusões







Não é aconselhado o uso de populações muito grandes
em casos com muitos itens;
O nº de gerações utilizadas aumenta linearmente o
tempo de resposta;
O uso FFD ajuda a encontrar uma solução boa em um
nº menor de gerações;
A função de seleção parece estar causando uma
convergência prematura;
A quantidade de testes possíveis é muito grande;
Vantagem: obter uma solução numa quantidade de
tempo pré-estabelecida;
Desvantagem: a solução encontrada é ótima?
PERGUNTAS?
Claudinei Costantin
Niarchos Pabalis Pombo
Samir Guilherme Zieger Merode