I AE S  I nte rna t io na l J o urna l o f   Art if icia l In t ellig ence   ( I J - AI )   Vo l.   6 ,   No .   3 ,  Sep tem b er   2 0 1 7 ,   p p .   1 0 0 ~ 1 1 1   I SS N:  2252 - 8938 ,   D OI : 1 0 . 1 1 5 9 1 /i j ai. v 6 . i3 . p p 1 0 0 - 1 1 1          100       J o ur na l ho m ep a g e :  h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I J AI   G ene tic  Alg o rith m   for  G ra mm a r I nduction a nd  Rul es  Verific a tion  t hro ug h a PDA  Si m ul a tor       H a ri  M o ha n P a nd ey   De p a rt m e n t  o f   Co m p u ter S c ien c e   a n d   E n g in e e rin g ,   A m it y   Un iv e rsi ty ,   In d ia       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   J u n   6 ,   2 0 1 7   R ev i s ed   A ug   8 ,   2 0 1 7   A cc ep ted   A u g   2 2 ,   2 0 1 7       T h e   f o c u s  o f   th is  p a p e r  is  t o w a rd s  d e v e lo p in g   a   g ra m m a ti c a l  in f e re n c e   s y ste m   u se s  a   g e n e ti c   a lg o rit h m   (GA ),   h a s  a   p o w e r f u l  g lo b a l  e x p lo ra ti o n   c a p a b il it y   th a t  c a n   e x p lo it   th e   o p ti m u m   o ff sp rin g .   T h e   i m p le m e n ted   s y ste m   ru n s  i n   tw o   p h a se s:  f irst,   g e n e ra ti o n   o f   g ra m m a r  ru les   a n d   v e rif ica ti o n   a n d   th e n   a p p li e s  t h e   GA ‟s  o p e ra ti o n   t o   o p ti m ize   th e   ru les .   A   p u s h d o wn   a u t o m a ta   sim u lato r  h a s  b e e n   d e v e lo p e d ,   w h ich   p a rse   th e   train in g   d a ta  o v e r  th e   g ra m m a r‟s  ru les .   A n   in v e rted   m u tatio n   w it h   r a n d o m   m a s k   a n d   th e n   „X OR‟   o p e ra to r   h a s  b e e n   a p p li e d   in tro d u c e s  d iv e rsity   in   th e   p o p u lati o n ,   h e lp s   th e   GA   n o t  to   g e t  trap p e d   a t  lo c a l  o p ti m u m .   T a g u c h i  m e th o d   h a s  b e e n   in c o rp o ra ted   t o   t u n e   t h e   p a ra m e ters   m a k e s  th e   p ro p o se d   a p p r o a c h   m o re   ro b u st,  sta ti stica ll y   so u n d   a n d   q u ick ly   c o n v e rg e n t.   T h e   p e r f o r m a n c e   o f   th e   p ro p o se d   sy ste m   h a s  b e e n   c o m p a re d   w it h :  c las si c a l  GA ,   ra n d o m   o ff sp rin g   GA   a n d   c ro w d in g   a lg o rit h m s.  O v e ra ll ,   a   g ra m m a ti c a l  in fe re n c e   s y ste m   h a s   b e e n   d e v e lo p e d   th a t  e m p lo y s a P DA   si m u lato r  f o r  v e ri f ica ti o n.   K ey w o r d :   C o n te x t f r ee   g r a m m ar   Gen etic  al g o r ith m   Gr a m m ar   in d u ct io n   P ar s in g   P u s h d o w n   a u to m a ta     Co p y rig h t  ©   2 0 1 7   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Har i M o h an   P an d e y ,     Dep ar t m en t o f   C o m p u ter   Sc ie n ce   an d   E n g i n ee r in g ,   ASET ,   Am it y   U n i v er s it y ,   Secto r   1 2 5 ,   No id a,   U. P .   I n d ia .   E m ail:  h ar i0 4 to p @ y ah o o . co . in       1.   I NT RO D UCT I O N     T h e  C o n te x t  f r ee   g r a m m ar s   ( C FG)   ( B NF  Gr a m m ar s )   h av e   b ee n   u s ed   ex ten s i v el y   to   d escr ib e  th e   s y n ta x   o f   p r o g r a m m i n g   la n g u ag es  a n d   n at u r a l  la n g u a g es.  P ar s in g   al g o r ith m s   f o r   C FG s   p l a y   a  s i g n i f ican t  r o le   in   th e  i m p le m en ta tio n   o f   co m p iler s   an d   in ter p r eter s   f o r   th e  p r o g r am m i n g   lan g u a g e s   an d   o f   p r o g r am s ,   w h ic h   “u n d er s ta n d ”  o r   tr an s late  th e   n atu r al  la n g u a g es.  T h er e  ex is t  t w o   d i f f er e n t  t y p e s   o f   p a r s er :  to p   d o w n   a n d   b o tto m   u p   p ar s er .   Sev er al  g o o d   alg o r ith m s   w er e  p r o p o s ed   in   liter at u r es  co n d u ct  s eq u e n tial  p ar s i n g   o f   t h e   co n tex t  f r ee   lan g u a g e s   ( C F L s ) .   So m e  o f   t h e  p o p u lar   p ar s in g   al g o r ith m s   ar e  C YK  p ar s i n g   [ 1 ,   2 ] ;  E ar ley ‟ s   p ar s in g   [ 3 ] ,   an d   T o m ita  p ar s i n g   [ 1 5 ] .   T h er e  ar e  m a n y   o th er   s tan d ar d   p ar s in g   al g o r ith m s   al s o   av ailab le,   w h ic h   in cl u d e  o p er ato r   p r ec ed en ce   p ar s in g ,   p r ed ictiv e  p ar s i n g ,   r ec u r s i v e  d escen t  p ar s i n g ,   n o n - r ec u r s i v e  d escen t   p ar s in g ,   L R   p ar s i n g ,   an d   L AL R   p ar s i n g   [ 1 6 ] .   No am   C h o m s k y   ( 1 9 5 6 )   p r esen ted   a  class i f icatio n   s ch e m e  k n o w n   as  th e  C h o m s k y   h ier ar ch y   [ 1 7 ] .   T h e  class i f icatio n   s c h e m e  p r o p o s ed   is   co n n ec ted   to   th e  class i f icatio n   o f   au to m a ta  as  s h o w n   in   t h e  Fig u r e  1 ,   w h ic h   ca n   b e  u s ed   to   r ec o g n ize  a  s p ec if ic  lan g u ag e   as  w ell  as  th e   g r a m m ar   u s ed   to   r ec o g n ize  th e m .   T h e  p r o b lem   o f   r ec o g n iz in g   a  lan g u a g e  ca n   b e  e x p lain ed   as:  “ let   L   b e  an y   lan g u ag e  o v er   a n   alp h ab et ,   th e  p r o b le m   is   to   d esig n   a n   a u to m ata   M th at  ac ce p t  an   i n p u t  s eq u en ce   in * .   T h e  M o n l y   ac ce p t th e  in p u t seq u e n ce   in   * if   th e y   ar e  v a lid   ele m e n t o f L ,   o th er w i s e  r ej ec ts ”.   Fig u r e  1   d ep icts   th at   ea ch   cla s s   o f   la n g u a g e  i n   t h e  C h o m s k y   h ier ar ch y   is   g e n er ated   b y   a  s p ec if ic  t y p e   o f   g r a m m ar ,   w h ic h   w ill  t h en   r ec o g n ize  b y   an   ap p r o p r iate  ty p e  o f   au to m ata.   Mo v i n g   u p   in   th e  h ier ar ch y   o f   t h e   lan g u a g es,  t h e  t y p e  o f   au to m ata  r eq u ir ed   to   r ec o g n ize  th e  lan g u ag e  is   c h alle n g in g ,   w h er ea s   t h e  t y p e  o f   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith m  fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   101   g r a m m ar   n ee d ed   to   cr ea te  th e  lan g u a g e  b ec o m es   m o r e  g en er al.   On e  ca n   s ee   t h at  T y p e  2   lan g u a g es,  g en er ated   b y   th e  C FG,  ar e  t h e  clas s   o f   lan g u a g es  t h at  ca n   b e  r ec o g n i ze d   b y   p u s h d o w n   au to m ata  ( eq u iv ale n t  to   f i n ite   au to m ata) ,   h av e  a n   u n b o u n d ed   s tack   a v ailab le.           Fig u r e  1 .   C h o m s k y   h ier ar ch y       Gr a m m atica l  i n f er e n ce   ( GI )   o r   g r a m m ar   lear n i n g   d ea ls   w ith   id ea lized   lear n in g   p r o ce d u r e  to   ac q u ir e   g r a m m ar s   o n   t h e  b asis   o f   t h e  ev id en ce   ab o u t  th e  la n g u a g es   [ 4 - 6 ] ,   w as  e x te n s i v el y   s t u d ied   in   [ 6 - 1 4 ]   d u e  to   its   w id e  f ield s   o f   ap p licatio n s   to   s o lv e  t h e  p ar ticle  p r o b lem s .   I n   GI   p r o ce s s ,   an   in d iv id u al  g r am m ar   r u le  n ee d s   to   b e  v er if ied   u s i n g   a n   i n p u t  s t r in g   o f   a  s p ec if ic   lan g u ag e   o v er   f in i te  s tate   co n tr o ller ,   w h er ea s   a  p u s h d o wn   au to m ato n   is   u s ed   to   g e n er ate  th e  eq u i v ale n t p r o lif e r atio n   f o r   th e  lan g u a g e.   T h is   p ap er   p r esen ts   a  GI   alg o r ith m   co m b i n es  w it h   t h e  g e n eti c  alg o r ith m   ( G A ) ,   w h ic h   h as  a   p o w er f u l   g lo b al  ex p lo r atio n   ca p ab ilit y .   A   P D A   s i m u lato r   h as  b ee n   i m p le m e n ted   i n   th e  co m p u tati o n al  ex p er i m e n t  t h at   e m p lo y s   a  r ec u r s iv e  m eth o d   f o r   th e  p ar s in g   th at  r es u lt s   in   ter m s   o f   ac ce p ta n ce   o r   r ej ec tio n   o f   th e  s tr in g .   T h e  p r o ce d u r e  f o r   th e  P D A   s i m u lato r   h as  b ee n   i m p le m e n ted   an d   e x p la in ed   w i th   th e   h elp   o f   e x a m p les.   T h e  au th o r   h a s   i m p le m e n ted   t w o   p o in ts   c u t  cr o s s o v er   b ased   c y clic  cr o s s o v er   an d   i n v er ted   m u tat io n   w i th   r an d o m   o f f s p r i n g   th e n   ap p lie d   „ XO R ‟   o p er atio n   f o r   t h e  r e p r o d u ctio n .   T h e  r ep r o d u ctio n   o p er ato r s   em p lo y ed   in tr o d u ce s   d iv er s it y   i n   t h e  p o p u latio n   h elp s   t h e  GI G A   to   ex p lo r e  th e  s ea r ch   s p ac e  ad eq u atel y .   T h e  au th o r   h a s   co m p ar ed   t h e  p er f o r m an ce   o f   th e   p r o p o s ed   GI GA  w it h   t h r ee   ex i s ti n g   al g o r ith m s   n a m el y   cla s s ical   g en et ic   alg o r ith m   ( C G A )   [ 3 8 ] ,   r an d o m   o f f s p r in g   g en er atio n   g e n etic  alg o r it h m   ( R OGG A )   [ 3 6 ]   an d   cr o w d i n g   alg o r ith m   [ 3 7 ] .   T h e  co m p ar ativ e  r es u lts   lead   to   a  co n clu s i o n   th at  t h e  p r o p o s ed   G I GA   o u tp er f o r m ed   t h ese s   alg o r ith m s .   T h e  r est  o f   th e  p ap er   is   o r g an ized   as  f o llo w s :  Sectio n   2   r ev ie w s   th e  r elate d   r esear c h es  o n   GI   p r o b lem .   Sectio n   3   p r esen t s   t h e  C FG  in d u ctio n   ap p r o ac h   u s i n g   G A   ad ap ted   in   t h i s   p ap er .   T h is   s ec tio n   s h o w s   th e  c h r o m o s o m e  s tr u c t u r in g ,   f it n es s   f u n ctio n   a n d   r ep r o d u ctio n   o p er ato r s   th at   h a v e  b ee n   e m p lo y ed   f o r   C F G   in d u ctio n .   Sect io n   4   s h o w s   th e  p u s h   d o w n   a u to m ata  s i m u la to r   w it h   t h e  v ar io u s   m et h o d s   i n co r p o r ated   f o r   th e   v er if ica tio n   p u r p o s e.   T h e  ex p er im e n tal  s et u p ,   r esu lt s   an d   d is cu s s i o n   o n   r esu lt s   ar e  g iv en   i n   Sectio n   5 .     Sectio n   6   co n clu d e s   th e  p ap er   an d   ass es s es t h e  f u t u r e  p er s p ec tiv es.       2.   RE L AT E D  WO RK   Go ld   [ 1 8 ]   p r o p o s ed   th e  f ir s t  l ea r n in g   m o d el  to   ad d r ess   “ I s   th e  in fo r ma tio n   s u fficien t  to   d etermin e   w h ich   o f  th e  p o s s ib le   la n g u a g es  is   th e   u n kn o w n   la n g u a g e? ”,   b u t  it  w a s   s u f f er ed   b ec au s e  s u f f icie n t  in f o r m atio n   ab o u t  t h e  id en ti f i ca tio n   o f   co r r ec t  g r a m m ar   d o es  n o t  e x is t.  T o   ad d r ess   th e  is s u e  o f   [ 1 8 ] ,   An g lu i n   [ 1 9 ]   p r o p o s ed   tell  tales.  A lt h o u g h ,   Go ld   [ 1 8 ]   laid   th e   f o u n d atio n   o f   lear n i n g   m o d el ,   b u t  B u n k e  a n d   A lb er to   [ 2 0 ]   p r o p o s ed   t h e  f ir s t  u s ab le  lear n in g   m o d el   also   s u f f er ed   s in ce   it  w a s   u n ab le  to   d ea l  w it h   n eg ati v e  d ata,   w as   n o t  f it  f o r   n o is y   d ata,   d o es  n o t  s u itab le  f o r   a  f i n ite  s ta te  m ac h in e,   t h er ef o r e  g o o d   f o r m al  la n g u a g e  th eo r y   w a s   lo s t.  T e ac h er   an d   q u er y   lear n in g   m o d el,   al s o   r ef er r ed   as   an   o r ac le  w a s   p r o p o s ed   in   [ 2 1 ]   is   a  s u p er v i s ed   lear n in g   m o d el  i n   w h ich   a n   o r ac le  k n o w s   th e  a n s w er .   I t  w as   f o u n d   ca p ab le  in   an s w er i n g   a   p ar ticu lar   t y p e  o f   q u er y   u s i n g   a n   i n f er e n ce   s y s te m ,   b u t  i m p le m e n ti n g   a n   o r ac le  is   a  m at ter   o f   co n ce r n ,   w h ic h   n ee d s   v as t   in f o r m atio n ,   h en ce   le s s   co m m o n l y   u s ed ,   w h er ea s   Go ld ‟ s   m o d el  is   m o r e  p o p u lar .   Valian t  [ 2 2 ]   co m b i n ed   th e  b est  f ea t u r es  o f   [ 1 8 ]   an d   [ 2 1 ]   an d   p r esen ted   p r o b a b ly   ap p r o x i m atel y   co r r ec t ( P A C )   lear n i n g   m o d el.   T h e  P A C   lear n i n g   m o d el  s u f f er ed   d u e  to   th e  f o llo w i n g   r ea s o n s :   T y p e   3 R e g u l a r   L a n g u a g e T y p e   2 C o n t e x t   F r e e   L a n g u a g e C o n t e x t   S e n s i t i v e   L a n g u a g e T y p e   1 T y p e   0 U n r e s t r i c t e d   L a n g u a g e F i n i t e   A u t o m a t a P u s h d o w n   A u t o m a t a L i n e a r   B o u n d e d   A u t o m a t a T u r i n g   M a c h i n e Languages A u t o m a t a Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0   –   11 1   102   1)   P A C   lear n i n g   ass u m es   th a t  t h e  in f er en ce   al g o r it h m   m u s t  le ar n   in   p o l y n o m ial  ti m e  u n d er   all  d is tr ib u tio n ,   b u t th i s   b eliev e s   is   to o   s tr in g   i n   r ea lit y .   2)   P A C   lear n in g   is   n o t  f it  f o r   n e g ati v e  an d   NP   h ar d   eq u i v alen ce   r esu lts .   A   m o d i f ied   v er s io n   o f   P A C   m o d el   w a s   p r esen t i n   [ 2 3 ]   in   w h ic h   s i m p licit y   w as  m ea s u r ed   u s i n g   Ko l m o g o r o v   co m p le x it y .   I n d u cti v e  in f er en ce   i s   th e  p r o ce s s   o f   m ak i n g   g e n er aliza tio n   f r o m   th e  i n p u t.  W y ar d   [ 2 4 ]   s h o w ed   th e   i m p ac t  o f   d if f er en t  g r a m m a r   r ep r esen tatio n .   T h e  ex p er im en tal  r esu l ts   p r esen ted   t h a t  th e  ev o l u tio n ar y   alg o r ith m   ( E A )   u s i n g   s ta n d ar d   co n te x t  f r ee   g r a m m ar   ( C FG)   ( B ac k u s   Nau r   Fo r m   ( B NF) )   o u tp er f o r m ed   o t h er s   [ 2 4 ] .   T h an ar u k   an d   Ok u m ar u   [ 2 5 ]   class if ied   GI   in to   th r ee   ca teg o r ies:   s u p er v i s ed ,   s em i - s u p er v i s ed   an d   u n s u p er v is ed .   J av ed   et.   al  [ 2 6 ]   p r o p o s ed   a  g en etic  p r o g r am m in g   ( GP )   b ased   ap p r o ac h   to   lear n   th e  C FG.   T h e  w o r k   p r esen ted   in   [ 2 6 ]   w a s   th e   ex te n s io n   o f   th e  w o r k   d o n e  i n   [ 2 4 ] .   A   s eq u e n tial  s tr u ct u r in g   ap p r o ac h   w a s   p r o p o s ed   in   [ 2 8 ]   th at  p e r f o r m   co d in g   an d   d ec o d in g   o f   b in ar y   co d ed   ch r o m o s o m es   in to   ter m in al s   an d   n o n - ter m in al s   a n d   v ice - v er s a.   A  G A   b ased   C F G  i n d u ctio n   l i b r ar y   w a s   p r o p o s ed   in   [ 2 8 ,   2 9 ] .   A  ca s e  s t u d y   o n   GI   w a s   p r o p o s ed   in   [ 2 7 ]   in cl u d es  t h e  b asic s   o f   G A  in   w h i ch   s i m p le   cr o s s o v er   ( o n e   an d   t w o   p o in ts )   a n d   b it   in v er s io n   m u tat io n   o p e r ato r s   w er e  u ti lized .   Hr n cic  et  al  [ 3 1 ,   3 2 ]   im p le m en ted   a  m e m etic  alg o r ith m   ( M A )   f o r   GI ,   w h ic h   as s is t  d o m ai n   ex p er ts   an d   s o f t w ar e  lan g u ag e  e n g i n ee r s   to   d ev elo p   d o m ai n - s p ec if ic  la n g u a g es   (D SLs)  b y   au to m atica ll y   p r o d u cin g   a  g r a m m ar .   T h eo r is ts   an d   e m p ir icis ts   ar e  t h e  t w o   m ai n   g r o u p s   co n tr ib u ti n g   i n   GI   [ 3 3 ,   3 4 ] .   L an g u a g e  class es  a n d   lear n in g   m o d els   w er e  co n s id er ed   b y   th e   t h eo r is ts   g r o u p ,   w h er ea s   e m p ir ici s ts   g r o u p   d ea lt  w it h   p r ac tical   p r o b lem s .   A   d etailed   s u r v e y   o f   v ar io u s   GI   alg o r it h m s   h as b ee n   p r esen ted   in   [ 4 ] ,   [ 3 3 ,   3 5 ] .       3.   G RAM M AT I CAL I NF E RE NCE US I N G   G E N E T I C  A L G O RI T H M   I n   t h is   s ec tio n ,   t h e  a u th o r   h a s   p r esen ted   a   b lo ck   d ia g r a m ,   s h o w s   t h e  p r o ce s s   o f   t h e  GI   u s e s   G A.   T h er e  ex is ts   d if f er e n t  GI   ap p r o ac h es  w er e  p r o p o s ed   a s   d is c u s s ed   in   Sectio n   2 .   T h e  au th o r s   h a v e  i m p le m e n ted   a  GA   b ased   ap p r o ac h   f o r   C FG   in d u ctio n .   Fig u r e  2   d ep icts   th e  b lo ck   d iag r a m   f o r   C FG in d u ctio n   u s es a   G A .           Fig u r e  2 .   B lo ck   d iag r a m   f o r   c o n tex t  f r ee   g r a m m ar   in d u ct io n   u s i n g   G A .       T h e  o v er all  p r o ce s s   h a s   b ee n   d iv id ed   in to   t w o   d if f er e n t   p h ase.   T h e  P h ase - 1   is   r esp o n s ib le  f o r   p r o d u ctio n   r u le  g e n er atio n   a n d   v er if icatio n   o v er   P DA   s i m u lato r ,   w h er ea s   P h a s e - 2   s h o w s   th e  s tep s   o f   G A  in co r p o r ated   to   o p tim ize  t h e  s ea r ch   p r o ce s s   an d   ex p lo r e  th e  s ea r ch   s p ac e  ad eq u atel y.   T h e  GI   p r o ce s s   s tar ts   g e n er ati n g   t h e  in itial  r an d o m   b i n ar y   c h r o m o s o m e  ( B C ) ,   w h ich   i s   th en   m ap p ed   to   ap p r o p r iate  s y m b o lic  c h r o m o s o m e   ( S C )   r ep r esen tat io n   o f   ter m i n als   a n d   n o n - ter m i n als  i n   a   s eq u en t ial   m an n er .   T h e  SC   h as  b ee n   d i v id ed   in to   eq u al  b lo ck   s ize  o f   f iv e  eq u al  to   p r o d u ctio n   r u le  le n g t h .   E ac h   SC   h as   b ee n   tr ac ed   f r o m   t h e  s tar t  s y m b o l  „ S ‟   to   ter m i n al  to   r e m o v e  u s e  les s   p r o d u ctio n   a n d   r est  o f   t h e  p r o d u ctio n s   h av e  b ee n   test ed   f o r   r e m o v al  o f   lef t  r ec u r s io n ,   u n i t  p r o d u ctio n ,   a m b ig u it y   a n d   lef t  f ac to r .   A   s tr i n g   to   b e  test ed   h as  b ee n   s elec ted   a n d   p ass ed   f o r   th e  v alid it y ,   i.e .   ac ce p tab ilit y   o f   t h e  C FG  eq u iv ale n t  t o   th e  ch r o m o s o m e.   T r a i n i n g   d a t a ( P o s i t i v e   a n d   n e g a t i v e ) G e n e r a t e   r a n d o m   c h r o m o s o m e P e r f o r m   s e q u e n t i a l   m a p p i n g   o f   b i n a r y   c h r o m o s o m e   t o   s y b o l i c   r e p r e s e n t a t i o n S p l i t   t h e   s y b o l i c   r e p r e s e n t a t i o n T r a c e   t h e   r u l e   f r o m   s t a r t   s y m b o l   t o   r e p r e s e n t   t h e   s p l i t e d   s y b o l i c   r e p r e s e n t a t i o n   i n   B N F   f o r m V e r f i y   t h e   i n p u t   s t r i n g   o v e r   t h e   r u l e s   i n d u c e d   t h r o u g h   P D A   S i m u l a t o r E v a l u a t e   t h e   f i t n e s s S e l e c t i o n   o f   p a r e n t   p a i r s A p p l y   r e p r o d u c t i o n   o p e r a t i o n s R e p l a c e m e n t   t o   i n c o r p o r a t e   n e w   p o p u l a t i o n C h e c k   t h e   t e r m i n a t i o n   c o n d i t i o n D i s p l a y   t h e   f i n a l   C F G   w i t h   t h e   t i m e   c o n s u m e d P h a s e - I P h a s e - I I S t a r t S t o p Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith m  fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   103   T h e  test   s tr in g   a n d   th e  C FG  r u les  ar e  t h e  in p u t  to   th e  f i n ite   s tate  co n tr o ller ,   w h ic h   v er if i es  th e  ac ce p tab ilit y   th r o u g h   t h e  p r o li f er atio n   o n   t h e  P DA .     3 . 1 .     Chro m o s o m e  Str uct ure     A  r an d o m   in i tial  b i n ar y   ch r o m o s o m e s   ( B C )   co n s i s t  o f   s eq u en ce   o f   0 ‟ s   an d   1 ‟ s   h a v e  b e en   cr ea ted   ( s ee   Fi g u r e  4 ) .   T h e  B C   is   m ap p ed   in to   ter m in al s   a n d   n o n - ter m i n als   in   a  s eq u en tial  m a n n er   f o llo w i n g   3 - b it/4 - b it  c o d in g   t h at  d ep en d   o n   t h e  n u m b er   o f   s y m b o ls   p r ese n t  i n   th e  la n g u a g e.   I f   m o r e  th a n   t wo   s y m b o l s   ar e  u s ed   in   t h e   lan g u ag e   t h en   4 - b it   r ep r esen tatio n   h as   b ee n   u s ed   o th er w i s e  u s e  3 - b it  r ep r ese n tatio n .   T h e  s tar t  s y m b o l   „ S ‟   h a s   b ee n   m ap p ed   at  “ 0 0 0 ”  an d   „ ? ‟   r ep r esen ts   th e  n u l l  s y m b o l  m ap p ed   at  “ 0 1 0 ”,   w h er ea s   f o r   o th er s   s y m b o ls   ( ter m i n al s   an d   n o n - te r m in a ls )   ar e  u s ed   as a p p r o p r ia te.       B in ar y   ch r o m o s o m e:   0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0     C o d in g   o f   ter m i n al  a n d   n o n - te r m in a ls   No n - ter m i n als   T er m in al s   S    000   1 100   A 001   0 101   B 111   ? 010   C 011   ? 110     S y m b o lic  ch r o m o s o m e  r ep r esen tatio n : S1 ? S?? S0 A B S0 S?? S ? C 0 C A S C AA ? 0 ? A 1 S1 ?? ? SA 0 0 ?     T h e  SC ‟ s   ar e   d iv id ed   i n to   b lo ck   s ize  o f   f iv e   eq u al   to   t h e  p r o d u ctio n   r u le  le n g t h   as   s h o w n   i n   T ab le  2 ,   w h ic h   ar e  t h e n   tr ac ed   f r o m   „ S‟   to   r e m o v e  t h e  i n s u f f icie n c y   p r ese n ts .   T h e  P D A   s i m u lat o r   ac ce p ts   test   s tr i n g   an d   th e   p r o d u ctio n   r u les  a s   a n   i n p u t  f o r   a n y   s p ec if ic  la n g u ag e,   v er i f ie s   t h e  ac ce p tab ilit y   v ia  p r o lif er atio n   o n   th e  P DA .     3. 2 .    F i t nes s   F un ct io n   T h e  f itn es s   o f   an   i n d iv id u al  h a s   b ee n   ca lcu lated   in   ea c h   G A   r u n   a n d   th e n   s elec tio n   o f   p ar en t  s tr in g   i s   d o n e.   I n   GI   p r o b le m ,   t h e  f i tn es s   o f   an   i n d iv id u al  c h r o m o s o m e   lar g el y   d ep en d s   u p o n   t h e  ac ce p tan c e   ( r ej ec tio n )   o f   th e  p o s itiv e  an d   n eg at iv e  s a m p le  s tr i n g s .   T h e  f itn es s   v al u e  in cr ea s e  f o r   ac ce p tin g   p o s iti v e  ( A P )   an d   r ej ec tin g   n eg at iv e  ( R N)   s a m p le,   w h er ea s   it  d ec r ea s es  f o r   ac ce p tin g   n e g ati v e  ( A N)   a n d   r ej ec tin g   p o s iti v e   ( R P )   s am p le.   T h e  p r o b lem   s p e cif ic  f ac to r   ( s )   also   p lay s   a  s ig n i f ican t  r o le  in   G A ‟ s   p er f o r m a n ce .   I n   ca s e  o f   GI ,   p r o d u ctio n   r u le  len g t h   ( P R )   is   an   i m p o r tan t f ac to r ,   h a s   b ee n   co n s id er ed   in   th e  f it n es s   ca lc u latio n .   E q u atio n   ( 1 )   h as b ee n   ap p lied   to   ca lcu late  t h e  f i tn e s s   o f   a n   in d i v id u a l.     * ( ( ) ( ) ) ( 2 * ) F i t n e s s C A P R N A N R P C P R         ( 1 )     T h e  f o llo w i n g   co n v e n tio n   h as  b ee n   f o llo w ed   f o r   th e   s elec tio n   o f   t h e  b est  g r a m m ar   r u les:   “A   g r a m m ar   t h at  ac ce p t s   all  t h e  p o s iti v e  s tr i n g s   a n d   r ej ec ts   th e  e n tire   n eg ati v e  s tr in g   f r o m   s et  o f   tr ain i n g   d at a   w it h   m in i m u m   n u m b er   o f   p r o d u ctio n   r u le s ” .   T h e  v a lu e  o f   co n s ta n t  ( C =   1 0 )   is   f o u n d   s u f f icie n t  to   ac co m m o d ate  g r a m m ar   r u les  b lo ck s   p r esen t i n   th e  s y m b o lic   ch r o m o s o m e.       3. 3 .     Repro du ct io n O pera t o r s   T h e  GA‟ s   p er f o r m a n ce   lar g e l y   d ep en d s   o n   t h e  t w o   m o s t   co m m o n l y   u s ed   g en etic  o p e r ato r s   ar e   cr o s s o v er   an d   m u tatio n .   T h e  o p er ato r s ‟   cr o s s o v er   an d   m u tatio n   p la y   a  s i g n i f ican t  r o l e  in   th e  p o p u lat io n   d iv er s it y   m a n a g e m e n t a n d   th e r ef o r e  i m p r o v es t h e  co n v er g en ce   s p ee d .   A   v ar iatio n   o f   t w o   p o in t  cr o s s o v er   b ased   o n   th e  c y clic  cr o s s o v er   h as  b ee n   i n co r p o r ated   to   p er f o r m   th e  cr o s s o v er   o p er atio n .   T h e  in v er ted   m u ta tio n   m et h o d   h as  b ee n   ap p lied   w it h   r an d o m   m a s k .   A s   w e  k n o w   th e   m u tatio n   o p er ato r   in tr o d u ce s   d iv er s it y   i n   th e   p o p u latio n   h e l p s   to   k ee p   t h e  s ea r c h   p r o ce s s   aliv e.   R a n d o m   m as k   is   u s e f u l  in   ac h iev i n g   th e  d iv er s it y .   T h e  f o llo w i n g   co n v e n tio n   h as  b ee n   ap p lied :  “ s i m p ly   ap p l y   “ XO R ”   o p er atio n   b et w ee n   t h e  p ar e n t  s tr in g s   r ec eiv ed   a f ter   cr o s s o v er   o p er a tio n   a n d   t h e  r an d o m   o f f s p r in g ”.   An   ex a m p le  f o r   b o th   cr o s s o v er   an d   m u ta tio n   o p er atio n s   h av e  b ee n   r ep r esen ted   in   Fi g u r e  3 .             Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0   –   11 1   104   .         P1   1   1   0   1   0   0   1   1     P 11   P 12   P 13   P2   0   0   1   0   1   1   1   0     P 21   P 22     P 23           OS1   1   0   1   0   1   1   1   1     P 22   P 13   P 11   OS2   0   1   0   1   1   0   0   0     P 12   P 23   P 21   ( a)   OS1   1   0   1   0   1   1   1   1                     RM   1   0   1   0   1   0   1   0     OS1  =   OS1  XO R   R M   OS1   0   0   0   0   0   1   0   1   ( b )     Fig u r e  3 .   D e m o n s tr atio n s   o f   c r o s s o v er   an d   m u tatio n   o p er atio n s .   ( a)   R ep r esen ti n g   th e  t w o   p o in t c u t c r o s s o v er   b ased   o n   cy c lic  cr o s s o v er .   ( b )   I n v er ted   m u tatio n   b y   g e n er ati n g   r a n d o m   m a s k   ( R M)   an d   th en   ap p l y in g   XO R   o p er atio n .       3. 3 .     Ver if ica t io n o f   Rules   us ing   P DA  Si m u la t o r   T h is   s ec tio n   e x p lain s   t h e  wo r k in g   o f   p u s h d o w n   a u to m a ta  in co r p o r ated   d u r in g   C FG   in d u ctio n .   T h e  P DA   s i m u lato r   u tili ze s   v ar io u s   m et h o d s   f o r   th e  v er i f i ca tio n   p u r p o s e.   T h e  d escr ip tio n   o f   ea ch   m et h o d   u s ed   in   t h e  i m p le m en tat io n   o f   P DA   s i m u lato r   is   o u tli n ed   b e lo w :   P DA _ S imu la to r   ( in p u t_ S tr in g ,   S ta ck ) :   I t  ac ce p ts   in p u t   s tr i n g   a n d   s tac k   a s   an   i n p u t.  T h e  p u r p o s e  o f   t h i s   p r o ce d u r e  is   to   s i m u late  t h e   o v er all  w o r k in g .   I t  u s es  to p   o f   s tack   ( T OS)   f o r   th e  s i m u latio n   p u r p o s e.   I f   T OS  =  i n p u t  s y m b o l  =  $ ,   i n d icate   th at   t h e  i n p u t   s tr i n g   i s   a cc ep ted   f o r   th e   g r a m m ar .   I f   T OS  =  T er m i n al  a n d   th e  f ir s t  s y m b o l  m atc h es  w i th   th e  s y m b o l  p r ese n t  at  T OS,  th en   b o th   th e  s y m b o ls   ar e  r e m o v ed .   I f   T OS  =  n o n - ter m i n al  ( X) ,   t h e n   i n   s u c h   s it u atio n ,   all  t h e  p r o d u ctio n   o f   „ X ‟   r ep lace   t h e  T OS  w i th   t h e   r ig h t  s id e  o f   t h e  p r o d u ctio n   r u le  an d   ca ll  t h e  P DA _ S imu la to r ( )   r ec u r s iv el y .   I n   ca s e  o f   n o n - ac ce p tan ce ,   t h e  s elec ted   p r o d u ctio n   r u les r ep ea t th e  p r o ce s s   f o r   an o th er   p r o d u ctio n   th at  s tar t s   w it h   „ X ‟ .   g et_ in p u t ( T_ in p u t _ S tr in g ) :   I t  s i m p l y   r etu r n s   t h e  n e x t te r m i n al  p r esen t in   t h e  i n p u t s tr in g .   g et_ To p _ S   ( T_ S ta ck ) :   R etu r n s   T OS sy m b o l p r esen t i n   th e  s t ac k .   r emo ve _ fir s t_ in p u t ( ) :   I t is u s e d   to   r em o v e  t h e  f ir s t s y m b o l o f   th e  i n p u t stri n g .   r emo ve _ TOP_ S ta ck   ( ) :   I t is u s ed   to   r em o v e  T OS ite m   f r o m   t h e  s tac k .   co p y_ r ig h t   ( T_ S ta ck ,   X ) :   I t  ac ce p t  s tack   an d   p r o d u ctio n   r u les  as  an   in p u t.  I t  is   u s ed   to   r ep lace   th e  T OS  w it h   r ig h t  s id e  o f   th e  p r o d u ctio n   r u l e.   ve r ify_ s tr in g   ( S tr in g   s tr ) :   T h is   p r o ce d u r e  is   ex ec u ted   to   tak e   th e  d ec is io n   ab o u t  th e  ac ce p tan ce   o r   r e j ec tio n   o f   th e  in p u t stri n g   “str”   T h e  p r o ce d u r e  P DA _ S imu la t o r   ( in p u t_ S tr in g ,   S ta ck )   an d   its   as s o ciate d   f u n ctio n s   d e f i n itio n s   ar e  g iv e n   b elo w :   P r o ce d ur e:   P DA _ Sim ula to r   ( inp ut_ Str i ng ,   Sta ck )   B eg in     Set T _ in p u t_ Strin g   =  i n p u t_ S tr in g     Set T _ Stack   =  Stack     Set X   =  g et_ in p u t( )     Set S  =  g et_ T o p _ S( )     I f   s tack   o v er f lo w ( )   th e n     r etu r n   ( 2 )     E n d   I f     I f   ( E n d _ o f _ Strin g   & &   E n d _ o f _ Stac k )   th e n     r etu r n   ( 1 )     E n d   I f     I f ( S = =  T er m in a l & &   X  =  =  S)     p er f o r m   r e m o v e_ f ir s t_ in p u t ( )     p er f o r m   r e m o v e_ T OP _ Stack   ( )     E n d   I f     I f ( S =   =  n o n - ter m in al)   t h en     Fo r   all  p r o d u ctio n   r u les i n   P   s tar tin g   w it h   S     I f   p r o d u ctio n   r u le  is   N u ll t h en     p er f o r m   r e m o v e_ T OP _ Stack   ( )   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith m  fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   105     E ls e     p er f o r m   r e m o v e_ T OP _ Stack   ( )     p er f o r m   co p y _ r ig h t ( S,  x )     E n d   Fo r     E n d   I f     Set Fo u n d   =  P DA _ Si m u la to r   ( T em p _ Strin g ,   T em p _ S tack )     I f   ( Fo u n d   =  =1 )   T h en     r etu r n   1     E ls e      r etu r n   0     E n d   I f   E n d     P r o ce d ur e:   g et_ inp ut ( T _ inp ut_ Str i ng )   B eg in     r etu r n   f ir s t s y m b o l  f r o m   T _ in p u t_ Strin g   E n d   P r o ce d ur e:   g et_ T o p _ S ( T _ Sta ck )   B eg in     r etu r n   f ir s t s y m b o l  f r o m   t h e  T _ Stack   E n d   P r o c ed ur e:   r em o ve _ f ir s t_ inp ut()   B eg in     d elete   f ir s t s y m b o l  f r o m   t h e  T _ in p u t_ Stri n g   E n d   P r o ce d ur e:   r em o ve _ T OP _ Sta ck   ( )   B eg in     d elete   f ir s t s y m b o l  f r o m   t h e  T _ Stack   E n d   P r o ce d ur e:   co p y_ r ig ht(T _ Sta ck ,   X )   B eg in     C o p ies th e  R HS o f   t h e  p r o d u ctio n   X  to   T _ Sta ck   E n d   P r o ce d ur e:   ve r if y_ s tr i ng ( Str i ng   s tr )   B eg in     ST K  =  “ S$ ”     STT   =  a p p en d   “ $ ”  to   s tr     R es u lt =   P DA _ Si m u lato r   ( s tr ,   ST K)     R es u lt ( ? )     C ase  0 :     Msg   =  “ R ej ec ted ”;     C ase  1 :      Msg   =  ” A cc ep ted ”     C ase  2 :       Msg   =  “ Stac k   o v er f lo w ”   E n d     C o m p u tatio n a l   s i m u latio n   r es u lts   h a v e  b ee n   s h o w n   f o r   b o th   t h e  ca s e,   i.e .   f o r   th e   ac ce p tan ce   a n d   r ej ec tio n   o f   th e  i n p u t  s tr i n g .   T h e  s imu la tio n   r esu lt - 1   r ep r esen t  th e   ac ce p tan ce   o f   th e  in p u t  s tr i n g   “ ( ) ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) ”  in   T ab le  1 .   T h e  b est  p o s s ib le  C FG  u s ed   f o r   th i s   p u r p o s e  is   <{ S,  M} ,   {( , ) },   {S M  M ?  M ( S)  M} ,   S>.                   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0   –   11 1   106     T ab le  1 .   P DA   s i m u latio n   r es u l t - 1   f o r   lan g u ag e  “ b ala n ce d   p ar en th e s is ”  f o r   th e  te s t stri n g   “ ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) ”   BC   0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0   SC   C   )   B   )   ?   ) )   A   C   A   S   A   S   S ?   S   S   ( S )   S ?   C   A   ?   S ? ?   ?   ?   S   A   A   ?   ?   ( A   C   ( ( C )   B ) ? )   )   A   C   A   S   A   S   S   ?   S   S   ( S )   S   C   A ? ?   S ? ?   ?   ?   S   A   A ? ?   (   A   C   (   (   S p l i t t i n g   o f   S C   C ) B ) ?   ) ) A C A   S A S S ?   S S ( S )   S ? C A ?   S ? ? ? ?   S A A ? ?   ( A C ( (   C ) B ) ?   ) ) A C A   S A S S ?   S S ( S )   S C A ? ?   S ? ? ? ?   S A A ? ?   ( A C ( (   R e mo v a l   o f   u n w a n t e d   r u l e s   C ) B ) ?   ) ) A C A   S A S S ?   S S ( S )   S C A ? ?   S ? ? ? ?   S A A ? ?   ( A C ( (   R u l e   a d d e d   a r e :   S ? ? ? ?   S S ( S )   R u l e   a f t e r   u se l e ss re mo v a l   f r o m t e r mi n a l   si d e :   S ? ? ? ?   S S ( S )   R e mo v a l   o f   u n w a n t e d   r u l e s o v e r   n   n u mb e r   o f   r u l e s a d d e d   a r e   :   2   O r i g i n a l   r u l e s a r e   : : 8   R u l e   a f t e r   u se l e ss re mo v a l   f r o m S si d e :   S ? ? ? ?   S S ( S )   T e st   f o r   r e c u r si o n   a t :   S ? ? ? ?   S S ( S )   SC   M   (   S   )   M   M   (   S   )   M   S   ?   ?   M   ?   ?   M   ?   ?   ?   ?   ?   S   ?   M   ?   ?   ?   M   ?   ?   ?   ?   ?   S   M   ?   ?   ?   ?   M   ?   ?   ?   ?   ?   F i n a l   r u l e s i n d u c e d   a r e :   S M   M ?   M ( S ) M   P D A   S i mu l a t o r   p r o l i f e r a t i o n   f o r   v e r i f i c a t i o n   o f   s t r i n g :   ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) )   S T R I N G   I S   ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M$   S T R I N G   I S   ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M $   S T R I N G   I S   ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M ) M $   S T R I N G   I S   ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M ) M $   S T R I N G   I S   ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M $   S T R I N G   I S   ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M $   S T R I N G   I S   ((()))$   S t a c k   i s   M$   S T R I N G   I S   (()))$   S t a c k   i s   M ) M $   S T R I N G   I S   ()))$   S t a c k   i s   M ) M ) M $   ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) )   st r i n g   i s a c c e p t e d       T h ese  g r a m m ar s   h a v e  b ee n   in d u ce d   f r o m   t h e  tr ain i n g   d ata   em p lo y in g   a  GA   i n   Fi g u r e  2 .   I t  ca n   b e   s ee n   t h at  th e  i n p u t  s tr i n g   an d   p r o d u ctio n   r u les  ar e  th e  in p u t   f o r   th e  f i n ite  s tate  co n tr o ller ,   w h ich   v er if ie s   th e   s tr in g   an d   p r o d u ctio n   r u le s   th r o u g h   p r o li f er atio n   v ia  th e  P D A   s i m u lato r .       4.   RE SU L T S  A ND  AN AL Y SI S   T h e  co m p u tatio n al  e x p er i m e n ts   h a v e  b ee n   co n d u cted .   N et  B ea n s   I DE   7 . 0 . 1 ,   I n tel  C o r e  T M  2   p r o ce s s o r   ( 2 . 8   GHz )   w it h   2   GB   R A M  h a s   b ee n   u s ed .   Fo u r   d if f er e n t  t y p e s   o f   la n g u a g e s   o f   v ar y in g   p atter n s   h av e  b ee n   ta k e n ,   ar e  g i v en   i n   T ab le  2 .       T ab le  2 .   T est L an g u a g es  De s c r ip tio n   L - id   D e scri p t i o n s   S t a n d a r d   S e t   L1   ( 1 0 ) *   o v e r   ( 0   +   1 ) *   T o mi t a   / D u p o n t   S e t     L2   A l l   st r i n g   n o t   c o n t a i n i n g   „ 0 0 0 ‟   o v e r   ( 0 + 1 ) *   T o mi t a   / D u p o n t   S e t   L3   B a l a n c e d   P a r e n t h e se s   H u i j se n   / K e l l e r   &   L u t z   se t     L4   O d d   b i n a r y   n u m b e r   e n d i n g   w i t h   1   D u p o n t   se t         4 . 1 .     P a ra m et er s   Select io n a nd   T u nin g   T h e  o r th o g o n al  ar r a y   m et h o d   h as  b ee n   u s ed   f o r   t h e  p ar a m et er   s elec tio n .   Or t h o g o n a l  ar r a y   is   h e lp f u l   in   s etti n g   t h e  w ell  b ala n ce d   e x p er im e n t s   a n d   T ag u c h i  s i g n a l - to - n o i s e  r atio s   ( SN R ) ,   w h ich   a r e  lo g   f u n ct io n s   o f   th e  d es ir ed   o u tp u t,  s er v e  as a n   o b j ec tiv e  f u n ctio n   f o r   o p ti m iz atio n   t h at  h elp s   i n   d ata  a n al y s i s   an d   p r ed ictio n   o f   o p tim u m   r es u lts .   E q u at io n   ( 2 )   h as b ee n   u s ed   to   ev al u ate  SN R .     2 1 1 0 l o g u N u i u i y S N R N                     ( 2 )     W h er e,   i =  ex p er im e n t  n u m b er ,   u =  tr ial  n u m b er ,   i N =  n u m b er   o f   tr ials   f o r   th e  e x p er i m e n t,  an d   u y =  n u m b er   g e n er atio n s   ta k e n   in   ea ch   tr ials   to   r ea ch   to   th e  s o l u tio n .         Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith m  fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   107   T ab le  3 .   P ar am eter   s elec tio n   b y   o r th o g o n a l a r r a y   m et h o d   Ex .   N o .   PS   P R L   CS   CR   MR   M e a n s   C o f f .   V a r i a t i o n   S t d . d e v .   S N R   1   1 2 0   5   1 2 0   0 . 6   0 . 5   3 . 5 6 6 6 7   0 . 0 4 2 8 2 7 8   0 . 1 5 2 7 5 3   - 1 1 . 0 5 0 6   2   1 2 0   5   1 2 0   0 . 9   0 . 8   4 . 0 6 6 6 7   0 . 0 3 7 5 6 2 1   0 . 1 5 2 7 5 3   - 1 2 . 1 8 8 9   3   1 2 0   8   2 4 0   0 . 6   0 . 5   3 . 2 6 6 6 7   0 . 0 4 6 7 6 1 0   0 . 1 5 2 7 5 3   - 1 0 . 2 8 8 4   4   1 2 0   8   24 0   0 . 9   0 . 8   3 . 5 6 6 6 7   0 . 0 9 0 1 2 7 6   0 . 3 2 1 4 5 5   - 1 1 . 0 6 8 7   5   3 6 0   5   2 4 0   0 . 6   0 . 8   3 . 5 0 0 0 0   0 . 0 2 8 5 7 1 4   0 . 1 0 0 0 0 0   - 1 0 . 8 8 3 7   6   3 6 0   5   2 4 0   0 . 9   0 . 5   3 . 5 9 0 0 0   0 . 0 4 6 0 2 4 3   0 . 1 6 5 2 2 7   - 1 1 . 1 0 8 0   7   3 6 0   8   1 2 0   0 . 6   0 . 8   3 . 3 0 0 0 0   0 . 0 6 0 6 0 6 1   0 . 2 0 0 0 0 0   - 1 0 . 3 8 0 9   8   3 6 0   8   1 2 0   0 . 9   0 . 5   3 . 5 0 0 0 0   0 . 0 4 9 4 8 7 2   0 . 1 7 3 2 0 5   - 1 0 . 8 8 8 4   R e sp o n se   f o r   S N R   ( S mal l   i s b e t t e r )   L o w   - 1 1 . 1 5   - 1 1 . 3 1   - 1 1 . 1 3   - 1 0 . 6 5   - 1 0 . 8 3   F o r   ( P S : P R L : C S : C R : M R =   1 2 0 :   5 :   1 2 0 :   0 . 6 :   0 . 5 )   H i g h   - 1 0 . 8 2   - 1 0 . 6 6   - 1 0 . 8 4   - 1 1 . 3 1   - 1 1 . 1 3   F o r   ( P S : P R L : C S : C R : M R =   3 6 0 :   8 :   2 4 0 :   0 . 9 :   0 . 8 )   D e l t a   0 . 3 3   0 . 6 5   0 . 2 9   0 . 6 6   0 . 3 0   D e l t a :   d i f f e r e n c e   b e t w e e n   L o w :   H i g h   R a n k   3   2   5   1   4   R a n k :   b a se d   o n   d e l t a   ( 1 :   H i g h e st   a n d   5 :   L o w e st )   S u i t a b l e   C o mb i n a t i o n   1 2 0   5   1 2 0   0 . 9   0 . 8   S N R   ( smal l e r   i s b e t t e r )   - 1 2 . 1 8 8 9   S N R :   S i g n a l   t o   n o i se   r a t i o       T h e  p er f o r m an ce   o f   t h e  G A   is   s ig n if ican t l y   a f f ec te d   b y   p o p u latio n   s ize  ( P S),   ch r o m o s o m e  s ize  ( C S),   cr o s s o v er   r ate  ( C R )   an d   m u ta tio n   r ate  ( MR).   T h e  p er f o r m a n ce   o f   G A   lar g el y   d ep en d s   o n   P S,  C S,  C R   an d   MR.  I n   GI ,   p r o d u ctio n   r u le  l en g t h   ( P R L )   is   al s o   an   i m p o r tan t  f ac to r   th at  a f f ec ts   th e  r es u lt.  T h e  o r th o g o n a l   ar r ay   i n v o l v es  f iv e  co n tr o l  f ac to r s   w it h   t w o   le v els:   P S =   [ 1 2 0 ,   3 6 0 ] ,   P R L =   [ 5 ,   8 ] ,   C S=   [ 1 2 0 ,   2 4 0 ] ,   CR=   [ 0 . 6 ,   0 . 9 ]   an d   MR =   [ 0 . 5 ,   0 . 8 ] ,   w h er e  f o llo w in g   s ett in g   g av e  t h e  b est  r esu l ts   P S=   1 2 0 ,   P R L =   5 ,   C S=   120,   CR=   0 . 9   a n d   MR=   0 . 8   ( See  T ab le  3   ex p er im e n t  n u m b er   2 ,   SNR = - 1 2 . 1 8 8 9 )   is   tak en   f o r   th e  r o b u s t  p r o ce s s   d esig n   an d   to   co n d u ct  t h e  ex p er i m en ts .     4 . 2 .    P er f o rm a nce  Co m pa ris o n   T h e  au th o r   h as  co m p ar ed   th e  p er f o r m a n ce   o f   t h e  p r o p o s ed   ap p r o ac h   w i th   C G A ,   R O GG A   [ 3 6 ]   an d   cr o w d in g   m et h o d   [ 3 7 ] .   T h e  s a m e  p ar a m e ter s   s e tti n g   h a v e  b e en   u s ed   f o r   C G A ,   R OGG A   a n d   cr o w d in g   i n   t h e   p r o p o s ed   GA .   T h e  C G A  w o r k s   u s i n g   r an d o m   i n it ial  p o p u latio n   o f   f i x ed   l en g t h   ch r o m o s o m e s .   I t  s tar ts   w it h   a  s et  o f   s o lu tio n   r ep r esen ted   b y   ch r o m o s o m e.   Usi n g   an   ap p r o p r iate  s elec tio n   tec h n iq u e  a  s o lu tio n   f r o m   o n e   p o p u latio n   is   p ick ed   d ep en d i n g   o n   it s   f it n es s   a n d   u s ed   to   f o r m   a  n e w   o f f s p r in g .   T h i s   p r o ce s s   r ep ea ted   u n ti l   th e  G A   r ea c h ed   to   th e  t h r es h o ld   o r   m a x i m u m   n u m b er   o f   g en er atio n .   Fo r   th e  p u r p o s e  o f   a n   ev o lu tio n   t h e  C G A  p er f o r m   a  o n eti m e  cr o s s o v er   an d   m u ta t io n   o p er ato r   f o r   r ep r o d u ctio n .   T h en   in d i v id u a ls   ar e  p ick ed   d ep en d i n g   o n   th eir   f itn e s s   v al u e  to   ac t a s   p ar en ts   to   g en er ate  o f f s p r in g   i n   th e  n e w   g en er atio n .     I n   R OGG A ,   b e f o r e  ap p l y i n g   r ep r o d u ctio n ,   test   f o r   s i m il ar it y   o f   t h e  g e n etic  m ater ial   h a s   b ee n   co n d u ct ed   –   if   f o u n d   s i m i la r ,   th en   g e n er ate  o f f s p r i n g   –   p r o d u cin g   a  r an d o m   s o l u ti o n   o th er w is e  ap p l y   r ep r o d u ctio n   in   n o r m al  f as h io n .     De  J o n g   ( 1 9 7 5 )   in tr o d u ce d   c r o w d in g   ap p r o ac h   to   p r eser v e  p o p u latio n   d iv er s it y   w h ic h   r esu lts   i n   p r ev en ti n g   p r e m at u r e  co n v er g en ce .   I t   w a s   ap p lied   in   th e   s u r v iv al   s o l u tio n   s tep   o f   t h e  G A   to   d ec id e  w h ic h   in d iv id u al  a m o n g   t h o s e  i n   t h e  cu r r e n t  p o p u latio n   an d   t h eir   o f f s p r i n g   in d i v id u al   w il l  p ass   to   t h e  n ex t   g en er atio n .   I t e li m i n ate s   th e  m o s t si m ilar   in d i v id u al  w h e n ev er   a  n e w   o n e  e n ter s   i n   a  s u b p o p u latio n .       4 . 3 .     Resul t s   a nd   Dis cu s s io n   T h e  ex p er im e n tal  r esu lts   s h o w   t h at  G A   is   ca p ab le  in   C FG  in d u ctio n .   T h e  m i n i m u m   d escr ip tio n   len g th   ( MD L )   p r in cip le   h a s   b ee n   ap p lied   an d   f o u n d   e f f e ctiv e  in   g e n er aliza tio n   a n d   s p ec ializatio n   o f   t h e   tr ain i n g   d ata.       T ab le  4 .   Gen er ated   g r am m ar   w it h   f it n es s   v al u e  an d   to tal  n u m b er   o f   r u les   L - id   F i t n e ss   G r a mm a r   V P S , , ,   L1   1 0 1 4   < {S },  { 0 ,   1 },   {S ? ,   S 1 0 S } ,   S >   L2   1 0 1 1   < {S , C , M } ,   { 0 ,   1 },   {S C C M ,   M ? ,   M 1 S M ,   C ? ,   C 0 },  S >   L3   1 0 1 4   < {S },  {( ,   ) } ,   {S ? ,   S   ( S ) S },  S >   L4   1 0 1 2   < {S ,   M },  { 0 ,   1 } ,   {S 1 M ,   S 0 S M ,   M S M ,   M ? },  S >               Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0   –   11 1   108   T ab le  5 .   C o m p ar is o n   b ased   o n   Gen er atio n   r an g e,   th r e s h o ld ,   t i m e  co n s u m ed ,   m ea n   ( µ)   an d   s tan d ar d   d ev iatio n   ( Std .   Dev iatio n )   f o r   ea ch   lan g u ag e  L 1   th r o u g h   L 4   A p p r o a c h   L - id   G e n .   R a n g e   T h r e sh o l d   T i me   ( i n   m i l l i se c o n d )   µ   S t d . D e v i a t i o n   G I G A   L1   5 ± 2   7   3 8 8 0 1 . 1   3 . 4   2 . 5   L2   2 2 ± 1 1   26   3 1 9 2 8 2 7   1 8 . 2   6 . 9   L3   8 ± 3   18   3 6 5 8 5 1 . 8   9 . 1   5 . 2 2   L4   9 ± 4   23   2 3 5 3 6 0 . 3   1 0 . 8   5 . 4 1   C G A   L1   6 ± 2   7   2 6 0 6 4 . 1   4 . 1   2 . 7 3   L2   1 4 ± 1 0   22   2 6 9 0 7 1 1   1 7 . 4   6 . 4 3   L3   8 ± 4   12   1 9 6 3 4 7   8 . 2   2 . 4 4   L4   7 ± 6   14   7 3 7 4 9 . 7   8 . 1   3 . 8 7   R O G G A   L1   4 ± 2   7   5 6 0 1 2 . 3   3 . 9   1 . 8   L2   2 0 ± 1 2   24   3 7 0 1 9 2 5   2 5 . 7   1 0 . 3 4   L3   7 ± 3   13   2 6 8 2 7 6 . 2   7 . 2   2 . 9 7   L4   1 2 ± 6   25   3 8 0 7 6 6 . 3   12   8 . 0 1   C r o w d i n g   L1   8 ± 6   32   3 5 9 0 7 7 . 3   8 . 7   2 . 7   L2   1 4 ± 1 2   27   3 6 8 8 2 0 3   1 4 . 3   7 . 8   L3   7 ± 6   24   2 5 8 7 2 3 . 1   9 . 8   2 . 5   L4   8 ± 6   15   8 0 0 7 8 . 5   9 . 2   1 . 6       T h e  tr ain in g   s et  an d   test   s et,   w h ic h   ar e  r eq u ir ed   f o r   th e  lear n in g   h a s   b ee n   g e n er ated   w ith   len g t h   „ L ‟   ( L =  0 ,   1 ,   2 ,   …. . )   s u ch   th at  it  co v er s   all  th e  p o s s ib le  v al id   s t r in g s   o f   th e  le n g th   L   till   t h e  s u f f icie n t  n u m b er   o f   v alid   s tr i n g s   o f   co r p u s   t h at  h as  b ee n   g e n er ated .   T h e  in v alid   s tr in g s   g e n er ated   d u r in g   th i s   p r o ce s s   ar e  co n s id er ed   as  n eg at iv e   s tr i n g s .   T h e  r es u lta n t  g r a m m ar s   ar e  v alid ated   ag a in s t  t h e  b e s t  k n o w n   a v ailab le  g r a m m ar .   T h e  s ta n d ar d   r ep r esen tat io n , , , V P S ha s   b ee n   ad ap ted   to   r ep r esen t  th e  g r a m m ar s   as  p r esen ted   in   T ab le  4 .   T h e  r esu lts   ar e  co llected   as  an   av er ag e  o f   t w e n t y   r u n s ;  h e n ce   g en er at io n   r an g e  h a s   b ee n   u s ed   ( s ee   T ab le  5 ) .   T h e  P DA   s i m u lato r   an d   it s   as s o ciate d   m e th o d s   h a v e  b ee n   f o u n d   e f f ec ti v e  i n   v a lid ati n g   t h e   s tr in g s   u s in g   th e   r esu ltan t  g r am m ar   an d   i ts   eq u i v alen t   p r o lif er atio n   o n   t h e  s tack .   T h e  p r o lif er atio n   th r o u g h   P DA   s i m u lato r   p r ese n ted   i n   T ab le  1 ,   2 ,   an d   3   ar e  f o r   b es t  g r a m m ar s   r ec ei v ed   o v er   t wen t y   s u cc es s f u l   G A  r u n s .   T h e  au th o r   h as  f o llo w e d   in s ta n ta n eo u s   d escr ip to r   “ ( c u r r en t  s ta te,   cu r r en t  i n p u t  s tr i n g ,   s tack   co n te n t) ”  f o r   th e  p r o lif er atio n   p u r p o s e.   T h e  „ $ ‟   s y m b o l  i n d icate s   th e  en d   o f   t h e  i n p u t  a n d   b o tto m   o f   t h e  s tac k   r esp ec tiv el y .   T h e  au th o r   h as   s h o w n   b est   av er a g e  f it n es s   v s .   g e n er atio n   c h ar t  f o r   ea ch   la n g u a g e  L 1   t h r o u g h   L 4 ,   i n d icate s   t h at   th e   p r o p o s ed   GI GA  d o es  n o t   s h o w ed   an y   p r e m atu r e   co n v er g e n ce .   I t  was  o b s er v ed   t h at  t h e   p o p u latio n   h as  co n v er g ed   to   th e  b est  v al u e  ea r lier   in   ca s e  o f   th e  s i m p le  g r a m m ar s ,   w h er ea s   it  h as  s h o w n   s lo w  co n v er g e n ce   f o r   r el ati v el y   co m p lex   g r a m m ar .   T h e  in v er ted   m u tatio n   o p er ato r   w i th   r an d o m   m as k s   an d   t h e n   XOR o p er atio n   in tr o d u ce s   s u f f icie n t d i v er s it y   in   th e   p o p u lat io n   h elp s   i n   a v o id in g   p r e m at u r e  co n v er g en ce   th a t  is   th e  m ai n   r ea s o n ;  t h e  au t h o r   h as  co m p ar ed   th e  alg o r ith m   w it h   t h e  e x is tin g   G A   p r o p o s ed   f o r   av o id in g   p r em at u r e  co n v er g e n ce .       4 . 4 .    St a t is t ica l A na ly s is   A   s tati s tical  te s t  h as  b ee n   p er f o r m ed   co n s id er in g   t h e  h y p o t h esi s :  “ th ere  is   n o   s ig n ifica n t   d iffer en ce   in   th e  mea n   o f  s a mp les  a t  t h e  5 %  leve l  o f  co n fid en ce ”.   T o tal  1 5   s a m p les  h a v e  b ee n   d r a w n   f r o m   ea c h   alg o r ith m   f o r   th e  r a n d o m l y   s e lecte d   lan g u a g e.   T h e  d escr ip ti v e  an a l y s is   is   d ep icted   in   T ab le  7   r ep r esen ts   t h e   m i n i m u m ,   m a x i m u m   a n d   av e r ag e  f it n es s .   T h e  m ai n   A NO VA   r es u lt  is   r ep r esen ted   in   T ab le  6 .   T h e  p -   v alu e   0 . 0 0 1 < 0 . 0 5   lea d s   t o   r e j ec tio n   o f   n u ll  h y p o th e s is .   T h er ef o r e,   m u ltip le  co m p ar is o n   te s ts :  T u k e y HS D  test   h a s   b ee n   ad ap ted .   T h e  r esu lt s   o f   T u k e y HS D  test   is   d ep icted   i n   T ab le  8   in d icate s   t h at  t h e  p er f o r m a n ce   o f   t h e  GI GA  is   s i g n i f ica n tl y   b etter   t h an   C G A   a n d   R OGG A  s i n ce   th e  p - v a lu e   0 . 0 0 2   an d   0 . 0 5   is   eith er   le s s   o r   eq u al   to   th e  0 . 0 5 ,   w h er ea s   th e  p r o p o s ed   GI GA   w i th   P D A   s i m u lato r   p er f o r m   b etter   th a n   t h e  cr o w d in g   m et h o d .   Fig u r e  4   g r ap h ical l y   d i s p la y s   th e  a v er ag e  f it n es s   v a lu e  o f   ea ch   al g o r ith m .   T h e  X - a x i s   r ep r esen t s   t h e  m et h o d s   an d   th e   Y - a x i s   r ep r es en ts   th e   esti m ated   m ar g in a l a v er ag e  f itn e s s .   T h e  a v er ag e   f itn ess   o f   t h e  GI G A  is   f o u n d   b etter   th an   o t h er   ap p r o a ch es.  T h e  C G A‟ s   p er f o r m an ce   h as b ee n   f o u n d   w o r s t.       T ab le  6 .   A NOV A   tab le  s h o w i n g   g r o u p   co m p ar is o n   r es u lt s     S u m o f   S q u a r e s   df   M e a n   S q u a r e   F   S i g .   B e t w e e n   G r o u p s   3 1 9 3 8 2 . 8 3 6   3   1 0 6 4 6 0 . 9 4 5   6 . 3 8 9   0 0 1   W i t h i n   G r o u p s   9 3 3 1 4 9 . 0 3 3   56   1 6 6 6 3 . 3 7 6       T o t a l   1 2 5 2 5 3 1 . 8 7 0   59               Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith m  fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   109   T ab le  7 .   Descr ip tiv e  an al y s is   M e t h o d   N   M e a n   S t d .   D e v i a t i o n   S t d .   Er r o r   9 5 %  C o n f i d e n c e   I n t e r v a l   f o r   M e a n   M i n i m u m   M a x i m u m   L o w e r   B o u n d   U p p e r   B o u n d   C G A   15   7 4 7 . 9 8 6 7   1 3 8 . 7 6 4 7 1   3 5 . 8 2 8 8 9   6 7 1 . 1 4 1 3   8 2 4 . 8 3 2 0   5 4 0 . 2 0   9 4 4 . 5 0   R O G G A   15   7 5 9 . 3 8 6 7   1 3 9 . 4 5 0 4 9   3 6 . 0 0 5 9 6   6 8 2 . 1 6 1 6   8 3 6 . 6 1 1 8   5 6 0 . 3 0   9 5 0 . 5 0   C r o w d i n g   15   8 5 5 . 9 9 3 3   1 1 2 . 4 8 9 4 0   2 9 . 0 4 4 6 4   7 9 3 . 6 9 8 8   9 1 8 . 2 8 7 9   6 3 4 . 8 0   1 0 0 3 . 0 0   G I G A   15   9 2 5 . 6 2 6 7   1 2 3 . 6 8 3 2 8   3 1 . 9 3 4 8 9   8 5 7 . 1 3 3 1   9 9 4 . 1 2 0 2   6 1 5 . 9 0   1 0 1 1 . 8 0   T o t a l   60   8 2 2 . 2 4 8 3   1 4 5 . 7 0 2 9 6   1 8 . 8 1 0 1 7   7 8 4 . 6 0 9 3   8 5 9 . 8 8 7 4   5 4 0 . 2 0   1 0 1 1 . 8 0       T ab le  8 .   Mu ltip le  co m p ar is o n s   test   ( P o s th o c  test : T u k e y   HS D  test )   ( I )   M e t h o d   ( J)   M e t h o d   M e a n   D i f f e r e n c e   ( I - J)   S t d .   Er r o r   S i g .   9 5 %  C o n f i d e n c e   I n t e r v a l   L o w e r   B o u n d   U p p e r   B o u n d   C G A   R O G G A   - 1 1 . 4 0 0 0 0   4 7 . 1 3 5 8 0   . 9 9 5   - 1 3 6 . 2 1 0 3   1 1 3 . 4 1 0 3   C r o w d i n g   - 1 0 8 . 0 0 6 6 7   4 7 . 1 3 5 8 0   . 1 1 2   - 2 3 2 . 8 1 6 9   1 6 . 8 0 3 6   G I G A   - 1 7 7 . 6 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 2   - 3 0 2 . 4 5 0 3   - 5 2 . 8 2 9 7   R O G G A   C G A   1 1 . 4 0 0 0 0   4 7 . 1 3 5 8 0   . 9 9 5   - 1 1 3 . 4 103   1 3 6 . 2 1 0 3   C r o w d i n g   - 9 6 . 6 0 6 6 7   4 7 . 1 3 5 8 0   . 1 8 3   - 2 2 1 . 4 1 6 9   2 8 . 2 0 3 6   G I G A   - 1 6 6 . 2 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 5   - 2 9 1 . 0 5 0 3   - 4 1 . 4 2 9 7   C r o w d i n g   C G A   1 0 8 . 0 0 6 6 7   4 7 . 1 3 5 8 0   . 1 1 2   - 1 6 . 8 0 3 6   2 3 2 . 8 1 6 9   R O G G A   9 6 . 6 0 6 6 7   4 7 . 1 3 5 8 0   . 1 8 3   - 2 8 . 2 0 3 6   2 2 1 . 4 1 6 9   G I G A   - 6 9 . 6 3 3 3 3   4 7 . 1 3 5 8 0   . 4 5 8   - 1 9 4 . 4 4 3 6   5 5 . 1 7 6 9   G I G A   C G A   1 7 7 . 6 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 2   5 2 . 8 2 9 7   3 0 2 . 4 5 0 3   R O G G A   1 6 6 . 2 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 5   4 1 . 4 2 9 7   2 9 1 . 0 5 0 3   C r o w d i n g   6 9 . 6 3 3 3 3   4 7 . 1 3 5 8 0   . 4 5 8   - 5 5 . 1 7 6 9   1 9 4 . 4 4 3 6   * .   T h e   me a n   d i f f e r e n c e   i s s i g n i f i c a n t   a t   t h e   0 . 0 5   l e v e l .           Fig u r e  4 .   Me an s   o f   a v e r ag e  f it n es s   w it h   r esp ec t to   th e  alg o r it h m s   ( m et h o d s )   ch ar t       5.   CO NCLU SI O N   I n   th i s   p ap er ,   th e  GI GA   h as  b ee n   p r esen ted   f o r   C FG  i n d u ctio n .   T h e  r esu lts   r ep o r ted   p r o v id e  th e   s ig n i f ica n t  e v id en ce   ab o u t  t h e   p er f o r m an ce   o f   th e   p r o p o s ed   alg o r it h m .   T h e  2 - le v el  o r t h o g o n al   ar r a y   a n d   t h e   T ag u ch i  m eth o d ‟ s   SN R   h a v e   b ee n   in co r p o r ated   to   f in d   th e  ap p r o p r iate  p a r am eter s ‟   s e tt in g   t h at  i n tr o d u ce s   r o b u s tn es s ,   f as t  co n v er g en ce   a n d   s tatis t ical  s o u n d n es s .   T h e  a u th o r   h a s   ex ec u ted   th e  p r o p o s ed   GI GA   f o r   C F L s   an d   r eg u lar   la n g u a g es   o f   v ar y in g   co m p le x itie s .   T h e  e x p er im en tal  r es u lt s   h av e   b ee n   f o u n d   en co u r ag in g   a s   t h e   p r o p o s ed   GI GA   h a s   b ee n   f o u n d   ca p ab le  in   C FG  i n d u ctio n   an d   g r ea tl y   i m p r o v e s   th e  p er f o r m a n ce .   T h e  P DA   s i m u lato r   h as   b ee n   in co r p o r ated   in   th e   ex p er i m en ts   h a v e   b ee n   f o u n d   w o r k i n g   s u cc e s s f u ll y   f o r   t h e  li g h t  w ei g h t  e x a m p le s ,   w h ic h   ca n   b e  i m p r o v ed   f o r   th e   lar g er   le n g th   d escr ip tio n   o f   th e   tr ain i n g   d ata  s et.   T h e  r esu lt  r ec eiv ed   ap p ly in g   p r o p o s ed   alg o r ith m   h as  b ee n   co m p ar ed   w it h   o t h er   ap p r o ac h es  in d icat es  th e  s u p er io r it y   o f   th e  GI G A .   T h e   au th o r   h as  p e r f o r m ed   s tatis tical  test s   ex p lai n s   t h e  p er f o r m an ce   s ig n i f ica n ce   o f   th e  p r o p o s e d   ap p r o ac h .   T h e  cu r r en t r esu l ts   ar e  en co u r ag i n g   b u t it  w o u ld   b e  in ter esti n g   to   i m p le m e n t th e  p r o p o s ed   ap p r o ac h   Evaluation Warning : The document was created with Spire.PDF for Python.