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.
|
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 |
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.