Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark

Resumo Técnico: Análise de Tempo de Execução do Algoritmo Genético Compacto (cGA) no Benchmark LeadingOnes

1. Problema e Contexto

O artigo aborda uma lacuna significativa na teoria dos Algoritmos de Estimação de Distribuição (EDAs). Embora o Algoritmo Genético Compacto (cGA) seja um dos EDAs mais simples e amplamente estudados, e o benchmark LeadingOnes seja um dos problemas mais analisados na computação evolutiva, não existia até então uma análise rigorosa de tempo de execução (runtime analysis) do cGA especificamente no problema LeadingOnes.

• O Problema LeadingOnes: Dado um vetor binário de tamanho $n$, a função de aptidão (fitness) retorna o comprimento do maior prefixo de uns consecutivos. É um problema unimodal, mas desafiador para heurísticas aleatórias devido à dependência sequencial dos bits (o bit na posição $k+1$ só contribui para a aptidão se todos os bits anteriores forem 1).
• O Algoritmo cGA: Um EDA univariado que mantém um vetor de frequências de probabilidade. Em cada iteração, amostra duas soluções, compara suas aptidões e atualiza as frequências em direção ao vencedor com um passo de tamanho $1/\mu$, onde $\mu$ é o tamanho da população hipotética.
• A Lacuna: Enquanto o algoritmo UMDA (Univariate Marginal Distribution Algorithm), um EDA similar mas que usa amostragem maior, já possuía análises de tempo de execução para LeadingOnes, o cGA carecia dessa prova formal, apesar de ser um algoritmo fundamental na área.

2. Metodologia

Os autores realizam uma análise teórica rigorosa baseada em análise de deriva (drift analysis) e ferramentas probabilísticas.

• Regime de Baixa Deriva Genética: A análise foca no regime onde o parâmetro $\mu$ é suficientemente grande ($\mu = \Omega(n \log^2 n)$) para garantir que flutuações aleatórias (deriva genética) não dominem o processo de atualização do modelo probabilístico.
• Ferramentas Matemáticas:
  • Teorema de Deriva Multiplicativa (Theorem 1): Usado para provar que as frequências convergem rapidamente para o valor ideal (próximo de 1) quando há um viés positivo.
  • Teorema de Deriva Negativa (Theorem 2): Utilizado para provar que, mesmo sob flutuações, as frequências não caem drasticamente abaixo de um certo limiar antes que a otimização seja concluída.
  • Teorema de Deriva Genética (Theorem 3): Garante que, com alta probabilidade, as frequências não se fixam em valores errados devido ao ruído aleatório.
• Estratégia de Prova Indutiva:
  1. Definir uma "posição crítica" $i$ como a menor posição onde a frequência $p_i$ está abaixo de $1 - 3/n$.
  2. Provar que, com alta probabilidade, essa posição crítica avança para a direita (de $i$ para $i+1$) a cada $O(\mu \log n)$ iterações.
  3. Demonstrar que, uma vez que todas as frequências estão próximas de 1, a amostragem do ótimo global ocorre rapidamente.

3. Principais Contribuições

• Primeira Análise Rigorosa: O trabalho fornece a primeira prova formal do tempo de execução do cGA no benchmark LeadingOnes.
• Limites Superiores de Tempo: Estabelece que, para um tamanho de problema $n$ e um parâmetro $\mu = \Omega(n \log^2 n)$, o cGA encontra o ótimo com alta probabilidade em $O(\mu n \log n)$ avaliações de função.
• Otimização do Parâmetro: Ao escolher o melhor $\mu = \Theta(n \log^2 n)$, o tempo de execução total é de $O(n^2 \log^3 n)$.
• Comparação com UMDA: O artigo destaca as diferenças fundamentais no comportamento de otimização entre o cGA e o UMDA, explicando por que o cGA pode ter um limite ligeiramente pior (fator polilogarítmico).

4. Resultados Chave

• Complexidade Temporal: O limite superior provado é $O(n^2 \log^3 n)$. Isso é ligeiramente pior do que o limite comum de $O(n^2)$ observado em muitas outras heurísticas (como o (1+1) EA) e no UMDA (que tem um limite de $\Theta(n^2 \log n)$ no regime de baixa deriva). A diferença é um fator de $O(\log^3 n)$ ou $O(\log^2 n)$, dependendo da comparação específica.
• Mecanismo de Atualização: A análise revela que o cGA, devido ao seu tamanho de amostra de apenas dois indivíduos, sofre de uma instabilidade maior. Enquanto o UMDA (com amostras maiores) consegue manter um segmento inicial de frequências no limite superior (1) de forma estável, o cGA frequentemente vê essas frequências oscilarem para baixo devido a amostragens onde ambos os indivíduos têm zeros em posições diferentes dentro do prefixo de uns.
• Estabilidade: O cGA requer um $\mu$ maior para manter a estabilidade necessária, o que contribui para o tempo de execução ligeiramente mais longo em comparação ao UMDA.

5. Significado e Conclusão

• Validação Teórica: O trabalho confirma que o cGA, apesar de sua simplicidade (apenas um parâmetro), é capaz de otimizar o LeadingOnes eficientemente, embora com um custo polilogarítmico adicional em comparação a algoritmos mais complexos como o UMDA.
• Insights sobre Dinâmica de EDAs: A análise expõe diferenças sutis nos princípios de funcionamento. O cGA é mais sensível a flutuações aleatórias devido à sua pequena amostra de atualização (2 indivíduos), o que torna o processo de "consertar" frequências no limite superior mais lento e instável do que no UMDA.
• Problema Aberto: Os autores destacam que, embora tenham provado um limite superior, não existe ainda um limite inferior (lower bound) correspondente. Portanto, não se pode afirmar com certeza se a diferença de desempenho é inerente aos algoritmos ou apenas uma artefato da análise atual. Provar um limite inferior que corresponda ao limite superior é considerado um problema difícil e aberto na área.

Em resumo, este artigo preenche uma lacuna teórica importante, demonstrando que o cGA é viável para LeadingOnes, mas também esclarece matematicamente por que algoritmos com tamanhos de amostra maiores (como o UMDA) podem ser teoricamente mais eficientes em cenários específicos de otimização sequencial.