🎯 Algoritmos Genéticos

Em poucas palavras

Definição técnica ou simplificada do conceito.

---

📝 Notas e Desenvolvimento

---

🔗 Conexões e Contexto

• Atlas: MdC - Programação, MdC - Matemática
• Notas Relacionadas:

---

📚 Referências e Fontes

Links Externos

• Youtube
• Wikipedia

Citações Diretas

📂 Outros Conteúdos Preservados

Informações Gerais

Contexto Histórico

• Teoria da Evolução:
  • Charles Darwin, em A Origem das Espécies (1859), formalizou que a evolução é impulsionada pela sobrevivência diferencial. Não é o puro acaso que dita o sucesso, mas a interação determinística entre as características do indivíduo e a pressão do ambiente.
  • Variação: Nenhuma população é homogênea. Existem variações morfológicas e comportamentais.
  • Contingentes da Natureza: Escassez de recursos, mudanças climáticas e predação atuam como “filtros”.
  • Seleção Natural: Indivíduos com variações adaptadas ao seu nicho possuem maior probabilidade de sobrevivência e sucesso reprodutivo.
• Teoria do DNA:
  • Mendel descobriu que a herança não é uma “mistura” fluida, mas sim composta por unidades discretas.
  • Segregação dos Fatores: Cada indivíduo possui um par de genes para cada característica, e estes se separam na formação das células reprodutivas.
  • Independência: Diferentes características são herdadas independentemente umas das outras (base para o que fazemos ao trocar partes de um vetor no AG)
• Teoria da Mutação:
  • No início do século XX, De Vries observou variações súbitas em plantas (Oenothera lamarckiana) que não eram explicadas apenas pela recombinação de Mendel.
  • Mutacionismo: Introduziu o conceito de que novas características surgem por alterações espontâneas e bruscas no material genético, não apenas por herança gradual.
  • Saltacionismo: A ideia de que a evolução pode dar “saltos” através dessas mutações.
• Idealização dos Algoritmos Genéticos:
  • John H. Holland desenvolveu principalmente a Teoria da Adaptação.
  • A premissa é elegante: em vez de tentar resolver um problema complexo “no braço”, criamos uma população de soluções candidatas e deixamos que as forças da evolução (seleção, cruzamento e mutação) filtrem as melhores ao longo das gerações.
• Algoritmos Genéticos vs Algoritmos evolutivos:
  • Algoritmos Evolutivos (AEs): É o termo genérico para todos os algoritmos de busca e otimização baseados na evolução biológica. Inclui Estratégias Evolutivas, Programação Evolutiva e Programação Genética.
  • Algoritmos Genéticos (AGs): são uma subcategoria dentro dos AEs. Caracteriza-se historicamente pelo uso de representações discretas (strings binárias) e pela forte ênfase no operador de crossover (recombinação).

Conceitos Fundamentais

• Pilares dos algoritmos genéticos:
  • Variação (Diversidade): Garantida pela inicialização randômica e pela mutação. Sem ela, ocorre a “convergência prematura”.
  • Hereditariedade (Explotação): Garantida pelo crossover. Permite que “blocos construtores” (building blocks) de soluções de sucesso sejam propagados.
  • Seleção (Pressão Direcional): Garantida pela função Fitness. Empurra a população estocástica em direção às regiões ótimas do espaço de busca.
• Terminologia:
  • Indivíduo (ou Cromossomo): Representa uma única solução candidata para o problema.
  • Gene: É a menor unidade de informação de um indivíduo. Representa uma variável específica ou uma característica da solução
  • População: O conjunto de todos os indivíduos em uma determinada iteração (geração).
  • Locus: A posição específica de um gene dentro do cromossomo.
  • Alelo: O valor específico que um gene assume em um determinado locus
  • Função de Aptidão (Fitness): Uma função matemática que avalia o desempenho de um indivíduo.
  • Geração: Uma iteração completa do algoritmo, desde a seleção até a criação de novos indivíduos que substituirão a população anterior.

Ciclo de um Algoritmo Genético Simples

graph TD
    A([Início]) --> B[Inicializar População Aleatória]
    B --> C[Decodificar Genótipos em Fenótipos]
    C --> D(Avaliação: Calcular Fitness de cada indivíduo)
    D --> E{Critério de Parada?<br>Ex: Gerações Max ou Erro Min}
    E -- Sim --> F([Fim: Retorna o Melhor Indivíduo global])
    E -- Não --> G[Seleção de Pais]
    G --> H[Recombinação - Crossover]
    H --> I[Mutação]
    I --> J[Substituição - Nova Geração]
    J --> C

• Etapas:
  • POPULAÇÃO INICIAL: Criação aleatória de um conjunto de indivíduos (soluções candidatas). É o ponto de partida no espaço de busca.
  • CÁLCULO APTIDÃO: Cada indivíduo é avaliado e recebe uma nota baseada em quão bem ele resolve o problema objetivo.
  • REPRODUÇÃO: Os indivíduos com melhor aptidão têm maior chance de serem selecionados como pais para gerar descendentes.
  • MUTAÇÃO: Pequenas alterações aleatórias e espontâneas são introduzidas nos genes dos descendentes, visando manter a diversidade genética e evitar que o algoritmo fique preso em ótimos locais.
  • SELEÇÃO: Uma nova população é formada, composta pelos melhores descendentes (e, em alguns casos, pelos melhores indivíduos da geração anterior), substituindo a população antiga.
  • O CICLO EVOLUTIVO: A seta circular no centro do diagrama indica que o processo de Avaliação, Reprodução, Mutação e Nova Seleção se repete por várias gerações até que um critério de parada seja atingido.

Representação de Indivíduos e Genes

1. Representação Binária (A Clássica de Holland)

Historicamente, é a representação mais comum e a que deu origem aos teoremas fundamentais dos AGs (como o Teorema dos Esquemas). O cromossomo é um vetor estático de booleanos (0s e 1s).

• Quando usar: Problemas de decisão (Sim/Não), problemas de seleção de características (Feature Selection para modelos de Inteligência Artificial) ou problemas da Mochila (Knapsack Problem).
• Exemplo Prático (Engenharia/Redes): Otimização do consumo de energia em uma rede de sensores sem fio. Imagine que temos 8 sensores em um ambiente. Queremos descobrir qual subconjunto de sensores deve permanecer ativo para cobrir a maior área possível gastando o mínimo de bateria.
  • Genótipo: [1, 0, 0, 1, 1, 0, 1, 0]
  • Decodificação (Fenótipo): Os sensores nos Loci 1, 4, 5 e 7 estão LIGADOS. Os demais estão em modo sleep (desligados).
• Ponto de Atenção para a Pós-Graduação (O Hamming Cliff): Se usarmos binário para representar números inteiros contínuos (ex: 0111 = 7 e 1000 = 8), a transição do 7 para o 8 exige a mutação de todos os 4 bits simultaneamente, criando uma “barreira” no espaço de busca. A solução clássica para isso é usar a codificação Código Gray em vez de binário puro.

2. Representação Real / Ponto Flutuante

Aqui, os genes perdem a restrição discreta e assumem valores contínuos (números de ponto flutuante). É a representação mais natural para a imensa maioria dos problemas de otimização em engenharia.

• Quando usar: Otimização de funções matemáticas contínuas, ajuste de parâmetros de controle dinâmico, ou otimização de pesos em arquiteturas de agentes inteligentes e redes neurais.
• Exemplo Prático (Controle e Automação): Sintonia de um controlador PID (Proporcional, Integral, Derivativo) para um motor elétrico. O indivíduo precisa definir as três constantes de ganho ($K_p$, $K_i$, $K_d$).
  • Genótipo: [12.45, 0.08, 3.14]
  • Decodificação (Fenótipo): $K_p=12.45$, $K_i=0.08$ e $K_d=3.14$. O fitness será calculado simulando o motor com esses ganhos e medindo o erro de regime e o overshoot.
• Vantagem: Evita a perda de precisão matemática que ocorreria ao converter números reais em longas cadeias binárias.

3. Representação Inteira e Permutação

Utilizada quando a solução é uma sequência de eventos, categorias ou rotas, onde a ordem dos fatores altera o produto ou onde itens não podem ser fracionados.

• Quando usar: Problemas de escalonamento de tarefas (Job-Shop Scheduling), roteamento de pacotes/veículos e o clássico Problema do Caixeiro Viajante (TSP - Traveling Salesman Problem).
• Exemplo Prático (Otimização Combinatória): Uma placa de circuito impresso onde um braço robótico precisa perfurar 6 furos em locais específicos. Qual a ordem de perfuração que minimiza o tempo total de deslocamento do braço?
  • Genótipo (Permutação): [3, 1, 6, 2, 5, 4]
  • Decodificação (Fenótipo): O robô vai primeiro ao furo 3, depois ao 1, depois ao 6, etc.
• Ponto de Atenção para a Pós-Graduação: Na permutação, cada gene só pode aparecer exatamente uma vez. Se você aplicar um crossover clássico cortando dois pais ao meio e juntando as metades, você inevitavelmente criará indivíduos inválidos (com cidades duplicadas e cidades faltando). Isso força a introdução de operadores matemáticos especializados, como o Order Crossover (OX) ou o Partially Mapped Crossover (PMX).

4. Representação em Árvore (Programação Genética - GP)

Esta é a representação mais complexa e fascinante. Idealizada por John Koza, ela emancipa o AG da ideia de otimizar parâmetros e passa a otimizar a própria estrutura de um programa, equação ou circuito lógico. O indivíduo tem tamanho dinâmico e formato hierárquico.

• Quando usar: Regressão simbólica (encontrar a fórmula matemática que explica um conjunto de dados complexos, como leituras de sensores), síntese de circuitos elétricos ou geração de regras para agentes autônomos.
• Exemplo Prático (Regressão Simbólica): Queremos que o algoritmo descubra a relação matemática entre a temperatura ($T$) e a pressão ($P$) lidas por um sensor. O AG não otimiza variáveis, ele constrói a função.
  • Estrutura: Os nós internos são Funções (operadores como +, *, sin, exp). As folhas são Terminais (variáveis como $T$, $P$, ou constantes como $2.5$).
  • Genótipo (Árvore): Representando a equação $y=(T\times 2.5)+\sin (P)$

graph TD
    A((+)) --> B(( * ))
    A --> C((sin))
    B --> D[T]
    B --> E[2.5]
    C --> F[P]
    
    classDef func fill:#e1f5fe,stroke:#039be5,stroke-width:2px;
    classDef term fill:#f3e5f5,stroke:#8e24aa,stroke-width:2px;
    class A,B,C func;
    class D,E,F term;

• Dinâmica: O crossover aqui ocorre trocando sub-árvores inteiras entre dois indivíduos, permitindo que as fórmulas cresçam, encolham e se adaptem até “encaixarem” nos dados de treinamento.

Operadores de Seleção

A fase de seleção é onde a “sobrevivência dos mais aptos” de Darwin é quantificada. O objetivo é escolher os indivíduos da geração atual que terão o direito de passar seu material genético adiante. Indivíduos piores não são sumariamente descartados; eles apenas têm uma probabilidade menor de serem escolhidos.

1. Seleção por Roleta (Proporcional à Aptidão)

É o método clássico original, muito didático, mas que raramente usamos em problemas reais complexos hoje em dia. A ideia é que cada indivíduo ganha uma “fatia” de uma roleta viciada, cujo tamanho é estritamente proporcional ao seu valor de fitness.

• Matemática: A probabilidade de seleção $P_i$ de um indivíduo $i$ é:

  $P_i=\frac{f_i}{{\sum }_{j=1}^N{f}_j}$

  (Onde $f_i$ é o fitness do indivíduo e $N$ é o tamanho da população).

• O Problema Crítico (Super-Indivíduo): Imagine uma população inicial aleatória onde quase todos têm nota 2, mas um indivíduo sortudo tem nota 100. Na roleta, ele ocupará 90% do espaço. Ele será selecionado dezenas de vezes, preenchendo a próxima geração com clones seus e matando a diversidade prematuramente (Convergência Prematura).

• O Segundo Problema (Estagnação Tardia): Perto do fim da otimização, todos os indivíduos são bons e têm fitness parecido (ex: 990, 992, 995). Na roleta, as fatias ficam quase idênticas, e a seleção vira uma escolha praticamente aleatória, perdendo a pressão para encontrar o ótimo global exato.

2. Seleção por Ranking (Ajuste de Escala)

Criado especificamente para resolver os dois problemas da Roleta. O Ranking ignora o valor absoluto do fitness.

• Mecânica: A população é ordenada do pior (posição 1) ao melhor (posição $N$). A probabilidade de seleção é calculada com base na posição (rank), e não na nota.
• Vantagem em Pós-Graduação: Resolve o problema do super-indivíduo. Se o melhor tem nota 100 e o segundo melhor tem nota 10, a distância absoluta é 90, mas no ranking, eles são apenas o “1º” e o “2º”. A pressão seletiva é mantida constante durante toda a execução do algoritmo, do início ao fim.

3. Seleção por Torneio (O Padrão da Indústria)

Atualmente, é o método mais utilizado em engenharia e aplicações reais devido à sua elegância, eficiência computacional e facilidade de ajuste.

• Mecânica:

  1. Sorteie aleatoriamente $k$ indivíduos da população (onde $k$ é o tamanho do torneio, geralmente $k=2$ ou $k=3$).
  2. Coloque-os para “batalhar”. O indivíduo com o maior fitness vence e vai para a piscina de cruzamento.
  3. Devolva os indivíduos à população (com reposição) e repita até ter pais suficientes.

• Por que é o favorito?

  • Eficiência: Não exige calcular a soma de todos os fitness (como na Roleta) nem ordenar um vetor inteiro (como no Ranking). $O(1)$ por seleção.
  • Controle Fino: O parâmetro $k$ é o “botão de volume” da pressão seletiva. Se $k=2$, a pressão é suave. Se $k=10$, apenas os mais fortes sobrevivem e a diversidade cai rápido.
  • Robustez Matemática: Lida perfeitamente com valores de fitness negativos (o que quebra a matemática da Roleta).

4. Elitismo (O Salva-Vidas Complementar)

O Elitismo não é um método de seleção de pais, mas sim uma política de sobrevivência intergeracional.

• Conceito: O cruzamento e a mutação são operadores destrutivos. É perfeitamente possível que os filhos dos dois melhores indivíduos da geração atual sejam piores que os pais (azar na quebra do cromossomo). Para garantir que o algoritmo não “esqueça” a melhor solução já encontrada, o Elitismo copia diretamente os $E$ melhores indivíduos da geração $t$ para a geração $t+1$, imunes à mutação.

Operadores de Cruzamento

O objetivo do Crossover é pegar duas soluções parentais promissoras e trocar informações entre elas na esperança de que os filhos herdem o melhor de ambos. A probabilidade de cruzamento ($P_c$) é tipicamente alta, variando de $70\%$ a $90\%$.

1. Cruzamento de Ponto Simples (Single-Point Crossover)

O método mais antigo e intuitivo, geralmente aplicado em codificação binária ou inteira.

• Mecânica: Sorteia-se aleatoriamente um único ponto de corte (locus $k$) ao longo do cromossomo de tamanho $L$, onde $1\le k<L$. Tudo que está à direita do ponto de corte é trocado entre os pais para formar dois filhos.
• Exemplo:
  • Pai 1: [ A B C | D E F ]
  • Pai 2: [ 1 2 3 | 4 5 6 ]
  • Filho 1: [ A B C | 4 5 6 ]
  • Filho 2: [ 1 2 3 | D E F ]
• O Gargalo (Viés Posicional): Este método sofre de um problema grave de topologia. Genes que estão fisicamente distantes no vetor (ex: posições 1 e 6) têm uma probabilidade enorme de serem separados (ruptura do bloco construtor). Se a inteligência da sua solução IoT depende de uma combinação estrita entre o primeiro parâmetro (bateria) e o último (potência do rádio), o ponto simples destruirá essa combinação na maioria das vezes.

2. Cruzamento de N-Pontos (Foco no 2-Pontos)

Uma generalização natural para reduzir o viés do ponto simples. Na prática, o Cruzamento de 2 Pontos é o mais utilizado quando se lida com vetores discretos.

• Mecânica: Sorteiam-se dois pontos de corte. Os segmentos intermediários são trocados, tratando o cromossomo conceitualmente como um anel contínuo (circular) em vez de uma linha reta.
• Exemplo:
  • Pai 1: [ A B | C D | E F ]
  • Pai 2: [ 1 2 | 3 4 | 5 6 ]
  • Filho 1: [ A B | 3 4 | E F ]
• Vantagem: Reduz significativamente o viés posicional. Genes nas extremidades agora podem ser herdados juntos.
• O Gargalo: Se aumentarmos muito o número de pontos (ex: cruzamento de 4 ou 5 pontos em um vetor pequeno), o operador perde seu caráter de “herança de blocos” e passa a agir quase como uma embaralhação aleatória, perdendo o propósito de explorar padrões.

3. Cruzamento Uniforme (Uniform Crossover)

Aqui, abandonamos a ideia de “cortar” o cromossomo. Cada gene é avaliado individualmente.

• Mecânica: Gera-se uma “Máscara Binária” do mesmo tamanho do cromossomo, jogando uma moeda (geralmente viciada em $p=0.5$) para cada locus. Se a máscara for 1, o Filho 1 recebe o gene do Pai 1. Se for 0, recebe do Pai 2. O Filho 2 recebe o inverso.
• Exemplo Máscara: [ 1, 0, 0, 1, 1, 0 ]
  • Pai 1: [ A B C D E F ]
  • Pai 2: [ 1 2 3 4 5 6 ]
  • Filho 1: [ A 2 3 D E 6 ]
• Vantagem: Elimina em 100% o viés posicional. A distância física entre os genes no vetor se torna completamente irrelevante. Excelente para problemas onde não sabemos a correlação entre as variáveis.
• O Gargalo (Alta Taxa de Ruptura): É o operador mais destrutivo. Ele quebra facilmente building blocks longos que a evolução demorou dezenas de gerações para construir. É uma excelente ferramenta exploratória no início, mas pode impedir a convergência fina no final da otimização.

4. Cruzamento para Pontos Flutuantes (Representação Real)

Quando nossos parâmetros são contínuos (ex: variáveis de configuração no Arduino, pesagens de balanceamento na AWS), cruzar partes binárias destrói a semântica do número. Precisamos de operadores aritméticos.

• Média Aritmética Simples:
  • O filho é literalmente a média entre os pais: $O_1=\frac{P_1+P_2}{2}$.
  • Problema Grave: Este método apenas “encolhe” o espaço de busca em direção ao centro geométrico da população. Ele é puramente explotatório e perde a capacidade de explorar os extremos do espaço.
• Cruzamento BLX-$\alpha$ (Blend Crossover): O padrão ouro para variáveis reais, desenvolvido por Eshelman e Schaffer. Ele expande o intervalo de busca proporcionalmente à distância entre os pais.

  • Mecânica: Para cada gene real (variável), calcula-se a distância absoluta entre o Pai 1 e o Pai 2: $d=|P_1-P_2|$.

  • O filho será sorteado de uma distribuição uniforme dentro do intervalo:

    $[\min (P_1,P_2)-\alpha \cdot d,\max (P_1,P_2)+\alpha \cdot d]$

  • Onde $\alpha$ é um parâmetro de controle (geralmente $\alpha =0.5$).

  • Vantagem em Pós-Graduação: Se os pais estão longe (alta diversidade), o filho pode nascer em uma área bem ampla. Se os pais convergiram e estão próximos, o filho nascerá muito próximo a eles, permitindo um ajuste fino (sintonia local) automático sem precisarmos mexer no algoritmo.

  • O Gargalo: O BLX-$\alpha$ pode gerar valores fora dos limites físicos do problema (ex: gerar um tempo de

Operadores de Mutação

A escolha da mutação, assim como o cruzamento, é estritamente dependente da representação (genótipo) escolhida para o problema.

1. Representação Binária: Mutação Bit-Flip

É a mutação mais rudimentar, diretamente herdada da biologia (onde uma base de DNA é trocada).

• Mecânica: O algoritmo percorre cada gene (bit) de cada indivíduo da população e “joga um dado” com probabilidade $P_m$. Se o evento ocorrer, o bit é invertido ($0\to 1$ ou $1\to 0$).
• Exemplo:
  • Original: [ 1, 0, 0, 1, 1 ]
  • Mutado (locus 3): [ 1, 0, 1, 1, 1 ]
• O Gargalo (O Efeito Avalanche do Genótipo-Fenótipo): Se você estiver usando binário puro para representar números inteiros, o Bit-Flip pode ser perigoso. Mudar o último bit de 1000 (8) para 1001 (9) causa uma alteração de apenas 1 unidade no fenótipo. Mas mudar o primeiro bit de 1000 (8) para 0000 (0) causa um salto massivo no espaço de busca. A mutação perde a capacidade de fazer ajustes finos precisos se a codificação não for robusta (como o Código Gray).

2. Representação de Permutação: Mutação Swap (Troca)

Em problemas combinatórios (como o Caixeiro Viajante - TSP ou Roteamento de Veículos), não podemos simplesmente alterar um valor, pois isso duplicaria uma cidade e excluiria outra, criando uma rota inválida. A mutação deve preservar a integridade da permutação.

• Mecânica: Sorteiam-se aleatoriamente dois loci diferentes no cromossomo e trocam-se os alelos de posição.
• Exemplo (Rota de Cidades):
  • Original: [ A, B, C, D, E, F ]
  • Mutado (troca 2 e 5): [ A, E, C, D, B, F ]
• Vantagem: É computacionalmente barata e garante 100% de validade da solução.
• O Gargalo (Baixa Disrupção): Em um problema de roteamento com 5.000 cidades, trocar apenas duas cidades de lugar causa um impacto microscópico na topologia da rota. Muitas vezes, o Swap não tem força suficiente para tirar o algoritmo de um ótimo local profundo.

3. Representação de Permutação: Mutação por Inversão

Para resolver a fraqueza do Swap, a Inversão atua em escala maciça, alterando drasticamente a ordem de uma sub-rota inteira.

• Mecânica: Sorteiam-se dois pontos de corte no cromossomo. A ordem de todos os genes contidos entre esses dois pontos é invertida.
• Exemplo:
  • Original: [ 1, | 2, 3, 4, 5, | 6, 7 ]
  • Mutado (inverte miolo): [ 1, | 5, 4, 3, 2, | 6, 7 ]
• O Gargalo (Extrema Disrupção): Ao passo que o Swap é fraco demais, a Inversão pode ser destrutiva demais. Ela quebra múltiplas conexões (edges) de uma vez só. É excelente no início da otimização, mas pode impedir que o algoritmo assente em uma rota perfeita nas gerações finais.

4. Representação Real: Mutação Gaussiana

Para parâmetros contínuos (como constantes de engenharia, pesos de redes neurais, variáveis do nosso nó IoT), a mutação não deve ser uma substituição cega, mas sim uma perturbação aditiva. A Mutação Gaussiana é o padrão absoluto na indústria.

• Mecânica: Em vez de trocar o número, nós somamos a ele um “ruído” extraído de uma Distribuição Normal (Gaussiana) centrada em zero: $N(0,{\sigma }^2)$.

  $Gen{e}_{novo}=Gen{e}_{antigo}+N(0,{\sigma }^2)$

• O Segredo (O Desvio Padrão $\sigma$): A curva Gaussiana tem formato de sino. Isso significa que a imensa maioria dos ruídos gerados será muito próxima de zero, e ruídos gigantescos serão raríssimos.

  • Efeito Prático: Na maioria das vezes, a mutação fará o gene $10.5$ virar $10.6$ ou $10.4$ (Ajuste Fino / Busca Local). Muito raramente, ela sorteará um número extremo e fará o $10.5$ pular para $15.2$ (Salto Exploratório).

• O Gargalo (Calibração Estática vs. Dinâmica): Se você definir um $\sigma$ grande no código, o algoritmo nunca convergirá, pois as soluções ficarão tremendo violentamente. Se definir um $\sigma$ muito pequeno, a evolução congela. A solução moderna na pós-graduação é o Controle de Parâmetros Adaptativo: começar com um $\sigma$ grande na Geração 1 e ir reduzindo matematicamente esse desvio padrão à medida que a otimização avança (imitando o Simulated Annealing).

Exemplos