O que é Computação Evolucionária?
Computação evolucionária (CE) é um subcampo da inteligência artificial inspirado na teoria da evolução natural. Ela utiliza mecanismos como seleção, cruzamento e mutação para resolver problemas de otimização e busca. Diferentemente de métodos tradicionais, a CE não exige derivadas ou informações gradientes. Em vez disso, ela trabalha com uma população de soluções candidatas, que evoluem ao longo de gerações. Esse processo é estocástico e robusto para espaços de busca complexos e multimodais.
Frequentemente, a CE é aplicada quando o espaço de soluções é enorme ou pouco compreendido. Por exemplo, ela pode projetar antenas, ajustar hiperparâmetros de redes neurais ou criar rotas logísticas. Sua flexibilidade é um grande atrativo, embora o custo computacional possa ser elevado. No entanto, com o aumento da capacidade de processamento, seu uso tem se popularizado rapidamente.
Fundamentos Matemáticos
Para entender a CE, precisamos formalizar alguns conceitos básicos. Uma solução é representada como um vetor \(\mathbf{x} = (x_1, x_2, …, x_n)\) em um domínio \(\mathcal{D}\). A qualidade dessa solução é medida por uma função de aptidão (fitness) \(f: \mathcal{D} \rightarrow \mathbb{R}\). O objetivo é encontrar \(\mathbf{x}^*\) que maximize (ou minimize) \(f(\mathbf{x})\). Formalmente, temos:
\[ \mathbf{x}^* = \arg\max_{\mathbf{x} \in \mathcal{D}} f(\mathbf{x}) \]A seleção é baseada na aptidão relativa de cada indivíduo. Uma abordagem comum é a seleção por roleta, onde a probabilidade \(p_i\) do indivíduo \(i\) ser escolhido é:
\[ p_i = \frac{f(\mathbf{x}_i)}{\sum_{j=1}^{N} f(\mathbf{x}_j)} \]para problemas de maximização (assumindo aptidões positivas). Em seguida, o cruzamento (recombinação) combina dois pais para gerar dois filhos. Para representação binária, o cruzamento de um ponto é dado por:
\[ \mathbf{y}_1 = (x_1^{(1)}, …, x_k^{(1)}, x_{k+1}^{(2)}, …, x_n^{(2)}) \] \[ \mathbf{y}_2 = (x_1^{(2)}, …, x_k^{(2)}, x_{k+1}^{(1)}, …, x_n^{(1)}) \]onde \(k\) é o ponto de corte aleatório. Já a mutação introduz variação aleatória, geralmente com probabilidade \(p_m\). Para variáveis contínuas, a mutação gaussiana adiciona um ruído \(\mathcal{N}(0, \sigma^2)\):
\[ x’_i = x_i + \mathcal{N}(0, \sigma^2) \]Esses operadores são aplicados repetidamente até que um critério de parada seja satisfeito. A convergência não é garantida para o ótimo global, mas empíricamente é muito eficaz.
Algoritmo Genético Canônico
O algoritmo genético (AG) é o exemplo mais conhecido de CE. Ele segue um fluxo simples: inicialização, avaliação, seleção, cruzamento, mutação e substituição. Cada geração produz uma nova população, geralmente do mesmo tamanho da anterior. A pressão seletiva direciona a busca para regiões promissoras do espaço. Contudo, a diversidade deve ser mantida para evitar convergência prematura.
Parâmetros importantes incluem o tamanho da população, a taxa de cruzamento e a taxa de mutação. Taxas altas de mutação podem transformar o AG em uma busca aleatória pura. Por outro lado, taxas muito baixas reduzem a capacidade de explorar novas áreas. O equilíbrio entre exploração e explotação é obtido por meio de ajustes empíricos. Muitas variantes existem, como o algoritmo de evolução diferencial e a programação genética.
Exemplo Clássico: Maximização de uma Função
Considere o problema de maximizar a função \(g(x) = x \cdot \sin(10\pi x) + 1\) no intervalo \([0, 1]\). Essa função é altamente oscilatória e possui múltiplos máximos locais. O máximo global está próximo de \(x = 0.85\), com valor aproximado de 1.85. Nosso objetivo é encontrar esse ponto usando um algoritmo genético simples. A aptidão será o próprio valor da função, e a representação será um vetor de bits (codificação binária).
Abaixo apresentamos um código Python completo para resolver esse problema no Google Colab. Ele utiliza uma população de 50 indivíduos, 20 gerações, cruzamento de dois pontos e mutação bit-flip. Ao final, são gerados dois gráficos: a evolução do melhor fitness e a função com o melhor ponto encontrado. O código é autoexplicativo e comentado para facilitar o entendimento de iniciantes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
# ============================================================ # Algoritmo Genético para maximizar g(x) = x*sin(10*pi*x) + 1 # ============================================================ import numpy as np import matplotlib.pyplot as plt # --- Função objetivo (fitness) --- def g(x): return x * np.sin(10 * np.pi * x) + 1.0 # --- Decodificação de binário para real no intervalo [0,1] --- def decode(bits): # bits é um array de 0/1 (tamanho 16) integer = int(''.join(map(str, bits)), 2) return integer / (2**len(bits) - 1) # --- Parâmetros do AG --- POP_SIZE = 50 GENES = 16 # precisão de 16 bits GENERATIONS = 20 MUTATION_RATE = 0.01 CROSSOVER_RATE = 0.8 # --- Inicialização aleatória --- pop = np.random.randint(0, 2, size=(POP_SIZE, GENES)) # --- Listas para guardar histórico --- best_fitness_hist = [] avg_fitness_hist = [] # --- Loop evolutivo --- for gen in range(GENERATIONS): # Avaliar todos os indivíduos fitness = np.array([g(decode(ind)) for ind in pop]) best_idx = np.argmax(fitness) best_fitness_hist.append(fitness[best_idx]) avg_fitness_hist.append(np.mean(fitness)) # Seleção por torneio (tamanho 3) new_pop = [] for _ in range(POP_SIZE): idx1 = np.random.choice(POP_SIZE, 3, replace=False) idx2 = np.random.choice(POP_SIZE, 3, replace=False) winner1 = idx1[np.argmax(fitness[idx1])] winner2 = idx2[np.argmax(fitness[idx2])] parent1 = pop[winner1].copy() parent2 = pop[winner2].copy() # Cruzamento com probabilidade CROSSOVER_RATE if np.random.rand() < CROSSOVER_RATE: # cruzamento de dois pontos cp1 = np.random.randint(1, GENES-2) cp2 = np.random.randint(cp1+1, GENES-1) child1 = np.concatenate([parent1[:cp1], parent2[cp1:cp2], parent1[cp2:]]) child2 = np.concatenate([parent2[:cp1], parent1[cp1:cp2], parent2[cp2:]]) else: child1, child2 = parent1, parent2 # Mutação bit-flip for child in [child1, child2]: for i in range(GENES): if np.random.rand() < MUTATION_RATE: child[i] = 1 - child[i] new_pop.extend([child1, child2]) # Manter tamanho da população (seleção por elitismo) pop = np.array(new_pop[:POP_SIZE]) # Elitismo: preservar o melhor indivíduo da geração anterior pop[0] = pop[best_idx] # --- Resultados finais --- best_individual = pop[np.argmax([g(decode(ind)) for ind in pop])] best_x = decode(best_individual) best_y = g(best_x) print(f"Melhor x encontrado: {best_x:.5f}, valor: {best_y:.5f}") # --- Gráfico 1: Evolução do fitness --- plt.figure(figsize=(12,5)) plt.subplot(1,2,1) plt.plot(best_fitness_hist, 'b-o', label='Melhor fitness') plt.plot(avg_fitness_hist, 'r--s', label='Fitness médio') plt.xlabel('Geração') plt.ylabel('Aptidão') plt.title('Evolução da aptidão') plt.legend() plt.grid(True) # --- Gráfico 2: Função e melhor ponto --- x_vals = np.linspace(0, 1, 500) y_vals = g(x_vals) plt.subplot(1,2,2) plt.plot(x_vals, y_vals, 'k-', linewidth=1.5, label='g(x)') plt.plot(best_x, best_y, 'ro', markersize=10, label='Melhor encontrado') plt.xlabel('x') plt.ylabel('g(x)') plt.title('Função e ponto ótimo') plt.legend() plt.grid(True) plt.tight_layout() plt.show() |
Esse código é executado diretamente no Colab e produz dois gráficos claros. O primeiro mostra a evolução do melhor e da média da aptidão ao longo das gerações. O segundo exibe a função contínua e o ponto vermelho que representa a melhor solução. Você pode alterar o número de gerações ou a taxa de mutação para observar mudanças. A convergência é rápida, e geralmente o algoritmo encontra um valor próximo de 1.85.
Considerações Finais
A computação evolucionária é uma ferramenta poderosa e acessível para problemas difíceis. Ela não requer conhecimento profundo de cálculo ou álgebra linear. Contudo, é importante entender seus parâmetros e limitações. Muitas melhorias podem ser incorporadas, como elitismo, adaptação de taxas e nichos. A área é ativa em pesquisa, com aplicações em engenharia, finanças e robótica.
Para um iniciante, recomendamos começar com o algoritmo genético clássico. Depois, explore variantes como evolução diferencial ou estratégias evolutivas. Lembre-se de que a CE não garante o ótimo global, mas oferece boas aproximações. Seu caráter estocástico exige múltiplas execuções para resultados confiáveis. Por fim, a combinação com outras técnicas híbridas tem sido cada vez mais utilizada.
Este material foi elaborado para fornecer uma base sólida e prática. Esperamos que você experimente o código e modifique os parâmetros livremente. A evolução artificial é fascinante e repleta de possibilidades criativas. Boa sorte em sua jornada no mundo da computação evolucionária!
