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!