loading...
DNA Computing Model for the 0/1 Knapsack Problem
Auckland, New Zealand December 13-December 15
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HIS.2006.21Sixth International Conference on Hyb ...
 This Article 
 
PDF
HTML
IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Aili Han, IEEE member; Shandong University at Weihai, China; Shandong University, Jinan, China
We have devised a DNA encoding method and a corresponding DNA algorithm for the 0/1 knapsack problem. Suppose that item set I={1,2 ... n}, profit set P={p_1,p_2,...,p_n}, weight set W={w_1,w_2,...,w_n}, and knapsack capacity is c. We use two DNA strands s_i1 and s_i2 to encode each item i, where the DNA strand s_i1 is with a length of wi whose center part is with a length of p_i, and the DNA strand s_i2 is the reverse complement of the center part of s_i1. For any two items i,j we add one DNA strand s_aij as an additional code, which is the reverse complement of the last part of s_i1 and the first part of s_j1. 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.
Citation:
Aili Han, "DNA Computing Model for the 0/1 Knapsack Problem," his, pp.18, Sixth International Conference on Hybrid Intelligent Systems (HIS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.