TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.4, April 201 4, pp. 3148 ~ 3 1 5 7   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i4.4785          3148     Re cei v ed Au gust 28, 20 13 ; Revi sed  No vem ber 1 7 , 2013; Accepte d  De cem ber  7, 2013   An Improved Evolutionary Algorithm with Ne w Gene tic  Operation for Optimization Problem      Wang Jiekai, Hu Ruikai, Wang  Chao*  Coll eg e of Mathematics Sci e n c e, Harbi n  Nor m al Univ ersit y ,   Harbi n , Hei l on gjia ng Prov inc e , P.R. China    *Corres p o ndi n g  author, e-ma i l : hsd w a ngc ha o@1 26.com       A b st r a ct  An improve d  e v oluti onary a l g o rith m (SCAGA) is  propose d  in this paper f o r solvin g opti m i z at io n   prob le m. In or d e r to co ntrol g e netic o per ation s  in a n   effectiv e ran ge, th e ne w  algorith m  r e gul ate b o th of t h e   crossover prob abil i ty  an d mut a tion prob ab ilit y  w i th  t he  iteration process. In  add ition, SC AGA presents  a   new  crossover  strategy that  restricts the cros s of t he chro moso mes to s o me  extent to  protect goo d g e n e s   sche m a. W e   also  perfor m   the sch e m a t heor e m  o n  th e al gor ith m  p r ocess to  an a l y z e  th e w o rki n g   mec h a n is m of  SCAGA, and  w e  conc lu de  that the new   alg o rith m is ef fective. Accord ing to ex per i m ent  results for  some test functions  an d  T SP pro b le ms,  S C AGA  hav e a hig h  p e rformanc e  i n  both  c onstra i n e d   unco n strain ed opti m i z at ion  pr obl e m s.      Ke y w ords :  ev oluti onary  al go rithm, cr ossov e r op erator,  mu tation  op erat or, crossover  strategy, sche m a   theore m     Copy right  ©  2014 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  Geneti c  al gorithm (GA  for  sho r t) i s   a  ki nd of  typi cal  evolutiona ry  algorith m  [1]. It is  a  stocha stic  se arch alg o rith m for glob al  optim izatio n  based on  pri n cipl e co me s from evoluti o n   mech ani sm i n  nature.  Wh en GA is u s e d  to comp a r e  with other traditional alg o r ithms, its uni que  codi ng pattern and searching metho d  can often  be  more effective [2]. As a re sult, it is  approp riate f o r o p timizatio n  problem  in  compl e x  sy stem [3-5]. Ho wever,  gen etic al gorith m  al so   has  som e  sh ortco m ing s  such a s  lo cal  optimal  solutions, lo we r converg e n c e speed et c, wh ich   limit the u s e  of gen etic  alg o rithm  se riou sly. Fo r such  pro b lem, m a ny effective i m provem ent  for  geneti c  alg o ri thm have be e n  pro p o s ed i n  re cent ye a r s.  And mo st re sea r ch ab out  GA focu se d o n   the geneti c  o perato r  an d the  execution  strategy [6-8].   The sta nda rd  geneti c  op erators  actu ally pr ovide  a ki nd of sto c h a s tic  sea r ch p r ocess  with un certai n prob ability. While the  operat ors ca n give each  individual  a cha n ce for   optimizatio n, it also have  a possibility lead into  the  recessio n of the grou p [9]. To redu ce the  blindn ess of geneti c  ope rations, an im proved a dapt ive genetic a l gorithm is p r opo sed in this   pape r. Mea n w hile, the  propo sed  algo rithm use a  n e w  crossove r strate gy so  as to  ma ke t h e   algorith m  more efficient.  The  re st of th is p ape r i s   organi zed  a s  fo llows. In Se ct ion 2,  we  introdu ce th e im proved   geneti c  algo ri thm SCAGA. In Section 3,  we p r e s ent a  theoreti c al a nalysi s  use schem a theo rem  for the al gori t hm. In Section 4, expe ri ment al results both  on b enchma r k fu nction  and  T SP  probl em are given and di scu s sed. Finall y , we con c lud e  in Section 5 .       2. Impro v ed  Adap tiv e  Genetic Algo rithm  2.1. Adap tiv e  Gene tic Al gorithm   Due to the e s sen c e of evolution is a d y namic  p r o c e ss,  s o me r e s ear che r s t h in k relat e d  geneti c  para m eters sh oul d be reg u late d adaptively  rathe r  than b e ing invari abl e. The adapti v e   geneti c  algo ri thm (AGA) p r opo sed by Srinvas c ould  regulate  cro ssover and m u tation pro babil i ty  to get GA more efficient [10]. But it still  has  so me disadvantages such  as  low convergence rate  and hig h  pro bability to local conve r ge n c e.In re cent  years, many rese arche r s  in  various field s  try  to find more  efficient meth od to improve  AGA. Some  comp re hen si ve methods  could be fou n d  in   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Im proved  Evolution a ry  Algorithm  with Ne w Gen e tic Ope r ation f o r… (Wa ng Ji ekai )  3149 [11-12]. And  there  are al so  som e  works  based o n  he u r istic me cha n i sm turn out  be efficie n t [13- 14].  In this p ape r, we p r e s ent  a ne w im proved ad aptive gen etic  alg o rithm S C AG A. The  prop osed ne w algo rithm is based on  adju s ting mut a tion and cro s sover proba bility to regulate  the evolution  process. Before iteratio n, SCAGA  use  a new initiali zation meth o d  to make su re  that the initiali zed  pop ulatio n ca n di stribu te in  the solut i on spa c e ev enly. And the  algorith m  cou l d   optimize  crossover and m u tation probability dynam i c ally by i m proved  cr ossov e r and  mutati on  operators. A  seri es of ne w met hod s to  regulate th e g enetic  ope ra t o rs dynami c a lly were ap pli e d   so a s  to improve the perfo rman ce of the  propo se d alg o rithm.     2.2. Population Initializati on  In gen eral,  way of gen etic algo rithm fo r pop ulation i n itialization  is com p letely random.   Ran domly initial populatio n  tends to make indivi dual s unevenly dist ributed in the  solutio n  spa c e.  It is ea sy to  cause the i m b a lan c ed  evol ution of th e  a l gorithm  in th e iteratio n p r oce s s a nd  re sult  in local opti m al solutio n s. In order to overco me this problem,   we use a  new meth od  with  uniform  soluti on sp ace to make the init i a l individual s can b e  evenl y distributed.   Step 1: Divide the solutio n  spa c e avera gely into  N su bsp a ces a c co rding to the p opulatio n si ze .  Step 2: Each sub s p a ce ge nerate  sub - in dividual s with  completely random  way.   Step 3: Comp ose all the  su b-individ ual s and get the in itial populatio n.   The in dividual s of initial popul ation con s i s t o f   A(0)= { A 1 (0) 1 ,A 2 (0) 1 ,…,A n (0 ) 1 } ∪ {A 1 (0 ) 2 ,A 2 (0) 2 ,…,A n (0 ) 2 } ∪∪ …{ A 1 (0 ) N ,A 2 (0) N ,…,A n (0) N } ∈ R N . This   approa ch  ca n improve th e diversity o f  populatio n  on the p r em ise of initiali zing  pop ulati o n   rand omly. And it can impro v es the co nver ge nce pe rforma nce of propo se d algo rithm.    2.3. The Improv ement of Cros sov e r and Muta tion  Opera t or   Acco rdi ng to  the schem a theorem [1], the natu r e of t he gen etic al gorithm  sho u l d  be the  repla c e m ent  of the origin a l  sch ema a n d  the form ati on of excell e n t sch ema. I n  the pro c e s s o f   geneti c  op eration, it sho u l d ke ep a  ne w sch e ma a s  mu ch  as  p o ssible i n  th e early time  of  popul ation evolution, in order to mainta in populat io n  diversity. In  the later peri od of populat ion   evolution, it  should  try to  maintain  an  a ppro p ri ate m ode  and  p r ev ent the  de struction, to  p r e v ent  the algorithm  from  premat urity. Individuals  hav e  a greater probability of high adaptability  to   contai n the f i ne sch e ma,  so they a r e  more  su ita b l e for the  rel a tively small  cro s sove r a n d   mutation p r o bability du rin g  the  evoluti on. On  t he  contra ry, low fitness in dividuals not  only is  unlikely to contain fine schema, but they may  have  a possibility to dam age the fine schem a by  hybridi z ing  wi th individu als co ntaine d fin e  sch e ma. T herefo r e, th e  low fitne s s a r e mo re  suita b le   for small e r  cro s sove r probability. For the almo st  average fitness, we   ca n increa se their  crossover and mutation probab ility properly to  expl ore the  potential fine  schema i n  these  individual s.  In this pape r we uses fo rmula (1 ) as  follo w that d e crea se s pro g re ssively while the   algorith m  iterating:    ma x si n( ( 1 ) ) 2 ge n x ge n                                                                         (1)    Whe r e  ge n   rep r e s ent th e cu rrent ev olution g ene ration,  gen ma x  rep r e s ent t he preset tota l  evolution ge n e ration.   More formally, let  N  be t he po pulatio n scale,  a  b e  the p e rcen tage that a  particula r  individual fitn ess a c count s for the  sum  of all individ ual’s,  F  and  F avg   represen t the individu al  fitness a nd a v erage fitne s s of popul atio n.  Apparently, whe n  a i s   cl ose r  to  1/ N ,  we  can  see t he pa rticular  individual fitn ess  F  is   clo s er t o   F avg  , thus (1 +Na )  is cl oser to  2. Acco rdin g  to the mentio ned ab ove, at this time th e   cro s sove r p r obability  sho u ld b e  hig h e r . Conve r sely, wh en th e  F   is mo re  far f r om  F avg , nam ely  ( 1+Na ) is  clo s er to 1, the  cro s sover  probability sh o u ld be  small e r. The follo wing fo rmula  are   use d  in this p aper:     (1 ) yl n N a                                                                                        (2)    Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3148 – 3 157   3150 In orde r to regulate the  crossove r pro bab ility and  mutation pro bability in an  effecti v e   rang e, we set up follo wi ng up dating   formula fo r  cross  pro babil i ty accordi n g  to the  sigm od   function:     ma x s i n ( (1 ) ) l n (1 ) 2 gen zx y N a ge n                                        (3)    1 ' 1 c z p e                                                                             (4)    Therefore, the crossover proba bility of two individual s is:     12 '' 2 cc c pp p                                                                          (5)    Becau s e m u tation ope rato r ca n distu r b  the per fo rm ance of the algorith m  to a ce rtain   extent, the determin a tion  of mutation p r oba bility is  very importa nt. In general,  the sele ction  o f   mutation probability is m a i n ly got according to expe ri ence, so it s reliability is oft en suspectable.  Accordi ng to  the followi ng formula,  the mutation probability  could be  adjusted  dynamically i n  a  better way.     ma x s i n( ( 1 ) ) 0. 5 2 m ge n p ge n                                                                   (6)    Where pm  represent the curr ent mutation probability .     The value of  pm will decrease gradually  with  the iteration process. In this way, it ca n   avoid getting into the local optimum in the early  peri o d ,  and it can also  improve the conve r ge nce   perfo rman ce  of SCAGA in the later pe rio d .    2.4. The Improv ement of Cros sov e r Strateg y     Cro s sove r op erato r  also h a s  a great influ enc e on the converg e n c e rate of GA. However,  traditional  cro s sover op erat ion often has  a certai n blin dne ss. The of fsprin g individ uals  which are  formed  by crossover of p a r ental  ch rom o som e s may  discard o r  d e s tru c t the fin e  gene s  sche ma   existed i n   pa rental  individ uals.  The r efo r e, in   ad ditio n  to th e a d ju stable  cro s so ver a nd  muta tion   probability, this paper  al so presents a  new  crossover stra tegy based on  our  rel a ted works [15 - 16]. So that the fit schem a  existed i n  pa rental  gen er a t ion is  prote c t ed to tra n sfe r  to offsp r ing  as  far as  poss ible.   Definition 1 (Codi ng Di sta n ce ): Suppo se that two individual s are  enco ded in  binary  respe c tively,  and the codin g  length is  L ,  we say the co ding di stan ce  of  X  and  Y  is :    , 1 () L X Ym m m kc                                                                                (7)    Whe r e  k  is th e given wei g h t,  ,, ,, 1, 0, X mY m m X mY m aa c aa   Definition 2 (Codi ng simil a rity): The c o d i ng simila rity betwe en two  individual s  X  and  Y   can b e  com p uted with formula (8 ).     , 1 (, ) / L X Ym m s SX Y k                                                                         (8)    Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Im proved  Evolution a ry  Algorithm  with Ne w Gen e tic Ope r ation f o r… (Wa ng Ji ekai )  3151 Obviou sly, th e value of coding simil a rity of any two in dividual s is b e twee n [0,1].  In orde r  to control the cro s sove r op eration, he re  we u s e a critical value a s  referen c e.   Definition 3 (Standard Cro s sover Poin t): The stand ard cro s sove r p o int ( sc p ) is a critical   value to de cide weathe r  the cro s sove r op eratio n  sho u ld b e  i m pleme n ted,  and it  can  be   comp uted a s  follows:    ma x ma x 2 3 g en g e n scp ge n                                                                         (9)    From the formula (9 ),  sc p  will contin uou sly incre a se  with the iteration of geneti c   algorith m . Based o n  above  definition, the new   cro s so ver strate gy can be de scrib ed as:     The valu e of  codi ng  simila rity between  i ndividual s i s  relatively lowe r in the  pri o r  stage  of  SCAGA. In o r de r to en su re that the out standi ng g e n e tic sch e ma  will not b e  broke n  for th e full  evolution of chromo som e  group,  scp  value sh o u l d  be relativ e ly low co ntrolled  crosso ver  operation. On  the co ntra ry, in t he late  st age s of SCA G A, the difference bet wee n  individu als  can   be very small ,  so the  sc p   shall  also in crea se. Acco rding to formu l a (9 ),  the in terse c tion  of  th e   dynamic  cont rol stand ards can   hel p imp r ove the  effici ence a nd  co n v ergen ce  pe rf orma nce of t h e   algorith m .     2.5. Impro v e d  Adap tiv e   Gene tic Alg o rithm                    The main ope ratio n s of the prop ose d  algo rith m SCAGA ca n be sum m ari z ed a s  follo ws:   Step 1: Initialize po pulatio n ,  initial popula t ion con s i s t of  A(0)= { A 1 (0 ) 1 ,A 2 (0) 1 ,…,A n (0 ) 1 } ∪ {A 1 (0 ) 2 ,  A 2 (0) 2 ,…,A n (0 ) 2 } ∪∪ …{ A 1 (0) N ,A 2 (0) N ,…,A n (0) N } ∈ R N ;  Step 2: Evaluation of the fitness value of  each in dividu al;  Step 3: Selection operator:  Perf orm sele ction op erato r  and get  A(t)={A 1 (t),A 2 (t),…,A n*N (t)} ;  Step 4: Cro s sover ope rato r: Perform the cro s sove r op eration a nd g e t  A’ ( t )={ A’ 1 ( t ) ,A ’ 2 ( t ) , … ,A ’ n* N ( t )}, if  the cro s so ver ope ration  con d ition is  satisfied, wh ere the  cro s sove r pro bability can b e  cal c ulate d  according to formul a (3 )(4 )  and (5 );   Step 5: Mutation ope rato r: Perform the  mutation ope ration acco rdi ng to formula  (6) a nd turn  individual s into  A’ ’ ( t ) ={A’ ’ 1 (t) ， A’ ’ 2 (t ) ，， …A ’ ’ n*N (t)} ;  Step 6: Repe at Step3~ Step5 until a st o pping  crite r io n is sati sfied;   Step 7: Output the best so lution of all individual s.      3. The Sche ma Theorem  Analy s is for SCAG A  The sche ma  theore m  ha s been a effici e n t method for analyzin g ge netic alg o rith m. The   schema th eo rem p r edi cts  that gro w th o f  high fi tness has a g ood  effect on alg o rithm p r o c e ss,  and in dicates sho w   crosso ver and  muta tion effect  on   the propag ation of ge netic  schema. In th is  se ction, we a nalyze p r op o s ed al gorith m  with sc hema  theore m . The  symbols u s e d  is as follo ws.  H   : a present schema   f(H)       : the fitness value of sche ma  f            : the average  fitness valu e of populatio n   H f         : the average  fitness valu e of sch ema  H  s ≤ scp   C l one  th e  pa re ntal Ch r o m o s o me  it se lf N o  Ye s Perform t h e   Crosso ver ope ration   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3148 – 3 157   3152 m ( H,gen +1)  : the number  of expected o ffspring  creat ed in gen erati on  gen +1  of schem a  H   m ( H,gen)    : the number  of sch ema  H  i n  gene ration  gen +1    δ (H )         : the defining length of sch e ma  H  O(H)         : the order of  schema  H  l                   : the length of the enco ded  solutio n    M(H,g en)       : the number  of solution of  gene ration g e n  of sch ema  H   Suppo se that  the sele ction  operato r  hav e impl emente d , we here to con s ide r  the  effect  of cro s sover  operator a nd  mutation ope rator.   Acco rdi ng to  the sch e m a  theo rem, t he  nu mbe r   of expecte d  offspri ng  created in  gene ration  gen + 1  of sch e m a   H  is given b y :    () ( ) (, 1 ) (, ) [ 1 ] 1 c f HH mH g e n m H g e n p fl                                      (10)    The pa ramet e r  P c  is  given by (5), (6) and (7).                                    To sim p lify a nalysi s  p r o c e dure,  we  assume that P’ c1  is e qual s to  P’ c2 , therefore, after   sub s tituting for Pc in form ula (10 ) , we  could get:     ma x s i n ( (1 ) ) l n (1 ) 2 () 1 ( ) (, 1 ) (, ) [ 1 ] 1 1 ge n Na ge n f HH mH g e n m H g e n fl e                          (11)    No w we  coul d get the  M(H,gen ) , and to estimate its value, we co nsid er to acq u ire the   summ ation of   m ( H,gen)  ov er all sol u tion s.    (, ) 1 (, 1 ) (, 1 ) MH g e n i MH g e n m H g e n                                                    (12)         From formula  (12), we co ul d get:    ma x (, ) sin ( ( 1 ) ) l n ( 1 ) 1 2 () 1 ( ) (, 1 ) (, ) [ 1 ] 1 1 MH g e n ge n Na i ge n f HH MH g e n m H g e n fl e                   (13)    From the ine quality (13 ) , we get:     ma x (, ) s i n ( (1 ) ) l n (1 ) 1 2 () 1 ( ) (, 1 ) [ 1 ] 1 1 MH g e n ge n Na i ge n f HH MH g e n fl e                           (14)           Con s id er that   H gen H M i f gen H M H f , , 1 , we can m o d i fy (14) as:     ma x sin ( ( 1 ) ) l n ( 1 ) 2 () 1 ( ) (, 1 ) (, ) [ 1 ] 1 1 ge n Na ge n f HH MH g e n M H g e n fl e                          (15)    No w co nsi der the cro s sove r strate gy pro posed in (9 ), (10 )  in se ctio n 2.4,   We could rea rra nge terms  of formula (1 5) as follo ws:  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Im proved  Evolution a ry  Algorithm  with Ne w Gen e tic Ope r ation f o r… (Wa ng Ji ekai )  3153 ma x ma x max ma x s i n ( (1 ) ) l n (1 ) ma x 2 (2 ) () (, 1 ) (, ) 3 2 () () (, ) 3( 1 ) 1 gen Na gen ge n g e n fH MH g e n M H g e n af ge n ge n g e n fH H MH g e n af ge n l e               (16)    Formul a (16 )  rep r e s ent s t he sch e ma t heorem  influ enced by p r o posed  crosso ver op erato r   and  cro s sov e r st r a t egy  in S C A G A .       After that we could  sim p ly get form  o f  the sch e ma  theorem  of  SCAGA effe cted by  mutation ope ration as follo ws d ue to mu tation prob abi lity used in (8 ).    ma x max ma x max s i n ( (1 ) ) l n (1 ) max 2 (2 ) [ 1 ( ) ] () (, 1 ) ( , ) 3 2 () [ 1 () ] () (, ) 3( 1 ) 1 m m gen Na ge n ge n g e n O H p fH MH g e n M H g e n af gen ge n g e n H OH p fH MH g e n af g e n l e                     (17)    Since  5 . 0 2 1 sin max gen gen P m , the schema theo re m for SCAGA  could b e  gen erali z ed to:            ma x ma x max ma x max ma x s i n ( (1 ) ) l n (1 ) ma x 2 ( 2 )[ 1 ( ) s i n (( 1 ) ) 0 . 5 ] 2 () (, 1 ) (, ) 3 ( ) [1 ( ) s i n ( (1 ) ) 0 . 5 ] 2 2 () (, ) 3( 1 ) 1 ge n Na gen ge n ge n g en O H ge n fH MH g e n M H g e n af ge n ge n HO H ge n ge n g en fH MH g e n af ge n l e          (18)    Since the sch e ma theo rem  for SGA can  be de scribe d as follo ws:     () () (, 1 ) ( , ) [ 1 ( ) ] 1 cm fH H mH g e n m H g e n p O H p fl                                         (19)    Con s id er (13), we get:    (, ) 1 () () (, 1 ) (, ) [ 1 ( ) ] 1 MH g e n SG A c m i fH H M Hg e n m H g e n p O H p fl                               (20 )     To com pare  M( H , ge n+ 1 ) SC A G A  and  M(H,gen+1) SGA , we coul d divide  (18) by (20),  or we  coul d  simplify the computation a s  follows:     () (1 ) ( 1 ( ) ) (, 1 ) 1 () (, 1 ) (1 ) ( 1 ( ) ) 1 () () 1( ) ( ) 11 () () 1( ) ( ) 11 IA G A S C A G A SG A S G A S C AG A S CAG A S C AG A SCAG A SG A S G A SG A S G A IA G A cm SC A G A SG A cm cm c m cm c m cm H pO H p MH g e n l H MH g e n pO H p l H H pp O H p O H p ll HH pp O H p O H p ll pp        I A GA I A GA I A GA S G A S GA S G A S GA cm cm c m pp pp p p                              (21)  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3148 – 3 157   3154 After s u bs tituting for  P m  an d  P c  of SCAGA in formula (21), we  coul d  get:    (, 1 ) 1 (, 1 ) SC AGA SG A MH g e n MH g e n                                                                       (22)    Equivalently, from (2 2) we can imm ediat ely get:    (, 1 ) (, 1 ) IAGA SGA MH g e n M H g e n                                                   (23)    Because the probability of so lution di sruption  with  high fitness  can be small e r than  solutio n  with  lowe r fitness,  we could o b s erve  th at propo sed S C AGA use hi gh  fitness valu e  to   prom ote sche ma.  Mea n whi l e,  SCAGA could also  g e t sche ma i n crease  steadily . From  (23),   we  can  see SCA G A is more efficient than SG A according  to the sche m a theore m .        4 Simulations  4.1. Functio n  Test  In orde r to test the perfo rman ce of SCAGA, three   commo nly used multim o dal test  function a r e  perfo rmed i n  this se ction.  Both function s and th eir v a riabl e ra nge  are summa ri zed   as  follows :     24 2 2 2 1 min ( , ) ( 4 2 . 1 / 3 ) ( 4 4 ) f xy x x x x y y y       Whe n  the ran ge of  f 1   is  x ∈ (-100,1 0 0 ) ,  y ∈ (-1 00,10 0), the optimum is  -1.031 628.     55 2 11 mi n ( , ) { c o s [( 1 ) ]} { c o s [( 1 ) ] } ii f x y ii x i i i y i        Whe n  the ran ge of  f 2   is  x ∈ (-10,10 ),  y ∈ (-10,10), the o p timum is -1 8 6 .7309.     22 2 2 2 2 3 m a x ( , ) 0 . 5 ( sin 0 . 5 ) / ( 1 0. 00 1 ( ) ) fx y x y x y      Whe n  the ran ge of   f 3    is  x ∈ (-1 00,10 0),  y ∈ (-10 0,100 ), the optimum is 1.    3 12 4 3 11 2 sin ( 2 ) sin ( 2 ) min ( ) () x x f xx x      Whe n  the ran ge of  f 4  is  x 1 ∈ (0,10),  x 2 ∈ (0, 10), and the  constraine d co ndition is:     2 11 2 () 1 0 gx x x  ， 2 21 2 () 1 ( 4 ) 0 gx x x  ,    The optimum  is ( 1 .2 279713 , 4 . 2453733 ) x , ( ) 0. 095825 fx  .    5 1 mi n ( ( ) ) n n i i f nx     Whe n  the ran ge of  f 5  is  n= 10,  xi ∈ (0,1 ),  i =1,..., n , and the con s trai ned  conditio n  is:     2 1 1 () 1 0 n i i hx x  ， the optimu m  is 1 / ( 1 , ..., ) x ni n  .  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Im proved  Evolution a ry  Algorithm  with Ne w Gen e tic Ope r ation f o r… (Wa ng Ji ekai )  3155 22 2 61 2 3 mi n ( ( 1 0 0 ( 5 ) ( 5) ( 5 ) ) / 1 0 0 )) fx x x       Whe n  the ran ge of  f 6  is  xi ∈ (0,10),  i =1,2,3 , and the con s train ed cond ition is:    22 2 12 3 ( ) ( ) ( ) ( ) 0. 0625 0 gx x p x q x r  ， , , 1 , 2 , ..., 9 pqr     The optimum  is ( 5 ,5 ,5 ) x , () 1 fx .  To evaluate the perfo rma n c e of the pro pos ed alg o rit h m, SGA, AGA and PSO  is use d   for comp ari s ons.  We  test ed a bove fu nction s fo r 5 0  times to gi ve a comp arison  of ave r age  solutio n  and  optimal sol u tion for the s e four alg o rithm s ,  The optimi z at ion re sults a r e listed in Ta ble 1.      Table 1. The  Tested  Com p arison Ta ble  of SGA, AGA, PSO and SCAGA for Te st Fun c tion s  Function  SG A  AG A  PSO  SCAG A   optimal    mean  optimal    mean  optimal  mean  optimal mean   f 1   -0.9622   -0.9453   -0.9934   -0.9681   -1.0314   -0.1012   -1.0312   -1.0229   f 2   -186.7250     -186.7010     -186.7300  -186.7180  -186.7280   -186.7100  -186.7300     -186.7240   f 3   0.9999   0.9999   0.9999   0.9999-   0.9999   0.9999   0.9999   0.9999   f 4   -0.0958   -0.0966   -0.0958   -0.0967   -0.0958   -0.0947   -0.0958   -0.0958   f 5   -1.0000   -0.9866   -1.0000   -0.9972   -1.0000   -1.0000   -1.0000   -1.0000   f 6   -1.0000   0.9466   -1.0000   0.9878   -1.0000   -0.9997   -1.0000   -1.0000       From T able 1 ,  the optimiza t ion re sults of  SCAGA for  f 1-6 , including  both of co nst r aine d   and un con s trained optimi z ation pro b le m, are better than those i n  SGA and AGA and PSO  algorith m  [10]. For  f 1 (Cam el function ), comp ared th e mean an d optimal re sult s with SGA and  AGA and PSO algo rithm, except the  re sults  with t he  mean  solutio n  of PSO is sl ightly better tha n   those  of SCA G A, other  rel a ted sim u lati on re sult s of t he propo se d  algorith m  are  better than  ot he r   algorith m  for comp ari s o n .  We use  f 2 ( Sh ubert  fun c tion ) a nd  f 3 ( S c haffer  fun c tion)  to test  conve r gen ce  pe rformance   of SCAGA. The com p a r iso n  of average  results of  SG A, AGA, and  SCAGA are li sted in Tabl e 2.      Table 2. Co m parin g of Con v ergen ce Pe rforman c e of  SGA, AGA, a nd SCAGA   Algorithm Function  Populat ion Time Gene ration   SG A   f 2   100 48  58  f 2   200 50  55  f 3   300 42  96  f 3   500 45  93  AG A   f 2   100 50  54  f 2   200 50  52  f 3   300 43  92  f 3   500 44  88  SCAG A   f 2   100 50  50  f 2   200 50  49  f 3   300 42  89  f 3   500 47  87      We u s e SG A, AGA, and SCAGA to test  Schaf fer  function  and  Shub ert  function   indep ende ntly for 50  time s. Form  the  co mpari s o n   result from  Tabl e 2, the  conv erge nce time s of   SCAGA are  more tha n  SGA and SCAGA while t he co nverg e n ce g ene rati on in averag e of  SCAGA is le ss than SGA a nd AGA.   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3148 – 3 1 57   3156 Form the e x perime n t above, we can se e SCAGA has a  better co n v ergen ce   perfo rman ce  than SGA and SCAGA,  and can o b tain better  optimal sol u tion than oth e r  comp ared alg o rithm.     4.2.  TSP  Pro b lem Test  The travelin g sale sm an  probl em ( TSP ) ha s attracte d attention from  many   mathemati c ia ns  and  com puter  scienti s ts a s  a   NP -compl ete p r o b lem. It invol v es findi n g t h e   sho r test  Ha miltonian cy cle in a com p lete dire ct e d  grap h, an d it is a go od gro und t o  test  perfo rman ce  of optimizatio n algorith m .  Firstly we ch oose to test  30-city and  1 05-city  TSP  probl em to  compa r e p r efe r en ce of  SCAGA with  both SGA and AGA.      Table 3. Perf ormance of SGA, AGA, and SCAGA for TSP  Cities Average   Optimal  Genes   Pop.  Size      SG A   AG A   SCAG A   SG A  AG A  SCAG A          30(424.0 ) 442.1   430.2   428.1   0  7  9  100  1000   105(1438 3) 16344.3   14801.4  14689.3   0  4  4  500  2000       We u s e p opul ation si ze a s   1000 a nd 2 0 0 0  for 30 -city a nd 105 - city  TSP  res p ec tiv e ly. For   both p r oble m s, SCAGA  re pre s ent  a bet ter pe rfor m a n c e tha n  AGA  and SGA  on  the average  of  tour le ngth. A nd SCAGA l o cated th e o p timal solution f o r 9 tim e s i n   30-city pro b le m and  4 time s   in 105 -city problem, while  AGA located  the optimal solution for 7 ti mes in 3 0 -cit y problem  an d 4  times in 105 -city proble m .   S e con d ly ,  we  sele ct  8  TSP  instan ce s to evaluate the  effectivene ss  of SCAGA. Figure 1  is a co mpa r ison with different algorith m  for the  perce ntage deviati ons of the av erag e sol u tio n  to  the best kno w n solution.            Figure 1. Percenta ge Deviations  of the  Average Solu tion in each  TSP  Datas e t of Three  Algorithm s      As we can  see in Fi gure  1, the propo sed  S C AGA gets relativel y   smalle r  pe rcenta ge  deviation s than both SG A and AGA. That indica te SCAGA is a efficient  algorithm for   optimizatio n probl em.       5. Conclusio n   In this p ape r,  we  present  a ne w evol utionary  algo rith m SCAGA b a s ed  on th e i m prove d   geneti c  op eration, whi c h  adopt s a d y namic m e th od to re gula t e cro s sove r and mutati on  prob ability. Solution of G A  can often  be infe cted  by its ran d o m ly initializin g popul ation  and  geneti c  p a ra meter. T he i m provem ent  in this  pa pe r co uld  ma ke  the S C AGA  obtain  g r eat e r  optimizatio n  perfo rman ce  and convergen ce pe rf ormance. Mea n whil e, we  prop ose a n e w  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     An Im proved  Evolution a ry  Algorithm  with Ne w Gen e tic Ope r ation f o r… (Wa ng Ji ekai )  3157 cro s sove r st rategy to dete r mine  wh ethe r to take  cro s sover ope rati on. The  dyna mic  control for  the crossove r operation  co uld help  i m prove the conv erge nce rate  of  the algo rith m. Acco rdin g  to   the schem a theorem an al ysis for S C A G A, we c oul d see th at SCAGA is m o re efficie n t than   SGA.In Section 4,  we al so co mpa r e t he optim i z ati on pe rforma nce  of SGA G A with  sev e ral  typical alg o rit h m in 6  different test fun c tions  and  TSP  probl em s. T herefo r e, it can be  co ncl u ded  that SCAGA  is hig h ly imp r oved  and i s  efficient  to  solve both  co nstrai ned  an d un con s trai ned  optimizatio n probl em.       Referen ces   [1]  JH Holl an d. Adaptatio n in N a tural Ar tifici al S y stems. MIT  Press. 1975: 1- 1 7 .  [2]  Goldb e rg  DE.  Genetic  Al go rithms in  Se ar ch, Optimizati on  an d Mac h i ne  Le arni ng.  Rea d in g. MA:   Addis on W e sle y . 19 89.   [3]  Chu ng-C h e ng  Lu, Vi ncent F   Yu. Data  env e l opm ent a nal ysis for ev alu a ti ng th e effici en c y   of ge neti c   alg o rithms o n   solvin g the v e hicle r outi ng p r obl em  w i th s o ft time  w i nd o w s .   C o mput ers & Industria l   Engi neer in g . 2012; 2(6 3 ): 520 -529.   [4]  A Serdar T a san, Mitsuo Gen. A genetic alg o ri thm bas ed appr oach to v ehicl e routi ng  prob lem  w i t h   simulta neo us p i ck-up a nd d e li veries.  Co mput ers & Industrial  Engin eeri n g . 2 012; 3(6 2 ): 755 -761.   [5]  José A Caste l l anos-Garz ón,  F e rnan do Díaz . An ev oluti o n a r y  com putati o n a l mod e l a p p l i ed to clust e r   ana l y sis of DN A microarra y d a ta.  Expert Systems w i th Appl i c ations . 20 13;  7(40): 25 75- 25 91.   [6] D  T h ierens.  A daptiv e  mutati on rate  contro l  st rategys in  g enetic  al gorith m s . Proc eed in gs of the  20 02   Con g ress on E v oluti onar y C o mputatio n CEC .  2002   [7]  MM Lotfi, R  T a vakkoli-Mog had dam. A  ge netic a l g o rithm  usin g pr iorit y -base d  e n co di ng  w i t h  n e w   oper ators for fixe d char ge tra n sportati on pr o b lems.  App lie d  Soft Comp utin g . 2013; 5( 13): 271 1-27 26.   [8]  L Cor d e lla,  C  De Stefa no, F  F ontan ell a , A  Ma rcel li Ev o G eneS ys. A  n e w  ev ol ution a r y   ap proac h to   grap h ge nerati on.  Appl ie d Soft Comp utin g . 2013; 4(1 3 ): 192 2-19 38.   [9]  David  H W o lp e r t, W illiam G M a crea d y .  No  Free  Lunc h T heo rems for Optim i zatio n .  IEEE Transactions   on Evol utio nar y Computati on.  1997; 4(1): 6 7 - 82.  [10]  M Srinivas, L  Patnaik. Ad apt ive Prob abi liti e s of Crossover  and  Mutati on  in Genetic Al g o rithm.  IEEE   Trans. On Syst em s ， Ma n ， a nd Cyb e rnetics .   1994; 24( 4): 656-6 66.   [11]  Lich eng  Jia o ,  Lei W a ng. A  Novel  Gen e tic  Algor ithm Ba sed o n  Immu nit y .  IEEE Transactions on  Systems, Man,  and Cyb e rn eti cs- Part A: Systems a nd H u ma ns . 30; 5.  [12]  Clau d i o  Comi s, Da Ronco,  Ernesto Beni ni.  A Simple x Crossover b a sed ev oluti o n a r y  a l gor ith m   inclu d i ng the g enetic d i versit y as objectiv e .  Appli ed Soft Co mputin g. 201 3; 4(13): 210 4-2 123.   [13]  Siva Venk ad es h, Gerrit Hoog enb oom. W a lter Po tter and  Ron a ld McC l e ndo n.A gen etic  algor ithm to   refine in put dat a selecti on for air temperat ur e  predicti on us ing artifici al n e u ral net w o rks.  Appl ied Soft   Co mp uting.  2 0 13; 5(13): 2 253 -226 0.  [14]  Adam  L C hen,  Dan i e l  H M a rtinez. A  he urist i c  metho d  bas ed on gen etic alg o rithm  for  t he base lin e- prod uct desi g n .   Expert Systems w i th Appl ic ations . 20 12; 5 ( 39): 582 9-5 8 3 7 .  [15] Jiekai  W a ng.  Impr ove d  Gene tic Algorith m  B a sed o n  the Sma ll Grou p Par a lle l . International Workshop  on F u ture Com m unic a tion a n d  Net w o r ki ng. IW F CN. 2011.   [16]  CAI Mingd i, YAO Huanmi n ,  W A NG Jiekai,  etc.  A Novel E v oluti onary A l g o rith m w i th Improve d  Genetic   Operator a nd  Crossov e r Strategy . T he 2013  2nd Intern atio nal C onfer ence  on Informatio n   T e chnol og y  and Ma na gem ent Innov ation.  ICIT MI. 2013.        Evaluation Warning : The document was created with Spire.PDF for Python.