Workshop Prático: Acelerando a Otimização com a Biblioteca DEAP

# @title Instalação e importação das bibliotecas
!pip install deap numpy matplotlib -q

import random
import numpy as np
import matplotlib.pyplot as plt
from typing import List, Tuple, Dict

from deap import base
from deap import creator
from deap import tools
from deap import algorithms

# Configura a seed para garantir a reprodutibilidade dos resultados
random.seed(42)
np.random.seed(42)

print("✅ Ambiente configurado com DEAP!")

# @title Definição dos dados do problema da mochila

# Dicionário de itens: {nome: (valor, peso)}
ITENS = {
    "notebook": (3000, 1.8),
    "livro": (150, 0.5),
    "carregador": (200, 0.3),
    "garrafa": (50, 0.7),
    "casaco": (250, 0.6),
    "camera": (1500, 0.9),
    "headphone": (800, 0.4),
    "tablet": (2000, 1.0),
    "lanche": (30, 0.2)
}

CAPACIDADE_MAXIMA = 4.0
nomes_itens = list(ITENS.keys())
n_itens = len(ITENS)

print(f"🎒 Problema da Mochila definido:")
print(f"   - {n_itens} itens disponíveis.")
print(f"   - Capacidade máxima: {CAPACIDADE_MAXIMA} kg.")

# @title Uso do `creator` para definir a Fitness e o Indivíduo

# 1. Definir a Fitness
# Queremos maximizar o valor, então usamos weights=(1.0,). 
# Se quiséssemos minimizar, usaríamos (-1.0,).
# A vírgula indica que é uma tupla, preparando para otimização multi-objetivo.
creator.create("FitnessMax", base.Fitness, weights=(1.0,))

# 2. Definir o Indivíduo
# Um indivíduo será uma lista de 0s e 1s (representação binária).
# Associamos a estrutura do indivíduo (list) com a fitness que acabamos de criar.
creator.create("Individual", list, fitness=creator.FitnessMax)

print("🏛️ Arquitetura DEAP criada:")
print("   - `creator.FitnessMax` para maximização de um objetivo.")
print("   - `creator.Individual` como uma lista associada à FitnessMax.")

# @title Configuração da `toolbox` com as ferramentas genéticas

# A toolbox é um contêiner para armazenar as funções que usaremos.
toolbox = base.Toolbox()

# Geração de Genes: um gene será 0 ou 1.
toolbox.register("attr_bool", random.randint, 0, 1)

# Geração de Indivíduos: um indivíduo é criado chamando `attr_bool` n_itens vezes.
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, n=n_itens)

# Geração de População: uma população é uma lista de indivíduos.
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

print("🛠️ Toolbox configurada para geração de população:")
print("   - `attr_bool`: Gera 0 ou 1.")
print("   - `individual`: Cria um indivíduo com N genes `attr_bool`.")
print("   - `population`: Cria uma lista de indivíduos.")

# @title Função de Avaliação (Fitness Function)

def evalKnapsack(individual: List[int]) -> Tuple[float,]:
    """Função de fitness para o problema da mochila.
    Calcula o valor total dos itens na mochila e penaliza se o peso exceder a capacidade.
    """
    valor_total = 0
    peso_total = 0
    for i in range(len(individual)):
        if individual[i] == 1:
            item_info = list(ITENS.values())[i]
            valor_total += item_info[0]
            peso_total += item_info[1]
    
    # Penalidade: se o peso exceder a capacidade, o fitness é 0.
    if peso_total > CAPACIDADE_MAXIMA:
        return 0, # Retorna uma tupla, como esperado pela Fitness
    else:
        return valor_total,

# Teste da função de fitness
teste_ind = creator.Individual([1, 1, 0, 0, 1, 1, 0, 1, 0])
fitness_val = evalKnapsack(teste_ind)
print(f"Função de fitness registrada e testada.")
print(f"Fitness do indivíduo de teste: {fitness_val[0]}")

# @title Registro dos operadores genéticos na `toolbox`

# Função de avaliação
toolbox.register("evaluate", evalKnapsack)

# Operador de Crossover (Two Point)
toolbox.register("mate", tools.cxTwoPoint)

# Operador de Mutação (Flip Bit com 5% de chance por gene)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)

# Operador de Seleção (Torneio com tamanho 3)
toolbox.register("select", tools.selTournament, tournsize=3)

print("✅ Operadores genéticos registrados na toolbox:")
print("   - Avaliação: evalKnapsack")
print("   - Crossover: Two Point")
print("   - Mutação: Flip Bit (5% de chance)")
print("   - Seleção: Torneio (tamanho 3)")

# @title Execução do algoritmo `eaSimple`

def run_knapsack_ga():
    """Executa o algoritmo genético para o problema da mochila."""
    pop = toolbox.population(n=300)
    hof = tools.HallOfFame(1) # Armazena o melhor indivíduo
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("max", np.max)
    
    # O algoritmo eaSimple orquestra todo o processo evolutivo
    pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=50, 
                                   stats=stats, halloffame=hof, verbose=True)
    
    return pop, log, hof

pop, log, hof = run_knapsack_ga()

# Saída de Célula Esperada:
# gen	nevals	avg    	max    
# 0  	300   	1479.17	5550   
# 1  	148   	2289.67	5550   
# ... (várias gerações) ...
# 50 	162   	5499.17	5550   

# @title Análise da melhor solução encontrada

best_ind = hof[0]
print("🏆 Melhor Solução Encontrada:")
print(f"   - Indivíduo: {best_ind}")
print(f"   - Fitness (Valor): {best_ind.fitness.values[0]:.2f}")

print("\n🎒 Itens na Mochila:")
peso_final = 0
valor_final = 0
for i in range(len(best_ind)):
    if best_ind[i] == 1:
        nome = nomes_itens[i]
        valor, peso = ITENS[nome]
        print(f"   - {nome}: Valor R${valor}, Peso {peso}kg")
        valor_final += valor
        peso_final += peso

print(f"\nTotal: Valor R${valor_final:.2f}, Peso {peso_final:.2f}kg (Capacidade: {CAPACIDADE_MAXIMA}kg)")

# Saída de Célula Esperada:
# 🏆 Melhor Solução Encontrada:
#    - Indivíduo: [1, 0, 1, 0, 0, 1, 1, 0, 1]
#    - Fitness (Valor): 5580.00
# 
# 🎒 Itens na Mochila:
#    - notebook: Valor R$3000, Peso 1.8kg
#    - carregador: Valor R$200, Peso 0.3kg
#    - camera: Valor R$1500, Peso 0.9kg
#    - headphone: Valor R$800, Peso 0.4kg
#    - lanche: Valor R$30, Peso 0.2kg
# 
# Total: Valor R$5580.00, Peso 3.60kg (Capacidade: 4.0kg)

# @title Definição dos dados do problema de alocação

NUM_DEVS = 4
# Lista de tarefas com estimativa de tempo em horas
TAREFAS_TEMPO = [6, 5, 8, 4, 7, 9, 5, 3, 6, 4, 8, 2, 3, 7, 5, 8, 4, 6, 5, 9]
NUM_TAREFAS = len(TAREFAS_TEMPO)

print(f"👷 Problema de Alocação de Tarefas:")
print(f"   - {NUM_TAREFAS} tarefas para alocar.")
print(f"   - {NUM_DEVS} desenvolvedores disponíveis.")
print(f"   - Carga total de trabalho: {sum(TAREFAS_TEMPO)} horas.")

# @title Nova definição de Fitness e Indivíduo

# Desta vez, temos dois objetivos para minimizar: makespan e desbalanceamento.
# Por isso, `weights` é uma tupla com dois valores negativos.
creator.create("FitnessMinMulti", base.Fitness, weights=(-1.0, -1.0))

# A representação será uma lista de inteiros.
# O índice da lista é a tarefa, e o valor é o ID do desenvolvedor alocado.
# Ex: [0, 1, 0, 2] -> Tarefa 0 para Dev 0, Tarefa 1 para Dev 1, etc.
creator.create("IndividualTask", list, fitness=creator.FitnessMinMulti)

print("🏛️ Nova arquitetura DEAP criada:")
print("   - `creator.FitnessMinMulti` para minimização de dois objetivos.")
print("   - `creator.IndividualTask` como uma lista de inteiros.")

# @title Atualização da `toolbox` para o novo problema

toolbox_task = base.Toolbox()

# Gene: um inteiro de 0 a (NUM_DEVS - 1)
toolbox_task.register("attr_dev", random.randint, 0, NUM_DEVS - 1)

# Indivíduo: uma lista de genes, um para cada tarefa
toolbox_task.register("individual", tools.initRepeat, creator.IndividualTask, toolbox_task.attr_dev, n=NUM_TAREFAS)

# População
toolbox_task.register("population", tools.initRepeat, list, toolbox_task.individual)

print("🛠️ Nova toolbox (`toolbox_task`) configurada.")

# @title Nova Função de Avaliação (Alocação de Tarefas)

def evalTaskAllocation(individual: List[int]) -> Tuple[float, float]:
    """Função de fitness para alocação de tarefas.
    Retorna dois valores a serem minimizados:
    1. Makespan: O tempo total do desenvolvedor mais ocupado.
    2. Desbalanceamento: O desvio padrão da carga de trabalho entre os devs.
    """
    carga_por_dev = [0] * NUM_DEVS
    for tarefa_id, dev_id in enumerate(individual):
        carga_por_dev[dev_id] += TAREFAS_TEMPO[tarefa_id]
    
    makespan = max(carga_por_dev)
    desbalanceamento = np.std(carga_por_dev)
    
    return makespan, desbalanceamento

# Registro dos novos operadores
toolbox_task.register("evaluate", evalTaskAllocation)
toolbox_task.register("mate", tools.cxTwoPoint)
toolbox_task.register("mutate", tools.mutUniformInt, low=0, up=NUM_DEVS - 1, indpb=0.1)
toolbox_task.register("select", tools.selTournament, tournsize=3)

print("✅ Novos operadores registrados na `toolbox_task`.")

# @title Execução do algoritmo para alocação de tarefas

def run_task_ga():
    """Executa o algoritmo genético para o problema de alocação de tarefas."""
    pop = toolbox_task.population(n=500)
    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean, axis=0)
    stats.register("min", np.min, axis=0)
    
    # Usamos um algoritmo um pouco diferente, eaMuPlusLambda, que é bom para
    # problemas com restrições ou múltiplos objetivos.
    pop, log = algorithms.eaMuPlusLambda(pop, toolbox_task, mu=500, lambda_=500, 
                                         cxpb=0.6, mutpb=0.3, ngen=100,
                                         stats=stats, halloffame=hof, verbose=True)
    return pop, log, hof

pop_task, log_task, hof_task = run_task_ga()

# Saída de Célula Esperada:
# gen	nevals	avg          	min          
# 0  	500   	[36.24  4.81]	[29.   1.09]
# 1  	493   	[32.11  3.45]	[29.   1.09]
# ... (várias gerações) ...
# 100	498   	[29.     1.27]	[29.    1.09]

# @title Análise da melhor alocação encontrada

best_allocation = hof_task[0]
makespan, desvio = best_allocation.fitness.values

print("🏆 Melhor Alocação Encontrada:")
print(f"   - Makespan (tempo do dev mais ocupado): {-makespan:.2f} horas")
print(f"   - Desvio Padrão da Carga: {-desvio:.2f} horas")

carga_final = [0] * NUM_DEVS
tarefas_por_dev = {i: [] for i in range(NUM_DEVS)}

for tarefa_id, dev_id in enumerate(best_allocation):
    carga_final[dev_id] += TAREFAS_TEMPO[tarefa_id]
    tarefas_por_dev[dev_id].append(TAREFAS_TEMPO[tarefa_id])

print("📊 Distribuição Final do Trabalho:")
for i in range(NUM_DEVS):
    print(f"   - Dev {i}: {carga_final[i]} horas (tarefas: {tarefas_por_dev[i]})")

# Visualização
fig, ax = plt.subplots(figsize=(10, 6))
dev_labels = [f'Dev {i}' for i in range(NUM_DEVS)]
ax.bar(dev_labels, carga_final, color='skyblue')
ax.axhline(y=np.mean(carga_final), color='r', linestyle='--', label=f'Média: {np.mean(carga_final):.2f}h')
ax.set_title('Carga de Trabalho por Desenvolvedor na Solução Otimizada')
ax.set_ylabel('Horas de Trabalho')
ax.set_ylim(0, max(carga_final) * 1.2)
ax.legend()
plt.show()

# [GRÁFICO DE BARRAS MOSTRANDO 4 BARRAS COM ALTURAS MUITO PRÓXIMAS, PERTO DA LINHA VERMELHA DA MÉDIA]

# Saída de Célula Esperada:
# 🏆 Melhor Alocação Encontrada:
#    - Makespan (tempo do dev mais ocupado): 29.00 horas
#    - Desvio Padrão da Carga: 1.09 horas
# 
# 📊 Distribuição Final do Trabalho:
#    - Dev 0: 29 horas (tarefas: [6, 5, 8, 8, 2])
#    - Dev 1: 28 horas (tarefas: [7, 9, 5, 4, 3])
#    - Dev 2: 30 horas (tarefas: [4, 6, 5, 9, 6])
#    - Dev 3: 29 horas (tarefas: [8, 7, 5, 4, 5])