do espaço verificado ou logicamente descartado
garantia de ótimoFUNDAMENTOS DE OTIMIZAÇÃO · SUBTÓPICO 06
Garantia, velocidade ou flexibilidade?
Métodos exatos provam a melhor resposta. Heurísticas usam conhecimento específico para decidir rápido. Metaheurísticas organizam uma busca flexível quando examinar tudo é inviável.
regra construída para um tipo de problema
boa resposta práticaestratégia geral de exploração e melhoria
equilíbrio da busca01 · TRÊS FORMAS DE PROCURAR
A diferença está no compromisso assumido.
Encontrar e provar
Explora o espaço sistematicamente ou usa propriedades matemáticas para eliminar regiões sem perder o ótimo.
- Ótimo garantido
- Limites e provas
- Custo pode crescer muito
força bruta · branch and bound · programação linearUsar uma regra útil
Aplica conhecimento do problema para construir uma solução rapidamente, sem garantia geral de ótimo.
- Execução rápida
- Regra específica
- Pode produzir viés
vizinho mais próximo · guloso · regra de prioridadeGuiar a busca
Define mecanismos gerais para explorar, intensificar e escapar de ótimos locais em diferentes problemas.
- Flexível e adaptável
- Busca iterativa
- Resultado aproximado
AG · PSO · ACO · recozimento simulado02 · GARANTIA × RECURSOS
A melhor escolha depende do tamanho e da exigência.
LEITURA DO MAPAMais garantia costuma exigir mais recurso computacional.
Os pontos indicam a posição típica de cada família — não uma regra absoluta.
Garantia da soluçãomaior
ótimo comprovadomenor
boa solução, sem prova
ótimo comprovadomenor
boa solução, sem prova
decisão críticapriorize prova
resposta rápidapriorize velocidade
grande espaço de buscaequilibre qualidade e orçamento
Exatoótimo comprovadocusto tende a crescer
Heurísticaresposta rápidasem garantia geral
Metaheurísticabusca adaptávelqualidade × orçamento
menor custo computacionalmaior custo computacional
03 · COMO CADA MÉTODO VÊ UMA ROTA
O mesmo problema produz buscas muito diferentes.
120 rotas
Enumera e compara
Com cinco destinos e início fixo, avalia todas as 5! permutações.
mais perto → próximo
Constrói uma vez
Parte da origem e sempre escolhe a cidade ainda não visitada mais próxima.
gerar ↔ melhorar
Modifica repetidamente
Troca trechos, aceita melhorias e mantém a melhor rota descoberta.
04 · LABORATÓRIO INTERATIVO
Resolva a mesma rota por três estratégias.
Compare distância, avaliações realizadas e evolução da melhor solução.
Melhor rota encontrada
Execute uma estratégia para iniciar.
Melhor valor por avaliação
A curva desce quando uma rota melhor é encontrada.
05 · QUANDO USAR
O contexto define o compromisso aceitável.
CenárioPreferênciaMotivo
Problema pequeno e decisão críticaExato
É possível pagar pelo tempo necessário para obter prova de otimalidade.
Resposta imediata com regra conhecidaHeurística
Uma construção simples atende ao tempo disponível.
Espaço grande e solução aproximada aceitávelMetaheurística
O orçamento é direcionado para regiões promissoras.
Planejamento operacional recorrenteHíbrido
Uma heurística cria a solução inicial e uma metaheurística a melhora.
06 · PRINCÍPIO CENTRAL
Qualidade deve ser comparada sob o mesmo orçamento.
FUNDAMENTOS DE OTIMIZAÇÃO CONCLUÍDOS
Próximo submenu: Fundamentos de Metaheurísticas.
Começaremos definindo solução candidata, população e fitness.
Iniciar próximo submenu →