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 Teoria de Transporte X Localização Laços nas Trajetórias ciclos Introdução II Fundamentos Mecanismos Básicos: Sistemas Dinâmicos, Processos Estocásticos (poucos e longos cálculos) Teoria Teoria de Transporte, Fórmula de Cox, Diagramas de “Kinouchi” X X (raras) Aplicações física, lingüística (variáveis qualitativas), economia e estatística (demoradas simulações) Experimentos Simulações Numéricas (M.Carlo) Técnicas de Clustering 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) Processo Espacial de Poisson Rd Equação de Boltzmann: Difusão etc. 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 Objetivo: determinar a constante de difusão e resolver a equação de difusão sob determinadas condições de contorno. 2 t (r , t ) D (r , t ) * v D , d , 1 cos 1 n * (r , t ) | (r , t )|2 : númerode partículaspor unidade de volume d: v: no intervalo[r , r dr ] no instantet dimensionalidade do sistema velocidade de propagaçãode energia da onda * : livrecaminhomédio de transporte cos : fatorde anisotropia do espalhamento : livrecaminhomédio n: densidade de desordem localizada : seção de choque Problema de espalhamento múltiplo é resolvido conhecendo apenas as características de um único espalhamento. Problema de Milne Feixe Refletido Difuso Comprimento da Onda Incidente = l Espessura da Placa = L Feixe Incidente Feixe Transmitido Coerente a Feixe Transmitido Difuso l l 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 m 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 m passos grafo do turista para m = 2 e caminhada para m=1 Número de arcos emergentes: m 1 (auto ref.) G1 G2 Caminhada do Turista: Modelo Determinista III Trajetória = Transiente + Ciclo-p Distribuição Conjunta: Sm,d(N)(t,p) Número de cidades visitadas Prob. de que uma cidade pertença ao ciclo p: Pm,d(A)(p) Caso Trivial (m = 0): S0,d(N)(t,p) = dt,0 dp,1 e P0,d(A)(1) = 1 Caminhada do Turista: Modelo Determinista IV Caso sem Memória (m = 1): N >> 1 P1,d ( p) d p , 2 (ciclo- 2 são atratores) ( A) 1, d P 1 (2) 1 Id com 1 d 1 1 Id I 1 , , 1 4 2 2 2 I z (a, b) : função beta incomplet anormalizada (1 I d1 )(t I d1 ) S1,d (t ) (t p I d1 ) (z) : função gama t p : númerode cidades visitadas (limite termodinâmico) Caminhada do Turista: Modelo Determinista V Modelos de Campo Médio: 1,E+00 0 1 2 3 4 5 6 7 8 9 10 2,0E-02 t 1,E-01 S0(,Nrm) (ne ) 1,6E-02 1,E-02 1,E-03 1,E-04 1,E-05 1,E-06 1,E-07 1,E-08 1,2E-02 S1(,Nrl ) (t ) N = 500 d = 1, 2, 3, 5, 8,0E-03 4,0E-03 0,0E+00 0 100 t N t 1 N k () S1,rl (t ) N (t 3) / 2 k 2 N (k 1) / 2 S1(,rl ) (t ) t 1 (t 2)! Modelo de Distâncias Aleatórias (m = 1) 200 300 400 500 ne 1,E-09 S1(,Nrl ) (t ) N = 1000, 2000, 4000, 8000, 16000, 32000 S0( ,Nrm) (t , p) ( N ) [ N (t p) 1]N t p ne t p Modelo de Mapeamento Aleatório (m = 0) Caminhada do Turista: Modelo Determinista VI Memória (m > 1): Caminhadas parcialmente autorepulsivas na janela t = m – 1 m=2 p=3 m=3 p=4 m=2 p=8 m=2 p = 10 m=3 p = 11 • • Período mínimo: p< = m + 1 = t + 2. d = 1 & m = 2 períodos ímpares > 3 & p = 6 são proibidos. Caminhada do Turista: Modelo Determinista VII Memória (m = 2): Caminhadas parcialmente auto-repulsivas na janela t = m – 1 d = 1,2,4,8,16,32 & 64 t Pt (t ) c exp (t ) d = 1,2,4,8,16,32 & 64 p Pt ( p) C (t ) p exp p ( t ) 0 Caminhada do Turista: Modelo Determinista VIII Memória (m > 1): Colapso de dados não funciona para d = 1 t=1,3 & 6 t=m–1 G( p / t ) t Pm ,2 ( p) t=1,2,4 & 10 2 d=2 d=1 p Pt ( p) C (t ) p exp p (t ) p0 6 pmin 0 Caminhada do Turista: Aplicação: Tesauro Sem memória m = 1: 1)Link – connection – link 2)Translation – conversion – change – alter – change 3)Constitution – establishment – organization – association – friendship – companionship – company – corporation – business – commerce – trade – deal – contract – agreement – accord – agreement Com memória m = 2: 1) Translation – conversion – change – alter – modify – adapt – become accostumed – get used to – get into the habit of – accept – believe – consider – think – believe t=0 d=2 extrapolação t=1 Mapa aleatório d=2 Modelo de Análise Semântica (d = 300) não foi validado, mas o modelo de mundo pequeno foi. Caminhada do Turista: Modelo Estocástico IX Wij exp[- E(Dij)] () = ---------------Zi N-1 Zi = j T -> 0 exp[- E(Dij)] j N1/dDij i Normalização função custo arbitrária temperatura formal E(Dij) T = -1 d 1/2 1/d Dij = N [ k (xi(k)–xj (k) )2] N # de cidades d dimensionalidade modelo determinista T -> Pulos isotrópicos Caminhada do Turista: Modelo Estocástico X Parâmetro de ordem: m = 0 <tr> Tempo médio de residência j N1/dDij i E(D) = Dl Possibilidades: l < d: l > d: l = d: p q Função Custo: <tr> sempre finito <tr> sempre diverge <tr> 1/ (1- / Ad ) Transição vítrea como nos modelos de armadilha de Bouchaud Caminhada do Turista: Modelo Estocástico XI p q m = 0 (1 e / Ad ) t1 ( ) t r ( ) 1 e ( N 1) / Ad 1 e (1 / Ad )Vd ( Dc ) t1 ( ) 1 / Ad Ad d /2 (d / 2 1) Dc : diâmetroda maior esfera vazia m = 1 física parecida, mas cálculos muito mais difíceis ... Caminhada do Turista: Modelo Estocástico XI m = 1 d=1 N=100, 200, 400 & 800 p q • <R()> # médio de sítios visitados/N. • S2R() variância de R(). • PNN() taxa de visitação ao viz. + prox. d=2 N=200, 400, 800 & 1600 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 (m << 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 m > 1 ? Mudança drástica de comportamento em função de m ? 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 m > 1 ? Uso em teoria da otimização e como ?