Hybrid Particle Swarm Algorithm for Solving Multidimensional Knapsack Problem

In order to effectively solve combinatorial optimization problems, the Estimation of Distribution Algorithm (EDA) and Particle Swarm Optimization (PSO) combine to form a new ED-PSO hybrid algorithm, the algorithm can effectively apply global statistical information and global optimal solution to the solution space search. This algorithm is used to solve the Multidimensional Knapsack Problem (MKP). Experimental results show that when solving multidimensional knapsack problem, ED-PSO algorithm is superior to traditional PSO algorithm, and also better than many heuristic intelligent algorithm. Meanwhile, ED-PSO algorithm uses fewer parameters, and therefore easier to be implemented, and run more stable.

---

W artykule przedstawiono wykorzystanie algorytmu hybrydowego ED-PSO do rozwiązania wielowymiarowego problem Knapsacka (ang. MKP). Zastosowano tu optymalizację roju cząstek (ang. PSO) oraz algorytmu estymacji EDA. Wyniki eksperymentalne pokazują, że w przypadku MKP proponowany algorytm wykazuje znacznie lepsze możliwości niż klasyczny PSO. Dodatkowo ED-PSO ma mniej parametrów, przez co jest łatwiejszy w implementacji.