I n d o n e s i a n   J o u r n a l   o f   E l e c t r i c a l   E n g i n e e r i n g   a n d   C o m p u t e r   S c i e n c e   V o l .   11 ,   N o .   3 S e p t e m b e r   201 8 ,   p p .   925 ~ 935   I S S N :   2502 - 4 7 5 2 D O I :   1 0 . 1 1 5 9 1 / i j e e c s . v 1 1 . i 3 . p p 9 2 5 - 9 3 5          925       J o u r n a l   h o m e p a g e h t t p : / / i a e s c o r e . c o m / j o u r n a l s / i n d e x . p h p / i j e e c s   D i s c r e te   C h i c k e n   S w a r m   O p ti m i z a ti o n   fo r   th e   Q u a d r a ti c   A s s i g n m e n P r o b l e m       S o u k a i n a   C h e r i f   B o u r k i   S e m l a l i 1 ,   M o h a m m e d   E s s a i d   R i f f i 2 ,   F a y ç a l   C h e b i h i 3   1 L A M A P I L a bora t ory , D e p a rt m e nt  of m a t he m a t i c s , F a c ul t y  of S c i e nc e s ,   U ni ve rs i t y  of Choua i b D oukka l i , E l   J a di d a , M oroc c o   2, 3 L A RO S E RI  L a bora t ory , D e p a rt m e nt  of Com p ut e r S c i e nc e s , F a c ul t y  of S c i e nc e s ,   U ni ve rs i t y  of Choua i b D oukka l i , E l   J a di da , M oroc c o       A r t i c l e   I n f o     A B S T R A C T     A r t i c l e   h i s t o r y :   R e c e i v e d   N o v   14 ,   2 0 1 7   R e v i s e d   J a n   8 ,   2 0 1 8   A c c e p t e d   M a y   2 6 ,   2 0 1 8     T he   qua dra t i c   a s s i g nm e nt   p robl e m   (Q A P i s   a   w e l l - know c om bi na t ori a l   op t i m i z a t i on  p robl e m w hi c c oul be   a p p l i e t di ffe re nt  a p p l i c a t i ons .   T he   m a i obj e c t i ve   of  t hi s   p a p e i s   t p re s e nt   t he   fi rs t   di s c re t i z a t i on  of  t he   c hi c ke s w a rm   op t i m i z a t i on  a l g ori t hm   (CS O t s ol ve   qua dra t i c   a s s i g nm e nt   p robl e m   w i t hout   us i ng   a   l oc a l   s e a rc h,  t he   a da p t a t i on  of  CS O  i n di s c re t e  c a s e   i s   ba s e on  re de fi ni ng   op e ra t i ons   a nd  op e ra t ors   of  t he   ori g i na l   ve rs i on.  A s   know n,  t he   CS O   i s   a   s t oc ha s t i c   m e t hod  i ns p i re from   t he   be ha vi or  of  c hi c k e ns   i s w a rm   w hi l e   s e a rc hi ng   for  food.   T he   e x p e ri m e nt s   a re   p e rform e d   on  a   s e t   of  56  be nc hm a rk  Q A P L IB  i ns t a nc e s T p rove   t he   c hoi c e   of  t he   a de qua t e   p a ra m e t e rs a   s t udy   i s  c onduc t  on CS O  us i ng  s i m ul a t i ons  on c e rt a i i ns t a nc e s T he   di s c us s i on  of  di ffe re nt   t e s t s   obt a i ns   c om p e t i t i ve   re s ul t s   c om p a re w i t t he   know m e t a he uri s t i c   of G e ne t i c  a l g ori t hm  ba s e d on S CX T he  re s ul t s   de m ons t ra t e  e ffe c t i ve ne s s  of t he  p rop os e CS O - QAP   t o s ol ve  t he   qua dra t i c   a s s i g nm e nt   p robl e m   i t e rm   of  t i m e   a nd  qua l i t y   of  s ol ut i ons .   T he   p rop os e a da p t a t i on  c a be   furt he a p p l i e by   us i ng   a   l oc a l   s e a rc s t ra t e g y   s uc a s   2 - op t   i orde t s ol ve   t he   s a m e   p robl e m   or  a not he N P - ha rd  c om bi na t ori a l   p robl e m .     K e y w o r d s :   C h i c k e n   s w a r m   o p t i m i z a t i o n   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   p r o b l e m   Q A P L i b   Q u a d r a t i c   a s s i g n m e n t   p r o b l e m   Copy r i ght   ©   201 8   Ins t i t ut e   of   A dv anc e d E ngi ne e r i ng  and Sc i e nc e   A l l   r i ght s  r e s e r v e d .   C o r r e s p o n d i n g   A u t h o r :   S o u k a i n a   C h e r i f   B o u r k i   S e m l a l i ,   L A M A P I   L a b o r a t o r y ,   D e p a r t m e n t   o f   m a t h e m a t i c s ,     F a c u l t y   o f   S c i e n c e s , U n i v e r s i t y   o f   C h o u a i b   D o u k k a l i ,     E l   J a d i d a ,   M o r o c c o .   E m a i l :   S o u k a i n a . c h e r i f . b . s @u c d . a c . m a       1.   I N T R O D U C T I O N     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   o c c u p i e s   a n   i m p o r t a n t   p l a c e   i n   d i s c r e t e   m a t h e m a t i c s   a n d   c o m p u t e r   s c i e n c e ,   a l t h o u g h   t h 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   p r o b l e m s   a r e   o f t e n   e a s y   t o   d e f i n e ,   b u t   t h e y   a r e   g e n e r a l l y   d i f f i c u l t   t o   s o l v e .   I n d e e d ,   m o s t   o f   t h e s e   p r o b l e m s   b e l o n g   t o   t h e   c l a s s   N P - h a r d   s u c h   a s   S c h e d u l i n g   W o r k f l o w   i n   C l o u d   C o m p u t i n g   [ 1 ] ,   T r a v e l i n g   S a l e s m a n   P r o b l e m   [ 2 ]   a n d   j o b   s h o p   s c h e d u l i n g   p r o b l e m   ( J S S P )   [ 3 ] .   T h e r e f o r e ,   N P - h a r d   p r o b l e m s   d o n t   h a v e   a n   e f f e c t i v e   s o l u t i o n   f o r   a l l   t h e   d a t a ,   t h e n   w e   n e e d   t o   d e f i n e   a   f o r m a l   f r a m e w o r k   f o r   m a n y   i n d u s t r y   i n   s c i e n c e ,   e n g i n e e r i n g   a n d   b u s i n e s s .   I n   t h i s   w o r k ,   w e   i n t e n d   t o   d i s c u s s   o n e   o f   t h e   m o s t   i n t e r e s t i n g   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   p r o b l e m   u s e d   i n   t h e   p l a n t   l a y o u t   i n   o r d e r   t o   d e t e r m i n e   t h e   i n t e r a c t i o n   a n d   t h e   d i s t a n c e   b e t w e e n   t w o   f a c i l i t i e s .   T h e   a i m   o f   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m   i s   t o   f i x   t h e   m o s t   e f f e c t i v e   a r r a n g e m e n t   o f   d e p a r t m e n t s   w i t h i n   t h e   p l a n t   w h e n   t h e   f l o w   b e t w e e n   d e p a r t m e n t s   r e m a i n s   c o n s t a n t   d u r i n g   t h e   h o r i z o n t a l   p l a n n i n g .   Q A P   i s   a   c l a s s i c a l   N P - h a r d   p r o b l e m   [ 4 ]   i n   w h i c h   i t   i s   n e c e s s a r y   t o   f i n d   t h e   o p t i m a l   p l a c e m e n t   o f   n   o b j e c t s   b y   t a k i n g   i n t o   a c c o u n t   b o t h   t h e   c o s t   o f   a l l o c a t i o n   o f   a n   e q u i p m e n t   a n d   i t s   i n t e r a c t i o n   w i t h   o t h e r   e q u i p m e n t s .   I n   t h e   f i e l d   o f   l o c a t i o n   s c i e n c e ,   m a n y   p r a c t i c a l   p r o b l e m s   c a n   b e   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2502 - 4 7 5 2   I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i ,   V o l .   11 ,   N o .   3 S e p t e m b e r   2 0 1 8   :     9 2 5     935   926   f o r m u l a t e d   a s   q u a d r a t i c   a s s i g n m e n t   p r o b l e m s   ( Q A P )   s u c h   a s   t h e   s t u d y   o f   B u r k a r d   [ 5 ]   w h i c h   a p p l i e d   t h e   h e u r i s t i c   p r o c e d u r e   p r o p o s e d   b y   M e t r o p o l i s   e t   a l   [ 6 ]   a n d   t h e   a p p r o a c h   o f   L a p o r t e   a n d   M e r c u r e   [ 7 ] ,   w h i c h   u s e d   t h e   p r o b l e m   o f   b a l a n c i n g   h y d r a u l i c   t u r b i n e   r u n n e r s .   M a n y   m e t h o d s   w e r e   a d a p t e d   t o   s o l v e   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m ,   a m o n g   t h e s e   a d a p t a t i o n s   a r e   m e t a h e u r i s t i c s .   M e t a h e u r i s t i c   i s   a   t e c h n i q u e   t h a t   s e e m s   t o   f i t   w i t h   t h e   s t r u c t u r e   o f   a n y   p r o b l e m .   S u c h   a s   s i m u l a t e d   a n n e a l i n g   b y   M R   W i l h e l m   i n   1 9 8 7   [ 8 ] ,   t h e   t a b o o   s e a r c h   [ 9 ] ,   t h e   g e n e t i c   a l g o r i t h m   [ 1 0 ] ,   t h e   g r e e d y   g e n e t i c   a l g o r i t h m   [ 1 1 ] ,   t h e   a n t   c o l o n y   a l g o r i t h m   [ 1 2 ]   a n d   H u n t i n g   S e a r c h   A l g o r i t h m   [ 1 3 ] .   T h e   S w a r m   o p t i m i z a t i o n   a l g o r i t h m s   o f f e r   a   n e w   a p p r o a c h   t o   s o l v e   s e v e r a l   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   p r o b l e m s   i n   e n g i n e e r i n g   a n d   c o m p u t e r   s c i e n c e s .   T h e s e   a l g o r i t h m s   a r e   p r o p o s e d   b y   m i m i c k i n g   t h e   i n t e l l i g e n c e   a n d   t h e   b e h a v i o r s   o f   t h e   p o p u l a t i o n   i n   n a t u r e ,   s u c h   a s   a n t   c o l o n y   o p t i m i z a t i o n   a l g o r i t h m     ( A C O )   [ 1 4 ] ,   b e e   c o l o n y   o p t i m i z a t i o n   [ 1 5 ] ,   a r t i f i c i a l   b e e   c o l o n y   a l g o r i t h m   ( A B C )   [ 1 6 ] ,   b a t - i n s p i r e d     a l g o r i t h m   [ 1 7 ] ,   P a r t i c l e   S w a r m   O p t i m i z a t i o n   ( P S O )   [ 1 8 ] ,   s p i d e r   m o n k e y   [ 1 9 ] ,   f i r e f l y   a l g o r i t h m s   [ 2 0 ]   a n d   c u c k o o   s e a r c h   [ 2 1 ] .   T h i s   p a p e r   a p p l i e d   t h e   C h i c k e n   s w a r m   o p t i m i z a t i o n   ( C S O )   w h i c h   i s   a n   a l g o r i t h m   t h a t   s i m u l a t e s   t h e   b e h a v i o r s   o f   t h e   c h i c k e n   s w a r m .   T h e   C S O   c a n   e f f e c t i v e l y   h a r n e s s   t h e   i n t e l l i g e n c e   o f   a   c h i c k e n   s w a r m   t o   s o l v e   p r a c t i c a l l y   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m .   T h e   p r o p o s e d   a d a p t a t i o n   o f   C S O   i s   t h e   f i r s t   d i s c r e t i z a t i o n   o f   t h e   c h i c k e n   s w a r m   o p t i m i z a t i o n   a l g o r i t h m   ( C S O )   t o   s o l v e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m ,   t h e   n e w   a p p r o a c h   o f   C S O   i n   d i s c r e t e   c a s e   i s   b a s e d   o n   r e d e f i n i t i o n   o f   o p e r a t i o n s   a n d   o p e r a t o r s   i n   o r d e r   t o   t o   s o l v e   t h e   m o s t   o f   Q A P L i b   i n s t a n c e s .   T h i s   p a p e r   i s   o r g a n i z e d   a s   f o l l o w s :   I n   t h e   s e c o n d   s e c t i o n ,   w e   d e s c r i b e   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m .   I n   t h e   t h i r d   s e c t i o n ,   w e   p r e s e n t   t h e   m e t a h e u r i s t i c   u s e d   i n   t h i s   w o r k   t o   s o l v e   t h e   Q A P .   T h e n ,   i n   t h e   f o u r t h   s e c t i o n ,   w e   p r o v i d e   m a n y   s i m u l a t i o n s   t o   j u s t i f y   t h e   c h o i c e   o f   p a r a m e t e r s   u s e d   a n d   t h e   r e s u l t s   o b t a i n e d   o f   t h i s   c o n t r i b u t i o n .   F i n a l l y ,   i n   t h e   l a s t   s e c t i o n ,   w e   c l o s e   t h i s   p a p e r   w i t h   a   c o n c l u s i o n .       2.   Q U A D R A T I C   A S S I G N M E N T   P R O B L E M   T h e   m a n a g e m e n t   o f   a   p l a n t   h a d   l o n g   b e e n   a   f i e l d   o f   r e s e a r c h ,   a s   a   r e s u l t ,   s e v e r a l   a p p r o a c h e s   a r e   d e v e l o p e d   o v e r   t h e   y e a r s ,   b u t   t h e   r e s o u r c e   a l l o c a t i o n   p r o b l e m   i s   s t i l l   p r e s e n t .   T h e r e   a r e   d i f f e r e n t   f o r m u l a t i o n s   t o   s o l v e   t h e   p r o b l e m   o f   f a c i l i t y   m a n a g e m e n t .   O n e   o f   t h e   s i m p l e   f o r m u l a t i o n s   t o   b e   m o d e l e d   i s   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m   ( P A Q ) .   C o n s i d e r e d   a s   o n e   o f   t h e   g r e a t   c h a l l e n g e   i n   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 ,   Q u a d r a t i c   A s s i g n m e n t   P r o b l e m   i s   i n t r o d u c e d   i n   t h e   f i r s t   t i m e   b y   k o o p m a n s   a n d   b e e k m a n n   i n   1 9 5 7   [ 2 2 ] .   T h e   Q A P   c a n   b e   r e f o r m u l a t e d   i n t o   m a n y   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   p r o b l e m s   s u c h   a s   t h e   g r a p h   p a r t i t i o n i n g   p r o b l e m s   a n d   t h e   T r a v e l l i n g   S a l e s m a n   P r o b l e m   [ 2 3 ] .   T h e   i d e a   i s   t o   s e t   t w o   m a t r i c e s   o f   s i z e   ( n , n ) ,   g i v e n   a s   A   =   ( a ij )   w h i c h   r e f e r s   t o   t h e   f l o w s   b e t w e e n   p a i r s   o f   f a c i l i t i e s   a n d ( ) ( ) ij Bb  f o r   t h e   d i s t a n c e   o f   t h e i r   l o c a t i o n s .   A f t e r   t h e   a f o r e m e n t i o n e d   d e s c r i p t i o n s ,   t h e   p u r p o s e   o f   t h i s   a p p r o a c h   i s   t o   f i n d   a *   p e r m u t a t i o n   a m o n g   a   s e t   n o f   p e r m u t a t i o n s ,   w h i c h   m i n i m i z e s   t h e   c o s t   a l l o c a t i o n   o f   f a c i l i t i e s   i n t o   l o c a t i o n s ,   t h e   m a t h e m a t i c a l   f o r m u l a t i o n   i s   g i v e n   a s   f o l l o w s :     ( ) ( ) 11 ( * ) m i n nn i j i j ij C a b                                            ( 1 )       3.   C H I C K E N   S WA R M   O P T I M I Z A T I O N   T h e   C h i c k e n   s w a r m   o p t i m i z a t i o n   ( C S O )   i s   a   s t o c h a s t i c   a l g o r i t h m   i n s p i r e d   b y   t h e   b e h a v i o r s   o f   a   c h i c k e n   s w a r m ;   a n d   i n t r o d u c e d   b y   M e n g ,   X . B .   A n d   a l .   [ 2 4 ] .   T h e   c h i c k e n   s w a r m   i s   d i v i d e d   i n t o   s e v e r a l   g r o u p s ;   e a c h   g r o u p   c o m p r i s e s   o n e   d o m i n a n t   r o o s t e r   a n d   m a n y   h e n s   a n d   c h i c k s .   E a c h   t y p e   o f   c h i c k e n   f o l l o w s   d i f f e r e n t   m o v e m e n t s .   T h e   r o o s t e r s ,   h e n s   a n d   c h i c k s   a r e   i d e n t i f i e d   b y   t h e   f i t n e s s   v a l u e   o f   t h e   c h i c k e n s   t h e m s e l v e s .   T h e   c h i c k e n s   w i t h   t h e   b e s t   f i t n e s s   v a l u e s   w o u l d   b e   d e s i g n a t e d   t o   a c t   a s   r o o s t e r s   o r   t h e   l e a d e r   o f   t h e   g r o u p ,   t h e y   c o u l d   s e a r c h   f o r   f o o d   i n   a   w i d e r   r a n g e   o f   s p a c e , t h e n   t h e y   w o u l d   b e   f o l l o w e d   b y   t h e   o t h e r s   c h i c k e n s   .   T h e   c h i c k e n s   w i t h   t h e   w o r s t   f i t n e s s   v a l u e s   w o u l d   b e   r e f e r r e d   a s   c h i c k s ,   w h i c h   c o u l d   s e e k   f o r   f o o d   a r o u n d   t h e i r   m o t h e r .   T h e   o t h e r s   w o u l d   b e   t h e   h e n s ,   w h i c h   r a n d o m l y   c h o o s e   t h e i r   g r o u p s   a n d   e s t a b l i s h   a   m o t h e r - c h i l d   r e l a t i o n   w i t h   c h i c k s .   T h e   t w o   r e l a t i o n s   o f   d o m i n a n c e   a n d   m o t h e r - c h i l d   b e t w e e n   t h e   h e n s   a n d   t h e   c h i c k s   a r e   a l l   u p d a t e d   a f t e r   f e w   g e n e r a t i o n s   , a   p a r a m e t e r   G   i s   u s e d   t o   i n d i c a t e   t h e   n u m b e r   o f   t i m e   s t e p s ,   i f   2 ; 2 0 G t h e n   t h e   a l g o r i t h m   c o u l d   g i v e   a   g o o d   r e s u l t s   a n d   c o u l d   e a s i l y   f a l l   i n t o   a   l o c a l   o p t i m u m ,   o t h e r w i s e   t h e s e   s t a t u s e s   r e m a i n   u n c h a n g e d .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i     I S S N :   2502 - 4 7 5 2       D i s c r e t e   C h i c k e n   S w a r m   O p t i m i z a t i o n   f o r   t h e   Q u a d r a t i c   A s s i g n m e n t   P r o b l e m s   ( S o u k a i n a   C .   B o u r k i   S e m l a l i )   927   I n   a   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   p r o b l e m ,   t h e   p o s i t i o n   o f   e a c h   c h i c k e n s   r e p r e s e n t s   a   s o l u t i o n .   T h e   r o o s t e r s   w i t h   t h e   b e s t   f i t n e s s   v a l u e s   a r e   t h e   m o s t   d o m i n a n t s   a n d   t h e y   c o u l d   s e a r c h   f o r   f o o d   i n   a   w i d e r   r a n g e   o f   s p a c e ,   t h e r e f o r e   t h e y   h a v e   p r i o r i t y   t o   a c c e s s   t o   f o o d   t h a n   t h e   h e n s   w i t h   l o w e r   f i t n e s s   v a l u e s ,   w h i c h   a r e   u n s t r a i n e d   t o   e a t   f o o d .   O n   t h e   o t h e r   h a n d ,   C h i c k s   m o v e   a r o u n d   t h e i r   m o t h e r s   t o   g e t   f o o d .   I n   [ 2 4 ]   t h e   n u m b e r   o f   r o o s t e r s ,   h e n s ,   c h i c k s   a n d   m o t h e r   h e n s ,   d e p i c t e d   b y   R N ,   H N ,   C N   a n d   M N ,   r e s p e c t i v e l y .   T h e   p r o b l e m   i s   s o l v e d   i n   a   D - d i m e n s i o n a l   s p a c e ,   x t i;j  s t a n d s   t h e   p o s i t i o n s   o f   a l l   t h e   N   c h i c k e n s   a t   t i m e   s t e p   t   w h i l e   s e a r c h i n g   f o r   f o o d .   T h e   p o s i t i o n   u p d a t e   e q u a t i o n   o f   t h e   r o o s t e r   c a n   b e   f o r m u l a t e d   a s :     12 ,, ( 1 ( 0 , ) ) tt i j i j x x R a n d n                                                                   ( 2 )     2 () || 1, e x p , 1 , , ki i ij ff f i f f f o t h e r w i s e k N k i                                         ( 3 )     W h e r e   - 2 ( 0 , ) R a n d n i s   a   G a u s s i a n   d i s t r i b u t i o n , 2 i s   a   s t a n d a r d   d e v i a t i o n .   T h e   r o o s t e r   i n d e x   k   i s   r a n d o m l y   s e l e c t e d   f r o m   t h e   r o o s t e r s   g r o u p ,   a n d   f   i s   t h e   f i t n e s s   v a l u e   o f   t h e   c o r r e s p o n d i n g   x .   T h e   h e n s   c a n   f o l l o w   t h e i r   g r o u p   l e a d e r s   t o   f o r a g e   f o r   f o o d ;   f u r t h e r m o r e ,   t h e y   m a y   r a n d o m l y   l o c a t e   a n d   s t e a l   t h e   g o o d   f o o d   f o u n d   b y   o t h e r   c h i c k e n s .   T h e s e   s i t u a t i o n s   c a n   b e   r e p r e s e n t e d   a s   b e l o w :     1 , , 1 , , 2 , , 1 ( ) 2 ( ) t t t t t t i j i j r j i j r j i j x x S R a n d x x S R a n d x x     ( 4 )     A s       ( 1 ) ( | | ) 1 ir i ff f Se        A n d   2 () 2 ri ff Se     W h e r e   R a n d   i s   c h o s e n   r a n d o m l y   f r o m   [ 0 ,   1 ] ,   r 1   a n d   r 2   a r e   t w o   i n d e x 12 rr ,   t h e   f i r s t   i s   t h e   i n d e x   o f   t h e   r o o s t e r   o t h e r w i s e   t h e   s e c o n d   i s   t h e   i n d e x   o f   a   r a n d o m   c h i c k e n   f r o m   t h e   s w a r m   ( r o o s t e r   o r   h e n ) .   A t   l a s t ,   t h e   p o s i t i o n   u p d a t e   e q u a t i o n   o f   t h e   c h i c k   i s   f o r m u l a t e d   i n   [ 2 4 ]   a s   f o l l o w s :     1 , , , , () t t t t i j i j m j i j x x F L x x               ( 5 )     W h e r e   1, mN   i s   t h e   i n d e x   o f   t h e   c h i c k s   m o t h e r   a n d   0 , 2 FL   i s   a   r a n d o m l y   s e l e c t e d   p a r a m e t e r   t o   r e f e r   t o   t h e   r e l a t i o n s h i p   b e t w e e n   t h e   c h i c k s   a n d   i t s   m o t h e r .     A s   t h e   c h i c k s   o n l y   l e a r n   a n d   g e t   p o s i t i o n   f r o m   t h e i r   m o t h e r s ,   t h e y   w i l l   e a s i l y   f a l l   i n t o   t h e   l o c a l   o p t i m u m   a s   t h e i r   m o t h e r s .   I n   2 0 1 5 ,   D i n g h u i   W u   [ 2 5 ]   a d d e d   t o   t h e   p o s i t i o n   u p d a t e   e q u a t i o n   o f   t h e   c h i c k s   t w o   f a c t o r s ,   t h e   f i r s t   o n e   i s   t h e   l e a r n i n g   f a c t o r   C   w h i c h   m e a n s   t h a t   t h e   c h i c k s   c o u l d   g e t   i n f o r m a t i o n   f r o m   t h e   r o o s t e r ,   t h e   s e c o n d   o n e   i s   W   a   s e l f - l e a r n i n g   c o e f f i c i e n t   f o r   t h e   c h i c k s .   T h e   n e w   e q u a t i o n   i s   m o d i f i e d   a s   f o l l o w s :     1 , , , , , , () t t t t t t i j i j m j i j r j i j x W x F L x x C x x           ( 6 )     W h e r e   r   i s   t h e   i n d e x   o f   t h e   r o o s t e r   a n d   m   i s   t h e   i n d e x   o f   t h e   m o t h e r .       4.   D I S C R E T E   C S O   A L G O R I T H M   F O R   Q U A D R A T I C   A S S I G N M E N T   P R O B L E M   A f t e r   o b s e r v i n g   e a c h   i n d i v i d u a l   i n   t h e   c h i c k e n   s w a r m ,   i t   w a s   f o u n d   t h a t   t h e   c h i c k e n   h a s   a   c a p a c i t y   f o r   c o m m u n i c a t i o n   a n d   a b i l i t y   t o   l e a r n ,   t h u s   t h e r e   i s   a   s t r i c t   h i e r a r c h i c a l   o r d e r ,   w h i c h   c a n   b e   u s e d   t o   m o d e l   a   n e w   s t o c h a s t i c   b i o - i n s p i r e d   a l g o r i t h m   i n   o r d e r   t o   s o l v e   m a n y   d i s c r e t e   o p t i m i z a t i o n   p r o b l e m .   I n   t h e   b e g i n n i n g ,   t h e   s w a r m   m u s t   b e   s t r u c t u r e d   b y   d e c l a r i n g   a   p o p u l a t i o n ,   i t s   p a r a m e t e r   c o n f i g u r a t i o n   i s   s i m p l e ,   t h e   f i x e d   i d e n t i t i e s   f o r   e a c h   i n d i v i d u a l   i s   d e f i n e d   a f t e r   i n d i c a t i n g   t h e   n u m b e r   o f   r o o s t e r s ,   h e n s   a n d   c h i c k e n s ;   t h e n   t h e   h i e r a r c h i c a l   o r d e r   b e t w e e n   t h e   i d e n t i t i e s   o f   t h e   c h i c k e n s   a n d   t h e   r e l a t i o n s   b e t w e e n   t h e   m o t h e r - c h i l d s   a r e   e s t a b l i s h e d ;   A n d   f i n a l l y ,   a   c e r t a i n   p a r a m e t e r   G   m u s t   b e   f i x e d   t o   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2502 - 4 7 5 2   I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i ,   V o l .   11 ,   N o .   3 S e p t e m b e r   2 0 1 8   :     9 2 5     935   928   r e g u l a r l y   u p d a t e   t h e   r e l a t i o n s   i n   t h e   c h i c k e n   s w a r m   s o   t h a t   t h e   p r o b l e m   o f   f a l l i n g   i n t o   a   l o c a l   o p t i m u m   i s   a v o i d e d .   E a c h   c h i c k e n   i s   r e p r e s e n t e d   b y   p o s i t i o n ,   w h i c h   i s   s u r r o g a t e d   b y   a   v e c t o r   o f   N   f a c i l i t i e s   a s s i g n e d   t o   l o c a t i o n s ,   t h e r e b y   a   c h i c k e n   c a n   s e a r c h   f o o d   i n   a   s e t   o f   s o l u t i o n s   S   ( t h e   s e a r c h   s p a c e ) ,   a n d   t h e   p o s i t i o n   o f   a   s e l e c t e d   c h i c k e n   i s   t h e   c u r r e n t   s o l u t i o n .   T h e   p u r p o s e   o f   t h e   d i s c r e t i z a t i o n   i s   t o   o b t a i n   t h e   p o s i t i o n   o f   t h e   c h i c k e n ,   w h i c h   p r o v i d e   t h e   m i n i m u m   o f   t h e   o b j e c t i v e   f u n c t i o n : fS  .   T h i s   s e c t i o n   d e s c r i b e s   a   n e w   a d a p t a t i o n   o f   t h e   o r i g i n a l   C S O   a l g o r i t h m ;   C S O - Q A P   i s   e s t a b l i s h e d   b y   t h e   r e d e f i n i t i o n   o f   t h e   o p e r a t o r s   a n d   t h e   o p e r a t i o n s   o f   C S O   ( F i g u r e   1   a n d   2 ) .     4 . 1 .   I n i t i a l i z e   t h e   p o p u l a t i o n   I n   t h i s   f i r s t   p a r t ,   a f t e r   r e a d i n g   t h e   i n s t a n c e s   o f   t h e   Q A P L I B ,   t h e   a l g o r i t h m   b e g i n s   w i t h   t h e   c r e a t i o n   o f   a n   i n i t i a l   p o p u l a t i o n   P   o f   N   e l e m e n t s   r a n d o m l y   s e l e c t e d   a m o n g   p   e x i s t i n g   p e r m u t a t i o n   o f   t h e   s e a r c h   s p a c e ,   w h i c h   c o n t a i n s   a l l   t h e   p o s s i b i l i t i e s   ( w h e r e 1! 2 n p ).   E a c h   p o s s i b i l i t y   i s   o b t a i n e d   b y   a s s i g n i n g   a   f a c i l i t y   t o   i t s   l o c a t i o n ,   a n d   t h e n   i t   i s   r e p r e s e n t e d   b y   a n   a r r a y   o f   i n t e g e r   o f   s i z e   n   w h e r e   e a c h   i n t e g e r   i s   a n   i n d e x   t h a t   r e f e r   t o   t h e   f a c i l i t y s   l o c a t i o n .   T h e   f o l l o w i n g   e x a m p l e   i s   a   s i m p l e   e x a m p l e   o f   a   Q A P   s o l u t i o n   t h a t   r e p r e s e n t s   a n   a s s i g n m e n t   o f   6   i n s t a l l a t i o n s   t o   6   l o c a t i o n s ;   t h e   s o l u t i o n   ( t h e   t a b l e   o f   a r r a y )   r e p r e s e n t s   a   c h i c k e n   i n   a   k n o w n   p o s i t i o n .         F i g u r e   1 .   E x a m p l e   o f   A s s i g n i n g   F a c i l i t i e s   t o   L o c a t i o n s   i n   Q A P   F i g u r e   2 .   M o v e m e n t   o f   a   C h i c k e n   i n   C S O         4 . 2 .   E s t a b l i s h   t h e   H i e r a r c h i c a l   O r d e r   T h e   s e l e c t e d   p o p u l a t i o n   i s   s o r t e d   a n d   r a n k e d   a f t e r   e v a l u a t i n g   t h e   f i t n e s s   v a l u e   o f   e a c h   i n d i v i d u a l ,   t h e n   a   h i e r a r c h a l   o r d e r   i n   t h e   s w a r m   i s   e s t a b l i s h e d ,   t h e   c h i c k e n s   w i t h   t h e   m i n i m u m   f i t n e s s   v a l u e s   a r e   d e s i g n a t e d   a s   t h e   r o o s t e r s ,   t h e   n u m b e r   o f   t h e   r o o s t e r s ,   t h e   h e n s ,   t h e   c h i c k s   a n d   t h e   m o t h e r   h e n s   d e p i c t e d   b y   R N ,   H N ,   C N   a n d   M N .   T h e   n u m b e r   o f   r o o s t e r s   c a n   b e   e x p r e s s e d   b y   t h e   E q u a t i o n   7 ,   t h e   n u m b e r   o f   h e n s   b y   t h e   E q u a t i o n   8 ,   o t h e r w i s e   t h e   n u m b e r   o f   c h i c k s   i s   c a l c u l a t e d   b y   t h e   E q u a t i o n   9 ,   a n   i n d e x   i s   a s s i g n e d   t o   e a c h   t y p e   1 ,   2   a n d   3   f o r   t h e   r o o s t e r s ,   h e n s   a n d   c h i c k s   r e s p e c t i v e l y .     R N N r p                                                                                                    ( 7 )     H N N h p                                                                                              ( 8 )     () C N N R N H N                                                                 ( 9 )     W h e r e   r p   i s   t h e   p r o p o r t i o n s   o f   r o o s t e r s   a n d   h p   i s   t h e   p r o p o r t i o n s   o f   h e n s .   M N   r e p r e s e n t s   t h e   n u m b e r   o f   m o t h e r   h e n s ,   i t   c o u l d   b e   c a l c u l a t e d   b y   1 0 ,   a n d   f u r t h e r m o r e   w e   a s s i g n   t o   e a c h   m o t h e r   a   r a n d o m   i d :     M N H N m p                                                                                                    ( 1 0 )     Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i     I S S N :   2502 - 4 7 5 2       D i s c r e t e   C h i c k e n   S w a r m   O p t i m i z a t i o n   f o r   t h e   Q u a d r a t i c   A s s i g n m e n t   P r o b l e m s   ( S o u k a i n a   C .   B o u r k i   S e m l a l i )   929   T h e   s i z e s   o f   R N ,   H N ,   C N   a n d   M N   d i r e c t l y   d e t e r m i n e   t h e   s t r u c t u r e   o f   t h e   s w a r m ,   w h i c h   a f f e c t   t h e   p e r f o r m a n c e   o f   C S O   t o   s o l v e   Q A P .     4 . 3 .   C r e a t e   g r o u p s   T h e   s w a r m   i s   r a n d o m l y   d i v i d e d   i n t o   d i f f e r e n t   g r o u p s   a c c o r d i n g   t o   t h e   p r o p o r t i o n s   o b t a i n e d   a t   t h e   b e g i n n i n g   o f   t h e   a l g o r i t h m ,   t h e   n u m b e r   o f   g r o u p s   i s   e q u a l   t o   n u m b e r   o f   r o o s t e r s ,   w e   a s s i g n   r a n d o m l y   t o   e a c h   m o t h e r   a n   i d   h e n c e   t h e   r e l a t i o n s h i p   b e t w e e n   c h i c k s   a n d   m o t h e r   h e n s   i s   s c h e d u l e d   i n d i s c r i m i n a t e l y   i n     e a c h   g r o u p .   A f t e r   G   i t e r a t i o n s ,   a   r e d i s t r i b u t i o n   o f   t h e   s w a r m   i s   r e q u i r e d ,   i n   o r d e r   t h a t   t h e   r o o s t e r s   f i n d   t h e   b e s t   s o l u t i o n   o f   t h e   s w a r m   a n d   t h e   o t h e r   i n d i v i d u a l s   c o u l d   m o v e   t o w a r d s   t h e s e   s o l u t i o n s   u n t i l   t h e   o p t i m u m   i s   f o u n d .     4 . 4 .   T h e   m o v e m e n t s   o f   a   c h i c k e n   I n   t h i s   a d a p t a t i o n ,   a   m o v e m e n t   o f   a   g i v e n   c h i c k e n   i s   r e p r e s e n t e d   b y   t h e   p e r m u t a t i o n   o f   t w o   o f   i t s   m a t r i x   e l e m e n t s .   A n   e x a m p l e   o f   a   p e r m u t a t i o n   i s   d e s c r i b e d   a s   f o l l o w s :   T h e r e   a r e   t h r e e   t y p e s   o f   c h i c k e n s   ( r o o s t e r s ,   h e n s   a n d   c h i c k s ) ,   e a c h   o n e   m o v e s   i n   a   s t r u c t u r e d   w a y   a c c o r d i n g   t o   a   h i e r a r c h y   d e f i n e d   i n   t h e   p r e v i o u s   s e c t i o n s .   T h u s ,   t h r e e   t y p e s   o f   m o v e m e n t s   a r e   p o s s i b l e ;   e a c h   o n e   i s   c h a r a c t e r i z e d   b y   a   s e t   o f   o p e r a t i o n s   a n d   o p e r a t o r s .   D u r i n g   t h e   d i s c r e t i z a t i o n ,   w e   d e f i n e d   a   s e t   o f   o p e r a t o r s ,   w h i c h   a r e       a n d     a s   f o l l o w s :     4 . 4 . 1 .   S u b t r a c t i o n   o p e r a t i o n       x i     x j   R e p r e s e n t s   a   l i s t   o f   p o s s i b l e   p e r m u t a t i o n s   a p p l i e d   f o r   s o l u t i o n   x i   t o   o b t a i n   s o l u t i o n   x j   F o r   e x a m p l e   :   x i =   1   2   3   4   5   6   7   8   a n d   x j   =   1   8   4   2   7   6   5   3   t h e n   x   x j =   ( 2 ;   8 ) ( 5 ;   7 ) ( 2 ;   3 ) ( 2 ;   4 ) .     4 . 4 . 2 .   M u l t i p l i c a t i o n   o p e r a t i o n       T h i s   o p e r a t i o n   m e a n s   t h a t   a   r a n d o m   n u m b e r   o f   p e r m u t a t i o n   i s   c h o s e n   b e t w e e n   0   a n d   1   i n   o r d e r   t o   a p p l y   i t   t o   a n   o p e r a t i o n .   F o r   e x a m p l e :   R = 0 , 5   a n d     x   x j   =   ( 2 ;   8 ) ( 5 ;   7 ) ( 2 ;   3 ) ( 2 ;   4 ) .   T h e n   R   (x   x j )   =   ( 2 ;   8 ) ( 5 ;   7 ) .     4 . 4 . 3 .   Ad d i t i o n   o p e r a t i o n         T h i s   o p e r a t i o n   i n d i c a t e s   t h a t   t h e   r a n d o m l y   c h o s e n   p e r m u t a t i o n   i s   a p p l i e d   t o   m o v e   f r o m   s o l u t i o n   i   t o   t h e   n e w   s o l u t i o n   j .   F o r   e x a m p l e :   S 1 =   1   2   3   4   5   6   7   8   a n d   R   (x   x j )   =   ( 2 ;   8 )   ( 5 ;   7 )   t h e n   x j =   1   8   3   4   7   6   5   2     4 . 4 . 4 .   T h e   n e i g h b o r h o o d     I n   t h e   c o n t i n u o u s   f o r m u l a   o f   Q A P ,   t h e   o b j e c t i v e   i s   t o   f i n d   a   p e r m u t a t i o n   p   o f   n   e l e m e n t s   t h a t   m i n i m i z e s   t h e   E q u a t i o n   1 ,   w h i c h   u s e s   t h e   f i t n e s s   v a l u e   i n   o r d e r   t o   e v a l u a t e   t h e   s o l u t i o n s .   O n   t h e   o t h e r   h a n d ,   i n   t h e   d i s c r e t e   c o n c e p t ,   w e   c a n   u s e   a n o t h e r   a p p r o a c h   t o   s a y   t h a t   a   s o l u t i o n   i s   c l o s e   t o   a n o t h e r   n e i g h b o r i n g   p e r m u t a t i o n ,   t h e n   t h e   d i f f e r e n c e s   b e t w e e n   t h e   s o l u t i o n s   i n s t e a d   o f   t h e   n e i g h b o r h o o d   b y   t h e   f i t n e s s   v a l u e .     4 . 4 . 5 .   R o o t e r s   m o v e m e n t :   I n   o r d e r   t o   e x p l a i n   w h y   t h e   r o o s t e r   w i t h   t h e   b e t t e r   f i t n e s s   v a l u e   c a n   s e e k   f o r   f o o d   i n   a   l a r g e r   s p a c e   , t h e   b e s t   r o o s t e r s   w i l l   h a v e   t h e   o p p o r t u n i t y   t o   d o   m o r e   p e r m u t a t i o n s   u n t i l   i t   f i n d   a   b e t t e r   s o l u t i o n   t h a n   t h e   o n e   w i t h   l e s s   f i t n e s s   v a l u e ,   a l l o w i n g   t o   s e a r c h   i n   a   w i d e r   n e i g h b o r h o o d .   F o r   t h a t   r e a s o n ,   w e   r e d e f i n e   t h e   o p e r a t i o n   r e p r e s e n t e d   i n   E q u a t i o n   2   b y   t h e   E q u a t i o n   1 1   a s :                 12 ( 0 , ) t t t i i i x x R a n d n x                                                                   ( 1 1 )     I n   a n o t h e r   w a y ,   a   r o o s t e r   m a k e s   a   s e l f - p e r m u t a t i o n   a n d   R a n d n   d e f i n e s   a   r a n d o m   p e r c e n t a g e   o f   p e r m u t a t i o n s   b e t w e e n   0   a n d   2   t o   b e   c h o s e n   i n   o r d e r   t o   a p p l y   i t   i n   t h e   c u r r e n t   s o l u t i o n   ( R o o s t e r   p o s i t i o n ) .   L e t s   i n   t h e   e x a m p l e   a s   b e l o w   t i x b e   t h e   c u r r e n t   r o o s t e r   a n d   1 t i x   i s   t h e   n e w   s o l u t i o n   t h e n 20% R a n d , f u r t h e r m o r e   t h e   c u r r e n t   R o o s t e r   m o v e   t o   t h e   p o s i t i o n   1 t i x . T h e   v a l u e   o f   t h e   p a r a m e t e r   R a n d n   i s   p r o p o r t i o n a l   t o   t h a t   o f   2 w h e r e   2 =   e x p ( d i f f )   a n d   d i f f   i s   t h e   p e r c e n t a g e   o f   d i f f e r e n c e   b e t w e e n   s o l u t i o n s ,   t h u s   t h e   m o r e   t h e   d i f f e r e n c e s   p e r s i s t   b e t w e e n   t h e   c u r r e n t   r o o s t e r   a n d   t h a t   o f   t h e   n e w   p o s i t i o n ,   t h e   m o r e   t h e   p r o b a b i l i t y   o f   a p p l y i n g   p e r m u t a t i o n s   i n c r e a s e s   e x p o n e n t i a l l y ,   w h i c h   m e a n s   t h a t   t h e   r o o s t e r   w i t h   b e t t e r   f i t n e s s   v a l u e s   c a n   g o   t o   t h e   n e w   p o s i t i o n   b y   a p p l y i n g   m o r e   p e r m u t a t i o n s   t h a t   i s   t o   s a y   s e a r c h   i n   a   w i d e r   r a n g e   o f   s p a c e   a n d   t h e   v a l u e   o f   R a n d n   i s   c h o s e n   r a n d o m l y   b e t w e e n   [ 0 , 1 ]   , w h i l e   f o r   t h e   o t h e r   r o o s t e r s   o f   t h e   s w a r m ,   t h e   v a l u e   i s   c h o s e n   r a n d o m l y   b e t w e e n   0   a n d   a   n u m b e r   l e s s   t h a n   1 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2502 - 4 7 5 2   I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i ,   V o l .   11 ,   N o .   3 S e p t e m b e r   2 0 1 8   :     9 2 5     935   930   4 . 4 . 6 .   H e n s   m o v e m e n t   I t   i s   n e c e s s a r y   t o   t a k e   i n t o   c o n s i d e r a t i o n   t h a t   h e n s   s o l u t i o n   m u s t   b e   d i f f e r e n t   t o   t h e   d o m i n a n t   r o o s t e r ,   o t h e r w i s e   i n   t h e   i t e r a t i o n s   t h a t   f o l l o w   a   s e t s   o f   r o o s t e r s   w i l l   m o v e   i n t o   t h e   s a m e   p o s i t i o n s ,   t h e n   t h e   s e a r c h   s p a c e   w i l l   b e   l i m i t e d .   T h e   e q u a t i o n   o f   h e n s   i s   r e d e f i n e d   a s   f o l l o w s :     1 12 1 ( ) 2 ( ) t t t t t t i i r i r i x x S R a n d n x x S R a n d n x x !!                         ( 1 2 )     T h e   f i r s t   p a r t   o f   t h e   E q u a t i o n   1 2   r e p r e s e n t s   t h e   m o v e m e n t   o f   h e n s   f o l l o w i n g   t h e i r   l e a d e r   o f   g r o u p   w i t h   a   w e l l - d e f i n e d   p r o b a b i l i t y ;   t h e   s e c o n d   p a r t   m e a n s   t h a t   h e n s   c o u l d   r a n d o m l y   s t e a l   f o o d   f r o m   o t h e r   c h i c k e n s   ( r o o s t e r s   o r   h e n s ) .     4 . 4 . 7 .   C h i c k s   m o u v e m e n t   I n   t h i s   a d a p t a t i o n ,   t h e   m o v e m e n t   o f   t h e   c h i c k s   i s   d i v i d e d   i n t o   3   s t e p s ,   f i r s t l y   t h e   c h i c k s   w i l l   u s e   a   s e l f - i m p r o v e m e n t   o p e r a t i o n   t o   s e a r c h   f o r   b e t t e r   s o l u t i o n s ,   t h e n   t h e   c h i c k s   w i l l   l o o k   f o r   f o o d   b y   l e a r n i n g   f r o m   t h e i r   m o t h e r s   w h i c h   m e a n s   t h a t   t h e   c h i c k s   w i l l   h a v e   m o r e   p r o b a b i l i t y   o f   r e s e m b l a n c e   b e t w e e n   t h e   c h i c k s   a n d   t h e i r   m o t h e r s .   F i n a l l y ,   t h e   c h i c k s   w i l l   u s e   t h e   s a m e   c o n c e p t   t o   l o o k   f o r   t h e   s o l u t i o n   o f   t h e   d o m i n a n t   r o o s t e r .   T h e   e q u a t i o n   o f   h e n s   i s   r e d e f i n e d   a s   f o l l o w s :     1 ( ) ( ) t t t t t t i i m i r i x W x F L x x C x x !!                           ( 1 3 )     W h e r e   W   i s   a   p a r a m e t e r   o f   s e l f - l e a r n i n g ,   F L   i s   a   l e a r n i n g - F a c t o r ,   w h i c h   m e a n s   t h a t   t h e   c h i c k   l e a r n s   f r o m   i t s   m o t h e r s   a n d   C   i s   a   l e a r n i n g   f a c t o r   a   p a r a m e t e r   o f   r e s e m b l a n c e   b e t w e e n   t h e   c h i c k s   a n d   t h e i r   d o m i n a n t   r o o s t e r ,   w h i c h   m e a n s   t h a t   t h e   c h i c k   c o u l d   l e a r n   f r o m   o f   t h e   r o o s t e r s   t o o .     4 . 5 .   D i s c r e t e   C S O   A l g o r i t h m   C S O - Q A P     T h e   C S O - Q A P   i n   p s e u d o - c o d e   f o r   o p t i m i z i n g   t h e   Q A P   i s   s u m m a r i z e d   a s   f o l l o w s :       D i s c r e t e   C h i c k e n   s w a r m   o p t i m i z a t i o n   a l g o r i t h m   1 .   I n i t i a l i z e   t h e   s i z e   o f   c h i c k e n   p o p u l a t i o n   2 .   G e n e r a t e   a   r a n d o m   p o p u l a t i o n   o f   N   c h i c k e n s   3 .   I n i t i a l i z e   t h e   a l g o r i t h m s   p a r a m e t e r s :   N   t h e   n u m b e r   o f   c h i c k e n s   i n   t h e   s w a r m ,   R a n d ,   r 1   i s   a n   i n d e x   o f   r o o s t e r ;   r 2   i s   a n   i n d e x   o f   c h i c k e n s ,   F L ,   C   a n d   w .   4 .   E v a l u a t e   t h e   f i t n e s s   v a l u e s   a t   t = 0   f o r   e a c h   c h i c k e n   ( s a v e   t h e   g l o b a l   b e s t   s o l u t i o n )   5 .   R a n k   t h e   c h i c k e n s   a n d   e s t a b l i s h   a   h i e r a r c h a l   o r d e r   i n   t h e   s w a r m   6 .   R a n d o m l y   d i v i d e   t h e   s w a r m   i n t o   d i f f e r e n t   g r o u p s   7 .   D e t e r m i n e   t h e   r e l a t i o n s h i p   b e t w e e n   t h e   c h i c k s   a n d   t h e   m o t h e r   h e n s   i n   a   g r o u p .   8 .   F i n d   a   n e w   s o l u t i o n   b y   u p d a t i n g   t h e   p o s i t i o n   o f   e a c h   r o o s t e r ,   h e n s   a n d   c h i c k s   u s i n g   t h e   n e w   e q u a t i o n s .   9 .   U p d a t e   t h e   n e w   s o l u t i o n   w h e n   i t   i s   b e t t e r   t h a n   t h e   p r e v i o u s   o n e .   1 0 .   R e t u r n   t o   s t e p   5   i f   G   i s   r e a c h e d   u n t i l   t h e   m a x i m u m   n u m b e r   o f   i t e r a t i o n s   i s   c h e c k e d   i n .   1 1 .   R e t u r n   r e s u l t s   a n d   v i s u a l i z a t i o n       5.     E X P E R I M E N T A L   R E S U L T S   A N D   D I S C U S S I O N   T h e   p e r f o r m a n c e   o f   t h e   n e w   a l g o r i t h m   i s   e v a l u a t e d   b y   t h e   c o m p u t a t i o n a l   e x p e r i m e n t s   w e r e   p e r f o r m e d   o n   t h e   Q A P   i n s t a n c e s   e x t r a c t e d   f r o m   Q A P L I B   a n d   t e s t e d   2 0   t i m e s   i n   1 0 0   i t e r a t i o n s   f o r   e a c h   i n s t a n c e .   T h e   a l g o r i t h m   w a s   i m p l e m e n t e d   o n   a   D E L L   i n   v i s u a l   s t u d i o   2 0 1 7   u s i n g   t h e   p r o g r a m i n g   l a n g u a g e   C #   a n d   s i m u l a t e d   w i t h   I n t e l ( R )   C o r e ( T M )   i 7 - 6 5 0 0   U   C P U   2 . 5 G H Z   ( 4   C P U s )   2 . 6   G H z   a n d   1 6 . 0 0   G B   o f   R A M   a n d   M i c r o s o f t   W i n d o w s   1 0   P r o f e s s i o n a l   ( 6 4 - b i t )   o p e r a t i n g   s y s t e m .     5 . 1 .   B e n c h m a r k   i n s t a n c e s     I n   o r d e r   t o   e v a l u a t e   t h e   p e r f o r m a n c e   o f   o u r   n e w   a l g o r i t h m ,   w e   t e s t   i t   o n   w e l l - k n o w n   b e n c h m a r k   i n s t a n c e s   o f   Q A P L I B   [ 2 6 ] ,   w e   c h o o s e   a   s e t   o f   5 6   d i f f e r e n t   i n s t a n c e s   a m o n g   t h e   1 3 5   i n s t a n c e s   f r o m   t h e   Q A P L I B ,   t h e n   w e   c o m p a r e   i t s   r e s u l t s   w i t h   t h o s e   o f   t h e   e x i s t i n g   m e t h o d s   i n   l i t e r a t u r e ,   t h e   s i z e   o f   e a c h   i n s t a n c e   i s   i n d i c a t e d   i n   t h e   i n s t a n c e   n a m e .   T h e r e   a r e   m a n y   t y p e s   o f   i n s t a n c e s   i n t e r p r e t i n g   a n d   d e s c r i b i n g   s e v e r a l   r e a l   a n d   r a n d o m   p r o b l e m s .   T h e   f i r s t   t y p e   i s   t h e   i n s t a n c e s   o b t a i n e d   f r o m   a   p r a c t i c a l   Q A P   a p p l i c a t i o n s   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i     I S S N :   2502 - 4 7 5 2       D i s c r e t e   C h i c k e n   S w a r m   O p t i m i z a t i o n   f o r   t h e   Q u a d r a t i c   A s s i g n m e n t   P r o b l e m s   ( S o u k a i n a   C .   B o u r k i   S e m l a l i )   931   R e a l - l i f e   i n s t a n c e s ,   t h e   s e c o n d   i s   t h e   r a n d o m l y   g e n e r a t e d   i n s t a n c e s   w i t h   a   s t r u c t u r e   s i m i l a r   t o   r e a l   l i f e   i n s t a n c e s ,   t h e   t h i r d   a r e   G r i d -   ba s e d   d i s t a n c e   m a t r i x   i n s t a n c e s   a n d   f i n a l l y   t h o s e   i n   w h i c h   t h e   d i s t a n c e s   a r e   c a l c u l a t e d   b y   t h e   M a n h a t t a n   d i s t a n c e .     5 . 2 .   P a r a m e t r i c   a n a l y s i s     I n   o r d e r   t o   c h o o s e   t h e   o p t i m u m   p a r a m e t e r   v a l u e s ,   w e   e x e c u t e   s e v e r a l   t e s t s   o n   c h r 1 2 a   a n d   b u r 2 6 a .   A s   s h o w n   i n   F i g u r e   3 ,   t h e   o p t i m a l   s i z e   o f   t h e   c h i c k e n   s w a r m   s h o u l d   b e   N = 5 0 0 ,   w h i c h   p r o v i d e   a   b e t t e r   c o m p r o m i s e   b e t w e e n   a v e r a g e   o f   B F S   a n d   a v e r a g e   o f   t i m e   f o r   e a c h   r u n   o f   t h e   i n s t a n c e   b u r 2 6 a .   O t h e r w i s e   G = 2   g u a r a n t e e s   c o n v e r g e n c e   o f   t h e   a l g o r i t h m ,   i t   m a y   a c h i e v e   a   g o o d   r e s u l t s   i n   m i n i m u m   a v e r a g e   t i m e   a s   r e p r e s e n t e d   i n   F i g u r e   7   o f   t h e   i n s t a n c e   c h r 1 2 a ,   t h i s   v a l u e   e n s u r e s   t h e   r o b u s t n e s s   o f   t h e   a l g o r i t h m   a n d   g u a r a n t e e s   t h e   r e d i s t r i b u t i o n   o f   t h e   s w a r m .   T h e   n u m b e r   o f   r o o s t e r s ,   h e n s   a n d   c h i c k s   c o u l d   a f f e c t   t h e   r e s u l t s ;   w e   c a n   o b s e r v e   t h a t   t h e   p e r c e n t a g e   o f   r o o s t e r s   m u s t   b e   g r e a t e r   t h a n   t h e   p e r c e n t a g e   o f   h e n s   a s   t h e   p e r c e n t a g e   o f   c h i c k s   t o   e n s u r e   f a s t e r   c o n v e r g e n c e .   I n   F i g u r e   4   R N   s h o u l d   r e p r e s e n t   1 0 %   o f   t h e   p o p u l a t i o n   w i t h   a   p e r c e n t a g e   o f   2 1 %   f o r   t h e   h e n s   a s   a p p e a r s   i n   F i g u r e   5 ,   w h i l e   t h e   r e s t   o f   t h e   s w a r m   w i l l   b e   c h i c k s   r e s p e c t i n g   t h a t   C N = N - RN - H N ,   t h e n   C N = 6 9 %   i n   F i g u r e   6 .   W e   n o t e   t h a t   t h e   g a p   b e t w e e n   6 3   a n d   7 2   g i v e s   b e t t e r   r e s u l t s   f o r   t h e   a v e r a g e   o f   B F S   a n d   t h e   a v e r a g e   o f   t i m e .   T h e   m o v e m e n t   o f   t h e   r o o s t e r s   p r e s e r v e s   t h e   e x p l o r a t i o n ;   o n   t h e   o t h e r   s i d e ,   t h e   m o v e m e n t   o f   h e n s   a n d   c h i c k s   p e r f o r m s   t h e   e x p l o i t a t i o n   o p e r a t i o n s .   M o r e o v e r   , a s   s h o w s   i n   F i g u r e   1 0 ,   t h e   a v e r a g e   o f   B F S   d e c r e a s e s   w h e n   t h e   s e l f - l e a r n i n g   p a r a m e t e r   W   i s   b e t w e e n   0 . 4   t o   0 , 6 ,   t h e n   w e   f o u n d   t h a t   f o r   W = 0 . 5 ,   t h e   c h i c k s   c o u l d   s e a r c h   f o r   t h e   s o l u t i o n   i n   a   l a r g e r   r a n g e   o f   s p a c e   w h i c h   a v o i d   t h e   p r o b l e m   o f   f a l l i n g   i n t o   l o c a l   o p t i m a l .   F u r t h e r m o r e   F L   i s   a   r a n d o m l y   c h o s e n   n u m b e r   b e t w e e n   0 , 4   a n d   1 ,   i t   a l l o w s   t h a t   t h e   c h i c k   c o u l d   l e a r n   f r o m   t h e   m o t h e r   w h i c h   e n s u r e   t h e   r o b u s t n e s s   o f   t h e   a l g o r i t h m ,   i n   F i g u r e   8   w e   s e t   t h e   p a r a m e t e r   F L = 0 . 4 .   E v e n t u a l l y   t h e   c h i c k s   c o u l d   a l s o   l e a r n   f r o m   t h e   l e a d e r   o f   t h e   g r o u p   u s i n g   a   l e a r n i n g   f a c t o r   C   f o r   b e t t e r   r e s u l t s   C = 0 . 7   i n   F i g u r e   9   w h i c h   g u a r a n t e e s   t h e   o p t i m a l   b a l a n c e   o f   i n t e n s i f i c a t i o n   a n d   d i v e r s i f i c a t i o n   f o r   o u r   m e t a h e u r i s t i c .       T a b l e   1 .   T h e   P a r a m e t e r s   v a l u e s   f o r   C S O - Q A P   P a r a m e t e r s   V a l u e s   N   ( p o p u l a t i o n   s i z e )   500   R N   ( N u m b e r   o f   r o o s t e r s )   10%   H N   ( N u m b e r   o f   h e n s )   21%   C N   ( N u m b e r   o f   c h i c k s )   69%   G   ( N u m b e r   o f   t o u r s   t o   u p d a t e   t h e   a l g o r i t h m )   2   C   ( R o o s t e r   l e a r n i n g   f a c t o r )   0 , 7   F L   ( H e n s   l e a r n i n g   f a c t o r )     0 , 4   W   ( s e l f - l e a r n i n g   f a c t o r )   0 . 5           F i g u r e   3 .   T h e   a v e r a g e   t i m e   w h i l e   v a r y i n g   t h e   p o p u l a t i o n   s i z e       F i g u r e   4 .   T h e   a v e r a g e   t i m e   a n d   t h e   a v e r a g e   B F S   w h i l e   v a r y i n g   R N       Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2502 - 4 7 5 2   I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i ,   V o l .   11 ,   N o .   3 S e p t e m b e r   2 0 1 8   :     9 2 5     935   932       F i g u r e   5 .   T h e   a v e r a g e   t i m e   a n d   t h e   p e r c e n t a g e   o f   E R R   w h i l e   v a r y i n g   H N           F i g u r e   6 .   T h e   a v e r a g e   t i m e   a n d   t h e   a v e r a g e   o f   B F S   w h i l e   v a r y i n g   C N         F i g u r e   7 .   T h e   a v e r a g e   o f   B F S   w h i l e   v a r y i n g   t h e   n u m b e r   o f   i t e r a t i o n s   G       F i g u r e   8 .   T h e   a v e r a g e   o f   B F S   w h i l e   v a r y i n g   t h e   l e a r n i n g - f a c t o r   F L           Fi g u r e   9 .   T h e   a v e r a g e   o f   B F S   w h i l e   v a r y i n g   t h e   l e a r n i n g - f a c t o r   C           F i g u r e   1 0 .   T h e   a v e r a g e   o f   B F S   w h i l e   v a r y i n g   t h e   l e a r n i n g - f a c t o r   W         F i g u r e   1 1 .   C o m p a r i s o n   o f   t h e   p e r c e n t a g e   E R R   o f   C S O - Q A P   a n d   S C X       F i g u r e   1 2 .   C o m p a r i s o n   o f   t h e   a v e r a g e   t i m e   o f   C S O - QA P   a n d   S C X     Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i     I S S N :   2502 - 4 7 5 2       D i s c r e t e   C h i c k e n   S w a r m   O p t i m i z a t i o n   f o r   t h e   Q u a d r a t i c   A s s i g n m e n t   P r o b l e m s   ( S o u k a i n a   C .   B o u r k i   S e m l a l i )   933   T a b l e   2.   R e s u l t s   O b t a i n e d   B y   A p p l y i n g   C s o - Q a p   t o   S o m e   Q a p l i b   I n s t a n c e s   N u m   i n s t a n c e   S o p t   B F S   a v g   T b e s t ( s )   T a v g   ( s )   E R R   ( % )   P S D   S u c c   ( % )   1   b u r 2 6 a   5426670   5426670   5432472, 35   8 , 7 9   1 0 , 3 8   0 , 1 0 6 9 2 2 8 4 6   0 , 0 5 4 0 0 8 6 1 4   5   2   b u r 2 6 b   3 817852   3817852   3821399, 6   5 , 4 7   9 , 4 1   0 , 0 9 2 9 2 1 3 6   0 , 1 0 3 1 6 6 5 9 1   20   3   b u r 2 6 c   5426795   5426795   5427660, 7   6 , 6 7   9 , 8 9   0 , 0 1 5 9 5 2 3 2 5   0 , 0 1 2 4 2 3 5 5 5   15   4   b u r 2 6 d   3821225   3821239   3821555, 25   9 , 5 5   1 0 , 0 2   0 , 0 0 8 6 4 2 5 1 6   0 , 0 0 7 2 0 8 0 4 5   0   5   b u r 2 6 e   5386879   5386879   5387692, 05   7 , 8 6   1 0 , 2 6   0 , 0 1 5 0 9 3 1 5 5   0 , 0 0 8 3 5 5 2   5   6   b u r 2 6 f   3782044   3782044   3782358, 25   6 , 1 4   9 , 6 5   0 , 0 0 8 3 0 8 9 9 9   0 , 0 0 9 3 4 8 9 6 5   25   7   b u r 2 6 g   10117172   10117172   10118484, 4   7 , 7 2   9 , 7 3   0 , 0 1 2 9 7 2 0 0 4   0 , 0 0 6 4 7 6 5 0 2   5   8   b u r 2 6 h   7098658   7098658   7099200, 15   7 , 8 5   9 , 5 4   0 , 0 0 7 6 3 7 3 5 9   0 , 0 0 5 3 2 4 0 7 4   15   9   c h r 1 2 a   9552   9552   9 6 5 1 , 8   0 , 2 6   1 , 1 2   1 , 0 4 4 8 0 7 3 7   2 , 0 9 9 3 0 5 0 9 8   80   10   c h r 1 5 a   9896   10136   1 0 7 4 6 , 3   2 , 9 9   3 , 1 2   8 , 5 9 2 3 6 0 5 5   3 , 3 2 3 6 5 1 6 9   0   11   c h r 1 5 b   7990   7990   8 6 8 2 , 5   1 , 6 7   2 , 9 3   8 , 6 6 7 0 8 3 8 5 5   6 , 7 2 7 1 2 7 3 0 2   30   12   c h r 1 8 a   11098   11118   12990   4 , 3 1   4 , 6 7   1 7 , 0 4 8 1 1 6 7 8   6 , 4 0 5 0 7 8 6 0 9   0   13   c h r 2 0c   14142   14142   1 7 2 1 2 , 9   5 , 5 4   6 , 0 9   2 1 , 7 1 4 7 5 0 3 9   1 1 , 6 9 0 8 8 1 7 2   5   14   c h r 2 5 a   3796   4254   4 8 3 5 , 1   9 , 1 9   9 , 4   2 7 , 3 7 3 5 5 1 1 1   4 , 7 5 6 6 3 8 7 2 2   0   15   e l s 1 9   17212548   17212548   17521363, 1   2 , 0 8   4 , 7 4   1 , 7 9 4 1 2 7 7 4 9   1 , 7 8 2 5 6 9 3 2 4   25   16   e s c 1 6 a   68   68   6 8 , 2   0 , 0 5   1 , 1 4   0 , 2 9 4 1 1 7 6 4 7   0 , 8 7 9 7 6 5 3 9 6   90   17   e s c 1 6 b   292   292   292   0 , 0 4   0 , 0 8   0   0   100   18   e s c 1 6 c   160   160   160   0 , 1 5   0 , 5 9   0   0   100   19   e s c 1 6 d   16   16   16   0 , 1 4   0 , 8 1   0   0   100   20   e s c 1 6 e   28   28   28   0 , 1 7   1 , 4 5   0   0   100   21   e s c 1 6 g   26   26   26   0 , 0 7   0 , 7 5   0   0   100   22   e s c 3 2 a   130   146   1 5 4 , 4   1 7 , 8 6   1 8 , 9 1   1 8 , 7 6 9 2 3 0 7 7   2 , 6 4 1 9 7 9 0 2 3   0   23   e s c 3 2 e   2   2   2   0 . 1 6   0 . 2 7   0   0   100   24   e s c 3 2 g   6   6   6   0 , 2 1   0 , 8 4   0   0   100   25   e s c 3 2 h   438   438   4 4 2 , 2   1 0 , 6 5   1 8 , 2 4   0 , 9 5 8 9 0 4 1 1   0 , 5 3 3 2 3 5 0 1 2   10   26   e s c 6 4 a   116   116   1 1 7 , 2   1 4 , 7 8   5 7 , 5 4   1 , 0 3 4 4 8 2 7 5 9   0 , 9 9 5 0 4 2 9 8 5   45   27   h a d 1 2   1652   1652   1 6 5 2 , 7   0 , 1 6   1 , 3 2   0 , 0 4 2 3 7 2 8 8 1   0 , 1 1 0 0 8 2 9 2 7   80   28   h a d 1 4   2724   2724   2724   0 , 3   1 , 0 1   0   0   100   29   h a d 2 0   6922   6922   6 9 3 0 , 5   1 , 7   6 , 2 1   0 , 1 2 2 7 9 6 8 8   0 , 1 0 1 5 6 8 0 8 4   20   30   k r a 3 0 a   88900   90700   9 2 2 3 9 , 5   1 3 , 5 4   1 4 , 4 2   3 , 7 5 6 4 6 7 9 4 2   0 , 8 2 1 4 6 6 7 2 6   0   31   k r a 3 0 b   91420   92690   93568   1 3 , 1 3   1 4 , 1   2 , 3 4 9 5 9 5 2 7 5   0 , 7 7 4 1 8 9 4 0 2   0   32   s t e 3 6a   9526   9974   1 0 2 2 4 , 8   1 8 , 9 7   2 1 , 0 1   7 , 3 3 5 7 1 2 7 8 6   1 , 9 3 2 1 3 0 4 3 7   0   33   t a i 1 2 a   224416   224416   224416   0 , 2 7   0 , 6 4   0   0   100   34   t a i 1 2 b   39464925   39464925   39464925   0 , 1 2   0 , 4 1   0   0   100   35   t a i 1 5 a   388214   388214   3 9 1 4 2 7 , 1   3 , 4 5   3 , 6 4   0 , 8 2 7 6 6 2 0 6 3   0 , 4 6 1 0 6 5 5 4 5   5   36   t a i 1 5 b   51765268   5 1765268   51784256, 4   0 , 4 5   2 , 2 4   0 , 0 3 6 6 8 1 7 3 8   0 , 0 6 6 1 6 6 3 2 6   75   37   t a i 1 7 a   491812   497732   5 0 0 6 9 8 , 7   4 , 4 5   4 , 6 6   1 , 8 0 6 9 3 0 2 9   0 , 4 4 0 2 6 9 7 3 7   0   38   t a i 2 0 a   703482   703482   7 2 2 0 7 1 , 7   5 , 8 1   6 , 4 9   2 , 6 4 2 5 2 6 7 4 6   0 , 7 7 0 2 3 4 1 2 1   5   39   t a i 2 0 b   122455319   122455319   1 2 2 8 0 5 6 6 8 , 4   2 , 7 5   5 , 9 5   0 , 2 8 6 1 0 3 824   0 , 2 1 0 4 8 1 2 3 6   30   40   t a i 2 5 a   1167256   1195890   1207142, 1   9 , 0 7   9 , 5 8   3 , 4 1 7 0 8 2 4 5 7   0 , 4 7 7 6 9 4 8 0 6   0   41   t a i 2 5 b   344355646   344355646   3 4 5 4 3 0 7 6 9 , 7   5 , 5 4   9 , 1 4   0 , 3 1 2 2 1 3 1 6 2   0 , 3 4 0 9 0 7 7 1 8   20   42   t a i 3 0 a   1818146   1875012   1893483, 6   1 1 , 5 6   1 2 , 0 4   4 , 1 4 3 6 4 9 6 3   0 , 4 8 2 2 8 0 2 5 6   0   43   t a i 3 0 b   637117113   638977983   6 4 4 6 5 9 6 8 4 , 1   1 1 , 8 7   3 1 , 9 1   1 , 1 8 3 8 5 9 4 4 2   0 , 8 0 2 9 0 1 5 8 5   0   44   t a i 3 5 a   2422002   2515012   2530168, 5   4 9 , 2 3   5 2 , 4 8   4 , 4 6 5 9 9 5 4 8 6   0 , 3 4 0 3 2 1 4 3 2   0   45   t a i 3 5 b   283315445   284893963   2 8 9 7 6 5 6 9 2 , 6   5 0 , 4 5   5 4 , 1 5   2 , 2 7 6 7 0 1 7 1 7   1 , 6 8 1 2 0 6 1 3 8   0   46   t a i 4 0 a   3139370   3246432   32 8 8 0 1 7 , 1   2 2 , 6 1   3 8 , 8 8   4 , 7 3 4 9 3 4 0 7 9   0 , 5 6 5 0 7 2 5 2 2   0   47   t a i 4 0 b   637250948   637409733   6 6 2 5 1 2 4 4 0 , 4   2 3 , 2 4   2 5 , 7 8   3 , 9 6 4 1 3 5 7 0 3   2 , 2 5 3 3 0 1 5 0 7   0   48   t a i 5 0 a   4938796   5163546   5199574, 5   3 6 , 8 7   3 7 , 7 9   5 , 2 8 0 2 0 3 9 2   0 , 2 9 6 1 1 5 1 6 1   0   49   t a i 5 0 b   458821517   462945371   4 7 2 1 8 9 4 3 4 , 4   3 6 , 5 2   3 7 , 6 1   2 , 9 1 3 5 3 3 2 2 7   1 , 2 0 0 4 4 3 0 0 5   0   50   t a i 6 0 a   7205962   7516098   7597042   5 2 , 2 8   5 9 , 8 7   5 , 4 2 7 1 7 2 6 6 6   0 , 3 6 8 3 0 2 7 8 1   0   51   t a i 6 0 b   608215054   611893551   633742259   5 2 , 3 2   6 2 , 9 7   4 , 1 9 7 0 6 8 9 1 2   2 , 6 1 5 2 2 7 5 5 4   0   52   t a i 6 4 c   1855928   1855928   1857875, 9   4 7 , 0 6   7 5 , 9 2   0 , 1 0 4 9 5 5 5 8   0 , 0 8 4 1 0 8 6 8 6   15   53   t a i 8 0 a   13499184   14155210   14196342, 5   1 0 9 , 6 2   1 1 5 , 6 2   5 , 1 6 4 4 4 9 1 9 9   0 , 1 6 1 3 0 5 3 4 7   0   54   t a i 8 0 b   818415043   845088215   8 6 1 8 4 2 1 8 9 , 4   109   1 1 3 , 1 7   5 , 3 0 6 2 4 9 7 7 8   0 , 6 7 0 8 2 4 5 3 2   0   55   t a i 1 0 0 a   21052466   22064510   22113282, 5   1 9 9 , 2 7   2 0 6 , 5 4   5 , 0 3 8 9 1 8 0 0 6   0 , 1 0 6 3 7 2 3 6 9   0   56   t a i 1 0 0 b   118599 6137   1 2 1 5 7 5 2 0 1 1   1 2 2 8 7 9 6 9 9 1   2 0 4 , 5 7   2 2 0 , 1   3 , 6 0 8 8 5 2 6 9 5   0 , 8 4 1 9 9 6 9 6 2   0       5 . 3 .   D i s c u s s i o n   o f   r e s u l t s   W e   p e r f o r m e d   s e v e r a l   t e s t s   o n   a   s e t   o f   d i f f e r e n t   i n s t a n c e s .   M o r e o v e r ,   t h e   T a b l e   2   s u m m a r i z e s   t h e   n u m e r i c a l   r e s u l t s   o f   t h e   C S O - Q A P   a l g o r i t h m   f o r   5 6   i n s t a n c e s   o f   2 0   r u n s ,   w e   c a n   n o t i c e   t h a t   t h e   o p t i m a l   s o l u t i o n s   i s   f o u n d   i n   6 0 %   o f   t h e   i n s t a n c e s   e s p e c i a l l y   w i t h   s m a l l   s i z e .   T h e   r e s u l t s   i n   T a b l e   2   s u m m a r i z e s   t h e   o b t a i n e d   r e s u l t s   b y   a p p l y i n g   t h e   C S O - Q A P   f o r   5 6   i n s t a n c e s   o f   Q A P L I B   o v e r   2 0   i n d e p e n d e n t   r u n s .   T h e   f i r s t   c o l u m n   i s   t h e   n a m e   o f   i n s t a n c e ;   t h e   S opt   i n d i c a t e d   i n   t h e   c o l u m n   t w o   p r e s e n t   t h e   b e s t   K n o w n   s o l u t i o n   o f   e a c h   i n s t a n c e   i n   t h e   Q A P L I B   d o c u m e n t a t i o n ,   t h e   t h i r d   c o l u m n   p r e s e n t   t h e   b e s t   f o u n d   s o l u t i o n   b y   t h e   C S O - Q A P   ( B F S ) ,   t h e   a v e r a g e   o f   t h e   b e s t   f o u n d   s o l u t i o n   a v g i s   i n d i c a t e d   i n   t h e   f o u r t h   c o l u m n .   T h e   r e m a i n i n g   c o l u m n s   c o n t a i n s   t h e   m e a s u r e s   u s e   t o   p e r f o r m   t h e   q u a l i t y   o f   t h e   s o l u t i o n   w h i c h   a r e :   t h e   b e s t   r u n   t i m e   T b e s t Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2502 - 4 7 5 2   I n d o n e s i a n   J   E l e c   E n g   &   C o m p   S c i ,   V o l .   11 ,   N o .   3 S e p t e m b e r   2 0 1 8   :     9 2 5     935   934   t h e   t i m e   a v e r a g e   T a v g ,   t h e   a v e r a g e   p e r c e n t a g e   o f   e r r o r   E r r   i n   1 6 , t h e   p e r c e n t a g e   o f   t h e   S t a n d a r d   D e v i a t i o n   P S D   i n   1 5   a n d   t h e   l a s t   c o l u m n   i s   t h e   p e r c e n t a g e   t o   g e t   t h e   B F S   ( S u c c ) .   T h e   q u a l i t y   o f   s o l u t i o n   i s   m e a s u r e d   by:   1 )   T h e   p e r c e n t a g e   o f   t h e   S t a n d a r d   D e v i a t i o n   a s :     100 a v g SD P S D                                                ( 1 4 )     W h e r e     20 2 1 20 i a v g i BFS SD                                                                         2 )   T h e   e r r o r   p e r c e n t a g e   i s   c a l c u l a t e d   b y :               ( 1 5 )     100 a v g o p t opt S ERR S          5 . 3 .   C o m p a r i s o n   w i t h   o t h e r   m e t a h e u r i s t i c   W e   c o m p a r e   t h e   a v e r a g e   p e r c e n t a g e   o f   e r r o r   t o   g e t   t h e   b e s t   K n o w n   s o l u t i o n   i n   o u r   p r o p o s e d   w o r k   w i t h   t h e   r e s u l t s   o b t a i n e d   b y   a p p l y i n g   a   s i m p l e   g e n e t i c   a l g o r i t h m   u s i n g   s e q u e n t i a l   c o n s t r u c t i v e   c r o s s o v e r   f o r   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m   [ 2 7 ] .   I n   t h i s   c o n t r i b u t i o n   o f   G e n e t i c   a l g o r i t h m ,   S C X   i s   a p p l i e d   t o   s o l v e   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m   w i t h o u t   u s i n g   t h e   l o c a l   s e a r c h   t o   i m p r o v e   t h e   r e s u l t s ,   t h e r e f o r e   t h e   G A   h a s   b e e n   r u n   o n   a   c o m p u t e r   w i t h   I n t e l ( R )   C o r e ( T M )   i 7 - 3 7 7 0   C P U   @3 . 4 0 G H z   a n d   8 . 0 0   G B   R A M .   F i g u r e   1 1   s h o w s   t h a t   t h e   p r o p o s e d   C S O - Q A P   i s   m u c h   b e t t e r   i n   t e r m   o f   t h e   a v e r a g e   p e r c e n t a g e   o f   e r r o r   t h a n   S C X   i n   t h e   G A   c o n t r i b u t i o n .   F u r t h e r m o r e ,   i n   o r d e r   t o   p r o v e   t h e   r o b u s t n e s s   o f   t h e   a l g o r i t h m ,   F i g u r e   1 2   p r e s e n t s   a   c o m p a r i s o n   b e t w e e n   C S O - Q A P   a n d   S C X   [ 2 7 ] .   T h e   a v e r a g e   o f   t i m e   o b t a i n e d   b y   t h e   C S O - Q A P   i s   a l m o s t   t h e   s a m e   o f   t h e   a v e r a g e   t i m e   o b t a i n e d   b y   S C X   a l g o r i t h m   i n   m o s t   o f   Q A P L I B   i n s t a n c e s   e s p e c i a l l y   i n   s m a l l   i n s t a n c e   a s   s h o w s   i n   F i g u r e   1 0 ;   i t   i s   o b v i o u s   t h a t   C S O - Q A P   m e t h o d   i s   v e r y   e f f e c t i v e   t o   s o l v e   t h e   Q A P   i n s t a n c e s   ( t a i 2 0 a ,   t a i 2 0 b ,   t a i 2 5 a ,   t a i 2 5 b ,   t a i 3 0 a )   i n   a   r e a s o n a b l e   t i m e .       6.   C O N C L U S I O N   I n   t h i s   p a p e r ,   w e   a p p l i e d   c h i c k e n   s w a r m   o p t i m i z a t i o n   ( C S O ) ,   a s   m e t a h e u r i s t i c   f o r   s o l v i n g   t h e   Q A P   w i t h o u t   u s i n g   a   l o c a l   s e a r c h .   W e   c o m p a r e   a s   w e l l   t h e   s o l u t i o n   f o u n d   w i t h   t h e   b e s t - k n o w n   s o l u t i o n ,   w h i c h   i s   i n t r o d u c e d   i n   Q A P L I B .   T h e   r e s u l t s   s h o w   t h a t   t h e   p r o p o s e d   a l g o r i t h m   h a v e   e f f e c t i v e l y   d e m o n s t r a t e d   t h e   a b i l i t y   t o   s o l v e   Q A P   a n d   o b t a i n   a   p r o m i s i n g   r e s u l t s   i n   t e r m s   o f   t h e   q u a l i t y   o f   s o l u t i o n s   a n d   t h e   c o m p u t i n g   t i m e   . T h e   o b t a i n e d   r e s u l t s   a r e   c o m p a r e d   w i t h   t h e   S C X   i n   t h e   G A   c o n t r i b u t i o n .   C S O - Q A P   t a k e s   a d v a n t a g e   o f   i n t e n s i f i c a t i o n ,   d i v e r s i f i c a t i o n   a p p r o a c h e s ,   t h e   m o v e m e n t   o f   s e a r c h i n g   f o r   f o o d   c o u l d   b e   s e e n   a s   i n t e n s i f i c a t i o n ,   a n d   t h e   d i v e r s i f i c a t i o n   c o u l d   b e   r e p r e s e n t e d   b y   t h e   r e o r g a n i z a t i o n   o f   t h e   s w a r m .   I n   f u t u r e   r e s e a r c h ,   w e   c a n   c o n d u c t   d i f f e r e n t   c o m p a r i s o n s   b e t w e e n   s e v e r a l   m e t a h e u r i s t i c s   b y   u s i n g   d i f f e r e n t   i n s t a n c e s   o f   Q A P .   W e   c a n   a l s o   a d d   l o w - l e v e l   h e u r i s t i c s   t o   s o l v e   e f f e c t i v e l y   t h e   q u a d r a t i c   a s s i g n m e n t   p r o b l e m   t h e n   w e   w i l l   a i m   t o   a p p l i c a t e   t h e   i m p r o v e d   C S O - Q A P   a l g o r i t h m   i n   o t h e r   c o m b i n a t o r i a l   op t i m i z a t i o n   p r o b l e m s ,   e s p e c i a l l y   f o r   p r o b l e m s   w i t h   h i g h   d i m e n s i o n s .       R E F E R E N C E S   [1]   S he ng - J un  X ue  a nd W u W u.  S c he dul i ng   w orkfl ow  i n c l oud  c om p u t i ng  ba s e d on hy bri d p a rt i c l e  s w a rm  a l g ori t hm Indone s i an J our nal   of  E l e c t r i c al   E ngi ne e r i ng  and Com put e r  Sc i e nc e ,   10(7): 1560 1566,  2012.   [2]   Y a bo  L uo,  M i L i u,  Z hong x i a H a o,  a nd  D ong bo  L i u.  A i m p rove ns g a - i i   a l g ori t hm   for m ul t i - obj e c t i ve  t ra ve l i ng   s a l e s m a p robl e m Indone s i an  J our nal  of  E l e c t r i c al   E ngi ne e r i ng  and Com put e r  Sc i e nc e 12(6): 4413 4418, 2014.   [3]   F a t i m a   S a y ot i M oha m m e E s s a i Ri ffi a nd  H a l i m a   L a ba ni O p t i m i z a t i on  of  m a ke s p a i j ob  s hop   s c he dul i ng   p robl e m   by   g ol de ba l l   a l g ori t hm .   Indone s i an  J o ur nal   of   E l e c t r i c al   E ngi ne e r i ng  and  Com put e r   Sc i e nc e 4(3): 542 547, 2016.   [4]   S a rt a j   S a hni   a nd  T e ofi l G onz a l e z P - c om p l e t e   a p p rox i m a t i on p robl e m s .”   J our nal  of  t he  A CM (J A CM),   23(3): 555 565, 1976.   [5]   Ra i ne E   Burka rd  a nd  F ra nz   Re ndl A   t he rm ody na m i c a l l y   m ot i va t e s i m ul a t i on  p roc e dure   for  c om bi na t ori a l   op t i m i z a t i on p robl e m s E ur ope an J our nal  of  O pe r at i onal  R e s e ar c h 17(2): 169 174, 1984.   Evaluation Warning : The document was created with Spire.PDF for Python.