Abstract Views :278 |
PDF Views:0
Authors
Affiliations
1 Department of Master of Computer Applications, M.S. Engineering College, Bangalore, IN
2 Faculty of Computer Studies
Kadi Sarva Vishwavidyalya, Gandhinagar, IN
Source
International Journal of Computational Intelligence Research, Vol 8, No 1 (2012), Pagination: 1-15
Abstract
This paper presents an influence of crossover operator in genetic algorithm for small to large minimum spanning tree problem. A minimum spanning tree problem becomes NP-hard problem when additional constraint degree is applied with each node to restrict the number of edges. Crossover operator plays an important role in genetic algorithm approach. Since many researchers have tried to solve this problem for small to mid size, we have explored the use of genetic algorithm with various crossover functions with modification but without changing the nature of genetic algorithm. Various crossover functions have been developed here as per the requirement of the problem and applied with the various size of network. In this paper we have tried to show the impact of crossover function in genetic algorithm.
Keywords
Genetic Algorithm, Crossover Operator Degree Constrained Minimum Spanning Tree
References
- F. Harary and J. P. Hayes, “Node fault tolerance in graphs,” Networks, vol. 27, no. 1, pp. 19–23, 1996
- H. K. Ku and J. P. Hayes, “Optimally edge fault-tolerant trees,” Networks, vol. 27, no. 3, pp. 203–214, 1996.
- Cunha, A. and A. Lucena, “Algorithms for the degree-constrained minimum spanning tree problem,” Electronic Notes in Discrete Mathematics, volume 19, pages 403-409, and 2005
- Narsingh Deo, 2000. Graph Theory with Applications to Engineering and Computer science: (PHI)
- A Novel Genetic Algorithm approach for Network Design wit Robust Fitness Function International Journal of Computer Theory and Engineering, Vol. 2, No. 3, June, 20101793-8201
- Melanie M. (1998). An Introduction to genetic Algorithm (PHI ) ISBN 81- 203-1385-5
- Michael D. Vose. 1999. The simple genetic algorithm : (PHI) ISBN 61-203- 2459-5
- Lixia Hanr and Yuping Wang, A Novel Genetic Algorithm for Degree- Constrained Minimum Spanning Tree Problem, IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.7A, July 2006
