International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 4, No. 5, 8 May 2012
Cover page and Table of Contents: PDF (size: 236KB)
A Novel Quantum Inspired Cuckoo Search Algorithm for Bin Packing Problem
Full Text (PDF, 236KB), PP.58-67
Views: 0 Downloads: 0
Author(s)
Index Terms
Bin Packing Problem, Heuristics, Cuckoo Search Algorithm, Quantum Computing, Hybrid Algorithms
Abstract
The Bin Packing Problem (BPP) is one of the most known combinatorial optimization problems. This problem consists to pack a set of items into a minimum number of bins. There are several variants of this problem; the most basic problem is the one-dimensional bin packing problem (1-BPP). In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the 1-BPP problem. The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions. The second contribution is proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.
Cite This Paper
Abdesslem Layeb, Seriel Rayene Boussalia, "A Novel Quantum Inspired Cuckoo Search Algorithm for Bin Packing Problem", International Journal of Information Technology and Computer Science(IJITCS), vol.4, no.5, pp.58-67, 2012. DOI:10.5815/ijitcs.2012.05.08
Reference
[1]Martello, S., and Toth, P. Bin-packing problem. In Knapsack Problems: Algorithms and Computer Implementations.Wiley, 1990, (8): 221–245.
[2]Coffman, E. G., Jr., Garey, M. R., and Johnson, D. S. Approximation algorithms for bin packing: A survery. In D. Hochbaum, editor, Appoximation algorithms for NP-Hard Problems, 1996, 46–93. PWS Publishing, Boston.
[3]Fleszar, K., Hindi, K. S., 2002. New heuristics for one-dimensional bin-packing. Computers and Operations Research, 29 (7): 821-839.
[4]lvim, A.C.F., Ribeiro, C.C., Glover, F., Aloise, D.J. A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem. Journal of Heuristics, 2004, (10):205–229.
[5]Kao, C.-Y. and F.-T. Lin. A stochastic approach for the one-dimensional bin-packing problems. In Systems, Man and Cybernetics, 1992, (2): 1545–1551.
[6]Scholl, A., R. Klein, and C. Juergens (1997). Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research,1997, 24(7): 627–645.
[7]Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics,1996, (2):5–30.
[8]Wang, S., Shi, R., Wang, L. and Ge, M. Study on improved ant colony optimization for bin-packing problem, International Conference on Computer Desingn and Application, 2010,(4):489–491 .
[9]Jourdan, L., Basseur, M. and Talbi, E.G., Hybridizing exact methods and metaheuristics: a taxonomy. European Journal of Operational Research. Vol. 199. 620-629, 2009.
[10]Fogel, D.B., An Introduction to Evolutionary Computation, Tutorial, Congress on Evolutionary Computation (CEC’2001), Seoul, Korea, 2001.
[11]Dorigo M. and Gambardella, L.M. Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, Vol.1, N. 1, pp. 53-66, 1997.
[12]Hu, X, Zhang, J. and Li, Y. Orthogonal methods based ant colony search for solving continuous optimization problems. Journal of Computer Science and Technology, 23(1), pp.2-18, 2008.
[13]Nabti, S. and Meshoul, S. Predator Prey Optimisation for Snake Based Contour Detection, International Journal of Intelligent Computing and Cybernetics - IJICC, Emerald Publishers, 2(2), pp.228-242, 2009.
[14]Clerc, M., and Kennedy, J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evo. Comp., 6(1) 58–73, 2002.
[15]Eberhart, R. C., Shi, Y. and Kennedy, J: Swarm Intelligence. The Morgan Kaufmann Series in Artificial Intelligence. Morgan Kaufmann, San Francisco, CA, USA, 2001.
[16]Yang, X.-S., and Deb, S., Engineering Optimisation by Cuckoo Search, Int. J. Mathematical Modelling and Numerical Optimisation, Vol. 1, No. 4, 330–343, 2010.
[17]Barthelemy, P., Bertolotti, J., Wiersma, D. S., 2008. A Lévy flight for light. Nature, 453, 495-498.
[18]Payne, R. B., Sorenson, M. D., and Klitz, K. The Cuckoos, Oxford University Press, 2005.
[19]Pavlyukevich, I. Lévy flights, non-local search and simulated annealing, J. Computational Physics, 226, 1830-1844, 2007.
[20]Tein L. H. and Ramli R., Recent advancements of nurse scheduling models and a potential path, in: Proc. 6th IMT-GT Conference on Mathematics, Statistics and its Applications (ICMSA 2010), pp. 395-409, 2010.
[21]Dhivya, M. Energy Efficient Computation of Data Fusion in Wireless Sensor Networks Using Cuckoo Based Particle Approach (CBPA), Int. J. of Communications, Network and System Sciences, Vol. 4, No. 4, 249-255, 2011.
[22]A. Gherboudj, A. Layeb, S. Chikhi.: Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm. to appear in the International Journal of Bio-Inspired Computation, ISSN 1758-0366, Inderscience publisher, 2012
[23]Jaeger, G. Quantum Information: An Overview. Berlin: Springer. 2006
[24]Han, K.H. and Kim, J.H.. "Quantum-inspired Evolutionary Algorithms with a New Termination Criterion, Hε Gate, and Two Phase Scheme," IEEE Transactions on Evolutionary Computation, IEEE Press, vol. 8, no. 2, pp. 156-169, April 2004.
[25]Layeb, A., Saidouni, D.E. A New Quantum Evolutionary Local Search Algorithm for MAX 3-SAT Problem. In Proceedings of the 3rd international Workshop on Hybrid Artificial intelligence Systems. Lecture Notes in Artificial Intelligence, vol. 5271. Springer-Verlag, Berlin, Heidelberg, (2008)172-179.
[26]Draa A., Meshoul S., Talbi H., Batouche A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem. Int. Arab J. Inf. Technol. 7(1):pp. 21-27, 2010.
[27]Layeb, A. Hybrid Quantum Scatter Search Algorithm for Combinatorial Optimization Problems. In the journal of Annals. Computer Science Series , ISSN: 1583-7165, Vol. 8, No.2, pp.227-244, 2010
[28]Layeb, A., Saidouni, D.E. A New Quantum Evolutionary Algorithm with Sifting Strategy for Binary Decision Diagram Ordering Problem, in the International Journal of Cognitive Informatics and Natural Intelligence. ISSN 1557-3958, Vol. 4. No 4, pp. 47-61, December 2010.
[29]Layeb: A novel quantum inspired cuckoo search for knapsack problems, in the International Journal of Bio-Inspired Computation, ISSN 1758-0366, Vol. 3, No. 5, pp.297–305, Inderscience publisher, 2011.