TY - JOUR
T1 - Solving 0-1 knapsack problems based on amoeboid organism algorithm
AU - Zhang, Xiaoge
AU - Huang, Shiyan
AU - Hu, Yong
AU - Zhang, Yajuan
AU - Mahadevan, Sankaran
AU - Deng, Yong
N1 - Funding Information:
The authors thank the anonymous reviewer for the valuable comments and suggestions to improve this paper. The Ph.D. candidate of the corresponding author in Shanghai Jiao Tong University, Peida Xu, give some discussions on the algorithm. The work is partially supported Chongqing Natural Science Foundation , Grant No. CSCT, 2010BA2003 , National Natural Science Foundation of China , Grant Nos. 61174022 and 71271061 , National High Technology Research and Development Program of China (863 Program) (No. 2013AA013801 ), Science and Technology Planning Project of Guangdong Province, China (2010B010600034, 2012B091100192), Business Intelligence Key Team of Guangdong University of Foreign Studies (TD1202), the Fundamental Research Funds for the Central Universities Grant No. XDJK2013D010 .
PY - 2013
Y1 - 2013
N2 - The 0-1 knapsack problem is an open issue in discrete optimization problems, which plays an important role in real applications. In this paper, a new bio-inspired model is proposed to solve this problem. The proposed method has three main steps. First, the 0-1 knapsack problem is converted into a directed graph by the network converting algorithm. Then, for the purpose of using the amoeboid organism model, the longest path problem is transformed into the shortest path problem. Finally, the shortest path problem can be well handled by the amoeboid organism algorithm. Numerical examples are given to illustrate the efficiency of the proposed model.
AB - The 0-1 knapsack problem is an open issue in discrete optimization problems, which plays an important role in real applications. In this paper, a new bio-inspired model is proposed to solve this problem. The proposed method has three main steps. First, the 0-1 knapsack problem is converted into a directed graph by the network converting algorithm. Then, for the purpose of using the amoeboid organism model, the longest path problem is transformed into the shortest path problem. Finally, the shortest path problem can be well handled by the amoeboid organism algorithm. Numerical examples are given to illustrate the efficiency of the proposed model.
KW - 0-1 Knapsack problem
KW - Bio-inspired algorithm
KW - Network converting algorithm
KW - Optimization
KW - Shortest path problem
UR - http://www.scopus.com/inward/record.url?scp=84877341037&partnerID=8YFLogxK
U2 - 10.1016/j.amc.2013.04.023
DO - 10.1016/j.amc.2013.04.023
M3 - Journal article
AN - SCOPUS:84877341037
SN - 0096-3003
VL - 219
SP - 9959
EP - 9970
JO - Applied Mathematics and Computation
JF - Applied Mathematics and Computation
IS - 19
ER -