A DNA Computing Algorithm for Solving the Knapsack Problem

被引：0
作者：
Ye, Lian [1 ]
机构：
[1] Chongqing Univ, Dept Comp, Chongqing, Peoples R China
来源：
INFORMATION AND BUSINESS INTELLIGENCE, PT II | 2012年 / 268卷
关键词：
0-1 knapsack problem; DNA computing; Optimization;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Knapsack problem is a classical NP-Complete problem. In this paper, a DNA computing algorithm is proposed to find out the optimal solution of 0-1 knapsack problem. The DNA encoding method is described to translate the weight and value of items into DNA stands. Then replicated the stands and took the combination of every DNA stand to form double stranded DNA sequences in order to find out the optimal solution. The proposed DNA encoding method is an improvement on the previous ones, and it provides further evidence for the ability of DNA computing to solve numerical optimization problems.
引用
收藏
页码：84 / 90
页数：7
相关论文
共 6 条
  • [1] MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS
    ADLEMAN, LM
    [J]. SCIENCE, 1994, 266 (5187) : 1021 - 1024
  • [2] Solution of the knapsack problem by deoxyribonucleic acid computing
    Aoi, Y
    Yoshinobu, T
    Tanizawa, K
    Kinoshita, K
    Iwasaki, H
    [J]. JAPANESE JOURNAL OF APPLIED PHYSICS PART 1-REGULAR PAPERS SHORT NOTES & REVIEW PAPERS, 1998, 37 (10): : 5839 - 5841
  • [3] Grosan C, 2004, IEEE C EVOL COMPUTAT, P1958
  • [4] DNA computing of solutions to knapsack problems
    Henkel, Christiaan V.
    Back, Thomas
    Kok, Joost N.
    Rozenberg, Grzegorz
    Spaink, Herman P.
    [J]. BIOSYSTEMS, 2007, 88 (1-2) : 156 - 162
  • [5] DNA SOLUTION OF HARD COMPUTATIONAL PROBLEMS
    LIPTON, RJ
    [J]. SCIENCE, 1995, 268 (5210) : 542 - 545
  • [6] Majid D, 2007, MATH COMPUT, V188, P1991
1