Computer Science ›› 2018, Vol. 45 ›› Issue (7): 73-77.doi: 10.11896/j.issn.1002-137X.2018.07.011

• NCIS 2017 • Previous Articles     Next Articles

Greedy Frog Leaping Algorithm for 01 Knapsack Problem

GAO Si-qi,XING Yu-xuan,XIAO Nong,LIU Fang   

  1. School of Computer,National University of Defense Technology,Changsha 410073,China
  • Received:2017-07-18 Online:2018-07-30 Published:2018-07-30

Abstract: 01 knapsack problem(01kp) is a classic combinatorial optimization problem and appears in many models of real world problem,such as cargo loading,budget control,resource allocation,financial management,and so forth.Many scientists have studied on this area for several decades and achieved a rich harvest.Even though 01kp has been researched for many years,it has been proved to be an NP complete problem,thus finding the best solution is not easy.In recent years,many original and improved intelligent algorithms was proposed to address 01 knapsack problem,for instance,chemical reaction optimization algorithm,genetic algorithm,particle swarm optimization algorithm,shuffled frog leaping algorithm,artificial bee colony algorithm,hill climbing algorithm and simulated annealing algorithm.This paper studied on many intelligent algorithms and 01 knapsack problems,and proposed greedy frog leaping algorithm (GFLA) to solve 01kp.Different from original shuffled frog leaping algorithm,GFLA always updates global best solution during each memeplex process,such that global exploration would employ the latest global best solution to expand the search space.In addition to traditional global exploration and local exploitation,aiming at 01kp,it proposed a greedy scheme at fitness computing stage,including drop and add two steps.At drop step,if the knapsack is over-weighted,then the item with minimum value density is removed from the knapsack and the solution is updated.At add step,if there is still space for the knapsack to load items,then items with minimum weight which have not been loaded are put into the knapsack and solution is also updated.Drop and add steps adopted in our work greatly improve greedy frog leaping algorithm’s ability to address 01kp.This paper conducted the experiments on benchmarks,and compared the results with chemical reaction optimization algorithm,genetic algorithm,quantum-inspired evolutionary algorithm,chemical reaction optimization with greedy strategy.All experimental results show that greedy frog leaping algorithm obtains the best solutions in all cases,which indicates that GFLA is an efficient algorithm to address 01 knapsack problem.

Key words: 01 knapsack problem, Greedy scheme, Value density, Min-allocate, Frog leaping algorithm

CLC Number: 

  • TP301
[1]LAGOUDAKIS,MICHAIL G.The 0-1 knapsack problem--An introductory survey .https://pdfs.semanticscholar.org/6bd6/2e0ba7233c5086fe4b9061926d191894714b.pdf. [2]SAHNI S.Approximate Algorithms for the 0/1 Knapsack Problem.Journal of the Acm,1975,22(1):115-124.SHI H.Solution to 0/1 knapsack problem based on improvedant colony algorithm∥2006 IEEE International Conference on Information Acquisition.IEEE,2006:1062-1066.
[4]YAN C,GAO S,LUO H,et al.A hybrid algorithm based on tabu search and chemical reaction optimization for 0-1 Knapsack problem∥International Conference in Swarm Intelligence.Springer,Cham,2015:229-237.
[5]HAN K H,KIM J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization.IEEE Transactions on Evolutionary Computation,2002,6(6):580-593.
[6]SHEN W,XU B,HUANG J P.An Improved Genetic Algorithm for 0-1 Knapsack Problems∥International Conference on NETWORKING & Distributed Computing.IEEE Computer Society,2011:32-35.
[7]TRUONG T K,LI K,XU Y.Chemical reaction optimizationwith greedy strategy for the 0-1 knapsack problem.Applied Soft Computing Journal,2013,13(4):1774-1780.
[8]EUSUFF M,LANSEY K,PASHA F.Shuffled frog-leaping algorithm:a memetic meta-heuristic for discrete optimization.Engineering Optimization,2006,38(2):129-154.
[1] WEI Lin-jing, NING Lu-lu, GUO Bin, HOU Zhen-xing, GAN Shi-run. K-mediods Cluster Mining and Parallel Optimization Based on Shuffled Frog Leaping Algorithm [J]. Computer Science, 2020, 47(10): 126-129.
[2] ZHANG Xin-ming, CHENG Jin-feng, KANG Qiang, WANG Xia. Improved Shuffled Frog Leaping Algorithm and Its Application in Multi-threshold Image Segmentation [J]. Computer Science, 2018, 45(8): 54-62.
[3] GUO Yuan-hua and ZHOU Xian-lin. Random-valued Impulse Noise Detection Based on Pixel-valued Density and Four Directions [J]. Computer Science, 2016, 43(Z11): 220-222.
[4] MI Xiao-ping and LI Xue-mei. Mining Algorithm of Frequency Domain Migration Intrusion Feature Based on Information Fusion Transfer [J]. Computer Science, 2015, 42(3): 224-227.
[5] LIU Xiao-qin,HUANG Kao-li,AN You-lin,LU Xiao-ming. Application of Improved Shuffled Frog Leaping Algorithm in Optimum of Sensor Location [J]. Computer Science, 2011, 38(2): 72-75.
[6] HAN Yi,CAI Jian-hu,ZHOU Gen-gui,LI Yan-lai,LIN Hua-zhen,TANG Jia-fu. Advances in Shuffled Frog Leaping Algorithm [J]. Computer Science, 2010, 37(7): 16-19.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .