O que é? A Tribo Evolucionista é uma das cinco grandes famílias de métodos da Inteligência Artificial. Inspirada na teoria da evolução de Charles Darwin, ela utiliza princípios como seleção natural, mutação e reprodução para encontrar soluções ótimas para problemas complexos.
Diferencial: É livre de derivadas e excelente para explorar espaços de busca enormes, irregulares ou pouco compreendidos, onde métodos tradicionais falham.
Os Algoritmos Genéticos são os mais populares e conhecidos da Computação Evolucionária. Trabalham com uma população de soluções codificadas como cromossomos (strings binárias ou vetores reais). A cada geração, os melhores indivíduos são selecionados para reprodução, gerando descendentes por cruzamento e mutação.
Define quais indivíduos sobrevivem e se reproduzem. A roleta atribui probabilidades proporcionais à aptidão; o torneio compara aleatoriamente um subconjunto e escolhe o melhor.
Probabilidade na roleta: \(P(i) = \frac{f_i}{\sum_{j=1}^{N} f_j}\)
Combina partes de dois cromossomos para gerar novos descendentes, promovendo a exploração do espaço de busca.
Crossover de ponto único: \(filho = pai_1[1..k] + pai_2[k+1..n]\)
Introduz pequenas alterações aleatórias em um cromossomo, garantindo diversidade genética e evitando convergência prematura.
Mutação binária: \(bit = 1 – bit\) (inverte o bit)
Avalia a qualidade de cada solução. É o “termômetro” que guia todo o processo evolutivo.
Exemplo: \(f(x) = \frac{1}{1 + erro(x)}\)
Enquanto os AGs evoluem parâmetros, a Programação Genética evolui programas de computador completos. As soluções são representadas como árvores de expressão, onde folhas são variáveis/constantes e nós internos são operadores.
Estruturas hierárquicas que representam funções ou programas. Ex: a expressão (x + 3) * y vira uma árvore com * na raiz.
Representação: \(f(x,y) = (x + 3) \times y\)
A população de árvores evolui por cruzamento (troca de sub-árvores) e mutação (alteração de nós), buscando programas que resolvam problemas específicos.
Crossover em PG: \(filho = arvore_1[subarvore_a] + arvore_2[subarvore_b]\)
Especializadas em otimização contínua (variáveis reais). Desenvolvidas na Alemanha, destacam-se pela auto-adaptação dos parâmetros de mutação.
(1+1)-ES
A mais simples: um pai gera um filho por mutação. O melhor entre os dois sobrevive.
Regra: \(x’ = x + \mathcal{N}(0, \sigma)\)
(μ,λ)-ES
μ pais geram λ descendentes (λ > μ). A nova geração é composta apenas pelos λ filhos, descartando os pais. Promove exploração.
Seleção: \(P_{t+1} = \mu \text{ melhores de } \lambda \text{ filhos}\)
(μ+λ)-ES
Pais e filhos competem juntos; os μ melhores sobrevivem. Abordagem mais elitista.
Seleção: \(P_{t+1} = \mu \text{ melhores de } (\mu \text{ pais} + \lambda \text{ filhos})\)
Evolui estruturas de dados sem restrição a uma representação fixa. Originalmente proposta para evoluir autômatos finitos que aprendem a tomar decisões.
Máquinas de estados que evoluem suas transições e estados por mutação (sem crossover). Cada autômato é avaliado por sua capacidade de resolver uma tarefa.
Autômato: \(M = (Q, \Sigma, \delta, q_0, F)\)
Inspirados no comportamento social de formigas para resolver problemas de otimização combinatória (ex: Caixeiro Viajante). As formigas artificiais depositam feromônios nas arestas de um grafo; a intensidade do feromônio guia futuras formigas para caminhos mais curtos.
Primeira versão. Todas as formigas constroem soluções completas e atualizam os feromônios com base no comprimento do caminho encontrado.
Atualização: \(\tau_{ij}(t+1) = (1-\rho) \cdot \tau_{ij}(t) + \sum_{k=1}^{m} \Delta \tau_{ij}^k\)
Evolução do AS, com mecanismo de exploração vs. exploração e atualização local de feromônio, melhorando a convergência.
Regra de transição: \(p_{ij}^k = \frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{l \in \text{permitidos}} [\tau_{il}]^\alpha [\eta_{il}]^\beta}\)
Inspirado no comportamento social de bandos de pássaros. Cada partícula representa uma solução candidata que se move no espaço de busca, ajustando sua posição com base em sua melhor experiência individual e na melhor experiência do grupo.
Cada partícula ajusta sua velocidade baseada em sua posição anterior e nas melhores posições encontradas, sem parâmetro de inércia.
Velocidade: \(v_i(t+1) = v_i(t) + c_1 \cdot r_1 \cdot (p_i – x_i(t)) + c_2 \cdot r_2 \cdot (g – x_i(t))\)
Adiciona um coeficiente de inércia que controla o impacto da velocidade anterior, equilibrando exploração global e local.
Velocidade com inércia: \(v_i(t+1) = w \cdot v_i(t) + c_1 \cdot r_1 \cdot (p_i – x_i(t)) + c_2 \cdot r_2 \cdot (g – x_i(t))\)
Posição: \(x_i(t+1) = x_i(t) + v_i(t+1)\)