Discrete Particle Swarm Optimization for Solving the Knapsack Problem

The knapsack problem, as a classic combinatorial optimization challenge, finds extensive applications in resource allocation, investment decision-making, and related domains. While traditional approaches like dynamic programming may encounter high computational complexity when handling large-scale problems, the Discrete Particle Swarm Optimization (DPSO) algorithm emerges as an efficient approximate solution due to its parallel search characteristics.

The core of DPSO lies in simulating bird flock foraging behavior. Each particle represents a potential solution (specifically, an item selection scheme) implemented through binary encoding: 1 denotes item inclusion, while 0 indicates exclusion. Particles dynamically adjust their positions (i.e., 0/1 combinations in the encoding string) based on individual historical optimal solutions and the global best solution. The velocity update formula is transformed into a probability mapping function, where continuous velocity values are converted into binary selection probabilities using a Sigmoid function - a key implementation detail requiring careful parameter tuning.

Algorithm implementation focuses on three critical aspects: 1) Fitness function design balancing knapsack value against capacity constraints, typically implemented as value summation with penalty terms for constraint violations; 2) Incorporation of mutation operators to prevent premature convergence, often implemented through bit-flip operations with controlled probability; 3) Hamming distance calculation during discrete position updates, ensuring meaningful exploration of the solution space. Compared to genetic algorithms, DPSO's swarm collaboration mechanism often achieves higher-quality solutions faster through its social learning component.

The method's advantages include concise code structure and easy parallelization, making it suitable for high-dimensional knapsack problems. Practical applications can extend to multi-objective optimization versions or combine with local search strategies (like 2-opt or neighborhood search) for enhanced solution accuracy. Key functions typically include particle initialization, fitness evaluation, velocity update with sigmoid transformation, and position update with repair mechanisms for constraint handling.