Hybrid Particle Swarm Algorithm for Solving Multidimensional Knapsack Problem

• Autorzy: Liu W.

Warianty tytułu

PL

Hybrydowy algorytm roju cząstek w rozwiązywaniu wielowymiarowego problemu Knapsacka

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

hybird particle swarm optimization; estimation of distribution algorithm; optimization; multidimensional Knapsack problem

PL

hybrydowa optymalizacja roju cząstek; algorytm estymacji rozkładu; wielowymiarowy problem Knapsacka

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2013
• Tom: R. 89, nr 1b
• Strony: 228--231
• Opis fizyczny: Bibliogr. 9 poz., schem.

Twórcy

autor

Liu W.

• The School of Computer Science and Technology Dalian University of Technology Dalian,China
• Dept.of Electrical Engineering,Institute of XinJinag Mechano-Electrical Vocational and Technical,Urumqi,China

Bibliografia

• [1] Kennedy, J., Eberhart, RC: Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. NJ: Piscataway, (1995) 1942-1948Goguen JA, Parameterized Programming.IEEE Transactions on Software Engineering,10(5):528-543,1984.
• [2] Zhang Yan etc., Overview of Particle Swarm Optimization and Its Improved Form, Computer Engineering and Application, 2005,41(2):62-63.
• [3] Zhou Shude etc., Overview of Estimation of Distribution Algorithms, AAS, 2007,33(2):113-124.
• [4] Fernanda Hembecker, Particle Swarm Optimization for the Multidimensional Knapsack Problem, Federal University of Technology Parana (UTFPR), 2001
• [5] Pelikan, M., Goldberg, DE, Lobo, F.: A Survey Of Optimization by Building and Using Probabilistic Models.IlliGAL Technical Report 99018,1999
• [6] Cai Zixing, Artificial Intelligence and Its Applications: Graduate Book (third edition), Tsinghua University Press, 2005
• [7] Ma Shaoping, Artificial Iintelligence, Tsinghua University Press, 2006
• [8] PCChu and JEBeasley, A Genetic Algorithm for the Multidimensional Knapsack Problem, Journal of Heuristics, 1999,4:63-86
• [9] Krzysztof Socha, Marco Dorigo. Ant colony optimization for continuous domains. European Journal of Operational Research (S0377-2217). 2008, 185(3): 1155-1173.