aula2 2012

Aurora Pozo– UFPR – Meta-Heurísticas

Metaheurísticas

DEFINIÇÃO







Uma heurística para um algoritmo heurístico
Combinam heurísticas básicas em um nível de estrutura mais alto
Eficiente e Efetivamente explorar o espaço de busca.
Metaheuristics in Combinatorial Optimization:
Overview and Conceptual Comparison.
CHRISTIAN BLUM AND ANDREA ROLI.

http://doi.acm.org/10.1145/937503.937505

METAHEURÍSTICAS




Métodos heurísticos, de caráter geral, com capacidade para escapar de ótimos locais
Podem ser baseados em Busca Local ou Busca Populacional.
Os métodos baseados em Busca Local são fundamentados na noção de vizinhança:





Dada uma solução s, diz-se que s’ é um vizinho de s, se s’ é obtido de s a partir de um movimento m, isto é: s’  s  m
A estrutura de vizinhança varia de acordo com o problema tratado

Os métodos baseados em Busca Populacional partem de um conjunto de soluções, aplicando sobre estes operadores que visam à melhoria desse conjunto.

Aurora Pozo– UFPR – Meta-Heurísticas

SIMULATED ANNEALING

Aurora Pozo– UFPR – MetaHeurísticas

INTRODUÇÃO








A origem da técnica de otimização conhecida por Simulated
Annealing (têmpera simulada ou anelamento simulado) vem de 1953, quando foi usada para simular em um computador o processo de annealing de cristais;
O annealing (anelamento ou têmpera) de certos materiais consiste em submetê-los inicialmente a altas temperaturas e reduzi-las gradualmente até atingirem, com aumentos e reduções do estado de energia, o equilíbrio térmico, tornandoos assim, consistentes e rígidos;
A técnica matemática de Simulated Annealing faz uma simulação algorítmica do processo físico da têmpera de materiais; A idéia de aplicar este método para resolver problemas de otimização combinatória surgiu bem mais tarde [Kirkpatrick et al., 1983], [Aragon et al., 1984].

Aurora Pozo– UFPR – MetaHeurísticas

FUNDAMENTAÇÃO










Proposto por Kirkpatrick et al. (1983)
Simula o processo de recozimento de metais;
O