Workshop Prático: Da Formulação à Solução com DEAP

# @title Instalação e importação das bibliotecas

!pip install deap -q

import random
import numpy as np

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

print("✅ Ambiente configurado com DEAP!")

# @title Parâmetros do Problema da Mochila

# Dicionário de itens: {nome: (valor, peso)}
ITENS = {
    "Laptop": (1500, 2),
    "Livro": (300, 1),
    "Garrafa de Água": (50, 0.5),
    "Câmera": (1200, 1.5),
    "Casaco": (400, 1),
    "Lanche": (100, 0.2),
    "Carregador Portátil": (500, 0.8),
    "Fone de Ouvido": (600, 0.3)
}

# Capacidade máxima da mochila em kg
CAPACIDADE_MAXIMA = 4.0

# Extrair listas de nomes, valores e pesos para facilitar o acesso
nomes_itens = list(ITENS.keys())
valores_itens = [item[0] for item in ITENS.values()]
pesos_itens = [item[1] for item in ITENS.values()]
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 Configuração do `creator` e `toolbox`

# 1. Usando o `creator` para definir a estrutura do fitness e do indivíduo
# Queremos maximizar o valor, então os pesos do fitness são positivos (1.0).
creator.create("FitnessMax", base.Fitness, weights=(1.0,))

# Nosso indivíduo será uma lista de 0s e 1s (representação binária).
creator.create("Individual", list, fitness=creator.FitnessMax)

# 2. Usando a `toolbox` para registrar as funções genéticas
toolbox = base.Toolbox()

# -- Geração de Indivíduos e População --

# Função `attr_bool`: gera um gene (0 ou 1). É o bloco de construção do nosso indivíduo.
toolbox.register("attr_bool", random.randint, 0, 1)

# Função `individual`: cria um indivíduo completo (cromossomo).
# Usa `tools.initRepeat` para chamar `attr_bool` n_itens vezes.
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, n=n_itens)

# Função `population`: cria a população inicial, uma lista de indivíduos.
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

print("🛠️  `creator` e `toolbox` configurados.")
print("   - Fitness: Maximizar um objetivo.")
print("   - Representação do Indivíduo: Lista binária (0s e 1s).")

# @title Implementação da Função de Fitness

def evalKnapsack(individual: list) -> tuple:
    """Função de fitness para o Problema da Mochila.

    Calcula o valor total dos itens no indivíduo. Se o peso total exceder
    a capacidade, retorna um fitness de 0 (penalidade).

    Parameters:
        individual: Uma lista de 0s e 1s representando a solução.

    Returns:
        Um tuple contendo o valor total (o fitness).
    """
    valor_total = 0.0
    peso_total = 0.0
    for i in range(len(individual)):
        if individual[i] == 1:
            valor_total += valores_itens[i]
            peso_total += pesos_itens[i]

    # Aplica a penalidade se a restrição de peso for violada
    if peso_total > CAPACIDADE_MAXIMA:
        return 0,  # Retorna uma tupla, pois o DEAP espera isso

    return valor_total,

# Testando a função com um indivíduo de exemplo
teste_ind = [1, 1, 0, 1, 0, 0, 0, 0] # Laptop, Livro, Câmera
teste_peso = pesos_itens[0] + pesos_itens[1] + pesos_itens[3]
teste_valor = valores_itens[0] + valores_itens[1] + valores_itens[3]
print(f"Indivíduo de teste: {teste_ind}")
print(f"Peso: {teste_peso:.2f} kg (inválido, > {CAPACIDADE_MAXIMA} kg)")
print(f"Fitness esperado: 0 (devido à penalidade)")
print(f"Fitness calculado: {evalKnapsack(teste_ind)}")

teste_ind_valido = [0, 1, 1, 1, 1, 1, 0, 0] # Livro, Garrafa, Câmera, Casaco, Lanche
teste_peso_valido = sum(pesos_itens[i] for i in [1,2,3,4,5])
print(f"\nIndivíduo de teste válido: {teste_ind_valido}")
print(f"Peso: {teste_peso_valido:.2f} kg (válido)")
print(f"Fitness calculado: {evalKnapsack(teste_ind_valido)}")

# @title Registro dos operadores na `toolbox`

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

# Operador de Crossover (Recombinação)
# `cxTwoPoint` combina dois indivíduos trocando um segmento entre dois pontos.
toolbox.register("mate", tools.cxTwoPoint)

# Operador de Mutação
# `mutFlipBit` inverte o valor de um ou mais bits (genes) em um indivídu-o.
# `indpb=0.05` significa que cada gene tem 5% de chance de ser invertido.
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)

# Operador de Seleção
# `selTournament` seleciona os melhores indivíduos através de um "torneio".
# `tournsize=3` significa que 3 indivíduos são escolhidos aleatoriamente, e o melhor deles vence.
toolbox.register("select", tools.selTournament, tournsize=3)

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

# @title Execução e análise dos resultados

def main():
    random.seed(42) # Para reprodutibilidade

    # Cria a população inicial
    pop = toolbox.population(n=300) # 300 indivíduos

    # HallOfFame armazena o melhor indivíduo encontrado durante a evolução
    hof = tools.HallOfFame(1)
    
    # Configura as estatísticas que queremos coletar
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("std", np.std)
    stats.register("min", np.min)
    stats.register("max", np.max)

    # Executa o algoritmo genético
    # CXPB: Probabilidade de Crossover
    # MUTPB: Probabilidade de Mutação
    # NGEN: Número de Gerações
    pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40, 
                                   stats=stats, halloffame=hof, verbose=True)

    return pop, log, hof

if __name__ == "__main__":
    pop, log, hof = main()

# @title Inspeção da melhor solução encontrada

best_solution = hof[0]
print("🏆 Melhor Solução Encontrada:")
print(f"   - Representação: {best_solution}")
print(f"   - Fitness (Valor Total): {best_solution.fitness.values[0]:.2f} R$")

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

print("\n📊 Resumo Final:")
print(f"   - Valor Total: {valor_final:.2f} R$")
print(f"   - Peso Total: {peso_final:.2f} kg (Capacidade: {CAPACIDADE_MAXIMA} kg)")

# @title Implementação da Função de Fitness

def evalKnapsack(individual: list) -> tuple:
    """Função de fitness para o Problema da Mochila.

    Calcula o valor total dos itens no indivíduo. Se o peso total exceder
    a capacidade, retorna um fitness de 0 (penalidade).

    Parameters:
        individual: Uma lista de 0s e 1s representando a solução.

    Returns:
        Um tuple contendo o valor total (o fitness).
    """
    valor_total = 0.0
    peso_total = 0.0
    for i in range(len(individual)):
        if individual[i] == 1:
            valor_total += valores_itens[i]
            peso_total += pesos_itens[i]

    # Aplica a penalidade se a restrição de peso for violada
    if peso_total > CAPACIDADE_MAXIMA:
        return 0,  # Retorna uma tupla, pois o DEAP espera isso

    return valor_total,

# Testando a função com um indivíduo de exemplo
teste_ind = [1, 1, 0, 1, 0, 0, 0, 0] # Laptop, Livro, Câmera
teste_peso = pesos_itens[0] + pesos_itens[1] + pesos_itens[3]
teste_valor = valores_itens[0] + valores_itens[1] + valores_itens[3]
print(f"Indivíduo de teste: {teste_ind}")
print(f"Peso: {teste_peso:.2f} kg (inválido, > {CAPACIDADE_MAXIMA} kg)")
print(f"Fitness esperado: 0 (devido à penalidade)")
print(f"Fitness calculado: {evalKnapsack(teste_ind)}")

teste_ind_valido = [0, 1, 1, 1, 1, 1, 0, 0] # Livro, Garrafa, Câmera, Casaco, Lanche
teste_peso_valido = sum(pesos_itens[i] for i in [1,2,3,4,5])
print(f"\nIndivíduo de teste válido: {teste_ind_valido}")
print(f"Peso: {teste_peso_valido:.2f} kg (válido)")
print(f"Fitness calculado: {evalKnapsack(teste_ind_valido)}")