Appl. Math. Inf. Sci. 8, No. 1, 139-144 (2014) 139
Applied Mathematics & Information Sciences
An International Journal
http://dx.doi.org/10.12785/amis/080117
Simulation DNA Algorithm of Set Covering Problem
Kang Zhou
∗
and Jin Chen
School of Math and Computer, Wuhan Polytechnic University, Wuhan 430023, P. R. China
Received: 3 Jun. 2013, Revised: 17 Sep. 2013, Accepted: 18 Sep. 2013
Published online: 1 Jan. 2014
Abstract: Sticker model is imitated by using set, variable length vector and biochemistry operator instead of tube, memory strand and
biochemistry experiment for the first time. Batch separation operator and electrophoresis operator are first put forward based on DNA
algorithm of Set Covering Problem (SCP) based on sticker model. Expression way, calculation method and basic properties of variable
length vector and the two biochemistry operators are analyzed in detail according to the characteristics of sticker model. Simulation
DNA algorithm (SDA) of SCP, which can find out all optimization set coverings, is designed, where all feasible set coverings are
extracted by using batch separation operator and all optimization set coverings are extracted by using electrophoresis operator. Minimal
element and deriving element are first introduced. And minimal element contains a large amount of deriving elements, so the set of
batch separation operator can be simplified. Less-than relation is established to simplify the set of electrophoresis operator. Therefore
the use of ’minimal element’ and ’less-than’ makes SDA of SCP more effective and practical. Time complexity of SDA of SCP is
proved, and it shows that SDA of SCP is an effective algorithm to solve SCP.
Keywords: sticker model, SDA, SCP, batch separation operator, electrophoresis operator, minimal element, less-than relation
1 Introduction
The application range of Set Covering Problem (SCP) is
wide [
1], articularly, SCP has an important application in
the field of optimalization of traffic network [
2,3] and the
Vehicle Routing Problem (VRP) [
4,5,6]. SCP is a famous
NP-complete problem. Domestic and foreign scholars put
forward heuristic search for solving SCP, such as genetic
algorithm [
7], ant colony algorithm [8], simulated
annealing algorithm [
9], evolutionary search algorithm
[
10] and so on. These algorithms can only obtain the
suboptimal solution of SCP. In 2010, Zhou K designed
closed circle DNA algorithm [
11] of SCP to obtain all the
optimization solutions of SCP by using high parallelism
and huge storage capacity of DNA computing, and
operating times of the DNA algorithm is linear. However,
the calculation scale of DNA computing is limited
because of DNA encoding problem, therefore, it is a
significant subject to solve SCP by borrowing thought of
DNA computing.
In 2009, Zhou K first put forward simulation DNA
algorithm (SDA) [
12] based on thought of DNA
computing by using the properties of solutions of Eight
Queens Problem(EQP) to obtain all solutions of EQP.
Therefore, in order to study SCP, SDA based on sticker
model [13,14] is used in the paper, and the method of
solving SCP is found out to obtain all solutions of SCP.
Meanwhile, in the SDA, batch separation operator and
electrophoresis operator are first put forward, and
simplification algorithms for the two operators are given.
2 DNA Algorithm of SCP
2.1 Introduction of Sticker Model
Computing subjects of sticker model [
13,14] are
composed of two types of substances, which are memory
strand and separation glass.
(1) Memory strand is single strand DNA molecular.
DNA encoding on position i (i = 1, 2, · ·· , n) of memory
strand is c
i
or b
i
, where c
i
is composed of d
i
and e
i
, and
|c
i
| = |d
i
e
i
| = |d
i
||e
i
|,|d
i
| = |b
i
|.
(2) Separation glass i stores single strand DNA d
′
i
which is the Watson-Crick complementary sequences of
DNA encoding d
i
.
Biochemistry experiments of sticker model are merge
experiment, separation experiment, batch separation
experiment, electrophoresis experiment and detection
experiment.
(1) Merge experiment: combine memory strands of
tube S
1
and tube S
2
into tube S.
∗
Corresponding author e-mail:
zhoukang wh@163.com
c
2014 NSP
Natural Sciences Publishing Cor.