Comportamento Exploratório do Turista e Problemas de Otimização

Alexandre Souto Martinez

Departamento de Física e Matemática (DFM)Faculdade de Filosofia, Ciências e Letras de Ribeirão Preto (FFCLRP)

Universidade de São Paulo (USP)

Introdução I Meios desordenados

Suporte para a dinâmica Mapa com cidades distribuídas ao acaso

Dinâmica: Regra de Movimentação

Propagação X LocalizaçãoTeoria de Laços nas Trajetórias

Transporte ciclos

Introdução II(raras)

FundamentosX AplicaçõesMecanismos Básicos: física,Sistemas Dinâmicos, lingüística (variáveis qualitativas), Processos Estocásticos economia e

estatística

(poucos e longos cálculos) (demoradas simulações) Teoria X Experimentos

Teoria de Transporte, Simulações Numéricas (M.Carlo)Fórmula de Cox, Técnicas de ClusteringDiagramas de “Kinouchi” Caminhadas de Macacos (in situ)

Meios Desordenados Simetria de translação de um meio homogêneo é quebrada

devido a flutuação de alguma grandeza característica: impureza em metais, variações abruptas do índice refração etc.

A simetria de translação é re-obtida quando considera-se grandezas médias sobre as realizações da desordem (localizada)

Equação de Boltzmann: Difusão etc.

Processo Espacial de Poisson Rd

P(V) dV = exp(-V) dV

V = Ad Rd (hiperesfera)

Ad = d/2 / (d/2+1)

A1 = 2, A2 = , A3 = 4/3, etc.

Meios Difusivos

n

dvD

trDtrt

1

,cos1

,

),(),(

*

*

2

Objetivo: determinar a constante de difusão e resolver a equação de difusão sob determinadas condições de contorno.

Problema de espalhamento múltiplo é resolvido conhecendo apenas as características de um único espalhamento.

choque de seção : localizada desordem de densidade :

médio caminho livre :toespalhamen do aanisotropi defator : cos

e transportde médio caminho livre :

onda da energia de propagação de elocidade v:sistema do lidadedimensiona :

instante no ]d,[ intervalo no volumede unidadepor partículas de número :),(),(

*

2

n

vd

trrr|tr|tr

Problema de Milne

L

Comprimento da Onda Incidente = Espessura da Placa = L

Feix

e Re

fletid

oDi

fuso

Feixe TransmitidoCoerente

Feixe TransmitidoDifuso

Feix

e In

ciden

te

a

l

Caminhada do Turista:Modelo Determinista I

Gere com pdf uniforme as coordenadas de N cidades nas arestas unitárias de um hipercubo de dimensão d matriz de distâncias tabela de vizinhança (grafo do turista)

Em uma dada cidade, vá para a cidade mais próxima que não tenha sido visitada nos últimos passos

Caminhada do Turista:Modelo Determinista II

De uma cidade, vá para a cidade mais próxima que não tenha sido visitada nos últimos passos

Número de arcos emergentes: (auto ref.) G1 G2

grafo do turista para = 2 e caminhada para = 1

Caminhada do Turista:Modelo Determinista III

Trajetória = Transiente + Ciclo-p Distribuição Conjunta: S,d

(N)(t,p) Número de cidades visitadas Prob. de que uma cidade pertença ao ciclo p: P,d

(A)(p)

Caso Trivial ( = 0): S,d

(N)(t,p) = t,0 p,1 e

P,d(A)(1) = 1

Caminhada do Turista:Modelo Determinista IV

Caso sem Memória ( = 1): N >> 1 (limite termodinâmico)

visitadascidades de número : gama função :(z)

)()()1( )(

anormalizad incompleta beta função :),(

1 , 21

21,

21

com 1

1)2(

)(

1

11

,1

41

)(,1

2,,1 atratores) são 2-(ciclo

pt

IptItItS

baI

dII

IP

pP

d

ddd

z

d

d

Ad

pd

Caminhada do Turista:Modelo Determinista V

Modelos de Campo Médio:

ptnNptN

NptS

e

ptNrm

]1)([

)(),()(,0

)!2(1)(

2/)1(2/)3(1

)()(

)(,1

2)(

,1

)(,1

tttS

kNkN

tNtN

tStS

rl

t

krl

Nrl

1,E-09

1,E-08

1,E-07

1,E-06

1,E-05

1,E-04

1,E-03

1,E-02

1,E-01

1,E+000 1 2 3 4 5 6 7 8 9 10

)()(,1 tS Nrl

d = 1, 2, 3, 5, N = 500

t

0,0E+00

4,0E-03

8,0E-03

1,2E-02

1,6E-02

2,0E-02

0 100 200 300 400 500

en

)()(,0 eNrm nS N = 1000,

2000, 4000, 8000, 16000, 32000

Modelo de Distâncias Aleatórias ( = 1)

Modelo de Mapeamento Aleatório ( = 0)

Caminhada do Turista:Modelo Determinista VI

Memória ( > 1): Caminhadas parcialmente auto-repulsivas na janela = – 1

• Período mínimo: p< = + 1 = + 2.• d = 1 & = 2 períodos ímpares > 3 & p = 6 são proibidos.

= 2p = 3

= 3p = 4

= 2p = 8

= 2p = 10

= 3p = 11

Caminhada do Turista:Modelo Determinista VII

Memória ( = 2): Caminhadas parcialmente auto-repulsivas na janela = – 1

d = 1,2,4,8,16,32 & 64

)(exp)( tctP

d = 1,2,4,8,16,32 & 64

)(exp)()(

0

pppCpP

Caminhada do Turista:Modelo Determinista VIII

Memória ( > 1): = – 1 Colapso de dados não funciona para d = 1

d = 1

=1,3 & 6

)()/( 2, pPpG

d = 2

=1,2,4 & 10

2

minpp 60

)(exp)()(

0

pppCpP

Caminhada do Turista:Aplicação: Tesauro

Modelo de Análise Semântica (d = 300) não foi validado, mas o modelo de mundo pequeno foi.

= 0

d = 2extrapolação

Sem memória = 1:

1) Link – connection – link2) Translation – conversion – change – alter – change3) Constitution – establishment – organization –

association – friendship – companionship – company – corporation – business – commerce – trade – deal – contract – agreement – accord – agreement

= 1Mapa aleatório

d = 2

Com memória = 2:

1) Translation – conversion – change – alter – modify – adapt – become accostumed – get used to – get into the habit of – accept – believe – consider – think – believe

exp[- E(Dij)] Wij () = ---------------- Zi

Zi = j

N-1 exp[- E(Dij)] Normalização

E(Dij) função custo arbitrária T = -1 temperatura formal Dij = N1/d[ k

d(xi(k)–xj

(k) )2]1/2

N # de cidades d dimensionalidade

Caminhada do Turista:Modelo Estocástico IX

N1/dDij

i

j

T -> 0 modelo determinista T -> Pulos isotrópicos

Caminhada do Turista:Modelo Estocástico X

N1/dDij

i

j

qp

= 0 Parâmetro de ordem: <tr> Tempo médio de residência

Função Custo: E(D) = D

Possibilidades: < d: <tr> sempre finito > d: <tr> sempre diverge = d: <tr> 1/ (1- / Ad )

Transição vítrea como nos modelos de armadilha de Bouchaud

Caminhada do Turista:Modelo Estocástico XI

= 0

vaziaesferamaior da diâmetro :)12/(

/11)(

1)()1()(

2/

)()/1(

1

/)1(1

/

c

d

d

d

DVA

AN

A

r

Dd

A

Aet

etet

cdd

d

d

= 1 física parecida, mas cálculos muito mais difíceis ...

qp

Caminhada do Turista:Modelo Estocástico XI = 1

d=1 N=100, 200, 400 & 800 d=2 N=200, 400, 800 & 1600

• <R()> # médio de sítios visitados/N. • S2

R() variância de R().• PNN() taxa de visitação ao viz. + prox.

qp

Agradecimento Colaboradores:

Osame Kinouchi, Gilson Francisco Lima, Sebastian Risau-Gusman, Rodrigo Silva González, Gisele M. Lourenço, Cesar Augusto Sangaleti Terçariol, Wilnice Tavares Reis Oliveira, Mônica Campiteli Felipe de Mouta Kiiper

Resultados Determinista:

Possibilidade de boa exploração do meio mesmo com pouca memória ( << N) utilizando-se somente informação local

Estocástico:

Melhor compromisso entre exploração e comprimento de caminhadas se dá na temperatura de transição vítrea.

Trabalhos Futuros Determinista:

Resultados analíticos para > 1 ? Mudança drástica de comportamento em função de ? Melhores simulações numéricas ? Associação com uma coeficiente de sub-difusão ?

Estocástico:

Associação com um coeficiente de (sub-)difusão ? Resultados numéricos para > 1 ? Uso em teoria da otimização e como ?