Computação Evolucionária

Em 22 de março de 2006 a NASA lançou três satélites com uma antena que ninguém desenhou. Ela parece um clipe de papel torturado, não tem sim...

Em 22 de março de 2006 a NASA lançou três satélites com uma antena que ninguém desenhou. Ela parece um clipe de papel torturado, não tem simetria nenhuma, e nenhum engenheiro seria capaz de justificar cada dobra — porque as dobras não foram escolhidas: foram selecionadas, geração após geração, por um programa que só sabia pontuar candidatos e deixar os piores morrerem. A antena evoluída rendeu 93% de eficiência contra 38% do par convencional e ficou pronta em cerca de três pessoas-mês. Neste quarto post da série sobre inteligência artificial, abrimos a caixa da computação evolucionária: você vai montar um algoritmo genético peça por peça — codificação, população, aptidão, seleção, cruzamento, mutação, elitismo e parada — e depois soltar um enxame de partículas e uma colônia de formigas na mesma tela, com quatro laboratórios interativos, três tutoriais em Python já executados e a pergunta incômoda no fim: quando essa turma toda vale a pena, e quando é só barulho caro.

A antena tem uns quatro centímetros e meio. Fio de metal dobrado em ângulos que parecem aleatórios, sem nenhuma daquelas curvas elegantes que a gente associa a engenharia aeroespacial. Se você a encontrasse numa gaveta, jogaria fora. Ela voou na missão Space Technology 5 e é, até onde se sabe, o primeiro hardware evoluído por computador a operar no espaço (HORNBY et al., 2006).

"Em 22 de março de 2006 a missão ST5 foi lançada com sucesso tendo a antena evoluída ST5-33-142-7 como uma de suas antenas. Esta antena evoluída é a primeira antena evoluída por computador a ser empregada em qualquer aplicação e é o primeiro hardware evoluído por computador no espaço."

Hornby, Globus, Linden e Lohn, AIAA Space 2006, na tradução do autor (HORNBY et al., 2006)

O detalhe que interessa aqui não é a antena. É o método. Ninguém escreveu "dobre 42 graus no terceiro segmento". Alguém escreveu um juiz: um programa que, dado um formato qualquer de fio, calcula o quanto ele irradia bem nas frequências e ângulos que a missão exige. E então soltou milhares de formatos aleatórios contra esse juiz, guardou os melhores, misturou-os, bagunçou-os um pouco e repetiu. O resultado é feio, funciona melhor que o desenho humano e — este é o ponto — é bom sem que ninguém saiba explicar por quê.

Isso é computação evolucionária. Este post desmonta a ideia peça por peça, com quatro laboratórios que rodam aqui mesmo na página e três programas em Python que você pode colar no Google Colab. No caminho, vamos ser honestos sobre os limites: existe um teorema que garante que nenhum desses métodos é bom em geral, e há muita aplicação por aí que seria melhor resolvida com uma planilha.

Geração 01

Otimizar é procurar num espaço grande demais

Simetria é uma preferência humana, não um requisito da física. Ilustração do autor (2026)

Comece por um problema mundano: você tem vinte objetos, cada um com um valor e um peso, e uma mochila que aguenta 50 quilos. Quais levar? Cada objeto entra ou não entra, então há 2²⁰ combinações possíveis — 1.048.576. Um computador testa todas em menos de um segundo. Sem drama.

Agora são cem objetos. As combinações passam a 2¹⁰⁰, um número com 31 dígitos. Se você testasse um bilhão de combinações por segundo desde o Big Bang, ainda não teria terminado uma fração perceptível da lista. E cem objetos é um problema pequeno: uma grade de distribuição elétrica tem milhares de chaves; um voo tem centenas de tripulantes para escalar; uma molécula candidata a fármaco tem dezenas de ângulos de torção que variam continuamente.

Diante disso existem três atitudes. A primeira é resolver exatamente: quando o problema tem estrutura matemática favorável — linearidade, convexidade, subestrutura ótima — há algoritmos que devolvem a resposta comprovadamente ótima. Programação linear, programação dinâmica, branch and bound. Sempre que essa porta estiver aberta, entre por ela: metaheurística é o que se usa quando a matemática exata não alcança, não quando ela dá trabalho.

A segunda é usar uma heurística: uma regra prática, específica do problema, que dá uma resposta razoável rapidamente. "Pegue sempre o objeto com maior valor por quilo." "Vá sempre para a cidade mais próxima ainda não visitada." Heurísticas são rápidas e frequentemente boas. Também são frequentemente enganadas — a regra do vizinho mais próximo, por exemplo, costuma deixar uma última cidade absurdamente longe para o fim.

A terceira é usar uma metaheurística: um esqueleto de busca genérico, que não sabe nada sobre mochilas ou antenas, e que se conecta ao problema por uma única porta — uma função que dá nota a candidatos. É a família da computação evolucionária. O preço dessa generalidade é que ela nunca prova que achou o ótimo: devolve o melhor que encontrou no tempo que teve.

O dilema que atravessa tudo: explorar ou aproveitar

Toda busca vive uma tensão. Exploração (exploration) é vasculhar regiões novas do espaço, arriscando desperdiçar tempo em lugares ruins. Aproveitamento (exploitation) é cavar mais fundo onde já se achou algo bom, arriscando ficar preso numa boa solução local enquanto a ótima está do outro lado do mapa. Exploração demais vira busca aleatória; aproveitamento demais vira convergência prematura. Cada operador que você vai conhecer daqui em diante é, no fundo, um botão que regula essa proporção.

Geração 02

Turing já tinha dito, três décadas antes

Em 1948, num relatório interno do National Physical Laboratory britânico que ficou inédito por vinte anos, Alan Turing dividiu a atividade intelectual em três tipos de busca. Uma delas era a busca genética: "existe a busca genética ou evolucionária, pela qual se procura uma combinação de genes, sendo o critério o valor de sobrevivência" (TURING, 1969). Dois anos depois, no artigo famoso sobre o teste que leva seu nome, ele detalhou a analogia ao propor que não se programasse uma mente adulta, e sim uma mente de criança sujeita a um processo de aprendizagem: "estrutura da máquina-criança = material hereditário; mudanças na máquina-criança = mutações; seleção natural = julgamento do experimentador" (TURING, 1950).

A ideia foi reinventada de forma independente em pelo menos três lugares. Na Alemanha, na primeira metade dos anos 1960, três estudantes da Universidade Técnica de Berlim — Ingo Rechenberg, Hans-Paul Schwefel e Peter Bienert — tentavam otimizar formatos em túnel de vento e esbarravam num problema chato: os métodos clássicos de gradiente exigem medições precisas, e medições de escoamento turbulento são ruidosas. A saída foi perturbar todas as variáveis ao mesmo tempo, ao acaso, com mutações pequenas mais prováveis que grandes, e ficar com a variante melhor. Em junho de 1964 rodaram o experimento da placa articulada — sem computador nenhum, ajustando o equipamento à mão a cada geração (BEYER; SCHWEFEL, 2002). Nascia a estratégia evolutiva (Evolutionsstrategie), sistematizada por Rechenberg em 1973 (RECHENBERG, 1973).

Nos Estados Unidos, Lawrence Fogel, Alvin Owens e Michael Walsh evoluíam populações de autômatos de estados finitos para prever sequências de símbolos, usando apenas mutação e seleção — sem recombinação. Era a programação evolutiva (FOGEL; OWENS; WALSH, 1966).

E em Michigan, John Holland fazia a pergunta mais teórica de todas: o que é, formalmente, um sistema que se adapta? Seu livro de 1975 estabeleceu o vocabulário que usamos até hoje — planos reprodutivos, esquemas, blocos construtivos — e deu nome ao método que este post vai desmontar: o algoritmo genético (HOLLAND, 1975). Um aluno dele, Kenneth De Jong, escreveu em 1975 a tese que virou a bancada de testes da área (DE JONG, 1975); outro, David Goldberg, escreveu em 1989 o livro que popularizou tudo isso fora da academia (GOLDBERG, 1989). Em 1992, John Koza levou a ideia ao limite lógico: em vez de evoluir números, evoluir programas, representados como árvores de expressões — a programação genética (KOZA, 1992).

Quadro 1 — Vertentes clássicas da computação evolucionária, por origem e representação

Vertente	Origem	O que é o indivíduo	Operadores principais
Estratégias evolutivas	Berlim, anos 1960	Vetor de números reais (com parâmetros de mutação próprios)	Mutação gaussiana autoadaptativa; seleção (µ+λ) ou (µ,λ)
Programação evolutiva	Califórnia, 1966	Autômato de estados finitos	Mutação e seleção; sem recombinação
Algoritmos genéticos	Michigan, 1975	Cadeia de símbolos (classicamente, bits)	Seleção, cruzamento, mutação
Programação genética	Stanford, 1992	Árvore de expressão — um programa	Cruzamento de subárvores, mutação de nós

Fonte: elaborado pelo autor com base em Beyer e Schwefel (2002), Fogel, Owens e Walsh (1966), Holland (1975) e Koza (1992).Nota: as fronteiras entre as vertentes se dissolveram a partir dos anos 1990; hoje é comum um único algoritmo combinar elementos de todas.

Geração 03

Codificação: virar o problema do avesso

Antes de evoluir qualquer coisa, é preciso decidir o que conta como "indivíduo". Ilustração do autor (2026)

A primeira decisão de um algoritmo genético não é técnica, é de tradução: como transformar uma solução candidata numa estrutura que possa ser cortada, colada e bagunçada? Essa estrutura é o cromossomo (ou genótipo); a solução real que ela descreve é o fenótipo. Na mochila de vinte objetos, o cromossomo natural é uma fita de vinte bits: 1 se o objeto entra, 0 se fica.

A escolha da codificação parece burocrática e é, na prática, a decisão que mais afeta o resultado. Um cromossomo bem escolhido faz com que soluções parecidas no papel sejam parecidas também na fita — e isso é o que permite ao cruzamento juntar pedaços bons de pais diferentes em vez de gerar monstros. Um cromossomo mal escolhido transforma o algoritmo genético numa busca aleatória cara.

1

Binária. Fita de 0 e 1. Clássica, simples, e o alvo da teoria de esquemas de Holland. Problema conhecido: em números inteiros codificados em binário puro, vizinhos podem estar longe na fita (7 = 0111 e 8 = 1000 diferem em todos os bits) — daí o uso frequente do código de Gray.

2

Real. Vetor de números de ponto flutuante, um por variável contínua. É o padrão em engenharia e o terreno natural das estratégias evolutivas. O cruzamento deixa de ser corte-e-cola e vira média ponderada ou sorteio dentro de um intervalo.

3

Permutação. Uma ordem: a sequência de cidades de uma rota, a ordem das tarefas numa máquina. Aqui o corte-e-cola comum quebra tudo — gera rotas com cidades repetidas —, e é preciso usar operadores especializados como o PMX ou o order crossover.

4

Árvore. Uma expressão, uma fórmula, um programa. É a codificação da programação genética, em que o cruzamento troca subárvores inteiras entre dois pais (KOZA, 1992).

Há ainda uma decisão silenciosa embutida: o que fazer com candidatos inviáveis. Uma fita de bits pode descrever uma mochila de 80 quilos, o que é fisicamente impossível. As três saídas usuais são penalizar (a aptidão cai, mas o indivíduo continua na população e pode contribuir com bons pedaços), reparar (remover objetos até caber) ou proibir (descartar e sortear de novo). Nos laboratórios deste post, usamos a penalização mais dura possível — aptidão zero — porque ela é fácil de ver acontecendo.

Geração 04

População e aptidão: uma multidão e um juiz

Um algoritmo genético não trabalha com uma solução: trabalha com uma população delas, tipicamente entre 30 e algumas centenas de indivíduos, gerada ao acaso no início. Trabalhar em paralelo tem duas virtudes. Primeiro, a busca ataca várias regiões do espaço ao mesmo tempo, o que reduz a chance de todo o esforço morrer no mesmo vale ruim. Segundo — e é o que distingue os algoritmos genéticos dos métodos de solução única —, a população é uma memória distribuída: pedaços de solução testados e aprovados ficam guardados em indivíduos diferentes e podem ser recombinados depois.

O juiz é a função de aptidão (fitness): um programa que recebe um cromossomo e devolve um número, quanto maior melhor. É o único ponto de contato entre o algoritmo genérico e o seu problema específico. Na antena da NASA, a função de aptidão era um simulador eletromagnético completo. Na mochila, são duas somas.

Três avisos práticos sobre a função de aptidão, aprendidos no susto por praticamente todo mundo que trabalha com isso:

!

Ela domina o custo. Um algoritmo genético com população 100 e 500 gerações faz 50 mil avaliações. Se cada avaliação é uma simulação de trinta segundos, são dezessete dias de máquina. Praticamente todo o esforço de engenharia em otimização evolutiva vai para tornar a função de aptidão barata, não para ajustar o algoritmo.

!

Ela é interpretada ao pé da letra. O algoritmo maximiza exatamente o que você escreveu, incluindo os atalhos que você não previu. Se a nota premia "cobertura de sinal" sem penalizar consumo, você recebe uma antena que consome absurdamente. A literatura chama isso de reward hacking, e é o mesmo fenômeno que assombra o aprendizado por reforço.

!

Ela pode ter mais de um objetivo. Custo e resistência, tempo e preço. Nesse caso não existe um único ótimo, e sim uma fronteira de Pareto de soluções em que melhorar um objetivo exige piorar outro. O algoritmo padrão para isso é o NSGA-II, que ordena a população em camadas de não dominância e usa uma medida de aglomeração para espalhar as soluções pela fronteira (DEB et al., 2002).

Geração 05

Seleção: quem vira pai

Duas formas de premiar o bom sem eliminar o diferente. Ilustração do autor (2026)

Selecionar é decidir quem tem direito a descendentes. O parâmetro que importa se chama pressão seletiva: o quanto ser bom aumenta a chance de reproduzir. Pressão alta acelera a convergência e mata a diversidade; pressão baixa preserva a diversidade e não sai do lugar.

A

Roleta (proporcional à aptidão). Cada indivíduo ocupa uma fatia de disco proporcional à sua nota; gira-se o disco. É a proposta original de Holland e a mais intuitiva. Tem dois defeitos sérios: um indivíduo excepcional no início domina o disco e a população inteira vira cópia dele; e, quando todas as notas ficam parecidas no fim, as fatias se igualam e a seleção vira sorteio puro. Além disso, ela não funciona com aptidões negativas nem com problemas de minimização sem transformação prévia.

B

Torneio. Sorteiam-se k indivíduos ao acaso e o melhor deles vence. É o método mais usado hoje: não se importa com a escala das notas (só com a ordem), é trivial de implementar e tem um botão de pressão seletiva embutido — k = 2 é suave, k = 7 é brutal.

C

Ranqueamento. Ordena-se a população e distribui-se a chance segundo a posição, não a nota. Imune a superindivíduos e a diferenças de escala; custa uma ordenação por geração.

Uma nota sobre vocabulário: seleção não é o mesmo que "descarte dos piores". Nos esquemas clássicos, os piores continuam podendo ser sorteados — com probabilidade baixa. Isso é proposital. Um indivíduo medíocre pode carregar o único pedaço de cromossomo que resolverá o problema daqui a quarenta gerações, e matá-lo cedo demais é uma forma silenciosa de convergência prematura.

Geração 06

Cruzamento e mutação: os dois motores

Cruzamento recombina o que já existe; mutação inventa o que não existe em ninguém. Ilustração do autor (2026)

O cruzamento (crossover) pega dois pais e produz filhos que misturam trechos de ambos. Na versão de um ponto, sorteia-se uma posição de corte e trocam-se as caudas. Na de dois pontos, troca-se o miolo. No cruzamento uniforme, cada gene é sorteado independentemente de um dos pais — o que destrói a noção de "trecho contíguo" e é mais disruptivo.

A intuição por trás do cruzamento é a hipótese dos blocos construtivos: soluções boas contêm subestruturas boas — trechos curtos de cromossomo que já são vantajosos por si — e o cruzamento junta blocos de pais diferentes numa cria melhor que os dois (GOLDBERG, 1989). É uma hipótese sedutora, ligada ao teorema dos esquemas de Holland, e vale registrar que ela nunca ganhou uma formulação matemática rigorosa nem se sustenta em todos os problemas. Taxas usuais de cruzamento ficam entre 0,6 e 0,95.

A mutação altera genes ao acaso: inverte um bit, soma um ruído gaussiano a um número real, troca duas posições de uma permutação. Sua função não é melhorar o indivíduo — quase sempre ele piora — e sim garantir que nenhum valor de gene desapareça para sempre da população. Se todos os indivíduos têm 0 na posição 7, nenhum cruzamento no mundo vai produzir um 1 ali; só a mutação recupera essa possibilidade.

A taxa clássica é 1/L, onde L é o comprimento do cromossomo — em média, um gene alterado por indivíduo. Taxas muito maiores dissolvem a informação acumulada e o algoritmo vira caminhada aleatória; taxas nulas travam a busca no material genético inicial. No laboratório da próxima seção você pode zerar a mutação e assistir à população inteira virar clone em poucas dezenas de gerações.

Quadro 2 — Operadores de cruzamento e mutação segundo a codificação adotada

Codificação	Cruzamento típico	Mutação típica	Cuidado principal
Binária	Um ponto, dois pontos, uniforme	Inversão de bit com probabilidade 1/L	Saltos artificiais entre inteiros vizinhos (usar código de Gray)
Real	Aritmético (média ponderada), BLX-α, SBX	Ruído gaussiano com desvio adaptativo	Filhos sempre no interior do envelope dos pais, se o operador for só média
Permutação	PMX, order crossover (OX), cycle crossover	Troca de duas posições, inversão de trecho	Corte-e-cola comum gera soluções inválidas
Árvore	Troca de subárvores entre os pais	Substituição de nó ou de subárvore	Crescimento descontrolado do tamanho (bloat)

Fonte: elaborado pelo autor com base em Goldberg (1989), Koza (1992) e Beyer e Schwefel (2002).Nota: os termos técnicos em inglês foram mantidos por serem a forma corrente na literatura brasileira da área; a tradução aproximada aparece entre parênteses na primeira ocorrência no texto.

Geração 07

Elitismo: o teorema que obriga a guardar o melhor

Aqui há um resultado bonito e pouco conhecido fora da área. Um algoritmo genético canônico — seleção proporcional, cruzamento e mutação, sem nenhuma proteção ao melhor indivíduo — pode perder a melhor solução que já encontrou. Basta que ela não seja sorteada, ou que seja sorteada e mutilada por uma mutação infeliz. E não se trata de azar raro: Günter Rudolph provou, modelando o algoritmo como uma cadeia de Markov finita e homogênea, que o algoritmo genético canônico nunca converge para o ótimo global, qualquer que seja a inicialização, o operador de cruzamento e a função objetivo (RUDOLPH, 1994).

"Prova-se, por meio de análise de cadeias de Markov finitas homogêneas, que um algoritmo genético canônico jamais convergirá para o ótimo global, independentemente da inicialização, do operador de cruzamento e da função objetivo. Mas variantes do algoritmo genético canônico que sempre mantêm a melhor solução na população, seja antes, seja depois da seleção, convergem para o ótimo global."

Günter Rudolph, IEEE Transactions on Neural Networks, 1994, na tradução do autor (RUDOLPH, 1994)

A correção é de uma linha de código: copie os e melhores indivíduos diretamente para a próxima geração, sem passar por seleção, cruzamento ou mutação. Isso é o elitismo, introduzido por De Jong em 1975 como o "modelo elitista R2" na tese em que ele comparou seis variantes de plano reprodutivo (DE JONG, 1975).

Duas ressalvas importantes, porque esse resultado costuma ser citado de forma exagerada. Primeira: "converge" aqui significa que a melhor solução já encontrada tende ao ótimo global quando o número de gerações tende ao infinito — o que é uma garantia assintótica, não uma promessa sobre o seu prazo de entrega. Segunda: elitismo demais estraga. Guardar metade da população como elite equivale a aumentar violentamente a pressão seletiva, e a busca convergirá rápido para algum lugar medíocre. A prática usual é preservar de um a dois indivíduos, ou algo entre 1% e 5% da população.

Geração 08

Parada: quando desligar

Como o algoritmo nunca prova que chegou ao ótimo, quem decide o fim é você. Os critérios usuais, quase sempre combinados por um "ou":

1

Orçamento. Um número máximo de gerações ou, melhor, de avaliações da função de aptidão — a unidade de custo que realmente conta e a única que permite comparar métodos diferentes de forma honesta.

2

Estagnação. Nenhuma melhora no melhor indivíduo por n gerações seguidas. Na evolução da antena da NASA, por exemplo, o critério registrado combinava as duas coisas: parar em 100 gerações, ou quando o melhor escore ficasse estagnado por 40 gerações, ou quando o escore médio ficasse estagnado por 10 (LOHN et al., 2003).

3

Alvo atingido. Quando existe uma nota que já basta — "erro abaixo de 1%", "atende a todos os requisitos da missão". É o critério mais saudável quando o problema tem um patamar de suficiência conhecido.

4

Perda de diversidade. Quando a população vira um bloco de clones, continuar é gastar processador para nada. Mede-se pela distância média entre indivíduos ou pela variância das aptidões.

Geração 09

Laboratório 1: monte o algoritmo genético e sabote-o

Chega de definição. Abaixo roda um algoritmo genético de verdade, no seu navegador, sobre o problema da mochila: 20 objetos, capacidade de 50 quilos, população de 24 indivíduos. Cada linha do painel esquerdo é um cromossomo; cada quadradinho, um gene (verde = objeto levado). A barra à direita de cada linha é a aptidão — verde para as mochilas válidas, um toco vermelho para as que estouraram os 50 quilos e por isso têm aptidão zero. A moldura dourada marca os indivíduos protegidos pelo elitismo, e as linhas aparecem sempre ordenadas da melhor para a pior.

O ótimo exato deste problema é R$ 255, calculado por programação dinâmica — então dá para saber, a cada instante, o quanto o algoritmo está errando. Use os chips para trocar um operador de cada vez e observe o que quebra: desligue o elitismo e veja o melhor indivíduo piorar entre gerações; zere a mutação e assista à população virar um bloco de clones; troque o torneio por seleção aleatória e acompanhe a linha da média deixar de subir.

Seleção

Cruzamento

Mutação

Elitismo

População — 24 indivíduos × 20 genes

Convergência

geração0

melhor da população—

média—

diversidade—

avaliações gastas0

População inicial sorteada. Clique em evoluir.

Quatro experimentos que valem o clique. Um: deixe tudo no padrão e evolua até parar — nas seis populações iniciais que o botão de reiniciar percorre, o algoritmo chegou aos R$ 255 entre a geração 26 e a 119. Dois: reinicie com mutação zero; a diversidade despenca para 0% e a busca congela abaixo do ótimo, porque não há mais material genético novo para o cruzamento embaralhar. Três: reinicie sem elitismo e observe a linha do "melhor" fazendo degraus para baixo — a prova visual do teorema de Rudolph. Quatro: troque o torneio pela seleção aleatória e compare as duas curvas: a linha do melhor ainda sobe, porque o elitismo guarda o recorde e a mutação continua sorteando, mas a linha da média fica rastejando lá embaixo (por volta de R$ 34, contra R$ 72 com torneio). Sem pressão seletiva não há população melhor — há apenas um sortudo protegido.

Geração 10

Enxame de partículas: sem pais, sem filhos, só vizinhança

Em 1995, o psicólogo social James Kennedy e o engenheiro Russell Eberhart estavam simulando bandos de pássaros. O ponto de partida eram os boids de Craig Reynolds, um modelo de 1987 em que o voo coordenado de um bando emerge de três regras locais aplicadas por cada indivíduo, sem maestro (REYNOLDS, 1987). Kennedy e Eberhart acrescentaram um poleiro atraente à simulação e perceberam que, se o "poleiro" fosse o mínimo de uma função, o bando resolvia um problema de otimização (KENNEDY; EBERHART, 1995).

A otimização por enxame de partículas (PSO, de particle swarm optimization) não tem cromossomo, nem cruzamento, nem morte. Cada partícula é uma solução candidata que voa pelo espaço guardando duas lembranças: o melhor lugar onde ela já esteve e o melhor lugar onde o enxame já esteve. A cada instante ela corrige a velocidade puxando um pouco para cada uma dessas memórias.

v ← w·v + c₁·r₁·(p − x)  +  c₂·r₂·(g − x)
inércia  ·  componente cognitivo  ·  componente social

x ← x + v

Nessas duas linhas mora tudo. O termo de inércia (w) é a teimosia: quanto da direção anterior a partícula mantém. O componente cognitivo (c₁) é a memória individual — "volte para onde você já se deu bem". O componente social (c₂) é a fofoca — "vá para onde o pessoal se deu bem". Os fatores r₁ e r₂ são números aleatórios entre 0 e 1, sorteados a cada passo, e são a única fonte de ruído do método.

O peso de inércia não estava na formulação original: foi acrescentado por Yuhui Shi e Eberhart em 1998, justamente para regular a balança entre exploração e aproveitamento — w alto no início, para o enxame varrer o espaço, e w baixo no fim, para ele assentar (SHI; EBERHART, 1998). A configuração que virou padrão de fato na literatura usa o coeficiente de constrição de Clerc e Kennedy, com χ ≈ 0,72984 e c₁ = c₂ = 2,05, e enxames de cerca de 50 partículas (BRATTON; KENNEDY, 2007).

Inércia w

Personalidade

Enxame

Paisagem de Rastrigin — claro é fundo, escuro é topo

✕ marca o mínimo global · clique no mapa para reposicionar o enxame

iteração0

melhor f encontrado—

dispersão do enxame—

avaliações gastas0

A função de Rastrigin tem um mínimo global em (0, 0), onde vale 0, e uma grade de mínimos locais quase tão bons ao redor. É a armadilha clássica para métodos que descem depressa demais.

Enxame sorteado. Clique em voar.

Vale brincar com as personalidades. Em só cognitiva (c₂ = 0), cada partícula vira um eremita: busca sozinha, o enxame nunca se junta e o resultado final é apenas o melhor de trinta buscas independentes e ruins. Em só social (c₁ = 0), o oposto: todo mundo desaba sobre o primeiro ponto razoável que alguém encontrar, e o enxame colapsa em poucas iterações — convergência prematura em estado puro. Com inércia 0,95, o enxame ganha tanta teimosia que fica orbitando o alvo sem conseguir pousar.

Geração 11

Colônia de formigas: a memória fica no chão

A escolha do caminho curto não é decisão de ninguém: é consequência de todos. Ilustração do autor (2026)

Em 1989, quatro pesquisadores da Universidade Livre de Bruxelas montaram um experimento de uma simplicidade cruel. Ligaram um ninho de formigas argentinas (Iridomyrmex humilis, hoje Linepithema humile) a uma fonte de alimento por uma ponte com dois ramos de comprimentos diferentes. Depois, contaram o tráfego (GOSS et al., 1989).

Quando os ramos tinham o mesmo comprimento, não houve preferência significativa. Quando o ramo longo era o dobro do curto, em 11 de 14 experimentos mais de 80% do tráfego total passou a usar o ramo curto — e em todos os 14 houve seleção significativa do ramo curto. O detalhe crucial é como: nenhuma formiga mede os dois ramos e compara. Cada uma deposita feromônio ao andar e tende a seguir onde há mais feromônio. Como as que pegam o ramo curto voltam antes, reforçam o ramo curto mais cedo, o que atrai mais formigas, que reforçam mais. Os próprios autores chamam isso de "um processo coletivo e auto-organizado".

Marco Dorigo transformou esse mecanismo em algoritmo na tese de doutorado que defendeu no Politécnico de Milão em 1992 (DORIGO, 1992), formalizado quatro anos depois como Ant System (DORIGO; MANIEZZO; COLORNI, 1996). A diferença estrutural em relação ao algoritmo genético e ao enxame é que a colônia não guarda soluções: guarda um viés de construção. A memória do algoritmo está numa matriz de feromônio, uma por par de cidades, e cada formiga constrói uma rota do zero a cada iteração, escolhendo o próximo destino com probabilidade proporcional a

p_ij ∝ τ_ij^α · η_ij^β     com   η_ij = 1 / d_ij
τ = feromônio (o que a colônia aprendeu)  ·  η = visibilidade (o que a geometria diz)

Depois de todas construírem, o feromônio evapora — τ ← (1 − ρ)·τ — e cada formiga deposita uma quantidade inversamente proporcional ao comprimento da rota que fez. A evaporação é o operador de esquecimento: sem ela, os primeiros acertos aleatórios se cristalizam e a colônia nunca mais muda de ideia.

Evaporação ρ

Peso do feromônio α

Visibilidade β

22 cidades — a espessura da linha é o feromônio

iteração0

melhor rota—

rota da rodada—

vizinho mais próximo—

Com α = 0 a colônia ignora o feromônio e vira uma heurística gulosa aleatorizada — sem aprendizado. Com β = 0 ela ignora a geometria e precisa descobrir tudo do zero, o que é lento mas funciona. É a diferença entre memória e intuição.

Mapa sorteado, feromônio uniforme. Clique em soltar formigas.

O experimento mais eloquente aqui é desligar β. Com β = 0 a formiga perde a visibilidade — não enxerga qual cidade está perto — e passa a decidir só pelo feromônio: as rotas encontradas ficam de 1,7 a 2,5 vezes mais longas que as do padrão nos quatro mapas que testamos. Já com α = 0 ela perde o feromônio e mantém a visibilidade: vira uma heurística gulosa aleatorizada, que produz rotas só 5% a 10% piores, mas não melhora com o tempo, porque não há memória a acumular. A intuição carrega a maior parte do resultado; a memória é o que transforma tentativa em aprendizado.

Um resultado negativo também merece registro: mexer na taxa de evaporação, neste mapa de 22 cidades, quase não muda o resultado final. Isso não desmente a teoria — a evaporação é o que impede a cristalização em problemas grandes e em execuções longas —, mas mostra que problemas pequenos são péssimos juízes de parâmetros. É por isso que ajustes calibrados num brinquedo de bancada tantas vezes desmoronam na instância real.

Geração 12

A corrida: mesmo problema, mesmo orçamento

Comparações entre metaheurísticas são um pântano metodológico. Quase toda tabela de artigo compara um método cuidadosamente ajustado pelos autores com versões desleixadas dos concorrentes, e o critério de parada raramente é o mesmo. A regra mínima de honestidade é fixar o orçamento de avaliações da função de aptidão — não o tempo de relógio, não o número de gerações, que significam coisas diferentes em cada método.

Abaixo, três buscas disputam o mesmo problema contínuo com exatamente as mesmas 4.500 avaliações: busca aleatória pura, algoritmo genético com codificação real e enxame de partículas. Clique em correr algumas vezes e depois em "dez corridas": o placar acumulado conta uma história bem diferente da que uma única figura de convergência contaria. Uma corrida só não prova nada — é preciso repetir e olhar a distribuição, que é justamente o que boa parte dos artigos da área não faz.

Paisagem

Dimensões

Melhor valor encontrado (escala logarítmica) × avaliações

busca aleatória—

algoritmo genético—

enxame de partículas—

corridas acumuladas0

vitórias AG × enxame0 × 0

A colônia de formigas não entra nesta corrida — ela constrói soluções discretas passo a passo e não sabe o que fazer com um vetor de números reais. Comparar os três no mesmo gráfico seria inscrever um nadador numa prova de ciclismo.

Escolha a paisagem e a dimensão e clique em correr.

O resultado é instrutivo justamente porque não há um vencedor. Na esfera — uma tigela lisa, sem mínimos locais — e na Rosenbrock, o enxame ganha com folga: nada atrapalha uma descida direta, e a memória de velocidade paga. Na Rastrigin em 2 dimensões os dois chegam ao fundo e a diferença é decimal. Mas na Rastrigin em 10 e em 30 dimensões, o placar vira: nas trinta corridas que rodamos em cada configuração, o algoritmo genético venceu 26 e 29 vezes. É o padrão que a literatura descreve há décadas — o enxame desce depressa, o genético mantém diversidade por mais tempo, e qual dos dois é melhor depende inteiramente da paisagem.

Repare também na curva cinza. A busca aleatória pura, com o mesmo orçamento, fica ordens de grandeza atrás — mas não fica parada. Sempre que alguém apresentar um algoritmo novo, essa é a primeira linha de base a exigir: ganhar da sorte é o mínimo, não o mérito. E aumente para 30 dimensões para ver os três piorarem ao mesmo tempo: é a maldição da dimensionalidade, que nenhuma metáfora biológica revoga.

Geração 13

Onde isso realmente é usado

A pergunta certa não é "metaheurística funciona?", e sim "em que tipo de problema ela ganha de alternativas mais simples?". A resposta empírica, depois de cinco décadas, é razoavelmente clara: ela ganha quando o espaço de busca é grande e sem estrutura explorável, quando a função objetivo é uma caixa-preta cara (uma simulação, um ensaio), quando não há derivadas disponíveis e quando uma solução muito boa já resolve o problema de negócio — não sendo necessário provar otimalidade.

Antenas que ninguém desenhou

Voltemos à ST5. A equipe de Ames rodou dois algoritmos evolutivos com representações e funções de aptidão diferentes. Na primeira rodada, documentada em 2003, uma das versões usava população de 200 indivíduos com taxa de mutação de 50%, e a outra, população de 50 com 50% de sobrevivência entre gerações e mutação de 1% (LOHN et al., 2003). Quando os requisitos de órbita mudaram durante a qualificação de voo, bastou ajustar a função de aptidão: em um mês havia um novo projeto pronto e prototipado — a flexibilidade que a evolução automatizada oferece e um desenho manual não (HORNBY; LOHN; LINDEN, 2011).

Gráfico 1 — Eficiência do sistema de antenas da missão ST5, por configuração — 2006

2 convencionais38%

1 convencional + 1 evoluída80%

2 evoluídas93%

Fonte: elaborado pelo autor com base em Hornby et al. (2006).Nota: "convencional" refere-se à antena helicoidal quadrifilar (QHA) projetada pelo fornecedor. Os percentuais são de eficiência do sistema de antenas medida em ensaio.Nota: a antena evoluída exigiu cerca de três pessoas-mês entre projeto e fabricação, contra aproximadamente cinco meses da convencional, segundo a mesma fonte.

Moléculas, redes e chão de fábrica

O encaixe molecular (docking) é um dos usos silenciosos mais massivos: o AutoDock, um dos programas mais utilizados do mundo para prever como uma molécula candidata se acomoda no sítio ativo de uma proteína, tem como núcleo um algoritmo genético "lamarckiano" — evolução com busca local, em que a melhora encontrada pelo indivíduo é escrita de volta no seu genótipo (MORRIS et al., 1998). O nome é uma piada interna com a teoria da herança de caracteres adquiridos: biologicamente falsa, computacionalmente muito útil.

Em redes de telecomunicações, o AntNet aplicou o princípio da colônia ao roteamento adaptativo: pacotes-formiga percorrem a rede e atualizam tabelas de roteamento probabilísticas, e o método superou seis algoritmos concorrentes em todas as condições experimentais testadas (DI CARO; DORIGO, 1998).

No escalonamento de produção, é instrutivo olhar os números sem filtro. Aplicado ao clássico problema de job shop, o Ant System resolve a instância MT06 (6 × 6) no valor ótimo conhecido, mas na MT10 (10 × 10) chega a 1.059 contra um ótimo de 930 — quase 14% acima (COLORNI et al., 1994). É um resultado honesto e revelador: a metaheurística entrega uma boa resposta rápida, não a melhor resposta, e em problemas industriais essa diferença de 14% pode ser irrelevante ou fatal, dependendo do que está em jogo.

Tabela 1 — Desempenho do Ant System em instâncias clássicas de job shop scheduling

Instância	Dimensão	Melhor conhecido	Ant System	Diferença (%)
MT06	6 × 6	55	55	0,0
MT10	10 × 10	930	1 059	13,9
ORB4	10 × 10	1 005	1 077	7,2

Fonte: elaborado pelo autor com base em Colorni et al. (1994).Nota: valores de makespan (tempo total de conclusão), quanto menor melhor. Parâmetros do experimento original: α = 1, β = 1, ρ = 0,7, número de formigas igual ao número de tarefas, 3.000 iterações.Nota: a fonte registra que o Ant System atinge o melhor valor conhecido na instância MT06 sem informar o número; adotou-se 55, valor consolidado na literatura para essa instância. A coluna de diferença percentual foi calculada pelo autor.

E no Brasil?

Há literatura brasileira sólida na área. Um exemplo com números publicados vem do grupo de energia da Universidade de São Paulo: aplicando algoritmos genéticos e variantes à reconfiguração de redes de distribuição de energia, os autores relatam, num caso de rede real, redução de perdas superior a 70% em relação à configuração então existente, com as variantes do algoritmo obtendo mais de 27% de ganho adicional sobre o algoritmo genético básico (BENTO; KAGAN, 2008).

Vale, porém, um alerta contra uma confusão comum em sala de aula. O planejamento da operação do sistema elétrico brasileiro — os modelos NEWAVE e DECOMP, que definem o despacho hidrotérmico e alimentam a formação do preço de curto prazo — não usa metaheurísticas bioinspiradas. Usa programação dinâmica dual estocástica, um método exato de decomposição, conforme os manuais de referência do próprio CEPEL (CEPEL, 2021). É o exemplo perfeito da regra da Geração 01: quando existe estrutura matemática explorável e a decisão vale bilhões, usa-se o método que oferece garantias.

Em termos de difusão, o pano de fundo mudou depressa: segundo a Pesquisa de Inovação Semestral do IBGE, o percentual de empresas industriais brasileiras com 100 ou mais pessoas ocupadas que usavam inteligência artificial saltou de 16,9% em 2022 para 41,9% em 2024 (IBGE, 2025). Otimização é a camada menos visível e provavelmente a mais lucrativa desse pacote.

Geração 14

O teorema que estraga a festa

Em 1997, David Wolpert e William Macready publicaram um resultado com nome de piada e consequências sérias: os teoremas do almoço grátis (no free lunch). O enunciado central é que, somando o desempenho sobre todas as funções objetivo possíveis, quaisquer dois algoritmos de busca empatam (WOLPERT; MACREADY, 1997). Qualquer vantagem que um método tenha numa classe de problemas é exatamente compensada por uma desvantagem em outra.

"Apresenta-se um conjunto de teoremas do 'almoço grátis' (NFL) que estabelecem que, para qualquer algoritmo, todo ganho de desempenho sobre uma classe de problemas é compensado pelo desempenho sobre outra classe."

Wolpert e Macready, IEEE Transactions on Evolutionary Computation, 1997, na tradução do autor (WOLPERT; MACREADY, 1997)

O teorema é frequentemente mal usado nas duas direções. Não significa que todo algoritmo é igualmente bom nos problemas reais — a média é sobre um universo de funções em que quase tudo é ruído puro, e problemas do mundo têm estrutura. Mas também não autoriza o argumento preguiçoso de que "como a distribuição real não é uniforme, o meu método é melhor": o próprio Wolpert observou depois que apenas supor uma distribuição não uniforme não estabelece absolutamente nada sobre qual algoritmo usar. A pergunta correta não é qual metaheurística é a melhor, e sim qual estrutura o seu problema tem e qual método a explora.

Os quatro pecados da área

1

A epidemia das metáforas. Nas últimas duas décadas foram publicados algoritmos inspirados em lobos, morcegos, vaga-lumes, baleias, casamentos, fogos de artifício e temperos culinários. Boa parte é, sob a metáfora, uma variação já conhecida de enxame ou de estratégia evolutiva com nomes novos para os mesmos termos. A metáfora não é evidência; a comparação controlada é.

2

Comparação desleal. Método próprio ajustado com carinho contra concorrentes com parâmetros padrão, critérios de parada diferentes, uma única execução por instância e nenhum teste estatístico. O mínimo aceitável são 30 execuções independentes, orçamento igual de avaliações e um teste não paramétrico.

3

Parâmetros de graça. Um algoritmo genético tem, no mínimo, cinco decisões livres — tamanho de população, taxa de cruzamento, taxa de mutação, tipo e pressão de seleção, elitismo. Ajustar isso custa execuções, e esse custo raramente entra na conta apresentada.

4

Ignorar o híbrido. Na prática industrial, quase nunca vence a metaheurística pura: vence o híbrido — evolução para explorar o espaço em grande escala, busca local para lapidar cada solução. É o caso do algoritmo lamarckiano do AutoDock. Nos nossos testes com as capitais brasileiras, adiante, a rota da colônia de formigas já era ótima local para a busca 2-opt — sinal de que os dois mecanismos convergiram para o mesmo ponto.

Geração 15

A evolução volta pela porta dos fundos

Havia uma sensação, em meados dos anos 2010, de que a computação evolucionária tinha virado assunto de nicho, atropelada pelas redes neurais profundas. O que aconteceu foi mais interessante: os dois se juntaram.

Em dezembro de 2023 o DeepMind publicou o FunSearch, um procedimento evolutivo em que os "indivíduos" são programas escritos por um modelo de linguagem e a "seleção" é um avaliador automático que executa cada programa e o pontua. O sistema encontrou um conjunto cap de tamanho 512 em dimensão 8, superando construções conhecidas, e heurísticas para empacotamento em bins melhores que as regras clássicas (ROMERA-PAREDES et al., 2024). Em maio de 2025 veio o AlphaEvolve, a versão industrial da mesma ideia: uma heurística de escalonamento descoberta por ele recupera continuamente, em média, 0,7% da capacidade computacional mundial do Google que de outro modo ficaria ociosa; um algoritmo evoluído multiplica matrizes complexas 4 × 4 com 48 multiplicações escalares, a primeira melhora em 56 anos sobre o método de Strassen nesse caso; e, num conjunto de mais de 50 problemas matemáticos em aberto, ele redescobriu o estado da arte em 75% dos casos e o superou em cerca de 20% (GOOGLE DEEPMIND, 2025).

O esqueleto é exatamente o que você montou no Laboratório 1: população, aptidão, seleção, variação, elitismo, parada. O que mudou foi o operador de mutação. Onde o algoritmo genético de 1975 invertia bits ao acaso, o AlphaEvolve pede a um modelo de linguagem que reescreva um trecho de código — uma mutação informada, que gera candidatos plausíveis em vez de candidatos aleatórios. Cinquenta anos depois, a estrutura de Holland continua de pé; o que ficou melhor foi a qualidade dos palpites.

Geração 16

Mão na massa: três programas prontos para o Colab

Os três programas abaixo foram executados pelo autor e as saídas reproduzidas são reais e completas. Todos rodam em segundos e não exigem instalação: cole num caderno do Google Colab e execute.

Tutorial 1 · Python puro Algoritmo genético do zero: o problema da mochila

Sem nenhuma biblioteca além da padrão. Estão aqui, em sequência e comentados, todos os componentes do post: codificação binária, população inicial aleatória, função de aptidão com penalização, seleção por torneio, cruzamento de um ponto, mutação a 1/L, elitismo e parada por número de gerações. No fim, o programa confere o resultado contra o ótimo exato calculado por programação dinâmica.

# Algoritmo genetico do zero: o problema da mochila 0-1
import random

random.seed(42)

# ---- 1. O PROBLEMA -------------------------------------------------
# 20 itens (valor em reais, peso em kg) e uma mochila de 50 kg.
ITENS = [(60, 10), (100, 20), (120, 30), (75, 15), (30, 8),
         (45, 12), (90, 25), (20, 5), (55, 14), (70, 18),
         (35, 9), (85, 22), (25, 6), (95, 26), (40, 11),
         (65, 16), (50, 13), (110, 28), (15, 4), (80, 21)]
CAPACIDADE = 50
N = len(ITENS)                 # tamanho do cromossomo

# ---- 2. CODIFICACAO E APTIDAO --------------------------------------
def aptidao(crom):
    """Cromossomo = lista de 0/1. Excesso de peso zera a aptidao."""
    valor = sum(ITENS[i][0] for i in range(N) if crom[i])
    peso  = sum(ITENS[i][1] for i in range(N) if crom[i])
    return 0 if peso > CAPACIDADE else valor

# ---- 3. OPERADORES -------------------------------------------------
def torneio(pop, apts, k=3):
    """Seleciona k individuos ao acaso e devolve o melhor deles."""
    disputantes = random.sample(range(len(pop)), k)
    campeao = max(disputantes, key=lambda i: apts[i])
    return pop[campeao][:]

def cruzamento(p1, p2, taxa=0.9):
    """Corte em um ponto."""
    if random.random() > taxa:
        return p1[:], p2[:]
    c = random.randint(1, N - 1)
    return p1[:c] + p2[c:], p2[:c] + p1[c:]

def mutacao(crom, taxa):
    """Inverte cada bit com probabilidade 'taxa' (padrao: 1/N)."""
    return [1 - g if random.random() < taxa else g for g in crom]

# ---- 4. O LOOP EVOLUTIVO -------------------------------------------
def ag(tam_pop=60, geracoes=80, elite=2, taxa_mut=1.0 / N):
    pop = [[random.randint(0, 1) for _ in range(N)] for _ in range(tam_pop)]
    historico = []
    for g in range(geracoes):
        apts = [aptidao(c) for c in pop]
        ordem = sorted(range(tam_pop), key=lambda i: apts[i], reverse=True)
        historico.append((g, apts[ordem[0]], sum(apts) / tam_pop))
        nova = [pop[i][:] for i in ordem[:elite]]        # ELITISMO
        while len(nova) < tam_pop:
            f1, f2 = cruzamento(torneio(pop, apts), torneio(pop, apts))
            nova.append(mutacao(f1, taxa_mut))
            if len(nova) < tam_pop:
                nova.append(mutacao(f2, taxa_mut))
        pop = nova
    apts = [aptidao(c) for c in pop]
    melhor = max(range(tam_pop), key=lambda i: apts[i])
    return pop[melhor], apts[melhor], historico

# ---- 5. RODANDO ----------------------------------------------------
crom, valor, hist = ag()
peso = sum(ITENS[i][1] for i in range(N) if crom[i])
print("cromossomo :", "".join(map(str, crom)))
print("valor      : R$", valor)
print("peso       :", peso, "kg de", CAPACIDADE)
print()
print("geracao | melhor | media")
for g, mel, med in hist[:5] + [("...", "...", "...")] + hist[-3:]:
    print("{:>7} | {:>6} | {:>6}".format(
        g, mel, round(med, 1) if isinstance(med, float) else med))

# ---- 6. CONFERINDO COM A RESPOSTA EXATA ----------------------------
# Programacao dinamica: da o otimo, mas so porque o problema e pequeno.
tab = [0] * (CAPACIDADE + 1)
for v, p in ITENS:
    for w in range(CAPACIDADE, p - 1, -1):
        tab[w] = max(tab[w], tab[w - p] + v)
print("\notimo exato (programacao dinamica): R$", tab[CAPACIDADE])

saída real da execução

cromossomo : 11010001000000000000
valor      : R$ 255
peso       : 50 kg de 50

geracao | melhor | media
      0 |    135 |    2.2
      1 |    195 |    7.8
      2 |    210 |   15.0
      3 |    210 |   28.2
      4 |    215 |   25.5
    ... |    ... |    ...
     77 |    255 |  111.4
     78 |    255 |   89.8
     79 |    255 |   89.6

otimo exato (programacao dinamica): R$ 255

Três coisas para reparar na saída. A mochila fecha em exatamente 50 quilos — a restrição está ativa, como quase sempre acontece. A média da população oscila para baixo no fim (111,4 → 89,6) enquanto o melhor fica parado em 255: é o efeito da mutação continuar produzindo inviáveis de aptidão zero, e é exatamente por isso que o elitismo precisa existir. E o algoritmo genético encontrou o ótimo exato — o que aqui é verificável porque o problema é minúsculo; num problema real, você nunca saberia.

Tutorial 2 · NumPy Enxame de partículas em vinte linhas

O PSO inteiro cabe num punhado de operações vetoriais. O problema é a função de Rastrigin em 10 dimensões, cheia de mínimos locais, e há uma comparação honesta no fim: busca aleatória pura com o mesmo orçamento de avaliações.

# Enxame de particulas (PSO) em NumPy
# Funcao de Rastrigin em 10 dimensoes: 1 minimo global (f=0) e milhares de locais.
import numpy as np

rng = np.random.default_rng(7)
D, N_PART, ITER = 10, 40, 300
LIM = 5.12
W, C1, C2 = 0.729, 1.49445, 1.49445   # constricao de Clerc & Kennedy

def rastrigin(X):
    return 10 * D + np.sum(X ** 2 - 10 * np.cos(2 * np.pi * X), axis=1)

# posicao, velocidade, melhor pessoal (p) e melhor global (g)
X = rng.uniform(-LIM, LIM, (N_PART, D))
V = rng.uniform(-1, 1, (N_PART, D))
P, fP = X.copy(), rastrigin(X)
g = int(np.argmin(fP)); G, fG = P[g].copy(), fP[g]

marcos = {}
for t in range(ITER):
    r1, r2 = rng.random((N_PART, D)), rng.random((N_PART, D))
    V = W * V + C1 * r1 * (P - X) + C2 * r2 * (G - X)
    V = np.clip(V, -LIM, LIM)
    X = np.clip(X + V, -LIM, LIM)
    f = rastrigin(X)
    melhorou = f < fP
    P[melhorou], fP[melhorou] = X[melhorou], f[melhorou]
    if fP.min() < fG:
        g = int(np.argmin(fP)); G, fG = P[g].copy(), fP[g]
    if t in (0, 9, 49, 99, 199, 299):
        marcos[t + 1] = (fG, float(np.mean(np.std(X, axis=0))))

print("iteracao |  melhor f  | dispersao do enxame")
for it, (v, s) in marcos.items():
    print("{:>8} | {:>10.4f} | {:.3f}".format(it, v, s))
print("\nmelhor posicao encontrada (5 primeiras coordenadas):")
print(np.round(G[:5], 4))
print("f(otimo global) = 0.0  em  x = (0, 0, ..., 0)")

# Comparacao honesta: busca aleatoria com o MESMO orcamento de avaliacoes
orcamento = N_PART * ITER
Y = rng.uniform(-LIM, LIM, (orcamento, D))
print("\nbusca aleatoria com {} avaliacoes: melhor f = {:.4f}".format(
    orcamento, float(rastrigin(Y).min())))
print("PSO      com {} avaliacoes: melhor f = {:.4f}".format(orcamento, float(fG)))

saída real da execução

iteracao |  melhor f  | dispersao do enxame
       1 |    91.2464 | 1.645
      10 |    56.4425 | 1.487
      50 |    32.6677 | 0.858
     100 |    11.7761 | 0.559
     200 |     3.9887 | 0.245
     300 |     3.9798 | 0.128

melhor posicao encontrada (5 primeiras coordenadas):
[-0.    -0.     0.     0.995  0.   ]
f(otimo global) = 0.0  em  x = (0, 0, ..., 0)

busca aleatoria com 12000 avaliacoes: melhor f = 74.6683
PSO      com 12000 avaliacoes: melhor f = 3.9798

Esta saída é mais interessante do que um sucesso limpo. O enxame chegou a 3,98 quando o ótimo é 0 — e a quarta coordenada parou em 0,995, não em zero. Na Rastrigin, cada coordenada travada em ±1 custa cerca de uma unidade: o enxame ficou preso num mínimo local a quatro coordenadas de distância do global, e a coluna de dispersão mostra o motivo — ela desabou de 1,645 para 0,128, ou seja, o enxame convergiu antes de terminar de procurar. Ainda assim, o PSO ficou dezenove vezes melhor que a busca aleatória com o mesmo orçamento. Ganhar da sorte é fácil; ganhar do ótimo, não.

Tutorial 3 · NumPy Colônia de formigas nas 27 capitais brasileiras

Aqui o Ant System resolve um caixeiro-viajante concreto: a menor rota fechada passando pelas 27 capitais do Brasil, com distâncias de grande círculo. A referência de comparação é a heurística do vizinho mais próximo, testada a partir de todas as 27 partidas possíveis.

# Colonia de formigas (Ant System) no caixeiro-viajante:
# a menor rota que passa pelas 27 capitais brasileiras e volta ao inicio.
import numpy as np

rng = np.random.default_rng(2026)

CAPITAIS = [
    ("Aracaju", -10.9472, -37.0731), ("Belem", -1.4558, -48.5039),
    ("Belo Horizonte", -19.9167, -43.9345), ("Boa Vista", 2.8235, -60.6758),
    ("Brasilia", -15.7939, -47.8828), ("Campo Grande", -20.4697, -54.6201),
    ("Cuiaba", -15.6014, -56.0979), ("Curitiba", -25.4284, -49.2733),
    ("Florianopolis", -27.5954, -48.5480), ("Fortaleza", -3.7319, -38.5267),
    ("Goiania", -16.6869, -49.2648), ("Joao Pessoa", -7.1195, -34.8450),
    ("Macapa", 0.0349, -51.0694), ("Maceio", -9.6498, -35.7089),
    ("Manaus", -3.1190, -60.0217), ("Natal", -5.7945, -35.2110),
    ("Palmas", -10.1849, -48.3336), ("Porto Alegre", -30.0346, -51.2177),
    ("Porto Velho", -8.7612, -63.9004), ("Recife", -8.0476, -34.8770),
    ("Rio Branco", -9.9754, -67.8249), ("Rio de Janeiro", -22.9068, -43.1729),
    ("Salvador", -12.9777, -38.5016), ("Sao Luis", -2.5297, -44.3028),
    ("Sao Paulo", -23.5505, -46.6333), ("Teresina", -5.0892, -42.8019),
    ("Vitoria", -20.3155, -40.3128),
]
NOMES = [c[0] for c in CAPITAIS]
n = len(CAPITAIS)

# ---- matriz de distancias (grande-circulo, em km) ------------------
lat = np.radians([c[1] for c in CAPITAIS])
lon = np.radians([c[2] for c in CAPITAIS])
dlat = lat[:, None] - lat[None, :]
dlon = lon[:, None] - lon[None, :]
a = np.sin(dlat / 2) ** 2 + np.cos(lat)[:, None] * np.cos(lat)[None, :] * np.sin(dlon / 2) ** 2
D = 6371.0 * 2 * np.arcsin(np.sqrt(a))
np.fill_diagonal(D, np.inf)

def custo(rota):
    return float(sum(D[rota[i], rota[(i + 1) % n]] for i in range(n)))

# ---- referencia: vizinho mais proximo ------------------------------
def vizinho_mais_proximo(inicio=0):
    rota, visitadas = [inicio], {inicio}
    while len(rota) < n:
        atual = rota[-1]
        prox = min((j for j in range(n) if j not in visitadas), key=lambda j: D[atual, j])
        rota.append(prox); visitadas.add(prox)
    return rota

# ---- Ant System (DORIGO; MANIEZZO; COLORNI, 1996) ------------------
ALFA, BETA, RHO, Q = 1.0, 3.0, 0.5, 1.0
N_FORMIGAS, N_ITER = 27, 200

eta = 1.0 / D                       # visibilidade: inverso da distancia
tau = np.ones((n, n))               # feromonio inicial uniforme
melhor_rota, melhor_custo = None, np.inf
historico = []

for it in range(N_ITER):
    rotas, custos = [], []
    for _ in range(N_FORMIGAS):
        inicio = int(rng.integers(n))
        rota, naovisit = [inicio], [j for j in range(n) if j != inicio]
        while naovisit:
            i = rota[-1]
            p = (tau[i, naovisit] ** ALFA) * (eta[i, naovisit] ** BETA)
            p = p / p.sum()
            escolha = naovisit[int(rng.choice(len(naovisit), p=p))]
            rota.append(escolha); naovisit.remove(escolha)
        rotas.append(rota); custos.append(custo(rota))
    k = int(np.argmin(custos))
    if custos[k] < melhor_custo:
        melhor_custo, melhor_rota = custos[k], rotas[k][:]
    tau *= (1 - RHO)                                   # evaporacao
    for rota, c in zip(rotas, custos):                 # deposito
        for i in range(n):
            u, v = rota[i], rota[(i + 1) % n]
            tau[u, v] += Q * 1000.0 / c
            tau[v, u] += Q * 1000.0 / c
    if it in (0, 9, 49, 99, 199):
        historico.append((it + 1, min(custos), melhor_custo))

vmp = min((vizinho_mais_proximo(i) for i in range(n)), key=custo)
print("vizinho mais proximo (melhor partida): {:>8.0f} km".format(custo(vmp)))
print()
print("iteracao | melhor da rodada | melhor ate agora")
for it, mr, ma in historico:
    print("{:>8} | {:>13.0f} km | {:>13.0f} km".format(it, mr, ma))
print()
print("Ant System                          : {:>8.0f} km".format(melhor_custo))
print("ganho sobre o vizinho mais proximo  : {:>8.1f} %".format(
    100 * (custo(vmp) - melhor_custo) / custo(vmp)))
print()
i0 = melhor_rota.index(0)
ordem = melhor_rota[i0:] + melhor_rota[:i0]
print("rota: " + " > ".join(NOMES[i] for i in ordem) + " > " + NOMES[ordem[0]])

saída real da execução

vizinho mais proximo (melhor partida):    14214 km

iteracao | melhor da rodada | melhor ate agora
       1 |         17406 km |         17406 km
      10 |         14074 km |         13971 km
      50 |         13961 km |         13801 km
     100 |         14243 km |         13801 km
     200 |         13961 km |         13801 km

Ant System                          :    13801 km
ganho sobre o vizinho mais proximo  :      2.9 %

rota: Aracaju > Salvador > Palmas > Brasilia > Goiania > Belo Horizonte >
Vitoria > Rio de Janeiro > Sao Paulo > Curitiba > Florianopolis >
Porto Alegre > Campo Grande > Cuiaba > Rio Branco > Porto Velho >
Manaus > Boa Vista > Macapa > Belem > Sao Luis > Teresina > Fortaleza >
Natal > Joao Pessoa > Recife > Maceio > Aracaju

A rota faz sentido geográfico: desce o litoral do Nordeste ao Sul, atravessa o Centro-Oeste até a Amazônia ocidental, sobe pelo Norte e fecha pelo litoral nordestino. O ganho sobre o vizinho mais próximo é de apenas 2,9% — o que é típico e importante de dizer: heurísticas simples já são muito boas, e a metaheurística disputa os últimos poucos por cento. Repare também na coluna "melhor da rodada": na iteração 100 ela piora para 14.243 km. A colônia não caminha monotonicamente para melhor; quem garante que nada se perde é o registro do melhor histórico — o elitismo, de novo, com outro nome.

Geração 17

Perguntas para o seu contexto

Marque o que já consegue explicar para um colega sem consultar o texto. Cada item corresponde a uma peça do algoritmo.

0 de 7

Sei escolher uma codificação para o meu problema e justificar por que soluções parecidas ficam parecidas no cromossomo. Consigo escrever a função de aptidão do meu problema e apontar o atalho que ela permitiria ao algoritmo. Sei a diferença entre roleta e torneio e sei qual usar quando as notas têm escalas muito diferentes. Sei dizer o que o cruzamento faz que a mutação não faz — e vice-versa. Consigo explicar por que, sem elitismo, o algoritmo pode perder a melhor solução que já encontrou. Sei comparar dois métodos de forma honesta, fixando o orçamento de avaliações e repetindo as execuções. Consigo dizer, para um problema concreto, se vale mais uma metaheurística ou um método exato.

Vale a transposição para a sala de aula, porque a estrutura é curiosamente familiar. Uma turma é uma população; uma avaliação é uma função de aptidão; e todo professor já viu o que acontece quando a nota premia exatamente aquilo que é fácil de medir — os alunos otimizam o critério, não o objetivo. Se a sua rubrica pode ser satisfeita sem que o aluno aprenda, ela será, e a culpa não é do aluno: é do desenho da função. O elitismo tem seu equivalente pedagógico na memória institucional — guardar o que funcionou, para não redescobrir tudo a cada semestre. E a diversidade tem o dela: uma turma inteira pensando igual converge rápido para uma resposta, e frequentemente para a errada.

Seleção final

Feio, funcional e sem explicação

Fica uma inquietação depois de olhar a antena da ST5 por tempo suficiente. Ela funciona melhor que o desenho humano e ninguém consegue contar a história de por quê — não há um princípio de engenharia por trás de cada dobra, há um histórico de seleção. É o mesmo tipo de opacidade que hoje discutimos a respeito das redes neurais, só que trinta anos mais velha e num pedaço de metal que dá para segurar na mão.

Talvez seja essa a lição mais durável da computação evolucionária, mais durável até que os algoritmos: a otimização não precisa de compreensão, mas a engenharia precisa de confiança — e confiança, quando não vem de entender, tem de vir de testar. A antena voou porque passou por qualificação de voo, não porque alguém entendeu suas dobras. Vale lembrar disso toda vez que alguém propuser colocar um sistema otimizado, e não compreendido, no lugar de uma decisão que afeta pessoas.

No próximo post da série a lente vira para os dados: se o algoritmo só otimiza o que a função de aptidão mede, e se a rede só aprende o que os exemplos mostram, então quem escolhe o critério e quem escolhe os exemplos decide o que a máquina vai fazer. Até lá, fica a pergunta: no seu trabalho, qual é a "função de aptidão" que já está sendo otimizada sem que ninguém a tenha escrito de propósito — e o que ela premia que você não gostaria de premiar?

Nota do autor: a expressão de Turing sobre a "busca genética ou evolucionária" não está no artigo de 1950 na Mind, como às vezes se lê, e sim no relatório Intelligent Machinery, escrito em 1948 no National Physical Laboratory e publicado apenas em 1969 em Machine Intelligence 5; a passagem da máquina-criança, essa sim, é do artigo de 1950 — as duas citações no texto refletem essa separação, e as traduções são do autor. Os parâmetros de população e mutação citados na Geração 13 (200 indivíduos com mutação de 50%; 50 indivíduos com mutação de 1%) referem-se à primeira rodada de evolução, documentada em 2003 para a antena ST5-3-10, e não à antena que efetivamente voou, a ST5-33-142-7, reevoluída depois da mudança de requisitos de órbita; as fontes da NASA consultadas não publicam os parâmetros dessa segunda rodada. Os percentuais de eficiência do Gráfico 1 são de ensaio do sistema de antenas e não devem ser lidos como eficiência de irradiação de uma antena isolada. Os valores da Tabela 1 são os publicados no experimento original de 1994 e não representam o estado da arte atual em job shop, hoje bem mais próximo do ótimo; a coluna de diferença percentual foi calculada pelo autor. Sobre o experimento das formigas: a formulação popular de que "praticamente todas as formigas passam a usar o caminho curto" é mais forte do que o resultado publicado — em 11 de 14 experimentos com razão 2 entre os ramos, mais de 80% do tráfego usou o ramo curto, e em 14 de 14 houve seleção significativa; a espécie é grafada Iridomyrmex humilis no artigo de 1989, sendo Linepithema humile a designação atual. A hipótese dos blocos construtivos é apresentada como hipótese, e não como resultado, porque nunca recebeu formulação matemática rigorosa nem se sustenta em todas as classes de problema. O resultado de convergência de Rudolph (1994) vale para otimização estática e é assintótico: garante que a melhor solução já encontrada tende ao ótimo global, não que isso ocorra em tempo útil. As coordenadas das capitais usadas no Tutorial 3 são aproximadas, referentes às sedes municipais, e as distâncias são de grande círculo — não de estrada; o valor de 13.801 km foi confirmado pelo autor como ótimo local para a busca 2-opt e reencontrado como melhor resultado em 3.000 reinícios aleatórios de 2-opt, mas não há aqui prova de otimalidade global. Os três programas em Python foram executados pelo autor com as sementes indicadas e as saídas reproduzidas são reais e completas, sem cortes; alterar a semente altera os números. Os laboratórios interativos desta página usam gerador pseudoaleatório próprio para que o botão de reiniciar percorra sempre a mesma sequência de cenários — não são reproduções dos programas em Python, e sim implementações independentes em JavaScript, com populações e orçamentos menores para caber no navegador. Sobre o setor elétrico brasileiro: a afirmação de que NEWAVE e DECOMP não empregam metaheurísticas bioinspiradas baseia-se na leitura dos manuais de referência do CEPEL, que descrevem programação dinâmica dual estocástica como método de solução. Por fim, não foram localizados documentos primários que atestem uso operacional de algoritmos genéticos, enxame de partículas ou colônia de formigas em produção na Petrobras ou na Embraer, ainda que exista literatura acadêmica brasileira sobre esses domínios — por isso o post não faz essa afirmação.

Referências

1. BENTO, Eduardo Pereira; KAGAN, Nelson. Algoritmos genéticos e variantes na solução de problemas de configuração de redes de distribuição. Sba: Controle & Automação Sociedade Brasileira de Automática, Campinas, v. 19, n. 3, p. 302-315, 2008. DOI: 10.1590/S0103-17592008000300006. Disponível em: https://www.scielo.br/j/ca/a/CJc9Y4GpQjMfpXpb7yFvpSH/. Acesso em: 19 ago. 2026.
2. BEYER, Hans-Georg; SCHWEFEL, Hans-Paul. Evolution strategies: a comprehensive introduction. Natural Computing, v. 1, n. 1, p. 3-52, 2002. DOI: 10.1023/A:1015059928466. Disponível em: https://doi.org/10.1023/A:1015059928466. Acesso em: 19 ago. 2026.
3. BRATTON, Daniel; KENNEDY, James. Defining a standard for particle swarm optimization. In: IEEE SWARM INTELLIGENCE SYMPOSIUM, 2007, Honolulu. Proceedings of the 2007 IEEE Swarm Intelligence Symposium. Piscataway: IEEE, 2007. p. 120-127. DOI: 10.1109/SIS.2007.368035.
4. CENTRO DE PESQUISAS DE ENERGIA ELÉTRICA (CEPEL). Manual de referência: modelo DECOMP. Versão 31. Rio de Janeiro: Eletrobras/Cepel, out. 2021. Disponível em: https://www.cepel.br/wp-content/uploads/2022/05/DECOMP_ManualReferencia_Out2021.pdf. Acesso em: 19 ago. 2026.
5. COLORNI, Alberto; DORIGO, Marco; MANIEZZO, Vittorio; TRUBIAN, Marco. Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science, v. 34, n. 1, p. 39-53, 1994. Disponível em: https://www.orbel.be/jorbel/index.php/jorbel/article/download/169/125/244. Acesso em: 19 ago. 2026.
6. DEB, Kalyanmoy; PRATAP, Amrit; AGARWAL, Sameer; MEYARIVAN, T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, v. 6, n. 2, p. 182-197, abr. 2002. DOI: 10.1109/4235.996017. Disponível em: https://doi.org/10.1109/4235.996017. Acesso em: 19 ago. 2026.
7. DE JONG, Kenneth Alan. An analysis of the behavior of a class of genetic adaptive systems. 1975. Tese (Doutorado em Computer and Communication Sciences) — University of Michigan, Ann Arbor, 1975. Disponível em: https://deepblue.lib.umich.edu/handle/2027.42/4507. Acesso em: 19 ago. 2026.
8. DI CARO, Gianni; DORIGO, Marco. AntNet: distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research, v. 9, p. 317-365, 1998. DOI: 10.1613/jair.530. Disponível em: https://doi.org/10.1613/jair.530. Acesso em: 19 ago. 2026.
9. DORIGO, Marco. Optimization, learning and natural algorithms. 1992. Tese (Doutorado) — Dipartimento di Elettronica, Politecnico di Milano, Milão, 1992. [Em italiano].
10. DORIGO, Marco; MANIEZZO, Vittorio; COLORNI, Alberto. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), v. 26, n. 1, p. 29-41, fev. 1996. DOI: 10.1109/3477.484436. Disponível em: https://doi.org/10.1109/3477.484436. Acesso em: 19 ago. 2026.
11. FOGEL, Lawrence J.; OWENS, Alvin J.; WALSH, Michael J. Artificial intelligence through simulated evolution. Nova York: John Wiley & Sons, 1966.
12. GOLDBERG, David E. Genetic algorithms in search, optimization, and machine learning. Reading: Addison-Wesley, 1989.
13. GOOGLE DEEPMIND. AlphaEvolve: a Gemini-powered coding agent for designing advanced algorithms. Londres: Google DeepMind, 14 maio 2025. Disponível em: https://deepmind.google/blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms/. Acesso em: 19 ago. 2026.
14. GOSS, S.; ARON, S.; DENEUBOURG, J. L.; PASTEELS, J. M. Self-organized shortcuts in the Argentine ant. Naturwissenschaften, v. 76, n. 12, p. 579-581, 1989. DOI: 10.1007/BF00462870. Disponível em: https://doi.org/10.1007/BF00462870. Acesso em: 19 ago. 2026.
15. HOLLAND, John H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press, 1975.
16. HORNBY, Gregory S.; GLOBUS, Al; LINDEN, Derek S.; LOHN, Jason D. Automated antenna design with evolutionary algorithms. In: AIAA SPACE 2006 CONFERENCE & EXPOSITION, 2006, San Jose. Anais. Reston: AIAA, 2006. DOI: 10.2514/6.2006-7242. Disponível em: https://ntrs.nasa.gov/citations/20060024675. Acesso em: 19 ago. 2026.
17. HORNBY, Gregory S.; LOHN, Jason D.; LINDEN, Derek S. Computer-automated evolution of an X-band antenna for NASA's Space Technology 5 mission. Evolutionary Computation, v. 19, n. 1, p. 1-23, 2011. DOI: 10.1162/EVCO_a_00005. Disponível em: https://doi.org/10.1162/EVCO_a_00005. Acesso em: 19 ago. 2026.
18. INSTITUTO BRASILEIRO DE GEOGRAFIA E ESTATÍSTICA (IBGE). De 2022 a 2024, percentual de empresas industriais utilizando inteligência artificial subiu de 16,9% para 41,9%. Agência IBGE Notícias, Rio de Janeiro, 24 set. 2025. Disponível em: https://agenciadenoticias.ibge.gov.br/agencia-noticias/2012-agencia-de-noticias/noticias/44551-de-2022-a-2024-percentual-de-empresas-industriais-utilizando-inteligencia-artificial-subiu-de-16-9-para-41-9. Acesso em: 19 ago. 2026.
19. KENNEDY, James; EBERHART, Russell. Particle swarm optimization. In: INTERNATIONAL CONFERENCE ON NEURAL NETWORKS, 1995, Perth. Proceedings of ICNN'95. Piscataway: IEEE, 1995. v. 4, p. 1942-1948. DOI: 10.1109/ICNN.1995.488968. Disponível em: https://doi.org/10.1109/ICNN.1995.488968. Acesso em: 19 ago. 2026.
20. KOZA, John R. Genetic programming: on the programming of computers by means of natural selection. Cambridge: MIT Press, 1992.
21. LOHN, Jason D.; LINDEN, Derek S.; HORNBY, Gregory S.; KRAUS, William F.; RODRIGUEZ-ARROYO, Adan; SEUFERT, Stephen E. Evolutionary design of an X-band antenna for NASA's Space Technology 5 mission. In: NASA/DOD CONFERENCE ON EVOLVABLE HARDWARE, 2003. Anais. Piscataway: IEEE, 2003. Disponível em: https://ntrs.nasa.gov/api/citations/20030067398/downloads/20030067398.pdf. Acesso em: 19 ago. 2026.
22. MORRIS, Garrett M.; GOODSELL, David S.; HALLIDAY, Robert S.; HUEY, Ruth; HART, William E.; BELEW, Richard K.; OLSON, Arthur J. Automated docking using a Lamarckian genetic algorithm and an empirical binding free energy function. Journal of Computational Chemistry, v. 19, n. 14, p. 1639-1662, 1998. DOI: 10.1002/(SICI)1096-987X(19981115)19:14<1639::AID-JCC10>3.0.CO;2-B.
23. RECHENBERG, Ingo. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart-Bad Cannstatt: Frommann-Holzboog, 1973. (Problemata, 15).
24. REYNOLDS, Craig W. Flocks, herds and schools: a distributed behavioral model. ACM SIGGRAPH Computer Graphics, v. 21, n. 4, p. 25-34, 1987. DOI: 10.1145/37402.37406. Disponível em: https://doi.org/10.1145/37402.37406. Acesso em: 19 ago. 2026.
25. ROMERA-PAREDES, Bernardino et al. Mathematical discoveries from program search with large language models. Nature, v. 625, n. 7995, p. 468-475, 2024. DOI: 10.1038/s41586-023-06924-6. Disponível em: https://www.nature.com/articles/s41586-023-06924-6. Acesso em: 19 ago. 2026.
26. RUDOLPH, Günter. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, v. 5, n. 1, p. 96-101, jan. 1994. DOI: 10.1109/72.265964. Disponível em: https://doi.org/10.1109/72.265964. Acesso em: 19 ago. 2026.
27. SHI, Yuhui; EBERHART, Russell. A modified particle swarm optimizer. In: IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION, 1998. IEEE World Congress on Computational Intelligence. Piscataway: IEEE, 1998. p. 69-73. DOI: 10.1109/ICEC.1998.699146.
28. TURING, Alan M. Computing machinery and intelligence. Mind, v. LIX, n. 236, p. 433-460, out. 1950. DOI: 10.1093/mind/LIX.236.433. Disponível em: https://academic.oup.com/mind/article/LIX/236/433/986238. Acesso em: 19 ago. 2026.
29. TURING, Alan M. Intelligent machinery. In: MELTZER, Bernard; MICHIE, Donald (ed.). Machine Intelligence 5. Edimburgo: Edinburgh University Press, 1969. p. 3-23. [Relatório do National Physical Laboratory redigido em 1948].
30. WOLPERT, David H.; MACREADY, William G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, v. 1, n. 1, p. 67-82, abr. 1997. DOI: 10.1109/4235.585893. Disponível em: https://doi.org/10.1109/4235.585893. Acesso em: 19 ago. 2026.