Scholarlink

<p>The maximum independent set problem is an NP-hard problem with important applications in distributed systems, network analysis, and bioinformatics. Due to its high computational complexity, finding optimal solutions for large graphs is very challenging. In this work, we propose a PSO based approach to solve the MaxIS problem. The PSO algorithm models each solution as a binary vector and uses swarm intelligence to explore the solution space. A local search technique is applied to refine the solutions and ensure their validity. The proposed PSO algorithm is tested on benchmark datasets including DIMACS, DIMACS10, and Miscellaneous graphs. Experimental results show that PSO achieves better solution quality and faster convergence compared to traditional metaheuristics like GA, GWO, and ACO. Overall, the results demonstrate that PSO is an effective and efficient method for approximating large Maximum Independent Sets, outperforming classical approaches in both solution size and computation time.</p>

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

Particle Swarm Optimization for Finding Maximum Independent Set

  • 期刊论文

  • 发表日期：

    2025年9月27日

查看全文
  • Ritika Verma,
  • Dharmendra Prasad Mahato

摘要

The maximum independent set problem is an NP-hard problem with important applications in distributed systems, network analysis, and bioinformatics. Due to its high computational complexity, finding optimal solutions for large graphs is very challenging. In this work, we propose a PSO based approach to solve the MaxIS problem. The PSO algorithm models each solution as a binary vector and uses swarm intelligence to explore the solution space. A local search technique is applied to refine the solutions and ensure their validity. The proposed PSO algorithm is tested on benchmark datasets including DIMACS, DIMACS10, and Miscellaneous graphs. Experimental results show that PSO achieves better solution quality and faster convergence compared to traditional metaheuristics like GA, GWO, and ACO. Overall, the results demonstrate that PSO is an effective and efficient method for approximating large Maximum Independent Sets, outperforming classical approaches in both solution size and computation time.