%0 Journal Article
%T An Improved Hybrid Encoding Cuckoo Search Algorithm for 0-1 Knapsack Problems
%A Yanhong Feng
%A Ke Jia
%A Yichao He
%J Computational Intelligence and Neuroscience
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/970456
%X 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¨C16]. 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
%U http://www.hindawi.com/journals/cin/2014/970456/