Cuckoo search (CS) is a new robust swarm intelligence method that is based on the brood parasitism of some cuckoo species. In this paper, an improved hybrid encoding cuckoo search algorithm (ICS) with greedy strategy is put forward for solving 0-1 knapsack problems. First of all, for solving binary optimization problem with ICS, based on the idea of individual hybrid encoding, the cuckoo search over a continuous space is transformed into the synchronous evolution search over discrete space. Subsequently, the concept of confidence interval (CI) is introduced; hence, the new position updating is designed and genetic mutation with a small probability is introduced. The former enables the population to move towards the global best solution rapidly in every generation, and the latter can effectively prevent the ICS from trapping into the local optimum. Furthermore, the greedy transform method is used to repair the infeasible solution and optimize the feasible solution. Experiments with a large number of KP instances show the effectiveness of the proposed algorithm and its ability to achieve good quality solutions. 1. Introduction The combinatorial optimization plays a very important role in operational research, discrete mathematics, and computer science. The knapsack problem is one of the classical combinatorial optimization problems that are difficult to solve and it has been extensively studied since the pioneering work of Dantzig [1]. Generally speaking, if the classification of these methods that are used to solve such problems is based on the nature of the algorithm, they can be simply divided into two categories [2]: exact methods and heuristic methods. Exact methods, like enumeration method [3, 4], branch and bound [5], and dynamic programming [6], can give the exact solutions; nevertheless, in the worst case, it is required to take a long time to get a satisfactory solution; sometimes the time increases exponentially with the increment of the size of the instance. Recently, nature-inspired metaheuristic algorithms perform powerfully and efficiently in solving the diverse optimization problems, including combinatorial problem. Metaheuristic algorithms include genetic algorithm [7], particle swarm optimization [8], ant colony optimization [9], artificial bee colony algorithm [10], differential evolution algorithm [11], harmony search algorithm [12, 13], and krill herd algorithm [14–16]. As is mentioned above, metaheuristic methods have been proven to be an effective means to cope with the combinatorial optimization problems including 0-1 knapsack
References
[1]
G. B. Dantzig, “Discrete-variable extremum problems,” Operations Research, vol. 5, no. 2, pp. 266–288, 1957.
[2]
L. Jourdan, M. Basseur, and E.-G. Talbi, “Hybridizing exact methods and metaheuristics: a taxonomy,” European Journal of Operational Research, vol. 199, no. 3, pp. 620–629, 2009.
[3]
A. V. Cabot, “An enumeration algorithm for knapsack problems,” Operations Research, vol. 18, no. 2, pp. 306–311, 1970.
[4]
R. J. W. James and Y. Nakagawa, “Enumeration methods for repeatedly solving Multidimensional Knapsack sub-problems,” IEICE Transactions on Information and Systems, vol. 88, no. 10, pp. 2329–2340, 2005.
[5]
P. J. Kolesar, “A branch and bound algorithm for the knapsack problem,” Management Science, vol. 13, no. 9, pp. 723–735, 1967.
[6]
S. Martello, Knapsack Problem: Algorithms and Computer Implementations, John Wiley & Sons, New York, NY, USA, 1990.
[7]
F.-T. Lin, “Solving the knapsack problem with imprecise weight coefficients using genetic algorithms,” European Journal of Operational Research, vol. 185, no. 1, pp. 133–145, 2008.
[8]
J. C. Bansal and K. Deep, “A modified binary particle swarm optimization for knapsack problems,” Applied Mathematics and Computation, vol. 218, no. 22, pp. 11042–11061, 2012.
[9]
M. Kong, P. Tian, and Y. Kao, “A new ant colony optimization algorithm for the multidimensional Knapsack problem,” Computers and Operations Research, vol. 35, no. 8, pp. 2672–2683, 2008.
[10]
M. H. Kashan, N. Nahavandi, and A. H. Kashan, “DisABC: a new artificial bee colony algorithm for binary optimization,” Applied Soft Computing Journal, vol. 12, no. 1, pp. 342–352, 2012.
[11]
L. Wang, X. Fu, Y. Mao, et al., “A novel modified binary differential evolution algorithm and its applications,” Neurocomputing, vol. 98, pp. 55–75, 2012.
[12]
D. Zou, L. Gao, S. Li, and J. Wu, “Solving 0-1 knapsack problem by a novel global harmony search algorithm,” Applied Soft Computing Journal, vol. 11, no. 2, pp. 1556–1564, 2011.
[13]
L. H. Guo, G. G. Wang, H. Wang, et al., “An effective hybrid firefly algorithm with harmony search for global numerical optimization,” The Scientific World Journal, vol. 2013, Article ID 125625, 9 pages, 2013.
[14]
G. G. Wang, A. H. Gandomi, and A. H. Alavi, “An effective krill herd algorithm with migration operator in biogeography-based optimization,” Applied Mathematical Modelling, 2013.
[15]
G. G. Wang, A. H. Gandomi, and A. H. Alavi, “Stud krill herd algorithm,” Neurocomputing, 2013.
[16]
G. G. Wang, L. H. Guo, H. Wang, et al., “Incorporating mutation scheme into krill herd algorithm for global numerical optimization,” Neural Computing and Applications, 2012.
[17]
X.-S. Yang and S. Deb, “Cuckoo search via Lévy flights,” in Proceedings of the IEEE World Congress on Nature and Biologically Inspired Computing (NABIC '09), pp. 210–214, December 2009.
[18]
X.-S. Yang and S. Deb, “Engineering optimisation by cuckoo search,” International Journal of Mathematical Modelling and Numerical Optimisation, vol. 1, no. 4, pp. 330–343, 2010.
K. Chaowanawate and A. Heednacram, “Implementation of cuckoo search in RBF neural network for flood forecasting,” in Proceedings of the 4th International Conference on Computational In-telligence, Communication Systems and Networks, pp. 22–26, 2012.
[21]
V. R. Chifu, C. B. Pop, I. Salomie, D. S. Suia, and A. N. Niculici, “Optimizing the semantic web service composition process using Cuckoo Search,” Intelligent Distributed Computing V, vol. 382, pp. 93–102, 2011.
[22]
K. Choudhary and G. N. Purohit, “A new testing approach using cuckoo search to achieve multi-objective genetic algorithm,” Journal of Computing, vol. 3, no. 4, pp. 117–119, 2011.
[23]
M. Dhivya, M. Sundarambal, and L. N. Anand, “Energy efficient computation of data fusion in wireless sensor networks using cuckoo based particle approach (CBPA),” International Journal of Computer Networks and Security, vol. 4, no. 4, pp. 249–255, 2011.
[24]
A. Gherboudj, A. Layeb, and S. Chikhi, “Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm,” International Journal of Bio-Inspired Computation, vol. 4, no. 4, pp. 229–236, 2012.
[25]
A. Layeb, “A novel quantum inspired cuckoo search for knapsack problems,” International Journal of Bio-Inspired Computation, vol. 3, no. 5, pp. 297–305, 2011.
[26]
X. S. Yang and S. Deb, “Cuckoo search: recent advances and applications,” Neural Computing and Applications, 2013.
[27]
T. K. Truong, K. Li, and Y. M. Xu, “Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem,” Applied Soft Computing, vol. 13, no. 4, pp. 1774–1780, 2013.
[28]
Y. C. He, X. Z. Wang, and Y. Z. Kou, “A binary differential evolution algorithm with hybrid encoding,” Journal of Computer Research and Development, vol. 44, no. 9, pp. 1476–1484, 2007.
[29]
E. G. Talbi, Metaheuristics: From Design To Implementation, John Wiley & Sons, New York, NY, USA, 2009.
[30]
J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in Proceedings of the IEEE International Conference on Computational Cybernetics and Simulation, vol. 5, pp. 4104–4108, October 1997.
[31]
J. Zhao, T. Huang, F. Pang, and Y. Liu, “Genetic algorithm based on greedy strategy in the 0-1 knapsack problem,” in Proceedings of the 3rd International Conference on Genetic and Evolutionary Computing (WGEC '09), pp. 105–107, October 2009.
[32]
Y. C. He, K. Q. Liu, and C. J. Zhang, “Greedy genetic algorithm for solving knapsack problems and its applications,” Computer Engineering and Design, vol. 28, no. 11, pp. 2655–2657, 2007.
[33]
A. P. Engelbrecht, Fundamentals of Computational Swarm Intelligence, John Wiley & Sons, Hoboken, NJ, USA, 2009.
[34]
H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, Springer, Berlin, Germany, 2004.
