Lv, J, Wang, X, Huang, M, Cheng, H and Li, F (2016) Solving 0-1 Knapsack Problem by Greedy Degree and Expectation Efficiency. Applied Soft Computing, 41. pp. 94-103. ISSN 1872-9681

Preview

Text manuscript-knapsack-ASC.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (963kB) | Preview

Abstract

It is well known that 0-1 knapsack problem (KP01) plays an important role in both computing theory and real life application. Due to its NP-hardness, lots of impressive research work has been performed on many variants of the problem. Inspired by region partition of items, an effective hybrid algorithm based on greedy degree and expectation efficiency (GDEE) is presented in this paper. In the proposed algorithm, initially determinate items region, candidate items region and unknown items region are generated to direct the selection of items. A greedy degree model inspired by greedy strategy is devised to select some items as initially determinate region. Dynamic expectation efficiency strategy is designed and used to select some other items as candidate region, and the remaining items are regarded as unknown region. To obtain the final items to which the best profit corresponds, static expectation efficiency strategy is proposed whilst the parallel computing method is adopted to update the objective function value. Extensive numerical investigations based on a large number of instances are conducted. The proposed GDEE algorithm is evaluated against chemical reaction optimization algorithm and modified discrete shuffled frog leaping algorithm. The comparative results show that GDEE is much more effective in solving KP01 than other algorithms and that it is a promising tool for solving combinatorial optimization problems such as resource allocation and production scheduling.

Item Type:	Article
Uncontrolled Keywords:	0102 Applied Mathematics, 0801 Artificial Intelligence And Image Processing, 0806 Information Systems
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	Computer Science & Mathematics
Publisher:	Elsevier
Date Deposited:	14 Mar 2016 12:31
Last Modified:	02 Aug 2022 15:38
DOI or ID number:	10.1016/j.asoc.2015.11.045
URI:	https://researchonline.ljmu.ac.uk/id/eprint/3199

View Item