SEMINÁRIO DE METHAHEURÍSTICA

Meta-heurísticas em
Otimização Combinatória
1a. Aula

Professores: Dario Aloise
Lima Júnior
14/agosto / 2012
1

Conteúdo do curso


Parte I - Complexidade de Algoritmos e Problemas
(introdutório) -> Prova ou trabalho!



Parte II - Meta-heurísticas:
◦ Heurísticas gulosas;
◦ MH p.d.



Trabalho da parte II:
◦ Implementação;
◦ Artigo científico (interpretação);
◦ Apresentação (trabalhos, seminário).

2

Parte I – 1ª. Aula
Complexidade Computacional de
Algoritmos e Problemas
(Motivação)

3

Otimização
Dado um conjunto X de soluções e uma função objetivo f: X, que associa a cada solução x  X um valor real f(x), a área de otimização consiste em desenvolver metodologias para encontrar a solução x*  X, dita ótima, para a qual f(x) é mínima (ou máxima).

4

Otimização Combinatória



Trata problemas de otimização em que o conjunto de soluções é discreto.
Dados
◦ Um conjunto finito E = {1,2,...,n}
E
◦ Uma função de custo c : 2 



O objetivo é encontrar x  F tal que
*

c( x )  c( x), x  F
*

onde F  2 problema. E

é o conjunto de soluções viáveis do

5

Otimização Combinatória
Min (Max) {Função Objetivo} suj. à:
 Programação

ou

Sol.Viáveis  discreto   Otimização
 Combinatória


Ou seja,
Min (Max) f(x)
Suj. à: x F  X,
Onde: X 

n

e

 X  < .

A busca por x em F que satisfaz o problema

“Complexidade Computacional”
6

Otimização Combinatória
Exemplos de Problemas de Otimização Combinatória (POC):
1- Árvore Geradora Mínima: nn-2 (Teorema de Caley).
Grafo original

K4 n=4 nn-2=42= 16

p/ n = 8, tem-se 262.144 candidatos à Árvore Geradora Mínima

7

Otimização Combinatória
Árvore Geradora Mínima

Grafo - Exemplo

8

Otimização Combinatória
2 - CAMINHO MAIS CURTO - Seja Kn+2 um grafo não-orientado, completo, com n+2 nós.
O número total de caminhos elementares unindo dois nós i  j é igual a: n n

k 0

 