Evaluating simple metaheuristics for the generalized steiner problem

Authors

  • Sergio Nesmachnow Centro de Cálculo, Instituto de Computación, Facultad de Ingeniería, Universidad de la República Montevideo, Uruguay.

Keywords:

Metaheuristics, Generalized Steiner Problem, Reliable network design

Abstract

This article presents the empirical evaluation of several simple metaheuristics applied to solve the Generalized Steiner Problem (GSP). This problem models the design of high-reliability communication networks, demanding a variable number of independent paths linking each pair of terminal nodes. GSP solutions are built using intermediate nodes for guaranteeing path redundancy, while trying to minimize the design total cost. The GSP is a NP-hard problem, and few algorithms have been proposed to solve it. In this work, we present the resolution of several GSP instances whose optimal solutions are known, using metaheuristic techniques. The comparative analysis shows promising results for some of the studied techniques

Downloads

Download data is not yet available.

References

[1] E. Alba, C. Cotta. “Optimización en entornos geográficamente distribuidos. Proyecto MALLBA”, Congreso Español de Algoritmos Evolutivos y Bioinspirados, pp. 38–45, 2002.
[2] M. Aroztegui, S. Arraga, S. Nesmachnow, “Resolución del Problema de Steiner Generalizado utilizando un algoritmo genético paralelo”, Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados, pp. 387-394, 2003.
[3] D. Corne, M. Oates, G. Smith, Telecommunications optimization, Wiley, 2000.
[4] L. Davis. Handbook of genetic algorithms, Van Nostrand Reinhold, New York, 1991.
[5] H. Esbensen, “Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm”, Networks 26, pp. 173-185, 1995.
[6] L. Eshelman, “The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination”, Foundations of Genetic Algorithms, pp. 265-283, 1991.
[7] L. Ford, D. Fulkerson, Flows in Networks. Princeton University Press, Princeton, 1962.
[8] D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
[9] V. Kahn, P. Crescenzi, A compendium of NP optimization problems, online at http://www.nada.kth.se/theory/problemlist.html, consulted November 2005.
[10] R. Karp, “Reducibility among combinatorial problems”, Complexity of Computer Communications, pp. 85-103, 1972.
[11] S. Kirkpatrik, C. Gelatt, M. Vecchi, “Optimization by simulated annealing”, Science, pp. 671–680, 1983.
[12] S. Nesmachnow, H. Cancela, E. Alba. “Técnicas evolutivas aplicadas al diseño de redes de comunicaciones confiables”, Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados, pp. 388-395, 2004.
[13] S. Nesmachnow, “Algoritmos genéticos paralelos y su aplicación al diseño de redes de comunicaciones confiables”, Master Thesis, PEDECIBA Informática, Universidad de la República, Uruguay, 2004.
[14] W. Pedrycz, A. Vasilakos, Computational intelligence in telecommunications networks, CRC Press, 2001.
[15] N. Mladenovic, P. Hansen, “Variable Neighborhood Search: principals and Applications”, European Journal Operational Research, 130, pp. 449-467, 1999.

Downloads

Published

2005-12-01

How to Cite

Nesmachnow, S. (2005). Evaluating simple metaheuristics for the generalized steiner problem. Journal of Computer Science and Technology, 5(04), p. 285–291. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/849

Issue

Section

Original Articles