An Efficient Approach for Steiner Tree Problem by Genetic Algorithm

International Journal of Computer Science and Engineering

© 2015 by SSRG - IJCSE Journal

Volume 2 Issue 5

Year of Publication : 2015

Authors : Ankit Anand, Shruti, Kunwar Ambarish Singh

10.14445/23488387/IJCSE-V2I5P133

How to Cite?

Ankit Anand, Shruti, Kunwar Ambarish Singh, "An Efficient Approach for Steiner Tree Problem by Genetic Algorithm," SSRG International Journal of Computer Science and Engineering , vol. 2,  no. 5, pp. 6-10 , 2015. Crossref, https://doi.org/10.14445/23488387/IJCSE-V2I5P133

Abstract:

We have applied a genetic algorithm (GA) to solve the Steiner Minimal Tree problem in graphs. In this a simple bit string representation is used, where a 1 or 0 corresponds to whether or not a node is included in the solution tree. The standard genetic operators-selection, crossover and mutation-are applied to both random and seeded initial populations of representations. Various parameters within the algorithm have to be set and we discuss how and why we have selected the values used. A standard set of graph problems used extensively in the comparison of Steiner tree algorithms has been solved using our resulting algorithm. We report our results (which are encouragingly good) and draw conclusions the proposed algorithm has several advantages. One advantage is that, it guarantees convergence to an optimal solution with probability one. And another advantage is that, not only the resultant solutions all are feasible, the solution quality is also much higher than that obtained by the other methods (immensely, in almost every case in our simulations, the algorithm can find the optimal solution of the problem).

Keywords:

Algorithm, Crossover, Genetic,Graph, Mutation, Steiner Tree...

References:

[1] Goldberg, G.A., Genetic Algorithms in Search, Optimization and Machine Learning, Pearson Education, Inc., 2002. 
[2] Mazumder, P. and Rudnick, E.M., Genetic Algorithms for VLSI Design, Layout and Test Automation, Prentice Hall, 1999. 
[3] S. L. HAKIMI (1971) Steiner's problem in graphs and its implications. Networks 1, 113-133. 
[4] M. L. SHORE, L. R. FOULDSan d P. B. GIBBONS,An algorithm for the Steiner problem in graphs. Networks 12, 323- 333. ( 1982) 
[5] Deb.K. and Srivastava S, A Genetic Algorithm Based Augmented Lagrangian Method for Accurate, Fast and Reliable Constrained Optimization. KanGAL Report No.2011012. (August, 2011). 
[6] Pettersson, F., Saxen, H. and Deb K, Genetic algorthm based multicriteria optimization of ironmaking in the blast furnace. Journal of Materials and Manufacturing Processes, 24, 1–7. (2009).