TELKOM
NIKA
, Vol. 11, No. 6, June 20
13, pp. 3187
~ 319
3
e-ISSN: 2087
-278X
3187
Re
cei
v
ed
De
cem
ber 2
8
, 2012; Re
vi
sed
April 3, 2013;
Accept
ed Ap
ril 18, 2013
A Personification Heuristic Genetic Algorithm for
Digital Microfluidics-based Biochips Placement
Jingsong Ya
ng
Institute of Disaster Preventi
o
n Sci
enc
e an
d T
e
chnolog
y, S
anh
e, Chi
n
a
e-mail: ya
ngj
in
gson
g@ci
dp.e
du.cn
A
b
st
r
a
ct
A person
i
ficati
on he
uristic
Genetic Alg
o
ri
thm is esta
bli
s
hed for the
place
m
ent o
f
digit
a
l
micr
oflui
d
ics-b
a
sed
bioc
hi
ps, in w
h
ic
h, the
p
e
rson
ificatio
n h
euristic a
l
g
o
rith
m is
used to c
o
ntrol the
packi
n
g
process, w
h
ile
the gen
etic alg
o
rith
m
is desi
g
ned to be us
ed
in multi-
ob
je
cti
v
e p
l
ace
m
ent r
e
sults
opti
m
i
z
i
ng.
As an exa
m
pl
e
,
the process
of micr
oflui
d
ic
mo
du
le p
h
ysic
a
l pl
ace
m
ent
i
n
multip
lex
ed i
n
-vitro di
ag
nos
tics
on
hu
ma
n
phy
siolo
g
ic
al fl
ui
d
s
is si
mul
a
ted.
T
he
exper
i
m
ent res
u
lts sh
ow
that
p
e
rso
n
ificati
on he
uri
s
tic
gen
etic a
l
g
o
rit
h
m ca
n ac
hi
e
v
e b
e
tter resu
lts in
mult
i-
obj
ective
opti
m
i
z
ation, c
o
mpar
e to th
e
para
l
le
l
reco
mbi
nativ
e simulat
ed an
ne
alin
g al
gorit
hm.
Ke
y
w
ords
: pe
rsonific
a
tion
h
euristic a
l
gor
ithm
, g
en
etic a
l
gorit
hm
, d
igit
al microfl
u
id
ic
s-base
d
bi
ochi
ps
,
plac
e
m
ent
Copy
right
©
2012 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Digital mi
crofluidics-ba
sed
biochip
s
, whi
c
h
are
wi
dely
used in
mo
re an
d mo
re
different
fields, su
ch
as an
alytical
chemi
s
try, clini
c
diag
no
sis, biol
ogy manufa
c
tory,
environm
en
tal
monitor,
and
military [1-3
]. As bio
c
hip
s
a
r
e
adopt
ed for compl
e
x pro
c
e
dure
s
in
mole
cul
a
r
biology, the
desi
gn
compl
e
xity of digital micro
fl
uidi
cs-ba
s
e
d
bio
c
hip
s
i
s
expe
cted to in
cre
a
se
due to the need of multiple and co
ncu
rre
nt assays
on a biochip.
The internati
onal tech
nolo
g
y
road
map
for semi
con
d
u
c
tors (ITRS) cl
early
point
s
out that the integratio
n
of electro-biolog
ical
device
s
i
s
o
n
e
of the m
a
j
o
r
chall
enge
s of sy
ste
m
in
tegration
bey
ond 2
009. T
h
e pla
c
em
ent
o
f
digital mi
crofluidics-ba
sed
biochip
s
i
s
o
n
e
of th
e
key p
o
ints i
n
the
chip d
e
si
gn, th
roug
h
whi
c
h
the
physi
cal po
sition of each bi
och
e
mical an
alysis op
eration can b
e
found with the
smalle
st bio
c
hip
area
and th
e
sho
r
test
com
p
letion. The
a
l
gorithm fo
r th
e pla
c
eme
n
t has
bee
n pai
d gre
a
t attenti
on
by different grou
ps. Su a
nd Ch
akrab
a
r
ty presented
a uni
fi
ed
synthesi
s
an
d placement
fl
ow
based
on
pa
rallel recombi
native si
mula
ted an
neali
n
g
.
They u
s
e
d
the list
-
sch
e
d
u
ling
algo
rith
m
for sche
dulin
g and a g
r
ee
dy place
m
ent
algorithm fo
r physical pla
c
ement [4-6].
The pla
c
em
e
n
t is
some
ho
w n
o
t
very com
p
acted
and
cannot m
eet
a
ll de
sign
sp
ecification
s
. While th
e T
-
tree
formulatio
n d
e
velope
d by
Yuh etc. fro
m
Taiwa
n
Un
ivers
i
ty [7, 8] shows
better res
u
lt
s
with
a tree-
based topol
o
g
ical rep
r
e
s
e
n
tation, but the com
p
letio
n
time is not
so goo
d du
e to the large
amount of cal
c
ulatio
ns n
e
e
ded an
d that is time-con
su
ming.
The pla
c
eme
n
t
of
digital
microfluidi
c
s-based ch
i
p
i
s
an
optimi
z
ati
on of
multi-o
b
jective
s
.
In this article,
we combi
ne
personifi
catio
n
heuri
s
tic al
gorithm with
geneti
c
algo
rithm to solve the
placement problem.Th
e
result
s sho
w
e
d
a better biochi
p are
a
and sho
r
ter
completion ti
me,
comp
are to the parall
e
l re
combinative si
mulated an
ne
aling algo
rith
m and T-tree.
2. The Place
ment of Micr
ofluidic-b
as
ed Biochips
The p
r
o
c
ed
ure of the pla
c
ement of mi
crofluidi
c
-ba
s
e
d
bio
c
hip
s
i
s
sho
w
n
as
Fi
gure
1.
There a
r
e
three in
puts to t
he pl
acement
problem.
Th
e first on
e i
s
t
he
seq
uen
cin
g
g
r
aph
G
= {
V
,
E
} that rep
r
e
s
ent
s the
p
r
o
t
ocol
of a
bio
a
ssay, where
V
= {
v
1
,
v
2
, .
. . ,
v
m
}
r
e
pr
es
e
n
t
s
a se
t o
f
m
assay ope
rati
ons a
nd
E
= {(
v
i
,
v
j
), 1
≤
i
,
j
≤
m
} denotes the data
depen
den
cie
s
between two
assay ope
rati
ons; i.e., the
pre
c
ed
en
ce constraints
.
We may need
at most one
stora
ge u
n
it for
each edge in
G
to store the interme
d
i
a
te data betwee
n
two da
ta-dep
end
ent
operatio
ns .
The
se
con
d
one i
s
the microflu
idic mod
u
le li
bra
r
y that co
ntains the b
a
s
ic mo
dule
s
for bio
c
hip
s
. Each
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No. 6, June 20
13 : 3187 – 3
193
3188
basi
c
mo
dule
is ch
ara
c
te
rized by its fu
nction
ality
(i.e., mix, dilution, etc.) an
d
param
eters
(i.e.,
width, heig
h
t, and ope
ratio
n
duratio
n). T
he third on
e is the de
sign
spe
c
ification, inclu
d
ing:
(
1
) th
e
fixe
d ar
c
h
itec
tur
e
(su
c
h as
10
×1
0 a
r
r
a
y) a
n
d
limite
d
ass
a
y
co
mp
le
tio
n
time
(s
uc
h
as 36
0 se
co
n
d
s)
(2) th
e maxi
mum nu
mbe
r
of instan
ce
s
for ea
ch type
of non
-re
co
nfigura
b
le d
e
vices(su
ch
as dete
c
tor a
nd dispen
sin
g
ports); t
hat is, the re
sou
r
ce con
s
trai
nts.
The pla
c
e
m
e
n
t of module
s
on the
microfluidic a
r
ray can
be mo
de
led a
s
a 3
-
D
packin
g
probl
em. Ea
ch mi
croflui
d
ic mod
u
le i
s
re
pre
s
ente
d
by
a 3
-
D b
o
x, the b
a
se of
which
de
note
s
the
recta
ngul
ar
a
r
ea of the
m
odule
and th
e heig
h
t
den
otes the tim
e
-span
of its operation. T
h
e
microfluidi
c
b
i
ochi
p pla
c
e
m
ent can n
o
w
be
view
ed
as th
e p
r
obl
em of pa
ckin
g these b
o
xe
s to
minimize the total base a
r
e
a
, while avoid
i
ng overla
ps.
Figure 1. Pro
c
ed
ure of the
Pl
acem
ent Problem of Biochips
3. Personific
a
tion Heuristic Genetic
Algorithm
Personificatio
n
heuri
s
tic
g
enetic al
gorit
hm is form
ul
ated ba
sed
on the sim
u
l
a
tion o
f
natural
optim
ization
law,
whi
c
h
ha
s some a
d
vant
a
ges of
solvin
g the
optimization of th
e
3-D
packin
g
pro
b
l
e
ms, e
s
pe
cia
lly when for t
he large-sc
al
e pro
b
lem
s
with great com
p
lexity. In order
to obtain a more comp
act
placement la
yout, we
com
b
ine the pe
rsonificatio
n
he
uristi
c algo
rithm
with the gene
tic algorithm.
Personificatio
n
heuri
s
tic
al
gorithm is u
s
ed to control t
he placeme
n
t o
f
the modul
es,
and the
n
o
p
timize the
p
l
acem
ent re
sults of the m
u
ltiple obj
ecti
ves by ge
net
ic
algorith
m
in orde
r to achiev
e the goal of smalle
st
microfluidic a
rray
area a
nd sho
r
test completi
on
time. The ke
y points of g
enetic
algo
rithm are t
he d
e
sig
n
of en
coding
and th
e sel
e
ctio
n of
the
fitnes
s
func
tion [9].
3.1. Personification Heuri
s
tic Algori
t
h
m
As we kno
w
, the efficien
cy
of perso
nificati
on he
uri
s
tic ap
plication
wa
s firstly proved on
the three
-
dim
ensi
onal p
a
cking problem [
10]. In the co
nstru
c
tion
of building
s
, workers al
way
s
set
a b
r
ick
as the
refe
ren
c
e
of
height
wh
en
wall
s a
r
e
built
. The
heig
h
t
of othe
r b
r
icks
can
not ex
ceed
that of the
ref
e
ren
c
e
b
r
ick
until no
othe
r bri
c
k
can be
build
in, whe
n
ne
w height referen
c
e bri
c
k
need to be
set. In addition, this enligh
t
ens the re
searche
r
s to set “referen
ce bri
c
ks” i
n
both
hori
z
ontal
an
d vertical
dire
ction
s
a
s
the
guide of
the
module
pla
c
ement in di
gital microfluidi
c
s-
based
bio
c
hi
ps. T
he
po
sitions of di
gital
microflu
idi
c
module
s
ca
n be re
corded
and
fo
und
by
the
Evaluation Warning : The document was created with Spire.PDF for Python.
TEL
K
A
P
refer
e
plac
e
micr
o
lines
.
3.1.1
dime
widt
h
must
we d
coo
r
d
archi
t
digit
a
impl
e
will
b
thus
sup
p
o
(
l
1
′
, 0
point
of th
micr
o
the p
z
) ad
3.1.2
on t
h
coo
r
d
set
i
n
Our
m
to th
e
coo
r
d
coo
r
d
can
b
mod
u
posit
i
Plac
e
posit
i
way
s
hori
z
o
K
OM
NIKA
P
ersonifi
ca
ti
o
e
n
c
e po
inte
d
e
ment re
sul
t
o
fluidi
c mod
u
.
. Selection
o
A
s sh
ow
n
ns
io
na
l c
o
o
r
h
, height
as
x
be as cl
ose
es
ig
ne
d a
m
d
in
ates o
f
th
e
Figur
The sta
r
t
t
ectu
re
-l
evel
a
l mi
crof
luid
e
me
ntation
a
b
e
l
i
′
,
w
i
′
,
h
i
′
.
T
th
e second
o
se t
he se
c
o
, 0) s
h
ould
b
(
l
1
′
+
l
2
′
, 0,
0
e th
ree
po
s
o
fluidi
c mod
u
o
s
sible
posi
t
ded, sho
w
n
. Calibratio
n
In the pl
a
h
e total
c
o
m
d
in
ates o
f
th
e
n
the pla
c
e
m
m
o
dule plac
e
e
sche
du
ling
d
in
ates i
n
in
c
d
in
ates i
n
in
c
b
e locate
d i
n
u
le
b
i
wit
h
o
t
i
on
(
x
,
y
,
z
)
,
e
th
e m
odu
l
i
on
s
;
if no
p
s
:
(1) If
L
x
<
o
ntal ref
e
re
n
o
n Heu
r
isti
c
G
d
set befor
e
t
s ne
ede
d
a
u
le
s ca
n be
f
o
f Place
me
n
n
in
Figure
2
r
din
a
tion, in
w
x
,
y,
z,
re
s
p
e
c
as
po
ss
ib
le
m
ethod to r
e
e
bottom are
e 2. Coo
r
din
ing and
en
d
sched
uling
,
ic module
a
t time
t
=0,
t
h
T
he firs
t
dig
i
on
e
c
an
b
e
o
n
d
digita
l
m
b
e del
ete
fr
o
0
) and
(
l
1
′
,
w
2
s
itions: (0,
w
u
le located i
n
t
ion collectio
in Figu
re
3.
n
of the
Ref
e
a
cem
ent lay
o
m
pl
etion ti
me
e
maximum
l
m
ent layout:
t
e
ment po
lic
y
seque
nces,
c
re
asin
g or
d
c
rea
s
ing or
d
n
to one of th
t
he
r m
o
d
u
le
,
and
in t
he
l
e
bi into
t
h
p
ositio
n av
ail
<
L
, then in
c
n
ce m
odul
e,
a
e-I
G
eneti
c
Alg
o
e
h
and i
n
t
h
a
s in other
f
ini
s
he
d with
n
t Point
2
, the
microfl
w
hi
ch th
e
u
p
c
tively. Bas
e
to the axis
o
e
co
rd the p
o
used a
s
th
e
ate Syste
m
ing ti
me of
e
,
namely th
e
with the
s
h
e length
of
i
tal microflui
d
e
located i
n
t
o
m
icrofluidi
c
m
o
m the po
ssi
2
′
, 0) ne
ed t
o
w
1
′
, 0)
，
(
l
1
′
+
n
to pos
i
tion
(
n of
mod
u
l
e
e
ren
ce Li
n
e
o
ut of
digital
and th
e ar
l
ength, wid
t
h
t
he referen
c
y
is determi
n
for the
mod
d
e
r
, an
d th
e
d
e
r
; then, m
a
e locat
i
o
n
s
s
s in the
sa
m
me
antime
,
t
h
e firs
t pos
s
able, adj
ust
m
c
re
as
e th
e
r
a
nd if
L
y
<
L,
i
SSN: 2087
-
2
o
rithm for Di
g
h
e pla
c
em
e
n
design
s
. T
h
much m
o
r
e
uidi
c modul
e
p
per left cor
n
e
d on the ex
p
o
f co
ordinat
i
o
o
int that c
a
n
e
c
o
or
d
i
na
te
s
e
ach d
i
gital
m
e
po
sition o
f
ched
uling
s
digital micr
o
d
ic modul
e
c
o
the two
p
m
odule cho
o
s
ble p
o
sitio
n
s
o
be
ad
ded
s
+
l
2
′
, 0, 0)
a
(
x
,
y
,
z
), t
h
e
n
i
+1, an
d a
n
o
e
microfl
u
idic
-
ea of
micro
f
h
, height ha
s
c
e line
L
y
for
ed a
s
: plac
e
ule
b
i
, firs
tly
locations wi
a
ke the ju
d
g
s
orte
d. Note
m
e coo
r
di
n
a
t
t
he conditio
n
s
ib
l
e
po
s
i
ti
o
m
ent can
b
e
r
eferen
ce lin
i
ncre
ase the
2
78
X
g
ital Microflu
i
n
t procedu
r
e
h
us, the w
h
flexibilities
b
e
s of th
e bio
n
er of th
e bo
p
erie
nces, t
h
o
n, or to the
be placed
i
s
of the digit
a
Figure 3.
m
icroflui
dic
m
f
the modul
e
s
eque
n
ce o
f
o
fluidic mo
d
u
c
an b
e
pl
ac
e
ossibl
e po
si
s
e the point
s
lis
t for the
t
o that the
th
a
nd (
l
1
′
,
w
2
n
po
s
i
tion
(
x
,
o
ther t
w
o
po
s
-
ba
se
d b
i
oc
h
f
luidic array
s
their limits.
y
-axis a
nd
e
the digital
m
,
the possibl
e
th s
a
me
y
c
g
e that if th
e
that the int
e
t
e plate
mu
s
n
of
y
+
w
i
′≤
L
n and
upd
a
e
perfo
rmed
e of
x-
axis
,
refer
e
n
c
e li
n
i
di
cs-b
ased
.
e
and
no
s
h
ol
e place
m
b
y the
s
e
ttin
chip is
emb
e
tt
o
m
s
e
t
as
h
e current m
o
last module
i
n w
h
ich
th
e
a
l microfluidi
c
Available
P
m
o
dule
s
are
e
on the
z
-a
f
(
b
1
,
b
2
,
…
u
le
b
i
along t
h
e
d in
th
e po
i
n
tions
: (
l
1
′
, 0
,
of (
l
1
′
, 0, 0)
t
hird mo
dul
e
ird module
c
′
, 0).
There
f
,
y
,
z
) need
t
s
itions (
x
+
l
i
′
,
h
ip
s
,
th
er
e a
r
s
, i.e. the t
h
T
herefo
r
e,
t
w
the
L
x
for
x
-
m
icroflui
dic
m
e
locations
a
c
oordi
nate a
r
e
digital mic
r
e
rse
c
tion of
s
t be
avoid
w
L
y
,
x
+
l
i
′≤
L
x
a
te the coll
e
i
n
either of
and set t
h
n
e o
f
y
-ax
i
s.
..
(Ji
ngsong
s
pe
cia
l
r
e
qu
e
ent
of the
g
of the
ref
e
e
dd
ed into
a
o
r
igin, and l
e
o
dule to be
p
pla
c
ed
, th
e
r
e
u
pper-left
c
c
modules.
P
oint
s
de
te
r
m
ine
d
xi
s. Suppo
s
…
,
b
n
) sta
r
h
e
x,
y,
and
n
t of
(0, 0,
0
,
0)
o
r
(0,
w
, t
h
en the p
o
e
, and
an
oth
e
c
a
n
be
put in
t
f
ore, if the
t
o be del
e
te
d
y
,
z
) a
nd
(
x
,
r
e m
a
ximu
m
h
ree –dim
e
n
w
o
refer
e
n
c
e
-
axis
, r
e
s
p
e
c
m
o
dule
s
acc
o
a
re s
o
r
t
ed b
y
r
e
so
rted by
r
ofluidic mo
d
dig
i
tal micr
o
w
he
n lo
cat
e
m
u
st
b
e
sa
t
e
ction of p
o
the followi
n
h
e modul
e
a
Yan
g
)
3189
e
st
o
f
digital
e
re
nce
three
e
ng
th
,
p
laced
r
efo
r
e,
c
or
ne
r
by its
e that
r
ts its
z
-axis
), a
nd
w
1
′
, 0),
o
int
o
f
e
r t
w
o
t
o on
e
digi
tal
d
from
y
+
w
i
′
,
limits
sio
nal
e
lines
c
tiv
e
ly.
o
rdi
n
g
y
the
y
the
x
d
ul
e
b
i
o
fluidic
e
d in
t
o
t
isfi
ed.
o
ss
ible
n
g two
a
s t
h
e
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No. 6, June 20
13 : 3187 – 3
193
3190
(2) If there i
s
still no
po
sitio
n
availabl
e fo
r
the m
odul
e
after the
refe
rence line
in
creased,
postp
one
the
operation
of t
he di
gital mi
crofluidi
c
m
o
d
u
le a
n
d
put th
e d
r
opl
et into
the sto
r
a
ge
u
n
it
temporarily, and pro
c
e
s
s wi
th priority wh
en
sp
are p
e
ri
od available f
o
r the ope
rati
on.
3.1.3. Perso
n
ification
He
uristic Algor
ithm Flo
w
In con
c
lu
sion
, 3D-pl
a
ce
m
ent algorith
m
pro
c
e
ss i
s
given, the algorithm in
put
is an
orde
rly digital
microfluidi
c
module
set B
= {
b
1
,
b
2
,... ,
b
n
}, whe
r
e
T
rep
r
e
s
ent
s sche
duling
en
d
time of digital
microfluidi
c
module
s
,
I
re
pre
s
ent
s o
r
d
e
rly pla
c
e
poi
nt set. When
I
is up
dated,
we
sho
u
ld
ke
ep t
he o
r
d
e
r of I
element
s. If the
cu
rre
nt
di
gital
mi
croflui
d
ic mod
u
le can
b
e
placed,
the
symbol
flag
=1, otherwise the
flag
=0. Th
e time of placement is
t
, which i
s
mainly
used to find t
he
t
moment
ne
ed to
sta
r
t o
f
the layout
of the m
odul
e. The
flow
of pla
c
eme
n
t
algo
rithm i
s
as
follows
:
3D-
pla
c
em
en
t
(
B
).
I
=
{
(0,0,0)}
，
L
y
=
L
x
=0
，
t
=0;
for
t
=
0
to
T
，
and
B
not null
{
n
= the nu
m
ber of sche
du
ling digital mi
croflui
d
ic m
o
dule on
t
moment
；
for
i
=
1
to
n
{
flag
=0;
for (
x
,
y
,
z
)
∈
I
if
b
i
can be pl
ace
d
at (
x
,
y
,
z
), and
x
+
l
i
′≤
L
x
,
y
+
w
i
′≤
L
y
, then
{
flag
=
1
, exit; }
if
flag
=0, then
if
L
x
=0 or
L
x
=
L
，
then
if
b
i
can be pl
ace
d
at (0,
L
y
), then
{
x
=0,
y
=
L
y
,
flag
=1,
L
y
=
L
y
+
w
i
′
,
L
x
=
l
i
′
; }
else if
L
y
<
L
, t
hen
{
L
y
=
L
,
L
x
=
L
,
i
=
i
−
1; }
els
e
{ for (
x
,
y
,
z
)
∈
I
and
x
=
L
x
,
y
=0
if
b
i
can be pl
ace
d
at (
x
,
y
,
z
) an
d
y
+
w
i
′≤
L
y
, then
{
flag
=1,
L
x
=
L
x
+
l
i
′
, exit
；
}
if
flag
=0, then
{
L
x
=
L
,
i
=
i
−
1; }}
if
flag
=1, then
{ pla
c
e
b
i
at (
x
,
y
,
z
),
I
=
I
/{(
x
,
y
,
z
)}, trans
late
b
i
al
ong the x a
n
d
y coo
r
din
a
te in
decrea
s
e
o
r
d
e
r, keep
the t
r
an
slation
co
ordin
a
tes (
x
′
,
y
′
,
z
′
),
I
=
I
∪
{(
x
′
+
l
i
′
,
y
′
,
z
′
), (
x
′
,
y
′
+
w
i
′
,
z
′
)
;
}}
add on
e to
z
coo
r
din
a
te an
d
z
∈
I
;
delete the already layout n
ode form
B
;
move forward
the back nod
e.}
3.2. Encoding
The en
codi
ng
of genetic algorithm in thi
s
pape
r
con
s
ists of three p
a
rts for the re
sou
r
ces
bindin
g
, sche
duling a
nd pl
acem
ent, re
spectively, whi
c
h dete
r
min
e
the start time
and en
d time
o
f
each o
peration, pe
rform
the di
stributi
on a
nd
placement fo
r th
e op
eratio
ns nee
ded
on
the
microfluidi
c
a
rray
s
,
such as mixing o
peratio
ns,
st
orag
e ope
rat
i
ons, dilution
ope
ratio
n
s and
observation [
11]. Each ch
romosome
co
nsi
s
ts of
k+
m+
n
ge
ne
s, and each gene
g(
i
)
∈
(0,1
)(
i
∈
(1,
k
+
m
+
n
)) re
prese
n
ts the
priority of the o
peratio
n, wh
e
r
e
k
represen
ts the n
u
mbe
r
of resource
s
bindin
g
,
m
re
pre
s
ent
s the
numbe
r of to
tal ope
ration
s,
n
rep
r
e
s
en
ts the n
u
mbe
r
of op
eratio
ns
need
to b
e
pl
ace
d
, which
mean
s th
e di
gital mi
croflui
d
ic
modul
e
wi
th high
er pri
o
rity will
be
pla
c
ed
firstly in the queue.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
A Personifi
ca
tion Heu
r
isti
c Geneti
c
Algorithm
for Digital Microfluidi
c
s-b
a
sed
...
(Ji
ngsong Yan
g
)
3191
3.3. Fitness
Function
In order to evaluate the
quality of
the pl
aceme
n
t
layout,
the optimization
of two
para
m
eters n
eed to
be
co
nsid
ere
d
, the
sm
aller a
r
ea
of the
mi
crof
luidic array
s
and th
e
sho
r
t
e
r
compl
e
tion ti
me [12]. Thi
s
is
a typica
l multi-obje
c
ti
ve optimizati
on issu
e. In this arti
cle, the
adaptatio
n values a
r
e obta
i
ned thro
ugh
the adaptive
weig
hts meth
od, in which the weig
hts a
r
e
adju
s
ted a
ccordin
g to the
adaptatio
n o
f
current g
e
n
e
ration to
a
c
quire th
e
sea
r
chi
ng a
b
ility of
positive direction, and the
valuable informatio
n
of curre
n
t popul
ation is u
s
ed
to readju
s
t the
weig
hts in ea
ch gen
eratio
n. The sele
ctive powe
r
of this method i
s
in betwe
en
of fixed-wei
ght
method
and
the rand
om
weight meth
od.
For a
given
chromo
som
e
x
，
the fitne
s
s
function
of
se
lf-
adaptive weig
ht is as follo
ws:
(1)
(2)
(3)
Whe
r
e
A
(
x
) a
nd
T
(
x
)
den
ote the area of
microfluidic
array with a
given ch
rom
o
some
x
and the total
compl
e
tion t
i
me;
A
ma
x
and
A
min
are th
e maximum
and mini
mu
m values
of
the
placement l
a
yout area
of
cu
rrent p
o
p
u
lation;
T
max
and
T
min
are
the m
a
ximu
m an
d mini
mum
values of the
compl
e
tion time of
all operations in
current popul
atio
n.
3.4. Algorith
m
Implementation
The main
ste
p
s of the pe
rsonificatio
n
he
uristi
c gen
etic algorithm a
r
e
as follows:
Step 1 : Initialization
o
f
genetic
pa
ramete
rs:
se
t the initial
popul
ation
si
ze a
s
Po
pSize;
here
d
itary ge
neratio
n a
s
G
n
; cro
s
sover prob
ablity as P
c
; the ratio of chromo
so
me
s
copi
ed directl
y
to next generation a
s
T
O
P;
the ratio of new individual
s gene
rated
rand
omly as
BOT;
Step 2 : g
enerate Pop
S
ize initial p
o
ssi
ble
solu
tio
n
with the
pri
o
rity-ba
s
e
d
e
n
co
ding m
e
th
od,
set
k
=
1
（
k is the initial searching number);
Step 3
: d
e
co
de ea
ch
chromo
som
e
: perform the
heuri
s
tic d
e
coding for the
first k gene
s to
determi
ne th
e area
of mi
croflui
d
ic arra
y and
com
p
l
e
tion time;
sort the fi
rst
k+1 to
k+m+1
gene
s to determi
n
e
the sched
u
ling ord
e
r a
n
d
cal
c
ulate th
e start time, end
time of ea
ch
operation a
n
d
the total ti
me s
pent T
(
x) by all the
o
peratio
ns und
er the
con
d
ition
s
of resou
r
ce co
nstrai
nt; plac
e all the op
eration
s
u
n
d
e
r the
sched
ulin
g
orde
r u
s
e
d
the pe
rson
ification h
e
u
r
istic alg
o
rit
h
m to o
b
tai
n
the pl
ace
m
ent
coo
r
din
a
tes a
nd the are
a
o
f
each op
erati
on A(x).
Step 4
:
cal
c
ulate t
he
weig
ht of self-fitness w
1
、
w
2
，
co
nvert the target val
ue of the current
popul
ation int
o
the fitne
s
s functio
n
value
,
and
so
rt the
ch
rom
o
some
s in
de
scendi
ng
orde
r a
c
cordi
ng to the fitness functio
n
va
lue, save the be
st fitness fun
c
tion v
a
lue
into f(x), and the be
st chro
moso
me into
Placem
ent
；
Step 5 : judge th
e end
ing condition,
if the
con
d
ition met, go to
step 1
1
(the
endin
g
condit
i
on
here i
s
k
≤
Gn;
if not, go to
the next step;
Step 6 : g
enerate ne
w
individual
s u
nder t
he
cro
s
sover
pro
b
a
b
ility Pc, the quantity of n
e
w
individual
s is
PopSize
×
（
1-TOP-BOT
）；
Step 7
: generate PopS
ize
×
BOT ne
w indivi
duals a
c
cordi
ng the
codi
ng pri
n
ci
ple ran
domly;
Step 8
: perform T
opol
ogical so
rt an
d evaluation f
o
r the ne
w in
dividual
s gen
erated;
Step 9
: sort the PopSize×T
O
P chro
moso
me
s
of the gene
ration
k together wi
th the new on
es
by Fitness fu
nction value i
n
increa
sing
orde
r, save the best into the Placem
ent
, and
save the fitne
ss valu
e into Placefun
ction
;
Step 10 : Set k=k+1, go to step 5;
Step 11 :
Output the op
timized Pla
c
e
m
ent, algorith
m
ended.
x
T
w
x
A
w
x
f
2
1
min
max
1
1
A
A
w
min
max
2
1
T
T
w
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No. 6, June 20
13 : 3187 – 3
193
3192
4. Results a
nd Analy
s
is
In ord
e
r to
e
v
aluate the
p
e
rform
a
n
c
e
o
f
the
pe
rsonif
i
cation
heu
ri
stic ge
netic
al
gorithm
(PHGA
)
, a
si
mulation
exp
e
rime
nt ba
se
d on th
e m
u
lt
iplexed in
-vitro diag
no
stics wa
s
ca
rrie
d
out
unde
r the e
n
v
ironme
n
t of Visual
C++ a
s
de
scrib
ed i
n
refe
ren
c
e [
5
] with the al
gorithm fo
rm
ulated
here.
For th
e mult
iplexed in
-virto diag
nosti
cs, we u
s
ed
the
same
desi
gn
spe
c
i
f
ication
s
(re
so
urce
constraint) a
s
Su and
Cha
k
raba
rty [5]. We assume
d th
at there i
s
one
reservoi
r/disp
ensi
ng port
for ea
ch
type
of sampl
e
s and re
agent
s
and
on
e opt
ical dete
c
tor for
each en
zyma
tic assay. First, we a
s
sum
ed that no
de
fective cell
s e
x
ist. Table 1
summ
ari
z
e
s
the
result of the multiplexed i
n
-vitro
dia
gno
stics. Com
p
a
r
ing with tho
s
e obtaine
d in
refere
nce [5], in
whi
c
h the Pa
rallel recombi
native simul
a
ted anne
aling
algorithm
(P
RSA) were
u
s
ed in th
e three
experim
ents,
the result
s by personification heu
risti
c
geneti
c
al
gorithm (P
HGA) sh
ow g
r
eat
advantag
e in completio
n
time and the biochip ar
ea.
Column 1 li
sts the type of sample
s a
n
d
reag
ents u
s
e
d
in
ea
ch
exa
m
ple: S
1
: blo
od pl
asm
a
, S
2
: blood
seru
m, S
3
: emicti
on, S
4
: saliva; A
1
:
glucose in
sp
ection, A
2
: lactic
aci
d
salt i
n
spection, A
3
: pyruvic acid salt
inspection, A
4
: g
l
u
t
amine
insp
ectio
n
. For ea
ch exa
m
ple, we ap
plied thre
e different desi
g
n spe
c
ificatio
ns, as liste
d
in
colum
n
2. For instan
ce, an
experim
ent with the scal
e
of 9×9
×
10
0 mean
s the m
a
ximum valu
es of
the bottom
coordi
nate p
r
o
j
ection
of
x
and
y
a
r
e 9,
and the l
o
n
gest
com
p
letion time of t
he
experim
ent is 100
se
con
d
s
. We
re
po
rt the re
sult
ing
area
(centim
eter) and co
mpletion
time
(in
se
con
d
s) use
d
the algorith
m
PRSA and
PHGA. As
shown in this table, PHGA
can meet al
l
desi
gn spe
c
ification
s
while
PRSA can
n
o
t. More imp
o
rtantly, PRSA requi
re
s la
rge
r
ba
sal a
r
ea
and lon
ger
co
mplete time than ou
r algo
ri
thm.
Figure 4
sho
w
s the
pla
c
e
m
ent result
of the exa
m
ple 1
sho
w
n
in T
able
1
with the
9×9
×
1
00 de
si
gn sp
ecifi
c
ati
on.
Table 1
.
Co
m
pari
s
on Expe
rimental
Re
sult
Description Design
Spec.
PRSA PHG
A
Basal
Area
（）
cm
Complete
Ti
me
（）
sec
Basal
Area
（）
cm
Complete
Ti
me
（）
sec
Example 1: S
1
, S
2
, S
3
and S
4
are
assay
e
d w
i
th
A
1
, A
2
, A
3
and A
4
9×9×100
8×8×120
7×7×140
9×9
10×9
9×9
98
117
126
9×8
7×5
4×5
74
102
106
Example 2: S
1
, S
2
and S
3
ar
e
assay
e
d w
i
th
A
1
, A
2
, A
3
and A
4
8×8×100
7×7×120
6×6×140
8×8
7×9
7×8
98
112
150
7×5
4×5
4×5
71
83
77
Example 3: S
1
, S
2
and S
3
ar
e
assay
e
d w
i
th
A
1
,A
2
and A
3
7×7×80
6×6×100
5×5×120
7×7
6×8
5×8
79
93
120
6×6
5×5
4×5
48
58
54
Figure 4.
The
3D View of the Place
m
ent
Result of the Example 1 with the 9×9
×
1
00 De
sig
n
Specification
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
A Personifi
ca
tion Heu
r
isti
c Geneti
c
Algorithm
for Digital Microfluidi
c
s-b
a
sed
...
(Ji
ngsong Yan
g
)
3193
5. Conclusio
n
The pla
c
em
e
n
t of digital microfluidi
c
s-based
bio
c
hi
ps is
a three
dimen
s
ional
packing
optimizatio
n probl
em
fo
r multiple
o
b
je
ctives. In thi
s
p
ape
r, a
p
e
rsonification
heu
risti
c
g
e
netic
algorith
m
ba
sed on th
e ide
a
of thre
e di
mensi
onal
pa
cki
ng p
r
obl
e
m
s i
s
form
ula
t
ed, of whi
c
h
the
desi
gning p
r
oce
dure and
the CAD si
mulation are
al
so provide
d
. From the results, it ca
n be
found that th
e optimi
z
atio
n of the
com
p
letion time
and bi
ochip
area
a
c
hieve
d
by the al
go
rithm
make th
e fou
ndation
of the studi
es
on
placement of
defect
-
tolera
nt digital microfluidic
bio
c
hi
ps
establi
s
h
ed, and in the
meantime, th
e algo
ri
thm can al
so b
e
used in m
any other th
ree
d
i
me
ns
io
na
l p
a
c
k
i
ng
p
r
ob
le
m.
Ackn
o
w
l
e
dg
ments
This
work was fund
ed b
y
he teache
rs' scie
nt
ific rese
arch fund
of china e
a
rthqua
ke
admini
s
tratio
n (G
ra
nt No.
201
1012
1);
the Seismi
c t
e
ch
nolo
g
y sp
ark pla
n
fou
n
dation of
Chi
n
a
unde
r (Grant
No. XH120
76
); sp
eci
a
l fun
d
of fund
ame
n
tal scientific re
sea
r
ch b
u
s
ine
s
s expe
n
s
e
for hig
h
e
r
school of
ce
ntral gove
r
nme
n
t
(proje
cts fo
r creation
tea
m
s) (G
ra
nt No. ZY201
101
04).
This
supp
ort
s
are gratefully ackno
w
led
g
e
d
.
Referen
ces
[1]
Hull
H. Smal
lp
ox
an
d b
i
oterro
rism. Publ
ic-he
a
lth R
e
spo
n
se
s.
Labor
atory a
nd C
lin
ical M
e
dicin
e
. 2
003;
(142)
4: 221
–22
8.
[2]
Z
eng
XF
, Yue
RF
, W
u
JG,
et al. Cre
a
ting
Liq
u
id
Drop
le
ts b
y
El
ectro
w
etting-b
a
se
d A
c
tuation fo
r
Digita
l
Microfl
u
i
d
ics-bi
och
i
ps.
Sci Chi
na Tech
Sci
. 2006; 36(
1):105
–1
12.
[3]
Yang
JS, Z
u
o
CC, Li
an
J, et
al. Dro
p
l
e
t Sch
edu
lin
g Al
gor
ithm for D
i
g
i
tal
Microflui
d
ics-b
a
sed
Bioc
hi
ps
.
Journ
a
l of Jili
n Univers
i
ty (Eng
ine
e
rin
g
an
d T
e
chn
o
lo
gy Editi
on)
, 200
7; 37(6
)
: 1380-1
3
8
5
.
[4]
Srinivas
an V,
Pamula VK, F
a
ir RB. A
n
Int
egrat
e
d
D
i
git
a
l
Microflu
idic
L
ab-o
n
-a-C
hip
for Cl
inic
a
l
Diag
nostics o
n
Human Ph
ys
io
logic
a
l F
l
u
i
ds.
Lab C
h
ip
. 2
004
; 4(4): 310–
315
.
[5]
Su F
,
Chakrabart
y
K. Mod
u
le
Plac
eme
n
t for F
ault-T
o
lerant Micro
fl
u
i
dics-Bas
ed Bi
ochi
ps.
ACM
T
r
ansactio
n
s o
n
Desi
gn Auto
mati
on of Elect
r
onic Syste
m
s
.
2006; 1
1
(3): 6
82–
71
0.
[6]
Su F
,
Chakrabart
y
K.
Unifi
ed Hig
h-L
e
vel
Synthesis an
d M
odul
e Pla
c
ement for Defect-T
olera
n
t
Microflui
d
ic Bi
o
c
hips
. 42
nd D
e
sign Autom
a
tio
n
Confer
enc
e.
Califor
ni
a. 200
5; 49: 825-
830.
[7]
Yuh PH, Yang CL, Chang YW.
Place
m
ent of Digita
l
Micro
fl
uid
i
c Bioch
i
ps Usi
n
g the T
-
tree
Fo
rm
ula
t
io
n
. 4
3
rd Des
i
gn Aut
o
matio
n
Conf
e
r
ence. San F
r
a
n
cisco. 20
06: 4
–28.
[8]
Yuh PH, Ya
ng
CL, Cha
ng Y
W
. Placement
of Defect-T
olerant Dig
ital Micr
o
fl
ui
dic Bi
ochi
p
s
Using th
e
T
-
tree F
o
rmula
tion.
ACM Jo
ur
nal
on E
m
ergi
ngT
ech
nol
og
ie
s in C
o
mputi
n
g
Systems
. 2007; (3)3: 13–
45.
[9]
Hog
a
S, In
dra
SW
. Desi
gn
Simulati
on
Pro
g
ram
of Ru
n
w
a
y
C
apac
it
y U
s
ing
Gen
e
tic
Algorit
hm a
t
Soekar
noH
atta
.
Internation
a
l
Journ
a
l of El
e
c
trical
an
d C
o
mp
uter En
gin
e
e
rin
g
(IJECE)
. 201
1; (1)2:
202
–2
12.
[1
0
]
H
a
ng
D
F
, We
i L
J
, Ch
en
QS, e
t
al
. A
C
o
mb
i
n
a
t
i
o
na
l H
euri
s
ti
c Alg
o
r
i
t
h
m
fo
r the
T
h
re
e
-
D
i
m
e
n
s
i
onal
Packing Problem. J
ournal of S
o
ftw
are
. 2007; 18(9): 20
83
−
2
0
89.
[11]
Jafar M. A S
t
ud
y o
n
th
e
Suitab
ilit
y
of
G
enetic A
l
g
o
ri
thm for Ad
apt
ive C
h
a
n
n
e
l
Equa
lizati
o
n
.
Internatio
na
l Journ
a
l of Electr
ical
a
nd Co
mp
uter Engi
ne
erin
g (IJECE).
2012; (2)3: 28
5–2
92.
[12]
Xu
eso
n
g
Y,
Qingh
ua W
.
An Improv
ed
Genetic A
l
g
o
ri
thm an
d Its
Appl
icatio
n.
TELKOMNIKA
Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
ng.
2012; (10)
5: 1
081
–1
086.
Evaluation Warning : The document was created with Spire.PDF for Python.