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 . 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 : exact methods and heuristic methods. Exact methods, like enumeration method [3, 4], branch and bound , and dynamic programming , 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 , particle swarm optimization , ant colony optimization , artificial bee colony algorithm , differential evolution algorithm , 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
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.
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.
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.
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.
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.
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.
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.
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.