Skip to main content
SpringerLink
Log in

Solving Large 0–1 Multidimensional Knapsack Problems by a New Simplified Binary Artificial Fish Swarm Algorithm

  • Published:
Journal of Mathematical Modelling and Algorithms in Operations Research

Abstract

The artificial fish swarm algorithm has recently been emerged in continuous global optimization. It uses points of a population in space to identify the position of fish in the school. Many real-world optimization problems are described by 0–1 multidimensional knapsack problems that are NP-hard. In the last decades, several exact as well as heuristic methods have been proposed for solving these problems. In this paper, a new simplified binary version of the artificial fish swarm algorithm is presented, where a point/fish is represented by a binary string of 0/1 bits. Trial points are created by using crossover and mutation in the different fish behavior that are randomly selected by using two user defined probability values. In order to make the points feasible, the presented algorithm uses a random heuristic drop-item procedure followed by an add-item procedure aiming to increase the profit throughout the adding of more items in the knapsack. A cyclic reinitialization of 50 % of the population, and a simple local search that allows the progress of a small percentage of points towards optimality and after that refines the best point in the population greatly improve the quality of the solutions. The presented method is tested on a set of benchmark instances and a comparison with other methods available in literature is shown. The comparison shows that the proposed method can be an alternative method for solving these problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Akçay, Y., Li, H., Xu, S.H.: Greedy algorithm for the general multidimensional knapsack problem. Ann. Oper. Res. 150, 17–29 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Al-Shihabi, S., Ólafsson, S.: A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem. Comput. Oper. Res. 37, 247–255 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  3. Azad, M.A.K., Rocha, A.M.A.C., Fernandes, E.M.G.P.: Solving multidimensional 0-1 knapsack problem with an artificial fish swarm algorithm. In: Murgante, B. et al. (eds.) Computational Science and Its Applications, ICCSA 2012, Part III, LNCS, vol. 7335, pp. 72–86. Springer-Verlag, Heidelberg (2012)

  4. Azad, M.A.K., Rocha, A.M.A.C., Fernandes, E.M.G.P.: A simplified binary artificial fish swarm algorithm for 0–1 quadratic knapsack problems. J. Comput. Appl. Math. 259, 897–904 (2014)

    Article  MathSciNet  Google Scholar 

  5. Balev, S., Yanev, N., Fréville, A., Andonov, R.: A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem. Eur. J. Oper. Res. 166, 63–76 (2008)

    Article  Google Scholar 

  6. Bansal, J.C., Deep, K.: A modified binary particle swarm optimization for knapsack problems. Appl. Math. Comput. 218(22), 11042–11061 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bonyadi, M.R., Li, X.: A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators. Oper. Res. - Int. J. 12, 229–252 (2012)

    Article  MATH  Google Scholar 

  8. Boyer, V., Elkihel, M., Baz, D.E.: Heuristics for the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. 199, 658–664 (2009)

    Article  MATH  Google Scholar 

  9. Cabot, A.V.: An enumeration algorithm for knapsack problems. Oper. Res. 18, 306–311 (1970)

    Article  MATH  Google Scholar 

  10. Chu, P.C., Beasley, J.E.: A genetic algorithm for the multidimensional knapsack problem. J. Heuristics 4, 63–86 (1998)

    Article  MATH  Google Scholar 

  11. Costa, M.F.P., Rocha, A.M.A.C., Fernandes, E.M.G.P.: An artificial fish swarm algorithm based hyperbolic augmented Lagrangian method. J. Comput. Appl. Math. 259, 868–876 (2014)

    Article  MathSciNet  Google Scholar 

  12. Djannaty, F., Doostdar, S.: A hybrid genetic algorithm for the multidimensional knapsack problem. Int. J. Contemp. Math. Sci. 3(9), 443–456 (2008)

    MathSciNet  MATH  Google Scholar 

  13. Drexl, A.: A simulated annealing approach to the multiconstraint zero–one knapsack problem. Computing 40, 1–8 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  14. Fontanari, J.F.: A statistical analysis of the knapsack problem. J. Phys. A Math. Gen. 28, 4751–4759 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fréville, A.: The multidimensional 0–1 knapsack problem: an overview. Eur. J. Oper. Res. 155, 1–21 (2004)

    Article  MATH  Google Scholar 

  16. Fréville, A., Plateau, G.: The 0–1 bidimensional knapsack problem: Towards an efficient high-level primitive tool. J. Heuristics 2, 147–167 (1996)

    Article  MATH  Google Scholar 

  17. Gavish, B., Pirkul, H.: Efficient algorithms for solving multiconstraint zero–one knapsack problems to optimality. Math. Program. 31, 78–105 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  18. Hanafi, S., Fréville, A.: An efficient tabu search approach for the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. 106, 659–675 (1998)

    Article  MATH  Google Scholar 

  19. Hill, R.R., Cho, Y.K., Moore, J.T.: Problem reduction heuristic for the 0–1 multidimensional knapsack problem. Comput. Oper. Res. 39, 19–26 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  20. Jiang, M., Mastorakis, N., Yuan, D., Lagunas, M.A.: Image segmentation with improved artificial fish swarm algorithm. In: Mastorakis, N. et al. (eds.) ECC 2008, LNEE, vol. 28, pp. 133–138. Springer-Verlag, Heidelberg (2009)

  21. Jiang, M., Wang, Y., Pfletschinger, S., Lagunas, M.A., Yuan, D.: Optimal multiuser detection with artificial fish swarm algorithm. In: Huang, D.S. et al. (eds.) ICIC 2007, CCIS, vol. 2, pp. 1084–1093. Springer-Verlag, Heidelberg (2007)

  22. Ke, L., Feng, Z., Ren, Z., Wei, X.: An ant colony optimization approach for the multidimensional knapsack problem. J. Heuristics 16, 65–83 (2010)

    Article  MATH  Google Scholar 

  23. Kong, M., Tian, P., Kao, Y.: A new ant colony optimization algorithm for the multidimensional knapsack problem. Comput. Oper. Res. 35, 2672–2683 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Langeveld, J., Engelbrecht, A.P.: Set-based particle swarm optimization applied to the multidimensional knapsack problem. Swarm Intell. 6, 297–342 (2012)

    Article  Google Scholar 

  25. Michalewicz, Z.: Genetic Algorithms+Data Structures=Evolution Programs. Springer, Berlin (1996)

    Book  MATH  Google Scholar 

  26. Neshat, M., Sepidnam, G., Sargolzaei, M., Toosi, A.N.: Artificial fish swarm algorithm: a survey of the state-of-the-art, hybridization, combinatorial and indicative applications. Artif. Intell. Rev 42(4), 965–997 (2014)

  27. Petersen, C.C.: Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Manag. Sci. 13(9), 736–750 (1967)

    Article  Google Scholar 

  28. Pirkul, H.: A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Nav. Res. Logist. 34, 161–172 (1987)

    Article  MATH  Google Scholar 

  29. Pisinger, D.: Algorithms for knapsack problems. Ph.D. thesis, Department of Computer Science, University of Copenhagen, Denmark. http://www.diku.dk/hjemmesider/ansatte/pisinger/ (1995)

  30. Puchinger, J., Raidl, G.R., Pferschy, U.: The multidimensional knapsack problem: structure and algorithms. INFORMS J. Comput 22(2), 250–265 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  31. Rocha, A.M.A.C., Fernandes, E.M.G.P., Martins, T.F.M.C.: Novel fish swarm heuristics for bound constrained global optimization problems. In: Murgante, B., et al. (eds.) Computational Science and Its Applications, ICCSA 2011, Part III, LNCS, vol. 6784, pp 185–199. Springer-Verlag, Heidelberg (2011)

  32. Rocha, A.M.A.C, Martins, T.F.M.C, Fernandes, E.M.G.P.: An augmented Lagrangian fish swarm based method for global optimization. J. Comput. Appl. Math. 235, 4611–4620 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  33. Sakawa, M., Kato, K.: Genetic algorithms with double strings for 0–1 programming problems. Eur. J. Oper. Res. 144, 581–597 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  34. Schilling, K.E.: The growth of m–constraint random knapsacks. Eur. J. Oper. Res. 46, 109–112 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  35. Shih, W.: A branch and bound method for the multiconstraint zero–one knapsack problem. J. Oper. Res. Soc. 30, 369–378 (1979)

    MATH  Google Scholar 

  36. Soyster, A.L., Lev, B., Slivka, W.: Zero–one programming with many variables and few constraints. Eur. J. Oper. Res. 2, 195–201 (1978)

    Article  MATH  Google Scholar 

  37. Vasquez, M., Vimont, Y.: Improved results on the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. 165, 70–81 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  38. Wang, C.R., Zhou, C.-L., Ma, J.-W.: An improved artificial fish swarm algorithm and its application in feed-forward neural networks. In: Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, pp. 2890–2894 (2005)

  39. Wang, X., Gao, N., Cai, S., Huang, M.: An artificial fish swarm algorithm based and abc supported QoS unicast routing scheme in NGI. In: Min, G., et al. (eds.) ISPA 2006, LNCS, vol. 4331, pp. 205–214. Springer-Verlag, Heidelberg (2006)

  40. Weingartner, H.M., Ness, D.N.: Methods for the solution of the multidimensional 0/1 knapsack problem. Oper. Res. 15, 83–103 (1967)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Algoritmi Research Centre, Campus de Gualtar, University of Minho, 4710–057, Braga, Portugal

    Md. Abul Kalam Azad, Ana Maria A. C. Rocha & Edite M. G. P. Fernandes

Authors
  1. Md. Abul Kalam Azad
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ana Maria A. C. Rocha
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Edite M. G. P. Fernandes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ana Maria A. C. Rocha.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Azad, M.A.K., Rocha, A.M.A.C. & Fernandes, E.M.G.P. Solving Large 0–1 Multidimensional Knapsack Problems by a New Simplified Binary Artificial Fish Swarm Algorithm. J Math Model Algor 14, 313–330 (2015). https://doi.org/10.1007/s10852-015-9275-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-015-9275-2

Keywords

Search

Navigation