Skip to content

Métodos de Busca Heurística

As heurísticas de busca são estratégias para encontrar soluções em problemas difíceis sem precisar explorar todo o espaço de possibilidades. Elas não garantem o resultado ótimo, mas entregam respostas úteis com um custo de tempo menor. Temos aqui algumas famílias de heurísticas e uma implementação em pseudocódigo para servir de inspiração, mas não se sinta satisfeito apenas com o que temos aqui, existem inúmeras heuristicas que não estão descritas aqui.

Heurísticas construtivas

A ideia é construir passo a passo a solução seguindo uma regra de decisão. Essa regra pode ser gulosa (sempre escolher o melhor incremento local) ou conter aleatoriedade para gerar diversidade. No cacheiro viajante, por exemplo, a cidade mais próxima ainda não visitada é escolhida; em mochila, o iten é escolhido por melhor relação valor/peso até atingir a capacidade máxima da mochila.

def heuristica_construtiva():
    S = solucao_vazia()
    while not solucao_completa(S):
        candidatos = candidatos_admissiveis(S)
        # regra gulosa: minimiza custo incremental 
        c_escolhido = min(candidatos, key=lambda c: custo_incremental(S, c))
        S = inserir(S, c_escolhido)           # atualizar estado parcial
    return S

Busca local

Partimos de uma solução inicial e tentamos melhorá-la explorando “vizinhos” obtidos por pequenas alterações. Se um vizinho melhora o custo, aceitamos a mudança e repetimos o processo até não existir mais melhora.

def busca_local(S0):
    S = S0
    while True:
        melhorou = False
        for S_viz in gerar_vizinhos(S):
            if custo(S_viz) < custo(S):
                S = S_viz          # estratégia "first improvement"
                melhorou = True
                break
        if not melhorou:
            break
    return S

Heurísticas baseadas em construção

Combinam construção e refino: primeiro geramos uma boa solução inicial de forma gulosa ou com aleatoriedade e, em seguida, aplicamos busca local para polir o resultado.

def construcao_mais_refino():
    S = heuristica_construtiva()  # ou uma variação com aleatoriedade (RCL)
    S = busca_local(S)            # refino por movimentos locais
    return S

Heurísticas baseadas em modificação

Aqui trabalhamos sobre uma solução existente aplicando uma perturbação para escapar de ótimos locais. Após perturbar, refinamos novamente com busca local. Esse padrão é a base do ILS (Iterated Local Search) e do VNS (Variable Neighborhood Search).

def modificacao_baseada(S_inicial, max_iter=100):
    S_best = S_inicial
    for _ in range(max_iter):
        S_pert = perturbar(S_best, intensidade=ajustar_intensidade())
        S_ref = busca_local(S_pert)
        if custo(S_ref) < custo(S_best):
            S_best = S_ref
    return S_best

Heurísticas baseadas em recombinação

Inspiradas em algoritmos evolutivos, combinam duas (ou mais) soluções “pais” para gerar uma nova solução “filha”, aproveitando blocos de boa qualidade de cada pai. Depois, refinam a filha com busca local.

def recombinacao_baseada(populacao, criterio_parada):
    P = inicializar_populacao(populacao)
    while not criterio_parada(P):
        A, B = selecionar_pais(P)             # torneio, roleta, ranking etc.
        C = recombinar(A, B)                  # OX/PMX/path-relinking/união+reparo
        C = busca_local(C)                    # passo memético (refino)
        P = atualizar_populacao(P, C)         # elitismo/substituição
    return melhor_solucao(P)

Hibridização de heurísticas

Misturamos estratégias para buffar o algorítmo: construção gulosa aleatória para diversidade, seguida de busca local para intensificação, e ILS para escapar de ótimos locais.

def hibrida_grasp_ils(max_iter=50):
    S_best = None
    for _ in range(max_iter):
        S = construtiva_aleatoria_com_RCL()   # construção com lista restrita de candidatos
        S = busca_local(S)                    # intensificação
        S = ILS(S)                            # diversificação controlada
        if S_best is None or custo(S) < custo(S_best):
            S_best = S
    return S_best

def ILS(S, limite_sem_melhora=10):
    sem_melhora = 0
    while sem_melhora < limite_sem_melhora:
        S_p = perturbar(S)                    # ex.: ruin&recreate, 3-opt forte, shake(VNS)
        S_p = busca_local(S_p)
        if custo(S_p) < custo(S):
            S = S_p
            sem_melhora = 0
        else:
            sem_melhora += 1
    return S

Híper-heurísticas

Em vez de desenhar uma única heurística, criamos um “orquestrador” que escolhe dinamicamente qual heurística de baixo nível aplicar a cada momento, com base em desempenho observado. Assim, o sistema alterna entre operadores como 2-opt, swap e reinserção, aprendendo quais funcionam melhor ao longo da execução.

from math import sqrt, log
import random

def hiper_heuristica(S0, heuristicas, T, epsilon=0.1):
    # heuristicas: lista de funções do tipo h(S) -> S'
    estat = {h: {"ganho": 0.0, "usos": 0} for h in heuristicas}
    S = S0
    for t in range(1, T + 1):
        if random.random() < epsilon:
            h = random.choice(heuristicas)    # exploração
        else:
            h = selecionar_por_ucb(estat, t)  # exploração vs. exploração

        S_novo = h(S)
        ganho = max(0.0, custo(S) - custo(S_novo))
        estat[h]["ganho"] += ganho
        estat[h]["usos"]  += 1

        if custo(S_novo) < custo(S):
            S = S_novo
    return S

def selecionar_por_ucb(estat, t):
    # UCB1 simples: média + sqrt(2*ln(t)/n)
    melhor_h, melhor_score = None, float("-inf")
    for h, info in estat.items():
        n = max(1, info["usos"])
        media = info["ganho"] / n
        bonus = sqrt(2.0 * log(max(2, t)) / n)
        score = media + bonus
        if score > melhor_score:
            melhor_h, melhor_score = h, score
    return melhor_h

Entendi! Você quer exemplos de heurísticas aleatórias (estratégias que exploram o espaço com escolhas ao acaso) e de heurísticas com filtro (estratégias que usam algum critério para selecionar candidatos, descartando opções ruins). Vou explicar de forma didática e depois te dar exemplos em pseudocódigo estilo Python.


Heurísticas aleatórias

A ideia aqui é simples: em vez de sempre escolher o “melhor” próximo passo, escolhemos aleatoriamente uma opção, ou entre todas, ou entre um subconjunto. Isso permite explorar soluções diferentes e fugir de caminhos muito determinísticos.

import random

def heuristica_aleatoria(items, capacidade):
    mochila = []
    peso = 0
    while True:
        candidatos = [i for i in items if peso + i.peso <= capacidade]
        if not candidatos:
            break
        escolhido = random.choice(candidatos)   # sorteia qualquer candidato viável
        mochila.append(escolhido)
        peso += escolhido.peso
        items.remove(escolhido)
    return mochila

Heurísticas com filtro

Aqui, em vez de aceitar qualquer candidato, aplicamos um filtro para limitar as opções a um subconjunto de candidatos considerados “bons”. Depois, escolhemos um deles (às vezes aleatoriamente, às vezes pelo melhor custo). Essa ideia é a base do GRASP.

import random

def heuristica_com_filtro(items, capacidade, alpha=0.3):
    mochila = []
    peso = 0
    while True:
        candidatos = [i for i in items if peso + i.peso <= capacidade]
        if not candidatos:
            break
        # filtro: mantém apenas candidatos dentro do top α (percentil de valor/peso)
        ratio = [i.valor / i.peso for i in candidatos]
        limite = min(ratio) + alpha * (max(ratio) - min(ratio))
        RCL = [i for i in candidatos if i.valor / i.peso >= limite]

        escolhido = random.choice(RCL)   # escolhe entre bons candidatos
        mochila.append(escolhido)
        peso += escolhido.peso
        items.remove(escolhido)
    return mochila