.png){kind=icon}
.png){kind=icon}
Return
Two population-based optimization algorithms for minimum weight connected dominating set problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.asoc.2017.06.023.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2017 Elsevier B.V. All rights reserved.
Keywords:
Minimum weight connected dominating set
Hybrid genetic algorithm
Population-based iterated greedy algorithm
Optimization heuristics
Undirected graph
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6.6
Papers:
1.4W
Citations:
4.8W