SavedAdd your journal

Journals / Anadolu Üniversitesi Bilim ve Teknoloji Dergisi :A-Uygulamalı Bilimler ve Mühendislik / 2013 / Cilt: 14 - Sayı: 3

Tepe Örtüsü Problemi için Yeni Bir Hibrid Genetik Algoritma

A New Hybrid Genetic Algorithm for Vertex Cover Problem

Onur UĞURLU
Pages
277–282
Publication Date
2022-10-11
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The experimental results have shown that the propose d algorithm can yield quality solutions in reasonable times.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The minimum vertex cover problem belongs to the class of NP-compl ete graph theoretical problems.
📊
Key Findings & Data:This paper presents a hybrid genetic algorithm to solve minimum ver tex cover problem.
💡
Conclusion & Impact:The experimental results have shown that the propose d algorithm can yield quality solutions in reasonable times.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters

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.

Özet

Minimum tepe örtüsü problemi, NP-Tam sınıfına ait teorik bir graf problemidir. Bu makale minimum tepe örtüsü problemini çözmek için yeni bir hibrid algoritma sunar. Bu makalede genetik algoritmaya yerel optimizasyon tekniğini eklenince basit genetik algoritmadan daha kaliteli sonuçlar elde edildiği gösterilmiştir. Ayrıca özellikle minimum tepe örtüsü problemi içinn, genel en iyi sonuca daha hızlı yakınsayan yeni bir mutasyon operatörü geliştirilmiştir. Yeni hibrid algoritma önceki çalışmalarla karşılaştırılmıştır. Hesaplama sonuçları algoritmanın makul sürelerde kaliteli sonuçlar verebileceğini göstermektedir

🔖

Cite This Article

UĞURLU, O. (2022). Tepe Örtüsü Problemi için Yeni Bir Hibrid Genetik Algoritma. Anadolu Üniversitesi Bilim ve Teknoloji Dergisi :A-Uygulamalı Bilimler ve Mühendislik, Cilt: 14 - Sayı: 3, 277–282. https://ajindex.com/articles/438398

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (11)

  1. Aggarwal, C. C., Orlin, J. B., Tai, R. P. (1997). Optimized Crossover for The İndependent Set Problem. Operations Research, 45(2), 226-234.
  2. 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.
  3. Clarkson, K. (1983). A Modification to The Greedy Algorithm for The Vertex Cover Problem. IPL, Vol. 16, 23-25.
  4. Cormen, T.H., Lieserson, C. E., Rivest R. L., Stein, C. (2001). Introduction to Algorithms. Second Edition,
  5. The MIT Press.
  6. 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.
  7. 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).
  8. 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.
  9. 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.
  10. 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.
  11. Pullan, W. (2009). Optimisation of Unweighted/Weighted Maximum Independent Sets and Minimum Vertex Covers. Discrete Optimization, 6(2), 214-21