Algorítimos Genéticos

16/07/202617/06/2026 Por antonino

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ção f(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.

# 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()

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()

Ao executar, o gráfico da esquerda mostra a melhora contínua do fitness. O gráfico da direita exibe todos os indivíduos finais espalhados perto do pico. O asterisco azul indica a melhor solução encontrada pelo AG. Esse exemplo demonstra a robustez do método mesmo sem conhecimento prévio. A convergência é alcançada, embora com variabilidade entre execuções. Para problemas reais, ajustes nos parâmetros são frequentemente necessários. Assim, os algoritmos genéticos oferecem uma ferramenta flexível e poderosa. Eles são aplicados em engenharia, finanças, robótica e muito mais. Com a prática, você poderá adaptá-los a seus próprios desafios.

Computação Evolucionaria

16/07/202617/06/2026 Por antonino

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.

# ============================================================
# 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()

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!