Amostragem por Importância para Estimar Valores Esperados: uma Abordagem com Heurísticas para Problemas Intervalares NP-Difíceis
DOI:
https://doi.org/10.5540/tema.2005.06.02.0261Abstract
O presente trabalho tem como objetivo mostrar a possibilidade de aproximar um problema NP-Difícil da computação intervalar, através do uso de heurísticas com ênfase em algoritmos baseados no Método de Monte Carlo. A fim de apresentar heurísticas para o problema genérico de estimar numericamente, dada uma precisão ", o valor esperado de uma função racional f(x1, ..., xn) com (x1, ..., xn) 2 Qn k=1 ×Ik escolhidos de acordo com uma função de densidade de probabilidade P(x1, ..., xn) conjunta, com Ik sendo intervalos, mostramos para o particular caso de um grafo regular de grau 2, cujos vértices podem assumir somente dois valores −1 e +1, o que restringe os intervalos a serem todos discretos Ik = [−1, 1] \ Z, k = 1, ..., n. Verificamos que o problema do valor esperado entre os pares de vértices adjacentes, tivera seu custo reduzido de O(2n) operações, através do cálculo exato, para O(Nsample) que seria a complexidade encontrada quando aproximamos o resultado obtido pela Heurística, onde Nsample é o número de amostras de configurações escolhidas através do processo de amostragem por importância no contexto do algoritmo de Metrópolis.References
[1] R.E. Campello e N. Maculan, “Algoritmos e Heurísticas: desenvolvimento e avaliação de performance”, EDUFF, Rio de Janeiro, 1994.
M.E. Garey e D.S. Johnson, “Computers and intractability: a guide to the theory of NP-completeness”, Freeman, San Francisco, 1979.
V. Kreinovich, A. Lakeyev, J. Rohn e P. Kahl, “Computational Complexity and Feasibility of Data Processing and Interval Computations”, Kluwer Academic Publishers, Dordrecht, 1998.
V. Kreinovich, Probabilities, intervals, what next? Optimization problems related to extension of interval computations to situations with partial information about probabilities, Global Optimization, 29, No. 3 (2003), 265-280.
N. Metropolis, W. A. Rosenbluth, M. N. Rosenbluth, A. H. Teller e E. Teller, Equation of state calculation by fast computer machines, J. Chem. Phys. 1, No. 6 (1953).
R.E. Moore, “Methods and Applications of Interval Analysis”, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1979.
R.M. Neal, “Probabilistic Inference using Markov Chain Monte Carlo Methods”, Thecnical Report, Departament of Computer Science, University of Toronto, 1993.
W.H. Press, S.A. Tenkolsky, W.T. Vetterling e B.P. Flannery, “Numerical Recipes in Fortran 77”, 2 ed., Cambridge University Press, 1994.
H. Rathschek e J. Rokne, “New Computer Methods for Global Optimization”, Ellis Horwood Limited, Great Britain, 1988.
L.V. Toscani e P.A.S. Veloso, “Complexidade de Algoritmos: análise, projetos e métodos”, Sagra Luzzato, Instituto de Informática da UFRGS, Porto Alegre, 2001.
B. Traylor e V. Kreinovich, A bright side of NP-hardness of interval computations: interval heuristics applied to NP-problems, Reliable Computing, 3 (1995), 343-359.
S.R.A. Salinas, “Introdução a Física Estatística”, Edusp, 1997.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.