↘
construir + refinarMETAHEURÍSTICAS CLÁSSICAS · SUBTÓPICO 04
Construa com critério. Sacuda com intenção.
GRASP produz muitos bons pontos de partida com aleatoriedade controlada. VNS muda sistematicamente a vizinhança quando a busca local para de encontrar melhorias.
↻
sacudir + buscar01 · DUAS FORMAS DE ESCAPAR
A variedade pode entrar no início ou durante o caminho.
Construa várias soluções diferentes.
lista restrita→sorteio guloso→busca local→repetir
Em cada iteração, a construção escolhe aleatoriamente entre candidatos suficientemente bons; depois, uma busca local intensifica o resultado.
Mude o tipo de perturbação.
N₁: troca→N₂: inserção→N₃: inversão→reiniciar
Quando uma vizinhança não gera melhora, VNS “sacode” a solução em uma vizinhança maior e volta a intensificar localmente.
02 · CONTROLE DA ALEATORIEDADE
Em GRASP, α regula quão gulosa é a construção.
Só o melhor candidato entra na lista restrita. É rápido, mas repete soluções parecidas.
A lista restrita de candidatos equilibra qualidade e diversidade entre as execuções.
Todos os candidatos podem entrar. A diversidade cresce, mas a construção perde orientação.
03 · LABORATÓRIO INTERATIVO
Faça construções GRASP e perturbações VNS na mesma rota.
O cenário usa seis cidades. GRASP gera uma rota inicial a partir de uma lista restrita; VNS testa trocas cada vez maiores antes de retornar à busca local.
Rota e perturbação
O traço mostra a solução que será refinada pela busca local.
Melhor custo por fase
Construções diferentes e vizinhanças maiores ampliam as chances de melhoria.
04 · QUANDO USAR CADA UMA
As duas técnicas também funcionam muito bem juntas.
AspectoGRASPVNSCombinação
Fonte de diversidadeconstruções distintasvizinhanças distintasinício + trajetória
Intensificaçãobusca local após construirbusca local após sacudirem ambos os momentos
Parâmetro centralα / tamanho da RCLordem e limite de korçamento total
05 · NO CÓDIGO
Uma solução diferente a cada rodada, uma vizinhança diferente quando necessário.
const semente = construirComRCL(alpha);
let melhor = buscaLocal(semente);
for (let k = 1; k <= kMax; k++) {
const candidata = buscaLocal(perturbar(melhor, k));
if (custo(candidata) < custo(melhor)) { melhor = candidata; k = 0; }
}Construir
Escolha na RCL.
Refinar
Faça busca local.
Sacudir
Aplique Nₖ.
Alternar
Troque k ou recomece.
FIM DAS METAHEURÍSTICAS CLÁSSICAS
Próximo: algoritmos bioinspirados.
Agora a exploração passa a ser conduzida por populações, evolução e enxames.
Iniciar módulo →