Uma Forma Distribuída de Busca Estocástica para Otimização Combinatória
Resumo
Este trabalho descreve uma aplicação de processamento distribuído à aproximação da solução de problemas NP-completos em Otimização Combinatória. O método básico utilizado é conhecido como "Simulated Annealing", e consiste em uma busca estocástica inspirada nos princípios da Física Estatística. Para uma vasta classe de problemas, o método pode ser paralelizado, permitindo que a busca possa se realizar sobre um conjunto relativamente grande de variáveis simultaneamente. Este trabalho descreve uma implementação distribuída do método através da associação de um processador dedicado a cada uma das variáveis do problema. Entre os problemas passíveis de paralelização, encontra-se o problema de encontrar-se uma cobertura de vértices de tamanho mínimo em um grafo. A implementação proposta apresenta um grau de concorrência que depende da forma como as diversas variáveis do problema se interrelacionam.
Referências
C. R. Aragon, D. S. Johnson, L. A. McGeoch e C. Schevon, "Optimization by Simulated Annealing: an Experimental Evaluation", Workshop on Statistical Physics in Engineering and Biology (Abril de 1984).
V. C. Barbosa, "Concurrency in Systems with Neighborhood Constraints", Tese de Doutorado, Computer Science Department, University of California, Los Angeles, CA (1986).
C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam (1976).
K. M. Chandy e J. Misra, "The Drinking Philosophers Problem", ACM Transactions on Programming Languages and Systems 6(4), pp. 632-646 (Outubro de 1984).
K.M. Chandy e L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Transactions on Computer Systems 3(1), pp. 63-75 (Fevereiro de 1985).
S. A. Cook, "The Complexity of Theorem-Proving Procedures", pp. 151-158 in Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, OH (Maio de 1971).
E. Felten, S. Karlin e S. W. Otto, "The Traveling Salesman Problem on a Hypercubic, MIMD Computer", pp. 6-10 in Proceedings of the International Conference on Parallel Processing, Chicago, IL (Agosto de 1985).
E. M. Gafni e D. P. Bertsekas, "Distributed Algorithms for Generating Loop-Free. Routes in Networks with Frequently Changing Topology", IEEE Transactions on Communications COM-29(1), pp. 11-18 (Janeiro de 1981).
E. M. Gafni e V. C. Barbosa, "Optimal Snapshots and the Maximum Flow in Precedence Graphs", Proceedings of the Twenty-Fourth Annual Allerton Conference on Communication, Control, and Computing (Outubro de 1986).
M. R. Garey e D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA (1979). )
S. Geman e D. Geman, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images", IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-6(6), pp. 721-741 (Novembro de 1984).
A.V. Goldberg e R. E. Tarjan, "A New Approach to the Maximum Flow Problem", pp. 136-146 in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley, CA (Maio de 1986).
R. M. Karp, "Reducibility among Combinatorial Problems", pp. 85-103 in Complexity of Computer Computations, eds. R. E. Miller e J. W. Thatcher, Plenum Press, New York, NY (1972).
S. Kirkpatrick, C. D. Gelatt e M. P. Vecchi, "Optimization by Simulated Annealing", Science 220(4598), pp. 671-680 (Maio de 1983).
L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM 21(7), pp. 558-565 (Julho de 1978).
D. G. Luenberger, Introduction to Linear and Nonlincar Programming, Addison-Wesley, Reading, MA (1973).
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller e E. Teller, "Equations of State Calculations by Fast Computing Machines", Journal of Chemical Physics 21, pp. 1087-1091 1953).
C. H. Papadimitriou e K. Steiglitz, Combinatorial Optimization, Prentice-Hall, Englewood Cliffs, NJ (1982).
C. L. Seitz, "The Cosmic Cube", Communications of the ACM 28(1), pp. 22-33 (Janeiro de 1985).
F. Spitzer, "Markov Random Fields and Gibbs Ensembles", American Mathematical Monthly 78, pp. 142-154 (1971).
S. Stahl, "n-Tuple Colorings and Associated Graphs", Journal of Combinatorial Theory, Series B 20(2), pp. 185-203 (Abril de 1976).
V. C. Barbosa, "Concurrency in Systems with Neighborhood Constraints", Tese de Doutorado, Computer Science Department, University of California, Los Angeles, CA (1986).
C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam (1976).
K. M. Chandy e J. Misra, "The Drinking Philosophers Problem", ACM Transactions on Programming Languages and Systems 6(4), pp. 632-646 (Outubro de 1984).
K.M. Chandy e L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Transactions on Computer Systems 3(1), pp. 63-75 (Fevereiro de 1985).
S. A. Cook, "The Complexity of Theorem-Proving Procedures", pp. 151-158 in Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, OH (Maio de 1971).
E. Felten, S. Karlin e S. W. Otto, "The Traveling Salesman Problem on a Hypercubic, MIMD Computer", pp. 6-10 in Proceedings of the International Conference on Parallel Processing, Chicago, IL (Agosto de 1985).
E. M. Gafni e D. P. Bertsekas, "Distributed Algorithms for Generating Loop-Free. Routes in Networks with Frequently Changing Topology", IEEE Transactions on Communications COM-29(1), pp. 11-18 (Janeiro de 1981).
E. M. Gafni e V. C. Barbosa, "Optimal Snapshots and the Maximum Flow in Precedence Graphs", Proceedings of the Twenty-Fourth Annual Allerton Conference on Communication, Control, and Computing (Outubro de 1986).
M. R. Garey e D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA (1979). )
S. Geman e D. Geman, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images", IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-6(6), pp. 721-741 (Novembro de 1984).
A.V. Goldberg e R. E. Tarjan, "A New Approach to the Maximum Flow Problem", pp. 136-146 in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley, CA (Maio de 1986).
R. M. Karp, "Reducibility among Combinatorial Problems", pp. 85-103 in Complexity of Computer Computations, eds. R. E. Miller e J. W. Thatcher, Plenum Press, New York, NY (1972).
S. Kirkpatrick, C. D. Gelatt e M. P. Vecchi, "Optimization by Simulated Annealing", Science 220(4598), pp. 671-680 (Maio de 1983).
L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM 21(7), pp. 558-565 (Julho de 1978).
D. G. Luenberger, Introduction to Linear and Nonlincar Programming, Addison-Wesley, Reading, MA (1973).
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller e E. Teller, "Equations of State Calculations by Fast Computing Machines", Journal of Chemical Physics 21, pp. 1087-1091 1953).
C. H. Papadimitriou e K. Steiglitz, Combinatorial Optimization, Prentice-Hall, Englewood Cliffs, NJ (1982).
C. L. Seitz, "The Cosmic Cube", Communications of the ACM 28(1), pp. 22-33 (Janeiro de 1985).
F. Spitzer, "Markov Random Fields and Gibbs Ensembles", American Mathematical Monthly 78, pp. 142-154 (1971).
S. Stahl, "n-Tuple Colorings and Associated Graphs", Journal of Combinatorial Theory, Series B 20(2), pp. 185-203 (Abril de 1976).
Publicado
13/05/1987
Como Citar
BARBOSA, Valmir C..
Uma Forma Distribuída de Busca Estocástica para Otimização Combinatória. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 1. , 1987, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1987
.
p. 331-342.
DOI: https://doi.org/10.5753/sbac-pad.1987.23590.
