Packing- Biased Random-Key Genetic Algorithm e o problema de empacotamento 3D

Imagina que você tem um kit de produtos e quer saber qual o tamanho da caixa que você precisa. Um algoritmo simples pode facilmente empilhar todos os produtos em uma única coluna e atrapalhar os seus planos, certo?

Aplicar o BRKGA (Biased Random-Key Genetic Algorithm) para resolver o problema de empacotamento 3D é uma alternativa.

Teoria

O BRKGA (Biased Random-Key Genetic Algorithm) para o Problema de Empacotamento 3D é uma abordagem baseada em algoritmos genéticos para resolver problemas de otimização de empacotamento tridimensional. O objetivo do problema de empacotamento 3D é colocar um conjunto de itens com dimensões tridimensionais (comprimento, largura e altura) em um número mínimo de compartimentos (ou caixas) com capacidades limitadas.

O BRKGA é uma classe de algoritmos genéticos que utiliza chaves aleatórias enviesadas para representar soluções. O algoritmo genético é uma técnica de busca heurística inspirada no processo de evolução natural. Ele trabalha com uma população de soluções candidatas (indivíduos), onde cada indivíduo representa uma solução potencial para o problema. Essas soluções evoluem ao longo do tempo por meio de operações como seleção, cruzamento (recombinação) e mutação.

Aqui está uma descrição geral do BRKGA para o problema de empacotamento 3D:

Inicialização: Gere uma população inicial de soluções candidatas aleatórias, representadas por chaves aleatórias enviesadas.
Avaliação: Calcule a aptidão (fitness) de cada indivíduo na população. No caso do problema de empacotamento 3D, a aptidão pode ser medida como o número de compartimentos utilizados ou o espaço desperdiçado nos compartimentos.
Seleção: Selecione os indivíduos da população atual com base em sua aptidão. Os indivíduos com melhor aptidão têm maior probabilidade de serem selecionados.
Cruzamento: Combine os indivíduos selecionados para criar novas soluções candidatas. No BRKGA, isso é feito combinando as chaves aleatórias enviesadas dos pais para gerar chaves para a prole.
Mutação: Introduza pequenas perturbações nas soluções candidatas recém-criadas. Isso é feito alterando aleatoriamente algumas das chaves enviesadas.
Atualização da população: Substitua uma parte da população atual pelas novas soluções candidatas geradas.
Condição de parada: Verifique se a condição de parada foi atingida, como um número máximo de gerações ou um limite de tempo.
Se a condição de parada não for atingida, volte ao passo 2.
Retorne a melhor solução encontrada.

O BRKGA para o problema de empacotamento 3D é uma abordagem heurística que pode fornecer soluções de alta qualidade em um tempo razoável. No entanto, como outros algoritmos genéticos, ele não garante encontrar a solução ótima global em todos os casos.

Na Prática

Defina os produtos e suas quantidades, como no exemplo fornecido:

python

Copy code
products = [ {"name": "Alpha", "quantity": 10, "dimensions": (10, 10, 10)}, {"name": "Bravo", "quantity": 1, "dimensions": (150, 200, 140)}, {"name": "Charlie", "quantity": 3, "dimensions": (15, 20, 14)} ]

Implemente o algoritmo BRKGA, adaptando-o para o problema de empacotamento 3D. Isso inclui a definição de funções de aptidão (fitness), cruzamento (crossover) e mutação específicas para este problema. Você pode usar bibliotecas de algoritmos genéticos em Python, como DEAP ( https://deap.readthedocs.io/en/master/ ) ou PyGMO ( https://esa.github.io/pygmo2/ ), para facilitar a implementação.
Configure os parâmetros do algoritmo, como o tamanho da população, o número máximo de gerações, a taxa de cruzamento e a taxa de mutação. Ajuste esses parâmetros de acordo com suas necessidades de desempenho e qualidade da solução.
Execute o algoritmo BRKGA com os produtos e parâmetros definidos. O algoritmo explorará várias soluções de empacotamento e tentará minimizar o número de caixas necessárias para acomodar todos os itens.
Obtenha a melhor solução encontrada pelo algoritmo. Essa solução representará o tamanho mínimo da caixa de papelão necessária para acomodar todos os itens, considerando a abordagem heurística do BRKGA.

Exemplo

Aqui está um exemplo simplificado de como implementar o BRKGA para o problema de empacotamento 3D usando a biblioteca DEAP em Python:

import rando
from deap import base, creator, tools


# Defina os produtos e suas quantidades
products = [
{"name": "Alpha", "quantity": 10, "dimensions": (10, 10, 10)},
{"name": "Bravo", "quantity": 1, "dimensions": (150, 200, 140)},
{"name": "Charlie", "quantity": 3, "dimensions": (15, 20, 14)}
]


# Função de aptidão (fitness)
def fitness(individual):
# Aqui, você deve implementar a função de aptidão que avalia a qualidade do empacotamento
# com base no indivíduo (representando uma solução de empacotamento)
pass


# Função de cruzamento (crossover)
def crossover(ind1, ind2):
# Aqui, você deve implementar a função de cruzamento que combina dois indivíduos
# para criar novos indivíduos (descendentes)
pass


# Função de mutação
def mutate(individual):
# Aqui, você deve implementar a função de mutação que introduz pequenas perturbações
# em um indivíduo
pass


# Criação de tipos personalizados
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)


# Inicialização
toolbox = base.Toolbox()
toolbox.register("attr_float", random.random)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=len(products))
toolbox.register("population", tools.initRepeat, list, toolbox.individual)


# Registro de operadores genéticos
toolbox.register("evaluate", fitness)
toolbox.register("mate", crossover)
toolbox.register("mutate", mutate)
toolbox.register("select", tools.selBest)


# Parâmetros
POP_SIZE = 100
N_GEN = 100
CX_PB = 0.8
MUT_PB = 0.2


# Algoritmo principal
def main():
pop = toolbox.population(n=POP_SIZE)
hof = tools.HallOfFame(1)


stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", numpy.mean)
stats.register("min", numpy.min)
stats.register("max", numpy.max)


pop, log = algorithms.eaSimple(pop, toolbox, cxpb=CX_PB, mutpb=MUT_PB, ngen=N_GEN,
stats=stats, halloffame=hof, verbose=True)

return hof[0]


if __name__ == "__main__":
best_solution = main()
print("Melhor solução encontrada:", best_solution)

Neste exemplo você precisará adaptar as funções fitness, crossover e mutate com base na representação e na estratégia de empacotamento e vale você esplorar informações sobre como usar a biblioteca DEAP e adaptar este exemplo ao seu problema específico.

Uma solução simples para o empacotamento

Usando algo mais simples, vou compartilhar um AWS Lambda escrito em python com a implementação da Biblioteca py3dbp :

#!/usr/bin/env python3
import logging
from py3dbp import Packer, Bin, Item


# Configurar o logger
logger = logging.getLogger()
logger.setLevel(logging.INFO)


# Isso configura o logger para exibir informações do log no console com um formato que inclui a data, a hora e o nível de log
logging.basicConfig(level=logging.INFO, format='%(asctime)s - %(levelname)s - %(message)s')


def lambda_handler(event=None, context=None):
logger.info("Iniciando o algoritmo de empacotamento")


# Crie um Packer
packer = Packer()


bins_info = [
("Caixa A", 10, 10, 10, 0),
("Caixa B", 12, 12, 11, 0),
("Caixa C", 15, 12, 11, 0),
("Caixa D", 20, 15, 12, 0),
("Caixa E", 25, 20, 15, 0),
("Caixa F", 30, 30, 15, 0),
("Caixa G", 40, 35, 20, 0),
("Caixa H", 50, 45, 30, 0),
("Caixa I", 300, 300, 300, 0),
("Caixa J", 1500, 1500, 1500, 0)
]


for bin_info in bins_info:
packer.add_bin(Bin(*bin_info))
logger.info(f"Adicionando caixa: {bin_info}")


# Defina os produtos e suas quantidades
products = [
{"name": "Alpha", "quantity": 10, "dimensions": (10, 10, 10)},
{"name": "Bravo", "quantity": 1, "dimensions": (150, 200, 140)},
{"name": "Charlie", "quantity": 3, "dimensions": (15, 20, 14)}
]


# Adicione os produtos como itens
for product in products:
for _ in range(product["quantity"]):
packer.add_item(Item(product["name"], *product["dimensions"], 0))
logger.info(f"Adicionando item: {product}")


# Execute o algoritmo de empacotamento
packer.pack()


# Qual seria uma caixa grande o suficiente para conter todos os itens?
ideal_bin = {
"max_width": sum(item.width for item in packer.items),
"max_depth": sum(item.depth for item in packer.items),
"max_height": sum(item.height for item in packer.items)
}
logger.info(f"Caixa ideal: {ideal_bin}")


# Encontre a caixa com o menor volume possível
for b in packer.bins:
if len(b.items) > 0 and len(b.unfitted_items) == 0:
best_bin = b
break

# Retorne o resultado
response = {
"statusCode": 200,
"body": {
"melhor caixa": best_bin.name,
"width": best_bin.width,
"depth": best_bin.depth,
"height": best_bin.height
}
}

logger.info(f"Resposta: {response}")
return response


if __name__ == "__main__":
lambda_handler()

O script acima dá o seguinte output:

2023-03-24 15:13:57,969 - INFO - Iniciando o algoritmo de empacotamento

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa A', 10, 10, 10, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa B', 12, 12, 11, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa C', 15, 12, 11, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa D', 20, 15, 12, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa E', 25, 20, 15, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa F', 30, 30, 15, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa G', 40, 35, 20, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa H', 50, 45, 30, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa I', 300, 300, 300, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando caixa: ('Caixa J', 1500, 1500, 1500, 0)

2023-03-24 15:13:57,969 - INFO - Adicionando item: {'name': 'Alpha', 'quantity': 10, 'dimensions': (10, 10, 10)}

2023-03-24 15:13:57,969 - INFO - Adicionando item: {'name': 'Bravo', 'quantity': 1, 'dimensions': (150, 200, 140)}

2023-03-24 15:13:57,969 - INFO - Adicionando item: {'name': 'Charlie', 'quantity': 3, 'dimensions': (15, 20, 14)}

2023-03-24 15:13:57,978 - INFO - Caixa ideal: {'max_width': Decimal('295.000'), 'max_depth': Decimal('282.000'), 'max_height': Decimal('360.000')}

2023-03-24 15:13:57,978 - INFO - Resposta: {'statusCode': 200, 'body': {'melhor caixa': 'Caixa I', 'width': Decimal('300.000'), 'depth': Decimal('300.000'), 'height': Decimal('300.000')}}

Explore mais

3D bin packing problem in R
Tutorial of BRKGA for 3D-Bin Packing Problem
Biblioteca py3dbp - 3D Bin Packing
The Bin Packing Problem

Já resolveu esse problema de outras formas? Me conta!