Ant colony optimization algorithm for the 0-1 knapsack problem

• Autorzy: Schiff K.

Warianty tytułu

PL

Algorytmy mrówkowe dla 0-1 problemu plecakowego

• Języki publikacji: EN

Abstrakty

EN

This article describes a new ant colony optimisation algorithm for the discrete knapsack problem with a new heuristic pattern, based on the ratio of the square of the profit coefficient to the square of the weight coefficient of the original problem. This new heuristic is used in order to choose objects that should be packed into the knapsack. This pattern was compared with two used in ant algorithms and which have been presented in the literature on the subject of ant colony optimisation algorithms for the 0-1 Knapsack Problem. The two other patterns are based on the ratio of the profit coefficient to the weight coefficient multiplied respectively by the total and the current knapsack load capacity. Results of tests under a width range of ant algorithm parameters such as the number of cycles, the number of ants, the evaporation rate, and the load knapsack capacity are shown and discussed.

PL

W artykule przedstawiono algorytm mrówkowy dla dyskretnego problemu plecakowego z nową heurystyką wyboru obiektów i został on porównany z dwoma innymi algorytmami spotkanymi w literaturze przedmiotu pod względem uzyskiwanego całkowitego zysku z załadowanych do plecaka przedmiotów. Nowa heurystyka wyboru została wyrażona poprzez stosunek kwadratu zysku do kwadratu wagi wybranego przedmiotu, gdy dwie znane już heurystyki to stosunek zysku do wagi odpowiednio pomnożony przez całkowitą i bieżącą ładowność plecaka. W artykule przedstawiono wyniki przeprowadzonych testów dla szerokiego zakresu parametrów algorytmów mrówkowych takich jak: współczynnik parowania, liczba cykli, liczba mrówek, ładowności plecaka jak i dla różnej liczby dostępnych przedmiotów do załadunku.

Słowa kluczowe

EN

knapsack problem; ant colony optimisation; heuristic algorithm

PL

problem plecakowy; algorytm mrówkowy; heurystyka

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Automatyka
• Rocznik: 2013
• Tom: R. 110, z. 3-AC
• Strony: 39--52
• Opis fizyczny: Bibliogr. 17 poz., wz., tab., wykr.

Twórcy

autor

Schiff K.

• Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology

Bibliografia

• [1] Kolhe P., Christensen H., Planning in Logistics: A survey, PerMIS’10 September 28–30, Baltimore 2010.
• [2] Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco 1979.
• [3] Sysło M., Deo N., Kowalik J., Algorytmy optymalizacji dyskretnej, PWN, 1993.
• [4] Toth P., Dynamic programming algorithms for the 0-1 knapsack problem, Computing 25, 1980, 29-45.
• [5] Fayard D., Plateau G., Algorithm 47: An algorithm for the solution of the 0-1 knapsack problem, Computing 28, 1982, 269-287.
• [6] Koleasr P., A branch and bound algorithm for the knapsack problem, Management Science 13, 1967, 723-735.
• [7] Fidanova S., Ant Colony Optimization for Multiple Knapsack Problem and Heuristic Model, Kluwer Academic Publishers, 2004.
• [8] Fidanova S., Ant Colony Optimization for Multiple Knapsack Problem and Model Bias, [in:] Margenov S., Vulkov L.G., Wasniewski J. (Eds.), Numerical Analysis and Its Applications, LNCS, Vol. 3401, Springer, Berlin Heidelberg, 2005, 280-287.
• [9] Fidanova S., Probabilistic Model of Ant Colony Optimization for Multiple Knapsack Problem, In Lirkov I., Margenov S., Wasniewski J. (Eds.), LSSC 2007, LNCS 4818, Berlin 2008, 545-552.
• [10] Alaya I., Solnon C., Gheira K., Ant algorithm for the multi-dimensional knapsack problem, International Conference on Bioinspired Optimization Methods and their Applications, (BIOMA 2004), 2004, 63-72.
• [11] Fidanova S., Heuristic for the multiple knapsack problem, IADIS International Conference on Applied Computing, 2005, 255-260.
• [12] Boryczka U., Ants and Multiple Knapsack Problem, 6th International Conference on Computer Information Systems and Industrial Management Applications (CISIM’07), 2007, IEEE Computer Society, No. P2894, 2007, 149-154.
• [13] Ke L., Feng Z., Ren Z., Wei X., An ant colony optimization approach for the multi-dimensional knapsack problem, Journal of Heuristics, Vol. 16, No. 1, 2010, 65-83.
• [14] Shahrear I., Faizul B., Sohel R., Solving the Multidimensional Multi-choice Knapsack Problem with the Help of Ants, M. Dorigo et al. (Eds.), ANTS 2010, LNCS 6234, Berlin 2010, 312-323.
• [15] Ji J., Huang Z., Liu C., Liu X., Zhong N., An Ant Colony Optimization Algorithm for Solving the Multidimensional Knapsack Problems, [in:] Proceedings of the 2007 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IEEE Computer Society, Los Alamitos, 2007, 10-16.
• [16] Leguizamon G., Michalewicz Z., A new version of ant system for subset problems; [in:] Proceedings of the 1999 Congress on Evolutionary Computation, CEC 1999, Vol. 2, 1999, 1458-1464.
• [17] Dorigo M., Caro D.G., Gambardella L.M., Ant algorithms for discrete optimization, Artificial Life, Vol. 5, No. 2, 1999, 137-172.