Aula 4: Acelerando a Otimização com a Biblioteca DEAP

Seção 1: Abertura e Engajamento¶

1.1. Problema Motivador¶

Nas aulas anteriores, construímos algoritmos de otimização “do zero”. Embora seja um exercício fundamental para entender os mecanismos internos de um Algoritmo Genético ou Simulated Annealing, você deve ter notado a quantidade de código repetitivo e propenso a erros: gerenciar a população, implementar operadores de crossover e mutação, garantir que os formatos dos dados sejam consistentes, etc.

Imagine agora que você é um engenheiro de software em uma equipe ágil. Sua tarefa não é pesquisar novos algoritmos, mas sim aplicar a otimização para resolver um problema real da empresa, como alocar centenas de tarefas para dezenas de desenvolvedores, otimizando o tempo de entrega e o balanceamento da carga de trabalho. Escrever tudo do zero seria inviável, ineficiente e difícil de manter. Como podemos passar da teoria para a prática de forma rápida e robusta, focando no problema de negócio em vez de na infraestrutura do algoritmo?

1.2. Objetivos deste Capítulo¶

Ao final deste capítulo, você será capaz de:

• Estruturar um problema de otimização utilizando os componentes principais da biblioteca DEAP (creator, toolbox).

• Configurar e executar um algoritmo evolutivo completo com poucas linhas de código, utilizando os operadores e algoritmos pré-definidos do DEAP.

• Modelar um problema de alocação de recursos (um desafio comum em engenharia de software) e encontrar soluções ótimas usando o DEAP.

Seção 2: Fundamentos Teóricos (Versão Expressa)¶

DEAP (Distributed Evolutionary Algorithms in Python) é um framework que nos permite focar na formulação do problema, em vez de na mecânica do algoritmo de otimização. Ele trata os componentes de um algoritmo evolutivo como “blocos de montar” que podemos configurar e conectar.

A filosofia do DEAP gira em torno de dois conceitos centrais: o creator e a toolbox.

1. creator (O Arquiteto): Define a estrutura das suas soluções. Ele cria “fábricas” de classes. Você o usa para definir duas coisas essenciais:

   • A Fitness: Como a qualidade de uma solução será medida (ex: FitnessMin para minimizar um valor, FitnessMax para maximizar).

   • O Indivíduo: A estrutura de dados que representa uma solução (ex: uma lista de 0s e 1s, uma permutação de inteiros, etc.), já associada à sua Fitness.

2. toolbox (A Caixa de Ferramentas): Armazena as funções (operadores) que atuarão sobre os indivíduos. É um contêiner para os “verbos” do seu algoritmo. Nela, você “registra” as ferramentas que irá usar:

   • Geradores de Genes e Indivíduos: Funções para criar valores aleatórios (ex: random.randint(0, 1)) e para popular um indivíduo com esses genes.

   • Operadores Evolutivos: As funções de evaluate (sua função de fitness), mate (crossover), mutate (mutação) e select (seleção).

Com a estrutura definida no creator e as ferramentas registradas na toolbox, basta escolher um dos algorithms prontos do DEAP (como eaSimple, eaMuPlusLambda), passar a toolbox para ele, e o framework orquestra todo o fluxo evolutivo para você.

Seção 3: Laboratório Prático Guiado (Google Colab)¶

3.1. Roteiro do Notebook: workshop.ipynb¶

No laboratório prático, vamos parar de reinventar a roda e usar o poder do DEAP para resolver problemas de otimização de forma profissional. Primeiro, revisitaremos o Problema da Mochila para entender como a mesma lógica que implementamos manualmente pode ser expressa de forma muito mais concisa com o DEAP. Em seguida, aplicaremos esse conhecimento a um problema mais realista de engenharia de software: alocar tarefas a desenvolvedores para minimizar o tempo de conclusão e maximizar o balanceamento da carga de trabalho.

3.2. Estrutura do Laboratório¶

O notebook será dividido nas seguintes partes:

• Parte 1: Configuração do Ambiente: Instalação da biblioteca deap.

• Parte 2: DEAP em Ação - O Problema da Mochila:

  • Definição da estrutura (creator) para a Fitness e o Indivíduo (mochila).

  • Registro dos operadores (toolbox): geração de itens, avaliação, crossover, mutação e seleção.

  • Execução do algoritmo eaSimple e análise dos resultados.

• Parte 3: Problema de Engenharia de Software - Alocação de Tarefas:

  • Modelagem do problema: tarefas com estimativas de tempo e desenvolvedores.

  • Definição de uma nova estrutura de Indivíduo (uma lista onde o índice é a tarefa e o valor é o desenvolvedor alocado).

  • Criação de uma função de fitness mais complexa que penaliza o desbalanceamento de carga.

• Parte 4: Otimização e Análise dos Resultados:

  • Execução do algoritmo para encontrar a melhor alocação de tarefas.

  • Visualização da distribuição de trabalho na melhor solução encontrada, comparando-a com uma alocação aleatória.

Seção 4: Análise e Discussão dos Resultados¶

4.1. Interpretando os Resultados¶

Ao final do notebook, teremos dois resultados principais:

1. Solução da Mochila: O DEAP encontrará uma combinação de itens que maximiza o valor sem exceder o peso da mochila. O log de saída mostrará a evolução da melhor fitness (valor) ao longo das gerações. Por que a convergência não é sempre linear?

2. Plano de Alocação de Tarefas: A solução será um plano de trabalho ótimo. O resultado não será apenas um número de fitness, mas uma distribuição de tarefas legível. Vamos analisar: A solução encontrada parece “justa”? Existe algum desenvolvedor sobrecarregado ou ocioso? Como a função de fitness que projetamos influenciou esse resultado?

4.2. O “Porquê” das Decisões¶

• Por que usar creator? Ele padroniza a criação de indivíduos e fitness, garantindo que todos os operadores da toolbox recebam e retornem objetos no formato esperado. É o “contrato” que une o ecossistema DEAP.

• Por que registrar funções na toolbox em vez de chamá-las diretamente? A toolbox permite que os algoritmos do DEAP sejam genéricos. O eaSimple, por exemplo, não sabe qual função de crossover ele vai usar; ele apenas sabe que deve chamar toolbox.mate. Isso permite trocar um operador cxTwoPoint por um cxOnePoint sem alterar uma linha do código do algoritmo principal, promovendo alta coesão e baixo acoplamento.

• Por que a função de fitness da alocação de tarefas é mais complexa? Problemas do mundo real raramente têm um único objetivo. Nossa função de fitness combina dois objetivos: minimizar o tempo total (makespan) e minimizar a variação da carga de trabalho entre os desenvolvedores. Essa é uma introdução prática a problemas multi-objetivo, que exploraremos mais a fundo no futuro.

Seção 5: Síntese e Próximos Passos¶

5.1. Resumo do Capítulo¶

• Frameworks como o DEAP abstraem a implementação de baixo nível de algoritmos evolutivos, permitindo focar na modelagem do problema.

• A arquitetura do DEAP é baseada em um creator para definir a estrutura dos dados (indivíduos) e uma toolbox para registrar as operações (operadores).

• É possível modelar problemas complexos de engenharia de software, como alocação de recursos, definindo uma representação de indivíduo e uma função de fitness adequadas.

• A troca de operadores (crossover, mutação) é trivial no DEAP, facilitando a experimentação para encontrar a melhor configuração para um problema.

5.2. Preparação para o Próximo Bloco¶

Nesta aula, usamos o DEAP para encontrar uma única solução ótima. No entanto, muitos problemas do mundo real, como o Next Release Problem (NRP), envolvem trade-offs inerentes. Por exemplo, queremos maximizar o valor para o cliente, mas ao mesmo tempo minimizar o custo de desenvolvimento. Não existe uma única “melhor” solução, mas sim um conjunto de soluções ótimas que representam diferentes balanços entre esses objetivos. Na próxima aula, exploraremos a Otimização Multi-Objetivo e como algoritmos como o NSGA-II nos ajudam a encontrar a “Fronteira de Pareto” de soluções de trade-off.