METAHEURÍSTICAS CLÁSSICAS · SUBTÓPICO 01

Subir sempre melhora — até a paisagem enganar.

Hill Climbing examina soluções vizinhas e troca o estado atual por uma alternativa melhor. É simples, rápido e útil, mas enxerga apenas o relevo ao seu redor.

Executar a subidaEntender o ciclo
1234ótimo localótimo global
estado atual vizinho aceitoaceitar se f(x′) > f(x)

01 · MECANISMO CENTRAL

Um ciclo curto produz a trajetória completa.

01Estado atual

Comece com uma solução válida x.

x ← solução inicial
→
02Vizinhança

Gere soluções próximas por um movimento.

N(x)
→
03Avaliação

Compare a qualidade dos candidatos.

f(x′) versus f(x)
→
04Decisão

Aceite uma melhora ou encerre a subida.

x ← x′

02 · ESCOLHA DO VIZINHO

“Subir” pode significar três decisões diferentes.

PRIMEIRA MELHORA

Parar na primeira opção melhor

Avalia menos vizinhos e pode avançar rapidamente.

first improvement
MELHOR MELHORA

Examinar todos e escolher o melhor

Gasta mais por ciclo para realizar o passo mais promissor.

steepest ascent
ESTOCÁSTICA

Sortear entre as melhorias

Adiciona variedade sem aceitar movimentos piores.

P(x′) ∝ ganho(x′)

03 · LIMITES DA VISÃO LOCAL

Nem toda parada significa que o melhor foi encontrado.

ÓTIMO LOCAL

O topo mais próximo vence

Nenhum vizinho melhora, embora exista outra região superior.

PLATÔ

Vizinhos parecem equivalentes

A função não oferece direção clara para continuar.

CRISTA

O melhor caminho exige combinação

Movimentos isolados não acompanham uma direção diagonal estreita.

informação disponívelsomente N(x)
+
regra de aceitaçãoapenas melhora
→
garantia obtidaótimo local

04 · LABORATÓRIO INTERATIVO

Escolha um início e acompanhe cada subida.

A paisagem possui dois picos. Aumente o raio para incluir outra bacia na vizinhança e alcançar o pico global.

EXPERIMENTO 11
iteração0
posição x1,20
qualidade f(x)—
avaliações1

Paisagem de busca

A faixa violeta representa N(x); os pontos menores são candidatos avaliados.

pronta
ESTADO ATUALx = 1,20f(x) = —
→
VIZINHO ESCOLHIDOaguardandoexecute um passo
→
DECISÃOprontanenhuma comparação

05 · ESCAPES PRÁTICOS

Recomeçar amplia o que uma busca local consegue enxergar.

UMA EXECUÇÃOum início → um ótimo local

O resultado depende diretamente da solução inicial.

MULTI-STARTvários inícios → comparar finais

Execuções independentes cobrem diferentes bacias de atração.

PERTURBAR E RETOMARescapar → intensificar novamente

Um salto maior fornece outra região para a busca local refinar.

06 · NO CÓDIGO

A versão essencial cabe em poucas linhas.

hill-climbing.js
function hillClimbing(inicial) {
  let atual = inicial;

  while (true) {
    const vizinho = melhorDe(vizinhanca(atual));
    if (fitness(vizinho) <= fitness(atual)) break;
    atual = vizinho;
  }

  return atual;
}
1
Inicializar

Escolha um candidato válido.

2
Gerar vizinhos

Aplique movimentos pequenos.

3
Aceitar melhora

Mantenha a trajetória ascendente.

4
Parar

Retorne quando nenhum vizinho superar o atual.

PRÓXIMO SUBTÓPICO

Recozimento Simulado.

O próximo método aceitará algumas pioras para atravessar vales e escapar de ótimos locais.

Continuar estudo →