Seleção (Roleta, Torneio)

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!

Indice