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 .   14 ,   N o .   1 A p r i l   201 9 ,   p p.   14 3 ~ 1 5 4   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 1 4 .i 1 . pp 14 3 - 1 5 4             143       Jou r n al   h o m e pa ge ht t p: / / i ae s c or e . c om / j our na l s / i nde x . php/ i j e e c s   Im p r o v e d   h u n t i n g   se a r c h   a l g o r i t h m   f o r   t h e   q u a d r a t i c   a ssi g n m e n t   p r o b l e m       A m i n e   A gh ar gh o r ,   M o h amm e d   Es s ai d   R i ffi ,   F ay ç al   C h e b i h i   L a r o s e r i   L a bo r a t o r y ,   D e pa r t m e nt   o f   C o m put e r   S c i e nc e s ,   F a c ul t y   o f   S c i e nc e s ,   U n i v e r s i t y   of   C ho ua i b   D o ukka l i ,   E l   J a d i da ,   M o r o c c o       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 M a y   1,   2 018   R e v i s e A ug   10,   2018   A c c e pt e D e c   25,   2 018     N o w a da y s ,   t he   m e t a h e u r i s t i c s   a r e   t he   m o s t   s t ud i e m e t ho ds   u s e t o   s o l v e   t he   ha r o pt i m i z a t i o pr o bl e m s .   H u nt i ng   S e a r c a l g o r i t hm   i s   a   m e t a he u r i s t i c   i ns p i r e by   t he   m e t ho o f   g r o up  hunt i ng   o f   pr e da t o r y   a ni m a l s   l i k e   w o l v e s .   C r e a t e f o r   s o l v i ng   c o nt i nuo us   o pt i m i z a t i o pr o bl e m s ,   r e c e nt l y ,   i t   i s   a da pt e a nd  e v a l ua t e t o   s o l v e   h a r d   c o m bi na t o r i a l   o pt i m i z a t i o pr o bl e m s .   T hi s   pa p e r   pr o po s e s   a i m pr o v e hu nt i ng   s e a r c a l g o r i t hm   t o   s o l v e   t he   qua d r a t i c   a s s i g nm e nt   pr o bl e m .   N o   l o c a l   s e a r c m e t ho i s   u s e d .   T o   e v a l u a t e   t h e   pe r f o r m a nc e s   o f   t hi s   w o r k,   t he   i m p r o v e H unt i ng   S e a r c i s   c he c ke o a   s e t   o f   36  i ns t a nc e s   o f   Q A P L i a n i t   o ut pe r f o r m s   t he   r e s ul t s   o bt a i n e by   t he   w e l l - kno w n   m e t a he ur i s t i c s .       Ke y w or d s :   Co m b i n a t o r i a l   o pt i m i z a t i o pr o b l e m   H un t i n g   s e a r c h   a l go r i t hm   M e t a h e uri s t i c   Q A P L i b   Q ua d r a t i c   a s s i g nm e nt   p r o b l e m   C opy r i gh t   ©   201 9   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 :   A m i n e   A g ha r g h o r ,   L a r o s e r i   L a b o r a t o r y ,   D e pa rt m e n t   o f   Co m put e S c i e n c e s ,     F a c ul t y   of   S c i e n c e s ,   U n i v e r s i t y   of   Ch o ua i b ,   D o ukka l i ,   E l   J a d i da ,   M o r o c c o .   E m a i l :   a m i n e . a g ha r g h o r@ g m a i l . c o m       1.   I N TR O D U C TI O N     M e t a h e uri s t i c s   a r e   t h e   b e s t   a l go ri t hm s   us e t o   s o l v e   t he   N P - H a r o pt i m i z a t i o n   p r o b l e m s   fo r     w h i c t h e r e   i s   n o   e xa c t   e ff e c t i v e   kn o w n   m e t h o d.   S o m e t i m e s ,   t h e y   c a n   b e   t h e   o nl y   pos s i b l e   m e t h o ds   t o   f i n d   a   go o s o l ut i o n   t o   t h e s e   h a r d   p r o b l e m s .   T h e   m o s t   i m po rt a nt   a dv a n t a ge   o f   us i ng  a   m e t a h e u ri s t i c   i s   t ha t   i t   us e s   a   hi g h   a b s t ra c t i o n   l e v e l .   T h e r e f o r e ,   i t   c a n   b e   a ppl i e t o   w i de   di ff e r e n t   p r o b l e m s .   N e w   m e t a h e uri s t i c s   a r e   pr o po s e r e c e n t l y   s uc h   a s   t h e   h u n t i n s e a r c h   [1] ,   t h e   c hi c ke n   s w a rm   o pt i m i z a t i o n   [2 ] ,   [ 3]  a n t h e   go l de n   b a l l   a l go ri t hm   [4] .     H un t i n S e a r c h   (H uS i s   a   de v e l o pe m e t a h e u ri s t i c   f o r   s o l v i n c o nt i n uo us   o pt i m i z a t i o n   p r o b l e m s .   It   s t a r t s   t o   b e   a da pt e t o   s o l ve   c o m b i na t o ri a l   o pt i m i z a t i o n   p r o b l e m s   s uc h   a s   T h e   T ra v e l i n S a l e s m a n   P r o b l e m   [ 5 ] ,   [ 6 a n t h e   n o - w a i t   f l ow   s h o s c h e dul i n [ 7 ].   It   i s   a l s o   p r o po s e a s   a   f i r s t   a d a pt a t i o f o r   t h e   Q ua d ra t i c   A s s i gnm e n t   P r o b l e m   [ 8 ].   H uS   i s   a   m e t h o i n s p i r e by   gr oup  h u nt i ng  o f   s o m e   a ni m a l s   s uc h   a s   w o l ve s   t h a t   o r ga ni z e   t h e i r   po s i t i o n   t o   s urr o u n d   t h e   p r e y .   E a c h   o f   t h e m   i s   r e l a t i v e   t o   t h e   po s i t i o o f   o t h e r s   a nd  e s pe c i a l l y   i n   r e l a t i o t o   t h e   po s i t i o o f   t h e i l e a de r.   Q ua d r a t i c   A s s i g nm e n t   P r o b l e m   (Q A P [ 9 i s   t h e   w e l l - kn o w di s c r e t e   o pt i m i z a t i o n   p r o b l e m   of   t h e   c a t e go r y   of   t h e   f a c i l i t i e s   l o c a t i o n   pr o b l e m s   N P - h a r d .   T h e   p r o b l e m   i s   t a s s i gn   a   s e t   of   f a c i l i t i e s   t o   a   s e t   o l o c a t i o n s   i n   o r de t o   m i ni m i z e   t h e   t o t a l   c o s t   of   a s s i gnm e nt s .   T h e   Q A P   ha s   s e v e r a l   a p pl i c a t i o n s   i c o m b i na t o ri a l   o pt i m i z a t i o p r o b l e m s   s uc h   a s   B a c kbo a r d   W i ri n [ 10 a n s c h e dul i n [ 11 ].   I n   o r de t o   s o l ve   t h e   Q A P ,   s e ve r a l   m e t a h e u ri s t i c s   ha v e   b e e n   pr o po s e [ 12 ].   T h e   p r e s e n t   pa pe r   p r o po s e s   a n   Im p r o v e H un t i n g   S e a r c h   a l go ri t hm   (IH uS a d a pt e a s   a   c o m b i na t o r i a l   o pt i m i z a t i o n   m e t h o t o   s o l ve   t h e   Q A P   i n   a   m i ni m um   CP U   r u t i m e .   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 .   14 ,   N o .   1 A p r i l   20 19   :     14 3     1 5 4   144   T h i s   p a pe r   i s   d i v i de i nt o   s i m a i s e c t i o n s .   T h e   f i r s t   o n e   i s   a n   i nt r o duc t i o n   o f   t h e   gi v e n   m e t h o a n d   t h e   b e n c h m a r p r o b l e m .   T h e   s e c o n s e c t i o n   pr e s e nt s   t h e   m e t a h e u r i s t i c   H uS .   T h e   t hi r s e c t i o n   p r o v i de s   a   de t a i l e d   de s c r i p t i o o f   t h e   Q A P .   T h e   f o ur t s e c t i o n   p r e s e nt s   t h e   p r o po s e a da pt a t i o a n d   i m p r o v e m e n t   o H uS   fo r   t h e   Q A P .   N um e r i c a l   r e s ul t s   o b t a i n e by   t h e   us e   of   I H uS   o n   t h e   Q A P L i b   i n s t a n c e s   [1 3 a r e   de m o n s t r a t e i n   t h e   f i v e   s e c t i o n ,   a n t h e   l a s t   s e c t i o n   c o n c l u d e s   t h e   w h o l e   w o r k.       2.   H U N TI N G   S EA R C H   A LG O R I TH M   H un t i n S e a r c h   a l go r i t hm   i s   a n   e vo l ut i o na r y   m e t h o i n s pi r e by   c o o p e r a t i v e   h unt i ng  of   s o m e   c a rni v o r e s   t h a t   h u nt   b i gge r   a n d   f a s t e p r e y s   t ha t h e m s e l v e s   w i t h   f e w e r   e n e r gy .   It   i s   a   po pul a t i o n - b a s e s t o c h a s t i c   m e t a h e uri s t i c .   T h e   po pul a t i o n   i s   t h e   h u nt i n g r o up  t h a t   c o n t a i n s   a   s e t   of   s o l ut i o n s   o t h e   s t udi e pr o b l e m ;   e a c h   h u nt e r   r e p r e s e n t s   a   s o l ut i o n.   T h e   l e a de r   r e p r e s e n t s   t h e   b e s t   s o l ut i o n   de f i n e by   a o b j e c t i ve   f un c t i o n.   A   h u nt e i s   c ha ra c t e ri z e b y   i t s   po s i t i o t ha t   de f i n e s   t h e   d i s t a n c e   b e t w e e n   i t   a n d   t h e   o t h e r   hu n t e r s .   T h e   h u nt i ng  p r o c e s s   i n   n a t u r e   r e p r e s e nt s   t h e   s e a r c h   o f   o pt i m um   i n   t h e   a l go ri t hm .   T h e   m o v e m e n t s   of  t h e   h u nt e r s   t o   e n c i r c l e   t h e   p r e y   r e pr e s e n t s   t h e   o pe ra t i o n s   o f   i m p r o v e m e n t   o f   t h e   i ni t i a l   s o l ut i o n s .   H un t e r s   do   t hr e e   m a i m o v e m e n t s .   T w o   m ov e m e n t s   o f   i n t e n s i f i c a t i o n   o pe r a t i o n s .   T h e s e   a r e   t h e   m o v e m e n t   t o w a r t h e   l e a de r   a n t h e   m o v e m e n t   t o w a r t h e   o t h e r   h u nt e r s .   T he   t hi r o n e   i s   a   d i v e r s i f i c a t i o o pe r a t i o n   t h e   r e o r g a n i z a t i o o f   t h e   hu n t e r s   w h e t h e y   b e c o m e   ve r y   c l o s e   t o   e a c h   o t h e r .   H uS   a l go r i t h m   i s   p r e s e nt e i n   F i gu r e   1:   -   HG   ( H u n t i n g   G r o up)   i s   t h e   po pul a t i o n   o f   hu n t e r s   us e f o r   t he   s e a r c h   o f   t h e   o pt i m um .   -   NE   ( N u m b e r   o f   E po c h s )   i s   t h e   n u m b e r   o f   l o o ps   t o   m a ke   f o r   t h e   s e a r c h .   -   IE   ( I t e r a t i o pe r   E po c h )   i s   t h e   n u m b e r   o f   t i m e s   pe e po c h   w h e r e   h u nt e r s   m a ke   a   m o v e .           F i gu r e   1 .   F l o w c h a r t   o f   h u nt i n g   s e a r c h   a l go r i t hm       T h e   m a i o pe ra t i o n s   o f   H uS   a r e :   a)   Ini t i a l i z e   t h e   H unt i ng  G r o up :   ge n e ra t e   a   s e t   o f   r a ndo m   s o l ut i o n s   f o r   a   p r o b l e m ;   e a c h   hu n t e r   r e p r e s e nt s   a   s o l ut i o n .   b)   M ov i n T o w a r t h e   L e a de r :   h u nt e r s   m o ve   t ow a r t h e   l e a de r,   w h i c h   m a ke s   t h e m   s t a y   c l o s e r   t o   t h e   l e a de r   unt i l   f i n d i n a   b e t t e r   s o l ut i o a n d   b e c o m i n t h e   n e w   l e a de r.   c)   Co o p e r a t i o a m o n g   H unt e r s :   e a c h   hu n t e r   m o v e s   t ow a r t h e   o t h e h u nt e r s   o j us t   m a ke s   a   ra n do m   m o v e .   No   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       Im pr ov e d   hun t i n s e ar c h   al gor i t hm   f or   t he   quadr a t i c   a s s i gn m e nt   pr obl e m   ( A m i ne   A g har ghor )   145   d)   R e o r ga n i z a t i o n   o f   h u nt e r s :   a t   s o m e   po i nt ,   h u nt e r s   b e c o m e   v e r y   c l o s e   t o   e a c h   o t h e r ,   w h i c m e a n s   t ha t   t h e y   r e p r e s e n t   a l m o s t   t h e   s a m e   s o l ut i o n .   I t hi s   c a s e ,   t h e y   h a v e   t o   b e   r e ge n e ra t e d ,   e xc e pt   t h e   l e a de r.       3.   Q U A D R A TI C   A S S I G N M EN P R O BLE M     3. 1 .       D e fi n i ti o n   Q A P   i s   a   c o m b i n a t o r i a l   o pt i m i z a t i o n   p r o b l e m   o f   t h e   c l a s s   N P - H a r w h o s e   c o m put a t i o n a l   c o m pl e xi t y   i n c r e a s e s   e xpo n e n t i a l l y   by   i n c r e a s i n t h e   n um b e r   o f   f a c i l i t i e s .   N o   e xa c t   m e t h o c a n   s o l v e   t h e   pr o b l e m   w h e n   t h e   n u m b e r   o f   f a c i l i t i e s   i s   uppe t h e t w e n t y .   G i v e n   a   s e t   of   f a c i l i t i e s   t o   a s s i gn   t o   a   s e t   o f   l o c a t i o n s ,   t h e re   i s   a   r e qui r e f l o w   be t w e e n   e v e r y   t w f a c i l i t i e s   a n a   r e qu i r e di s t a n c e   be t w e e n   e v e r y   t w o   l oc a t i o ns .   T h e   pr o b l e m   i s   t o   f i n t h e   b e s t   a s s i gn m e n t   o t h e   f a c i l i t i e s   t o   t h e   l o c a t i o n s   t o   ha v e   t h e   m i n i m u m   t o t a l   c o s t   of   f l ow s   a n d i s t a n c e s .   F i gu r e   i s   a n   e xa m p l e   o f   a s s i gn m e n t   o f   t hr e e   f a c i l i t i e s   t o   t hr e e   l o c a t i o n s .   D1   a n D2   a r e   t h e   di s t a n c e s   b e t w e e n   t h e   l o c a t i o n s ,   a n d   F1   a nd  F2   a r e   t h e   f l o w s   b e t w e e n   t h e   f a c i l i t i e s .           F i g u r e   2 .   A s s i g nm e n t   o f   t hr e e   f a c i l i t i e s       T h e   o pt i m a l   s o l ut i o i s   de f i n e b y   a n   o b j e c t i ve   f un c t i o n   f r o m   a   d i s c r e t e   s ub s e t   of   t h e   f e a s i b l e   s o l ut i o n s .   L e t   E   b e   t h e   s e t   o f   t h e   f e a s i b l e   s o l ut i o n s ;   S   i s   a   s ub s e t   of   E ;   a n :     i s   t h e   o b j e c t i ve   f un c t i o n.   T h e   p r o b l e m   i s   t o   f i n d :     mi n { ( ) }     ( 1 )       W h e r e   s   i s   a   s o l ut i o n   f r o m   S .   I t   i s   a   v e c t o r   of   ,   w h i c h   c o n t a i n s   i nde xe s   of   f a c i l i t i e s   a s s i g n e r e s pe c t i v e l y   t l o c a t i o n s   1 ,   2, …, n.   n   i s   t h e   n u m b e r   o f   t h e   l o c a t i o n s .     T h e   o b j e c t i ve   f un c t i o n   gi v e s   t h e   c o s t   o f   t h e   a s s i g n m e n t ,   de f i n e a s   f o l l o w s :     ( ) =   ( ) ( ) ×    = 1 = 1   ( 2)       W h e r e   (  )     a n d   (  )     a r e   t w o   m a t r i c e s .   (  )   i s   t h e   s qua r e   m a t r i x   t ha t   r e p r e s e n t s   t h e   r e qu i r e f l ow   b e t w e e n   f a c i l i t y   i   a n d   j (  )   i s   t h e   s qua r e   m a t r i t h a t   r e p r e s e nt s   t h e   d i s t a n c e   b e t w e e n   l o c a t i o a n d   j .     s     S ,   s ( i )   i s   t h e   l o c a t i o t o   w hi c f a c i l i t y   i   i s   a s s i g n e a n d   n   i s   t h e   di m e n s i o n   o f   t h e   t w o   m a t r i c e s .       4.   I M P R O V ED   H U N TI N G   S EA R C H   A LG O R I TH M     H uS   a s   a   m e t a h e u ri s t i c s   us e s   i n t e n s i f i c a t i o n   a n d i v e r s i f i c a t i o n   o pe ra t i o n s .   T h e   m o ve   t ow a r ds   t h e   l e a de r   a n d   t h e   c o o p e r a t i o n   a m o n hu n t e r s   a r e   t h e   i nt e n s i f i c a t i o n   o pe r a t i o n s ;   a n t h e   r e o r ga ni z a t i o n   o f   h u nt e r s   i s   t h e   di v e r s i f i c a t i o n   o pe r a t i o n.   H uS   us e s   a l s a   po pul a t i o of  i n d i v i dua l s   (t h e   h u nt e r s i n   t h e   s e a r c h   s pa c e   t h a t   u nde r go e s   m u t a t i o o pe r a t i o n s .   It   i s   a e v o l ut i o n a r y   a l g o r i t hm .     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 .   14 ,   N o .   1 A p r i l   20 19   :     14 3     1 5 4   146   4. 1     A d ap tat i o n   4. 1 . 1   I n i t i al i z e   th e   h u n ti n g r o u p   T o   r e p r e s e n t   a   s o l ut i o n   o f   Q A P   i n   a   p r o g r a m ,   a n   a rra y   o f   i nt e ge r   i s   us e d,   w h e r e   t h e   a rra y   i n de xe s   r e f e r   t o   t h e   l o c a t i o n s   r e s pe c t i v e l y   1,   2,   ,   n   ( n   i s   t h e   num b e r   of   l oc a t i o n s a nd  t h e   a rra y   c o n t e nt s   r e f e r   t o   f a c i l i t i e s   a s s i g n e t o   e a c h   l o c a t i o n .   F i gu r e   i s   a n   e xa m pl e   of  a   Q A P   s o l ut i o n   t h a t   r e p r e s e n t s   a n   a s s i g nm e n t   o f i ve   f a c i l i t i e s   t o   f i v e   l o c a t i o n s ;   t h e   s o l ut i o i s   r e p r e s e nt e by   a   h u nt e r .   In   t h i s   f i r s t   s t e p,   a   s e t   o f   r a n do m   s o l ut i o n s   c a l l e t h e   H un t i n G r o up  (H G i s   c r e a t e d.   E a c h   s o l ut i o n   i s   r e pr e s e nt e by   a   h u nt e r   a nd  t h e   s i z e   o f   t h e   s e t   o f   s o l ut i o n s   i s   c a l l e t h e   H un t i n G r o up  S i z e   (H G S ).     F i gu r e   4   i s   a e xa m pl e   o f   a   H G   o f   H G S = 3.           F i g u r e   3 .   A e xa m pl e   o f   a n   a s s i g nm e n t   f a c i l i t i e s   s o l ut i o n     F i gu r e   4 .   A e xa m pl e   o f   a   H G   i ni t i a l i z a t i o n       4. 1 . 2   Th e   m o v e m e n ts   o h u n te r   T h e   o n l y   pos s i b l e   r e pr e s e n t a t i o n   o t h e   m o v e m e n t   of   a   gi v e n   h u n t e r   i n   t h e   p r o gr a m   i s   t h e   pe r m ut a t i o n   o f   t w o   of   i t s   a rra y   c o n t e nt s .   T h e   a l go ri t hm   i s   us e t de f i n e   t h e   s t ra t e gy   a n t h e   s i z e s   of  pe r m ut a t i o n s   t o   do .   T h e r e f o r e ,   a   m o v e m e n t   o f   a   h u n t e i s   e qu a l   t o   a   pe r m u t a t i o a s   i t   i s   s h o w n   i (3 ).       1    =   1       (3)       T h e   m o ve m e n t   o f   a   h unt e r   H i   t ow a r a n o t h e r   h u nt e r   H j   i s   a l s o   a   p e r m u t a t i o n   i n   a   gi v e n   a rra y   i n de k .   O n e   s e a r c h   f o r   t h e   l o c a t i o n   o t h e   c o n t e n t   a rra y   i n   H i   t h a t   i s   s i m i l a r   t o   t h e   c o n t e n t   o a rra y   H j   i n   t h e   a rr a y   i n de k   a n pe rm ut e   t h e m   i n   H i   a s   i t   s h o w n   i n   (4) H i   i s   t h e   u pda t e hu n t e r   a n H j   i s   f r o m   w h i c h   t h e   upd a t e   i s   i n s pi r e d.     1    ( , , ) = 1    ( , , )   ( 4 )       F i gu r e   5   i s   a e xa m pl e   o f   m o ve m e n t   o f   t h e   hu n t e r   H 1   t o w a r t h e   hu n t e r   H 3   i t h e   a rra y   i n de k =2 .           F i gu r e   5 .   A e xa m pl e   o f   a   m o v e m e n t   t o w a r d   a   h u nt e r       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       Im pr ov e d   hun t i n s e ar c h   al gor i t hm   f or   t he   quadr a t i c   a s s i gn m e nt   pr obl e m   ( A m i ne   A g har ghor )   147   4. 1 . M o v i n to w ar d s   th e   l e ad e r   A f t e r   t h e   i n i t i a l i z a t i o n   o t h e   H G   s t a r t s   t h e   l o o of   t h e   N E   i t e ra t i o n s .   I n   t hi s   l o o p   s t a rt s   t h e   s e c o n l o o of   IE   i t e ra t i o n s ,   w h e r e   c o m e s   t h e   m o ve   t ow a r ds   t h e   l e a de r   (M T L ).   I n   t h i s   s t e p,   e a c h   h u nt e r   m o v e s   t o w a r t h e   l e a de r   by   c o p y i n a   pa rt   f r o m   t h e   b e s t   s o l ut i on;   t h e   s i z e   of  t h e   m o ve m e n t   t o w a r ds   t h e   l e a de (S M L w h i c i s   t h e   s i z e   o f   t h e   c o pi e pa rt   i s   c a l c u l a t e d   a s   f o l l o w s :     =       ×    × ( , )   (5)       W h e r e :   -   R a n i s   a   u ni f o r m   r a ndo m   n u m b e r   t h a t   v a ri e s   b e t w e e n   a nd  1 .   -   M M L   (M a xi m um   M o v e m e n t   t ow a r t h e   L e a de r i s   a   n u m b e r   b e t w e e n   a n r e pr e s e nt i n t h e   m a x i m u m   c l o s e r   r a t e   o f   a   h u nt e t o   t h e   l e a de r .   -   F u n c t i o D   r e f e r s   t o   t h e   di s t a n c e   b e t w e e n   t w o   h u nt e r s .   It   i s   t h e   n u m b e r   o f   t h e   di f f e r e n t   a s s i g n m e nt s   i t h e   t w o   r e p r e s e n t e s o l ut i o n s .   H L   i s   t h e   l e a de a nd  H i   i s   t h e   h u n t e n u m b e r   i .     E a c h   m o v e m e n t   t o w a r a   l e a de r   (M T L i s   c ha r a c t e r i z e by   a   s t a rt   a rra y   i n de t ha t   i s   c h o s e n   ra n do m l y   a n a   s i z e   o f   m o v e m e n t s   t o w a r d   t h e   l e a de r   t h a t   i s   SML .     1   =   ×    (6)       F i gu r e   6   i s   a e xa m pl e   o f   a   m o v e m e n t   o f   t h e   hu n t e n um b e o n e   t o w a r ds   t h e   l e a de r,   t h e   S M L = 2 .           F i g u r e   6 .   A e xa m pl e   o f   a   m o v e m e n t   t o w a r ds   t h e   l e a de r       4. 1 . 4   C o o p e r ati o n   am o n h u n te r s   A l w a y s   i n   t h e   l o o of   IE   i t e r a t i o n s ,   a f t e r   t h e   m o v e   t ow a r ds   t h e   l e a de c o m e s   t h e   c o o pe r a t i o n   a m o n h u nt e r s ,   w h e r e   e a c h   h u nt e r   m o v e s   t ow a r ds   t h e   o t h e h u n t e rs   by   c o p y i n a   pa rt   f r o m   t h e i s o l ut i o n   w i t h   t h e   pr o b a b i l i t y   H G C R ,   o r   by   c h a n g i n t h e i r   po s i t i o n   r e l a t i v e l y   t o   t h e m s e l v e s   w i t h   t h e   p r o b a b i l i t y   (1 - H G C R ).   H G C R   ( H un t i n G r o up  Co n s i de ra t i o n   R a t e i s   a   n u m b e r   b e t w e e n   a n 1.   F i gu r e   i s   a n   e xa m pl e   o f   t h e   m o ve m e n t   o f   t h e   h u nt e n u m b e r   1   t o w a r ds   t hr e e   di f f e r e n t   hunt e r s   (t h e   c a s e   o f   t h e   p r o b a b i l i t y   H G C R ).   A n F i gu r e   i s   a n   e xa m pl e   of   c h a ngi n t h e   po s i t i o n   o f   a   h u n t e r   r e l a t i v e l y   t i t s e l f   (t h e   c a s e   of  t h e   pr o b a b i l i t y   1 - H G C R ).             F i gu r e   7 .   A e xa m pl e   o f   a   m o v e m e n t   t o w a r ds   o t h e r s   hu n t e r s   (t h e   c a s e   o f   H G CR )   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 .   14 ,   N o .   1 A p r i l   20 19   :     14 3     1 5 4   148       F i g u r e   8 .   A e xa m pl e   o f   c h a ngi n g   t h e   po s i t i o ( t h e   c a s e   o f   1 - H G C R )       4. 1 . 5   R e o r gan i z ati o n   T h e   i nt e n s i f i c a t i o n   o pe ra t i o n s   r e duc e   t h e   di s t a n c e s   a m o n t h e   h u nt e r s .   S o ,   t h e   s o l ut i o n s   p r e s e n t e by   t h e s e   h u n t e r s   b e c o m e   a l m o s t   s i m i l a r,   w h i c h   c a n   l e a d   t o   a   b l o c ka ge   i n   a   l o c a l   o pt i m um .   T h e n,   a   di v e r s i f i c a t i o n   o pe ra t i o n   i s   n e e de d:   t h e   r e o r g a ni z a t i o n   h u n t e r s .   F i gu r e   i s   a n   e xa m p l e   of   r e o r ga n i z a t i o n   o f   a   po pul a t i o n   o f   hu n t e r s   o f   H G S = 3.           F i g u r e   9 .   A e xa m pl e   o f   r e o r g a n i z a t i o n   hu n t e r s       4. 1 . S t r at e gi e s   a)   B a c k u p   s ys te m   A t   t h e   e n o f   e v e r y   i n t e n s i f i c a t i o n   o pe ra t i o n,   a   b a c kup  s y s t e m   i s   a pp l i e a nd  o nl y   t h e   go o n e w   s o l ut i o n s   a r e   t a ke n .   If   t h e   m o v e m e n t   t o w a r ds   t h e   l e a de r   o r   t o w a r ds   o t h e r   h u nt e r s   g i v e s   w o r s e   s o l ut i o n ,   o n e   r e t u rn s   t o   t h e   p r e v i o us   po s i t i o n .   T hi s   s t r a t e g y   h e l ps   a   r a pi d   c o n v e r ge n c e   t o w a r ds   l o c a l   o pt i m um .     b)   En d   c r i t e r i a   T h e   e n o f   t h e   s e a r c h   p r o c e s s   i s   de t e r m i n e b y   t h e   n u m b e r   o f   e p o c h s   NE   o r   by   i t s   h a l f   i n   t h e   c a s e   of  a   s t a t i o na r y   o pt i m um .     4. 2 .      I m p r o v e m e n ts   4. 2 . 1   O n e   b o n e   b a c k u p   s ys te m   T h e   f i r s t   i m p r o v e m e n t   i s   a pp l i e a t   t h e   s t r a t e gy   of   t h e   b a c kup  s y s t e m .   T h e r e fo r e ,   a   b a c kup  i s   m a de   fo r   e v e r y   c h a nge   du r i n g   t h e   o pe r a t i o o f   i n t e n s i f i c a t i o n   a nd  n o t   u nt i l   t h e   e nd.   F i gu r e   10  i s   a n   e xa m p l e   o f   t h e   i m p r o v e b a c kup  s y s t e m   du r i n g   t h e   m o v e m e n t   t o w a r ds   l e a d e r .     4. 2 .2   L e ad e r   m ov i n to w ar d s   h u n te r s   In   t h e   i ni t i a l   H uS   a l go r i t h m ,   t h e   l e a de r   do e s   n o t   m o ve   a l o n g   t h e   s e a r c h.   T h e   n e w   pr o po s e d   i m p r o v e m e n t   i s   t o   m ov e   t h e   l e a de r   t o w a r ds   t h e   o t h e r   h u nt e r s   (L M T H w h i l e   us i n t h e   b a c kup  s y s t e m   fo r   pr e s e r v i n i t s   qu a l i t y   of   t h e   b e s t - f o un po s i t i o n.   F i gu r e   1 i s   a n   e xa m p l e   o f   a   l e a de r   m o v i ng  t o w a r ds   t hr e e   h u nt e r s   us i ng  t h e   i m p r o v e b a c kup  s y s t 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       Im pr ov e d   hun t i n s e ar c h   al gor i t hm   f or   t he   quadr a t i c   a s s i gn m e nt   pr obl e m   ( A m i ne   A g har ghor )   149       F i g u r e   10 .   A e xa m pl e   o f   a i m p r o v e b a c kup  s y s t e m           F i g u r e   11 .   A e xa m pl e   o f   a   m o v e m e n t   o f   t h e   l e a de t o w a r ds   t h e   o t h e h u nt e r s       4. 2 . 3   D yn am i c   p a r am e te r s   T h e   f i n a l   p r o po s e i m pr o v e m e n t   i s   a t   t h e   l e v e l   of   c h a ngi n p a r a m e t e r s   dy n a m i c a l l y   dur i ng  t h e   s e a r c h   o o pt i m um .   T hi s   i m p r o v e m e n t   h e l ps   b e t t e r   c o n t r o l   t h e   i n t e n s i f i c a t i o n   a nd  t h e   di v e r s i f i c a t i o n   o pe r a t i o n s .   P a ra m e t e r s   a r e   c l a s s i fy   i n   t hr e e   c a t e go r i e s :   p a ra m e t e r s   o f   s t a t i c   v a l ue ,   pa ra m e t e r s   o f   d y n a m i c   v a l ue   a n p a r a m e t e r s   o f   h y b r i v a l ue .   T h e   p a r a m e t e r s   o f   s t a t i c   v a l ue   a r e   HGS H G CR   a n d   NE ;   t h e y   h a v e   t h e   s a m e   v a l ue   f r o m   t h e   b e gi nn i n o f   t h e   s e a r c h   u nt i l   t h e   e nd.   T h e   pa ra m e t e r   o f   d y n a m i c   v a l ue   i s   MML ;   i t   c h a nge s   i t s   v a l ue   dur i ng  t h e   s e a r c h .   A n t h e   pa r a m e t e r   o h y b r i v a l ue   i s   E P S ;   i t   c ha n ge s   i t s   v a l ue   un de c e r t a i n   c o n d i t i o n s .   T h e   p r o po s e de f i ni t i o n s   f o r   t h e   s t a t i c   pa ra m e t e r s   a r e   a s   f o l l ow s :         =     (7)        = 100   (8)     W h e r e   N   i s   t h e   s i z e   o f   t h e   e v a l u a t e Q A P L i b   i n s t a n c e .   T h e   p r o po s e de f i ni t i o n s   f o r   t h e   dy n a m i c   p a r a m e t e r s   a r e   a s   f o l l ow s :       = (   )      (9)          = 0 . 2 + 0 . 3   ×   (10)      = mi n { ( ) ( ) }     (11)     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 .   14 ,   N o .   1 A p r i l   20 19   :     14 3     1 5 4   150      = {  + 0 . 01 ×  , > 0 . 5  0 . 01 ×  , < 0 . 3     (12)        = {  + 5 × (   ) , > 0 . 5  5 × (   ) , < 0 . 3   (13)       W h e r e :   1.   RL W   ( R a t e   o f   t h e   d i s t a n c e   b e t w e e n   t h e   L e a de r   a n d   t h e   W o r s t   h u nt e r ).   2.   T N   ( T ra ppe d   N um b e r )   i s   t h e   num b e o f   e p o c h   t ha t   t h e   di s t a nc e   be t w e e n   t h e   l e a de a nd  t h e   w o r s t   h u nt e r   i s   l o w e r   t ha E P S .   3.   E N   ( E po c h   N um b e r )   i s   t h e   num b e o f   e p o c h s   r e a c h e d   du r i ng   t h e   s e a r c h .   4.   E P S   ( Ep s i l o n )   i s   t h e   m i n i m u m   d i s t a n c e   b e t w e e n   t h e   l e a de r   a n d   t h e   w o r s t   h u nt e r.   5.   s   i s   a   s o l ut i o f r o m   t h e   s ub s e t   o f   s o l ut i o n s   S.   6.   ( )   i s   t h e   v a l ue   o f   t h e   o b j e c t i ve   f un c t i o o f   t h e   b e s t   s o l ut i o r e p r e s e nt e by   t h e   l e a de r   d u r i n g   t h e   s e a r c h   o f   t h e   o pt i m um .     7.   ( )   i s   t h e   v a l ue   o f   t h e   o b j e c t i ve   f un c t i o o f   t h e   w o r s t   s o l ut i o d uri n g   t h e   s e a r c o f   t h e   o pt i m u m .   A c c o r di n t o   (10)   t h e   v a l ue   o f   MML   i s   de c r e a s i n g   w h i l e   t h e   v a l ue   o f   TN   i s   i n c r e a s i n g   a n v i c e   v e r s a .   T h e   m i ni m u m   v a l ue   o f   MML   i s   0 . a n d   t h e   m a xi m um   v a l ue   i s   0 . 5 .   T h e   v a l ue   o f   E P S   i (11 )   i s   de t e rm i n e a s   t h e   m i ni m um   di s t a n c e   du ri n t h e   s e a r c h ,   t h e n ,   i (1 2)  i s   a n   i m p r o v e m e n t   o f   E P S .   A c c o r di n t o   (1 3)   i f   t h e   RL W   i s   s upe r i o r   t o   0. 5,   w h i c h   m e a n s   t ha t   t h e   di s t a n c e   be t w e e n   t h e   l e a de a n t h e   w o r s t   h u n t e r   i s   50%   s upe ri o t o   E P S ,   t h e   v a l ue   o f   IE   i s   i n c r e a s i n t o   i n t n s i fy   t h e   s e a r c h.   A n d   i f   t h e   RL W   i s   i n f e ri o r   t o   0. 3 ,   w h i c h   m e a n s   t h a t   t h e   di s t a n c e   b e t w e e n   t h e   l e a de r   a nd  t h e   w o r s t   h u nt e r   i s   30%  i n f i ri o r   t o   E P S ,   t h e   v a l ue   of   IE   i s   d e c r e a s i ng  t o   r e duc e   t h e   i n t e n s i f i c a t i o n   du ri n t h e   s e a r c h .   T h e   m i n i m u m   v a l ue   of  IE   i s   30   a n d   t h e   m a xi m um   v a l ue   i s   1 00 .       5.   EX P ER I M EN TA R ES U L TS   5. 1 .       Ex p e r i m e n tal   r e s u l ts   o th e   p r o p o s e d   i m p r ov e m e n ts   T h i s   s e c t i o n   p r e s e n t s   t h e   pe r f o r m a n c e   of   I H uS   a l go r i t hm   o n   i n s t a n c e s   of   Q A P L i b .   T h e   t e s t s   a r e   pe r f o r m e o n   a   c o m put e r   p r o c e s s o r   I n t e l (R Co r e (T M i 5 - 4 300  CP U   @   1 . 9G H z   @   2 . 50   G H z   a n G B   of  R A M .   20  t i m e s   t e s t e f o r   e a c h   i n s t a n c e .   T h e   m o s t   i m po r t a nt   c o l l e c t e da t a   f r o m   t h e   ob t a i n e r e s ul t s   o v e r   t h e   20  r u n s   a r e :   1.   δ bes t :   T h e   B e s t - F o un S o l ut i o n s   ( B F S ).   2.   δ avg :   T h e   a v e r a ge   o f   t h e   B F S   3.   P S D P e r c e n t a ge   o f   t h e   S t a nda r d   D e v i a t i o n .   4.   S u c . :   T h e   pe r c e n t a ge   o f   S u c c e s s   i n   ge t t i n g   t h e   B e s t - K n o w n   S o l ut i o n   ( BK S ).   5.   θ avg :   T h e   a v e r a ge   pe r c e n t a ge   o f   e r r o r   i n   ge t t i ng  t h e   B F S .   6.   Γ avg :   T h e   a v e ra ge   r u t i m e   o f   t h e   p r o g r a m   i ge t t i n t h e   B F S .   7.   Γ bes t :   T h e   b e s t   r u t i m e   o f   t h e   p r o g ra m   i ge t t i n g   t h e   B F S .     PSD   i s   c a l c u l a t e d   a s   f o l l ow :     PSD =  × 100   (14)       SD = ( ) 2 20 = 1 20   (15)     W h e r e       SD   i s   t h e   S t a n da rd  D e v i a t i o n.     B SF i s   t h e   b e s t - f o un s o l ut i o n   i n   t h e   t e s t   n u m b e r   i .   θ a v g   i s   c a l c ul a t e a s   f o l l ow :     θ av g = ( ) × 100   (16)       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       Im pr ov e d   hun t i n s e ar c h   al gor i t hm   f or   t he   quadr a t i c   a s s i gn m e nt   pr obl e m   ( A m i ne   A g har ghor )   151   5. 1 . 1   O n e   b o n e   b a c k u p   s ys te m   T a b l e   s h o w s   t h e   us e pa r a m e t e r   v a l ue s   f o r   t h e   t e s t s   o f   t he   n e w   pr o po s e b a c kup  s y s t e m   o n   t h e   Q A P L i b   i n s t a n c e   B ur 26 a .   T a b l e   s h o w s   t h e   ob t a i n e r e s ul t s   c o m pa r e t o   t h e   o l b a c kup  s y s t e m   (b a c kup   s y s t e m   fo r   a l l   t h e   m o di f i e pa rt   i t h e   s o l ut i o n ) .       T a b l e   1 .   P a ra m e t e V a l ue s   HGS   M M L   IE   NE   26   0 . 3   30   100         T a b l e   2 .   O n e   B y   O n e   B a c kup  S y s t e m   Co m pa r e d   T o   F ul l   P a r t   B a c kup  S y s t e m   Ba c k u p   s y s t e m   S u c .   ( % )   θ a v g   (% )   Γb e s t   ( s e c )   Γa v g   ( s e c )   F u l l   p a rt   1   0 . 2 0 4 9   2 . 1 4 5   2 . 9 1 1   O n e   b y   o n e   87   0 . 0 1 0 7   0 . 9 0 1   2 4 . 6 3 4       A c c o r di n t o   t h e   t a b l e ,   t h e   s uc c e s s   of   f i n di ng  t h e   o pt i m um   b y   t h e   n e w   pr o po s e b a c kup  s y s t e m   h a s   i n c r e a s e c o n s i de ra b l y   c o m pa r e t o   t h e   o n e   ob t a i n e by   t h e   o l b a c kup  s y s t e m ,   e xa c t l y   86  t i m e s   b e t t e r .   T h e   pe r c e n t a ge   of   e rr o r   i s   r e duc e m o r e   t ha n   20  t i m e s ,   a n t h e   b e s t   t i m e   i s   r e duc e m o r e   t h a n   t i m e s .   F i n a l l y ,   t h e   a v e ra ge   t i m e   i s   i n c r e a s e m o r e   t ha n   1 t i m e s   b e c a us e   o f   t h e   a dd i t i o n a l   t e s t s .     5. 1 . 2   L e ad e r   m ov i n to w ar d   h u n te r s   T a b l e   s h o w s   t h e   ob t a i n e r e s ul t s   f o r   t h e   t e s t s   of   t h e   n e w   pr o p o s e d   o p e r a t i o n:   t h e   m o ve   of   t h e   l e a de t o w a r d   h u nt e r s   (L M T H o n   t h e   Q A P L i b   i n s t a n c e   B ur 2 6a .         T a b l e   3 .   R e s ul t s   F o T h e   L m t O pe r a t i o n   P ro p o s e d   o p e ra t i o n   S u c .   ( % )   θ a v g   (% )   Γb e s t   ( s e c )   Γa v g   ( s e c )   L M T H   100   0   0 . 9 5 4   1 6 . 6 6 9       A c c o r di n t o   t h e   t a b l e ,   t h e   s uc c e s s   t o   f i n t h e   o pt i m u m   by   t h e   n e w   pr o po s e L M T H   o p e r a t i o n   ha s   r e a c h e 10 0%,   a n t h e   a v e r a ge   t i m e   i s   i m p r o v e by   33%.     5. 1 . 3   D yn am i c   p a r am e te r s   5. 1 . 3. 1   H u n ti n G r o u p   S i z e   F i gu r e   12  s h o w s   t h e   o b t a i n e r e s ul t s   f r o m   t h e   t e s t s   o f   t h e   pr o po s e v a l ue s   of   H G S   a ppl i e t o   t h e   Q A P L i b   i n s t a n c e   B ur 26 a .   T h e   p r o po s e v a l ue s   of   H G S   a r e :       =     (17)       =   × 2   (18)       =   ÷ 2   (19)     W h e r e   N   i s   t h e   s i z e   o f   t h e   e v a l u a t e Q A P L i b   i n s t a n c e .   ( B u r 2 6 a )   =      A c c o r di n t o   F i gu r e   12,   (18)   i s   b e t t e r   t ha n   ( 19)   i n   a l l   t h e   o b t a i n e r e s ul t s .   (17)   i s   b e t t e r   t h a (18)   i a l l   t h e   o b t a i n e r e s ul t s   e xc e pt   fo r   Γ a v g   b y   l e s s   t h a n   1 0% .   T h e   m o s t   i m po r t a n t   r e s ul t   i s   θ a v g .   S o ,   (17)   i s   t h e   b e t t e r   v a l ue   f o r   H G S .     5. 1 . 3. 2   M ax i m u m   M ov e m e n to w ar d   th e   Le ad e r   F i gu r e   13  s h o w s   t h e   ob t a i n e r e s ul t s   f r o m   t h e   t e s t s   o t h e   f i xe m a xi m u m   a n m i n i m u m   v a l ue s   o M M L   a ppl i e t o   t h e   Q A P L i b   i n s t a n c e   B ur 26a .   A c c o r di ng  t o   F i gur e   13 ,   t h e   a v e ra ge   e rr o r   i s   e qua l   t o   a n d   t h e   a v e ra ge   t i m e   i s   t h e   l e a s t   w h e n   t h e   M M L   v a l ue   i s   b e t w e e 0 . a n d   0. 5.     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 .   14 ,   N o .   1 A p r i l   20 19   :     14 3     1 5 4   152       F i gu r e   12 .   T h e   r e s ul t s   o b t a i n e by   c h a ngi n g   t h e   v a l ue   o f   H G S           F i gu r e   13 .   T h e   r e s ul t s   o b t a i n e by   c h a ngi n g   t h e   m a xi m u m   a n d   m i ni m u m   v a l ue s   o f   M M L       5. 1 . 3. 3   Ep s i l o n   a n d   th e   i t e r a ti o n   p e r   e p o c h   F i gu r e   14  s h o w s   t h e   o b t a i n e r e s ul t s   f r o m   t h e   t e s t s   o f   t h e   R LW  v a l ue s   t ha t   i n c r e a s e   o r   de c r e a s e   t h e   v a l ue s   of   Ep s   a n d   IE   a pp l i e t o   t h e   Q A P L i b   i n s t a n c e   B ur 2 6a .           F i gu r e   14 .   T h e   r e s ul t s   o b t a i n e by   c h a ngi n g   t h e   E ps   a nd  t h e   IE   v a l ue s       A c c o r di n t o   F i gu r e   14 ,   t h e   a v e r a ge   e rr o r   i s   e qua l   t o   a n d   t h e   a v e ra ge   t i m e   i s   t h e   l e a s t   w h e n   t h e   Ep s   a n t h e   IE   v a l ue s   a r e   i m p r o v e w h e t h e   v a l ue   o f   R LW   i s   i n f e r i o r   t o   0 . o r   s upe r i o t o   0 . 5.   T a b l e   s h o w s   t h e   o b t a i n e r e s ul t s   f o r   t h e   t e s t s   of   t h e   d y n a m i c   pa ra m e t e r s   c o m pa r e t o   t h e   s t a t i c   pa ra m e t e r s   o n   t h e   Q A P L i i n s t a n c e   B ur 26a .   A c c o r di n t o   t h e   t a b l e ,   t h e   dy n a m i c   pa r a m e t e r s   ha v e   i m pr o v e t h e   be s t   t i m e   a n d   t h e   a v e ra ge   t i m e   t o   f i n d   t h e   o pt i m um .   Evaluation Warning : The document was created with Spire.PDF for Python.