Lv, J and Wang, X and Huang, M and 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
manuscript-knapsack-ASC.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.
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.
|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
|Date Deposited:||14 Mar 2016 12:31|
|Last Modified:||31 Dec 2016 00:50|
|DOI or Identification number:||10.1016/j.asoc.2015.11.045|
Actions (login required)