Arquivo de Python - Página 17 de 31

Estratégia Evolutiva (μ,λ)-ES

16/07/202617/06/2026 Por antonino

O que é a (μ,λ)-ES?

A (μ,λ)-ES é uma estratégia evolutiva que mantém μ pais e gera λ filhos. Aqui, λ é sempre maior que μ, geralmente λ ≈ 4μ a 7μ. Cada filho é criado por mutação gaussiana a partir de um pai escolhido. Após avaliar todos os λ filhos, apenas os μ melhores sobrevivem. Os pais antigos são completamente descartados, sem exceção. Essa abordagem é chamada de seleção de truncamento (μ,λ). Ela permite que o algoritmo esqueça soluções antigas e explore novas. Isso reduz o risco de estagnação em mínimos locais. Por outro lado, a (μ+λ)-ES mantém os pais na competição. A notação (μ,λ) enfatiza que a população parental é renovada a cada geração.

Mecanismos de auto-adaptação e recombinação

Cada indivíduo carrega seu próprio desvio-padrão para mutação adaptativa. Esses desvios também sofrem mutação log-normal e são herdados pelos filhos. Além disso, muitas variantes usam crossover para combinar dois pais. O crossover intermediário calcula a média dos vetores parentais. Já o crossover discreto troca coordenadas entre os pais escolhidos. Ambos aumentam a diversidade genética dentro da população de filhos. A seleção dos pais para reprodução é geralmente uniforme ou por torneio. Contudo, a sobrevivência é sempre determinística: os μ melhores filhos.

Vantagens e cenários de uso

A grande vantagem é a capacidade de escapar de ótimos locais com facilidade. Ela é especialmente eficaz em paisagens multimodais e ruidosas. Além disso, a auto-adaptação dispensa ajustes manuais de taxa de mutação. Seu custo computacional é maior que o da (1+1)-ES, mas ainda viável. Ela é usada em otimização de hiperparâmetros de redes neurais. Também é aplicada em design de aerofólios e roteamento de veículos. Para iniciantes, ela representa o salto natural após a (1+1)-ES.

A (μ,λ)-ES foi formalizada por Schwefel na década de 1970. Ela introduziu o conceito de “população” como um grupo de candidatos. Isso contrasta com a abordagem elitista estrita da (1+1)-ES. A escolha de μ e λ afeta diretamente a pressão seletiva do algoritmo. Valores maiores de λ aumentam a exploração, mas custam mais avaliações. Valores menores de μ concentram a busca nas melhores regiões. A razão λ/μ típica fica entre 3 e 7 para bons resultados. Os desvios-padrão evoluem conforme a regra do 1/5 ou via deriva genética. Na prática, a auto-adaptação log-normal é mais comum e robusta. Ela multiplica o sigma por exp(τ * N(0,1)), onde τ é uma constante. Isso permite que cada dimensão tenha seu próprio passo de mutação. Assim, a (μ,λ)-ES se adapta a escalas diferentes em cada variável. Ela é considerada uma das melhores para otimização contínua. Sua implementação é direta e seu desempenho é amplamente documentado.

Um exemplo clássico é minimizar a função de Ackley em 10 dimensões. Ela tem um mínimo global em (0,…,0) com valor 0. A superfície é cheia de mínimos locais, desafiando algoritmos simples. A (μ,λ)-ES encontra o ótimo com poucas gerações graças à diversidade. Esse problema demonstra o poder da recombinação e da população múltipla.

Enunciado do exemplo clássico

Implemente a (μ,λ)-ES com μ=15, λ=100 para minimizar a função de Ackley em 2 dimensões: f(x,y) = -20*exp(-0.2*sqrt(0.5*(x²+y²))) – exp(0.5*(cos(2πx)+cos(2πy))) + 20 + e. Domínio: x,y ∈ [-5, 5]. Use mutação com sigma inicial 0.5 e auto-adaptação log-normal. Execute por 200 gerações e armazene o melhor fitness e o melhor ponto por geração. Plote a curva de convergência e a trajetória do melhor ponto no espaço 2D.

import numpy as np  
import matplotlib.pyplot as plt  

# Função de Ackley (minimização)  
def ackley(x, y):  
    term1 = -20 * np.exp(-0.2 * np.sqrt(0.5 * (x**2 + y**2)))  
    term2 = -np.exp(0.5 * (np.cos(2*np.pi*x) + np.cos(2*np.pi*y)))  
    return term1 + term2 + 20 + np.e  

# Parâmetros  
mu = 15  
lambda_ = 100  
geracoes = 200  
dim = 2  
limites = [-5, 5]  
sigma_inicial = 0.5  
tau = 1.0 / np.sqrt(2 * dim)  # constante de aprendizado  

# Inicialização dos pais  
pais = np.random.uniform(limites[0], limites[1], size=(mu, dim))  
sigmas = np.full((mu, dim), sigma_inicial)  

# Históricos  
melhor_fitness_hist = []  
melhor_ponto_hist = []  

for gen in range(geracoes):  
    # Gerar λ filhos  
    filhos = np.zeros((lambda_, dim))  
    sigmas_filhos = np.zeros((lambda_, dim))  
    for i in range(lambda_):  
        # Escolher um pai aleatoriamente (com reposição)  
        idx_pai = np.random.randint(mu)  
        # Auto-adaptação dos sigmas  
        novo_sigma = sigmas[idx_pai] * np.exp(tau * np.random.normal(0, 1, size=dim))  
        novo_sigma = np.clip(novo_sigma, 1e-8, 10.0)  
        # Mutação do filho  
        filho = pais[idx_pai] + np.random.normal(0, novo_sigma)  
        filho = np.clip(filho, limites[0], limites[1])  
        filhos[i] = filho  
        sigmas_filhos[i] = novo_sigma  

    # Avaliar todos os filhos  
    fitness_filhos = np.array([ackley(f[0], f[1]) for f in filhos])  

    # Seleção (μ,λ): escolher os μ melhores filhos  
    indices_melhores = np.argsort(fitness_filhos)[:mu]  
    pais = filhos[indices_melhores]  
    sigmas = sigmas_filhos[indices_melhores]  

    # Registrar melhor da geração  
    melhor_idx = np.argmin(fitness_filhos)  
    melhor_fitness_hist.append(fitness_filhos[melhor_idx])  
    melhor_ponto_hist.append(filhos[melhor_idx].copy())  

# Resultado final  
melhor_final = min(melhor_fitness_hist)  
idx_final = melhor_fitness_hist.index(melhor_final)  
ponto_final = melhor_ponto_hist[idx_final]  
print(f"Melhor fitness encontrado: {melhor_final:.6f}")  
print(f"Ponto ótimo: x={ponto_final[0]:.6f}, y={ponto_final[1]:.6f}")  

# Gráfico 1: Curva de convergência  
plt.figure(figsize=(12, 5))  
plt.subplot(1, 2, 1)  
plt.semilogy(melhor_fitness_hist, 'b-', linewidth=2)  
plt.title('Convergência da (μ,λ)-ES na Ackley')  
plt.xlabel('Geração')  
plt.ylabel('Melhor f(x,y) (escala log)')  
plt.grid(True)  

# Gráfico 2: Trajetória do melhor ponto com contornos  
x_vals = np.linspace(limites[0], limites[1], 200)  
y_vals = np.linspace(limites[0], limites[1], 200)  
X, Y = np.meshgrid(x_vals, y_vals)  
Z = ackley(X, Y)  

plt.subplot(1, 2, 2)  
contour = plt.contourf(X, Y, Z, levels=50, cmap='plasma', alpha=0.8)  
plt.colorbar(contour, label='f(x,y)')  
pts = np.array(melhor_ponto_hist)  
plt.plot(pts[:,0], pts[:,1], 'w-', linewidth=1.5, alpha=0.7, label='Trajetória')  
plt.scatter(pts[0,0], pts[0,1], color='lime', s=80, label='Início')  
plt.scatter(pts[-1,0], pts[-1,1], color='red', s=100, label='Final')  
plt.scatter(0, 0, color='white', marker='*', s=200, label='Ótimo global')  
plt.title('Trajetória do Melhor Ponto - Ackley 2D')  
plt.xlabel('x')  
plt.ylabel('y')  
plt.legend()  
plt.grid(True)  
plt.tight_layout()  
plt.show()

import numpy as np

import matplotlib.pyplot as plt

# Função de Ackley (minimização)

def ackley(x, y):

term1 = -20 * np.exp(-0.2 * np.sqrt(0.5 * (x**2 + y**2)))

term2 = -np.exp(0.5 * (np.cos(2*np.pi*x) + np.cos(2*np.pi*y)))

return term1 + term2 + 20 + np.e

# Parâmetros

mu = 15

lambda_ = 100

geracoes = 200

dim = 2

limites = [-5, 5]

sigma_inicial = 0.5

tau = 1.0 / np.sqrt(2 * dim) # constante de aprendizado

# Inicialização dos pais

pais = np.random.uniform(limites[0], limites[1], size=(mu, dim))

sigmas = np.full((mu, dim), sigma_inicial)

# Históricos

melhor_fitness_hist = []

melhor_ponto_hist = []

for gen in range(geracoes):

# Gerar λ filhos

filhos = np.zeros((lambda_, dim))

sigmas_filhos = np.zeros((lambda_, dim))

for i in range(lambda_):

# Escolher um pai aleatoriamente (com reposição)

idx_pai = np.random.randint(mu)

# Auto-adaptação dos sigmas

novo_sigma = sigmas[idx_pai] * np.exp(tau * np.random.normal(0, 1, size=dim))

novo_sigma = np.clip(novo_sigma, 1e-8, 10.0)

# Mutação do filho

filho = pais[idx_pai] + np.random.normal(0, novo_sigma)

filho = np.clip(filho, limites[0], limites[1])

filhos[i] = filho

sigmas_filhos[i] = novo_sigma

# Avaliar todos os filhos

fitness_filhos = np.array([ackley(f[0], f[1]) for f in filhos])

# Seleção (μ,λ): escolher os μ melhores filhos

indices_melhores = np.argsort(fitness_filhos)[:mu]

pais = filhos[indices_melhores]

sigmas = sigmas_filhos[indices_melhores]

# Registrar melhor da geração

melhor_idx = np.argmin(fitness_filhos)

melhor_fitness_hist.append(fitness_filhos[melhor_idx])

melhor_ponto_hist.append(filhos[melhor_idx].copy())

# Resultado final

melhor_final = min(melhor_fitness_hist)

idx_final = melhor_fitness_hist.index(melhor_final)

ponto_final = melhor_ponto_hist[idx_final]

print(f"Melhor fitness encontrado: {melhor_final:.6f}")

print(f"Ponto ótimo: x={ponto_final[0]:.6f}, y={ponto_final[1]:.6f}")

# Gráfico 1: Curva de convergência

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

plt.subplot(1, 2, 1)

plt.semilogy(melhor_fitness_hist, 'b-', linewidth=2)

plt.title('Convergência da (μ,λ)-ES na Ackley')

plt.xlabel('Geração')

plt.ylabel('Melhor f(x,y) (escala log)')

plt.grid(True)

# Gráfico 2: Trajetória do melhor ponto com contornos

x_vals = np.linspace(limites[0], limites[1], 200)

y_vals = np.linspace(limites[0], limites[1], 200)

X, Y = np.meshgrid(x_vals, y_vals)

Z = ackley(X, Y)

plt.subplot(1, 2, 2)

contour = plt.contourf(X, Y, Z, levels=50, cmap='plasma', alpha=0.8)

plt.colorbar(contour, label='f(x,y)')

pts = np.array(melhor_ponto_hist)

plt.plot(pts[:,0], pts[:,1], 'w-', linewidth=1.5, alpha=0.7, label='Trajetória')

plt.scatter(pts[0,0], pts[0,1], color='lime', s=80, label='Início')

plt.scatter(pts[-1,0], pts[-1,1], color='red', s=100, label='Final')

plt.scatter(0, 0, color='white', marker='*', s=200, label='Ótimo global')

plt.title('Trajetória do Melhor Ponto - Ackley 2D')

plt.xlabel('x')

plt.ylabel('y')

plt.legend()

plt.grid(True)

plt.tight_layout()

plt.show()

Este código implementa a (μ,λ)-ES com auto-adaptação log-normal. A curva de convergência mostra queda acentuada nas primeiras gerações. A trajetória revela como o ponto se move pelo vale da função Ackley. Mesmo com muitos mínimos locais, o algoritmo encontra o global. A diversidade provida por λ=100 filhos é crucial para esse sucesso. Para iniciantes, este exemplo evidencia o poder das populações maiores. A (μ,λ)-ES é, portanto, uma ferramenta robusta e escalável.

Estratégia Evolutiva (1+1)-ES

16/07/202617/06/2026 Por antonino

O que é a (1+1)-ES?

A (1+1)-ES é a estratégia evolutiva mais simples que existe. Ela mantém apenas um indivíduo pai e gera um único filho por geração. O filho é criado pela adição de ruído gaussiano ao pai. Se o filho tiver aptidão melhor ou igual, ele substitui o pai. Caso contrário, o pai permanece inalterado para a próxima iteração. Esse mecanismo é chamado de seleção elitista (1+1). A notação indica que um pai e um filho competem pela sobrevivência. Apesar da simplicidade, ela é eficaz para funções contínuas e unimodais. Ela foi proposta por Rechenberg nos anos 1960 como protótipo inicial. Sua principal característica é a auto-adaptação do passo de mutação. O tamanho do passo é ajustado dinamicamente com base na taxa de sucesso. Assim, a (1+1)-ES aprende a velocidade ideal de exploração.

Regra de adaptação do passo (1/5 de sucesso)

Rechenberg introduziu uma regra heurística para ajustar o desvio-padrão. A cada geração, conta-se quantas mutações foram bem-sucedidas (filho aceito). Se a taxa de sucesso for maior que 1/5, o passo de mutação aumenta. Se for menor que 1/5, o passo diminui para refinar a busca local. Essa regra mantém a convergência próxima do ótimo de forma equilibrada. O fator de ajuste típico é multiplicar por 0.85 ou dividir por 0.85. Portanto, o algoritmo se torna autônomo e dispensa ajustes manuais. Isso é especialmente útil para iniciantes que não conhecem a paisagem.

Vantagens e limitações da abordagem

A grande vantagem é a extrema simplicidade de implementação e entendimento. Ela requer poucas linhas de código e nenhuma população grande. Além disso, o custo computacional por geração é mínimo. Contudo, ela pode estagnar em mínimos locais em funções multimodais. Sua natureza determinística (um filho) limita a diversidade exploratória. Para problemas com muitas variáveis, a convergência pode ser lenta. Mesmo assim, ela é um excelente ponto de partida didático. Muitos a utilizam para calibrar parâmetros em experimentos reais.

A (1+1)-ES é um caso particular das estratégias evolutivas maiores. Diferentemente da (μ, λ), ela não mantém múltiplos candidatos simultaneamente. Isso reduz drasticamente a memória e o tempo de avaliação por iteração. Por outro lado, a ausência de crossover limita a recombinação de boas características. Ainda assim, a mutação com passo adaptativo é surpreendentemente poderosa. Ela é capaz de resolver problemas com até dezenas de dimensões. A regra do 1/5 foi provada como ótima para funções esféricas. Em outros cenários, ela funciona bem na prática, embora sem garantia formal. O usuário deve monitorar a taxa de sucesso para evitar passos muito grandes. Passos grandes causam saltos que ultrapassam o ótimo repetidamente. Passos pequenos levam a uma convergência extremamente lenta. O equilíbrio é alcançado pela própria adaptação dinâmica. Assim, a (1+1)-ES ensina conceitos fundamentais de auto-ajuste. Ela é frequentemente a primeira estratégia evolutiva ensinada em cursos.

Um exemplo clássico é minimizar a função esférica f(x) = x₁² + x₂² + … + xₙ². O mínimo global está em (0,0,…,0) com valor zero. A (1+1)-ES encontra esse ponto com alta precisão após algumas centenas de gerações. O passo inicial é escolhido arbitrariamente, mas logo se ajusta. Esse problema é ideal para demonstrar a regra do 1/5 na prática.

Enunciado do exemplo clássico

Implemente a (1+1)-ES para minimizar a função de Rosenbrock em 2 dimensões: f(x,y) = (1 – x)² + 100*(y – x²)², com x,y ∈ [-2, 2]. O mínimo global é em (1,1) com f=0. Use passo inicial sigma=0.1. Aplique a regra de adaptação 1/5 com fator 0.85 a cada 10 gerações. Execute por 500 gerações e armazene o melhor valor e a distância até (1,1). Plote a evolução do valor da função e a trajetória do ponto no espaço 2D. Forneça o código Python completo e auto-contido.

import numpy as np  
import matplotlib.pyplot as plt  

# Função de Rosenbrock (aptidão - minimizar)  
def rosenbrock(x, y):  
    return (1 - x)**2 + 100 * (y - x**2)**2  

# Parâmetros  
sigma = 0.1  
fator = 0.85  
janela = 10  # a cada 10 gerações ajusta sigma  
geracoes = 500  
limites = [-2, 2]  

# Inicialização: ponto aleatório  
pai = np.random.uniform(limites[0], limites[1], size=2)  
fitness_pai = rosenbrock(pai[0], pai[1])  

# Históricos  
historico_fitness = [fitness_pai]  
historico_pontos = [pai.copy()]  
sucessos = 0  

for gen in range(geracoes):  
    # Gerar filho com mutação gaussiana  
    filho = pai + np.random.normal(0, sigma, size=2)  
    filho = np.clip(filho, limites[0], limites[1])  
    fitness_filho = rosenbrock(filho[0], filho[1])  

    # Seleção (1+1): substitui se filho for melhor ou igual  
    if fitness_filho <= fitness_pai:  
        pai = filho  
        fitness_pai = fitness_filho  
        sucessos += 1  

    # Registrar histórico  
    historico_fitness.append(fitness_pai)  
    historico_pontos.append(pai.copy())  

    # Adaptação do passo a cada janela de gerações  
    if (gen + 1) % janela == 0:  
        taxa_sucesso = sucessos / janela  
        if taxa_sucesso > 0.2:  # 1/5 = 0.2  
            sigma *= fator  
        elif taxa_sucesso < 0.2:  
            sigma /= fator  
        # Se for exatamente 0.2, mantém sigma  
        sucessos = 0  # reinicia contador  

# Resultado final  
print(f"Melhor solução: x = {pai[0]:.6f}, y = {pai[1]:.6f}")  
print(f"Valor mínimo de f(x,y) = {fitness_pai:.6f}")  
print(f"Distância até (1,1) = {np.linalg.norm(pai - np.array([1,1])):.6f}")  

# Gráfico 1: Evolução do fitness  
plt.figure(figsize=(12, 5))  
plt.subplot(1, 2, 1)  
plt.semilogy(historico_fitness, 'b-', linewidth=2)  
plt.title('Convergência da (1+1)-ES na Rosenbrock')  
plt.xlabel('Geração')  
plt.ylabel('f(x,y) (escala log)')  
plt.grid(True)  

# Gráfico 2: Trajetória no espaço 2D com contornos  
x_vals = np.linspace(limites[0], limites[1], 200)  
y_vals = np.linspace(limites[0], limites[1], 200)  
X, Y = np.meshgrid(x_vals, y_vals)  
Z = rosenbrock(X, Y)  

plt.subplot(1, 2, 2)  
contour = plt.contourf(X, Y, Z, levels=50, cmap='viridis', alpha=0.7)  
plt.colorbar(contour, label='f(x,y)')  
# Trajetória dos pontos (cada 5 gerações para não poluir)  
pts = np.array(historico_pontos)  
plt.plot(pts[:,0], pts[:,1], 'r-', linewidth=1, alpha=0.6, label='Trajetória')  
plt.scatter(pts[0,0], pts[0,1], color='green', s=80, label='Início')  
plt.scatter(pts[-1,0], pts[-1,1], color='red', s=100, label='Final')  
plt.scatter([1], [1], color='white', marker='*', s=200, label='Ótimo (1,1)')  
plt.title('Trajetória do Ponto no Espaço 2D')  
plt.xlabel('x')  
plt.ylabel('y')  
plt.legend()  
plt.grid(True)  
plt.tight_layout()  
plt.show()

import numpy as np

import matplotlib.pyplot as plt

# Função de Rosenbrock (aptidão - minimizar)

def rosenbrock(x, y):

return (1 - x)**2 + 100 * (y - x**2)**2

# Parâmetros

sigma = 0.1

fator = 0.85

janela = 10 # a cada 10 gerações ajusta sigma

geracoes = 500

limites = [-2, 2]

# Inicialização: ponto aleatório

pai = np.random.uniform(limites[0], limites[1], size=2)

fitness_pai = rosenbrock(pai[0], pai[1])

# Históricos

historico_fitness = [fitness_pai]

historico_pontos = [pai.copy()]

sucessos = 0

for gen in range(geracoes):

# Gerar filho com mutação gaussiana

filho = pai + np.random.normal(0, sigma, size=2)

filho = np.clip(filho, limites[0], limites[1])

fitness_filho = rosenbrock(filho[0], filho[1])

# Seleção (1+1): substitui se filho for melhor ou igual

if fitness_filho <= fitness_pai:

pai = filho

fitness_pai = fitness_filho

sucessos += 1

# Registrar histórico

historico_fitness.append(fitness_pai)

historico_pontos.append(pai.copy())

# Adaptação do passo a cada janela de gerações

if (gen + 1) % janela == 0:

taxa_sucesso = sucessos / janela

if taxa_sucesso > 0.2: # 1/5 = 0.2

sigma *= fator

elif taxa_sucesso < 0.2:

sigma /= fator

# Se for exatamente 0.2, mantém sigma

sucessos = 0 # reinicia contador

# Resultado final

print(f"Melhor solução: x = {pai[0]:.6f}, y = {pai[1]:.6f}")

print(f"Valor mínimo de f(x,y) = {fitness_pai:.6f}")

print(f"Distância até (1,1) = {np.linalg.norm(pai - np.array([1,1])):.6f}")

# Gráfico 1: Evolução do fitness

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

plt.subplot(1, 2, 1)

plt.semilogy(historico_fitness, 'b-', linewidth=2)

plt.title('Convergência da (1+1)-ES na Rosenbrock')

plt.xlabel('Geração')

plt.ylabel('f(x,y) (escala log)')

plt.grid(True)

# Gráfico 2: Trajetória no espaço 2D com contornos

x_vals = np.linspace(limites[0], limites[1], 200)

y_vals = np.linspace(limites[0], limites[1], 200)

X, Y = np.meshgrid(x_vals, y_vals)

Z = rosenbrock(X, Y)

plt.subplot(1, 2, 2)

contour = plt.contourf(X, Y, Z, levels=50, cmap='viridis', alpha=0.7)

plt.colorbar(contour, label='f(x,y)')

# Trajetória dos pontos (cada 5 gerações para não poluir)

pts = np.array(historico_pontos)

plt.plot(pts[:,0], pts[:,1], 'r-', linewidth=1, alpha=0.6, label='Trajetória')

plt.scatter(pts[0,0], pts[0,1], color='green', s=80, label='Início')

plt.scatter(pts[-1,0], pts[-1,1], color='red', s=100, label='Final')

plt.scatter([1], [1], color='white', marker='*', s=200, label='Ótimo (1,1)')

plt.title('Trajetória do Ponto no Espaço 2D')

plt.xlabel('x')

plt.ylabel('y')

plt.legend()

plt.grid(True)

plt.tight_layout()

plt.show()

Este código demonstra a (1+1)-ES na prática com visualização clara. A evolução do fitness em escala log mostra a rápida melhoria inicial. A trajetória revela como o ponto serpenteia até o vale da Rosenbrock. A regra do 1/5 ajusta o sigma automaticamente, sem intervenção manual. Mesmo sendo um único indivíduo, a busca é eficaz e estável. Para iniciantes, esse exemplo conecta teoria, código e gráficos intuitivos. A (1+1)-ES é, portanto, uma porta de entrada simples para computação evolutiva.