Comparative Study of Cuckoo Inspired Metaheuristics Applying to Knapsack Problems

Print
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
Amira Gherboudj
10.5120/ijca2016912508

Amira Gherboudj. Comparative Study of Cuckoo Inspired Metaheuristics Applying to Knapsack Problems. International Journal of Computer Applications 155(12):25-31, December 2016. BibTeX

@article{10.5120/ijca2016912508,
	author = {Amira Gherboudj},
	title = {Comparative Study of Cuckoo Inspired Metaheuristics Applying to Knapsack Problems},
	journal = {International Journal of Computer Applications},
	issue_date = {December 2016},
	volume = {155},
	number = {12},
	month = {Dec},
	year = {2016},
	issn = {0975-8887},
	pages = {25-31},
	numpages = {7},
	url = {http://www.ijcaonline.org/archives/volume155/number12/26658-2016912508},
	doi = {10.5120/ijca2016912508},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

Cuckoo Optimization Algorithm (COA) and Cuckoo Search Algorithm (CS) are two population-based metaheuristics. They are based on the cuckoo’s behavior in their lifestyle and their characteristics in egg laying and breeding. Both algorithms are proposed for continuous optimization problems. In this paper, we propose a comparative study of COA and CS. For this we have proposed a binary version of COA (called BCOA) algorithm using the Sigmoid function like we have do in a later work, in which we have proposed a binary version of CS algorithm that we have called BCS. In aim to compare the efficiency of the too algorithms, we have used the proposed BCOA to resolve knapsack problem (KP) and Multidimensional knapsack problem (MKP) problems and we have compared the obtained results with those obtained by BCS.

References

  1. Yang, X.-S., and Deb, S., Engineering Optimisation by Cuckoo Search, Int. J. Mathematical Modelling and Numerical Optimisation, Vol. 1, No. 4, pp. 330–343, 2010.
  2. R. Rajabioun. Cuckoo Optimization Algorithm. Applied Soft Computing. Vol 11, N° 8, pp 5508-5518, 2011.
  3. Gherboudj. A, Chikhi. S. BPSO Algorithms for Knapsack Problem. A. Özcan, J. Zizka, and D. Nagamalai (Eds.): WiMo/CoNeCo 2011, CCIS 162, pp. 217–227, 2011. Springer (2011).
  4. A. Gherboudj, A. Layeb, S. Chikhi. Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm. International Journal of Bio-Inspired Computation. Vol. 4, N°.4, pp 229-236. Inderscience Publishers ISSN (Print): 1758-0366, ISSN (online): 1758-0374. DOI: 10.1504/IJBIC.2012.048063. 2012.
  5. Liao, C-J., Tseng, C-T. and Luarn, P. (2007) ‘A discrete version of particle swarm optimization for flowshop scheduling problems’, Computers & Operations Research, Vol. 34, No. 10, pp.3099–3111, Elsevier.
  6. Pongchairerks, P. (2009) ‘Particle swarm optimization algorithm applied to scheduling problems’, ScienceAsia, Vol. 35, No. 1, pp.89–94.
  7. Zhan, Z-h. and Zhang, J. (2009) ‘Discrete particle swarm optimization for multiple destination routing problems’, in Giacobini, M. et al. (Eds.): Proc. EvoWorkshops 2009, LNCS, Vol. 5484, pp.117–122, Springer.
  8. Julstrom. B-A. Greedy, Genetic, and Greedy Genetic Algorithms for the Quadratic Knapsack Problem. In proc. GECCO '05 Proceedings of the 2005 conference on Genetic and evolutionary computation, Publisher: ACM, pp. 607-614. ISBN: 1595930108.
  9. Singh. A and Baghel. A-S. A New Grouping Genetic Algorithm for the Quadratic Multiple Knapsack Problem. In proc. C. Cotta and J. van Hemert (Eds.): EvoCOP 2007, LNCS 4446, pp. 210 – 218, Springer (2007).
  10. Kong. M and Tian. P. Apply the Particle Swarm Optimization to the Multidimensional Knapsack Problem. In proc. L. Rutkowski et al. (Eds.): ICAISC 2006, LNAI 4029, pp. 1140–1149, Springer (2006).
  11. Pisinger, D.: Where are the hard knapsack problems? Computers and Operations Research, Vol.32, N°. 9, pp. 2271-2284, 2005.
  12. Chu .P.C, Beasley. J.E. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4: 63–86 (1998).
  13. Vasquez. M and Vimont. Y., Improved results on the 0–1 multidimensional knapsack problem, European Journal of Operational Research 165 (1), pp. 70–81, 2005.

Keywords

Combinatorial optimization, Cuckoo Optimization Algorithm, Cuckoo Search, Binary Cuckoo Optimization Algorithm, Binary Cuckoo Search, knapsack problem, Multidimensional knapsack problem.