Quando os problemas de otimização são demasiado complexos para uma resolução exata em tempo razoável (problemas NP-difíceis), recorre-se a heurísticas — algoritmos que procuram boas soluções, não necessariamente ótimas globais, com custo computacional controlado.
Algoritmo Genético
Inspirado na evolução biológica. Parte de uma população de soluções candidatas e aplica operadores de seleção, cruzamento e mutação para gerar soluções progressivamente melhores.
- Inicialização — gerar população inicial (aleatória ou heurística)
- Avaliação — calcular a função de aptidão (fitness) de cada indivíduo
- Seleção — os melhores têm maior probabilidade de serem escolhidos como progenitores
- Cruzamento (crossover) — combinar dois progenitores para gerar descendentes
- Mutação — alterar aleatoriamente parte de um indivíduo (evita convergência prematura)
- Substituição — nova geração substitui a anterior (parcial ou total)
- Repetir até critério de paragem (nº de gerações, sem melhoria há N gerações)
Exemplo de aplicação: problema de escalonamento de produção com 50 tarefas em 10 máquinas — o espaço de soluções é 50! o que torna inviável a enumeração exaustiva.
Simulated Annealing (Arrefecimento Simulado)
Inspirado no arrefecimento controlado de metais. Explora soluções vizinhas da solução atual e aceita movimentos piores com uma probabilidade que decresce com o tempo (temperatura T), permitindo escapar a ótimos locais.
- Aceitar solução pior com probabilidade: P = e−ΔE/T
- T decresce segundo uma schedule de arrefecimento (ex.: T ← αT, com α ≈ 0,95)
- Quando T → 0 o algoritmo comporta-se como uma pesquisa gulosa
Simples de implementar e eficaz no problema do caixeiro viajante e em problemas de layout de instalações.
Pesquisa Tabu (Tabu Search)
Mantém uma lista tabu de soluções (ou movimentos) recentemente visitados, proibindo revisitá-los durante um número fixo de iterações. Permite explorar regiões do espaço de soluções que um algoritmo guloso evitaria.
- Lista tabu de dimensão fixa (memória de curto prazo)
- Critério de aspiração — permite aceitar um movimento tabu se produzir um novo melhor global
- Eficaz em problemas de routing e sequenciamento
Comparação
| Heurística | Pontos fortes | Aplicações típicas |
|---|---|---|
| Algoritmo Genético | Bom em espaços de grande dimensão; paralelizável | Escalonamento, design, otimização de parâmetros |
| Simulated Annealing | Simples de implementar; poucos parâmetros | Caixeiro viajante, layout, redes |
| Pesquisa Tabu | Evita ciclos; explora bem a vizinhança | Routing, job-shop scheduling |
Heurísticas vs. métodos exatos
Os métodos exatos (Branch & Bound, Cortes de Gomory) garantem a solução ótima mas podem ser impraticáveis para instâncias grandes. As heurísticas trocam garantia de otimalidade por velocidade — na prática, soluções a 1–5 % do ótimo obtidas em segundos são frequentemente preferíveis ao ótimo exato obtido em horas.