Improved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set

Yupeng Zhou, Jinshu Li, Yang Liu, Shuai Lv, Yong Lai and Jianan Wang
Additional contact information
Yupeng Zhou: Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
Jinshu Li: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Yang Liu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Shuai Lv: Urban Construction Archives, Changchun 130000, China
Yong Lai: Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
Jianan Wang: Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Mathematics, 2020, vol. 8, issue 7, 1-17

Abstract: The minimum weight vertex independent dominating set (MWVIDS) problem is an important version of the minimum independent dominating set. The MWVIDS problem has a number of applications in many fields. However, the MWVIDS problem is known to be NP-hard and thus computationally challenging. In this work, we present the improved memetic algorithm called MSSAS for solving the MWVIDS problem. The proposed MSSAS algorithm combines probability-based dynamic optimization (PDO) (to generate good and diverse offspring solutions by assembling elements of existing good solutions) as well as a local search phase named C_LS (to seek high-quality local optima by combining the idea of constrained-based two-level configuration checking strategy and tabu mechanism). The extensive results on popular DIMACS and BHOLIB benchmarks demonstrate that MSSAS competes favorably with the state-of-the-art algorithms. In addition, we analyze the benefits of the newly raised components including two above proposed ideas with our memetic framework. It is worth mentioning that the combination of both components has excellent effects for the MWVIDS problem.

Keywords: combinatorial optimization; minimum weight vertex independent dominating set; local search; constrained-based CC 2; probability-based dynamic optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/7/1155/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/7/1155/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:7:p:1155-:d:384597

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().