Rede

ADEE – EST - UAlgarve

Routing com meta-heuristicas

Redes de Alto Débito

Pedro Cardoso, Ph.D. [e-mail] w3.ualg.pt/~pcardoso
• Sabia que em média uma árvore produz apenas 20 resmas de papel. Antes de imprimir este documento pense bem se tem mesmo que o fazer. Poupe papel. Lembre-se que há cada vez menos árvores. • A compra de papel 100% reciclado pós-consumo diminui sua emissão de carbono em 2,2 kg por resma. • Cada tonelada de papel reciclado economiza electricidade suficiente para iluminar uma casa de 3 quartos durante um ano. Fontes: http://www.openland.pt, http://www.diadaarvore.org.br

O que é uma heurística?
Heurística:
Arte de inventar ou descobrir; Método de ensino que procura que o aluno atinja os conhecimentos ou a solução para os problemas por esforço próprio; HISTÓRIA procura de documentos; INFORMÁTICA: regra (ou conjunto de regras) que pretende obter uma aproximação à solução de um problema;

www.infopedia.pt

12­04­08

Redes de Alto Débito

2

O que é uma heurística?
●

Exemplo: Algoritmo para dar troco
–

Enquanto não tiver o troco
●

Dá a moeda do valor mais elevado, menor ou igual do que o troco em dívida

12­04­08

Redes de Alto Débito

3

O que é uma metaheurística?
Metaelemento de formação de palavras, de origem grega, que exprime a ideia de mudança, união, transformação no vocabulário científico, e a ideia de nível superior, maior generalidade no vocabulário filosófico;

www.infopedia.pt

Na Informática: Uma meta-heurística é um método heurístico para resolver de forma genérica problemas de optimização.
12­04­08 Redes de Alto Débito 4

O que é uma metaheurística?
Algoritmo aplicável a qualquer problema onde seja possível definir uma “vizinhança”

12­04­08

Redes de Alto Débito

5

O que é uma metaheurística?
Exemplos:
Algoritmos genéticos Simulated annealing Tabu search Swarm Intelligence
Ant Colony Optimization Particle swarm optimization

...

12­04­08

Redes de