O que são autômatos finitos evolutivos?
Autômatos finitos evolutivos (AFE) são máquinas de estados que aprendem por evolução artificial. Cada indivíduo é um autômato finito determinístico (AFD) com estados, transições e saídas. A evolução altera o número de estados, as transições ou os símbolos de saída. Diferentemente de redes neurais, eles são discretos, interpretáveis e leves. A aptidão mede o quão bem o autômato resolve uma tarefa sequencial. Por exemplo, ele pode prever o próximo elemento de uma série temporal. Ou pode classificar padrões binários que chegam ao longo do tempo. A programação evolutiva foi originalmente criada para evoluir esses autômatos. Portanto, os AFE são a aplicação clássica da programação evolutiva.
Como funciona a evolução de um autômato?
Inicialmente, uma população de autômatos aleatórios é gerada. Cada um tem um número fixo de estados (ex.: 5) e alfabeto de entrada. As transições são tabelas que mapeiam (estado, símbolo) para próximo estado. Cada estado também possui uma saída (ex.: 0 ou 1 para classificação). A mutação pode alterar uma transição, uma saída ou adicionar/remover estados. O crossover pode trocar sub-tabelas de transição entre dois autômatos. A avaliação percorre o autômato com uma sequência de entrada conhecida. A saída gerada é comparada com a saída desejada (supervisionado). A aptidão é a acurácia ou o erro acumulado ao longo da sequência. Os melhores autômatos são selecionados para a próxima geração.
Aplicações e vantagens práticas
AFE são usados em reconhecimento de padrões temporais e linguagens regulares. Eles também são aplicados em controle de robôs com sensores discretos. Uma grande vantagem é a total interpretabilidade do comportamento aprendido. O engenheiro pode inspecionar estados e transições para entender a decisão. Além disso, eles exigem pouca memória e executam em tempo real. Contudo, eles não lidam bem com entradas contínuas ou ruidosas. Para esses casos, pré-processamento ou fuzzificação é necessário. Ainda assim, os AFE são uma ferramenta didática e poderosa.
Os autômatos finitos evolutivos foram popularizados por Fogel no final dos anos 1960. Ele usou AFE para prever o comportamento de sinais de radar e econômicos. Cada autômato previa o próximo bit de uma sequência binária. A aptidão era a porcentagem de acertos ao longo de todo o histórico. A mutação podia trocar uma transição ou inverter a saída de um estado. Não havia crossover na versão original, apenas mutação pura. Com o tempo, variantes com crossover e auto-adaptação surgiram. Hoje, os AFE são usados em jogos, segurança e bioinformática. Por exemplo, eles podem detectar anomalias em tráfego de rede. Também podem modelar o comportamento de usuários em sistemas interativos. Sua simplicidade os torna ideais para dispositivos embarcados. Eles são frequentemente comparados a redes neurais recorrentes discretizadas. A principal diferença é a ausência de pesos contínuos. Assim, os AFE oferecem um equilíbrio entre expressividade e clareza.
Um exemplo clássico é o problema de previsão do próximo símbolo em uma sequência. Dada uma sequência binária gerada por uma máquina de estados oculta. O AFE deve inferir a regra subjacente sem conhecer a máquina original. Por exemplo, a sequência alterna entre 0 e 1 após cada dois dígitos. O autômato evolui sua tabela de transições até acertar a previsão. Esse problema é simples, mas ilustra perfeitamente o mecanismo de aprendizado.
Enunciado do exemplo clássico
Evolua um autômato finito determinístico com 4 estados para prever o próximo bit da sequência de Fibonacci binária (módulo 2). A sequência é: 0,1,1,0,1,1,0,1,1,… (período 3: 0,1,1 repetido). Use 100 exemplos de treinamento (bits) e 50 de teste (após o treino). População de 50 autômatos, mutação de transição (10%) e saída (5%) por geração. Execute 100 gerações, com seleção por torneio de tamanho 3. Plote a acurácia de treino e teste ao longo das gerações. Plote também um diagrama do melhor autômato encontrado (texto).
|
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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
import numpy as np import matplotlib.pyplot as plt # Gera sequência de Fibonacci módulo 2 (período 3: 0,1,1) def fibonacci_binaria(n): seq = [] a, b = 0, 1 for _ in range(n): seq.append(a % 2) a, b = b, (a + b) % 2 return seq # Parâmetros num_estados = 4 alfabeto = [0, 1] pop_size = 50 geracoes = 100 taxa_mut_trans = 0.10 taxa_mut_saida = 0.05 tamanho_torneio = 3 # Gerar dados treino_len = 100 teste_len = 50 treino_seq = fibonacci_binaria(treino_len) teste_seq = fibonacci_binaria(treino_len + teste_len)[treino_len:] # Representação: cada autômato é (transicoes, saidas) # transicoes: dict (estado, simbolo) -> prox_estado # saidas: dict estado -> 0 ou 1 def cria_autômato(): trans = {} saidas = {} for e in range(num_estados): saidas[e] = np.random.randint(0, 2) for s in alfabeto: trans[(e, s)] = np.random.randint(0, num_estados) return trans, saidas def avaliar(automato, seq, n_predicoes): trans, saidas = automato estado = 0 acertos = 0 # Usamos os primeiros n_predicoes bits para prever o próximo for i in range(n_predicoes - 1): simbolo = seq[i] estado = trans[(estado, simbolo)] predicao = saidas[estado] if predicao == seq[i+1]: acertos += 1 return acertos / (n_predicoes - 1) if n_predicoes > 1 else 0.0 def mutar(automato): trans, saidas = automato # Mutação de transição for key in list(trans.keys()): if np.random.random() < taxa_mut_trans: trans[key] = np.random.randint(0, num_estados) # Mutação de saída for e in saidas: if np.random.random() < taxa_mut_saida: saidas[e] = 1 - saidas[e] return trans, saidas # Inicialização populacao = [cria_autômato() for _ in range(pop_size)] # Histórico de acurácias melhor_treino_hist = [] melhor_teste_hist = [] melhor_automato = None for gen in range(geracoes): # Avaliar treino fitness_treino = [avaliar(ind, treino_seq, treino_len) for ind in populacao] # Seleção por torneio nova_pop = [] for _ in range(pop_size): indices = np.random.choice(pop_size, tamanho_torneio, replace=False) vencedor = indices[np.argmax([fitness_treino[i] for i in indices])] nova_pop.append(populacao[vencedor]) # Mutação (exceto o melhor, elitismo) melhor_idx = np.argmax(fitness_treino) melhor_ind = populacao[melhor_idx] nova_pop[0] = melhor_ind # mantém o melhor for i in range(1, pop_size): nova_pop[i] = mutar(nova_pop[i]) populacao = nova_pop # Melhor da geração melhor_treino = np.max(fitness_treino) melhor_teste = avaliar(melhor_ind, teste_seq, teste_len) melhor_treino_hist.append(melhor_treino) melhor_teste_hist.append(melhor_teste) if melhor_treino > max(melhor_treino_hist[:-1], default=-1): melhor_automato = (melhor_ind[0].copy(), melhor_ind[1].copy()) # Resultado final print("Melhor autômato encontrado:") trans, saidas = melhor_automato print("Transições (estado, símbolo) -> próximo estado:") for e in range(num_estados): for s in alfabeto: print(f" ({e},{s}) -> {trans[(e,s)]}") print("Saídas por estado:") for e in range(num_estados): print(f" estado {e} -> {saidas[e]}") # Gráfico 1: Acurácias de treino e teste plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(melhor_treino_hist, 'b-', label='Treino', linewidth=2) plt.plot(melhor_teste_hist, 'r--', label='Teste', linewidth=2) plt.title('Evolução da Acurácia - AFE') plt.xlabel('Geração') plt.ylabel('Acurácia') plt.ylim(0, 1.05) plt.legend() plt.grid(True) # Gráfico 2: Diagrama textual do melhor autômato plt.subplot(1, 2, 2) texto = "Melhor AFD encontrado:\n\n" texto += "Transições:\n" for e in range(num_estados): for s in alfabeto: texto += f" δ({e},{s}) = {trans[(e,s)]}\n" texto += "\nSaídas:\n" for e in range(num_estados): texto += f" λ({e}) = {saidas[e]}\n" plt.text(0.1, 0.5, texto, fontsize=10, family='monospace', bbox=dict(facecolor='lightyellow', alpha=0.9)) plt.axis('off') plt.title('Estrutura do Melhor Autômato') plt.tight_layout() plt.show() |
Este código evolui um AFD para prever a sequência de Fibonacci binária. A curva de acurácia mostra a melhoria tanto em treino quanto em teste. O diagrama textual exibe as transições e saídas do melhor autômato. Observe que o autômato converge para o período 3 (0,1,1) após algumas gerações. A interpretabilidade é total: cada estado e transição podem ser lidos. Para iniciantes, este exemplo conecta evolução, autômatos e previsão. Os autômatos finitos evolutivos são, portanto, uma ferramenta educativa e prática.