Otimização Combinatória e o Uso de Heurísticas

O que são Problemas de Otimização Combinatória?

Problemas de Otimização Combinatória são aqueles nos quais as variáveis de decisão são discretas, ou seja, onde a solução é um conjunto ou uma sequência de inteiros ou outros objetos discretos. O desafio de encontrar soluções ótimas para tais problemas é conhecido como otimização combinatória. Estes problemas têm como característica um número enorme de soluções viáveis, que surgem de diferentes maneiras de realizar operações ou de alocar itens ou pessoas a diferentes posições.

O Conceito de Heurística

O termo "heurística" deriva da palavra grega heuriskein, que significa "encontrar" ou "descobrir". No contexto da Otimização Combinatória, uma heurística é utilizada em contraste com os métodos exatos, que garantem encontrar uma solução ótima global.

Definição: Uma heurística é uma técnica que busca encontrar boas soluções (próximas da ótima) a um custo computacional razoável, sem, no entanto, garantir a viabilidade ou a otimalidade. Em muitos casos, também não é possível estabelecer quão próxima da solução ótima uma determinada solução viável se encontra.

Heurísticas geralmente são mais flexíveis e capazes de lidar com funções-objetivo e/ou restrições mais complicadas (e mais realistas) do que os algoritmos exatos.

Por que usar Heurísticas?

Existem duas causas principais que justificam o enorme interesse no uso de heurísticas:

1. O desenvolvimento do conceito de complexidade computacional;
2. O aumento significativo na potência e eficiência das abordagens computacionais mais modernas.

Tipos de Heurísticas

• Construtivas: Iniciam com os dados do problema e, passo a passo, adicionam elementos que parecem contribuir para uma boa solução final. O ponto de partida é uma solução incompleta que é complementada gradualmente. Exemplo: Heurística do vizinho mais próximo para o problema do caixeiro-viajante.
• De Melhoramento: Partem de uma solução completa e a modificam progressivamente, buscando aperfeiçoá-la. Utilizam a ideia de vizinhança para explorar soluções alternativas. Várias soluções iniciais podem ser usadas, e a melhor solução final é escolhida. Esta estratégia também pode ser usada para transformar uma solução inviável em viável. Exemplo: Método de subida/descida (hill climbing).
• Análise de Componentes: Baseadas na abordagem "dividir para conquistar", são úteis para problemas complexos que precisam ser divididos em partes menores para análise. A ideia é lidar com os componentes separadamente e, depois, uni-los de maneira aceitável.
• De Aprendizagem: Analisam e combinam as diferentes opções como se fossem ramos de uma árvore. Um método é definido para percorrer esses ramos em busca da melhor solução, e a escolha de qual ramo seguir é guiada pela aprendizagem com os resultados de decisões anteriores. Exemplo: O término antecipado em um algoritmo de busca do tipo branch and bound.