Scholarlink

<p>The partial set covering problem (PSCP) is a significant combinatorial optimization problem that finds applications in numerous real-world scenarios. The objective of PSCP is to encompass a minimum number of subsets while ensuring the coverage of at least <i>n</i> elements. Due to its NP-hard nature, solving large-scale PSCP efficiently remains a critical issue in computational intelligence. To effectively tackle this challenge, we delve into a population-based approach that incorporates a modified tabu search, thereby striking a delicate balance between exploration and exploitation. To further enhance its efficacy, we employ the multiple path-relinking strategy and the fix-and-optimize process. Finally, the dynamic resource allocation scheme is utilized to save computing efforts. Comparative experiments of the proposed algorithm were conducted against three state-of-the-art competitors, across two distinct categories, encompassing 150 instances. The results significantly underscore the profound effectiveness of our proposed algorithm, as evidenced by the updating of 67 best-known solutions. Moreover, we conduct an in-depth analysis of the key components inherent to the algorithm, shedding light on their respective influences on the whole performance.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An effective population-based approach for the partial set covering problem

  • 期刊论文

  • 发表日期：

    2025年2月8日

查看全文
  • Ye Zhang,
  • Jinlong He,
  • Yupeng Zhou,
  • Shuli Hu,
  • Dunbo Cai,
  • Naiyu Tian,
  • Minghao Yin

摘要

The partial set covering problem (PSCP) is a significant combinatorial optimization problem that finds applications in numerous real-world scenarios. The objective of PSCP is to encompass a minimum number of subsets while ensuring the coverage of at least n elements. Due to its NP-hard nature, solving large-scale PSCP efficiently remains a critical issue in computational intelligence. To effectively tackle this challenge, we delve into a population-based approach that incorporates a modified tabu search, thereby striking a delicate balance between exploration and exploitation. To further enhance its efficacy, we employ the multiple path-relinking strategy and the fix-and-optimize process. Finally, the dynamic resource allocation scheme is utilized to save computing efforts. Comparative experiments of the proposed algorithm were conducted against three state-of-the-art competitors, across two distinct categories, encompassing 150 instances. The results significantly underscore the profound effectiveness of our proposed algorithm, as evidenced by the updating of 67 best-known solutions. Moreover, we conduct an in-depth analysis of the key components inherent to the algorithm, shedding light on their respective influences on the whole performance.