antonino, Autor em Área de Trampo

O que é seleção em algoritmos evolutivos?

A seleção é um processo fundamental nos algoritmos evolutivos. Ela imita a escolha natural dos seres vivos. Indivíduos mais aptos têm maior chance de reprodução. Assim, a população melhora ao longo das gerações. Esse mecanismo guia a busca por soluções ótimas. Portanto, a seleção não é aleatória, mas direcionada. Ela equilibra exploração e exploração do espaço de busca. Sem ela, o algoritmo seria uma busca cega. Por isso, a seleção é o coração da evolução computacional.

Roleta: probabilidade proporcional à aptidão

A roleta é um método clássico de seleção proporcional. Cada indivíduo ocupa uma fatia da roleta. O tamanho da fatia é proporcional à sua aptidão. Então, indivíduos melhores têm áreas maiores. Um número aleatório decide qual fatia é escolhida. Esse processo é repetido até preencher a nova população. Contudo, a roleta pode sofrer com convergência prematura. Isso acontece quando um indivíduo muito bom domina. A diversidade da população pode ser reduzida rapidamente. Mesmo assim, ela é simples e intuitiva para iniciantes.

Torneio: competição direta entre indivíduos

O torneio é outro método de seleção muito usado. Ele escolhe aleatoriamente um grupo de indivíduos. O tamanho do grupo é definido pelo usuário. Depois, compara-se a aptidão de todos eles. O vencedor é aquele com maior aptidão. Esse vencedor é copiado para a nova geração. O processo se repete até completar a população. Uma vantagem é não precisar de normalização. Além disso, o torneio mantém pressão seletiva ajustável. Torneios maiores aumentam a pressão seletiva. Por outro lado, torneios menores preservam diversidade. Assim, o torneio é robusto e popular na prática.

Comparação entre roleta e torneio

A roleta é sensível à escala da aptidão. Já o torneio depende apenas de comparações relativas. A roleta pode ser implementada facilmente. O torneio é mais eficiente computacionalmente. A roleta é recomendada quando a aptidão é positiva. O torneio funciona bem com aptidões negativas também. Ambos os métodos são estocásticos por natureza. Eles introduzem aleatoriedade controlada no processo. Essa aleatoriedade evita ficar preso em ótimos locais. Portanto, a escolha entre eles é situacional. Iniciantes frequentemente começam com o torneio. Ele é mais tolerante a diferentes escalas de aptidão.

Exemplo clássico: maximização de uma função

Considere o problema de maximizar f(x) = x². O domínio é x no intervalo [0, 31]. Representamos x como um binário de 5 bits. A população inicial tem 6 indivíduos aleatórios. Usaremos seleção por torneio de tamanho 3. O crossover é de um ponto com probabilidade 0.7. A mutação troca um bit com chance 0.01. Executamos 20 gerações para evoluir a população. Ao final, esperamos encontrar x próximo de 31. Esse é um problema clássico de algoritmos genéticos. Ele ilustra bem o poder da seleção evolutiva. Agora, veja a resolução completa em Python abaixo.

import numpy as np
import matplotlib.pyplot as plt
import random

# Função objetivo (maximizar)
def fitness(x):
    return x**2

# Decodifica binário para inteiro
def decode(bits):
    return int(''.join(map(str, bits)), 2)

# Inicializa população aleatória (6 indivíduos, 5 bits)
pop_size = 6
bits = 5
pop = [[random.randint(0,1) for _ in range(bits)] for _ in range(pop_size)]

# Armazena melhores aptidões por geração
melhores = []
medias = []

for geracao in range(20):
    # Avalia aptidão
    fitnesses = [fitness(decode(ind)) for ind in pop]
    melhores.append(max(fitnesses))
    medias.append(np.mean(fitnesses))
    
    # Nova população por torneio (tamanho 3)
    nova_pop = []
    for _ in range(pop_size):
        # Seleciona 3 indivíduos aleatórios
        candidatos = random.sample(range(pop_size), 3)
        # Escolhe o de maior aptidão (vencedor)
        vencedor = max(candidatos, key=lambda i: fitnesses[i])
        nova_pop.append(pop[vencedor].copy())
    pop = nova_pop
    
    # Crossover de um ponto (prob 0.7)
    for i in range(0, pop_size-1, 2):
        if random.random() < 0.7:
            ponto = random.randint(1, bits-1)
            pop[i][ponto:], pop[i+1][ponto:] = pop[i+1][ponto:], pop[i][ponto:]
    
    # Mutação (prob 0.01 por bit)
    for i in range(pop_size):
        for j in range(bits):
            if random.random() < 0.01:
                pop[i][j] = 1 - pop[i][j]

# Resultado final
melhor_ind = max(pop, key=lambda ind: fitness(decode(ind)))
melhor_x = decode(melhor_ind)
print(f"Melhor x encontrado: {melhor_x} -> f(x) = {fitness(melhor_x)}")

# Gráficos
plt.figure(figsize=(12,4))
plt.subplot(1,2,1)
plt.plot(melhores, label='Melhor aptidão', color='green')
plt.plot(medias, label='Média da população', color='blue')
plt.xlabel('Geração')
plt.ylabel('Aptidão')
plt.title('Evolução da aptidão')
plt.legend()
plt.grid(True)

plt.subplot(1,2,2)
plt.bar(range(len(melhores)), melhores, alpha=0.6, color='orange')
plt.xlabel('Geração')
plt.ylabel('Melhor aptidão')
plt.title('Progresso do melhor indivíduo')
plt.grid(True)
plt.tight_layout()
plt.show()

import numpy as np

import matplotlib.pyplot as plt

import random

# Função objetivo (maximizar)

def fitness(x):

return x**2

# Decodifica binário para inteiro

def decode(bits):

return int(''.join(map(str, bits)), 2)

# Inicializa população aleatória (6 indivíduos, 5 bits)

pop_size = 6

bits = 5

pop = [[random.randint(0,1) for _ in range(bits)] for _ in range(pop_size)]

# Armazena melhores aptidões por geração

melhores = []

medias = []

for geracao in range(20):

# Avalia aptidão

fitnesses = [fitness(decode(ind)) for ind in pop]

melhores.append(max(fitnesses))

medias.append(np.mean(fitnesses))

# Nova população por torneio (tamanho 3)

nova_pop = []

for _ in range(pop_size):

# Seleciona 3 indivíduos aleatórios

candidatos = random.sample(range(pop_size), 3)

# Escolhe o de maior aptidão (vencedor)

vencedor = max(candidatos, key=lambda i: fitnesses[i])

nova_pop.append(pop[vencedor].copy())

pop = nova_pop

# Crossover de um ponto (prob 0.7)

for i in range(0, pop_size-1, 2):

if random.random() < 0.7:

ponto = random.randint(1, bits-1)

pop[i][ponto:], pop[i+1][ponto:] = pop[i+1][ponto:], pop[i][ponto:]

# Mutação (prob 0.01 por bit)

for i in range(pop_size):

for j in range(bits):

if random.random() < 0.01:

pop[i][j] = 1 - pop[i][j]

# Resultado final

melhor_ind = max(pop, key=lambda ind: fitness(decode(ind)))

melhor_x = decode(melhor_ind)

print(f"Melhor x encontrado: {melhor_x} -> f(x) = {fitness(melhor_x)}")

# Gráficos

plt.figure(figsize=(12,4))

plt.subplot(1,2,1)

plt.plot(melhores, label='Melhor aptidão', color='green')

plt.plot(medias, label='Média da população', color='blue')

plt.xlabel('Geração')

plt.ylabel('Aptidão')

plt.title('Evolução da aptidão')

plt.legend()

plt.grid(True)

plt.subplot(1,2,2)

plt.bar(range(len(melhores)), melhores, alpha=0.6, color='orange')

plt.xlabel('Geração')

plt.ylabel('Melhor aptidão')

plt.title('Progresso do melhor indivíduo')

plt.grid(True)

plt.tight_layout()

plt.show()

Análise dos resultados esperados

O código executa no Google Colab sem modificações. A aptidão máxima teórica é 961 (para x=31). Com 20 gerações, frequentemente atingimos x=31. O gráfico da esquerda mostra a evolução das médias. Ele também exibe o melhor valor por geração. O gráfico da direita destaca o progresso do máximo. É comum ver saltos repentinos na curva. Esses saltos vêm do crossover e da mutação. A seleção por torneio mantém pressão constante. Portanto, a convergência é rápida e estável. Esse exemplo ensina na prática os conceitos. Ele é reproduzível e fácil de modificar. Tente alterar o tamanho do torneio, por exemplo. Observe como isso afeta a velocidade de convergência. A experimentação é a melhor forma de aprender.

Conclusão sobre seleção em algoritmos evolutivos

A seleção é o motor da evolução artificial. Roleta e torneio são duas estratégias complementares. A roleta é probabilística e baseada em proporções. O torneio é competitivo e baseado em comparações. Ambas têm vantagens e desvantagens conhecidas. A escolha depende do problema e da experiência. Para iniciantes, o torneio é geralmente recomendado. Ele é mais simples de ajustar e entender. Os gráficos mostram claramente o efeito da seleção. Eles revelam como a população melhora gradativamente. Por fim, lembre-se: sem seleção, não há evolução. Ela direciona a busca para regiões promissoras. Portanto, domine esse conceito para avançar. A prática com o código solidifica o aprendizado. Bons estudos e boas evoluções!

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.

Seleção (Roleta, Torneio)

O que é seleção em algoritmos evolutivos?

Roleta: probabilidade proporcional à aptidão

Torneio: competição direta entre indivíduos

Comparação entre roleta e torneio

Exemplo clássico: maximização de uma função

Análise dos resultados esperados

Conclusão sobre seleção em algoritmos evolutivos

Algorítimos Genéticos

O que são algoritmos genéticos?

Principais operadores evolutivos

Formulação matemática básica

Exemplo clássico: maximização de uma função