Two population-based optimization algorithms for minimum weight connected dominating set problem

Dagdeviren Z. A., Aydin D., ERDEM M. G.

Applied Soft Computing Journal, cilt.59, ss.644-658, 2017 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 59
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1016/j.asoc.2017.06.023
  • Dergi Adı: Applied Soft Computing Journal
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.644-658
  • Anahtar Kelimeler: Hybrid genetic algorithm, Minimum weight connected dominating set, Optimization heuristics, Population-based iterated greedy algorithm, Undirected graph
  • Manisa Celal Bayar Üniversitesi Adresli: Hayır

Özet

Minimum weight connected dominating set (MWCDS) is a very important NP-Hard problem used in many applications such as backbone formation, data aggregation, routing and scheduling in wireless ad hoc and sensor networks. Population-based approaches are very useful to solve NP-Hard optimization problems. In this study, a hybrid genetic algorithm (HGA) and a population-based iterated greedy (PBIG) algorithm for MWCDS problem are proposed. To the best of our knowledge, the proposed algorithms are the first population-based algorithms to solve MWCDS problem on undirected graphs. HGA is a steady-state procedure which incorporates a greedy heuristic with a genetic search. PBIG algorithm refines the population by partially destroying and greedily reconstructing individual solutions. We compare the performance of the proposed algorithms with other greedy heuristics and brute force methods through extensive simulations. We show that our proposed algorithms perform very well in terms of MWCDS solution quality and CPU time.