Abstract
The minimum vertex cover problem belongs to the class of NP-compl ete graph theoretical problems. This paper presents a hybrid genetic algorithm to solve minimum ver tex cover problem. In this paper, it has been shown that when local optimization technique is added t o genetic algorithm to form hybrid genetic algorithm, it gives more quality solution than simple genet ic algorithm. Also, anew mutation operator has been developed especially for minimum vertex cover problem, whichc onverges faster to the global optimal solution. The new hybrid gentic algorith m has been compared with the previous works. The experimental results have shown that the propose d algorithm can yield quality solutions in reasonable times
Keywords
References
- Aggarwal, C. C., Orlin, J. B., Tai, R. P. (1997). Optimized Crossover for The İndependent Set Problem. Operations Research, 45(2), 226-234.
- Balas, E, and Niehaus, W. (1996). Finding Large Cliques in Arbitrary Graphs by Bipartite Matching. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, 29-52.
- Clarkson, K. (1983). A Modification to The Greedy Algorithm for The Vertex Cover Problem. IPL, Vol. 16, 23-25.
- Cormen, T.H., Lieserson, C. E., Rivest R. L., Stein, C. (2001). Introduction to Algorithms. Second Edition, The MIT Press.
- Dharwadker A. (2011). The Vertex Cover Algorithm. Createspace.
- Clique Benchmarks, (1993). Benchmark Instances Made Available by Electronic Transfer At Dimacs.Rutgers.Edu, Rutgers Univ., Piscataway. NJ.
- El-Mihoub, T. A., Hopgood, A. A., Nolle, L., & Battersby, A. (2006). Hybrid Genetic Algorithms: A Review. Engineering Letters, 13(2), 124-137.
- Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to The Theory Np – Completeness. San Francisco: Freeman
- Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Massachusetts: Addison Wesley.
- Khuri, S. and Bäck, T. (1994). An Evolutionary Heuristic for The Minimum Vertex Cover Problem. in Genetic Algorithms within The Framework of Evolutionary Computation–Proc. of The KI-94 Workshop. Germany, 86-90.
- Kotecha, K. and Gambhava, N. (2003). A Hybrid Genetic Algorithm for Minimum Vertex Cover Problem. In The First Indian International Conference on Artificial Intelligence, 904-913.
- Mitchell, M. (2002). Introduction To Genetic Algorithms. New Delhi: Prentice-Hall
- Monien, B. and Speckenmeyer, E. (1985). Ramsey Numbers and an Approximation Algorithm for The Vertex Cover Problem. Acta Informatica, 22(1), 115-123.
- Pullan, W. (2009). Optimisation of Unweighted/Weighted Maximum Independent Sets and Minimum Vertex Covers. Discrete Optimization, 6(2), 214-21
Abstract
Keywords
Tepe örtüsü problemi Hibrid algoritmalar Genetik algoritmalar Yerel optimizasyon teknikleri
References
- Aggarwal, C. C., Orlin, J. B., Tai, R. P. (1997). Optimized Crossover for The İndependent Set Problem. Operations Research, 45(2), 226-234.
- Balas, E, and Niehaus, W. (1996). Finding Large Cliques in Arbitrary Graphs by Bipartite Matching. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, 29-52.
- Clarkson, K. (1983). A Modification to The Greedy Algorithm for The Vertex Cover Problem. IPL, Vol. 16, 23-25.
- Cormen, T.H., Lieserson, C. E., Rivest R. L., Stein, C. (2001). Introduction to Algorithms. Second Edition, The MIT Press.
- Dharwadker A. (2011). The Vertex Cover Algorithm. Createspace.
- Clique Benchmarks, (1993). Benchmark Instances Made Available by Electronic Transfer At Dimacs.Rutgers.Edu, Rutgers Univ., Piscataway. NJ.
- El-Mihoub, T. A., Hopgood, A. A., Nolle, L., & Battersby, A. (2006). Hybrid Genetic Algorithms: A Review. Engineering Letters, 13(2), 124-137.
- Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to The Theory Np – Completeness. San Francisco: Freeman
- Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Massachusetts: Addison Wesley.
- Khuri, S. and Bäck, T. (1994). An Evolutionary Heuristic for The Minimum Vertex Cover Problem. in Genetic Algorithms within The Framework of Evolutionary Computation–Proc. of The KI-94 Workshop. Germany, 86-90.
- Kotecha, K. and Gambhava, N. (2003). A Hybrid Genetic Algorithm for Minimum Vertex Cover Problem. In The First Indian International Conference on Artificial Intelligence, 904-913.
- Mitchell, M. (2002). Introduction To Genetic Algorithms. New Delhi: Prentice-Hall
- Monien, B. and Speckenmeyer, E. (1985). Ramsey Numbers and an Approximation Algorithm for The Vertex Cover Problem. Acta Informatica, 22(1), 115-123.
- Pullan, W. (2009). Optimisation of Unweighted/Weighted Maximum Independent Sets and Minimum Vertex Covers. Discrete Optimization, 6(2), 214-21
Details
| Primary Language | English |
|---|---|
| Journal Section | Articles |
| Authors | |
| Publication Date | May 4, 2015 |
| Published in Issue | Year 2013 Volume: 14 Issue: 3 |
