I n d on e s i an   Jo u r n al   o El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   18 ,   N o .   2 M a y   20 20 ,   pp .   1035 ~ 1039   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 8 .i 2 . pp 103 5 - 1039             1035       Jou r n al   h o m e pa ge ht t p: / / i j e e c s . i a e s c or e . c om   A n   e n h a n c e d   h y b r i d   g e n e t i c   a l g o r i t h m   f o r   s o l v i n g   t r a v e l i n g   sa l e sm a n   p r o b l e m       Ze r av an   A r i f   A l i ,   S u b h i   A h m e d   R as h e e d ,   N ab e e l   N o ’m an   A l i   1 M a na g e m e n t   I nf o r m a t i o S y s t e m ,   D e p a r t m e n t   a t   D uho k   P o l y t e c hni c   U ni v e r s i t y ,   I r a q       A r ti c l e   I n fo     A B S TR A C T     Ar t i c l e   h i s t or y :   R e c e i v e A ug   7 ,   2019   R e v i s e N o v   9 ,   2019   A c c e pt e N o v   23 ,   201 9       R o bus t   kno w t he   e xc e e di ng l y   f a m e N P - ha r d   pr o bl e m   i n   c o m bi na t o r i a l   o pt i m i z a t i o i s   t h e   T r a v e l i ng   S a l e s m a n   P r o bl e m   ( T S P ) ,   p r o m o t i ng   t he   s k i l l f ul   a l g o r i t hm s   t o   g e t   t he   s o l u t i o o f   T S P   ha v e   be e t h e   bur de n   f o r   s e v e r a l   s c ho l a r s .   F o r   i n qu i r i ng   g l o ba l   o pt i m a l   s o l ut i o n,   t h e   pr e s e nt e d   a l g o r i t hm   hy br i di z e s   g e ne t i c   a n d   l o c a l   s e a r c a l g o r i t hm   t o   t a ke   o ut   t he   upl i f t e d   qu a l i t y   r e s u l t s .     T he   g e n e t i c   a l g o r i t hm   g i v e s   t h e   be s t   i ndi v i d ua l   o f   po pul a t i o by   e nha nc i ng   bo t c r o s s   o v e r   a nd  m u t a t i o o pe r a t o r s   w hi l e   l o c a l   s e a r c g i v e s   t he   be s t   l o c a l   s o l ut i o ns   by   t e s t i ng   a l l   n e i g hbo r   s o l u t i o n.   B y   c o m pa r i ng   w i t h   t he   c o nv e nt i o na l   g e ne t i c   a l g o r i t hm ,   t he   num e r i c a l   o ut c o m e s   a c t s   t ha t   t he   pr e s e nt e a l g o r i t hm   i s   m o r e   a de q ua t e   t o   a t t a i o pt i m a l   o r   v e r y   ne a r   t o   i t .   P r o b l e m s   a r r e s t e f r o m   t he   T S P   l i b r a r y   s t r o ng l y   t r i a l   t h e   a l g o r i t hm   a n s ho w s   t ha t   t h e   p r o po s e a l g o r i t hm   c a r e a o ut c o m e s   w i t h i r e a c o pt i m a l .   F o r   m o r e   de t a i l s ,   pl e a s e   do w nl o a T E M P L A T E   H E L P   F I L E   f r o m   t he   w e b s i t e .   Ke y w or ds :   G e n e t i c   a l go ri t hm   L oc a l   s e a r c h   T S P     C opy r i gh t   ©   2020   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e .     A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   Z e r a v a n   A ri f   A l i   D uh o P o l y t e c gn i c   U ni v e r s i t y ,   D e pa r t m e n t   a t   D u ho P o l y t e c hni c   U ni v e r s i t y ,   I r a q.   E m a i l dqs z e e b a r e e 2@ l i v e . ut m . m y       1.   I N TR O D U C TI O N     T h e   T r a v e l i n S a l e s m a n   P r o b l e m   [1]  i s   t h e   r e n o w n e a n c o n s i de r a b l e   c o m b i n a t o r i a l   o pt i m i z a t i o n   pr o b l e m s .   It   w a s   e xa m i n i ng  i n   t h e o r e t i c a l   c o m put e r   s c i e n c e   a n o pe r a t i o n a l   r e s e a r c h   f i e l ds .   E v e r   a f t e r   t h e r e   i s   n o   s o l ut i o n   n e a r   a n pr o xi m a l   t o   c o n s t a n t ,   c o n s e q ue n t l y   t h e   t r a v e l i n s a l e s m a n   pr o b l e m   i s   N P   c o m pl e t e .   A s   i n   de f i n i t i o n   o f   t h e   T S P ,   t h e   m a i n   i de a   s a y s   t h e r e   s e v e r a l   c i t i e s   a n t h e   di s t a n c e   a m o n e a c h   c o upl e   o f   i t .   T h e   go a l   a c t   t o   r e t ur t o   t h e   r o o t   c i t y   a f t e r w o r v i s i t i n e v e r y   c i t y   n i c e l y   a t   o n e   t i m e .   T h e   c h a l l e n ge   i s   t o   c a l c ul a t e   a nd  m i n i m i z e   t h e   t o t a l   v a l ue   o f   t h e   c o s t   dur i n t r a v e l i n [2 - 3].   T h e   t e s t   a n di f f i c ul t y   i n   t h e   t r a v e l i n s a l e s m a n   pr o b l e m   s o m e t h i n g   c ur i o us ,   s o   t h a t   r e s e a r c h e r s   m a ke   i t   a s   a   po di um   i n   o r de r   t o   e xa m i n e   b o t h   t h e   e xa c t   a nd  a ppr o x i m a t i o n   a l go r i t h m s .   T h e   e xa c t   a l go r i t h m s   a r e   go o f o r   t h e   s m a l l   pr o b l e m s ,   w h i l e   t h e y   a r e   n o t   f o r   t he   l a r ge   r a n ge   pr o b l e m s ,   b e c a us e   t h e   pe r f o r m a n c e   i s   de c r e a s e d,   a n t h e   t i m e   n e e t o   ge t   t h e   o pt i m a l   o n e   i s     l o n [4].   T h a t   i s   w h y   t h e   o t h e r   t y pe s   o f   a l go r i t hm s   a r e   b e t t e r   a n t h e y   pr o v i de   e l e ga n t   r e s ul t s .   T h e r e   a r e   t w o   t y pe s   o f   o pt i m a l   s o l ut i o n s ,   o n e   o f   t h e m   i s   l o c a l   w h i l e   t h e   o t h e r   i s   gl o b a l ,   a n b o t h   s o l ut i o n s   c a n   ge t   b y   us i ng  t h e   a ppr o xi m a t i o n   a l go r i t hm s   [5].   A l go r i t h m s   us e t o   f i n o pt i m um   c a l l e h e ur i s t i c   o pt i m i z a t i o n .   D i f f e r e n t   ki n ds   o f   h e ur i s t i c   a l go r i t hm s   h a v e   b e e n   h a n dl e t o   l e a t o   ge t   t h e   l o c a l   o pt i m a l   s o l ut i o n   a n t r y   t o   ga i n   t he   gl o b a l   o pt i m a l   s o l ut i o n   o r   n e a r   gl o b a l   s o l ut i o n   t o   s o l v e   T S P ,   l i ke   G e n e t i c   A l go r i t h m   [5 - 6],   S i m ul a t e A n n e a l i ng  [7],   P a r t i c l e   S w a r m   [8],   T a b S e a r c h   [9],   A r t i f i c i a l   N e ur a l   N e t w o r [9 - 10]  A n t   Co l o n y   [10] ,   A r t i f i c i a l   Im m un e   a l go r i t h m ,   a n ge n e t i c   a l go r i t h m   [11].     G A   c o n c e pt   f o r m a l i z e f o r   t h e   f i r s t   t i m e   b y   H o l l a n [12].   It   e m ul a t e s   t h e   n a t ura l   s e l e c t i o n   a n t he   e v o l ut i o n   m e c h a n i s m   o f   D a r w i n .   T h e   ge n e t i c   a l go r i t h m   pr o v e a m o n a l l   o f   t h e s e   e v o l ut i o n a r y   a l go r i t h m s   t ha t   i t   h a s   b e s t   pe r f o r m a n c e   a n pr o v i de   m o r e   pr e c i s e l y   a n e f f i c i e n c y   f o r   s o l v i n t h e   c o m b i n a t o r i a l   o pt i m i z a t i o n   pr o b l e m s   (CO P ).   W i t h i n   o ur   w o r k,   w e   pl a n ne a   G e n e t i c   Im pr o v e m e n t   Co n c e n t r i c   T a b A l go r i t h m   (G ICT A ) ,   w h i c h   i n t e gr a t e s   t h e   l o c a l   t e c h n i que   t o   c l a s s i c a l   m e t a h e ur i s t i c   G A .   In   h y b r i a l go r i t h m   (pr e s e n t e d)  t h e   l o c a l   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   18 ,   N o .   2 M a y   20 2 :     1035   -   1 039   1036   a ppr o a c h   t e s t e t o   t h e   b e s t   i n di v i dua l   s o l ut i o n   o b t a i n e b y   G A   i n   o r de r   t o   pr o t e c t   t h e   c o r r e s po n de n c e   due   t o   s e a r c h   pr o c e s s   b e t w e e n   b o t h   e xpl o r a t i o n   a n e xpl o i t a t i o n   [13].   T h e   ge n e t i c   a l go r i t hm   t r i e s   t o   b e   m o r e   e f f e c t i v e   f o r   f i n di n b e s t   po pul a t i o n   w h i l e   t h e   go a l   o f   l o c a l   m e t h o i s   t o   pr o v i de   b e t t e r   s o l ut i o n   b y   t e s t i n a l l   i t s   n e i gh b o r i ng  a n s e l e c t i n t h e   b e s t   f i t n e s s .   T o   i m pr o v e   t h e   n a t ure   o f   m e t a h e ur i s t i c   a l go r i t h m ,   l o c a l   t e c h n i q u e   h a s   b e e n   i n s e r t i ng  i n t o   i t .   O v e r a l l ,   t h e r e   i s   n o   w a y   t o   pi c up  t h e   o pt i m a l   s o l ut i o n   [13 - 15].   Co n s e que n t l y ,     i n   e v o l ut i o n a r y   a l go r i t h m s   w i t h o ut   a ppl y i n l o c a l   t e c h n i que s   t h e r e   i s   n o   pr o m i s e   t o   o b t a i n   t h e   o pt i m a l     s o l ut i o n   [16].   T o   c h e c t h e   c a pa b i l i t y   o f   pr o v i n t h e   pr o po s e a l go r i t hm ,   a   b e n c h m a r pr o b l e m   t a ke n   f r o m   T S P L IB   [17]  a r e   us e d.   R e m a i n   s e c t i o n s   o f   t h i s   pa pe r   i s   f o r m e a s   f o l l o w s .   S e c t i o n   t w o   s h o r t l y   i n t ro duc e   t he   t r a v e l i n s a l e s m a n   pr o b l e m .   S e c t i o n   t h r e e   de s c r i b e   t h e   b a s i c   G ICT A .   S e c t i o n   f o ur   e xpl a i n s / di s c us s e s   t he   r e s ul t s .   F i n a l   s e c t i o n   pr o v i de s   t h e   c o n c l us i o n ,   f ut ur e   w o r a n e xpa n s i o n .       2.   TR A V ELI N G   S A LES M A N   P R O BLE M   ( TS P )   T h e   t r a v e l i ng   s a l e s m a pr o b l e m   (T S P )   i s   t h r e n o w n e d   quo t e n o n   de t e r m i ni s t i c   po l y n o m i a l   ha rd  pr o b l e m   i n   CO ,   b e c a us e   t h e   di f f i c ul t y   a n c h a l l e ngi ng   t o   s o l v e   i t   r a t he t h a un de r s t a ndi ng   i t   [18] A   l o t   o f   a l go r i t hm s   a n a   v a r i o us   a ppr o a c h a s   b e e n   t e s t e i n   o r de r   t o   s o l v i n t h e   t r a v e l i ng  s a l e s m a p r o b l e m ,   s o m e   o t h e m   h a s   a   go o pe r f o r m a nc e   a n o b t a i n e a   v e r y   w e l l   s o l ut i o n s ,   w h i l e   o t h e r s   h a v e   l i m i t a t i o t o   s o l v e   s o m e   o v e r y   l a r ge   pr o b l e m s .   T S P   de s c r i b e s   h a s   b e e n   do n e   i n   G r a ph  t h e o r y   de s c r i b e s   a s   a   w e i gh t e gr a ph  w h e r e   v a r i a b l e s   a r e   c h a r a c t e ri z e a s   f o l l o w s ,   T S P = G   =   (V ,   E ,   c i n   w h i c h   V   =   (v 1, v 2, . .   v m ),   v e r t e i s   v i (1< i < m ),   E   =   e i j (m x m (e dge s   s e t w h e r e   e i j   (1< i ,   j < n i s   t h e   e dge   w h i c h   c o n t a c t   v i   a n v j ,   a n a   :   E -- > Z ,   t h e   c o s t   o r   di s t a n c e   us ua l l y   r e f e r   t o   c ,   a n t h e   c o s t   m us t   n o t   o v e r r i de   c .   T S P   i s   c l a s s i f i e i n t o   t w o   c a t e go r i e s ,   o n e   o f   t h e m   i s   S y m m e t r i c   w h i l e   t h e   o t h e r   i s   A s y m m e t r i c   b a s e o n   t h e   gr a ph  t y pe   a n a r ra nge m e nt   o f   di s t a nc e s .   If   t h e   di s t a n c e   i n   t w o   s i de s   i s   s a m e ,   i t   i s   s y m m e t r i c ,   b ut   i f   n o t   e qua l   i t   i s   a s y m m e t r i c   [19]   T o   c a l c ul a t e   t h e   t o ur   l e n gt h   f o r   s y m m e t r i c   t y pe   i s   s h o w n   b e l o w   i n   ( 1 )     = ( D     + 1 ) + D     + 1   1 = 1   (1)     T h e   pr o b l e m   i s   o pa c i t y   f o r   f i n di ng  a   l o w e s t   pa t h .   B y   us i n t h e   E uc l i de a D i s t a n c e   T h e   di s t a nc e   b e t w e e n   c i t i e s   w i t h   c o o r di n a t e s   (x, y )i s   c a l c ul a t e a s   f o l l o w s :     D xy = ( ) 2   (2)       3.   TH E   P R O P O S ED   A L G O R I TH M   A   h y b r i G A   us e a s   a   t e c hn i que   f o r   i n c o r po ra t i o n   o f   G A   w i t t h e   l o c a l   t e c hn i que s   t o   s o l ve   t h e   t r a v e l i n g   s a l e s m a p r o b l e m   i e f f i c i e n t   m a nn e r .   T h e   r o l e   o f   t h e   ge n e t i c   a l go r i t hm   i s   t o   c h o o s e   b e s t   i ndi v i dua l   s o l ut i o by   s a t i s fy i n g   a   r e v e r s e   s e que n c e   m ut a t i o n ,   t o urna m e nt   s e l e c t i o n,   a nd   a o rde r e d   c r o s s ov e r   a s   w e l l   a s   t h e   i ni t i a l   s o l ut i o n   ha s   b e e n   s e l e c t   r a ndo m l y   i t h e   v e r y   be gi nni n g   o f   t h e   a l go ri t hm .   I c o n t ra s t ,   t h e   r o l e   o f   t h e   l o c a l   m e t h o i s   t o   e s c a pe   f r o m   l o c a l   o pt i m a   b y   a c t i n a n g e n e ra t i n s o m e   a c t i o n   t o   i m p r o v e   t h e   o v e r   ha n s o l ut i o a n d   t r y i n g   t o   r e a c t h e   gl o b a l   o pt i m a l   s o l ut i o n   o s ub   gl o b a l   o pt i m a l   s o l ut i o de pe ndi n g   o t h e   s c a l e   of   t h e   p r o b l e m .   I l a r ge   s c a l e s   t h e   p r o po s e a l go r i t hm   pi c ks   up   t h e   v e r y   n e a g l o b a l   s o l ut i o n,   w h i l e   i s m a l l   a n d   m e d i um   s c a l e s   t h e   p r e s e nt e d   a l go r i t hm   e a s y   r e a c t o   g l ob a l   s o l ut i o i s h o r t   t i m e .   T h e   p r o po s e H y b r i G e n e t i c   A l go ri t hm   c o m b i n e s   t h e   l o c a l   s e a r c h   m e t h o i nt o   b e s t   i n di v i du a l   s o l ut i o n   f o un by   t h e   t ra di t i o na l   m e t a h e u r i s t i c   a l go r i t hm   w i t h   a   v i e w   t o   c o n t r o l   a n d   p r o t e c t   t he   po i s e   a n t o   pi c ks   t h e   po s i t i v e l y   a dv a n t a ge s   f o r   bo t e xpl o ra t i o a n d   e xpl o i t a t i o a b i l i t y   due   t o   t h e   s e a r c pr o c e s s   [19 - 20] .   T h e   go a l   o f   l o c a l   s e a r c i s   t e xc h a n g i n a l l   t h e   o ut s t a n di ng  s o l ut i o n s   n e a r by   t o   t h e   f i ne s t   fo un s o l ut i o n   a nd  e v a l ua t i n g   t h e   d i s t a n c e ,     w h i c di s t a n c e   i s   s m a l l   o r   ha v e   a   l e s s   f i t n e s s ,   i o r de t o   i m p rov e   i t ,   a f t e r   t h a t   i t   w i l l   b e   s e l e c t   a s   a   b e s t   s o l ut i o n   fo un d   s o   f a r.   If   t h e   f a v o r a b l e   s o l ut i o i s   w o r s e   t h a t o   v e r y   n e a r b y   s o l ut i o n ,   i t   i s   go i n g   t o   e xc h a n ge   i t ,   a n d   i t   w i l l   b e c o m e   t h e   b e s t   s o l ut i o n,   a nd  t h e   p r o c e s s   w i l l   c o n t i nue   unt i l   a l l   n e a r b y   s o l ut i o n   b e e n   c h e c ke a n g l o b a l   o r   n e a r   t o   gl o b a l   s o l ut i o h a s   b e e n   t a ke n .   H e ur i s t i c   ge n e t i c   a l go r i t hm   i s   t r i e t o   e nha n c e   e ve r y   p o pul a t i o n   by   s e l e c t   b e s t   i n di v i du a l .   F o t h e   a b o ve   r e a s o t h e   i m po r t a nt   o f   l o c a l   m e t h o ds   a ppe a t o   o b t a i t h e   b e s t     o ut c o m e s   [21].   T a ki ng  i n t o   a c c o un t   w i t h o ut   l o c a l   t e c hn i que s   n o   m e t h o c a b e   fo un f o r   o pt i m u m   s o l ut i o n s ,   a n t h e r e   i s   n o   gu a r a nt e e   t o   c r o s s   t h e   l o c a l   o pt i m a l ,   a n i t s   v e r y   t i m e   c o n s um i n w i t h o ut   a n y   c h a n ge ,   a nd  i t   r e m a i i s t uc a s   w e l l .   T h e r e fo r e ,   e v o l ut i o n a r y   a l go ri t hm s   ha v e   l i m i t e o ppo rt u n i t y   r u n   a w a y   f r o m   l o c a l   s o l ut i o a n d   p i c u t h e   o pt i m a l   gl o b a l   s o l ut i o n.   T h e   f o l l ow i ng  h y b r i d   a l go ri t hm   i l l us t r a t e s   t h e   s t e ps   o f   f i n d i n a n s e l e c t i n g   t h e   ra n do m   i n i t i a l   s o l ut i o u nt i l   a rri v e   t o   t h e   b e s t - f o un s o l ut i o o v e r   a l l   a ppl y i n g   t h e   a l go r i t hm   fo r   s o l v i n g   t ra v e l l i n g   s a l e s m a p r o b l e m .     Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A e nhan c e h y br i g e ne t i c   al gor i t hm   f or   s ol v i ng   t r a v e l i ng   s al e s m an   pr obl e m   ( Z e r av an  A r i f   A l i )   1037   3. 1 .       A l go r i th m - 1   a)   A ppl y i n t h e   ge n e t i c   a l go r i t hm   p a r a m e t e r s   (i ni t i a l i z a t i o n,   E v a l ua t i o n,   s e l e c t i o n ,   c r o s s o ve r   a n d   m ut a t i o n t o   o b t a i n   t h e   b e s t   i ndi v i dua l   s o l ut i o n.     b)   T h e   b e s t   i n d i v i dua l   s o l ut i o f o un b y   t h e   ge n e t i c   a l go r i t hm   i t   e xe r c i s e t o   t h e   l o c a l   s e a r c h   m e t h o d.   It   i s   s e t   t o   t h e   c e nt e s o l ut i o n .   c)   S e t   c o un t = 0 ,   p = 0 ,   f l a g = 0.   F i n e s t   l i s t   c o nt a i n   t h e   m i ddl e   s o l ut i o n .   B e s t   fo un s o l ut i o n   i s   s e t   t o   t h e   b e s t   l i s t   a s   w e l l   a s   t h e   b e s t   f i t n e s s   i s   s e t   t o   t h e   b e s t   fo un s o l ut i o f i t ne s s .   d)   If   f l a g= 0. t h e   i t e r a t i o w i l l   s t o p.   e)   If   f l a g= 1.   E v a l ua t e   t h e   c e n t e r   s o l ut i o n e a r by .     f)   If   t h e   f i t n e s s   o f   m i d   s o l ut i o i s   n o t   b e t t e t ha t o   i t ’s   v e r y   n e a s o l ut i o n.   S e t   t h e   b e s t   f o un s o l ut i o a n d   i t s   s o l ut i o n   t o   t h e   v e r y   n e a o n e .   g)   H a m m i n g   d i s t a n c e   b e t w e e n   t h e   o ut s t a n d i n g   f o un a n d   t h e   v e r y   n e a s o l ut i o n   t o   i t   w i l l   b e   c a l c ul a t e .   h)   If   t h e   o ut s t a n d i n g   f o un s o l ut i o n   s t i l l   b e t t e r   t o   i t s   n e a r by   s o l u t i o n,   go   t o   s t e 4 .   i)   O t h e r w i s e ,   s e t   n e i g h b o r   s o l ut i o t o   t h e   ha m m i ng  d i s t a n c e .   j)   If   b e s t   s o l ut i o f o un go   t o   s t e p   2.   k)   O t h e r w i s e   s e t   c o un t = c o un t + a n d   go   t o   s t e ( t o   e v a l ua t e   t he   r e a m i ng  e xc h a n ge s ).   l)   If   c r i t e r i a   r e a c h e d ,   i t e r a t i o s t o p.   m)   O t h e r w i s e ,   go   t o   s t e p   1.       4.   C O M P U TA TI O N A L   R ES U LTS   In   o r de r   t o   a s s e s s   t h e   e f f i c i e n c y   a n t h e   c a pa b i l i t y   o f   t h e   G ICT A .   T w e n t y   s e v e n   (27)  s y m m e t ri c   b e n c h m a rk   pr o b l e m   h a v e   b e e n   c a r r y   o ut   f r o m   T S P L IB .   B a y s 29,   B e r l i n 52 ,   Ch 150,   E i l 101,   K r o A 100,   K r o A 1 5 0 ,   K r o B 100,   K r o B 150,   K r o C100,   K r o E 100,   a n L i n 105.   M o r e o v e r ,   t o   t a ke   t h e   a v e r a ge   e v e r y   pr o b l e m   h a s   b e e n   e xa m i ne 10  t i m e s .   G e n e t i c   a l go r i t hm   pa r a m e t e rs   c o n s i s t s   o f   t h e   f o l l o w i n g:   P o pul a t i o s i z e = 200,   m ut a t i o pr o b a b i l i t y = 0. 0 1,   c r o s s o v e r   pr o b a b i l i t y = 1,   a n t h e   ge n e r a t i o n = 20 t o   t e r m i na t e .   T o   pr o t e c t   a n t o   m i n i m i z e   t i m e   c o n s um i n c o m put a t i o n ,   t h e   l o c a l   m e t h o o n l y   t e s t e a a ppl i e o n c e   e v e r y   f i f t y   i t e r a t i o n .   In   T a b l e   1 .   i l l us t ra t e s   t h e   n um e r i c a l   r e s ul t   o b t a i n e b y   t h e   pr o po s e a l go r i t hm ,   a n i t   i s   de s c r i b e a s   f o l l o w s :   c o l um n   o n e   i n c l ude   t h e   n a m e   o f   t h e   T S P   pr o b l e m ,   c o l um n   t w o   e xh i b i t   t h e   f a v o r a b l e   o ut c o m e s   f o und  b y   t h e   pl a n ne d   a l go r i t hm   w h i l e   t h e   m e a n   i s   ge t   i n   t h e   t h i rd   c o l um n ,   t h e   c o l um n   f o ur   r e f e r s   t o   t h e   e r r o r   pe r c e n t a g e ,   t h e   f i f t h   a n s i xt h   c o l um n   i n di c a t e d   t h e   s t a n da rd  de v i a t i o n   a s   w e l l   a s   t i m e   e xe c ut i n g.   A s   s h o w n   i n   t a b l e   b e l o w   pr o b l e m s   w i t h   l i m i t e do m a i t h e y   a r e   a ppl i e s   i n   c o n c i s e   t i m e   a n a c h i e v e   t o   t h e   gl o b a l   s o l ut i o n   b y   r e s t r i c t e a n f i n i t e   m o v e s ,   h o w e v e r   pr o b l e m s   h a v e   a   l a r ge   do m a i n   t h e y   w e r e   t o o m uc h   t i m e   ge t   gl o b a l   s o l ut i o n s .   T a b l e   2.   S h o w   t h e   e xe c ut i o n   o f   t h e   t r a di t i o na l   ge n e t i c   a l go r i t h m .   A s   s e e n   t h e   r e s ul t   h a s   b e e n   pl a n t   by   t h e   pl a n n e a l go r i t h m   a r e   m uc h   f a v o r a b l e   c o m pa r e t o   t h e   r e s ul t   o f   t h e   h e ur i s t i c   ge n e t i c   a l go r i t h m   h a v e .     T h i s   i s   pr o v e   t h a t   t h e   pr e s e n t e a l go r i t h m   h a s   b e s t   pe r f o r m a n c e   c o m pa r i n t o   t h e   G A .   T a b l e   de m o n s t r a t e   t h e   b e s t   s o l ut i o n   o b t a i n e b y   l o c a l   s e a r c h   t e c h n i que .   A s   s h o w n   b e l o w   t h e   go t   s o l ut i o n s   a r e   l o c a l   o pt i m a l   s o l ut i o n .   T h e   r e a s o n   f o r   t h a t   i s ,   t h e   l o c a l   s e a r c h   m e t h o c a n n o t   e s c a pe   a n c l i m b   f r o m   t h e   l o c a l   o pt i m a l   s o l ut i o n .   T h a t ’s   w h y   o n l y   l o c a l   t e c h n i que s   n e v e r   r e a c h   t o   t h e   gl o b a l   o pt i m a l   s o l ut i o n.   S o   t h e   pr o po s e a l go r i t h m   t r i e t o   c o v e r   t h i s   i s s ue   a n c o m b i n e t o   t h e   h e ur i s t i c   a l go r i t hm   i n   o r de r   t o   r un   a w a y   f r o m   s t uc k.   In   c o n t r a s t ,   l o c a l   t e c h n i que s   e a s i l y   r e a c h   t o   t h e   l o c a l   o pt i m a l   s o l ut i o n   w i t h o ut   c o n s um i n t i m e .   In   c o m pa r i s o n   t o   t h e   o t h e r   r e s e a r c h e s ,   w e   h a v e   s e e n   n o t   a l l   r e s e a r c h e r s   us e s   t h e   s a m e   i n s t a nc e s   o f   T S P   pr o b l e m s .   m a n y   s c i e n t i s t s   a ppl i e v a r i o us   i n s t a n c e s   o n   t h e i r   a l go r i t h m s .   S o m e   o f   t h e   c o m m o n   pr o b l e m   t e s t e b y   m a n y   o f   t h e m   a r e   B e r l i n 52,   K r o A 100,   a n L i n 105.   A s   w e   n o t i c e d,   t h e   pr o po s e a l go r i t hm   h a v e   b e t t e r   r e s po n c o m pa r i n t o   t h e   o t h e r s   [22 - 25].       T a b l e   1 .   H y b r i d   G e n e t i c   A l go r i t hm   E xpe ri m e nt a l   R e s ul t s   P ro b l e m   [O p t i m a l ]   Be s t     S o l .   A v e ra g e     (M e a n )   E rro r     (% )   ST   D E V   T i m e     (S e c . )   Ba y s 2 9   [2 0 2 0 ]   2020   2 0 4 4 . 8   0   87   131   Be rl i n 5 2   [7 5 4 2 ]   7542   7736   0   19   11   Ch 1 5 0   [6 5 2 8 ]   6879   7019   0 . 0 5   1 8 . 9   2031   E i l 1 0 1   [6 2 9 ]   632   665   0 . 1   5 5 . 6   934   K r o A 1 0 0   [2 1 2 8 2 ]   2 1 7 2 1   2 2 3 2 1   0 . 0 2   312   1377   k ro A 1 5 0   [2 6 5 2 4 ]   2 8 0 8 7   2 8 9 0 0   0 . 0 7   939   2409   k ro B1 0 0   [2 2 1 4 1 ]   2 2 1 7 7   2 2 7 7 3   0 . 0 0 1   371   3127   k ro B1 5 0   [2 6 1 3 0 ]   2 7 4 1 9   2 8 3 4 9   0 . 0 5   965   2257   k ro C1 0 0   [2 0 7 4 9 ]   2 1 1 5 7   2 2 2 0 1   0 . 0 1   641   1372   k ro E 1 0 0   [2 2 0 6 8 ]   2 2 3 2 4   2 2 6 9 7   0 . 0 1 2   321   925   L i n 1 0 5   [1 4 3 7 9 ]   1 4 6 1 1   1 5 0 0 1   0 . 0 3   177   1017     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2502 - 4752   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   18 ,   N o .   2 M a y   20 2 :     1035   -   1 039   1038   T a b l e   2 .   G e n e t i c   A l go r i t hm   E xpe r i m e nt a l   R e s ul t s   P ro b l e m   [O p t i m a l ]   Be s t   S o l .   A v e ra g e   (M e a n )   E rro r   (% )   ST   D E V   T i m e   (S e c . )   Ba y s 2 9   [2 0 2 0 ]   2020   2096   0   46   2 . 5   Be rl i n 5 2   [7 5 4 2 ]   7543   8117   0 . 0 0 0 2   333   21   Ch 1 5 0   [6 5 2 8 ]   7314   7657   0 . 1   194   190   E i l 1 0 1   [6 2 9 ]   685   710   0 . 0 8   17   184   K r o A 1 0 0   [2 1 2 8 2 ]   2 2 5 6 3   2 3 7 3 3   0 . 0 6   924   161   k ro A 1 5 0   [2 6 5 2 4 ]   2 9 2 3 3   3 0 3 3 0   0 . 1   834   821   k ro B1 0 0   [2 2 1 4 1 ]   2 3 6 7 0   2 4 2 4 5   0 . 0 7   512   186   k ro B1 5 0   [2 6 1 3 0 ]   2 9 7 7 1   3 0 9 8 3   0 . 1   701   741   k ro C1 0 0   [2 0 7 4 9 ]   2 2 7 0 9   2 3 6 6 9   0 . 9   682   183   k ro E 1 0 0   [2 2 0 6 8 ]   2 3 5 3 4   2 4 4 4 3   0 . 0 7   739   191   L i n 1 0 5   [1 4 3 7 9 ]   1 4 6 3 1   1 5 6 7 5   0 . 0 1   511   222       T a b l e   3 .   L o c a l   S e a r c A l go r i t hm   E xpe r i m e nt a l   R e s ul t s   P ro b l e m   [O p t i m a l ]   Be s t   S o l .   A v e ra g e   (M e a n )   E rro r   (% )   ST   D E V   T i m e   (S e c . )   Ba y s 2 9   [2 0 2 0 ]   2153   2305   0 . 0 6   86   2 . 7   Be rl i n 5 2   [7 5 4 2 ]   8035   8862   0 . 0 6   445   5 . 7   Ch 1 5 0   [6 5 2 8 ]   9398   9803   0 . 4   215   27   E i l 1 0 1   [6 2 9 ]   715   752   0 . 1   215   14   K r o A 1 0 0   [2 1 2 8 2 ]   2 7 5 8 5   3 0 1 9 3   0 . 3   1306   15   k ro A 1 5 0   [2 6 5 2 4 ]   3 8 2 7 3   4 1 3 0 3   0 . 4 5   1565   29   k ro B1 0 0   [2 2 1 4 1 ]   2 8 1 0 7   3 1 0 0 3   0 . 3   1315   25   k ro B1 5 0   [2 6 1 3 0 ]   3 7 8 5 5   4 1 3 7 5   0 . 4 6   2525   29   k ro C1 0 0   [2 0 7 4 9 ]   2 7 2 5 0   2 9 7 2 9   0 . 3   1605   14   k ro E 1 0 0   [2 2 0 6 8 ]   2 8 9 9 1   3 0 0 6 5   0 . 3   745   24   L i n 1 0 5   [1 4 3 7 9 ]   2 0 1 7 0   2 1 8 4 0   0 . 4   1190   14       5.   C O N C LU S I O N     T o   c o n c l ude   t h i s   pa pe r,   a   h y b r i ge n e t i c   a l go ri t hm   ( i n t e g ra t i o n   o f   bo t h   l o c a l   t e c hni que   a nd  h e u ri s t i c   G A t e s t e d   t o   t h e   s y m m e t r i c   E uc l i de a t ra v e l i n g   s a l e s m a p r o b l e m .   By   c o m pa r i ng   t o   t h e   t ra di t i o na l   ge n e t i c   a l go ri t hm   e xpe ri m e n t a l   s h o w s   t h e   p r o po s e a l go ri t hm   h a s   a   b e t t e r e s po n s e   a s   w e l l   a s   i t s   i m p r o v e t h e   pe r f o r m a n c e   b y   m a ki ng  t h e m   t o   de s e rt i o f r o m   t h e   r e gi o n a l   o l o c a l   f a v o r a b l e   a n d   s e a r c f o r   t h e   m o s t   f a v o r a b l e   o r   n e a t o   i t ,   a nd  s h o w s   t ha t   i t ’s   ha s   e xc e l l e n t   e xe c ut i o n   f o r   a   c e r t a i n   s c o pe .         R EF ER EN C ES     [ 1]   E .   O s a b a ,   R .   C a r b a l l e do ,   F .   D i a z ,   a nd   A .   P e r a l l o s ,   A na l y s i s   o f   t h e   s ui t a b i l i t y   of   us i ng   bl i nd   c r o s s o v e r   o pe r a t o r s   i n   g e ne t i c   a l g o r i t hm s   f o r   s o l v i ng   r o uni ng   p r o bl e m s .   I E E E   I nt e r n at i ona l   Sy m p os i um   on   A p pl i e C om pu t at i on al   I nt e l l i ge nc e   and   I nf or m a t i c s 2013 ,   pp .   17 - 22 .   [ 2]   P .   C ha ng ,   W .   H ua ng ,   C .   T i ng ,   a nd   W .   C ha ng ,   A   v ar i e t al   ge ne t i c   a l g or i t hm   by   e x t e r na l   s e l f - e v o l v i ng   m ul t i pl e - a r c h i v e s   f or   c om b i na t o r i a l   o pt i m i z a t i o p r ob l e m s .   P r o c e e di ng s   o f   t he   11t h   I E E E   I nt e r na t i o na l   C o nf e r e nc e   o H i g P e r f o r m a nc e   C o m put i ng   a nd  C o m m uni c a t i o ns ,   200 9,   pp .   609 - 61 4.   [ 3]   Al - O ba i di ,   A .   T .   S . ,   A bdu l l a h,   H .   S . ,   &   A hm e d ,   Z .   O .   M e e r ka t   c l a a l g o r i t hm :   A   ne w   s w a r m   i nt e l l i g e nc e   a l g o r i t hm .   I nd one s i an  J ou r na l   of   E l e c t r i c al   E ng i ne e r i ng   a nd  C om p ut e r   S c i e nc e ,   2 018 ,   pp.   3 54 - 360 .   [ 4]   S .   S h ubh r a ,   B .   S a ng ha m i t r a ,   a nd   K .   S a nk a r .   N e w   O pe r at or s   of   G e ne t i c   A l go r i t hm s   f or   T r a v e l i n Sa l e s m an  P r o bl e m .   I nt e r na t i o na l   C o nf e r e nc e   o P a t t e r R e c o g ni t i o n,   2004 ,   pp .   497 - 500 .   [ 5]   J .   G r e f e ns t e t t e ,   R .   G o pa l ,   B .   R o s i m a i t a ,   a nd   D .   G uc ht ,   G e ne t i c   A l gor i t hm s   f or   t he   T r av e l i ng   Sal e s m a P r ob l e m .   P r o c .   I nt .   C o nf .   G e ne t i c   A l g o r i t hm s   a nd   T he i r   A ppl i c a t i o ns ,   J u l y   1985,   pp .   160 - 16 8.   [ 6]   S .   K i r kpa t r i c k,   J r .   G e l a t t ,   a n M .   V e c c hi ,   O pt i m i z a t i o by   S i m ul a t e A nne a l i ng .   S c i e nc e ,   1983 ,   498 - 51 6.     [ 7]   I n gg i P . ,   N e s d i   E . ,   F a dh i l a h   S . ,   &   F e b i   N u r   S a l i s a h .   O pt i m i z a t i o L e a r n i ng   V e c t o r   Q u a n t i z a t i o n   U s i ng   G e ne t i c   A l go r i t hm   f o r   D e t e c t i o o f   D i a be t i c s .   I nd one s i an  J our na l   o f   E l e c t r i c a l   E ngi ne e r i ng  a nd  C om pu t e r   Sc i e nc e ,   2018 ,   pp.   11 11 - 1116 .   [ 8]   J .   K e nn e dy   a nd  R .   E be r ha r t ,   P ar t i c l e   s w ar m   op t i m i z at i on .   P r o c e e di ng s   o f   I E E E   I nt e r n a t i o na l   C o nf e r e nc e   o N e u r a l   N e t w o r ks ,   1995 ,   pp .   194 2 - 1948 .   [ 9]   F .   G l o v e r ,   T a bu  S e a r c h,   P a r t   I .   O R SA   J our nal   o C om put i n g ,   19 8 9,   pp .   190 - 206 .   [ 10]   E e s a ,   A .   S . ,   O r m a n,   Z . ,   &   B r i f c a ni ,   A .   M .   A .   A   n e w   f e a t u r e   s e l e c t i o m o de l   b a s e d   o I D a nd  be e s   a l g o r i t hm   f o r   i nt r u s i o de t e c t i o n   s y s t e m .   T u r k i s h   J our nal   o f   E l e c t r i c a l   E ngi ne e r i ng  &   C om pu t e r   S c i e nc e s ,   2015 ,   pp .   615 - 622 .   [ 11]   S .   J a y a l a ks hm i ,   R .   A s w i ni .   A   N o v e l   O pt i m i z a t i o A l g o r i t hm   B a s e o S t i ng i ng   B e ha v i o r   o f   B e e .   I A E S   I nt e r n at i on al   J o ur n al   o f   A r t i f i c i a l   I n t e l l i ge nc e   ( I J - A I ) ,   2018 ,   pp .   15 3 - 164.     Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752       A e nhan c e h y br i g e ne t i c   al gor i t hm   f or   s ol v i ng   t r a v e l i ng   s al e s m an   pr obl e m   ( Z e r av an  A r i f   A l i )   1039   [ 12]   D .   P h a m ,   a n T .   H uy nh,   a E f f e c t i v e   C om bi na t i o o f   G e ne t i c   A l g o r i t hm s   and   t he   V a r i a bl e   N e i g hbor hood   Se ar c f o r   Sol v i n T r av e l l i ng   Sa l e s m an  P r ob l e m .   I E E E   C o nf e r e nc e   o T e c hn o l og i e s   a n A ppl i c a t i o ns   o f   A r t i f i c i a l   I nt e l l i g e nc e 2015 ,   pp.   1 42 - 149 .   [ 13]   D .   Z v i ,   T a bu   S e a r c a nd   H y br i d   G e ne t i c   A l g o r i t hm s   f o r   Q ua dr a t i c   A s s i g nm e n t   P r o b l e m s .   E u r ope an   J our na l   of   O pe r at i ona l   R e s e ar c h ,   2 008 ,   pp.   90 - 107 .   [ 14]   D .   Z e e ba r e e ,   H .   H a r o n,   A .   M uh s i n ,   a nd   S .   Z e e ba r e e .   C o m bi na t i o o f   K - m e a n s   c l us t e r i ng   w i t h   G e ne t i c   A l g o r i t hm :     A   r e v i e w .   I n t e r nat i on al   J our n al   o f   A pp l i e E ng i ne e r i ng   R e s e ar c h ,   201 7,   pp .   142 38 - 1424 5.   [ 15]   X i ng w a ng   H . ,   X u e w e n   Z . ,   R u i   H . ,   &   X W .   A e nha nc e hy br i di z e a r t i f i c i a l   be e   c o l o n y   a l g o r i t hm   f o r   o pt i m i z a t i o pr o bl e m s .   I A E S   I n t e r na t i ona l   J ou r na l   of   A r t i f i c i al   I nt e l l i ge nc e   ( I J - A I ) ,   2019 ,   pp .   87 - 94 .     [ 16]   J .   P o t v i n,   T he   T r a v e l i ng   S a l e s m a P r o bl e m :   A   N e ur a l   N e t w o r P e r s p e c t i v e .   O R SA   J .   C om p ut .   1993 ,   pp .   328 - 348 .     [ 17]   ht t p: / / e l i b . z i b . de / pu b/ m p - t e s t da t a / t s p / t s p l i b / t s p / i nde x . h t m l .   [ 18]   A r a na na y a kg i ,   R e duc e   T o t a l   D i s t a nc e   a nd   T i m e   U s i ng   G e ne t i c   A l go r i t hm .   I n t e r na t i ona l   J o ur na l   o f   C om pu t e r   Sc i e nc e   a nd   E ng i ne e r i ng   T e c hno l o gy ,   2 014 ,   pp .   8 15 - 819 .   [ 19]   J .   H o l l a nd ,   A da p t a t i o n   i n   N a t ur a l   a nd   A r t i f i c i a l   S y s t e m s :   A I nt r o duc t o r y   A na l y s i s   w i t h   A ppl i c a t i o ns   t o   B i o l o gy ,   C o nt r o l ,   a n A r t i f i c i a l   I nt e l l i g e nc e .   U n i v e r s i t y   M i c hi g a P r e s s ,   A n A r bo r ,   M I ,   U S A ,   1975 .   [ 20]   E e s a ,   A .   S . ,   O r m a n,   Z . ,   &   B r i f c a ni ,   A .   M .   A .   A   no v e l   f e a t u r e - s e l e c t i o a pp r o a c ba s e o t h e   c ut t l e f i s h   o pt i m i z a t i o a l g o r i t hm   f o r   i nt r us i o d e t e c t i o s y s t e m s .   E x pe r t   Sy s t e m s   w i t h   A p pl i c a t i o ns ,   2015 ,   pp .   2670 - 26 79 .   [ 21]   S ur a khi ,   O . ,   K h a na f s e h,   M . ,   &   J a f f a l ,   Y .   A e nh a nc e d   B i o m e t r i c - ba s e d   F a c e   R e c o g ni t i o S y s t e m   us i ng   G e ne t i c   a nd  C R O   A l g o r i t hm s . "   [ 22]   Y .   D e ng ,   Y .   L i u ,   a nd   D .   Z ho u A I m pr ov e G e ne t i c   A l g o r i t hm   w i t I ni t i a l   P o pul a t i o S t r a t e g y   f o r   S y m m e t r i c   T S P .   M a t he m at i c a l   P r ob l e m s   i n   E ng i ne e r i ng ,   201 5,   pp .   791 - 79 7.   [ 23]   P .   C ha nn ,   W .   H s i u ,   C .   J ung D y na m i c   di v e r s i t y   c o nt r o l   i n   g e ne t i c   a l g o r i t hm   f o r   m i ni ng   un s e a r c he d   s o l ut i o n   s p a c e   i T S P   pr o bl e m s .   E x pe r t   S y s t e m s   w i t A ppl i c at i on s ,   20 10 ,   p p.   18 6 3 - 1878.   [ 24]   F . H a n i f ,   N .   K ha n ,   S .   I na y a t ul l a h ,   &   S .   T a j ud di n.   S o l v i ng   T S P   P r o bl e m   by   U s i ng   G e ne t i c   A l go r i t hm .   I n t e r na t i ona l   J our nal   o f   B as i c   &   A ppl i e S c i e nc e s ,   2009 .   [ 25]   Y .   Y u,   Y .   C he a nd   T .   L i .   A   N e w   D e s i g o f   G e n e t i c   A l g o r i t hm   f o r   S o l v i ng   T S P .   20 11   F our t h   I n t e r na t i ona l   J o i n t   C onf e r e nc e   on   C om p ut a t i ona l   Sc i e nc e s   a nd   O pt i m i z a t i o n ,   20 11 ,   p p.   309 - 31 3.     Evaluation Warning : The document was created with Spire.PDF for Python.