The week's pick
Reseach Article
A Hybrid Algorithm for Solving Steiner Tree Problem
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 41 - Number 5 |
| Year of Publication: 2012 |
| Authors: Samira Noferesti, Hamed Shah-hosseini |
10.5120/5536-7584
|
Samira Noferesti, Hamed Shah-hosseini . A Hybrid Algorithm for Solving Steiner Tree Problem. International Journal of Computer Applications. 41, 5 ( March 2012), 14-20. DOI=10.5120/5536-7584
Abstract
In this paper, a hybrid algorithm based on modified intelligent water drops algorithm and learning automata for solving Steiner tree problem is proposed. Since the Steiner tree problem is NP-hard, the aim of this paper is to design an algorithm to construct high quality Steiner trees in a short time which are suitable for real time multicast routing in networks. The global search and fast convergence ability of the intelligent water drops algorithm make it efficient to the problem. To achieve better results, we used learning automata for adjusting IWD parameters. IWD has several parameters. The appropriate selections of these parameters have large effects on the performance and convergence of the algorithm. Experimental results on the OR-library test cases show that the proposed algorithm outperforms traditional heuristic algorithms and other iteration based algorithms with faster convergence speed.
References
- Li, K. , Shen, C. , Jaikaeo, C. and Sridhara, V. 2008. Ant-based Distributed Constrained Steiner Tree Algorithm for Jointly Conserving Energy and Bounding Delay in Ad hoc Multicast Routing, ACM Transactions on Autonomous and Adaptive Systems, 3, 1.
- Hu, X. , Zhang, J. and Zhang, L. 2009. Swarm Intelligence Inspired Multicast Routing: An Ant Colony Optimization Approach, EvoWorkshops, 51-60.
- Shah-Hosseini, H. 2007. Problem Solving by Intelligent Water Drops, in Proceedings of IEEE Congress on Evolutionary Computation, Singapore, 3226-3231.
- Shah-Hosseini, H. 2009. The Intelligent Water Drops Algorithm: A Nature-Inspired Swarm-Based Optimization Algorithm, International Journal of Bio-Inspired Computation, 1 , 71-79.
- Shah-Hosseini, H. 2009. Optimization with the Nature-Inspired Intelligent Water Drops Algorithm, In Santos, W. P. D. ed. Evolutionary computation. Tech, Vienna, Austria, 297-320.
- Shah-Hosseini, H. 2011. An Intelligent Water Drop Algorithm for Solving Economic Load Dispatch Problem, International Journal of Electrical and Electronics Engineering, 5, 1.
- Hougardy, S. , and Promel, H. J. 1999. A 1. 598 Approximation Algorithm for the Steiner Problem in Graphs, ACM-SIAM Symposium on Discrete Algorithm, USA, 448-453, 1999.
- Laarhoven, V. and William, J. 2010. Exact and Heuristic Algorithms for the Euclidean Steiner Tree Problem, PhD thesis. , University of Iowa.
- Cormen, T. H. , Leiserson, C. E. , Rivest, R. L. , and Stein, C. (2001), Introduction to Algorithms, 2nd edn. MIT Press, Cambridge.
- Karp, R. M. 1972. Reducibility among combinatorial problems, In Complexity of Computer Computation, Plenum Press, New York, 8-103.
- Garey, M. R. , Graham, R. L. and Johnson, D. S. 1977. The Complexity of Computing Steiner Minimal Trees, SIAM Journal of Applied Mathematics, 32, 4, 835-859.
- Garey, M. R. and Johnson, D. S. 1977. The Rectilinear Steiner Tree Problem is NP-complete, SIAM Journal on Applied Mathematics, 32, 4, 826-834.
- Esbensen, H. 1995. Computing Near-Optimal Solutions to the Steiner Problem in a Graph Using a Genetic Algorithm, Networks, 26, 173-185.
- Robins, G. and Zelikovski, A. 2000. Improved Steiner Tree Approximation in Graphs, In Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 770-779, 2000.
- Diane, M. , and Plesnik, J. 1999. Three New Heuristics for the Steiner Problem in Graphs, Acta Math. , LX, 105-121.
- Rayward-smith, V. J. , and Clare, A. 1986. On Finding Steiner vertices, Networks, 16, 283-294.
- Kapsalis, A. , Rayward-smith, V. J. , and Smith, J. D. 1993. Solving the Graphical Steiner Tree Problem Using Genetic Algorithms, Journal of the Operational Research Society, 44 , 397-406.
- Ding, S. , and Ishii, N. 1995. An Online Genetic Algorithm for Dynamic Steiner Tree Problem, Symposium on Computational Geometry, 337-343.
- Zhan, Z. , and Zhang, J. 2009. Discrete Particle Swarm Optimization for Multiple Destination Routing Problems, In Proceedings of EvoWorkshops, 117-122.
- Ma, X. and Liu, Q. 2010. A Particle Swarm Optimization for Steiner Tree Problem, In Sixth International Conference on Natural Computation, ICNC 2010, 2561-2565.
- Tashakori, M. , Adibi, P. , Jahanian, A. and Norallah, A. (2004), 'Solving Dynamic Steiner Tree Problem by Using Ant Colony System', in 9th Annual Conference of Computer Society Of Iran, Tehran, Iran.
- Meybodi, M. R. , and Beigy, H. 2002. A Note on Learning Automata Based Schemes for Adaptation of BP Parameters, Journal of Neurocomputing, 48, 957-974.
- Noferesti, S. , and Rajaei, M. 2011. A Hybrid Algorithm Based on Ant Colony System and Learning Automata for Solving Steiner Tree Problem, International Journal of Applied Mathematics and Statistics, 22.
- Beasley, J. E. 1990. OR-Library: Distributing Test Problems by Electronic Mail, Operational Research. SOC. , 41 ,11, 1096-1072.
- Noferesti, S. , and Rajayi, M. 2009. Solving Steiner Tree Problem by Using Learning Automata, Computational Intelligence and Software Engineering, CiSE 2009, 1-4.
Index Terms
Keywords