Problema do Caixeiro Viajante: um motivo para outras conversas!

O Problema do Caixeiro Viajante ...um motivo para outras conversas!

António J. Batel Anjo Departamento de Matemática Universidade de Aveiro GO-Grupo de Optimização http://www.mat.ua.pt/go

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Dada uma lista de cidades um vendedor partindo de uma cidade inicial pretende visitá-las todas uma única vez, e regressar à cidade de partida por forma a que a distância percorrida seja mínima.

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

“The Traveling Salesman, how he should be and what he should do to get Commissions and to be Successful in his Business. By a veteran Traveling Salesman” publicado na Alemanha em 1832.

Este livro apresenta a essência do problema no seu último capítulo, onde se afirma: “The most important aspect is to cover as many locations as possible, without visiting a location twice...”

• 1931-32 - Merril Flood. • 1954- Dantzig, Fulkerson e Jonhson

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

n

min S f ( )   d i  ( i ) i 1

b

c d e

D  d ij 

f

g a h

S é o conjunto de todas as permutações circulares das n cidades.

  ( (1),  (2),,  (n ))

j

i

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

... fazendo uma permutação num microsegundo 10 cidades em segundos 15 cidades em meses 20 cidades em séculos

... usando obviamente a pesquisa exaustiva.

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Classificacão de Problemas

Problemas NP-completos NP

P

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

fl417

Desempenho

p264

a535

ch130 ch150 d1655 a280

fl1577

rd100

pr1002

ulysses16

eil76

kroA100

dantzig42 bays29

st70

berlin52

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

[P]

Verificação Formal Prova de Convergência Análise da Complexidade Algoritmos

Caracterização Formal Determinismo

[NP]

Métodos Aproximados Heurísticas Metaheurísticas

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

?

Inspiração em Fenómenos Físicos

Simulação da Têmpera Métodos Genéticos Castor Atarefado Redes Neuronais Pesquisa Tabú Sistemas Formigueiro ... O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Mecanismo de transição b

b

c

c

d

d e

e

f

f

g

g

a

a h

j

h

j

i

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

i

A Questão: Metaheurística

Modelo Formal Caracterização Convergência Assimptótica (Geração Automática de ) Esquemas Algorítmicos Previsão do Desempenho Adequação O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Uma Abordagem Matemática:

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Metaheurísticas

• Algoritmos Genéticos • Redes Neuronais e Máquinas de Boltzmann • Têmpera Simulada

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Algoritmos Genéticos

...ideias de Charles Darwin sobre sobrevivência e adaptação cruzamento

1010 010101 1101 111111

mutação

1010 111111 1101 010101

1010

0 10101

1010

1

10101

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Redes Neuronais e Máquinas de Boltzmann

... modelos matemáticos baseados na conexão e funcionamento dos neurónios. ... pertencem à área da Computação Neuronal ... paralelismo

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Têmpera Simulada

Transições

Algoritmo de Metropolis O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Problemas e Complexidade

Máxima Entropia

Optimização Combinatória

Entropia

Teoria das Probabilidades Estatística

Cadeias de Markov Têmpera Controlada pela Entropia

Processos Estocásticos

Simulação da Têmpera Algoritmo de Metropolis

Autómatos Estocásticos

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de

Modelos Formais para Metaheurísticas: Precisam-se!

O Problema do Caixeiro Viajante Seminário do CEMPA - Dep. de