TELKOM NIKA , Vol. 11, No. 9, September 20 13, pp.  5517 ~55 2 2   ISSN: 2302-4 046           5517      Re cei v ed Ap ril 19, 2013; Revi sed  Ju n e  12, 2013; Accepted June 2 7 , 2013   Bionic Intelligent Optimization Algorithm based on  MMAS and Fish-Swarm Algorithm      Jingjing Yang* 1 , Benzhen  Guo 1 , Jixiang Gou 2 , Xiao Zhang 1   1 School of inf o rmation Sci enc e & Engin eer in g, Hebe i North  Univers i t y , Z h a ngji a ko u 07 50 0 0 , Heib ei,  P.R.Chin a, + 86-313- 804 17 35   2 School of inf o rmation Sci enc e & Engin eer in g, Lanzh ou  U n i v ersit y , L anzh o u  730 00 0, Gansu, P.R.China,  + 86-93 1-89 13 7 4 6   *Corres p o ndi n g  author, e-ma i l : r78z- y an g@1 26.com* 1 , 179 2 295 39 9@q q .co m , yjr78z @gm a il.com 2       A b st r a ct  W i th larg nu mb er  of ants, t he  ant c o lo ny  alg o ri th m w o u l d a l w a ys take   a l ong  ti me  or  is rath er   difficult to  fin d  the  opti m al  p a th fro m  c o mp lex c hapt er  p a t h, further  mor e , ther e  ex ists a c ontra dictio n   betw een sta g n a tion,  accel e ra ted co nverg e n c e a nd  prec oc ity. In this p a per, w e  pr opo se a  new  b i o n i c   opti m i z at ion   al gorith m T h e ma in id ea of  the alg o rith is  to intro duc e t he  hori z o n s c o ncept  in th e M M AS  fish sw arm a l g o rith m, so it w oul d take s hort e r time  to fin d   the opti m al p a t h  w i th nu mer o us ants, an d t he  introd uction  of the conce p t of fish sw arm al g o rith con gest i on l e vel w oul d  enab le the a n t colony find th path of  glo b a l   opti m i z at ion w i t h a stron g  cro w ding l i m it  w h i c h avo i ds th emerg ence  of l o cal  extre m a n d   improves th e a ccuracy an d efficiency  of the a l gorit hm.      Ke y w ords MMAS, artificial fish sw arm al go rithm, visi on, cong estio n  leve l     Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion   The ant colo ny algorithm  (Ant Colony  Opti mizatio n  ACO)  was p r opo sed in 19 91 by the   Italian schol a r  Dorig o  M et  al. It is an ev olutiona ry alg o rithm b a sed  on swa r m int e lligen ce  bio n ic  with the ch aracteri stics of  grou pme n t, robu stne ss, collabo ration a nd rapi dne ss [1, 2]. However,   due to the fact that ant initial motion  is ran dom, whe n  the po pulation  size  is too larg e ,  it  become s  very difficult or even impo ssi ble to  find an optimal pat h in a sho r t perio d of time,  furthermore,  with time  going on, it is   eas y  to fall  i n to lo cal mi nim a  later,  amo u n ting to le ss t han   the global opt imum. The M M AS (MAX-MIN Ant System ) is an imp r oved ant colo ny algorithm  put  forwa r d by th e Germ an re sea r che r s Stuetzle T.  The  difference b e twee n the improve d  algo rithm   and th e tra d itional  ant  colo ny algo rithm i s  that  ea ch it eration  allo ws only the  be st  perfo rmin g a n to update pat h pheromo n e ,  which  will h e lp to  prevent  prematu r e converg e n c e [3, 4].  Artificial fish  swarm algo rith m (Artificial Fi sh Swarm Al gorithm, AFS A ) [5] is pro p o se d b y   Li Xiaolei an d Qian Jixin  in 2002. The  algorithm  ha s the ability to overcome l o cal minim a  to  obtain gl obal  extreme, b u t AFSA ha s a fa ster converg e n c e j u st in th e e a rly time, th convergence speed  will be come  slower l a ter, sometim e s ev en stop the  process  of convergence so it is difficu lt to get an a c curate o p tim a l solution  wi th the only hope to find the the soluti o n   domain [6, 7] of the optimal solution.   In this pa pe r, we a nalyzes the ch aracte ri stics  of MM AS and fish  swarm  algo rithm an d   find the simila rities of the o p timization m e ch ani sm  bet wee n  these two alg o rithm s , com b ine d  wit h   the advanta g e s of  both me thods,  we  pro posed a  ne w hybrid bioni c optimizatio n algorith m   whi c can b e tter im prove the opti m izati on effici ency of the al gorithm.       2.  MMAS Algor ithm and Fis h  S w a r Alg o rithm   2.1. MMAS Algorithm  Assu me that  the numb e o f  ants in the  colony  m, the  distan ce  bet wee n  any p a th i and j  is   ,1 , 2 , . . . , di j n ij  bt i  sta n d s  fo r the  num be of ants of  poi nt i at time  t ,   1 n mb t i i t ij   is the  re sidu a l  amou nt of in formation  of  path ij a n t time t. The valu e of  0 ij  is 0, the  dire ction   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 9, September 201 3:  551 7 – 5522   5518 of movement  of ant 1, 2 , . . . kk m  is d e termin ed b a sed on th e a m ount of info rmation  on e a ch   path,   k p t ij  indi cates the probability of ant k choo sing the  path ij  at time t,  parameter   01    is a factor  repre s e n ts inf o rmatio n re si dual,  1  is a co efficient whi c h can  signify  the conte n t of the pheromo ne evapo ratio n  (i.e., t he degree  of the passag e  of informatio n). Ea ch   ant sho u ld be have to meet the followin g  con d ition s 1)  Cho o se the n e xt path with the co rre sp o ndi ng p r ob abi lity based on  the con c e n tra t ion of the   horm one in th e path.  2)  No l ong er sel e ct the  p a th t r averse d a n d  st o r e thi s  po int with  a  dat a st ru cture,  called ta bu  list to co ntrol  it, the taboo list stored all  the  path s  unt il the momen t  t and taboo  the ant to   find the optimal value agai n before a c ce ss the m  after N intera ction s 3)  After the com p letion of th e  first iteration,  ac co rdin g to  the len g th of  the path to  relea s e the   corre s p ondin g  con c e n trati ons of ph ero m one.     2.1.1. Pheromone Upd a te Rules an d Res t rictio ns  [8]   (1)  Upd a te on ly the best pe rformin g  ant pheromo n e      11 be s t tt ij ij i j                                              (1)    in the above  equatio n,   1 be s t ij be st L  (2) T he p heromone  re stri ction s : set a  uppe r an d lo wer limit s for the phe romo ne:  mi n max and ma x mi n t ij   , in ord e to avoid p r e m ature  co nve r gen ce. If ma x ij , th en  ma x ij else if mi n ij  , then  mi n ij  and eq uati on  0 mi n  shoul d b e  assured. While re sea r chi n g ,   set the  maxi mum p h e r om one to  b e  a n  estim a ted  m a ximum limit,  and   S  is a  gl obal  optimal  s o lution:      11 li m 1 t ij ij t f S                                                (2)    If got global optimal solutio n , then refre s max , try to get a  dynamic valu e of   ma x t       1 1 max ma x mi n 1 1 n P P be s t dec n P P de c be s t                                     (3)    In the above equation,   max 1 max mi n n PP dec b est    . The sele ction of maximum and  minimum ph erom one val ue is dete r m i ned by t he averag e pat h length. By setting a p a th   pheromo ne  concentratio n   to en sure it i s  n o t t oo hi g h  to avoid  premat ure  stag nation, an d t h e   same  way to avoid red u ci n g  the possibili ty of  finding a  new path.   2.1.2. Transition Rules   The probability of selecting path  ij for ant k at time t can be calculated with the following  equatio n:         0 tt ij ij k pt j a l l o w e d ij k k a llo w e d t t ki k i k ot h e r w i s e                              (4)  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046         Bionic Intelligent Optim i zation Algorith m  based on  MMAS and Fi sh-S wa rm … (Jingji ng Yang 5519 With  0, 1 , 1 a llo w e d n ta b u kk   to provi de all the po ssible p a ths a n  ant coul d select.     2.2. FISH S w arm Algorith m    The mai n  be haviors of fish swarm in cl ude  foragin g   behavio r, swarmin g  be ha vior and  followin g  beh avior.  Fora ging be havior: assu ming the cu rre nt st ate of the artificial fish swa r m  is  X i rand omly sel e ct a  state  X j  within its sen s ing  ra nge, f o r the  maxim a l value, if  YY ij , move a   step forwa r d  the dire ction ,  else ra ndo mly sele ct a state X j , determine wh ether i t  meets the   forwa r co nd itions o r  n o t. Try repeate d ly for seve ral times, if it  doe s not m e et the conditi ons  forwa r d, ra nd omly move one step.   Swarmi ng be havior: assu ming  the cu rrent state to  be  X i , explore the numb e r of  partne r n f  and  central lo cati on X c in current  neigh borhoo d   d V is a b le ij . I f   Y c Y i n f , meaning   that the pa rtn e rs have  more food  and th e clu s te is le ss  cro w de d, so m o ve on step to wa rd t he  dire ction of the cente r  of  pa rtners, othe rwise imple m en t the foraging  behavio r.   Bulletin boa rd: Re co rd th e statu s  of t he individ ual  artificial fi sh . Each a r tificial fish  individual in t he optimi z ati on proc ess  will examine  whether th e in dividual  state  is bette r tha n  the   state of the bulletin boa rd whe n  the optimization i s   co mpleted, if the state  of the  bulletin boa rd  is  better tha n  th e individu al  state, the bulle tin boa rd   stat e will  be  ch a nged  to thei own  state, th us  makin g  the b u lletin boa rd to record the history optim al state.   Its behavio mech ani sm i s  to sele ct b ehavior to  m a ke th e big g e st a c t in th e optimal  dire ction forward, if fail to  make the n e xt stat e behavior better than  the current b ehavior, take a  rand om be ha vior.      3.  A Ne w   Hy brid Bionic Optimization Al gorithm   3.1. Thought of the Alg o r i thm  MMAS fish swarm algo rith m belong s to swar m optimi z ation alg o rit h m, when the  number  of individual s rea c h a cert ain extent, the entire  po pu lation will exh i bit some inte lligent beh avior.  The ant colo ny is to find the optimal p a ths,  whil e fish swa r m is to find a food so urce. T h e   simila rities b e t ween them a r e as follo win g 1)  For  ant colo ny algo rithm,  0 ij  is  equ al e v erywhe re  at the be ginni ng, all a n t s   randomly sel e cted path; While the fish sw arm algori thm will try to  select a state  X j  randomly.   2)  Ant colony al gorithm  will perform the  conv ergence of the algorit hm  according to the  update  of p h e rom one,  na mely  1 t ij . The   more  ph ero m one s, the m o re a n ts. Fi sh  swarm  algorith m   p e rform conve r g e s ba sed   on  clu s ters  and   rea r-e nd  beh avior. G ene rally, for a r tificial  fish, whe r e t here  i s  m o st  wate r, the r e  is mo st foo d ,  that is,  the  optimal  soluti on d o main.  T he  large r  the n u m ber  of artificial fish is, the mo re it  is lik ely to attrac t more artific i al fis h . So  the  clu s ters and  rear-en d  beh a v ior of ants is similar  to secrete phe rom o nes b ehavio r of fish stocks.  Whe n  the nu mber of ant  colony is very  la rge, the mo vement of most ants  are  random,  so i n  thi s  a r ticle,  we i n trod uce d  visi on  concept  b e fore  ea ch ite r atio n of the  fish -swarm al gorith m .   Whe n  ant  u pdate p h e r o m one to  choo se  path ij  with  larg est  k p t ij , if there  exists a b e tter path   in all paths  within visio n , that is  dt d t ij vi s ual , then the ant will  try to select  be st iVisual   again, or, ij is the final choi ce.   At the begi n n ing  of the  algorith m , an t colo ny alg o rithm i s  e a sy to fall int o  lo cal  conve r ge nce, so in this p a per, we intro duce a pa ra meter  , a degree of cong e s tion of the fish   swarm  algo ri thm  co ncept , which  can  avoid p r emat ure self-agg regation phe romone   at  ea rly  time, which n o t only preve n ts prematu r e ant col ony redu nda nt co nverge nce, b u t also imp r o v es  the ability of  global o p timization.  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 9, September 201 3:  551 7 – 5522   5520 3.2.  Main Steps  of the  Algori t hm   Take th e tra v eling salesman p r obl em  (TSP) [9] a s  exampl e, the main  ste p s of the   algorith m  are  as follo wing:   Step 1 : Set i n itial time t =  0, put m a n t into n  cities  ra ndomly, the i n itial co ncent ration  of  pheromo ne for ea ch path i s    00 ij Step 2 : Set  S = 1,(s is th e su bscri p t of the tabu  li st), store th e ini t ial city numb e r of Kth  ant into  ta b u s k  which stand s for t he Sth city the curre n t ant is traveling in.   Step 3 : The probability of ant k shifting  from position i to position  k is:        0 tt ij ij k p t j a llow e d ij k ka l l o w e d t t ki k i k ot h e rw i s e                              (5)    Equation 0, 1 , 1 a llo w e d n ta b u kk   indicate s all the  cities the  ant coul d ch oo se and  are   two pa ram e ters  re pre s e n t the phe rom one the  ant  accumul a ted  while m o vin g , and g ene rally   t ij equal s to  1 d ij Step 4 : Ant k fist inspe c t a t  position i, the vision value  is  d vi s u a l , which  will  find a path ix  rand omly and  then comp are   k p t ij  with the largest path ij, if  dd ij ix , then choo se path ij, else,  cho o se path i x Step 5 : Whe n  the ant moving as the a bov e path, calcul ate the conge stion  ij with the  followin g  equ ation:      2 t ij ij t ij ij                                                          (6)    If  t ij  , we kno w  that the path is  not that crowd ed, then the ant will move from p a th i to   path j  according to this path, else, in  the fe asible neighborhood  the ant will re-sel ect a sub- optimal p a th.   t  is th e thre shol d ant ti me t which  will up date  a c cordi ng to  the e quation    1 ct te  Step 6 : After n iteration s , update the ph e r omo ne,      11 best tt ij ij ij                                            (7)    In the a bove  equ ation,  1 be st ij best L  . Each  iteratio n p r ocess just update  the  best  pe rformi ng   ant phe romo nes to avoi d  sea r ching to o co nc entrat ed mainly a d opting ph ero m one  smo o thing  mech ani sm to adju s t the  con c e n tration  of the phero m one, in a ccorda n ce with  the pro porti on  update d .   Step 7 : On cycle  to  upda te the  bulletin  boa rd, th cycles of th e o p timal p a th.  Until the   next cycle if there i s  a better path than t he  value, the n  update the  bulletin boa rd  again.   Step 8 Rep e a t Step 2 to  Step 7 until  converg e n c a s  a  path o r  a  spe c ified  nu mber  of  times .   Step 9 : The a l gorithm termi nated with th e output of op timal solution.     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046         Bionic Intelligent Optim i zation Algorith m  based on  MMAS and Fi sh-S wa rm … (Jingji ng Yang 5521 4.  TSP Instanc e  Simulation  In ord e r to te st the effe ctivene ss  of the  al gorith m , take the traveli n g sal e sman  p r oble m   Oliver 30 a s  an insta n ce o f  the calcul ation.   The p a ram e ter  setting s are as foll owi n gs: n = 10 0, try_numbe r=1 0 =1,   =5,   = 0 .1,  NC_max=20 0 , Q = 100, =0. 6 . The  alg o rit h m i s   reali z e d  with  Matla b 7 .0, the  co nfiguratio of th e   PC is: Pentiu m Dual -core  E5400 2G RAM.  Optimizatio n  curve a nd the  shorte st path  is sho w n in F i gure 1.               Figure 1. The  Optimizing  Curve of the I m prove d   Algorithm   Figure 2. The  Average Le n g th  and the Sho r test Path of the  Improved Alg o rithm   Figure 3. The  eil76 Path  of the Improved Algorithm       As the data show in the ab ove figure, st anda rd optim al solution i s  423.74 06; the integer  distan ce fo r 420. The al g o rithm of hi s pape r a c hiev es a o p timal  distan ce of 4 23.207 1, slig htly  better than th e optimal sol u tion whi c h i m pr ove d  the accuracy of the algo rithm.   To furthe r vali date the me rits of the imp r o v ed algo rithm  comp are d  wi th other al gori t hms,  we take the T SP problem e il76 (76  cities) as exam ple.       Table 1. Co m pari s on of the  Propo sed Al gorithm  with other Algo rith ms  Algorithm Maximum  length   Mi nimum length  Average length   AFSA 588.14   554.32   570.27   ACO 565.16   545.97   553.04   SA 570.42   548.26   564.67   MMAS 561.38   544.08   551.83   Proposed  Algorithm  556.29  543.86   549.04       5. Conclu sion   Bionic alg o rit h m based on  MMAS fish swarm algo rith m were intro duced in the con c e p of vision and  conge stion  of the fish swarm al go rithm enabli ng the ant colon y  optimizatio n to  better avoid  l o cal   minim a  and improve the effici ency  of the algorithm. However, MMAS require   relatively hig h  about pa ra meters com p ared  with  AFSA. The improved algo rith m of this pap er is  mainly ba se d  on a n t colon y  algorithm,  so pa ramete rs wo uld h a ve  a direct im pa ct on t he  re sults   of algo rithm.  Ho w to  ma ke  the m o st  ap prop riate   choi ce  of p a ra me ters or  cho o se a  an  alg o rit h whi c h ha le ast req u ire m ents abo ut  p a ram e ters  to  perfo rm org a n ically  i n tegration  of intelli gent  algorith m an d de sign  efficient and m o re ada ptive al gorithm  used  to solve the  a c tual p r obl em  is   what we must  continu e  to do wi th the following res e arc h  work .     Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046   TELKOM NIKA  Vol. 11, No . 9, September 201 3:  551 7 – 5522   5522 Ackn o w l e dg ement  This work was su ppo rted  by the National  Scien c and Te chn o l ogy Support  Program  (No. 20 12BA J 18B0 8 ) of M i nistry  of Scie nce a nd Te ch nology.       Referen ces   [1]  Dorig o  M, M a n i ezzo  V, Co lor n i A. P o sitiv e  f eed back  as  search  strateg y . T e chnic a R eport  91- 016 ,   Dipartim ento d i  Electronic a , Politec nico d i  Mil ano, IT . 1991.   [2]  Color n i A,  Dori go M, Ma niezz o  V.  Distri bute d  opti m i z a t i on  by ant c o l oni e s . Procee din g s  of the F i rs t   Europ e a n  Conf erenc e on Artifi cial Lif e . Elsevi er. 1992; 1 34-1 42.   [3]  Stutzle T ,  Hoos H.  Improvements on the ant system Introducing MAX-M I N ant system .  Proce edi ng s   of the Inter nati ona l Co nfere n c e on  Artificia l   Neur al N e t w or ks and  Gen e tic  Algor ithms. W i en: Spr i n ger   Verla g . 199 7; 245-2 49.   [4] Stutzle  T .   MA X-MIN ant system for Q uadr a t ic Assign ment  Probl e m s . T e chnic a l R e p o rt AIDA-97-0 4 ,   Intellect Grou p ,  Department  of Comput er Scienc e,  Darm stadt Univers i ty of T e chnol o g y ,  Germa n y .   199 7.  [5]  W ang C u iru,  Z hou C h u n le i, Ma Jia n w e i.   An Improv ed  Artificial F i s h -sw a rm Al gorit hm an d Its   Appl icatio n in  F eed-forw ard  Neural N e tw orks . Proceed i ngs of 200 5 Internati o n a l C onfere n ce o n   Machine Learning and Cy bernetics. Piscata w a y ,  USA: IEEE Press.  2005: 289 0-28 94.   [6]  Jian g Min g y a n , Yuan D o n g feng.  Wavelet Threshold  Optim i z a t i on  with Artificial Fish Swarm  Algorit h m .  Pro c eed ings  of 2 005  Internati o nal  Co nfer enc e o n  N eura l   Net w orks. Pis c ata w a y , U S A :   IEEE Press. 2005: 569- 57 2.   [7]  CR W a n g , C L  Z hou, JW  M a An i m prove d  artifici al  fish -sw a rm a l gor ithm a nd  its a pplic atio n i n   feedforw a rd  n eura l  n e tw orks.  Proc. of th F ourth Int. C o nf. on M a ch in e L earn i n g   an d C y b e rn etics.   200 5; 289 0-28 94.   [8]  T homas stutzl e, Holg er Hoo s MAX-MIN a n t system  and local searc h  for combinatorial optim i z at io prob le ms . Proc . Of 2nd Int. On Metahe uristic s . W i en: Spring er-Verla g. 199 7.  [9]  Chio ng R. Nat u re-Insp i red Al gorithms  for Optimisati on, Sp ring er. 200 9; 536.   Evaluation Warning : The document was created with Spire.PDF for Python.