Os algoritmos evolucionários são métodos de busca e otimização inspirados na evolução biológica. Também conhecidos como planos adaptativos, eles imitam processos como mutação, recombinação e seleção natural para encontrar soluções para problemas complexos.
Conceitos básicos
- Mutações: pequenas alterações aleatórias em uma solução já existente, com o objetivo de melhorar o resultado. Muitas vezes seguem uma distribuição normal, ou seja, mudam pouco na maioria dos casos.
- Recombinação: mistura características de duas soluções diferentes para gerar uma nova.
- Crossover: tipo de recombinação que combina partes específicas de duas soluções.
- Espaço de busca: conjunto de todas as soluções possíveis que podem ser exploradas.
- Espaço de parâmetros: além da busca pelo melhor resultado, também define como a procura é feita, ou seja, quais argumentos e estratégias são usados.
Principais métodos
Algoritmos Genéticos (AG) – 1962
Inspirados nos processos genéticos de organismos biológicos, enfatizam a recombinação como principal operador de busca e usam mutações de forma secundária.Estratégias Evolutivas (EE) – 1966
Focam principalmente nas mutações, sem incluir recombinação. Muito usados em problemas de otimização contínua.Programação Evolutiva (PE) – 1973/1975
Destaca mutações com distribuição normal aplicadas em vetores reais. Dá ênfase tanto à mutação quanto à recombinação no processo de busca.Programação Genética (PG) – 1992
Representa soluções como estruturas de árvore, aplicando operadores de mutação e crossover nesse formato.
Exemplo simples: a pizza perfeita
Imagine que cada pizza é descrita por três números: quantidade de queijo, molho e tempero. A ideia é encontrar a pizza “ideal”, próxima de uma receita-alvo. Para isso:
- Gera-se uma população inicial de pizzas com quantidades aleatórias.
- Cada pizza é avaliada pela proximidade em relação à receita perfeita.
- As melhores pizzas são selecionadas e, a partir delas, cria-se uma nova geração usando crossover (mistura de receitas) e mutação (pequenas mudanças).
Esse processo é repetido por várias gerações até que a população convirja para pizzas próximas da ideal.
// Cada pizza é representada por 3 números:
// quantidade de queijo, quantidade de molho e quantidade de tempero.
// (na vida real seria mais complexo, mas vamos simplificar)
type Pizza = { queijo: number; molho: number; tempero: number };
// Criar uma pizza aleatória
function pizzaAleatoria(): Pizza {
return {
queijo: Math.random() * 10, // até 10 colheres
molho: Math.random() * 10,
tempero: Math.random() * 10
};
}
// Nossa função de "provar a pizza e dar nota"
// Aqui eu inventei que a pizza perfeita é 8 de queijo, 5 de molho e 3 de tempero.
// Quanto mais perto disso, maior a nota.
function avaliar(pizza: Pizza): number {
const alvo = { queijo: 8, molho: 5, tempero: 3 };
const erro =
Math.abs(pizza.queijo - alvo.queijo) +
Math.abs(pizza.molho - alvo.molho) +
Math.abs(pizza.tempero - alvo.tempero);
return -erro; // quanto menor o erro, melhor a nota
}
// Misturar duas pizzas (Crossover)
// Pegamos metade dos ingredientes da primeira pizza e o resto da segunda.
function crossover(p1: Pizza, p2: Pizza): Pizza {
return {
queijo: Math.random() < 0.5 ? p1.queijo : p2.queijo,
molho: Math.random() < 0.5 ? p1.molho : p2.molho,
tempero: Math.random() < 0.5 ? p1.tempero : p2.tempero
};
}
// Mudar um pouco uma pizza (Mutação)
// Pequenas alterações para tentar melhorar
function mutacao(p: Pizza): Pizza {
return {
queijo: p.queijo + (Math.random() - 0.5), // muda no máximo meio ponto pra cima ou pra baixo
molho: p.molho + (Math.random() - 0.5),
tempero: p.tempero + (Math.random() - 0.5)
};
}
// Nosso "campeonato de pizzas"
function buscarPizzaPerfeita() {
let populacao: Pizza[] = Array.from({ length: 10 }, pizzaAleatoria);
for (let geracao = 1; geracao <= 20; geracao++) {
// Avaliamos todas as pizzas
populacao.sort((a, b) => avaliar(b) - avaliar(a));
console.log(`Geração ${geracao} - Melhor pizza:`, populacao[0], "Nota:", avaliar(populacao[0]));
// Pegamos as 5 melhores pizzas
const melhores = populacao.slice(0, 5);
// Criamos novas pizzas misturando e mutando
let novaPop: Pizza[] = [];
while (novaPop.length < 10) {
const pai = melhores[Math.floor(Math.random() * melhores.length)];
const mae = melhores[Math.floor(Math.random() * melhores.length)];
let filho = crossover(pai, mae); // misturando receitas
filho = mutacao(filho); // mudando um pouco
novaPop.push(filho);
}
populacao = novaPop;
}
}
buscarPizzaPerfeita();
Exemplo mais realista: ajuste de hiperparâmetros
Um caso prático é a otimização de modelos de Machine Learning. Em vez de pizza, temos parâmetros como:
- learningRate (taxa de aprendizado)
- numTrees (número de árvores)
- maxDepth (profundidade máxima)
O algoritmo evolucionário gera diferentes combinações desses parâmetros, avalia o desempenho do modelo em cada uma delas e mantém as melhores combinações para as próximas gerações. Isso é muito próximo do que frameworks como Optuna, DEAP e Nevergrad fazem em produção.
type Modelo = { learningRate: number; numTrees: number; maxDepth: number };
// Gera um modelo com parâmetros aleatórios
function modeloAleatorio(): Modelo {
return {
learningRate: +(Math.random() * 0.49 + 0.01).toFixed(2), // entre 0.01 e 0.5
numTrees: Math.floor(Math.random() * 191) + 10, // entre 10 e 200
maxDepth: Math.floor(Math.random() * 14) + 2 // entre 2 e 15
};
}
// "Avalia" o modelo (simulação)
// Aqui não treinamos um modelo real (seria pesado), só simulamos a precisão.
function avaliar(modelo: Modelo): number {
// Simulação de pontuação: combina parâmetros e adiciona um pouco de aleatoriedade
const scoreBase =
-Math.abs(modelo.learningRate - 0.15) * 50 + // bom se for perto de 0.15
-Math.abs(modelo.numTrees - 120) * 0.1 + // bom se for perto de 120
-Math.abs(modelo.maxDepth - 8) * 2; // bom se for perto de 8
return scoreBase + Math.random() * 5; // ruído para simular variação real
}
// Mistura dois modelos (crossover)
function crossover(a: Modelo, b: Modelo): Modelo {
return {
learningRate: Math.random() < 0.5 ? a.learningRate : b.learningRate,
numTrees: Math.random() < 0.5 ? a.numTrees : b.numTrees,
maxDepth: Math.random() < 0.5 ? a.maxDepth : b.maxDepth
};
}
// Pequenas mudanças (mutação)
function mutacao(m: Modelo): Modelo {
return {
learningRate: +(m.learningRate + (Math.random() - 0.5) * 0.05).toFixed(2),
numTrees: m.numTrees + Math.floor((Math.random() - 0.5) * 10),
maxDepth: m.maxDepth + Math.floor((Math.random() - 0.5) * 2)
};
}
// O "campeonato" de modelos
function buscarMelhorModelo() {
let populacao: Modelo[] = Array.from({ length: 12 }, modeloAleatorio);
for (let geracao = 1; geracao <= 15; geracao++) {
// Avalia todos
populacao.sort((a, b) => avaliar(b) - avaliar(a));
console.log(`Geração ${geracao} - Melhor modelo:`, populacao[0], "Score:", avaliar(populacao[0]).toFixed(2));
// Seleciona top 6
const melhores = populacao.slice(0, 6);
// Gera nova população
const novaPop: Modelo[] = [];
while (novaPop.length < 12) {
const pai = melhores[Math.floor(Math.random() * melhores.length)];
const mae = melhores[Math.floor(Math.random() * melhores.length)];
let filho = crossover(pai, mae);
filho = mutacao(filho);
novaPop.push(filho);
}
populacao = novaPop;
}
}
buscarMelhorModelo();
Exemplo prático com TensorFlow.js
Para ilustrar, considere o treino de uma rede neural simples (classificação do dataset Iris). O processo segue as mesmas etapas:
- Indivíduo = conjunto de hiperparâmetros (learningRate, units, epochs).
- População inicial = valores aleatórios.
- Avaliação = treinar e medir a acurácia.
- Seleção = manter os melhores.
- Crossover = misturar parâmetros de dois indivíduos.
- Mutação = pequenas alterações aleatórias.
A cada geração, o algoritmo testa várias combinações, seleciona as melhores e as combina para evoluir os resultados. Com isso, a rede vai alcançando valores de acurácia cada vez mais altos.
npm install @tensorflow/tfjs @tensorflow/tfjs-node
import * as tf from '@tensorflow/tfjs-node';
// ---------- 1) Carregar dados ----------
import iris from 'ml-dataset-iris';
// X = características, Y = classes
const X = iris.getNumbers();
const yLabels = iris.getClasses().map(c => {
if (c === 'setosa') return 0;
if (c === 'versicolor') return 1;
return 2;
});
// Normaliza os dados
const Xtensor = tf.tensor2d(X);
const mean = Xtensor.mean(0);
const std = Xtensor.sub(mean).square().mean(0).sqrt();
const Xnorm = Xtensor.sub(mean).div(std);
const Ytensor = tf.oneHot(tf.tensor1d(yLabels, 'int32'), 3);
// Divide treino/teste
const trainSize = Math.floor(X.length * 0.8);
const Xtrain = Xnorm.slice([0, 0], [trainSize, -1]);
const Ytrain = Ytensor.slice([0, 0], [trainSize, -1]);
const Xtest = Xnorm.slice([trainSize, 0], [X.length - trainSize, -1]);
const Ytest = Ytensor.slice([trainSize, 0], [X.length - trainSize, -1]);
// ---------- 2) Função para criar modelo ----------
async function criarEavaliar(params) {
const model = tf.sequential();
model.add(tf.layers.dense({ units: params.units, activation: 'relu', inputShape: [4] }));
model.add(tf.layers.dense({ units: 3, activation: 'softmax' }));
const optimizer = tf.train.adam(params.learningRate);
model.compile({ optimizer, loss: 'categoricalCrossentropy', metrics: ['accuracy'] });
// Treinar silenciosamente
await model.fit(Xtrain, Ytrain, {
epochs: params.epochs,
verbose: 0
});
// Avaliar no teste
const evalResult = model.evaluate(Xtest, Ytest, { verbose: 0 });
const acc = (await evalResult[1].data())[0];
return acc; // acurácia
}
// ---------- 3) Gerar indivíduo aleatório ----------
function individuoAleatorio() {
return {
learningRate: +(Math.random() * 0.09 + 0.01).toFixed(3), // 0.01 - 0.1
units: Math.floor(Math.random() * 40) + 5, // 5 - 45
epochs: Math.floor(Math.random() * 50) + 10 // 10 - 60
};
}
// ---------- 4) Crossover ----------
function crossover(a, b) {
return {
learningRate: Math.random() < 0.5 ? a.learningRate : b.learningRate,
units: Math.random() < 0.5 ? a.units : b.units,
epochs: Math.random() < 0.5 ? a.epochs : b.epochs
};
}
// ---------- 5) Mutação ----------
function mutacao(ind) {
const novo = { ...ind };
const chave = Math.floor(Math.random() * 3);
if (chave === 0) {
novo.learningRate = +(novo.learningRate + (Math.random() - 0.5) * 0.01).toFixed(3);
novo.learningRate = Math.max(0.001, Math.min(0.1, novo.learningRate));
} else if (chave === 1) {
novo.units = Math.max(5, Math.min(50, novo.units + Math.floor((Math.random() - 0.5) * 10)));
} else {
novo.epochs = Math.max(5, Math.min(100, novo.epochs + Math.floor((Math.random() - 0.5) * 10)));
}
return novo;
}
// ---------- 6) Algoritmo evolucionário ----------
async function evolucao(geracoes = 5, tamanhoPop = 6) {
let populacao = Array.from({ length: tamanhoPop }, individuoAleatorio);
for (let g = 1; g <= geracoes; g++) {
// Avaliar todos
const notas = [];
for (const ind of populacao) {
const acc = await criarEavaliar(ind);
notas.push({ ind, acc });
}
// Ordenar por acurácia
notas.sort((a, b) => b.acc - a.acc);
console.log(`Geração ${g} - Melhor: ACC=${notas[0].acc.toFixed(4)} Params=`, notas[0].ind);
// Seleção
const elite = notas.slice(0, tamanhoPop / 2).map(n => n.ind);
// Nova população
const novaPop = [...elite];
while (novaPop.length < tamanhoPop) {
const pai = elite[Math.floor(Math.random() * elite.length)];
const mae = elite[Math.floor(Math.random() * elite.length)];
let filho = crossover(pai, mae);
if (Math.random() < 0.3) filho = mutacao(filho);
novaPop.push(filho);
}
populacao = novaPop;
}
}
evolucao();
Exemplo de saída do console:
Geração 1 - Melhor: ACC=0.9333 Params= { learningRate: 0.021, units: 25, epochs: 40 }
Geração 2 - Melhor: ACC=0.9667 Params= { learningRate: 0.018, units: 30, epochs: 45 }
Geração 3 - Melhor: ACC=0.9733 Params= { learningRate: 0.019, units: 28, epochs: 50 }
Conclusão
Os algoritmos evolucionários oferecem uma forma flexível e poderosa de buscar soluções para problemas complexos. Do ajuste fino de hiperparâmetros ao design de modelos mais sofisticados, eles exploram e combinam possibilidades de maneira adaptativa, simulando a evolução natural para chegar a resultados cada vez melhores.
Top comments (0)