Computação Evolucionária e Algoritmos Genéticos

Até aqui, cada algoritmo explorou uma estrutura explícita: custos, heurísticas, adversários ou restrições. Agora manteremos várias soluções simultaneamente e produziremos novas candidatas combinando partes das anteriores. A inspiração vem da evolução biológica, mas o resultado é engenharia: uma família de métodos estocásticos de otimização chamada computação evolucionária.

Um algoritmo genético não prova que encontrou o ótimo e não recebe virtude científica por mencionar cromossomos. Seu desempenho depende da codificação, dos operadores e da forma de medir. Uma representação ruim faz o cruzamento fabricar lixo com eficiência; uma pressão seletiva excessiva transforma a população em uma cópia prematura do primeiro indivíduo razoável. A biologia fornece a metáfora. O projeto do algoritmo continua sendo nosso.

1. Metáfora biológica e o laço evolutivo

Um indivíduo codifica uma solução candidata. O conjunto de indivíduos é a população. A aptidão mede a qualidade de cada candidato. Uma geração aplica seleção de pais, recombinação, mutação, avaliação e substituição para construir a população seguinte.

O laço fundamental pode ser escrito como

na qual $P_t$ é a população na geração $t$. A fórmula esconde decisões importantes. Selecionar pode significar roleta, torneio ou posto; substituir pode conservar a elite ou trocar toda a população; mutar pode inverter bits, trocar posições ou adicionar ruído gaussiano.

O algoritmo para quando atinge um orçamento de avaliações, uma qualidade-alvo ou um número de gerações sem melhora. Convergiu não significa automaticamente chegou ao ótimo; pode significar apenas que a população perdeu diversidade e já não produz novidades.

2. Representação

A representação define quais soluções existem para o algoritmo e quais vizinhanças os operadores conseguem explorar. em uma mochila com oito itens, um cromossomo binário de oito bits é natural: o bit $i$ vale $1$ quando o item $i$ é escolhido. Para parâmetros contínuos, genes reais evitam converter precisão em cadeias binárias. Para o caixeiro-viajante, o cromossomo precisa ser uma permutação das cidades.

Os operadores devem respeitar a representação. Inverter um bit preserva um vetor binário. Trocar duas posições preserva uma permutação. Cruzar duas rotas cortando e colando sufixos, porém, pode repetir uma cidade e apagar outra. O cruzamento de ordem, ou OX, copia um segmento de um pai e preenche as posições restantes na ordem em que as cidades aparecem no outro.

Há três estratégias para restrições. A primeira atribui baixa aptidão a indivíduos inválidos. A segunda repara o indivíduo depois do operador. A terceira projeta a codificação para que estados inválidos não possam nascer. A terceira é elegante quando possível; a segunda pode introduzir um viés invisível; a primeira permite explorar perto da fronteira, mas exige uma penalidade calibrada.

3. Função de aptidão

A função de aptidão $\operatorname{fit}(x)$ transforma um indivíduo $x$ em um número usado pela seleção. Para a mochila, vamos adotar pesos

e valores

com capacidade $15$. O cromossomo $11000011$, escrito na ordem dos itens $0$ a $7$, seleciona os itens $0$, $1$, $6$ e $7$. Seu peso é $2+3+4+1=10$ e seu valor é $6+5+7+3=21$.

Uma aptidão simples é o valor total quando o peso respeita a capacidade e zero caso contrário:

Essa escolha cria um penhasco: uma solução de peso $16$ e valor alto recebe o mesmo zero de uma seleção inútil. Uma penalidade gradual preservaria informação sobre proximidade, por exemplo $\sum_i v_ix_i-\lambda\max(0,\sum_iw_ix_i-15)$. O coeficiente $\lambda$ precisa ser declarado, porque muda a paisagem.

Exercícios resolvidos

1. Avalie o cromossomo $11000011$.

Solução:

Ele pesa $10$, vale $21$ e é viável. Sua aptidão pela regra acima é $21$.

2. Como transformar um custo $c(x)\ge0$ em aptidão de maximização?

Solução:

Podemos usar $1/(1+c(x))$. Custos menores produzem aptidões maiores sem exigir um limite superior conhecido.

3. O que ocorre quando todas as aptidões são quase iguais?

Solução:

A seleção se aproxima de um sorteio uniforme. A pressão seletiva fica baixa e o progresso médio tende a ser lento.

4. Para aptidões ${10,12,14,90}$, qual fração da roleta pertence ao valor $90$?

Solução:

A soma é $126$ e a fração é $90/126\approx71{,}43\%$. Um indivíduo domina a reprodução e ameaça a diversidade.

5. Qual é a diferença entre penalizar e reparar uma mochila acima da capacidade?

Solução:

Penalizar mantém o cromossomo e reduz sua aptidão. Reparar remove itens até torná-lo viável, alterando o ponto produzido pelo operador e introduzindo a política de remoção no algoritmo.

4. Seleção

Na seleção por roleta, a probabilidade do indivíduo $i$ é

desde que as aptidões sejam não negativas e a soma seja positiva. Para ${3,1,6,2}$, obtemos ${0{,}25,0{,}0833,0{,}5,0{,}1667}$. A escala absoluta importa: somar uma constante a todas as aptidões muda as probabilidades mesmo preservando a ordem.

Na seleção por torneio, sorteamos $k$ indivíduos e escolhemos o melhor. Com população de tamanho $N$ e sorteios com reposição, a probabilidade de o melhor aparecer em um torneio é

Para $N=4$ e $k=2$, vale $1-(3/4)^2=7/16=43{,}75\%$. Aumentar $k$ eleva a pressão seletiva sem depender da escala das aptidões. A seleção por posto também usa a ordem, não os valores crus, atribuindo pesos segundo a posição no ranking.

Exercícios resolvidos

1. Calcule a roleta para ${3,1,6,2}$.

Solução:

Dividindo pela soma $12$, obtemos $0{,}25$, $0{,}0833$, $0{,}5$ e $0{,}1667$.

2. Qual é a probabilidade de o melhor participar de um torneio de tamanho dois em uma população de quatro, com reposição?

Solução:

Há duas formas complementares de fazer a conta:

Portanto, mesmo sendo o melhor da população, ele participa de menos da metade dos torneios de tamanho dois.

3. Por que o torneio é invariável a uma transformação crescente da aptidão?

Solução:

Ele compara posições relativas. Qualquer transformação estritamente crescente preserva quem vence cada torneio.

4. Que risco surge ao aumentar muito $k$?

Solução:

Poucos indivíduos passam a gerar a maior parte da descendência. A população perde diversidade e pode convergir antes do ótimo.

5. Por que a roleta falha com aptidões negativas?

Solução:

Probabilidades não podem ser negativas. É preciso deslocar ou escalonar os valores, ou usar um método baseado em ranking.

5. Cruzamento

O cruzamento de um ponto escolhe um corte $c$ e combina o prefixo de um pai com o sufixo do outro. Para

os filhos são $1100\mid0111$ e $0011\mid1010$. Dois pontos trocam apenas o segmento entre os cortes. O cruzamento uniforme usa uma máscara para decidir, gene a gene, de qual pai cada posição virá.

O operador pressupõe que blocos próximos no cromossomo representem componentes que vale preservar juntos. Se genes fortemente relacionados estão distantes, um corte tende a separá-los. Essa dependência entre codificação e cruzamento é chamada de ligação, ou linkage. O operador não descobre automaticamente a semântica dos bits.

Exercícios resolvidos

1. Cruze $11001010$ e $00110111$ após o quarto bit.

Solução:

Os filhos são $11000111$ e $00111010$.

2. O que muda no cruzamento de dois pontos?

Solução:

Troca-se o segmento central entre dois cortes, preservando os prefixos e sufixos de seus respectivos pais.

3. Com máscara $10101010$, como funciona o cruzamento uniforme?

Solução:

Nas posições com máscara $1$, o primeiro filho recebe o gene do primeiro pai; nas demais, recebe o do segundo. O outro filho faz o complemento.

4. Por que um ponto é inadequado para rotas?

Solução:

A colagem pode repetir cidades presentes nos dois trechos e eliminar cidades ausentes, produzindo uma sequência que não é permutação.

5. Como OX preserva uma rota válida?

Solução:

Copia um segmento de um pai e preenche as lacunas com as cidades ainda ausentes na ordem do outro pai. Cada cidade aparece exatamente uma vez.

6. Mutação e elitismo

A mutação reintroduz variação. em um cromossomo binário, cada bit pode ser invertido com probabilidade $p_m$. O número esperado de mutações em $L$ bits é $Lp_m$. Para $L=20$ e $p_m=0{,}01$, a esperança é $0{,}2$ bit por indivíduo. Esperança não é promessa: a maioria não muda, alguns mudam uma vez e poucos mudam mais.

Taxa baixa demais não recupera alelos perdidos; taxa alta demais destrói a herança e aproxima a busca de amostragem aleatória. Para genes reais, uma mutação comum é $x’=x+\mathcal{N}(0,\sigma^2)$, na qual $\sigma$ controla o tamanho típico do passo.

O elitismo copia os melhores indivíduos intactos para a geração seguinte. Se ao menos uma cópia do melhor sobrevive, a melhor aptidão observada nunca diminui. Isso não garante progresso e pode acelerar a homogeneização, mas preserva descobertas que cruzamento e mutação poderiam apagar.

Exercícios resolvidos

1. Quantos bits esperamos mutar com $L=20$ e $p_m=0{,}01$?

Solução:

$20\cdot0{,}01=0{,}2$.

2. Por que elitismo impede regressão do melhor valor?

Solução:

O argumento pode ser resumido pela comparação entre as duas populações:

Como os demais descendentes ainda podem superar essa cópia, concluímos que $\max\operatorname{fit}(P_{t+1})\ge\max\operatorname{fit}(P_t)$. O elitismo impede a regressão do melhor valor, embora não garanta que ele aumente.

3. Qual mutação preserva uma permutação?

Solução:

Trocar duas posições, inverter um segmento ou mover um elemento. Bit-flip não se aplica a cidades.

4. O que ocorre quando $p_m=0{,}5$ em bits independentes?

Solução:

Cada bit do descendente se torna quase independente do original. A herança desaparece e o operador se aproxima de gerar outra cadeia aleatória.

5. O que $\sigma$ controla na mutação gaussiana?

Solução:

O desvio-padrão da perturbação, portanto o tamanho típico do passo no espaço real.

7. Convergência, esquemas e diversidade

Um esquema é um padrão sobre ${0,1,*}$, no qual * aceita qualquer bit. O esquema $1**0$ contém as cadeias de quatro bits que começam em $1$ e terminam em $0$. Sua ordem é o número de posições fixas, aqui $2$; seu comprimento de definição é a distância entre a primeira e a última posição fixa, aqui $3$.

O teorema dos esquemas de Holland fornece, para o algoritmo genético canônico, um limite inferior para o número esperado de representantes de um esquema na geração seguinte. Esquemas com aptidão acima da média, baixa ordem e pequeno comprimento têm maior chance de sobreviver à seleção, ao cruzamento e à mutação. O resultado é uma desigualdade sob hipóteses específicas, não uma prova de que qualquer algoritmo genético encontra o ótimo.

Medimos diversidade binária pela distância de Hamming. Para uma população $P$ com $N$ indivíduos de comprimento $L$, a distância média entre pares é

Quando $\bar d_H$ cai perto de zero, cruzar indivíduos quase idênticos produz pouca novidade. Ilhas, mutação adaptativa, compartilhamento de aptidão e reinicialização parcial são respostas possíveis, mas cada uma muda o algoritmo e precisa ser avaliada.

Exercícios resolvidos

1. Quais cadeias de quatro bits pertencem a $1**0$?

Solução:

$1000$, $1010$, $1100$ e $1110$.

2. Qual é a ordem e o comprimento de definição de $1**0$?

Solução:

Ordem $2$ e comprimento $3$.

3. Por que uma população homogênea caracteriza convergência prematura?

Solução:

Os operadores recombinam quase os mesmos alelos; a busca perde caminhos para regiões não representadas antes de alcançar a melhor solução.

4. Qual é a distância de Hamming entre $11001010$ e $10011110$?

Solução:

As cadeias diferem nas posições $1$, $3$ e $5$, usando índices iniciados em zero. A distância é $3$.

5. O teorema dos esquemas garante o ótimo?

Solução:

Não. Ele limita a reprodução esperada de esquemas sob um modelo específico. Populações finitas, amostragem, ligação e operadores diferentes impedem essa leitura triunfalista.

8. Uma mochila evolutiva em C++23

O programa abaixo resolve a mochila de oito itens. Antes de confiar no algoritmo genético, enumera os $2^8=256$ cromossomos e obtém o ótimo exato, valor $27$, peso $15$, cromossomo decimal $211$. Depois executa 32 sementes, sempre com população, orçamento e operadores idênticos. No MSVC 19.51, usamos cl /std:c++latest /permissive- /W4 /EHsc /utf-8 /O2 genetico.cpp.

#include <algorithm>
#include <array>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <random>
#include <ranges>
#include <vector>

constexpr std::size_t genes = 8;
constexpr std::uint16_t mascara_genes = (1u << genes) - 1u;
constexpr int capacidade = 15;
constexpr std::array pesos{2, 3, 6, 7, 5, 9, 4, 1};
constexpr std::array valores{6, 5, 8, 9, 6, 10, 7, 3};

struct Individuo {
    std::uint16_t cromossomo{};
    int aptidao{};
};

[[nodiscard]] constexpr std::pair<int, int> peso_valor(
    const std::uint16_t cromossomo) noexcept {
    int peso = 0;
    int valor = 0;
    for (std::size_t i = 0; i < genes; ++i) {
        if ((cromossomo & (1u << i)) != 0) {
            peso += pesos[i];
            valor += valores[i];
        }
    }
    return {peso, valor};
}

[[nodiscard]] constexpr int avaliar(
    const std::uint16_t cromossomo) noexcept {
    const auto [peso, valor] = peso_valor(cromossomo);
    return peso <= capacidade ? valor : 0;
}

[[nodiscard]] Individuo torneio(
    const std::vector<Individuo>& populacao, std::mt19937& gerador) {
    std::uniform_int_distribution<std::size_t> indice{
        0, populacao.size() - 1};
    const Individuo a = populacao[indice(gerador)];
    const Individuo b = populacao[indice(gerador)];
    return a.aptidao >= b.aptidao ? a : b;
}

[[nodiscard]] std::uint16_t cruzar(
    const std::uint16_t a,
    const std::uint16_t b,
    std::mt19937& gerador) {
    std::uniform_int_distribution<int> corte{1, static_cast<int>(genes - 1)};
    const int posicao = corte(gerador);
    const auto mascara_baixa =
        static_cast<std::uint16_t>((1u << posicao) - 1u);
    return static_cast<std::uint16_t>(
        ((a & mascara_baixa) | (b & ~mascara_baixa)) & mascara_genes);
}

[[nodiscard]] std::uint16_t mutar(
    std::uint16_t cromossomo, std::mt19937& gerador) {
    std::bernoulli_distribution inverte{0.05};
    for (std::size_t i = 0; i < genes; ++i) {
        if (inverte(gerador)) {
            cromossomo ^= static_cast<std::uint16_t>(1u << i);
        }
    }
    return cromossomo;
}

[[nodiscard]] Individuo executar(const std::uint32_t semente) {
    constexpr std::size_t tamanho_populacao = 128;
    constexpr int geracoes = 80;
    std::mt19937 gerador{semente};
    std::uniform_int_distribution<int> alelo{0, mascara_genes};

    std::vector<Individuo> populacao;
    populacao.reserve(tamanho_populacao);
    for (std::size_t i = 0; i < tamanho_populacao; ++i) {
        const auto cromossomo = static_cast<std::uint16_t>(alelo(gerador));
        populacao.push_back({cromossomo, avaliar(cromossomo)});
    }

    for (int geracao = 0; geracao < geracoes; ++geracao) {
        const auto melhor = std::ranges::max_element(
            populacao, {}, &Individuo::aptidao);
        std::vector<Individuo> proxima;
        proxima.reserve(tamanho_populacao);
        proxima.push_back(*melhor);

        while (proxima.size() < tamanho_populacao) {
            const Individuo pai = torneio(populacao, gerador);
            const Individuo mae = torneio(populacao, gerador);
            const std::uint16_t filho =
                mutar(cruzar(pai.cromossomo, mae.cromossomo, gerador), gerador);
            proxima.push_back({filho, avaliar(filho)});
        }
        populacao = std::move(proxima);
    }

    return *std::ranges::max_element(
        populacao, {}, &Individuo::aptidao);
}

int main() {
    Individuo otimo;
    for (std::uint16_t cromossomo = 0;
         cromossomo <= mascara_genes;
         ++cromossomo) {
        const int aptidao = avaliar(cromossomo);
        if (aptidao > otimo.aptidao) {
            otimo = {cromossomo, aptidao};
        }
    }

    constexpr std::uint32_t execucoes = 32;
    std::vector<int> melhores;
    melhores.reserve(execucoes);
    std::size_t sucessos = 0;
    for (std::uint32_t semente = 0; semente < execucoes; ++semente) {
        const Individuo resultado = executar(semente);
        melhores.push_back(resultado.aptidao);
        sucessos += resultado.aptidao == otimo.aptidao ? 1u : 0u;
    }
    std::ranges::sort(melhores);
    const int mediana = melhores[melhores.size() / 2];
    const auto [peso_otimo, valor_otimo] = peso_valor(otimo.cromossomo);

    std::cout << "otimo exato: cromossomo=" << otimo.cromossomo
              << ", peso=" << peso_otimo
              << ", valor=" << valor_otimo << '\n';
    std::cout << "sucessos=" << sucessos << '/' << execucoes
              << ", mediana=" << mediana << '\n';

    return sucessos == execucoes && mediana == otimo.aptidao ? 0 : 2;
}

peso_valor é constexpr, portanto pode ser usado tanto na enumeração de referência quanto na busca estocástica. O elitismo copia o melhor indivíduo antes de gerar descendentes. A comparação com o ótimo exato impede que uma curva ascendente seja confundida com solução correta. Em problemas grandes, o ótimo não estará disponível; ainda assim, múltiplas sementes, orçamento igual, quantis e melhor limite conhecido continuam obrigatórios.

O laboratório usa os mesmos oito itens. Ajuste população e mutação, reinicie com a mesma semente e observe a aptidão máxima, a média e a diversidade. Uma taxa que produz uma curva bonita em uma única execução continua sendo apenas uma anedota animada.

9. Evolução não absolve metodologia

Representação define o espaço; aptidão define o que conta como progresso; seleção controla quem se reproduz; cruzamento recombina; mutação recupera variação; elitismo preserva a melhor evidência. O algoritmo genético não elimina as escolhas de projeto. Ele as concentra.

No próximo artigo, trocaremos população por conhecimento explícito. Uma linguagem lógica dirá o que o agente sabe, e regras de inferência dirão o que ele pode concluir.

Acrônimos e Abreviações neste artigo

A seguir está a lista de todos os acrônimos e abreviações identificados no texto, organizados em ordem alfabética com o termo original em inglês e a tradução para o português:

Referências

EIBEN, A. E.; SMITH, J. E. Introduction to evolutionary computing. 2. ed. Berlin: Springer, 2015. DOI: https://doi.org/10.1007/978-3-662-44874-8. Acesso em: 24 jul. 2026.

HOLLAND, J. H. Adaptation in natural and artificial systems. Cambridge: MIT Press, 1992. Disponível em: https://mitpress.mit.edu/9780262581110/adaptation-in-natural-and-artificial-systems/. Acesso em: 24 jul. 2026.

LUGER, G. F. Artificial Intelligence: structures and strategies for complex problem solving. 6. ed. Albuquerque: University of New Mexico, 2009. Disponível em: https://www.cs.unm.edu/~luger/ai-final/. Acesso em: 24 jul. 2026.

MICROSOFT. Microsoft C/C++ language conformance by Visual Studio version. Redmond, 2026. Disponível em: https://learn.microsoft.com/en-us/cpp/overview/visual-cpp-language-conformance?view=msvc-170. Acesso em: 24 jul. 2026.

RUSSELL, S.; NORVIG, P. Artificial Intelligence: a modern approach. 4. ed. Hoboken: Pearson, 2020. Disponível em: https://aima.cs.berkeley.edu/. Acesso em: 24 jul. 2026.

WHITLEY, D. A genetic algorithm tutorial. Statistics and Computing, Dordrecht, v. 4, p. 65–85, 1994. Disponível em: https://www.cs.colostate.edu/~genitor/Pubs.html. Acesso em: 24 jul. 2026.