TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 16, No. 3, Dece mbe r  2 015, pp. 565  ~ 573   DOI: 10.115 9 1 /telkomni ka. v 16i3.914 1        565     Re cei v ed  Jun e  21, 2015; Revi sed O c tob e r 6, 2015; A c cepted O c to ber 28, 20 15   Tissue-like P System Based DNA-GA for Clus tering      Caiping Hou* 1 , Xi y u  Liu 2   Schoo l of Man agem ent Scie n c e and En gi ne erin g, Shan don g Normal U n iv ersit y , Jin an, S han do ng, Chi n *Corres p o ndi n g  author, e-ma i l : sdnuhc p@1 6 3 .com 1 , sdxy liu@163.com 2       A b st r a ct  In recent yea r s, DNA-GA  algorithm  is  dra w ing  attention from  scholars. Th e a l gorithm  com b ine s  the  DNA en co di ng a nd  Gen e t ic Algo rithm ,  whi c h  solves the p r em ature con v ergen ce  of geneti c  al gorithm s, the  wea k  lo cal  sea r ch capa bility and  bin a ry  Ham m i ng cliff pro b le m s   effectivel y. How to d e si g n  a m o re ef fective  wa y t o  im prove th e perfo rm an ce of  DNA -G algorithm  is  m o re wo rth studyin g.As is  kno w n to  all,t he tissue -like  P system  ca n sea r ch for t h e   optim al clu s tering  pa rtitio n with  the  h e lp of it s p a rallel  com puting a d vantag e effecti v el y. This  pape r is un d e r thi s  prem ise a nd p r e s e n ts DNA- GA  algorithm  ba sed  on tissu e -like P system s   (TP D NA - G A )  wit h  a  loop  st ru ct u r e of  cell s,   which  aim s  to co m b ine the p a ralleli sm  an d the  evol utiona ry  rules of tissue -like P syste m s  to  im prove perfo rm ance of the DNA -GA algo rith m.  The obj ecti ve  of this pap er is to use the  TPDNA -GA  algorithm  to sup port  clu s tering i n  order to  find the best  clu s terin g  ce nter.Thi s algo rithm  is of particula r intere st to when  d ealing  with la rge  and  heteroge neou s d a ta  sets an d wh en b e ing fa c ed  with an  u n kn own num ber  of cl uste rs.  Expe rim ental re sults sho w  that the p r o p o se d TP DNA -GA al gorith m  for clu s teri ng i s  supe rio r  o r   com petitive to cla ssi cal  k-m eans algo rit h m   and several evol utiona ry clu s te ring al gorithm s.     Ke y w ord:  DN A computin g, g enetic a l g o rith m,  tissue-l i ke P  system, cluste ring ce nter     Copy right  ©  2015 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  This  research concerns the  capability of the tissue-l ike  system  com putational model  to provide a  framework for DNA-GA algorith m Th e gene ral flo w  of the tra d itional ge ne tic   algorith m  is to get the optimal sol u tion  schem e in several  candi date  grou ps. In  each   gene ration,th e geneti c  alg o rithm is  sel e cted a c co rd ing to fitness and gen etic recon s tru c tion  method to ge nerate n e candid a te indi viduals. In  the cycle of evolution  gen etic algo rithm, the  fitness fu ncti on facilitate s   the ca ndid a te  individual to   evolution. It   can form  ne individual s aft e r   contin uou s it erative p r o c e ss  and th ese  individual s h a ve improved  adapta b ility comp ared to  the   previou s  i ndi vidual in  ge n e ral. T h is pe rforman c e  of  geneti c  al gori t hm ge nerally use the  G e n e tic  Algorithm a s  the body of  algorithm  whe n  we will imp r o v e the algorit hm.  Membrane computing (kn o wn as  P systems)  i s  a  cla ss  of dist ribut ed pa rallel  co mputing   model s, it focuse on th communi catio n  in th e me m b ran e s,  cell s,  tissue s o r  ot her  structu r e s  of  orga nisms.In  this p r o c e ss, the su bsta n c e in  cell m e mbrane  occur  cha nge randomly  and  in   parall e l,su ch  as diverting ,  variation and so  o n , whi c h ma ke s the algo rithm have greatly   parall e lism,  so a la rge  nu mber  of ope ration can b e   compl e ted at  a mome nt. Compa r ed to t hese  benefits of m e mbrane  co mputing, th tissu e-li ke   P system   is  in a  maximally parall e l way and   can find th e best  candi dat e individual s i n  a sh orte r time, whi c h m u st be effe ctive to choo se  the  optimal clu s te ring cente r     2. A Brief O u tline of Tiss ue-like P Sy stems   Tissue -like P system s we re   presented by  Martin-Vide  et  al.  in [[ 1] ],whi c h is an other type  of P system due to the stru ctur e of their mem b ra ne. Instead  of con s ide r in g a hiera r chi c al  stru cture, me mbra ne s are  cha nge d as a  general a  graph. They exist two biolo g i c al in spiratio ns  (s ee [[ 2] ]): inter cell ula r  co mmuni cation  and coop erati on between n euro n s.   The inte cellular comm unication i s  ba sed  on  sympo r t/antip ort rules,  which  are   introdu ce d a s  the  comm unication rul e s b e twe en  cell s. Sympo r t rule s m e a n s that o b je cts  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 16, No. 3, Dece mb er 201 5 :  565 – 573   566 coo perate to traverse a m e mbrane  tog e ther in the  same directio n ,  where a s in t he antipo r t ru les,  obje c ts a c ro ss a memb ran e  resi ding at  both sid e s of  it but in oppo site dire ction s  [[ 3] ].   Formally, a tissue-li ke P system with  in put of degre e  q >0 is a con s tru c t:    Π  =  (A,w 1  ,..., q  ,R 1  ,.. .,R  q ,R’,I,O )     Whe r e:   (1) A is a finit e  alpha bet, whose symbol s are call ed ob jects;   (2) w  i  (1 i q )  is finite set of strings ove r  A, whic h re prese n ts multiset of objects  pre s ent   in cell i at the initial configuration;  (3) R  (1 i q )  is finite set of evolution rul e s in cell i;  (4)  R’ is  finite s e t of c o mmunic ation  rules of the form (i,u/v,j), for i,j {0,1,2,...,q},    j, u,v A,|  u | + |v| is the  length of the comm uni cati on rule  (i,u/v,  j);   (5) I {1,2,..., q} is  the input c e ll;  (6) O in dicate s the output region of t he  whol e system  in the enviro n ment.    A tissue - like P system of degree q > can b e   viewed as a  set  of q cells la b e led by  1,2,...,q, each of which  consist s  of an el ementary  membrane. We  will use I  to express the input  cell  and  O  to  den ote the  o u tput region.   In above  defi n ition, R  i  (1 i q) is finite  set of evolutio n   rules in  cell  i, whose  rul e  is  of the form  u v,u,v A. The ap plicatio n of the  rule  mean s that u   will  be evolved to  v. In most of the existing t i ssue-li ke P  systems a nd v a riant s, evolu t ion rule  of the   form is  ba se d on  string  o f  object s .Moreover,  the q cell will be arrang ed  a s  a  loop  to polo g based on th e  commu nication rul e s d e scrib ed b e low.  The commu nicatio n  rul e  (i,u/v,j) can b e   applie ove r  two cell la b e led by  i and   j su ch  th at  u  is containe in cell i  an d v  is containe in  cell j. The ap plicatio n of this rule me an s that  the objects of the mul t is ets re prese n ted by u and  are inte rchan ged bet wee n  the two cell s. Note that  if either i = 0  or j = 0 the n  the object s   are   interchan ged  betwe en a ce ll and the env ironm ent [[ 4] ].   The rule s of  a system like de scrib e d  are used in  the non-d e termini s tic m a ximally  parall e l manner  when there are  several  possi bilities,  as usual  i n  t he framework of m e mbrane   comp uting.In  each  step, all  cell whi c h  can evolve   must evolve i n  a maximally parallel  way. T h at  is to say, in e a ch  step e a ch obje c t in a  membrane  ca n only be u s e d  for on e rul e , but the syst em  applie s a mul t iset of rule s whi c h is maxi mal: no furthe r rule  can b e  adde d [[ 5] ].   In a tissue-li ke P system  o f  degre e  d,a  comp utation i s  a  seq uen ce  of step s whi c start  with the  c e lls   1,...,q c ontaining the multisets  w  1 ,...,w  and  whe r e, d u ring  ea ch  st ep, one  or m o re  rule s a r e a p p lied to the  cu rre nt multisets of  sy mbol obje c ts.  Th e comp utation start s   from   th initial configu r ation an d proce e d s  as d e fined  befo r e ;  only halting computatio n s  (rea ching  config uratio n  whe r e n o  ru le ca n be  ap plied)  give a  re sult, and t he re sult i s   encode d by the   multiset of ob jects. A comp utati on is su cce ssful if and  only if it halts. When it halts, it produ ce s a   final result in output cell.       3. DNA Algo rithm Bas e on Tissue - like P s y stem (TPDNA-GA)  3.1. DN A Co ding  The m a in g e netic m a teri a l  of organi sms i s   DNA  that contain s  a  wealth  of gen etic  informatio n. The ba sic el ements of th e DNA is  Nu cleotid e. Nucl eotide co ntai ns four b a se s:  (ade nine ), G (gua nine ), C  (cyto s ine )  an d T (t hymine). Where A p a irs  with T, and C pai rs  wi th   G.The sequ e n ce of the  DNA mole cule s can be a b stracted  as th e strin g  co m posed by the  four  bases. DNA  encode s u s the potential  solutio n  of t he four ba se t o  optimizatio n pro b lem, which  is an effe ctive method to ex pre ss i ndividu al and ma ke i t  more suitabl e to recombi n e and vari ate.  Adding DNA  enco d ing t o  the geneti c  algo rithm i s  more suit able for exp r essin g  co m p lex  knowledge, whi c h has  hi gher coding   accuracy.It is easy to m a i n ta in the diversity of i ndivi dual and m o re  ea sily to intro d u ce th e g ene tic mani pul ati on. A key  problem  of imp a ct on  a c curacy  and  conve r g ence rate  of probl em  sol v ing is t he l ength of the  DNA  stra nd . This p ape r use   quante r na ry  encodin g  in t he literature  [[ 6] ] instead  o f  E’={0,1,2,3} 1 ,1 is the l e n g th of the  DNA  seq uen ce. Th is allo ws to e x press the  so lution of  the proble m  as a i n teger  strin g  of quatern a ry Gene rally, the optimizatio n probl em ca n be de scribe d as follo ws:      Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Tissue -like P System  Base d DNA -GA fo r Clu s teri ng (Caipi ng Ho u)  567 )   x  ,...,  x  , f(x   Min    n     ,...,    2    1, = i    ,     maxi   X ≤     X ≤       mini    X n   2 1 i     In the pra c tical optimizatio n pro b lem s t he variabl e x i  is  an integer  s t ring  with length L.[x   min i ,x  max  i ] is the bou nda ri es of x i . x  min i  is a  cod e  string of 0 an ma x  i  is a co de stri ng of 4 l -1.  Duri ng th e en codi ng p r o c e ss, thi s  a r e a   of x  ma x  i mi n i  is t r an slate d  into 4 l  se g m ents.  T here f ore,  the accu ra cy  of variable x i  is  (x  max  i mi n  i  )/4 an d th e length  of e a ch i ndividua l n-dim e n s ion a variable i s  L=n × l[[ 7] ].     3.2. Fitness  Function   Geneti c  alg o r ithm exist s   su ch a  fun c tion t hat pl ays d e ci sive role in th e e v olution   dire ction of g enetic al gorit hm. This fun c tion is  the fitness functio n . Fitness may be the obje c ti ve   function  and   it may also b e  a fun c tion   of the obj ecti ve functio n  related. Mo re  over, it can  a l so  have nothin g  to do with the  objective fun c tion. Ge n e tic algorithm ev aluate s  the candid a te by the  size of the value of the fitness fun c tion. G enetic algorithm can d e termi n e the cha n ce of  can d idate  so lutions into t he next gen eration of  g e netic ba se d on the value  of the fitness  function. It is about wh eth e r the quality  of candi d a te  solution s m a y have a better cha n ce of  geneti c  evol u t ion.Also,it is  about  wh ethe r the  exce ll en t cha r a c teri sti c s of the  po p u lation  ca n b e   contin ued.   As the di re ct ion of  sea r ch and  evolut i onary  guidin g  the TP DNA-GA alg o rit h m, the  desi gning of t he fitness fun c tion is very i m porta n t. This  paper us e a fitnes s  func tion as  follows   F (x ) =1/( 1+f ( x ) )     Whe r e, f(x) i s  the  obj ecti ve functio n   of the  o p timization  proble m  of minimi zing. After this  treatment, the range of fitness  func tion values  is  [0,1].  After en codi n g  n  individu al s of  the i n itia pop ulation  i n to qu aternary seq uen ce, w so rt  the fitness va lues by the fitness fun c tion  value.  Reserve the minimum value of individual fitn ess  (the worst ind i vidual) a nd t he maximum  individual  (th e  be st individ ual)(a total of  two individu a l s)   as limit individual s. The remainin g (N-2) indi vidu al s co ndu ct T P  processin g . Reserving t h e   individual of t he wo rst fitness value i s  in ord e r to  m a intain the di versity of the  offsprin g, which  make it po ssi ble for the alg o rithm to escape from  lo ca l optimum an d avoid falling into premat ure  conve r ge nce.    3.3. Tissue-li ke P Proces sing  After the ope ration, the two limit individ uals  rem a in s in the area s betwe en the  basi c   outer mem b rane and the  surfa c e m e m b ran e . The re mainin g (N-2) individu als are put into m  basi c  m e mbrane s eq ually, whi c h fo rms  a P syst e m .And ea ch i ndiv i dual in  ea ch  membrane  can  be viewed  a s  a  cell.In th is  se ction,the  memb ran e s will b e  a r ra nged  as a l o op top o logy.The  individual s h a v e som e  evol ution rules to  evolve ea ch  other i n  the  system, whil comm uni cati o n   rule s betwee n  individual m e mbrane s are use d  to exchang e and  sh are the info rmation.  In this p ape r,  the tissue -li k e P sy stem u s e s   a sin g le -l ayer  m e mb ra ne stru cture becau se     the layers of  the tissue -like P  system s a r e rela ted  to the mag n itude of po pu lation si ze  N.  In   orde r to make the runni ng  time of each  membrane  re lative to the average of the  runni ng time, w e   define the nu mber of the  membrane s a s  follows:     Z= 2 N     Whe r N i s  the total num ber of i ndivid uals  of in itial  popul ation,  Z is the  sq u a re  root of  (N-2 )   (ro und do wn)  [[ 6] ]. When  N is l a rg e en ough,  we  can  get the s qua re root of N  d i rectly. Using  this  way to d e fine  the nu mbe r   Z ca n mai n ta in simil a r limi t  individual betwe en int r a m embrane  a nd  extramemb r a ne, whi c h can  redu ce the o v erall co nvergen ce time.    3.3.1. Rules   At the same t i me, the evol ution rul e  of the  mem b ra n e  is defin ed.  The role of e v olution   rule s is to evolve the individuals in th e membrane s to gene rat e  new in dividuals u s e d  in the   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 16, No. 3, Dece mb er 201 5 :  565 – 573   568 cal c ulatio n of  fitness.  Du ri ng the evol u t ion,  each m e mbrane  mai n tains th e same  size (th e   numbe r of individual s). Every individual  in each  me mbra ne will b e  evolved after executing  the   sele ction, cro s sover a nd  mutation in t u rn.  When th e individual are evolve d,each memb rane  sen d s its  be st individual to the neigh boring  memb ra n e s (su c h a s   membrane i - 1 and me mbrane  i+1)  and by u s ing the  com m unication ru le,   we ret r ieve the best in dividual from  the neigh bori n g   membrane whi c h con s titute a matchi ng pool of  th e individual in the next calcul ation ste p . A  matchin g  po o l  is made  up  of all individu als in e a ch m e mbrane a n d  the best indi viduals from i t s   two adja c ent  membra ne s. The individuals in  mat c hing pool  wi ll be evolved by executi n g   sele ction, cro s sover an d mutation ope ration s in turn.In orde r to maintain the size of individual in ea ch  mem b ran e , tru n ca tion op eratio n is u s ed t o   con s titute n e w  in dividual  pool  acco rdin g to  the fitness fu nction. T he in dividual s in n e w in di vidual pool will  be regarded as  t he  individ uals  to  be evolved in  next computi ng step [[ 8] ].  The sp eci a l logical stru ctu r e ca n bri ng the followi ng b enefits:   (1) T he  co-evolution of indi viduals in th e  m memb ran e can a c cele rate the  conv erge nce   of the propo sed TPDNA-G A  algorithm.   (2) The  indivi dual  sha r in mech ani sm o f  the local n e i ghbo rho od  st ructu r e  can e nhan ce  the diversity of individuals  in the entire system.  After all the in dividual s in the tissue - li ke P sy stem are  evolved, the best individu a l  will be   comm uni cate d to the environment. Th ey will ste p  to  n e xt round  ope ration tog e the r  with the i n itial   2 limit individuals. As it in volves multipl e  best  individ uals in the  e v olut ion of the system s, the  t i ssu e-li ke P  sy st em  can e f f e ct iv ely  solv the probl em  of local opti m um algo rith m.    3.3.2. Selection Opera t or   In this pape r, we adopt th e limit individual re se rvatio ns an d the fitness fun c tion  as the   sele ction o p e r ator.  Choo se the sm alle st fitness  value of the indi viduals in  ea ch g ene ratio n  to  comp are with  the be st in di vidual from  the p r ev iou s   gene ration  a nd  sele ct the  minimum  fitness  value of the i ndividual s a s   the limit indivi dual s to  pa rti c ipate i n  sele cting of th e n e xt gene ratio n . It  will not rel e a s e the be st i ndividual to the extram e m bran e until it rea c he s the  con d ition s  of the   membrane  di ssolution  (wh en it rea c he s the  ma xim u m exe c utio n ste p  n u mb er  G). T he  b e st  individual  will  carry o n  the  iteration  op era t ion out side  the me mbran e . In the  oute r  me mbrane,  we   adopt the limi t  individual re servatio ns a s  well.    3.3.3. Cross o v e r Operators   In this pa per,   we  use th e re con s tru c tion   cro s s o ver operator. Before the  rec o ns truc tion  o f   the cro s s op eration, t w o i ndividual s fro m  the  p opul ation  shoul d be sele cted as  th pa ren t s.  Since the m a in purpo se  of the reco n s tru c tion is  t o  cha nge th e simila rity of the outstan din g   individual, the  choi ce of the  parent s is no t random,  whi c h is to say we need  cho o se the relatively  simila r indivi dual s. Firstly, choo se o n e  indi vidual  as o ne of the pa rent s randomly in t he  individual s wi th better fitness. And ra nd omly sele ct two individu al s as a candid a te pare n ts. Then  by comp ari n g  the simila rity betwe en  ca ndidate  par e n ts an d the  known pa rent s, we sele ct the   individual tha t  is more  si milar to the  kno w n p a ren t s as a nothe r pa rent of the re co nst r u c tion   operation.  Here  we  defin e that the  si milarity  bet ween in dividu als i s  the  di stan ce  between  individual s. T he smalle r th e dista n ce is,  the mo re  si milar the t w o  bodie s  a r b e lieved.After  th e   two pa rent s are d e termin ed, we defin e the indivi d ual with bett e r fitness a s  the parent A and   anothe r indivi dual is d e fine d as pa rent B .   The sp ecifi c  descri p tion of  the re con s truction  cro s so ver o peration   process i s   shown in   the Figure 1.  At first, we choose one ba se rand omly in the la tter of the parent A that is the [L/2, L] and  cut the seq u e n ce fra g ment  R behind thi s  ba se fr om the parent A.  Then pa ste the fragm ent into   the front of t he pa rent B,  whi c h fo rm in termedi ate in dividual A a n d  interm ediat e individu al B . In   the DNA ge n e tic alg o rithm ,  the length o f  the individu al is fixed. Th erefo r e it ne e d s to g ene rat e  a  seq uen ce fra g ment R’ in t he latter of interme d iate ind i vidual A which contai ns th e same n u mb er  of base s  with  R. At  the sa me time,we cut a seque nce fragme n t from the latter of intermedia t individual B t hat also  cont ains th sam e  num ber of  ba ses with   R.The r eby,it  forms two  ne w   individual s: p r oge ny A a n d  progeny  B.In this  pap er we ad opt the  same  pro babili ty of crossov e operator in sid e  and out side  the membra ne.        Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Tissue -like P System  Base d DNA -GA fo r Clu s teri ng (Caipi ng Ho u)  569                      Figure 1. The  reco nst r u c tio n  cro s sove r o peratio n       It should be  noted that d ue to the re constructi o n  o f  the cro s sover ope ratio n  is more  compl e x and  the cha nge s are la rge r  for the populat i on individual s, so the execution pro babil i ty  Pr of the reco nstru c tion  cro ss  sho u ld cho o se  a  smalle r value. Here  we defin e Pr=0.05.     3.3.4. Mutati on Opera t or   In the genetic algo rithm, mutation ope rator i s  main ly to ensure  the diversity of the  grou ps in a  certain  deg ree .  In ord e r to  fully  displ a y the pe rforman c of the  cro s sover  ope ra to pre s ente d  in  this pap er, th e mutation o perato r  u s e t he co mmon v a riant s (n orm a l mutation, NM)  operator that  is com m only  use d  in the DNA geneti c  al gorithm.    This o perator is simila r to  the flip variati on of the bin a ry GA,whi ch  is to mutate  every  base in th individual  wit h  proba bility p m  into another base. T he  probability of performi n g   variation of th e wh ole in dividual i s  p m ×L. For exa m ple,  the ba se  C i s  repla c ed  by base A in th individual.   The si ngle - p o int mutation  is used to  reali z e the  mutations  of individual s. If v is a   mutation poi n t determi ned accord i ng to  mutation probability  p m , its value  become s , after  mutating.    0         v ,     v ×   δ   ×   2        v 0    =      v ,    δ   ×   2        v     Whe r e the  si gns  “+” o r  “-”  oc cur  with e q ual proba bility, and  δ  is  a real num be r in  the ran ge [0, 1 ],  gene rated  with uniform di st ribution.     3.4. The Implementa tion  Steps  o f   the TPDNA-GA Algorithm   The procedu re of TPDNA-GA can b e  su mmari zed a s   follows:  (1) Before runnin g  the  algorith m ,we  need  to  se t the pa ram e ters of the  algo rithm   (initializi ng t he po pulatio n), in cludi ng  popul ation  size N, th e  larg est p o p u lation evol u t ion   algebrai c  G,  reconstruction cros execution probabilit y P, common  variant execution  probabil i ty  p m (2)  Ra ndomly  prod uce N i n dividual s with  the lengt of L=n x l, which ma ke up  th e initial  popul ation. And the cu rren t evolut ion ge neratio n is se t to 1;  (3)  DNA en co ding:calculate  the value of  each individu al's fitness an d sortin g;  (4) Sel e ct an d re serve t w o individual with  the maxi mum and mi nimum fitness value.  The rem a inin g (N-2) in dividual s are p u t into m membran e s e quall y , which form s a tissue-li ke P   system s. We  set the maxi mum execution st ep n u mb er as T 1  insi d e  the membrane s;  (5) The pro p o se ge netic operation s   were ca rri ed o u t for ea ch  of the individu a l s withi n   the membran e s: sel e ctio n, cro s sove r an d mutation.  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 16, No. 3, Dece mb er 201 5 :  565 – 573   570 (6)  Run th step of (5) i n  each of th e memb ran e  repe atedly until the me mbra ne   operation re ach e s the m a ximum evol ution gen er at ion and p r od uce a b e st i ndividual  whi c con s titutes a  matchin g  po o l  with the indi vidual s in th e  adjacent me mbra ne s. Th e matchi ng p ool  con s i s ts  of al l individual s i n  on e me mbrane   and  the t w be st indiv i dual s fro m  t h e   a d ja cent t w o   membranes. The  individuals  in mat c hing pool  will be evolved  by executing sele ction, crossover  and m u tation  ope ration s in  turn. In o r d e r  to mai n tain  the si ze  of in dividual s in e a ch  memb ra ne,  truncation o p e ration i s  u s e d  to co nstitut e  ne w individ ual po ol a c co rding to th e fi tness fun c tio n The individu a l s in ne w indi vidual pool  will be reg a r d e d  as the in di viduals to be  evolved in n e xt  comp uting st ep.  (7)  Run the  st ep of (5 ) in the matchi ng p ool  until it rea c he s the max i mum execution step   numbe r (with  the sam e  m e mbrane exe c ution  step n u mbe r  T1 in side the mem b ran e ).Th en   t he  membrane s are dissolve d.   The fin a l  be st indivi dual(a total  of one ) i s  relea s ed to  the   environ ment  whi c h compo s e s  the elite popul ati on wit h  the initial two limit individuals.   (8) Elite  po pulation  co n duct the  ge netic m anip u lation: cro s sover an mutation,  sele ction. We  set the maximum execution  step n u mb er as T 2  outsi de the memb rane.   (9)  Ru n the step of (7 ) re p eatedly until the op eratio rea c he s the t e rmin ation  co ndition.  And the optimal solutio n  is gen er ate d .The TPDNA-GA algorithm  end s.      4. Applicatio n of TPDNA-GA Algo rith m in Clusteri ng   4.1. Introduc tion of Clu s tering and Cl usterin g  Me asure   From n o o n , let us a s sume that we  are  con c e r n ed with a  dat a set D,  whi c h h a s n  sampl e  p o int s  a nd i s  p a rtit ioned  into  clusters,  C 1 ,C 2 ,... ,C k . Each  of them i s   re pre s ente d  a s  an   m-dime nsi o n a l vecto r  of  real nu mbe r s,  say x 1 , x 2 ,... ,x  n , where  x i  = [ x i1 , x i2 ,.. ., in ]. Denote  by  z 1, z 2,  ...,z   k  the corre s po n d ing  clu s ter  cente r s. If th e dista n ces  of sam p le p o int x i  to c l us ter  cent e r s z  p  (p =  1,2,...,k ) s a tis f y:     p, j   an d 1,2,..., = p ||, p z   -   i ||     || j   z -   i ||     Then sampl e  point x i  is assigned to cl ust e r C  , i =  1,2,...,n.   Gene rally  sp eaki ng, pa rtitional  clu s teri ng alg o rithm  sea r che s  fo r the o p timal  clu s ter  cente r s in th e solution  sp ace  a c cordi n g to  some  cl usteri ng  mea s ure in  orde r to solve dat clu s terin g  pro b lem. A com m only use d  cl usteri ng me a s ure is:     M(C 1 ,C 2 ,...,C k  ) =   k 1x i ||   z - x ||   j iC i j      The smalle r the M value, t he hig her th e  clu s terin g  q uality. In this work, the  cl usteri ng  measure is a l so u s e d  to e v aluate the i ndividual of  the syste m  d u ring  mem b rane evol ution .  If  the M value of an membra ne is the sma ller, the me mbrane is  the better, otherwis e , it is  worse.  Since data  set D has  k cluster  cent ers and e a ch clu s ter  cente r  is a m-dim ensi onal   vector, ea ch  membrane in  the system i s  co nsi der ed  as a (k×m)-di mensi onal  re al vector of the  form:     km k2 k1 im i2 i1 1m 12 11 z ,..., z , z ,..., z ,..., z , z ,..., z ,..., z , z z     Whe r e z 11, z 12, ..., z 1d,   are d co mpone nts of  ith clu s t e r ce nt er i z , i= 1,2,...,k . For  s i mplic i ty, s u ppos e   that each  cell  has the sam e  numbe r of obje c ts, whi c h is den oted  by D [[ 9] ].   Initially, the system will ra n domly gene ra tes m  initial o b ject s for ea ch cell.When a n  initial   obje c t z is g enerated,  (k×d)  ran dom  re al nu mbe r s a r pro d u c ed   repe atedly to  form  it with  the   c o ns traint of:    B z A ,..., B z   A ,..., B z A d id d j ij j 1 i1   1     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Tissue -like P System  Base d DNA -GA fo r Clu s teri ng (Caipi ng Ho u)  571 Whe r e j A and j B are  lower bou n d  an d u ppe r bou nd  of  jth  dimensi onal  compon ent of  dat a   points ,  res pec tively, j =  1,2,... ,d.     4.2. Cluste ring Ba s e d on  TPDNA-GA  Acco rdi ng to  the compo n ents  discu s sed ab ove, th e de sign ed t i ssue-li ke  P  system  based  DNA  can be fo rmall y  used fo clu s terin g   to  cho o se th e be st  clu s terin g  ce nter. The  opti m al  solutio n  in  th e environm e n t refe rs to t he o p timal  cl usteri ng th at  we  co uld  obt ain fro m  the   data   given [[ 10 ] ]. The objective function f(x) will be  reali z ed by evaluating the  distances  between two  individual s fro m  each oth e r.   Steps that use TPDNA -GA  to solve the  probl em of cl usteri ng a r e a s  follows:   (1) Fi rst of all ,  give the data sets that  n eed to be cl u s tere d and  condu ct DNA encodin g   for data;   (2) Cal c ulate the  obje c tive  function;   (3) Determin e the fitne s function  a cco rding  to the  o b jective fun c t i on, whi c h  is  use d  to  evaluate the  poste rity of the geneti c  alg o ri thm s  and g r asp the evol utionary di re ction.  (4) Introd uce  TPDNA-GA  algo rithm o perat io n a n d  determine t he o perating  ope rato (sel ect op erator, cross op erator,mutation operator).  (5)  Perfo r m TPDNA -GA algorith m   to gene rate  th e  optimal  sol u tion that is th e optimal  c l us te r i ng  c e n t e r Based  on  the  propo sed  T P DNA-GA, th e be st o b je ct in the  envi r o n ment i s   reg a rde d  a s   the system o u tput, which is t he found o p timal clu s ter centers.       5. Experiment Re sults a nd Analy s is  In this se ction ,  the propo se d TPDNA -GA  algorit hm i s   evaluated for  clu s terin g  on  the five   real -life data  sets p r ovide d  in UCI [[ 11] ] (inclu ding th e Iris, Brea st  Can c er,  Win e , New T h yroid   and Live r Di sorde r s) an d  comp ared with cla ssi cal  k-m ean s alg o rithm a nd several  clu s te ring   algorith m s, in cludi ng GA [[ 12] ] an d PSO  [[ 13] ]. In ord e r to te st the  robu stne ss of  these  cl uste ring  algorith m s,  we re peat th experim ents  50 time s fo each d a ta  set .  The M  valu e is al so u s e d  to   measure the  clu s terin g  qu ality of each   clu s terin g  al g o rithm. Th at is to  say, if the M value  of  one   individual i s  the smalle r than othe rs,the fitnes s value s  will be  smalle r, wh ich me ans t h e   individual will  be better tha n  others. So the clu s ter  ce nters  will also  be better. Th ese al gorithm s   are impl emen ted in Matlab 7.1.      Table  1.  The perfo rman ce comp ari s o n s of  tissue - like P systems of  different deg rees  Data sets  4 cells   8 cells   16 cells   20 cells   Iris  96.84   96.81  96.75  96.77   ±0.0751   ±0.0435  ±0.0428  ±0.0361   Breast Cancer   2974.24   2971.14  2970.24  2969.06   ±1.5431   ±1.5287  ±1.1225  ±1.0970   Wine  16309.01   16303.42  16292.25  16301.97   ±2.5053   ±1.9595  ±0.1529  ±2.8563   Ne w  Th yr oid  1885.69   1870.37  1869.29  1871.18   ±14.3773   ±1.7355  ±0.9215  ±2.2496   Liver Disorders   9860.54   9859.02  9851.78  9857.08   ±5.7239   ±0.5116  ±0.0347  ±0.1043       In the exp e ri ments,  we  u s e f our  kind s o f  tissu e-li ke P  syste m s with  deg ree s   4, 8,  16  and   20 re sp ective ly. The purpo se i s  to evalu a te the effe ct s of the n u mb er of cells  (dif ferent de gree s)  on cl uste ring  quality. The  four tissue -li k e P syst em are a pplie d to find out the  optimal cl ust e centers for the five data  sets re spectivel y . The average values  ar e used to illust rate the average  perfo rman ce  of the algorit hms while st anda rd devia tions indi cate  their robu stn e ss. As we can  see, T able  1  provide s   exp e rime ntal results of th e tissue -like P  system s of fou r  deg ree s   on f i ve  data  sets  re spectively. It can be  furth e r ob serve d  th at the tissue -l ike P  system  with d egree  16  obtains the smallest average valu es and standard  deviations on a ll of data set s , whi c h illustrate  that the tissu e-like P syste m  with deg re e 16 ha s goo d clu s terin g  q uality and hig h  robu stne ss.  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 16, No. 3, Dece mb er 201 5 :  565 – 573   572 For thi s  re ason, we  will d o  experim ent   on TPDNA-GA, k-me an s, GA, and PSO with  degree 1 6 . In the experi m e n ts, the pa ra meters of TP DNA -GA a r set a s  follo ws. The pop ulati on  size i s   200  (N = 20 0). T h e  l a rge s pop ula t ion evolutio n  alge braic G i s   set  as 30 0,  whi c h i s  to  say  that the m a ximum evol utio n ge ne ral i n side A1   an d o u tside  A2 i s   150. T he  parameters  of th e   mutation op e r ator i s  set as pm =0.0 1. And the   crossover probability   is set  as   Pr=0.05. The  numbe r of m e mbrane s i s   15(m =  1 5 ). In  ord e r to  stud y performan ces of ti ssue-li ke P  system s of  different d egrees, fou r   ca ses a r co nsi d ered  in the  e x perime n ts: q =  4; 8; 1 6 ; 2 0 . And for  ea ch   test probl em, we ru n 50 times for the five algorithm s of   TPDNA-GA, k-m ean s, GA and PSO The   results a r e sh own in Ta ble  2.      Table 2. The  results obtai n ed by the alg o ri thms  for 50 runs  on the five data s e ts  Data sets  TPDNA- G A   GA   PSO  k-means  Iris  96.80  99.83   97.23   104.11   ±0.1436  ±5.5239   ±0.3513   ±12.4563   Breast Cancer   2997.36   3249.26  3050.04  3251.21   ±2.1345   ±229.734  ±110.801  ±251.143   Wine  16292.25   16298.42  16292.25  16312.43   ±0.1530   ±2.1523  ±0.1531  ±9.4269   Ne w  Th yr oid  1870.36   1875.11  1872.51  1886.25   ±0.9215   ±13.5834  ±11.0923  ±16.2189   Liver Disorders   9851.81   9856.14  9851.73  9868.32   ±0.0348   ±1.9523  ±0.0356  ±7.9274       In orde r to fu rther  evaluat e clu s teri ng p e rform a n c e, the propo se TPDNA -GA a l gorithm   is compa r ed  with GA-ba s e d  and PSO -b ase d  clu s te ri ng algo rithm s  as well a s  cl assical k-me ans  algorith m . Ta ble 2  give s t he  com pari s o n  results  of t he tissu e -li k e  P  system  of  deg re e 1 6   with   other fou r  cl u s terin g  alg o rit h ms o n  the fi ve data set s , respe c tively.   From  the re sults,  we can see   that the TPDNA-GA p r ovi des the o p timum aver a g e  value and  smalle st stan dard d e viatio n in   comp are to those of othe r a l gorit hm s.Fo r instan ce, the  optimum valu e is 96.80  whi c h is o b taine d   in mo st of ru ns  of TPDNA - GA al gorith m , however other th ree  al gorithm s fail t o  attain the  value  even on ce  wi thin 50 run s . And the resul t s on the  Win e  also sho w  that the TPDNA-GA algo rith provide s  the  optimum valu e of 16292.2 5  while  the  PSO, GA and k-m ean s o b tain 162 98. 42,  1629 2.25  an d 16 312.4 3   resp ectively. In ad dition, t he tissu e -li k e  P sy stem  o b tains smalle st  standard deviation on each  data set in compare to other three al gorithm s , whi c h illustrates that it  has  high  rob u stne ss. Thi s  is  a st ron g  eviden ce  t o  prove th signifi cant  su perio rity of the  prop osed alg o rithm.       6. Conclusio n   In this pape r, a new DNA-GA algorithm  based  o n  tissue -like P system (TP D NA-GA) is  prop osed  by combi n ing  DNA-GA  with t i ssue-li ke  P  s y s t em for the firs t time and we us e it  for  clu s terin g . Di stingui sh ed f r om th e existing evol utio nary  clu s teri ng te chniq u e s , two i nhe rent  mech ani sm of  t i ssu e-li ke  P  sy st em a r e  ex ploit ed to realize the TP DNA -GA alg o r ithm, incl udi ng   evolution an d com m uni cation me cha n ism s . A nd t he two i nhe rent rule s a r e used b e tween  membrane s that contain  th e ave r age  n u m ber of  i ndividual s.Moreov er, the  comm unication  rule imply  re alize a  lo cal neig h borh ood  stru cture,   nam ely, each m e mb rane  ex chan ges an sha r es  the be st obj e c ts  with its two adja c e n t m e mbrane.  Un der th control of two  rul e s a nd the   fitness  function  of in dividual s, the  TPDNA -GA  algorith m  is  a b le to search  for the optim al clu s ter  ce n t ers  for a d a ta set to be  clu s tere d.In ad d i tion, the local neig hbo rh ood  stru cture  can  guid e  the  exploitation o f  the optimal   obje c t an d e nhan ce  the  d i versity of ev olution  obje c ts. The r efo r e,  the   TPDNA -GA  a l gorithm pre s ented  in  thi s  pape r can be  viewed  as  su ccessful in stan ce fo r da ta  c l us te r i ng After repe ate d  verification,  the TPDNA -GA  algorith m  performs  wel l  when the p o pulation   size is la rge  enou gh. The  future work is to im prove the algo rithm  efficien cy wh en the pop ula t ion   size is small.        Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Tissue -like P System  Base d DNA -GA fo r Clu s teri ng (Caipi ng Ho u)  573 Referen ces   [1]  Martin-Vid e C, Pazos J, Paun  Gh, Rodrig ue z-Pat on A. A ne w  c l ass of s y mbolic  abstract  neura l  nets :   T i ssue P s y ste m s. In: Ibarra OH, Z hang L.  Editors . COCOON. Lecture Notes  in C o mp u t er Scienc e.  Sprin ger. 20 02 : 290 - 29 9.  [2]  Martin-Vid e C, Paun Gh, Pazos J,  Rodrig uez-Pato n  A. T i ssue P sy st ems.  T heoreti c al Co mp ute r   Scienc e . 200 3; 296(2): 29 5 - 3 26.   [3]  Peng  H, Z h an g J, W a n g  J,  W ang  T ,  Pére z-Jiménez  MJ,  Risc o s-Nú ñez  A.  Mem b ra ne C l u s te ri ng : A  Novel  Cl usteri ng Al gorit h m  u nder M e mbra n e  Co mputi n g T w e l fth Brai nstorming  W eek  on Mem b ra n e   Comp uting (B W M C201 4). 20 14: 311- 32 8.  [4]  Carn ero J, Di az-Pern il D, Gutierrez-N a ra njo MA.  Des i gning tissue-like  P systems for im age  se gm en ta ti on   o n  pa ra ll el  a r ch i t e c tu re s . N i n t h Brainstorm i ng W eek  on  Membra ne C o mputin g. 20 11:   43-6 2 [5]  F r eund R, P ă u n  G, Pérez-Jiménez MJ. T i ssue P s y stems  w i t h  cha n n e l states.  T heoretic al Co mpute r   Scienc e.  200 5; 330(1): 10 1-1 16.   [6]  W ang K, W ang N. A novel  RNA ge netic  alg o rithm for p a rameter esti mation of d y n a mic s y st ems.   Che m ic al En gi neer ing R e se a r ch and D e sig n .   2010; 88( 11): 148 5-14 93.   [7]  Z hao S, Li u X. Researc h  on  a Ne w  D N A- GA Algorithm  Based  on P S y stem . F r ontie r and F u tu r e   Devel o p m ent  of Informatio n  T e chn o lo gy i n  Med i cin e   an d Ed ucatio n Springer, Netherlands. 2014:  169 1-16 98.   [8]  Escuela G, Gutiérrez-Naranjo MA.  An a p p licatio n of  ge n e tic al gorit hms  to me mbra ne  co mputi n g Eighth Bra i nsto rming W eek o n  Membra n e  Co mputin g. 201 0: 101-1 08.   [9]  Bakar RBA, W a tada J, P edr ycz W. DNA ap proac to so lv e cluster i ng  pr obl em bas ed  on a m u tua l   order.  Biosystem s.  20 08; 91( 1 ) : 1-12.  [10]  Bakar RBA,  W a tada J, Pe dr y cz W .  A p r oxim it y   ap pro a ch to DNA  base d  cluster i ng a nal ys is.  Internatio na l Journ a l of Innov ative  Co mputin g, Informati on  and C ontrol.  2 008; 4(5): 1 203 -121 2.  [11]  http://archive.ic s .uci.edu/ml/   [12]  S Ban d y o pdh ya y ,   U M aul ik. An  evol utio n a r y  tech niq u e  bas ed  on  k- means  al gorit hm for  optima l   clusteri ng in R N Inf. Sci . 200 2; 146: 22 1-23 7.   [13]  YT  Kao, E  Zahar a, IW  Ka o. A h y bri d iz ed  ap proac h to data cluste ring, Expert S y stems  w i t h   Appl icatio ns. 2 008; 34( 3): 175 4-17 62.       Evaluation Warning : The document was created with Spire.PDF for Python.