A Distributed Architecture Supporting Heuristic and Metaheuristic Optimization Methods
Resumo
This paper presents a distributed software architecture that allows the cooperation among research institutions in the field of Operations Research. It has as main aims to share existing algorithms for optimization problems, to allow the easy testing of these algorithms with existing instances, and to share computational power among the cooperating institutions. This is achieved respecting the autonomy and heterogeneity of the cooperating institutions. The five functional blocks that build the architecture are discussed here and also a study case of a Parallel Memetic Algorithm to solve the Traveling Salesman Problem running on this environment is analysed.
Palavras-chave:
Optimization Algorithms, Memetic Algorithm, Master-Slave, Distributed Environment
Referências
AMIN, S. Simulated Jumping. Operations Research, EUA, p. 23-38, 1999.
BURION, Luciana Salete. Algoritmo Memético para o Problema do Caixeiro Viajante Assimétrico como parte de um Framework para Algoritmos Evolutivos. Master Thesis, Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação, São Paulo, Brazil, 2000.
CANTÚ-PAZ, E. A Survey of Parallel Genetic Algorilhms. Calculateurs Paralleles, Reseaux et Systems Repartics. Paris, v. 10, n. 2. p. 141-171, 1998.
CASANOVA, H.; DONGARRA, J. NetSolve: A Network server for solving computacional science problems. Technical Report CS-95-313, University of Tennessee, Knoxville, Tennessee, 1995.
CZYZYK, J.; MESNIER, M. P.; MORE, J. J. The Network-Enabled Optimization System (NEOS) Server, Preprint MCS-P615-1096, Argonne National Laboratory, Argonne, lllinois, 1997.
FEO, T.; REZENDE. A greed randomized adaptative search procedure for maximum independent set. Operations Research, EUA, ed.42,p.860--879, 1994.
FIECHTER, C. N. A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems. Discrete Applied Malhematics, EUA, p. 243-267, 1994.
GLOBUS RESOURCE MANAGER SPECIFICATION. Globus working note, available at http://www.globus.org, 1997.
GLOVER, F. Heuristics for Integer Programming Using Surrogate Constraints. Decision Sciences, EUA, ed. 8, p. 156-166, 1977.
GLOVER, F.; LAGUNA, M. Tabu Search. Modem Heuristic Techniques, Blackwell Scientific Publications, Oxford, EUA, p. 70-150, 1993.
GOLDBERG, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, EUA, 1989.
KIRKPATRICK, S.; GELATT, C. D.; VECCHI, M. P. Optimization by Simulated Annealing. Science, EUA, ed. 220, p. 671-679, 1983.
LITZKOW, M. J.; LIVNY, M.; MUTKA, M. W. Condor-A hunter for idle workstations. In Proceedings of the 8th International Conference on Distributed Computing Systems, Whashington, District of Columbia, IEEE Computer Society Press, p. 108-111, 1988
METANEOS: METACOMPUTING ENVIRONMENTS FOR OPTIMIZATION, propose available at http://www.mcs.anl.gov/metaneos, 1998.
MOSCATO, Pablo. Memetic Algorithms: A Short Introduction. New Ideas in Optimization, McGraw-Hill, Washington, EUA, cap. 2, 1999.
NEWELL, A.; SHAW, J. C.; SIMON, H. A. Empirical explorations with the logic theory machine. Western Joint Computer Conference, EUA, p. 218-239, 1958.
OMG-Document. Common Object Request Broker Architecture, http://www.omg.org, 2001.
OSMAN, lbrahim. Heuristics for Combinatorial Optimization Problems: Developments and New Directions. In Proceedings of the first seminar on lnformation Technology and Applications, Marfield Conference Center, EUA, Sep. 1991.
POTVIN, J. Y. The Traveling Salesman Problem: A Neural Network Perspective. ORSA Journal on Computing, EUA, ed. 5, p. 338-348, 1993.
RAYWARD-SMITH, V. J.; OSMAN, I. H.; REEVES, C. R.; SMITH, G. D. Genetic Algorithms in Search, optimization and Machine Learning. Addison-Wesley, EUA, 1989.
STÜTZLE, T.; DORJGO, M. ACO Algorithms for the Traveling Salesman Problem. Evolutionary Algorithms in Engineering and Computer Science: Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications, EUA, 1999.
VINOSKJ, S. CORBA: Integrating Diverse Applications Within Distributed Heterogeneous Environments, IEEE Communications Magazine, 1997.
VINOSKJ, S. New Features for CORBA 3.0, Communications of the ACM, vol 41, no 10, October 1998.
BURION, Luciana Salete. Algoritmo Memético para o Problema do Caixeiro Viajante Assimétrico como parte de um Framework para Algoritmos Evolutivos. Master Thesis, Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação, São Paulo, Brazil, 2000.
CANTÚ-PAZ, E. A Survey of Parallel Genetic Algorilhms. Calculateurs Paralleles, Reseaux et Systems Repartics. Paris, v. 10, n. 2. p. 141-171, 1998.
CASANOVA, H.; DONGARRA, J. NetSolve: A Network server for solving computacional science problems. Technical Report CS-95-313, University of Tennessee, Knoxville, Tennessee, 1995.
CZYZYK, J.; MESNIER, M. P.; MORE, J. J. The Network-Enabled Optimization System (NEOS) Server, Preprint MCS-P615-1096, Argonne National Laboratory, Argonne, lllinois, 1997.
FEO, T.; REZENDE. A greed randomized adaptative search procedure for maximum independent set. Operations Research, EUA, ed.42,p.860--879, 1994.
FIECHTER, C. N. A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems. Discrete Applied Malhematics, EUA, p. 243-267, 1994.
GLOBUS RESOURCE MANAGER SPECIFICATION. Globus working note, available at http://www.globus.org, 1997.
GLOVER, F. Heuristics for Integer Programming Using Surrogate Constraints. Decision Sciences, EUA, ed. 8, p. 156-166, 1977.
GLOVER, F.; LAGUNA, M. Tabu Search. Modem Heuristic Techniques, Blackwell Scientific Publications, Oxford, EUA, p. 70-150, 1993.
GOLDBERG, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, EUA, 1989.
KIRKPATRICK, S.; GELATT, C. D.; VECCHI, M. P. Optimization by Simulated Annealing. Science, EUA, ed. 220, p. 671-679, 1983.
LITZKOW, M. J.; LIVNY, M.; MUTKA, M. W. Condor-A hunter for idle workstations. In Proceedings of the 8th International Conference on Distributed Computing Systems, Whashington, District of Columbia, IEEE Computer Society Press, p. 108-111, 1988
METANEOS: METACOMPUTING ENVIRONMENTS FOR OPTIMIZATION, propose available at http://www.mcs.anl.gov/metaneos, 1998.
MOSCATO, Pablo. Memetic Algorithms: A Short Introduction. New Ideas in Optimization, McGraw-Hill, Washington, EUA, cap. 2, 1999.
NEWELL, A.; SHAW, J. C.; SIMON, H. A. Empirical explorations with the logic theory machine. Western Joint Computer Conference, EUA, p. 218-239, 1958.
OMG-Document. Common Object Request Broker Architecture, http://www.omg.org, 2001.
OSMAN, lbrahim. Heuristics for Combinatorial Optimization Problems: Developments and New Directions. In Proceedings of the first seminar on lnformation Technology and Applications, Marfield Conference Center, EUA, Sep. 1991.
POTVIN, J. Y. The Traveling Salesman Problem: A Neural Network Perspective. ORSA Journal on Computing, EUA, ed. 5, p. 338-348, 1993.
RAYWARD-SMITH, V. J.; OSMAN, I. H.; REEVES, C. R.; SMITH, G. D. Genetic Algorithms in Search, optimization and Machine Learning. Addison-Wesley, EUA, 1989.
STÜTZLE, T.; DORJGO, M. ACO Algorithms for the Traveling Salesman Problem. Evolutionary Algorithms in Engineering and Computer Science: Recent Advances in Genetic Algorithms, Evolution Strategies, Evolutionary Programming, Genetic Programming and Industrial Applications, EUA, 1999.
VINOSKJ, S. CORBA: Integrating Diverse Applications Within Distributed Heterogeneous Environments, IEEE Communications Magazine, 1997.
VINOSKJ, S. New Features for CORBA 3.0, Communications of the ACM, vol 41, no 10, October 1998.
Publicado
10/09/2001
Como Citar
COSTA, Celso M. da; DOTTI, Fernado L.; MATHIAS, Eder N.; MÜLLER, Felipe M..
A Distributed Architecture Supporting Heuristic and Metaheuristic Optimization Methods. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 13. , 2001, Pirenópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2001
.
p. 172-179.
DOI: https://doi.org/10.5753/sbac-pad.2001.22206.
