O que são algoritmos genéticos?
Algoritmos genéticos (AGs) pertencem à família dos algoritmos evolucionários. Eles imitam o processo de seleção natural da biologia. Assim, soluções para problemas complexos podem ser encontradas. Cada possível solução é representada como um “indivíduo” em uma população. Esses indivíduos geralmente são codificados como cadeias binárias ou números reais. A qualidade de cada um é medida por uma função de aptidão (*fitness*). Quanto maior o valor de aptidão, melhor é a solução. Portanto, o algoritmo busca maximizar (ou minimizar) essa função.Principais operadores evolutivos
Três operadores biológicos são simulados: seleção, cruzamento e mutação. A seleção escolhe os indivíduos mais aptos para reprodução. O cruzamento combina partes de dois pais para gerar filhos. A mutação introduz pequenas alterações aleatórias em um indivíduo. Dessa forma, a diversidade genética é mantida ao longo das gerações. Esses operadores são aplicados repetidamente até um critério de parada. Exemplos de critério incluem número máximo de gerações ou convergência.Formulação matemática básica
Seja uma população de tamanho *N* na geração *t*:P(t) = {x_1(t), x_2(t), ..., x_N(t)}.
Cada indivíduo x_i possui um vetor de genes.
A função aptidão é f(x_i), que retorna um valor real.
A probabilidade de seleção do indivíduo *i* é proporcional a f(x_i).
Para maximização, usa-se p_i = f(x_i) / Σ f(x_j).
No cruzamento de um ponto, dois pais trocam genes após uma posição *k*.
A mutação flip inverte um bit com probabilidade p_m (taxa de mutação).
A nova população P(t+1) é formada pelos filhos e, talvez, pelos melhores pais (elitismo).
O processo iterativo busca o ótimo global x* tal que f(x*) ≥ f(x) para todo x.
Matematicamente, o AG é um método estocástico de otimização.
Ele não exige derivadas nem convexidade da função objetivo.
Por isso, é amplamente usado em problemas com muitos máximos locais.
Exemplo clássico: maximização de uma função
Considere a funçãof(x) = x * sen(10π * x) + 1 no intervalo [0, 1].
O objetivo é encontrar o valor de x que maximiza f(x).
Esta função possui várias oscilações, sendo um teste comum para AGs.
O máximo global aproximado ocorre em torno de x ≈ 0.85, com f ≈ 2.85.
Resolveremos este problema com um AG binário de 20 bits (precisão ~ 1e-6).
Enunciado do problema:
Implemente um algoritmo genético para maximizar f(x) no domínio dado.
Use população de 50 indivíduos, 100 gerações, taxa de cruzamento 0.8 e mutação 0.01.
Adote seleção por roleta e elitismo (manter o melhor indivíduo).
Ao final, exiba o melhor x encontrado e seu valor de f(x).
Gere dois gráficos: (1) evolução do melhor fitness por geração; (2) população final sobre a curva da função.
A resolução em Python para o Google Colab está abaixo.
O código é autoexplicativo e utiliza apenas NumPy e Matplotlib.
|
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 |
# Algoritmo Genético para maximizar f(x) = x * sin(10*pi*x) + 1 # Executar no Google Colab import numpy as np import matplotlib.pyplot as plt # Parâmetros do AG POP_SIZE = 50 GENERATIONS = 100 CROSSOVER_RATE = 0.8 MUTATION_RATE = 0.01 BITS = 20 # precisão de 2^20 discretizações no intervalo [0,1] # Função objetivo def f(x): return x * np.sin(10 * np.pi * x) + 1.0 # Decodificação de binário para real no intervalo [0,1] def decode(binary): integer = int(''.join(map(str, binary)), 2) return integer / (2**BITS - 1) # Inicialização aleatória da população def init_population(): return np.random.randint(0, 2, size=(POP_SIZE, BITS)) # Seleção por roleta (maximização) def roulette(pop, fitness): total = np.sum(fitness) probs = fitness / total idx = np.random.choice(range(POP_SIZE), size=POP_SIZE, p=probs) return pop[idx] # Cruzamento de um ponto def crossover(parents): offspring = parents.copy() for i in range(0, POP_SIZE, 2): if np.random.rand() < CROSSOVER_RATE and i+1 < POP_SIZE: point = np.random.randint(1, BITS) offspring[i, point:] = parents[i+1, point:] offspring[i+1, point:] = parents[i, point:] return offspring # Mutação flip def mutate(pop): for i in range(POP_SIZE): for j in range(BITS): if np.random.rand() < MUTATION_RATE: pop[i, j] = 1 - pop[i, j] return pop # Elitismo: mantém o melhor indivíduo def elitism(pop, fitness, new_pop): best_idx = np.argmax(fitness) worst_idx = np.argmin(fitness) # substitui o pior filho new_pop[worst_idx] = pop[best_idx] return new_pop # Execução do AG pop = init_population() best_fitness_history = [] best_x_history = [] for gen in range(GENERATIONS): # Avaliação x_vals = np.array([decode(ind) for ind in pop]) fitness = np.array([f(x) for x in x_vals]) best_idx = np.argmax(fitness) best_fitness_history.append(fitness[best_idx]) best_x_history.append(x_vals[best_idx]) # Seleção selected = roulette(pop, fitness) # Cruzamento offspring = crossover(selected) # Mutação offspring = mutate(offspring) # Elitismo pop = elitism(pop, fitness, offspring) # Resultado final final_x = decode(pop[np.argmax(fitness)]) final_f = f(final_x) print(f"Melhor x encontrado: {final_x:.6f}") print(f"f(x) máximo: {final_f:.6f}") # Gráfico 1: Evolução do melhor fitness plt.figure(figsize=(12,5)) plt.subplot(1,2,1) plt.plot(best_fitness_history, 'b-') plt.title('Evolução do Melhor Fitness') plt.xlabel('Geração') plt.ylabel('Fitness') plt.grid(True) # Gráfico 2: População final sobre a curva plt.subplot(1,2,2) x_curve = np.linspace(0, 1, 500) y_curve = f(x_curve) plt.plot(x_curve, y_curve, 'k-', label='Função') # População final x_final = np.array([decode(ind) for ind in pop]) y_final = f(x_final) plt.scatter(x_final, y_final, c='red', s=30, label='População final') plt.scatter([final_x], [final_f], c='blue', s=100, marker='*', label='Melhor') plt.title('População Final sobre a Função') plt.xlabel('x') plt.ylabel('f(x)') plt.legend() plt.grid(True) plt.tight_layout() plt.show() |