caixeiro viajante

Capítulo

3
Meta-heurísticas e Otimização Combinatória:
Aplicações em Problemas Ambientais
José Carlos Becceneri

Resumo
Este minicurso oferece uma introdução aos problemas de natureza combinatória e à aplicabilidade de algumas meta-heurísticas utilizadas atualmente na solução desses problemas. Inicialmente, analisamos alguns conceitos básicos mais comumente empregados na área de otimização, utilizando o Problema do Caixeiro Viajante. Também são abordadas as meta-heurísticas Simulated Annealing e Colônia de Formigas.
Concluímos este minicurso expondo algumas aplicações a problemas ambientais nas quais foram utilizadas meta-heurísticas. Nosso objetivo com esse estudo é oferecer uma abordagem introdutória para pessoas que queiram se iniciar na área de Otimização
Combinatória e Meta-heurísticas.

1. Introdução
Problemas de otimização consistem em achar a melhor combinação dentre um conjunto de variáveis para maximizar ou minimizar uma função, geralmente chamada de função objetivo ou função custo. Esses problemas podem ser divididos em três categorias: aqueles cujas variáveis assumem valores reais (ou contínuos), aqueles cujas variáveis assumem valores discretos (ou inteiros) e aqueles em que há variáveis inteiras e contínuas, classificados, respectivamente, como problemas de Otimização Contínua, Otimização
Combinatória ou Discreta, e Otimização Mista. Nesta seção estudaremos apenas problemas de Otimização Combinatória.
Nosso objetivo com esse estudo é oferecer uma abordagem introdutória para pessoas que queiram se iniciar na área de Otimização Combinatória e Meta-heurísticas.
Para exemplificar alguns conceitos básicos, utilizaremos o Problema do Caixeiro Viajante, definido na próxima seção. Duas meta-heurísticas foram escolhidas para o nosso estudo:
Simulated Annealing e Colônia de Formigas. Na penúltima seção, daremos alguns exemplos da aplicabilidade das meta-heurísticas aqui estudadas. Escolhemos problemas aplicados às questões