Yang Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Yang Liu has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Jianan Wang
School of Physics, Northeast Normal University, Changchun, China
1 shared publication - Jinshu Li
School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
1 shared publication - Shuai Lv
Urban Construction Archives, Changchun 130000, China
1 shared publication - Yong Lai
Jilin University
1 shared publication - Yupeng Zhou
School of Information Science and Technology, Northeast Normal University, Changchun, China
1 shared publication
Latest Publications
- Open Access
- 15 July 2020
- Published by MDPI AG in Mathematics
- Vol. 8 (7) , 1155
Improved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set
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.
- 15 July 2020
- Published by MDPI AG in Mathematics
- Vol. 8 (7) , 1155
Open AccessImproved Memetic Algorithm for Solving the Minimum Weight Vertex Independent Dominating Set
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.