O que é a função de aptidão?
A função de aptidão é o coração de qualquer algoritmo evolutivo ou genético. Ela quantifica o quão boa é uma solução candidata para um problema específico. Em essência, ela atribui uma nota ou valor numérico a cada indivíduo da população. Portanto, soluções melhores recebem pontuações mais altas, enquanto as piores ficam com notas baixas. Esse valor guia todo o processo de seleção durante a evolução. Sem ela, o algoritmo não teria direção para melhorar ao longo das gerações. A definição da função depende totalmente do domínio do problema. Por exemplo, ela pode maximizar o lucro ou minimizar o custo de uma rota. Ela também pode medir a precisão de um modelo de machine learning. Assim, a função de aptidão traduz um objetivo abstrato em uma métrica concreta.
Por que ela é tão importante?
A importância da função de aptidão não pode ser subestimada. Ela determina quais indivíduos sobrevivem e reproduzem seus genes. Indivíduos com alta aptidão são frequentemente escolhidos para a próxima geração. Por outro lado, os com baixa aptidão são descartados pelo algoritmo. Dessa forma, a população evolui gradualmente em direção ao ótimo. Uma função mal projetada pode levar a resultados ruins ou tendenciosos. Ela deve ser suave e contínua sempre que possível para facilitar a busca. Além disso, ela precisa ser computacionalmente eficiente para populações grandes. A escolha cuidadosa da função reflete o conhecimento do especialista sobre o problema. Portanto, ela é o principal ponto de contato entre a heurística e a realidade.
Características essenciais
Uma boa função de aptidão possui algumas características-chave. Primeiramente, ela deve ser consistente com o objetivo final do projeto. Em segundo lugar, ela precisa diferenciar claramente soluções boas das ruins. Essa diferença é chamada de pressão seletiva no jargão da área. Ela também deve ser escalável para lidar com diferentes tamanhos de entrada. Muitas vezes, ela é normalizada entre 0 e 1 para facilitar a comparação. Contudo, a normalização não é obrigatória em todos os cenários. A função pode ser estática ou dinâmica, dependendo da evolução do problema. Funções dinâmicas mudam ao longo do tempo, exigindo adaptação contínua. Por fim, ela deve ser fácil de interpretar pelos desenvolvedores do sistema.
A função de aptidão é usada em problemas de otimização complexos. Ela é aplicada em engenharia, finanças, robótica e bioinformática. Em cada caso, ela reflete uma medida de desempenho ou qualidade. Por exemplo, em um problema de caixeiro viajante, ela mede a distância total. Quanto menor a distância, maior deve ser a aptidão atribuída. Isso exige uma transformação, como o inverso da distância. Em problemas de maximização, a aptidão é diretamente proporcional ao objetivo. Já em minimização, ela é inversamente proporcional ao custo. Essa adaptação é trivial, mas crucial para o sucesso do algoritmo. Muitas vezes, ela é combinada com penalidades para restrições violadas. Assim, soluções inviáveis são punidas com notas artificialmente baixas. Isso garante que a busca permaneça dentro do espaço factível. A função de aptidão pode ser vista como um “juiz” imparcial da evolução. Ela fornece feedback a cada iteração sem viés humano. Desse modo, o algoritmo aprende sozinho a melhorar suas soluções.
Um exemplo clássico é o problema de maximização de uma função matemática. Suponha que queremos encontrar o máximo de f(x) = x * sen(10πx) + 1. O domínio é restrito ao intervalo [0, 1] para a variável x. A aptidão de cada indivíduo é simplesmente o valor de f(x). Indivíduos com x que produzem f(x) maior são mais aptos. O algoritmo genético irá cruzar e mutar esses x ao longo das gerações. Ao final, ele convergirá para um valor próximo do máximo global. Esse problema é simples, mas ilustra perfeitamente o conceito central. Abaixo, apresento um enunciado completo com resolução em Python.
Enunciado do exemplo clássico
Considere a função f(x) = x * sen(10πx) + 1, com x no intervalo [0, 1]. Seu objetivo é encontrar o valor de x que maximiza f(x) usando um algoritmo genético. Utilize uma população de 20 indivíduos, codificados como números reais. Aplique seleção por torneio de tamanho 2, crossover aritmético e mutação gaussiana. Execute o algoritmo por 50 gerações e plote a evolução da melhor aptidão. Ao final, exiba o melhor x encontrado e seu respectivo valor de f(x).
|
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 |
import numpy as np import matplotlib.pyplot as plt # Definição da função de aptidão (fitness) def fitness(x): return x * np.sin(10 * np.pi * x) + 1.0 # Parâmetros pop_size = 20 geracoes = 50 taxa_mutacao = 0.1 sigma = 0.05 intervalo = (0.0, 1.0) # Inicialização da população populacao = np.random.uniform(intervalo[0], intervalo[1], pop_size) # Lista para armazenar o melhor fitness por geração melhor_fitness_historico = [] for gen in range(geracoes): # Avaliação da aptidão aptidoes = fitness(populacao) melhor_idx = np.argmax(aptidoes) melhor_fitness_historico.append(aptidoes[melhor_idx]) # Seleção por torneio (tamanho 2) nova_populacao = [] for _ in range(pop_size): i1, i2 = np.random.choice(pop_size, 2, replace=False) vencedor = populacao[i1] if aptidoes[i1] > aptidoes[i2] else populacao[i2] nova_populacao.append(vencedor) nova_populacao = np.array(nova_populacao) # Crossover aritmético (média dos pais) filhos = [] for i in range(0, pop_size, 2): p1 = nova_populacao[i] p2 = nova_populacao[(i+1) % pop_size] alpha = np.random.random() f1 = alpha * p1 + (1 - alpha) * p2 f2 = (1 - alpha) * p1 + alpha * p2 filhos.extend([f1, f2]) nova_populacao = np.array(filhos[:pop_size]) # Mutação gaussiana for i in range(pop_size): if np.random.random() < taxa_mutacao: nova_populacao[i] += np.random.normal(0, sigma) nova_populacao[i] = np.clip(nova_populacao[i], intervalo[0], intervalo[1]) populacao = nova_populacao # Resultado final melhor_x = populacao[np.argmax(fitness(populacao))] melhor_f = fitness(melhor_x) print(f"Melhor x encontrado: {melhor_x:.6f}") print(f"Valor máximo de f(x): {melhor_f:.6f}") # Gráfico 1: Evolução da melhor aptidão plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(melhor_fitness_historico, 'b-', linewidth=2) plt.title('Evolução da Melhor Aptidão') plt.xlabel('Geração') plt.ylabel('Aptidão (f(x))') plt.grid(True) # Gráfico 2: Função e o ponto encontrado x_plot = np.linspace(0, 1, 1000) y_plot = fitness(x_plot) plt.subplot(1, 2, 2) plt.plot(x_plot, y_plot, 'g-', label='f(x) = x*sen(10πx)+1') plt.scatter([melhor_x], [melhor_f], color='red', s=100, label='Melhor encontrado') plt.title('Função e o Ótimo Encontrado') plt.xlabel('x') plt.ylabel('f(x)') plt.legend() plt.grid(True) plt.tight_layout() plt.show() |
Este código está pronto para ser executado no Google Colab. Ele gera dois gráficos: a evolução da aptidão e a função com o ponto ótimo. A execução mostra como a função de aptidão guia a busca iterativamente. Mesmo para iniciantes, o conceito se torna claro com essa demonstração prática. A função de aptidão é, portanto, a bússola que orienta o algoritmo genético.