This paper presents a performance analysis of a Particle Swarm Optimization (PSO) algorithm enhanced with a bit-flip operator for solving the 0-1 knapsack problem. The objective of the proposed method is to enhance the exploration capabilities of the classical PSO algorithm by introducing random perturbations to the particle solutions through the bit-flip operator. The efficacy of the algorithm is evaluated on a set of benchmark instances of the 0-1 knapsack problem, and its effectiveness is compared to the optimal solutions that are known to exist. The experimental results demonstrate that the enhanced PSO algorithm consistently achieves near-optimal solutions, thereby showcasing its ability to effectively explore the solution space and converge toward optimal or near-optimal solutions. Moreover, the analysis of the standard deviation across different instances demonstrates the algorithm’s robustness and consistency in performance. The paper offers insights into the algorithm’s convergence behavior and computational efficiency. The paper also outlines potential avenues for future research, including parameter tuning, the integration of other metaheuristics, and the development of extensions to accommodate various real-world constraints.

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

Performance Analysis of Particle Swarm Optimization Algorithm with Bit-Flip Operator for 0-1 Knapsack Problem

  • Hasan Karaca,
  • Emrullah Sonuç,
  • Nesrin Aydin Atasoy

摘要

This paper presents a performance analysis of a Particle Swarm Optimization (PSO) algorithm enhanced with a bit-flip operator for solving the 0-1 knapsack problem. The objective of the proposed method is to enhance the exploration capabilities of the classical PSO algorithm by introducing random perturbations to the particle solutions through the bit-flip operator. The efficacy of the algorithm is evaluated on a set of benchmark instances of the 0-1 knapsack problem, and its effectiveness is compared to the optimal solutions that are known to exist. The experimental results demonstrate that the enhanced PSO algorithm consistently achieves near-optimal solutions, thereby showcasing its ability to effectively explore the solution space and converge toward optimal or near-optimal solutions. Moreover, the analysis of the standard deviation across different instances demonstrates the algorithm’s robustness and consistency in performance. The paper offers insights into the algorithm’s convergence behavior and computational efficiency. The paper also outlines potential avenues for future research, including parameter tuning, the integration of other metaheuristics, and the development of extensions to accommodate various real-world constraints.