Int ern at i onal  Journ al  of El e ctrical  an d  Co mput er  En gin eeri ng   (IJ E C E)   Vo l.   11 ,  No.   1 ,  Febr uar y   2021 , pp.  71 6 ~ 727   IS S N: 20 88 - 8708 ,  DOI: 10 .11 591/ ijece . v11 i 1 . pp 716 - 727          716       Journ al h om e page :  http: // ij ece.i aesc or e.c om   Stoch astic loc al sear ch:   a   state - of - t he - art r evie w       Muhame t  K astra ti,  Ma re ng l en Bi ba   Depa rtment  o f  C om pute r  Scie n ce,  Univer si t y   of   N ew  York Tirana,   Albania       Art ic le  In f o     ABSTR A CT   Art ic le  history:   Re cei ved   N ov  4 , 2 01 9   Re vised  Ju l   1 2 ,   2020   Accepte d  J ul  27, 2 020       The   m ai n  objec ti ve  of  thi s  pap er  is  to  provide  a  stat e - of - the - a rt  rev ie w ,   ana l y z e  and   disc uss   stocha stic   lo ca l  se arc h  te chn i ques  used  for  solving  har d   combinat ori al   pr oble m s.  It  begi n s  with  a  short  in troduc ti on ,   m otivati on  and  som e  basic   nota t ion  on  combin at oria l  probl ems ,   sea rch   par ad igms   and  othe r  rel ev ant   f ea tur e s  of  sea rch ing   te chn ique s  as   nee d ed  for  b ac kground .     In  the   foll owin g  a  brie f  ov erv i ew  of  the   stoch asti c  lo cal  sea r c h  m et hods  al ong  with  an   ana l y sis  of  t he  stat e - of - the - art   stocha st ic   l oca l  se arc h  al gorit hm s  is  g i ven.   Fin al l y ,   the  la st   par t   of  th e   pape r   pre sen t  a nd  discuss  som e  of  the   m ost  la t est  tre nds   in  applic at ion   of  stocha sti c  l oca l  se arch   al gorit hm s  in  ma chi n e  le arn ing,   dat a  m ini ng  and  som e  othe r  are as  of  scie nc e   and  engi n ee r in g.   W e  con cl ud e   with  a   disc uss ion  on  ca pa bil ities  and   li m it ations of  sto cha sti c  lo cal  se a rch   a lgori thms .   Ke yw or d s :   An t c olony  op t i m iz ation   Ev olu ti onary a lgorit hm s   Gr ee dy r a ndom iz e adap ti ve   Iterate d  l ocal s earch   Stoch a sti c loca l search   This   is an  open   acc ess arti cl e   un der  the  CC  B Y - SA   l ic ense .     Corres pond in g  Aut h or :   Muh am et  K ast rati ,    Dep a rtm ent o f C om pu te r  Scie nce,   Un i ver sit y o f New  York  Tira na,     ”Kod ra e Die ll it ”,  Tirana , Alb ania.   Em a il :  m uh a m et .k ast rati @ gma il .co m       1.   INTROD U CTION   Re s earche rs  a r e  strug gling  to   ta ckle   com bin at ori al   pro ble m s  as  the  num ber   of   t hese  is  pr es ent  i n  sever al   br a nc he s  in  sci ence  and   i ndus try   on   w hich  c om pu ta ti on al   m et hods   ha ve  be en  wi dely   ap plied,  includi ng  arti f ic ia l  intel li gen ce,  m achine  le arn i ng,  data  m ining ,  operat ion s  resea rch,   bio - in form at i cs  an d  el ect ro nic  c omm erce.  So m e  of   the  m os t  w el l - known  c om bin at or ia l  prob le m s  include   find i ng  shor te st  o r  cheap e st  paths   in  gr a phs ,  find i ng   s olu ti ons  for  pr opos it ion al   form ulae   (S A T),   sche duli ng,  tim e - ta blin g,   plan ning,  opti m iz ing   resour c e  al locat ion   an d  oth e r  var i ou s  do m ai ns   [1 ] .   Stoch ast ic   local   search  (S LS )  ha s   pro ved   to  be   su ccess fu ll y  and   e xtensi ve ly   us ed  ap proach   for  s olvi ng   c om bin at or ia l  hard  pro blem s .    SLS  al gorithm s  us e  ra ndom i zat ion   m et ho d  durin g  the  ge ner at io n  or   sel ect ion   of  ca ndidate   so lut io ns  [1 ] .   These  al gorith m s   are  com mo nly   us e d  f or   so lvi ng   hard  c om bin at or ia l  optim iz at ion   and   decisi on  pr oble m s.     As  presente d  by   [1 ]   so m e   of   the  early   and   suc cessf ully   app li ed  exam ples  of   SLS   te c hniq ue s  us ed  f or   s ol ving  op ti m iz ation   pro blem s  includes  the   L in - K ern i gh a n  al gor it h m ,  wh ic h  is   ap plied   f or  s olv in g  t he  tra velli ng  sal es m an  prob l e m   (TSP )  [ 2],  evo l ution a ry  al gorithm s  [3 ]   and   sim ulate d  ann eal in g  [ 4]  as   well   as  so m e  oth e r   su ccess fu l  e xa m ples  of   us ing  these  al gorith m s   fo r  s olv in g  NP - c om plete   decisi on  pro bl e m s,  including   gr a ph  colo rin g  pro ble m   (G CP )  [5 ] ,   the  Sati sfiabili ty   pr oble m   i n  pro posit ion al   log ic   (SAT)   [ 6,   7].   Mo re  rec ently ,   SLS   al gorithm s  hav e  s uccess fu ll y  been   a pp li ed  for  pro ble m - so lving   a nd  fo r  m od el in g  in  var i ous  are as  of   sci entifi c an d  e ng i neer i ng problem s.   The  w orkin g  pr i nciple  in  tradit ion al   local   search  al gorit hm s  wh en  de al ing   with  an   instance  of    a  com bin at or ia l  prob le m   rely   on  the  fact  that   searc h  f or  s olu ti ons  ha ppe n  in  the  s pace  of   can did at e  s olut ion s.   Additi on al ly ,  the  local   sear ch  proce ss  sta rts  by  m ov ing   from   cur r ent  so luti on  t o  ot her   s olu ti on   i n    a  neighb orh ood  sp ace  of  the  cand i date  so lut ion s ,  an d  decis ion   on  each  se arch   ste p  has  been   m ade  by  us in g  Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Sto c hasti c local  sea rc h: A st ate - of - t he - ar t rev ie w   ( Muham et   Kastrati )   717   on ly   existi ng  inf or m at ion   [1 ] .  On   the  ot her   side,  SLS  al go rithm s,  wh en  use d  f or   so l ving   har d  c om bin at or ia l  pro blem s   are  char act erize d  by   ran dom iz ation ,  res pecti vely ,   gen e rati on   of   i niti al   so luti on s   as  well   as  decisi on s   ta ken   on  eac h  ste p  is  ty pical ly   base d  on  ra ndom iz at ion .  F urt her m or e,   som e  SLS  m et ho ds   durin g  t he  s ear c h  process  us e  s om e  kin d  of   m e m or y  te chn i ques  in  orde r  to  kee p  a  li m i t ed  num ber   of  m os t  recently   visit ed   cand i date  so l ut ion s  [1 ] .  As  m entioned  ab ove  se ver al   S L S  al gorithm s  hav e   bee n  e ffec ti ve  ap proac h  us ed   m ai nly  to  so lve  hard  com bina torial   pro blem s,  including  SA T,  M AX - S AT,   TS P,   Sc he du li ng,  Tim e - Tabli ng   and   P r otein  F old in g.   S om e  oth e r  us e fu l  pr ogress  re ga rd i ng   to  S LS  al gorithm s  fo r  S AT  is  done,   c ov e rin g  al gorithm s  of   t he  GSAT,   G W SA T,   r obust   S LS  al go rithm s  for  M AX - S AT   ( WalkS AT ,  I RoTS,   G LSS A T  an d  SA P S)  a nd  othe r hyb ri d  S LS  m et ho ds   [ 1].   SLS  al gorithm   eng i neer i ng   i nvolv e s  m any  chall enges  that   the  researc h  com m un it y  mu st  ad dr es s.  They  are  a   ve ry  stron g  s upporter   of  m any  e ff ect ive  he uri sti cs  fo r  s ol vin g   ha rd   com pu ta ti on al ly   co m plex  pro blem s.  Gen erall y,  eng inee rin g  of   the se  ty pes  of   al go rithm s  in  m anu al   way  requires  a  ver y  caref ul  and   t o  m u c h   e f f o r t   i n   o r d e r   t o   r e a c h   h i g h   a n d   a c c e p t a b l e   p e r f o r m a n c e .   O n   t h e   o t h e r   s i d e ,   a u t o m a t ic   a l g o r i t h m   c o n f i g u r a t i o n   i s   a n   i m p r e s s i v e   a p p r o a c h   i n t r o d u c e d   t o   i m p r o v e   t h e   p e r f o r m a n c e   o f   a l g o r i t h m s   f o r   c om pu ta ti on al ly  hard  pro blem s.   A  lot  of  w ork  r el at ed  to  al gorithm   eng ineerin g  has  bee n  done   by  researc h  c omm un it y  wit h  re gard   on  autom at ic   a lgorit hm   con fig urat ion   an d  pa ra m et er  tun ing   t echn i qu e s.  E xam ples  of   thes e  include  Pa ra m ILS   al gorithm   introdu ce d  by  H utter  et   al .  [8 ] ,   aut om at ed  al go rit hm s  con fi gurat ion   an d  param et er  tu ning  pr e sented   b y   H o o s  i n   [ 9 ] ,   a u t o m a t i c   d e s i g n   o f  h y b r i d   S L S  a l g o r i t h m s  b y  M a r m i o n   e t   a l . ,   [ 1 0 ] ,   g r a m m a r - b a s e d   ge ner at i on  of   SLS  heurist ic s  by  Ma sci a  et   al .  [11 ] , p erm utati on   fl ow s hop  p r oble m s  by  Pagnozzi  a nd   Stützl e   [12],  al go rithm   c o m p a r i s o n   b y   a u t o m a t i c a l l y   c o n f i g u r a b l e   S L S   f r a m e w o r k s   b y   M a s c i a   e t   a l . ,   [ 1 3 ] ,   r e v i s i t i n g   s i m u l a t e d   a n n e a l i n g   b y   F r a n z i n   a n d   S t ü t z l e   [ 1 4 ] .   O n   t h e   o t h e r   s i d e ,   F r a n z i n   e t   a l . ,   [ 1 5 ]   s t u d i e d   t h e   e f f e c t   o f   t r a n s f o r m a t i o n s   f o r   n u m e r i c a l   p a r a m e t e r s ,   F r a n z i n   a n d   S t ü t z l e   [ 1 6 ]   p e r f o r m e d   c o m p a r i s o n   o f   a c c e p t a n c e   crit eri a  in  ra ndom iz e d  local   searche s,  M u  e t al . ,   [ 17 ]  c onduct ed  a  r ese arc h on the im pact o f  au t om at ed  al gorithm  co nfi gurati on etc.   In   t he  la st  ye ar s ,  to  m uch   e ffo rt   has   bee n  m ade  by  resea rch  com m un it y  rel at ing   to   the  a ppli cat ion   of  SLS  in  var i ous  dom ai ns   of  sci ence  a nd  eng i neer i ng.  So m e  of   the  m os t  su ccessfu l  exam ples  of   S LS  app li cat io n  inc lud es:   c om bin at or ia l  pro blem s   (S AT  a nd   TSP),  arti fici al   intel li gen ce,  m a chine  le arn i ng   a nd   data  m ining ,  s cheduli ng,  ti m e - ta blin g,   prot ei n  fo l ding  an d  to  m any  oth er  areas.  I n  thi s  pap e r  we  ha ve  bee n  m uch   m or e  focuse d  on   the  r esearch  wor k  cond ucted  in  the  la st  five  ye ars  in  the  area   of   SLS .  W e  will   sta rt   with  the  work   of   Z hou  a n d  H u  [ 18 ] ,  who  presented  t he  gra dient - base d  ad aptive  stoc hast ic   search  ( G A SS)   for   n on - dif fer e ntia ble  opti m iz at i on   a nd  la tt er  Rosin  [19],  w ho   presente d  how  the   un we igh te d  SLS  c a n  b e  eff e ct ive   f or  ra ndom   CSP  be nch m ark s ,   D r ugan   [ 20] ,  in  w hich  was   prese nted  st oc hastic   Paret o  local   s earch   for  m any o bj ec ti ve  qu a drat ic  assign m ent p r oble m   instances ,   Froh li ch  et   al . ,   [ 21 ]   pr ese nte d  ap plica ti on   of SLS   for  sat isfia bili t y  m od ul o  the or ie s .   Anothe r   si gn i fic ant  co ntri bu ti on  to  t he  fiel d  include s  a  pa pe r  by  Bo ughac i  et   al . ,   [ 22 ]   wi th  re gard   to   the  app li cat io n  of   SLS  for  i m age  ste ga nogra ph y,  Wang  et   al . ,   [ 23]   on   est im at ion   of   the  di stribu ti on  al go rithm   with  a  SL S  f or  un ce rtai n  ca pa ci ta te d  arc  r outi ng   pro blem s ,  f ollow e d  by  Re zoug  a nd   B oughaci   [ 24 ]   de al ing  with  integ rati on  of   sel f - a dap ti ve  ha rm on y  search  with  a  SLS  for   ta ckling   kn a ps ac k  pro bl e m .  Fu rthe rm or e,  in  the  la st  tw o  y ears  the re  a re  sever al   ot her   s tud ie s  c onduct ed  with  reg a r d  to  t he  SL S  a pp li cat io n,   i nclud i ng  Pu ti khin  a nd   Kasc heev   [25] ,  they   us e d  S LS  f or   s olv in g   SA T  prob le m s  by  exten ding   con ti nu ou s  B oo le a n  f o r m u l a s ,   C h u   e t   a l . ,   [ 2 6 ]   p r e s e n t e d   n e i g h b o r i n g   v a r i a b l e s   b a s e d   c o n f i g u r a t i o n   c h e c k i n g   i n   S L S   f o r   w e i g h t e d   p a r t i a l   m a x i m u m   s a t i s f i a b i l i t y ,   L u o   [ 2 7 ] ,   w h o   a p p l i e d   s t o c h a s t i c   i t e r a t i v e   e v o l u t i o n   C T   rec on st ru ct io n  al gorithm   for  lim it ed - ang le   sp ar se  pro je ct ion   data,  Y u  et   al . ,   [ 28]   i ntr oduce d  the  Th om ps on   sa m pl ing   f or   op t i m izing  SLS.   Oliveira  et   al . ,   [ 29 ]   stu died  a naly sis  of  the  AC O  al gorithm   fo r  s ol ving  T SP ,  Pa quet e  an d  Stützl e   [30]   p r e s e n t e d   a   r e v i e w   o f   S L S   A l g o r i t h m s   f o r   m u l t i   o b j e c t i v e   c o m b i n a t o r i a l   o p t i m i z a t i o n ,   N i u   e t   a l . ,   [ 3 1 ]   i n t r o d u c e d     a   n e w   S L S   a p p r o a c h   f o r   c o m p u t i n g   p r e f e r r e d   e x t e n s i o n s   o f   a b s t r a c t   a r g u m e n t a t i o n ,   S a n t o s   e t   a l . ,   [ 3 2 ] ,   w h o   p e r f o r m e d  a n a l y s i s  o f   S L S   m e t h o d s  f o r   t h e  u n r e l a t e d  p a r a l l e l  m a c h i n e  s c h e d u l i n g  p r o b l e m   a n d   Weise  et   al . ,   [ 33 ] ,   who   s howe d a n  im pr oved   ge ner ic   BET - AND - R UN strate gy  w it h per form ance  pr e dicti on for   SLS.   The  num ber   of  pa per s  pu blishe d  in  la st  t wen ty   ye ars  on  so m e  of   the  m os t - well   known  com pu te r   li br aries  (s uch  as  IEE E,  Sprin ger,  Else vier  a nd  ACM)   bette r  s hows   the  l at est   tren ds   dir ect ion   a nd  sci e ntific   sign ific a nce  of  this  fiel d.   S LS  an d  it s  su ccessf ul  app li cat ion   has  a ls o  at tract ed  the   at te ntion   of  sever a l   sci entifi c  discipli nes  incl ud i ng   com pu te r  sci ence  an d  t heir   br a nc hes  s uch  as  arti fici al   intel li gen ce,  m a chin e   le arn in g,   data   m ining ,  ec on om ic s  and   m a nag em ent,  ph ysi cs,  chem istr y  an d  bi o - i nfor m at ic s.  There  has  al read y bee n o ne  excell e nt bo ok  i ntr oduce d by two pio nee r s o f  t he  fiel d,  Hoos  a nd   Stütz le  [ 1], which  present s  an  e xcell ent  a nd  c om pr ehe ns ive  ov e r view  on  SL S  m et ho ds,  te ch niques  a nd  al gorithm s  app li cat io n.   In  2015 ,   te n  ye ars  la te r , a gain we re  Hoos  a nd St ützle  [ 34]  wh o pro vid e a  ge ner al   ov erv ie w on SLS  A lg ori thm s .   This  pa per   se rv es  li k e  a  c om ple m entary  on e  t o  those   pr e viously   pu blishe d,   o n  th e  sa m e  tim e   pro vid es  sta te - of - the - art  rev i ew  on  SL S  m et ho ds,  al go rithm s  and   m os t  rece nt  de ve lop m ent  tren ds   a nd   app li cat io n  in  sci ence  an d  in du st ry.  First,  it   giv es  a  sh ort   ov e r view  on  com bin at or ia l  pro blem s  and   search   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    71 5   -   72 7   718   par a dig m s  and  so m e   oth er  use fu l  bac kgr ound  nota ti on .  T he n,   SLS  m et ho ds   are  presente d  from   three  ki nd   of  aspects  (classe s ):  the   first  cl a ss  is  known   as  “sim ple”   SLS  m et ho ds,  as   th e  te rm   sh ows  t hey  are   m ai nly   base d  on   sim ple  search  te ch ni ques,   the  sec ond  cl ass  com pr ise s  of   hybri d  SLS   m et ho ds,  w hi ch  inte gr at e  se ver al   searchi ng   te c hniq ues  an d  he ur ist ic s  an d  th e  third   cl ass  nam ed  as  “ popu la ti on - base d ”   SLS  m et ho ds  that   procee ds   with  a  set   or   po pu l at ion   of  can di date  so luti on s .   These  SL S  m et hods   com pr i se  a  nu m ber   of  well - known  te c hn i ques  w hich  m ain ly   hav e  bee n  insp ire d  by  nat ur al   phe no m en a,  an d  so m e  of  the  m os t  su cc essfu l  app li cat io n  of  these  m et ho ds  in  sci ence  a nd   i ndus try   ha ve  bee n  pr es ent ed.   Finall y,  besides  t he  r ecent  achievem ents,  so m e fu tu r e c ha ll eng es a nd li m it a ti on  are  br ie fly  d isc us se d.   The  rest  of  thi s  pa per  is  orga nized   as  th e  f ol lowing:  I n  t he   seco nd  sect io n  is  giv e n  a  bri ef  ove rv ie w   of  bac kgr ound   theo ry  sta rtin g  with  a   ge ne r al   introd uction  of  c om bin at ori al   prob le m s,  search   pa ra digm s  a nd  SLS  te c hn i qu e s.  T he  t hird  s ect ion   giv es   c om pr ehe ns ive   rev ie w  of  the  sta te - of - the - art   in  SLS  al gori thm s,   m et ho ds   a nd   t echn i qu e s  fro m   it s  early  stag e  of  de velo pm ent  to  the  present  days.  T he   four t h  sect io n  prese nts   the  m os t  recent  app li cat ion   of  SLS  al gori th m s   in  m achine  le arn in g,   da ta   m ining   an d  ot her   ar eas  in  sc ie nce   and in dustry. T he  la st sect io n pro vid es  bri efly  so m e con cl udin g rem ark s .       2.   BACKG ROU ND AN D NO TATION   In   the  f ollo wing   is  gi ven   a  sh ort   intr oduct ion   in  bac kgr ound  the or y  an d  nota ti on   as  it   has  been  c o n s i d e r e d   a s   m o r e   t h a n   n e c e s s a r y   i n   o r d e r   t o   f a c i l i t a t e   u n d e r s t a n d i n g   o f   t h e   S L S   m e t h o d s ,   t e c h n i q u e s   a n d   a l g o r i t h m s .     2.1 .     Co m bina t oria l  prob le m s   Com bin at or ia l  pro blem s  can  be  cat e gorized   in  tw o  m ajor  gro up s:  c om bin at ori al   decisi on  pr ob le m s   and  com bin at ori al   op ti m isa t i on  pro blem s.  The  tw o  prot ot ypic al   com bin at or ia l  pro ble m s  widely   known   a re  SA T   an d  TSP .   The  nu m ber   of  these  pro blem s   is   la rg e,  an d  the y  are  pr es ent  in  sever al   br a nc hes  of   c om pu te r  sci ences,  eco nom ic s  and   m anag em ent,  physi cs,  c hem ist ry,  bio - inf orm atic s  an d  oth e r  res earch   areas   in  science   and   in dustry  in  w hich  com pu ta ti onal   m eth ods  fi nd   ap pl ic at ion s.  So m e  oth er  well   known  c om bi nato rial   pro blem s   includes  fin ding  s hortest   r ound  tr ips  (TSP),  s ol ving  pro posit ion al   f or m ulae  (S A T),   plan ni ng   a nd   sche du li ng,  ti m e - ta bling ,  r es ource all ocati on, p red ic ti on  of pro te in  str uctu res,  etc .     2. 2 .     Search  p aradigms   In   ge ne ral  almost  al l  co m pu ta ti on al   appr oa ch es  us e d  to  de al   with  hard  com bin at or ia l  pro blem s   can   be  re pr ese nted   as  search  al gorithm s.  T he  work i ng   pri nci ple  em plo ye d  in  case  of   t he  search  a ppr oac h  is  to  gen e rate  a nd  evaluate  ca nd i dat e  so l utio ns  in  it erati ve  way.  On   one  hand,  w he n  c om bin at or ia l  de ci si on  pro blem s  app r oach  is  us e d,   the  process  of   eval uating  a  cand i date  s olut ion   is  relat ed   with   the  proc ess  of   decisi on  w hether   it   represe nts  an  act ual  so luti on.  O n  t he  oth e r  ha nd ,  wh e n  deali ng  with  opti m i zat ion  pro blem s,  it  g ener al ly  im plies  d et erm ining  t he   res pecti ve va lue of t he obje ct ive fun ct io n .   a.   So l ution  met hods   for   co m bina torial  pro blem s - t he re  ha s  bee n  a g reat  inte re st  and   m any  ef forts  ha ve  been  m ade  to  the  de sign   of   c om bin at or ia l  (optim i zat ion )  pro blem s,  and   a  nu m ber   al go rithm   f or   s olv i ng   the s e   kinds  o f  ha rd   and  com plex  pro blem s  hav e  bee n  de sig ne d.   In   ge ner al ,   these  al gorith m s  are  t y p i c a l l y   c a t e g o r i z e d   a s   e i t h e r   e x a c t   o r   a p p r o x i m a t e   a l g o r i t h m s .   T h e   f i r s t   c l a s s   i s   k n o w n   a s   e x a c t   a l g o r i t h m s   a n d   c o m p r i s e s   a l g o r i t h m s   t h a t   g u a r a n t e e   t o   s o l v e   e v e r y   f i n i t e   s i z e   i n s t a n c e   o f   a   com bin at ori al   op ti m iz at ion  pro blem .  Wh il e  the  oth e r  cl a ss  com pr is es  a lgorit hm s  wh ic h  m ake  a  tra de - off   bet ween  t he  guara ntee  of  fin ding  op ti m a l solutio ns  a nd  getti ng   good  s olu ti ons i n po l ynom ia l - tim e [3 5].   b.   Con str uctiv e  al go rit hms - ge ne rate  init ia l  so lu ti on s  from   scratch  an d  la te r   s olu ti on  c om po nen ts   are  a d d e d   t o   t h e   i n i t i a l   s o l u t i o n s   a c c o r d i n g   t o   s o m e   r u l e s   u n t i l   a   s o l u t i o n   i s   c o m p l e t e .   T h i s   t y p e   o f   al go rit hm s  i s   consi der e d  to  be  the f ast est  appr oxim a te   m e t hods , h ow e ve r  the so luti ons  pro vid e d  by the m  q uite of te n  i s  with lo we r qu a li ty  co m par ed wit h on e  pr ov i ded b y l ocal se a rch al gorithm s.    c.   Lo c al  Sea rc h - the  w orkin g  pr i nciple  of   local   search  al gorithm s  is  as  fo ll ow in g,   they   sta rt  by  gen erati ng   an  init ia l  so luti on   an d  the n  iterate  fr om   current  so l ution   t o  oth e r  can dida te   so luti on   in   a  neighborho od  sp ace  of the c a nd i date s olu ti o ns , by  rep la ci ng actual   so l utio n by bette r  one  foun d  [ 35] .   d.   Pert urba ti ve  ( local)   searc h - wh e n  deali ng  with  c om bin at or ia l  prob le m s  can did at e  s ol utions  c on sist   of  so luti on  c om po ne nts  a nd  ty pi cal   case  is  with  assi gn i ng  tru th  val ues  t o  in div id ual  pro posit ion al   v a riabl es   wh e n  deali ng  with  S AT  pro blem s.  On   the   oth e r  hand,  c and i date  s olu ti on s   can   easi ly   be  c ha ng e d  in to   new   ca ndidate   so luti ons  by  app ly in g  one  or   m or e  m od ific at ion   on   res pecti ve  s olu ti on  com ponen ts .    This  proce ss  of  cha ng i ng   is  known  as  t he  per t urbin g  of  a  giv e n  can dida te   so luti on.  A ccordin g  to  [1]   search  al gorith m s   wh ic h  a re  base d  on  this  m echan ism   (te chn i qu e )  in  order   to  ge ner at e  the  can did at e  so luti ons a re c al le d  pe rtu rb at i ve  sea rch m et ho ds.   e.   Con str uctiv e  ( local)   search - t he  ge ner at i on   of   the  ca ndida te   so luti ons  in   com bin at or ia l  prob le m s  are  m ade  by  re pea te dly  exten ding  par ti al   s olu ti on s   that  c an   be   de fine d  as   a   searc h  pro ble m   and   the  m ai n  Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Sto c hasti c local  sea rc h: A st ate - of - t he - ar t rev ie w   ( Muham et   Kastrati )   719   obj ect ive   he re   is  to   get  a   ‘ good’   can did a te   so luti on,   w her e   use d  f or  opti m iz at ion   pro blem s,  and    the  “goo dn e ss ”  cor relat e  to  the  obj ect ive  f un ct io n.   Algor it h m s  based   on  this  m echan is m   are  cal le d   const ru ct ive  se arch m et ho ds   ( al so   known  as  const ru ct ive   he ur ist ic  m et ho ds).     2.3 .     St oc hastic  l oc al se arch   The  wor king  pr i nciple  in  t r aditi on al   local   searc h  al gorit hm s  wh en   ap pl ie d  to  s olv e  c om bin at or ia l  pro blem   is  cha racteri zed  wit h  fact  that  search  for  so l utio ns  happen   in  the   sp ace  siz e  of   cand i date  so lut ion s .     In   a ddit ion ,   th e  local   searc h  procee ds   by  first  ta king  a n  ge ner at ed   init ia l  cand idate   s olu ti on,  a nd  then   is   it erated  f ro m   on e   can dida te   so l ution  to  a no t her  can did a te   so luti on  wi thin  pr e def i ne d  neig hborh oo d,   a nd     the  decisi on  on  each  ste p  is   ta ken   base d  on l y  on  e xisti ng   l ocal  inf orm at ion   [1 ] .  H ow e ve r,   local   search   ty pical ly   is  char act erized   wit h  tw o  ki nd  of  pro blem s  su ch   as:   (i )  getti ng  stuck   in   local   op ti m a  and   (ii)   bei ng  m isgu ide d by e valuati on  (ob j e ct ive)  f unct io n.       3.   SLS M ET HO DS   In   t his  pa rt,   a re  s hortly   pr e sented  so m e  of   t he  m os t  prom inent  SLS   m e tho ds,  inc lud in g  t hei r   app li cat io n  to  s olv e  ha rd com bin at ori al  pr oblem s.      3.1 .    Simpl e SLS  m eth od s     I n  orde r  to  en su re  t he  searc h   process   to  esc ape  f ro m   a  local   op ti m a   ( m ini m u m ),   a  nu m ber   of   S LS   m et ho ds   acce pt   wo rse ning  m ov e s.  This  part   is  dev oted  t o  these  m et ho ds  wh ic h  are  know n  as  sim pl e  SLS   m et ho ds,  as t he se m et ho ds   e m plo y on ly  on e ty pe  of sea rc h  te ch niques , o n  li m it ed  neig hbor hood sets  [ 34 ] .   a.   Ra ndomize d  it erativ e  im pr ov emen t  ( R II ) - is  sim ply  based   on  it erati ve   i m pr ovem ent  exten de d  with  rand om iz a ti on .  Mor e  pr eci sel y, in each  ste p i te rati on  is p e rfor m ed  base d o n  pr ob a bili ty   , t he  sel ect ion   of  ne xt  sea rc hi ng   posit ion  ′   is  do ne  us in g  un i form l y  at   r andom   within  current   nei ghbor hood  ( ) ,  known   as   uni nfor m ed  rand om   walk  ste p,  or  in   oth er   ci r cum sta nces  1 −   i s  use d  to   perf or m   an  i m pr ovem ent  ste p.   He re,  t he    is  cal le d  as  w al k  pro ba bili ty  or   so m et i m es   it   is  al so   known  a s  noise   par am et er.  O ne  of the  m ai n  adv a ntage s  of  R II  is  that  they  a re easy to  b e  im ple m ented  [ 1] .   The  s uccess fu l   ap plica ti on   of  RII  al gorithm s  ha ve  be en  pro ve n  in  se ve r al   op ti m iz a ti on s  a nd  decisi ons  pro bl e m s.  As  pr es e nted  by  [34]  in  the  1990s  ar e  i m ple m ented  so m e  ver sion   of   RI I  by  us in g  m ino r  va riat ion s,  in  s uch   cas es  the  rando m   it erati on   is  defi ned   with  r ega rd   to  the  am ou nt  of   co ns trai nt   vio la ti ons  in   pl ace  of  c hoos in g  un if orm l y  at   rand om ,  chang es  those   that  e nab le   R II  al gor it h m s  to  be   on e  of the c urre nt s ta te - of - the - art  al gorithm s u sed  to  s olv e  SA T  problem s an d C SP s [3 4].   b.   Probabil ist ic   i te ra ti ve  impro vement  ( PI I) - un li ke  so m e  oth er  m et ho ds   t hat  acce pts  s om e  wo rse ning   search  ste ps ,  he re  this  m et ho d  is  base d  on   t he  idea  of   us in g  so m e  acce ptance  crit eria  w hich  is  based   on   pro bab il ist ic   evaluati on  f unct ion .  In   c ontras t  t o  RII,   eac h  ste p  of  PII  re quires  tw o  ste ps:   the  first  ste p  deals  with  sel e ct ion   of  nei ghbori ng  can did at e  so l ution  ′   in  c urren t  nei ghbo rho od  ( ) ,  w hich  t ypic al ly  is  done  by  usi ng  un if orm l y  at   rand om   app r oa ch;  the  sec ond  ste p  is  use d  t o  determ ine  wh e ther  to   acce pt   or   no t  ′   as  the  new   ca nd i dat e  so luti on.  I n  add it io n,   f or  c la ss  of   prob le m s   wh ere  m ini m iz ation   is   require d,  t he M et ro poli s c onditi on s  i s used   as accepta nce  pro bab il it y [34 ] .      ( ; ; ′ ) : = ( 1 if ( ′ ) < ( )  ( ( ′ ) − ( ) ) ot h er wi se ,       wh e re   ( ; ; ′ )   repres ents  pr ob a bili ty   of   acce ptanc e  an d    denote s  the  e valuati on  f unct ion  w hi ch   sh oul d  be   re duced.   T he  para m et er    nam ed  as     re pr ese nts   the  im pact  of  t he   pr ob a bili ty   w hethe r   to  acce pt  or  not  w orseni ng   search   ste ps   a nd  is  eq uiv al e nt  to  c onsta nt - te m per at ur e  de fine d  to  sim ulat ed  ann eal in g.  It  i s  worth   m entio ni ng  t hat  for  value   of  = 0 ,  the n,  P II  will   ef fe ct ively   tur ns  into   a n  it erati ve   i m pr ovem en t pr oce dure,  and  f or v al ue of T= ∞, th e n  acc ompli sh es  unif orm  r and om  w al k [34].   c.   Simulated  anne aling   ( SA ) - is  si m ple  SLS  m et hod,   wh ic h  s h ares  sim il ar  featur es  with  P II ,  a par t  f r om  tem per at ur e  pa ram et er    that  is  m od ifie d  at   r un   ti m e.  This  m et ho d  is  ins pi red   by  natu ral  ph e nom eno n  analo gy,  res pe ct ively   the  slow   co oling   of   s olid  m a te rial s.  The  par am et e r  T  (te m per at ure)  init ia ll y  ha s  the  hi gh  val ue ,  w hich   the n  i s  pro gressi vel y  decr ease d  unti l  the  lo west   tem per at ure  va lue  is  reac he d.   High  te m per at ur e v al ue s  m ea ns   that pro ba bili ty   of   acce ptin g  worse ning  ca nd i date  so l utio ns  w il l  be  h i g h .   T h u s ,   a s   t e m p e r a t u r e   d e c r e a s e s ,   t h e   p r o b a b i l i t y   o f   a c c e p t i n g   w o r s e n i n g   c a n d i d a t e   s o l u t i o n s   dec reases  as   well ,  wh ic h  m eans  that  searc h  proces s  pro gressi vely   be gin s  to  be  gr ee dy .  Fu rt her m or e ,  for  ve ry  low  tem per at ur es   ( sm a ll   values  of  T ),   al m os t  on ly   nei ghbors   that  ha ve  bett er  or  at   le ast   equ al   val ue  of  Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    71 5   -   72 7   720   evaluati on  t o   t he  c urre nt  can did at e  s olu ti on   can   be   acce pt ed  [34].  SA  ha s  bee n  su cces s fu ll y  an d  wide ly   u s e d   t o   s o l v e   h a r d   c o m p u t a t i o n a l   p r o b l e m s ,   b y   i n v o l v i n g   v a r i o u s   f o r m s   o f   a n n e a l i n g   a n d   a c c e p t a n c e   t e s t s .   d.   Tabu  sea rch  ( t s) - is  ano ther   si m ple  SLS  m eth od,   w hich  is   c har a ct erize d  by   exp li ci t  m e mo ry  dep e nde ncy   durin g  the  sea rch   process  [36].  In   it s  sim ple  fo rm ,  known  as  sim ple  tab u  sea rc h,   it   pe rfor m s  it erativ e  i m pr ovem ent  fr om   one  po te nt ia l  so luti on    t o  a n  im pr ov e d  so l utio n  ′   in   the  neig hbor hood  of    unti l   so m e  stop pi ng   crit erion  has   be en  sat isfie d.  I n  or der   t o  av oi d  getti ng  st uck  on  local   opti m a  an d  to  e nsur e   that  al l  reg ions  in  their  nei ghbo rho od   hav e   been   e xp l or e d,  so m e  kin d  of   sh ort - te rm   m e m or y  has  been  us e d.   I n  order   to  sk ip  m e m or iz ing   w ho le   se t  of   cand i date  so luti ons  an d  e xp li ci tl y  fo rb i dden  these ,  he r e  is  assigne d  a  ta bu   sta tus  t o  each  com ponen t   and   is  kee pt  track  of  each  s olu ti on   c om po ne nt  wh e n  it   wa s   la st  m od ifie d.   TS  al gorithm s  even   sim ple  on e  has  pr ov e d  to  perform   qu it e  go od  in  sev eral  nu m be r  of   pro blem s.  Ho wev e r,   it s  pe rfor m ance  is  str ongly  relat ed  on   t he  ta bu  te nure  set ti ngs.  I n  or der   to  esca pe   the  prob le m   of  fi nd i ng  fi xe d  set ti ng s ,  wh ic h  a re  s uitable   for  a   gi ven  s pe ci fic  pro blem ,  reacti ve   ta bu  search  m echani s m  h as b ee n  i ntr oduce d  in  or der  to m od ify  t he  ta bu te nure  set ti ng s at  run - tim e [3 4].   e.   Dyna mic  local   s earch   ( DLS) - in  the  previ ous  sect ion   we   hav e  prese nted  seve ral  te chn iq ues  us e d  f or  escapin g  f ro m   local   op ti m a   by  us ing   m ini m al ly   wo rsen i ng  ste ps   in  local   search .  U nlike   oth er  ‘sim ple’  SLS  m e tho ds p resen te d  ab ov e , D LS [1] do es n’ t pe rm i t wo r senin g  searc h  s te ps , but in  cont rast it  u pd at es     the ev al uatio n functi on  durin g  the  local sea r ch  in  or der  t o  a vo i d gett ing st uck on l ocal  optim a [3 4].     Accor ding  t o  [ 34 ]   t he  update d  e valuati on   f unct ion  ′   is  cal cu la te d  as  t he  sum   ′ ( )   an d   ( ) ,  that i s :     ′ ( ) : = ( ) + ∑ ∈  ( )  ( )   (1)     ′ ( )   represe nts  th e  or i gin al   eva luati on   functi on  val ue,     ( )   de note s  pe nalti es  for  eve ry  so l ut ion  com po ne nt  ,   ( )   represe nts  a  s et   of  s olu ti on   com ponen ts   of  .  At  t he  be ginnin g,  al l  pe nalti es  ha ve    the  va lue  e qua l  to  zer o.  Depend i ng  on  the  pen al ty   updating  m echan ism   an d  c hoic e  of   so l ution  com pone nts   that  are  us e d  t o  a dju st  t he  pe nalti es,  the re  e xist  dif fere nt  va ria nts  of  D LS .  I n  t he  beg i nn i ng,  ( )   is  cal culat ed  for  e a c h     a c c o r d i n g   t o   e q u a t i o n :   ( ) : =  ( ) / ( 1 +  ( ) )   w h e r e    ( )   i s   u s e d   t o   m e a s u r e   t h e   e f f e c t   o f     o n   t h e   e v a l u a t i o n   f u n c t i o n   a n d   t h e n   p e n a l t i e s   a r e   i n c r e a s e d   f o r   s o l u t i o n   c o m p o n e n t s   t h a t   h a v e   m a x i m a l   u t i l i t y   [ 3 4 ] .     3.2 .     Hy brid  SLS   meth od s   Ther e  e xist  sev eral  m or e  com plex  SLS  m et ho ds   known  as  hybri d  m et ho ds,  wh ic h   integ r at e  diff ere nt   ty pes  of  sea rc h t echn iq ues (ex .,  co ns tr uctio n sea rch   with  pert urbati ve  local   search )  or in vo lv ing   oth e r  ty pe s o f  com plex  m od i ficat ion s  of   c urre nt  can did at e   so luti ons,  i n  orde r  to  gen e rat e  eff ect ive  i niti al   sta rting   poi nt  f or   fo ll owin g  it era ti ve  im pr ov em ent  sea rch  [ 34] .  The   f ollow i ng  sect io n  pr e sents  a   sho rt  over view   of  t he   m os t   prom inent h yb rid  m et ho d s.   a.   G r e e d y   r a n d o m i z e d   a d a p t i v e   s e a r c h   p r o c e d u r e s   ( G R A S P ) - t h e   w o r k i n g   p r i n c i p l e   u s e d   b y   G R A S P   [ 3 7 ]   i s   i n t e g r a t i o n   o f   r a n d o m i z e d   g r e e d y   c o n s t r u c t i v e   s e a r c h   w i t h   a   s u c c e s s i v e   p e r t u r b a t i v e   l o c a l   sear ch  T he  process   o f   g e n e r a t i n g   i m p r o v e d   s o l u t i o n s   b y   c o n s t r u c t i o n   h e u r i s t i c s   ( g r e e d y   r a n d o m i z e d   p r o c e d u r e )   i s   co ntin ually  rep eat e d  unti l  a  te r m inati on   crit erion   is  m e t.  The  pr e senc e  of   the  w ord  adapti ve   sp eci fied  in  GR ASP   nam e, is to  denote that hy br i d sea rch p ro ce du re invo l ves  a n adaptive  constr uction he ur ist i c. In  t h e   s i m i l a r   w a y ,   t h e   t e r m   r a n d o m i z e d   d e n o t e s   t h a t   r a n d o m i z a t i o n   i s   u s e d ,   a n d   i t   i s   r e a l i z e d  b y   u s i n g   t h e   s o - c a l l e d   r e s t r i c t e d   c a n d i d a t e   l i s t   t h a t   k e e p s   t h e   b e s t - s c o r i n g   c o m p o n e n t s   d e p e n d i n g   o n   a   h e u r i s t i c s   f u n c t i o n   [ 3 4 ] .   b.   Iterated   gr eed y  ( IG ) - is  an othe r  al g ori thm   that  belo ng  to   hybr i d  S LS  m et ho ds.  The   w orki ng  pr inci ple  of   IG   is  that  it   i te rati vely   per f or m s  gr eedy  c on st ru ct io n  he ur ist ic s  in  ord er  to  pro du ce   a  sequ e nce  of   cand i date  so lu ti on s  that  ha ve   hig h - qu al it y.  In   this  al gorithm ,  the  key  pr inciple   is  to  sw it ch  betwe e n  so luti on  c onstr uction  an d  des tructi on  ph as es ,  w hile  this  e nsures   bette r  pe rfor m ance  th rough  i nteg rati on  of tw o  ty pes o f  searc h  te ch ni ques  dif fer e nt to  each othe r [34 ] .   The  basic  pr i nc iple  ap plied  t o  I G  al gorithm ,  was   re disco ve red  a  nu m ber   of   t im es  and   pr esented   with  diff e re nt  nam es,  su ch   as :  ru in - a nd  rec r eat e,  it erati ve  f la tt ening   a nd  it erati ve  c on st ruct ion   heurist ic .    IG   al gorithm s  hav e   bee n  s ucc essfu ll y  use d  f or   so l ving  a  num ber   of   pro blem s  and   obta ine d  re su lt s  s how   that,  especial ly   wh e n  inte gr at ed  with  per t urbati ve  local   search ,  they   a chieve d  im pr essive  res ults  on   m any o ptim iz a ti on   pro blem s [ 38, 39].   c.   Iterated   loc al  searc h  ( ILS) - is  an oth er   suc ce ssfu l  hybri d  S LS  m et ho d,   w hich  is  m ai nly  known   as  hybri d   betwee n  pe rtu r bation  m echani s m   and   local   se arch   al gorith m .   As  pr ese nt ed  in  [ 34 ]   an  ILS  al gorithm   com pr ise s  by  four   basic  ty pes  of   m echan ism s :  (i)  m echan ism   us ed  to  gen e rate  an  init ia l  so luti ons     (ex.,  co ns tr uction  he ur ist ic s),   (ii)  a  subsidiar y  (p ert urbati ve )  local   searc h  proce dure,  (iii )   a  per tu rb at i on   proce dure  that   perform s  m o dificat ion   t o  c and i date  so l ution   a nd   (iv )  an  acce pta nce   crit erion.  IL S  al gorithm s,  esp eci al ly   it s  basic  ve rsion,  is   ch aracte rized   as fa st  an d  easi ly   im ple m ented.   F ur t her m or e, b y  app ly in g  s om e   ty pes  of  m od ific at ion ,   IL S  r epr e se nts  sta te - of - t he - a rt  m eth od  us e d  t o  s ol ve  a  wide   ra nge   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Sto c hasti c local  sea rc h: A st ate - of - t he - ar t rev ie w   ( Muham et   Kastrati )   721   of   c om bin at or i al   prob le m s  [34].  D uri ng  the   la st  ye ars  sev eral  ve rsions  of  IL S  hav e  be en  re disc ov e re d  and  f ound  unde r  di ff e ren t  na m es,  li ke  la rge - ste p  Ma rko v  chains   [ 40 ]   a nd  chai ned   l oc al   op ti m iz a ti on   [41],  but  al so   there  e xist  so m e  con ce ptu al   c onnecti on  of  the  un der ly ing   al gorithm s  wit h  dif fer e nt  ty pe s   of   var ia ble  nei ghbor hood  sea rch,  f ur th erm or e  V NS   a nd   S VNS  m et ho ds   are  co ns ide re d  as  ver si ons  of   ILS, w hich  b e ne fit by  us in g  th e ad van ta ges o f pertu r bat ion  at  r un ti m e [3 4] .     3.3 .     Pop ul at i on - b ase d S LS  met h od s   These  m et ho ds   are  c onside r ed  m or e   c om plex   com par e  t o  oth e r  SL S  m et ho ds ,  beca us e  t hey  are   est ablished   ba s ed  on princi ple of  us in g  a  set   or po pu la ti on  of ca nd i date so l utions.    a.   Ant  c olony  opti miza ti on  ( ACO) - is  par t  of  popula ti on - bas ed  S LS  m et hods   t hat  has   be en  widely   a nd  su ccess fu ll y  e m plo ye d  to  s olv e  m any  com plex  com bin at or ia l  prob le m s  [42 - 44] .  T his  al gorithm   reli es  on  bio lo gical   phe no m ena  (a nts),  an d  he re  te r m   arti fici al   a nts  re pr ese nts   m ulti - agen t  m e tho ds   whos e   insp irat io n  c om es  fr om   collecti ve  beh a viors  of  real  ant  colo nies.  Ty pi cal ly ,  co m m un ic at ion   base d  on  ph e r om on es  of   the  bi ologica l  ant  is  the  par a dig m   us ed.  Co m bin at ion   of  a rtific ia l  ants  w it h  local   searc h  al gorithm s  ha ve  bee n  su cce ssfu ll y  us e d  i n  seve ral  op ti m iz at ion   ta sk s.  Fu rt her   de ta il s  abo ut  thes e  m oth od s ca n b e f ound in  [29,  44 ] .   b.   Evolutio nary  al go rit hms   ( EAs) - is   on e  of  the  m os t  widely  us ed  an d  su c cesfu ll   popula ti on - base d  S L S   m et ho d  us e d  f or  so l ving  c om plex  com pu ta ti on al   prob le m s  in  recent  y e ars.  EA s  have  bee n  ge ner al ly   insp ire d  f ro m   bio lo gical   evaluati on  w hi ch  cha racteri z ed  by  three  m os t  well - known  ev olu ti on   m echan ism   su ch  as   m utati on ,  rec om bin at ion  an d  sel ect io n.   Anothe r  si gn i ficant  m echan ism   is  evaluati on   functi on, which  is k now n  as fi tness .  T hese  a lgorit hm s  are  al so   c har act eriz ed  with r an do m iz at ion   proce ss   wh ic h  is  use d  to  ge ner at e  t he   init ia l  set   of   c and i date  so l ution s ,  a nd   t hen   gr ee dy  co ns tr uc ti on   heurist ic s  that  is  m a inly   e m plo ye d  to  s eed  the  popula ti on .  Lat er ,  this  under ly in g  popula ti on   is  subj ect   of  th ree   m os t  well   known  ge netic - base d  m echani s m   known   a s  m utati on ,  r ecom bin at ion  an d  s el ect ion .     In   ge ner al ,  E A s  perform ance  is  strongly  rela te d  with  the  ri gh t  us e  of   the  evo l ution a ry  m echan ism ,  due   to  this  fact,  to o  m uch   resear ch  w ork  has  be e n  do ne  with  reg a rd   t o  desi gn  an d  ef fecti ve   us e  of  m utati on  and  rec om bin at ion   m echan is m   [3 4].   EAs   ha ve  been  exte ns sively   us ed   to  s olv e  dif fer e nt  ki nd s   of  rea l  world  prob le m s  and   re su lt s  ob ta ine d  s how   that  EAs  achi eved   sta te - of - t he - a rt  resu lt   w hen   a pp li e d  to   so lve  c o m b i n a t o r i a l   r e l a t e d   p r o b l e m s   i n c l u d i n g   f i n d i n g   s h o r t   a n d   i m p l e m e n t a t i o n - f r i e n d l y   a d d i t i o n   c h a i n s   [ 4 5 ]   a n d   f i n d i n g   n a s h   e q u i l i b r i u m   i n   e l e c t r i c i t y   m a r k e t s   [ 4 6 ,   4 7 ] .       4.   STATE - OF - T HE - A RT I N S LS   In   this  sect io n ,   we  hav e  br ie fl y  pr esente d  a   sta te - of - the - art  rev ie w  in  SLS  m et ho ds   a nd   it s  su ccessf ul   app li cat io n  in  s ci ence a nd eng ineerin g .     4.1.   Int e gratio n   of sy s tem at ic  se arch  and SLS   SLS  a nd   syst em at ic  search  usuall y hav e  b e en  co ns i der e d as t wo   sepa rate  ap pr oach e s appli ed  to s ol ve   com plex  com bin at or ia l  opti m iz at ion   an d  de ci sion   pro blem s.  D ue  to  t heir   sp eci fic  c har a ct erist ic s  fo r   a  wh il e  these  ap proac hes  ha ve  been  con si der e d  m or e  c on c urre nt   then  c om ple m entary.  H owever,  duri ng   t he  la st   decad e  ha s   be en  ide ntifie d   an   inc reased  at te ntion   to  th e  e xp l or i ng,  de sign   a nd   de ve lop m ent  of   hy br i d  m et ho ds,  w hic h  in vo l ve  inte gr at io n  of  sys tem at ic  search   and   S LS  a ppr oac hes  with   purpose  e nha ncin g     the  al go rit hm s .  These  hybri d  m e tho ds   ca n  be  cl assifi ed  in  two  m ajo r  cl asses  de pe nd i ng   on   the   ro le   of  com bin ed  te ch ni ques  a nd  th e  ro le   t hey  pl ay .  Acc ordin g  to  this  cat e gorizat io n  the   f irst  cl ass  com pr ise s   appr oach es  where  the  syst e m at ic   search  te chn i qu e s  ser ves   as  m ast er  pr oc ess  wh il e  othe r  proce dure  ( SLS)   is   eng a ge d  to  ta c kle  any  issue  t hat  can  a rise  thr ough ou t  the  syst e m atic  search  ste ps .  In   t he   seco nd   cl ass ,   these  ro le s  hav e   bee n  cha nged ,  here  SLS  al go rith m   serv es  as  t he   m ast er  proces s,  w hile  syst em at ic   search  te chn i qu e   is use d wh e n d eal ing   with s pe ci fic ta sk s t hat  arise d uri ng ru nn i ng tim e o f SLS al gorithm   [34].     4.2 .     SLS a l gori thm  en gineeri ng   The  def i niti on  of   ge ner al - pu rpose  S LS  m et hods   is  no t  s i m ple  as  that  of   fu ll y  de fin ed  reci pes:   m eaning   that   there  are  s om e  op en  c ho ic es  durin g  the  al gorithm s  desig n,   f urt he rm or e  on ly   pro per   com bin at ion s  of   t hese  ch oice s  can  he lp  on   desig ning  of   e f fecti ve  al gorit hm s,  wh ic h  ca n  be  us e d  f or   s olv in g  sp eci fic  dom ain   pro blem s.  As  sug gested   by   [ 34 ]   m or e  a nd  m or e  m et ho do l og ic al   rese arch  is  need ed   to  be   unde rtake n  to wards  a n  im pr ov e d  desi gn  a nd  im pl e m enta ti on   of  SL S  al gorithm s.   Alth ough  S LS  al gorithm s   eng i neer i ng   fol low s   the  m ot ivati on   of   al gorithm s  eng in eerin g;  they   are  m a inly   us ed  to  so l ve  N P - ha r d  pro blem s  that  are  c harac te rized  with  c omplex  a nd  unpr edict able  beh a vior,  a ddit ion a ll y,  the  prese nc e  of   stochastic it y m akes a naly sis   of these  alg or it hm s  m or e h ar d and com plex.     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    71 5   -   72 7   722   4.3 .     Au t om at ic  configu ra tion o f  SLS  algorith ms   As  m any  oth e r   al gorithm s,  th e  pe rfor m ance  of  SLS   al gorit hm s  is  strongl y  relat ed  t o  th e  num ber   of   desig n  c ho ic es   and   par am et er  set ti ng s .  Fin ding  ri gh t  de sign   a nd  co nf i gurati on  of   SL S  al gorithm s  i nvolv e s   set ti ng   a  la rg e   num ber   of  ca te gorical ,  or din al   a nd  num erical   par am et ers.   T he  m ai n  goal   in   desi gning  of   autom at ic   con fig ur at io n  of   SLS  al go rithm s  is  to  fi nd  th e  pro per   set ti ng s   of   t hese  pa ram et ers  in  order   t o  achieve   t he  op tim a l  perform a nce  [34].  Acc ordi ng  to  [17]  t he  a uto m at ic   c onfig ur at io n  of   SLS   al gorith m s  i s     a  powerf ul  an d  wi dely   us ed  appr oach   t hat  has  sig nifica nt  ro le   in  th e   de sign   a nd   de vel op m ent  of   al gorithm s  that p rovide  b e tt er   perf or m ance   in  pro blem  s olv in g .   As  w e  m entioned   a bove   the   perform ance  of   SLS  al gorithm s  us ually   de pends  on   the   nu m ber   of  desig n  ch oices   and   pa ram et e r  tun in g.   I n  doin g  so ,   m any  research e r s  ha ve  bee n  for  a  wh il e  unhapp y  with  m anu al   al gorithm   con fig ur at ion ,  a nd  in  a   nu m ber   of  fi el ds   they   ha ve   introd uced   t heir  a ppro ac he s  for   autom at ic   par a m et er  tun in g.   A ppro ac hes   for  set ti ng  pa ram et ers  hav e   bee n  pr ese nt ed  a nd  desc ri bed  by     a  nu m ber   of  a uthors,  but  we   will   descr i be  so m e   of   the   m os t  prom inent  on e s  that  hav e   bee n  pu blishe d   their  researc h  w ork   in   the   la st  deca de .  H utter  et   al . ,   [8 ]   i n  thei r  st ud y   present ed   m et ho ds  that  s et   pro per  pa ra m et ers  autom at ic ally  i n  order  to   en ha nce  t he  perform ance  on  a  gi ven   cl ass  of  pro blem   instances .  T wo  ye ars   la te r,  ano t her   e xtensi ve  resear ch  wa s  condu ct e d  by   Hoos  [9 ]   on  autom at ed  al go r it h m s  con fig ur at ion   an d  par a m et er  tun in g.   In   thi s  stud y,  they   pr ese nted   a n  exten de d   int rod uction  to  t he  sig nificant   ro le   that  aut om at e d   al gorithm s  config ur at io n  a nd   par am et er  tun i ng   te c hn i ques  play   in  the  im ple m entat ion   of  al gorithm s  that   hav e   bette r  perf or m ance.  T his   study   al so   giv es  a  br ie f  s urvey  on   the  area  of   al gorithm   con fig urat ion   a nd   par a m et er  tun in g  te c hniq ues.   A n o t h e r   s t u d y   o n   a u t o m a t i c   d e s i g n   o f   h y b r i d   S L S   a l g o r i t h m s   h a s   b e e n   i n t r o d u c e d   b y   M a r m i o n   e t   a l . ,   [ 1 0 ]   w h o   p r o p o s e d   a   p r a c t i c a l ,   u n i f i e d   s t r u c t u r e   t h a t   i n t e g r a t e s   s e v e r a l   S L S   m e t h o d s .   T h i s   a p p r o a c h   i s   u n i f i e d   du e  t o    the  fact  that  inv ol ves  these  m et aheurist ic s  into  a  sing le   str uc ture  w hich  ca n  be  se par at el y  instanti at ed  an d  ca n  be  us e d  t o  ge ner at e  c om plex  c om bin at ions  an d  va riants   as  well .   Aro und  t he  sam e  tim e,  gr am m ar - base d  gen e rati on  of   SLS  he ur ist i cs  thr ough  au tom a ti c  al go rithm   con fig ur a ti on   to ols  has   been   i ntrod uc e d  by     Ma sci a  et   al . ,   [11 ] .  A uthor s   pro pose d  he re   a  ne w  a ppro ac h   t hat  is  base d  on  us i ng  s om e  sequ e nce  of  cat eg ori cal ,  int eger,  a nd  real - value d  par am et ers   an d  a uto m at ic   al go rithm   config ur at io n  i n  order  to  fin d  out    the   al g or it hm   that  perf or m s  bette r  f or   t he  sp eci fic  prob le m   at   han d.  T he re  is  an oth e r  stud y  c onduct ed  by  Ma sci a  et   al . ,   [ 13 ] ,  c oncer ning   to  th e  al gorit h m   co m par iso n  by  a uto m at icall y  con fig urab le   SLS  f ram ewo r ks ,   wh ic h  is  a  case  stud y  us i ng  flo w - s hop  sc he du li ng  pr ob le m   (F SP) .  Th e  ob ta ine d  res ult s  sh owe d  that   hybri d  al gorithm s that are i ns ta ntiat ed were  ab le  t o m at ch  and im pr ove  over t he b est  conv e ntio na l SL S m et ho d.   Anothe r  resea r ch  with  re gard   to   the  i m pact   of   aut om at ed   al go rithm   con fi gurati on   on  the  scal in g  beh a vior  of  sta te - of - the - art  in exact  TSP  so l ve rs  was  pre se nt ed  by  Mu  et   al . ,   [17].  He   inve sti gate d  the  ef fects   of   aut om at ic   alg ori thm   con fig ur at io n  in  re ga rd   to  im pr ov i ng  the   perform a nce  of   the  tw o  well   known   in exact  so lve rs  for  t he   TSP,  E AX  an d  L KH.  By   u s ing   t his   new  way  of   a naly zi ng  the  em pirical   scal ing   of  r unning   tim e  as  a  fu nction  of   pro blem   instance  siz e,  dem on strat ed   t hat  autom at ed  config ur at io n  h as  im po rtant  eff ect   on  the  scal ing  beh a vior  of E AX.   Wor k  on  a utom at ed  al gorith m   con fig ur at io n  a nd  par am eter   tu ning   te ch ni qu es   ha s  been   al so   done   by   Fr a nzin  a nd   S tützl e   [16]  w ho   ha ve  eval ua te d  seve ral  a ccepta nce  c rite ria  base d  on   exp e rim ental  work.    They  fi rst  m ade  tun in g  of  nu m erical   par am et ers  of   t he  al gorithm s  us ing  autom at ic  al go rithm   con fi gurati on  appr oach   f or   qu a drat ic   assignm ent  pro blem   and   a  per m utati on   flo ws hop  pro blem .   Fr anzi n  et   al . ,   i n  [ 15]   pr ese nt ed   the   eff ect   of   tra ns f or m at ion s  of   num erical   par am et ers  in  autom atic  alg ori thm   con figurati on.     The  a uthors  he re  stu died  t he   i m pact  of   al te rin g  the  sam pling   sp ace  of   par am et ers  in   autom at ed  al gorith m   c o n f i g u r a t i o n s .  F r a n z i n   a n d   S t ü t z l e   [ 1 4 ]   d e s c r i b e d  S A   a s   a n   e n s e m b l e  o f   a l g o r i t h m i c   c o m p o n e n t s   a n d  d e s c r i b e  S A   v a r i a n t s   f r o m   t h e   l i t e r a t u r e   w i t h i n   t h e s e   c o m p o n e n t s .   T h e y   h a v e   a l s o   e x p e r i m e n t a l l y   dem on strat ed  the  pote ntial   of   this  ne w  appr oach   on   three  well - known  com bin at or ia l  optim iz a ti on   pro blem s ,  su ch  as  qu adr at i c   assignm ent  prob le m   and   two  var ia nts  of   t he  per m utati on   flo w  shop   pro blem .   Pagn oz zi   and   Stützl e   [1 2]   pr ese nt ed   a n  autom at ic  design   of   hy br i d  SLS  al gorith m s   fo r  pe rm ut at ion   flo wsho p  pro blem s  ( PFSP).     Her e ,  they   a uto m atical ly   gen erate d  a  ne w  sta te - of - the - art   al gorithm   fo r   so m e  of   the  m os t  widel y  stud i ed   var ia nts of t he PFSP .     4.4 .     Ap pli ca tio n  of SLS  algorith ms   T his  par t  giv e s  a  br ie f   over vi ew  of  s om e   su ccess fu l  a ppli cat ion s   of  SL S   al gorithm s  use d  to   s olv e   op ti m iz ation   and   sea rch   pro bl e m s.  W e  ha ve   cat ego rize d  th ese  exam ples  i n  two  m ajo r  gr oups :  ap plica ti on   of   SLS  al gorithm s  in  m achine  l earn i ng   a nd  da ta   m ining   an d ,   app li cat ion   of   SLS  al gorith m s   in  oth er  a r eas  of  sci ence a nd en gin ee rin g.         Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Sto c hasti c local  sea rc h: A st ate - of - t he - ar t rev ie w   ( Muham et   Kastrati )   723   4.4.1 .   SLS in  machine  learn ing   In  this secti on,  are p re sente d  s om e o f  the  m os t  recent trends  o n  ap plica ti on  of  SLS  in the a rea o f data   m ining ,  gra ph   m ining   an d  m a chine  le anin g.   Ho s sai n  et   al . ,   [48 ]   pr ese nted  the  app li cat io n  of   SLS   f or   pa tt ern   set   m ining .  He re  auth or s  pro po s ed  the  ap pl ic at ion   of   SL S   fo r  s olv in g  th e  patte rn   set   m ining,  pa rtic ularly ,  to  t h e   t a s k   o f   c o n c e p t   l e a r n i n g .   T h e y   a p p l i e d   h e r e   a   n u m b e r   S L S   a l g o r i t h m s   o n   a   c o n v e n t i o n a l   b e n c h m a r k   p r o b l e m   i n s t a n c e   f o r   p a t t e r n   s e t   m i n i n g   a n d   t h e   r e s u l t s   o b t a i n e d   s h o w e d   p r o m i s i n g   r e s u l t s   f o r   f u r t h e r   e x p l o r a t i o n .   Brunat o  a nd  Ba tt it i  [4 9]  inv e sti gated  SLS   f or   direct  trai ni ng   of  thr esh ol d  net wor ks .  In  this  stud y  auth or s  a ppli ed  SLS  al go rith m s   fo r  trai ni ng  ne ur al   ne tw orks  by  in volv ing   th res ho l d  act ivati on   f unc ti on s,  a  novel  te chn i que  known  as  bin ary  le arn i ng   m achine  (BL M).  BLM   wo r ks   base d  on  th e  pr inciple   of  changi ng   ind ivi du al   bits  of each  w ei gh t  and sele ct ing i m pr ov in g  m oves.    Brunat o  an d  Ba tt iti  in  [5 0]   pr ese nted  a  new   a lg or it hm  based   on  m ulti scal e  SLS  with  bin a ry  represe ntati on   for  trai ni ng  ne ur al   n et w orks.  In   t his  w ork  they   pro po s ed   a  te le scop ic   m ul ti scal e  ver sion  of   local  searc h,   w her e t he nu m ber  of  bits was  incr ease d  i n  a n adaptive  w ay ,  in  this  way le ad ing  t o  a  faster   s ear c h  process  a nd  to   local   m ini m a  of   bette r  qual it y.   Laachem i  and  Bo ughaci  [ 51 ]   pr ese nte d  an  inte resti ng  work   reg a rd i ng  W e b  ser vice  cl as sific at ion .  In  this  pa pe r,   a uth ors  c om bin ed   SLS  with  s uppo rt  vecto r  m achine   (S VM )  f or   We b  ser vices  cl assifi cat ion .  T hi s   m et ho d  was   perform ed   in  two  st e ps ,  fi rst  SLS  m e ta - he ur ist ic   was   us e d  for   featu re  sel ect ion ,   an d  la te r  S VM  al gori thm s  was   ap pl ie d  to  do  t he   cl assifi cat io n  ta s k.   Additi on al ly ,  t his  m et ho d,  w hich  ty pical ly   involve s  SL S  a nd  S VM  f or  Web   se rv ic e  cl as sific at ion   was  furth e r   validat ed  b y a ut hors on the  qu al it y of  w e b  se rv ic e  (QWS ) D at aset .    Nekkaa  a nd   B oughaci   in  [ 52]   pro po se d   a   hybr i d  sea rch  m et ho d  that  i nteg rates  ha rm on y  sea rc h  al gorithm s  (H SA )  with  SLS   fo r  feat ur e  sel ect ion   as  a  com bin at or ia l  optim iz at ion   pro bl em   in  cl assifi cat ion .  They  intr oduc e d   a  novel  sel ect ion   strat e gy   base d  on  pro bab il it y  te chn i qu e   em plo ye d  in  HAS - S LS ,   w hich  m anag es  to   se le ct   the  ap pro pr ia te   s olu t io ns  by  usi ng  SL S  to  filt er  out   irreleva nt  or  r edun dan t  featu res,   by   pro vid in g  a  go od   tra de - of f  be tween  e xp l or at ion   a nd   e xp l oitat i on .  F ur the r m or e,  the  hybri d  HAS - SLS  i s  then   integrate d wit h a  S VM   cl assif ie r.   Far hi  an d  Bo ughaci  i n  [5 3 ]   pro posed   us e   of   SLS  m et ho d  f or   s ol ving  the  f re qu e nt  s ubgr aph  m ining   (F S M)  pro blem .   They  intro duced  her e   the  no ti on  of  di versi ficat ion   that  com pr ise   on e  of   the  m os t  prom inent  appr oach es   a ppli ed  t o  s olv e  hard  optim iz ation   pro blem s.  The  im ple m entat ion   a nd  eva luati on  of  pro po s ed   m et ho ds   was  t est ed  on   se ver a l t ypes o f data   set s includ i ng  syntheti c an d  r eal - w or ld  one.  At the   sam e tim e this   m et ho d  was  c om par ed  to  oth er  sta te - of - the - art  m et ho ds  currently   us e d,   incl ud i ng   l ocal  searc h,   GA   a nd  var ia ble  nei ghbor hood  sea rc h  (VNS )  al go r it h m s.  This  m et hod  was  a bl e  to  e ff ic ie ntl y  disco ver  dive rsified  su bg raphs  in  t he  searc h  s pa ce  thr ou gh  ex plorin g  ne w  s olu ti ons  by  usi ng   ra ndom nes s  durin g  the  s earch   process .  The  obta ined  resu lt s  sh owe d  that  S LS  m e tho d  pro du ce  c om petit i ve  res ults  and   so luti ons  f ound  ha ve  bette r   qu al it y com par ed  t o  th ose  foun d by LS , GA  a nd  VNS  al gorithm s.   Ma farja  et   al . ,   [54 ]   pro po se d  bi nar y  va ria nts  f or   the  la t est   ver sio n  of  gr ass hoppe r  op ti m iz ation  al gorithm s  (G OA)  us e d  f or   featur e  sel ect i on.  More  pr eci sel y,  GOA  al gorithm s  is  app li ed  to  sel ect   op tim al  featur e   subset   by  rem ov in g  irreleva nt  fea tures,  w hich  l at te r  will   be  use d  for  cl assif ic at ion   pur pos es  into     the  wr a pper - ba sed  fram ewo rk .  A ut hors  he re  introd uced   tw o  m echan ism s   i n  orde r  to  desi gn   a  bi nar y  ve rsi on   of   GOA.   The  f irst  m echan is m ,   is  on e  w hic h  is  base d  on   bo t h  Sigm oid   and   V - sh a pe d  trans fer   functi on s ,  an d  al gorithm s  are  nam ed  as  BGO A - S  an d  B GOA - V,   res pe ct ively .  The  s econd  m echani s m   inv olv es  a  novel  te chn iq ue  t hat  integrates  t he   best  s olu ti on   obta ined  so   f ar.  Additi on al l y,  a  m utati on   operato r  is  use d  to   enh a nce   the  e xplo rati on  phas e  in  B GOA   al gorithm   and  is  nam ed  as  B G OA - M.  These   m et ho ds  are   ev al uate d  on  a  c onside ra bly  seve ral  be nch m ark   data  set s  an d  obta in ed  res ult  sho w ed  t hat  the   pe r form ance  achi eved  by   BGO A  an d  BGO A - M  is  superi or   w he n  c om par ed  to  pe rfor m ance  ob t ai ned   by  oth e r   si m i la r  recent ly   us ed  te chn iq ues  in  t he   li te ratu re.     4.5 .     Oth er  SLS  appl ic at io n   In   rece nt  ye ars ,  m or e  an d  m o re  effor ts  hav e   been   de vote d  to  the  ap plica tio n  of   SL S  al gorithm s  for   so lvi ng   of   se ve ral  com pu ta ti on al   hard  opti m i z at ion   and   s earch  pro blem s.  U nlike  previ ou s  sect i on,  he re  are   br ie fly   prese nted  so m e  of   th e  recent  s ucce ssfu l  a pp li cat ion   of   SLS  in  oth e r  sci ence  and   i ndus try   f ie lds ,   includi ng  S AT ,  MA X - S AT ,  TSP,   sche duli ng  an d  routin g  prob le m s.   Boug haci  et   al . ,   [22]  com bin e d  SL S  m et a - heu risti cs   with  the  le ast   sign ific a nt  bits   (LSB)   te c hn i que  f or   im age  ste ganogra ph y.  The  a uthors  i n  this  stud y,   im ple mented  t hr ee   m et hods   nam ed  as  LSB ,  LS B+ LS  an d  LS B+ SLS,   w hich   achiev ed   sig nifican t   resu lt s  by  al so  dem on strat ing   the  ben e fits   of   the  pro po s ed  m e tho d  in  i m age  ste gan ogra phy.   Dru ga n  [20]  pr es e nted   the  use   of   stoc hastic   par et o  local   s earch  ( SprLS )  for  m any - obj e ct ive  qu a dr at ic   assignm ent  pr ob le m   (MO QAP)  in sta nces.  P utik hin  and   Kasc heev  [25]  pr e sente d  a  heurist ic   ap proac h  f or   fin di ng   init ia l  valu es  for   SLS  i n  s olv in g SAT  pr ob le m  b y usi ng c on ti nuo us  e xtensi ons  of Bo olean  for m ulas.    Wang  et   al . ,   [23]  pro po se d  a  novel  rob ust   op ti m isa ti on   ap proac h  th at   inv ol ves  es tim a ti on   of    the  distrib utio n  al gorithm   (ED A )  an d  S LS  for  ta ckli ng   uncertai n  capaci ta te d  ar c  routing   pro blem s.     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  11 , No .  1,   Febr uar y  2021  :    71 5   -   72 7   724   This  m et ho d  com bin es  an  E DA   with  a  no vel  two  sta ge  SLS  proce dur e  to  perform   m ini m iz at ion   of   the   m axi m al  total   cost  over  a  set   of   di ff e ren t  sce nar i os .  He re ,   t he  SLS  pr ocedur e  is  us e d  to  avo i d  extrem e  fitness  values  of  unprom isi ng   m ov es  in  local   sea rc h.   T he  res ults  ob ta ine d  e xper i m enta ll y  on   two  set s  of  be nc hm ark  pro blem s sh owed  that t his alg or it hm  o ut perf or m s stat e - of - the - a rt r es ults.   Zh ou   a nd   H u  in  [18]  pro pose d  gradie nt - base d  ada ptiv e  stochastic   s earch  for  no n - diff e re ntiable   o p t i m i z a t i o n   a l g o r i t h m   f o r   s o l v i n g   g e n e r a l   o p t i m i z a t i o n   p r o b l e m s   w i t h   l i t t l e   s t r u c t u r e .   T h e   p r o p o s e d   a p p r o a c h   u s e   r a n d o m   s a m p l i n g   t e c h n i q u e   t o   i t e r a t i v e l y   f i n d   h i g h   q u a l i t y   s o l u t i o n s   f r o m   a   p a r a m e t e r i z e d   di stribu ti on m od el  o ver  the  so l ution   s pace.  C hu   et   al . ,   [ 26]   pro pose d  a  ne w  S LS  al gorithm   cal le d  CC HNV  ( hard  ne ig hbori ng   var ia bles  base d  co nf i gurati on  chec king)  f or   s olv in g  W PMS  (w ei gh te d  pa rtia l  m axi m u m   satisfiabili ty ).   Re su lt s  ob ta in ed  by  a  nu m ber   of   e xp e rim e nts  on   a  br oad  ran ge   of   WPM S  instances  sh owe d  that  CC H N V   perform ance outpe rfor m s the  sta te - of - the - art  SLS   al gorithm s r ece ntly  u se d t o  s olv e   WPMS problem .     Lu o  [ 27 ]   pro pose d  a  stoc has ti c  it erati ve  evo luti on  CT  re const ru ct io n  al gorithm   fo r  li m it ed - ang le   sp ars e  pro j ect ion   data.  T he  w orkin g  pri nci ple  of   this  al go rithm   is  as  fo ll ow:  a  stochastic   appro ac h  is  a pp li e d   for  searc hing,  and   Ma rko v  C hain  is  us ed  t o  pre dict  it erati ve  ev olu ti on  m od el   and   acc el erate  the  pro po s ed   a l g o r i t h m ’ s   c o n v e r g e n c e .   T h e   e x p e r i m e n t a l   r e s u l t s   o b t a i n e d   b y   t h e   p r o p o s e d   a l g o r i t h m   i n   i m a g e   r e c o n s t r u c t i o n   f r o m   l i m i t e d - a n g l e   s p a r s e   p r o j e c t i o n   d a t a   a r e   p r o m i s i n g   a n d   r o b u s t n e s s .   So m e  oth er  s uc cessf ul  ap plica ti on s  of   S LS  introd uced   rec ently   include :  analy sis  of   SL S  m e tho ds  us e d  f or so l ving the  unr el at e d par al le l m achine sc hedulin g pro blem  p resen te d   by Sa nto s   et  a l . ,   [32], im pro ved  g e n e r i c   B E T - AND - R U N   s t r a t e g y   w i t h   p e r f o r m a n c e   p r e d i c t i o n   f o r   S L S   b y   W e i s e   e t   a l . ,   [ 3 3 ] .   O n   t h e   o t h e r   s i d e ,   L o r e n z  a n d   W ö r z   [ 5 5 ]  d e m o n s t r a t e d  b e n e f i t s   o f  u s i n g  t h e  l e a r n e d  c l a u s e s   o n  S L S ,   f o l l o w e d   b y   H e  a t  a l . ,   [56 ]   who   pr ese nted   his  a ppr oach  f or  s olv in g  floati ng - point  c onstra int   by  us in g  S LS,   Ca ceres  et   al . ,   [5 7 ]   who   pro pose d  us in g  of  SLS  in  direct  ape rt ur e  op ti m isa t i on   pro blem   in  intensit y  m od ulate d  ra diati on  thera py.  S usa n  an d  Bhu ta ni  [ 58 ]   i ntr oduce d  a  novel  m e m etic   al gorithm   that  incorp or at es   gr ee dy  SL S  m uta ti on   f or   cour se   sche du li ng  a nd  Chu   et   al . ,   [59 ]   pr es ente d  pr om isi ng   e m pirical   inv est igati on  of  usi ng  SLS   for  so l ving  M AX - SA T  pro blem .       5.   CONCL US I O N   Nowa days,  t he re  is  gr eat   interest   in  re search   com m un it y  an d  i ndus t ry  to  so l ve  c om plex  com bin at or ia l  op ti m isa t ion   a nd   decisi on   pr ob le m s,  as  the  nu m ber   of  the se  is  pr ese nt  in  seve ral  bran ches  in   sci ence  an d  in du st ry  on   wh ic h  com pu ta ti onal   m e tho ds  ha ve  bee n  widel y  app li ed.   SL S   is  ver y  i m po rtant  and  powe rful  to ol  us e d  f or  s olv i ng  ha r d  c om bi nato rial   optim i sat ion   pro blem s.  A s  a  ne w  a p pr oach  it   is  m ai nly   char act e rized  by   ran dom iz ation   durin g  the  lo cal   search.   SL S  al go rit hm s  h ave  bee n  us e d  for  a  wh il e  to  ta ckle   hard  c om bin at or ia l  prob le m s  as  the  num ber   of  t hese  is  present  i n  se veral   br a nc hes  in   sci ence  a nd  in du st ry  includi ng   a rtif ic ia l  i ntelligence,  m achine  le arn i ng,  data  m ining ,  ope rati on s  re searc h,  bio in form at ics  an d  el ect ro nic c omm erce.   Var i ou s  SLS  m et ho ds   ha ve   been  em plo ye ed  to  s olve   c om bin at or ia l  optim isa ti on   prob le m s,  bu t   us ua ll y  al l  thes e  m et ho ds   ha ve   been   gro upe d  in  th ree  m ajor  cl asses:   the  fi rst  cl ass  is  known  as  " sim ple"   SLS  m et ho ds,  as  th e  te rm   den otes   they   are  m a inly   based   on   sim ple  searc h  te ch niques,  the  sec ond  cl ass  c omprises   of   hybri d  SLS  m et ho ds,  w hic h  inte gr at e  se ve ral  searc hing  te chn iq ues  an d  he ur ist ic s  an d  the  thir d  cl as s  wh ic h  is  m or e  com plex  an d  is  know n  as  popula ti on - base d  SL S  m et ho ds,  w hic h  pr oceed s  wit h  a  set   or  popu la ti on   of   cand i date  so lut ion s .  These  S L S  m et ho ds   c om pr ise s  a  nu m ber   of   well - kn own  te ch nique s  m ai nly  insp ir ed  by  natu ral phe nom ena,  w hich  have  been wi del y   app li ed  to  v a rio us  tas ks .   Exce pt  the  fa ct   that  these  al gorithm s  are  widely   us ed   and  are  powe rful  to ol  in  ta ckling  ha r d  com bin at or ia l  pro blem s,  m anu al   co nf ig urat ion   of   t hese  al gorithm s  is  com plex  and   ti m e  con su m ing  ta sk .     In   order   t o  ov erp as s  these  pro blem s  a  lot  of   researc h  w ork  ha s  bee n  done  with  re ga rd   t o  the  a uto m at ed   al gorithm   config ur at io n  a nd  par am et er  tu ning  te ch niqu es.   A ddit ion al ly ,  so m e  of   t he  la te st  su cc essfu l   app li cat io n  of  SLS  al gorithm s  in  m achine  lear ni ng,  data  m i ning  an d  oth er  fiel ds   in  sci e nc e  and   i ndus try   hav e   b e e n   p r e s e n t e d .   W e   h o p e   t h a t   i s s u e s   d i s c u s s e d   i n   t h i s   p a p e r   w i l l   p u s h   f o r w a r d   t h e   d i s c u s s i o n   i n   t h e   a r e a   S L S   r e s e a r c h ,   o n   t h e   s a m e   t i m e   i t   m a y   s e r v e   a s   c o m p l e m e n t a r y   m a t e r i a l   f o r   o t h e r   r e s e a r c h e r s   i n t e r e s t e d   i n   a r e a   o f   S L S .       REFERE NC ES   [1]   Holger   H .   Hoos   and  Thomas Stüt zl e ,   “ Stocha st ic l oca l   sea r c h:  Fou ndat ions  and app li c at ions, ”   El sev i er ,   2004 .   [2]   Shen  Li n  and  Br i an  W .   Kerni gh a n,   “ An  eff ec t ive   heur isti c  al gor ithm   for   the   tra v eling - sale sm an  pr oble m , ”   Informs ,  vol.   21 ,   no .   2 ,   pp .   498 - 516 ,   1973 .   [3]   Thomas  Bac k ,   “ Evol uti on ar y   algorithms   in  th eo r y   and  p racti c e:  evol u ti on  str ate gie s,  evol ut iona r y   progra m m ing,  gene t ic   al gor it h m s,”   Oxford  uni ve rs it y   press ,   19 96.   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Sto c hasti c local  sea rc h: A st ate - of - t he - ar t rev ie w   ( Muham et   Kastrati )   725   [4]   Scott   Kirkpa tric k,   C .   Daniel  G el a tt ,   and  Mar i o  P .   Vec chi ,   “ Opti m iz at io n  b y  sim ula te d  ann ea l ing, ”   Scienc e ,    vol.   220 ,   no .   459 8,   pp .   671 - 680 ,   1983.   [5]   Ala in  Her tz  and   Dom ini que  de   W err a,   “ Us ing  t abu  sea r c h  tech nique s  for  g rap h  col or ing,”   Co mputing ,  vo l.  39 ,    no.   4 ,   pp .   345 - 3 51,   1987 .   [6]   Bart   Selman,   H e ct or  J .   L eve sque ,   David  G .   Mit ch el l ,   et   al. ,   “ A  ne w m et hod  for  solving  har d  sat isfi a bil i t y   p r o b l e m s , ”   In  P r o c e e d i n g s   T e n t h   N a t i o n a l   C o n f e r e n c e   o n   A r t i f i c i a l   I n t e l l i g e n c e   ( A A A I - 92) ,   v o l .   9 2 ,   p p .   4 4 0 - 4 4 6 ,   1 9 9 2 .   [7]   Bart   Selman,   H e nr y   A .   Kau tz,  an d  Bram  Cohen,   “ Noise  strat eg ie s for  improvin g  lo ca l  se arc h , ”   In   A AA I - 94 ,   vo l.   94 ,   pp.   337 - 343 ,   19 94.   [8]   Frank  Hutte r ,   H olge r  H .   Hoos ,   Kevin  L e y ton - B rown,  and  Thomas  Stütz le,   “ P ara m il s:  an  aut o m at ic   al gori thm   conf iguration fra m ework, ”   Journ al  of   Artificia l   In te lligen ce R ese a rch,   vol .   36 ,   pp .   267 - 306,   2009 .   [9]   Holger   H .   Hoos ,   “ Autom at ed  a lg orit hm   con figur a ti on  and  p ara m eter  tun ing,”  Au to nomous   search ,  pp.   37 - 71 ,   2011 .   [10]   Marie - E lé onor e M armion,   Franc o  Mascia,  Manu el   L óp ez - Ib ánez, a nd  Thomas Stü tz l e,   “ Autom at ic de sign o f  h y brid   s t o c h a s t i c   l o c a l   s e a r c h   a l g o r i t h m s , ”   I n   I n t e r n a t i o n a l   W o r k s h o p   o n   H y b r i d   M e t a h e u r i s t i c s ,  v o l .   7 9 1 9 ,   p p .   1 4 4 - 1 5 8 ,   2 0 1 3 .   [11]   Franc o  Masci a,   Manue l  Lóp ez - I báñe z ,   Jér émie  Dub ois - La coste,   and  Thomas  St ütz l e,   “ Gram m ar - base d  gen era t io n  of  stocha sti c  lo c al   se arc h  h eur ist ic s  through  aut o m at ic   al gori thm  conf ig ur at ion   t ools ,”   Comput er s  &   operati ons   research ,   vo l. 51 ,   pp .   190 - 199 ,   2 014.   [12]   Feder i co   Pagno zz i  and  Thomas  Stütz le,  “ Aut om at ic   d esign  of  h y br id  stoch asti c  local  se ar ch  al go rit hm s  fo r  per m uta ti on   flo ws hop  proble m s,”   European Jou rnal  of  Operat io nal  R ese arch ,  vo l.   276 ,   no .   2 ,   pp .   409 - 421,   2019 .   [13]   Franc o  Masci a,   Manue l  Lóp ez - I báñe z ,   Jéré m i e  Dubois - La coste,   Marie - E lé on or e   Marm ion,   and  Thomas  Stütz le,   “ Algorit hm   compari son  b y   aut o m at ic a lly   conf ig ura ble  stocha st i c  lo ca l   sea r ch  f rameworks:  A  c ase   stud y   usin g  flow - shop   sche d uli ng  prob le m s,”   In  Int ernati onal   Workshop   on  H ybrid  Me tahe uri stic s ,  vo l.  8457,   pp.   30 - 44 ,   2014 .   [14]   Alb ert o  Franz in  and  Thomas  Stüt zl e ,   “ Revi sit ing  sim ula te d  ann eal ing:   A  compone nt - base d  an aly si s,”   Computers   &  Operations  Re se arch ,   vol .   104 ,   p p.   191 - 206 ,   201 9.   [15]   Alber to  Franz in ,   Le slie   Pére z  Các ere s,  and  Thom as   Stütz le,   “ Eff ec t  of  tra nsform ations  of  nu m eri c al   par amet ers  in  au tomatic  al gori t hm   conf igura t io n, ”   Opt imizati on   Letters ,  vol .   12 ,   no.   8 ,   pp .   1741 - 1753,   2018 .   [16]   Alb ert o  Franz in   and  Thomas  Stütz l e,   “ Com p ari son  of  acce pt a nce   c riter ia  in  ran dom iz ed  local  sea r che s, ”   In   Inte rnational   Co nfe renc e  on   Artif ic ial E vol ut ion  ( Ev olution  Arti f iciel l e) ,  vol .   1076 4,   pp .   16 - 29 ,   20 17.   [17]   Zongxu  Mu,  Ho lge r  H.  Hoos ,   and  Thomas  Stütz l e,   “ The   impact   of  aut om ate d  al gori thm  conf igura t ion  on  t h e   sca li ng  beh avi o ur  of  stat e - of - th e - art   in exact   tsp   solvers, ”   In  Int ernati onal  Conf ere nce   on  Learning  and   Inte llige nt  Optimizati on ,  vo l.   10079 ,   pp .   157 - 172 ,   2016 .   [18]   Enl u  Zhou   and   Jiaqi ao  Hu ,   “ Gradi en t - base d  adaptive   sto cha st ic   sea rch   for   non - d iffe ren ti ab le  optim iz at ion , ”   I EEE   Tr ansacti ons o n  Aut omatic Cont r ol ,   vo l. 59, no. 7, pp. 1818 - 1832,   2014.   [19]   Christophe r  D .   Rosi n,   “ Unw ei ghte d  stocha st ic   l oca l  sea r ch  ca n  be  eff e c ti v e  for  ran dom   csp  benc hm ark s ,”   arXiv   pre print  arXi v:1 411. 7480 ,   2014.   [20]   Mada li n a  M.   Drugan,   “ Stoch astic  par et o   local  se arc h  for   m an y   o bje c ti ve   quadr at i c  assignm ent   pr oble m   insta n ce s , ”   2015  IEEE  Con gress   on  Ev olu tionar y  Computation ( CEC) ,   Sendai ,   pp .   1754 - 1761 ,   2015 .   [21]   Andrea s  Fröhlic h,   Arm in  Bie re,  Christoph  M .   Wi nte rstei g er,   a nd  Youssef   Ham adi ,   “ Stocha sti c  loc al   sea rch   f or   sati sfiability   m o dul o  the ori es ,”   Proce ed ings  of   the   Tw ent y - N i nth  AA AI  Con f ere nce   on  Arti f ic ial   In te l li g ence ,     pp.   1136 - 1143 ,   2015.   [22]   Dali l a  Boughaci,   Abdelha f id  Ke m ouche ,   and  Ho ci ne   L ac h ibi ,   “ St ocha sti c  local  se arc h  combined  with  lsb  te chn iq ue  for  image   stega n ogra ph y ,”   2016   13th  Learning  a nd  Technol og y Confe renc e  ( L & T) ,   Jedda h ,  pp .   1 - 9,   2016 .   [23]   Juan  W ang,   Ke  Ta ng,   Jos e  A .   L oza no,   and  Xin  Yao,   “ Esti m at io n  of  the   d istri bu ti on  a lgori thm  with  a  stoch astic   loc a l  sea rch   for   unce rt ai n  c apaci t at ed  arc   rout i ng  proble m s,”   I EE E  Tr ansacti o ns  on  Ev olut ion ary  Computati o n ,    vol.   20 ,   no .   1 ,   pp .   96 - 109 ,   2016 .   [24]   Abde ll ah   Rez ou g  and  Da li l a  Bo ughac i , ”   A  self - ada pt ive   h armony   se arc h   combin ed  with   a  sto chas ti c  lo cal  se arch   for  the   0 - 1  m ult i dimensional   kna psac k  probl em, ”   Inte rnational   Jo urnal  of  Bi o - Ins pired  Computation ,  vol.   8 ,   no.   4 ,   pp .   234 - 239 ,   20 16.   [25]   Nikit a  Putikh in  and  Nikolay   K a sche ev,   “ A  heur isti c  to  find  ini t i al   va lue s  for  sto cha sti c  local  se a rch   in  sa t   using  cont inuous  exte n sions  of  boole an  form ula s,”   2017  IEE E  East - W est   Design  &   Te st  Symposium  ( EWD TS) ,   Novi  Sad ,  pp.   1 - 4 ,   2017 .   [26]   Yi  Chu,   Chuan   Luo,   W enxua n   Huan g,   Haih a ng  You,  and  D ongrui  Fan,   “ Hard  nei ghbor ing   var ia b le s  base d  conf iguration  ch ec king  in  sto ch a stic   local  sea r ch   for  weight ed   p art i al   m axi m um  sati sfiability , ”   2017  IEE E  29th   Inte rnational   Co nfe renc e  on   Tool s wit h  Arti f ic ia l  I nte lligen ce ( ICT AI) ,   Boston,  MA ,   pp .   139 - 146 ,   2 017.   [27]   La n  Luo,   Hong xia   Gao ,   Yingh ao  Luo ,   and   Yongfei   Ch en,   “ A  stocha sti c  i terati v e  evo lut ion   ct   r ec onstru ct i on   al gorit hm   for  lim it ed - angle  sparse  proje ction  dat a , ”   2017  IEEE   Inte rnational   C onfe renc e  on  Bioinformatic s  and   Bi omedi ci ne   ( BIB M) ,   Kansas Ci t y ,   MO ,   pp .   740 - 744 ,   2017 .   [28]   Tong  Yu,  Branis la v  Kveton,   an d  Ole  J .   M engsh oel ,   “ Thomps on  sam pli ng  for  op t imizi ng  stoch asti c  lo ca l  sea r ch,”     In  J o i n t   E u r o p e a n   C o n f e r e n c e   o n   M a c h i n e   L e a r n i n g   a n d   K n o w l e d g e   D i s c o v e r y   i n   D a t a b a s e s ,  v o l .   1 0 5 3 4 ,   p p .   4 9 3 - 510 ,   2 0 1 7 .   [29]   Sabrina   Olive i ra ,   Moham ed  Saiful la h  Hus sin,  Andrea   Roli ,   M arc o  Dorigo,   an d  Thomas  Stütz le ,   “ Anal y s is  of    the   popu la t ion - base d  an t  co lon y   op ti m izati on   al gorit hm   for   t he  ts p  and  th e   qap,”   2017   IE EE   Congress   o n   Ev olutionar y  Co mputati on  ( CEC ) ,   San  Sebastian ,   p p.   1734 - 1741,   2017.   [30]   Lui s  Paquete  and  Thomas  Stütz l e,   “ Stoch asti c  lo cal  sea r c h  al gorit hm s  for  m ult iobj e c tive  combinat or i al  opti m iz ation, ”   Handbook  of  Approxi mation  Al gorithms  and  Me tahe uristi cs:  Me thol ogi es  and  Tr adit ional  Appl ic a ti ons ,  vo l.   1 ,   2018 .   [31]   Dangd ang  Niu,   Le i  Li u ,   and  Shuai  Lü,   “ New  stocha stic   local  sea r ch  app roa ch es  for  computing  pre fer red   extensions   of  abstract   arg u m ent at ion , ”   AI   Comm unic ati ons ,   vol.   31 ,   no .   5439 ,   pp .   1 - 14 ,   2016 .   Evaluation Warning : The document was created with Spire.PDF for Python.