I n te r n ati o n al   Jo u r n al   o El e c tr i c a l   an d   C o m p u te r   En gi n e e r i n g   (I JEC E )   V o l .   10 ,   N o .   3 J u n e   20 20,   pp .   2484 ~ 2502   IS S N :   2088 - 8708 D O I :   10. 1 1591 / i j e c e . v 10 i 3 . pp2484 - 2502             2484       Jou r n al   h o m e pa ge ht t p: / / i j e c e . i ae s c or e . c om / i nd e x . php / IJ E CE   A p p l y i n g   t h e   b i g   b a n g - b i g   c r u n c h   m e t a h e u r i st i c   t o   l a r g e - s i z e d   o p e r a t i o n a l   p r o b l e m s       Y o u s e K .   Q aw q z e h 1 G h a i th   J ar ad at 2 ,   A l i   A l - Y o u s e f 3 ,   A n m ar   A b u - H am d ah 4 I b r ah i m   A l m ar as h d e h 5 M u tas e m   A l s m ad i 6 M o h am m e d   Tayfo u r 7 ,   K h a l i d   S h ak e r 8 F i r as   H ad d ad 9   1 D e pa r t m e n t   o f   C o m put e r   S c i e nc e   a nd   I nf o r m a t i o n,   C o l l e g e   o f   S c i e nc e - Z ul f i ,   M a j m a a h   U n i v e r s i t y S a udi   A r a b i a   2 , 3 D e pa r t m e n t   o f   C o m put e r   S c i e nc e ,   F a c u l t y   o f   C o m put e r   S c i e nc e   a nd  I nf o r m a t i o T e c hno l o gy ,   J e r a s h   U n i v e r s i t y ,   J o r d a n   4 D e pa r t m e n t   o f   M a na g e m e n t   I nf o r m a t i o S y s t e m ,   C o l l e g e   o f   B us i n e s s ,   T a i ba h   U n i v e r s i t y S a ud i   A r a b i a   5 ,   6 ,   7 D e pa r t m e n t   o f   M a na g e m e n t   I nf o r m a t i o S y s t e m s ,   C o l l e g e   o f   A ppl i e d   S t ud i e s   a nd   C o m m uni t y   S e r v i c e ,   I m a m   A bdul r a hm a n   B i n   F a i s a l   U n i v e r s i t y ,   D a m m a m ,   S a u di   A r a bi a   8 D e pa r t m e n t   o f   C o m put e r   S c i e nc e ,   F a c u l t y   o f   C o m put e r   S c i e nc e   a n I nf o r m a t i o T e c hno l o gy ,   A nba r   U ni v e r s i t y ,   I r a q   9 D e pa r t m e n t   o f   G e ne r a l   c o ur s e s ,   C o l l e g e   o f   A ppl i e d   S t udi e s   a n C o m m uni t y   S e r v i c e ,   I m a m   A bdul r a hm a n   B i n   F a i s a l   U n i v e r s i t y ,   D a m m a m ,   S a u di   A r a bi a       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 d   J un   2 7 ,   201 9   R e v i s e N o v   0 7 ,   2019   A c c e pt e N o v   25,   2019       I t hi s   s t udy ,   w e   p r e s e n t   a i nv e s t i g a t i o o f   c o m pa r i ng   t he   c a p a b i l i t y   of   a   bi g   ba ng - bi g   c r unc m e t a h e u r i s t i c   ( B B B C )   f o r   m a na g i ng   o pe r a t i o na l   pr o bl e m s   i nc l ud i ng   c o m bi na t o r i a l   o pt i m i z a t i o p r o bl e m s .   T he   B B B C   i s   a   pr o duc t   o f     t he   e v o l ut i o t h e o r y   o f   t he   un i v e r s e   i n   phy s i c s   a nd   a s t r o no m y .   T w o   m a i pha s e s   o f   B B B C   a r e   t h e   bi g   ba ng   a nd   t he   b i g   c r unc h.   T he   b i g   b a ng   ph a s e   i nv o l v e s   t he   c r e a t i o o f   a   po pul a t i o o f   r a ndo m   i n i t i a l   s o l ut i o ns ,   w hi l e   i n     t he   b i g   c r unc h   pha s e   t he s e   s o l u t i o ns   a r e   s hr u nk   i nt o   o ne   e l i t e   s o l u t i o e x hi b i t e d   by   a   m a s s   c e nt e r .   T h i s   s t udy   l o o ks   i nt o   t h e   B B B C s   e f f e c t i v e ne s s   i n   a s s i g nm e nt   a nd   s c he du l i ng   p r o bl e m s .   W he r e   i t   w a s   e nha nc e d   by   i nc o r po r a t i ng  a n   e l i t e   po o l   o f   di v e r s e   a nd   hi g h   qu a l i t y   s o l ut i o ns ;   a   s i m pl e   de s c e n t   he ur i s t i c   a s   a   l o c a l   s e a r c m e t ho d;   i m p l i c i t   r e c o m bi na t i o n;   E uc l i d e a n   di s t a nc e ;   d y na m i c   po pul a t i o s i z e ;   a nd   e l i t i s m   s t r a t e g i e s .   T ho s e   s t r a t e g i e s   p r o v i de   a   ba l a nc e d   s e a r c o f   di v e r s e   a n g o o qua l i t y   po pul a t i o n.   T he   i nv e s t i g a t i o i s   c o nduc t e by   c o m pa r i ng   t he   p r o po s e B B B C   w i t h   s i m i l a r   m e t a h e ur i s t i c s .   T he   B B B C   i s   t e s t e o n   t h r e e   di f f e r e nt   c l a s s e s   o f   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 ;   na m e l y ,   qu a dr a t i c   a s s i g nm e n t ,   b i n   pa c ki ng ,   a n j o s ho s c he du l i ng   pr o bl e m s .   W he r e   t he   i nc o r po r a t e d   s t r a t e g i e s   h a v e   a   g r e a t e r   i m pa c t   o n   t h e   B B B C ' s   pe r f o r m a nc e .   E x pe r i m e nt s   s ho w e d   t ha t   t h e   B B B C   m a i nt a i n s   a   g o od  b a l a nc e   be t w e e di v e r s i t y   a nd  qua l i t y   w hi c pr o duc e s   h i g h - qua l i t y   s o l ut i o ns ,   a nd   o ut pe r f o r m s   o t h e r   i de n t i c a l   m e t a he u r i s t i c s   ( e . g .   s w a r m   i nt e l l i g e nc e   a n e v o l ut i o na r y   a l g o r i t hm s )   r e po r t e d   i n   t he   l i t e r a t ur e .   Ke y w or d s :   B i b a n g - b i c r u n c h   m e t a h e u r i s t i c     B i n   pa c ki ng     Co m b i n a t o r i a l   o pt i m i z a t i o n   J ob   s h o s c h e dul i n g     Q ua d r a t i c   a s s i g nm e nt     C opy r i gh t   ©   2020   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e   A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   Y o us e f   K .   Q a w qz e h   D e pa rt m e n t   o f   Co m put e S c i e n c e   a nd  I n f o rm a t i o n ,   M a j m a a h   U ni v e r s i t y ,   M a j m a a h   U ni v e r s i t y   66,   M a j m a a ( A l   Z ul f i ),   1196 2,   S a ud i   A ra b i a ,   K S A .   E m a i l :   y . qa w qz e h @ m u. e du . s a       1.   I N TR O D U C TI O N     O pe r a t i o na l   p r o b l e m s   (O P m a na ge m e n t   i s   a n   i m po r t a n t   c o nc e pt   of   de a l i n w i t c o m pl e r e a l - w o r l i n dus t ri a l   p r o b l e m s   (e . g.   a s s i g nm e n t   a nd   s c h e dul i n g) .   A s   i l l u s t ra t e d   i t h e   l i t e r a t u r e   i n   t h e   p a s t   t hr e e   de c a de s ,   M e t a h e uri s t i c s   po s e s   a   po t e nt i a l   i m pa c t   o n   t a s ks   o f   m a na gi n s uc o pe r a t i o na l   p r o b l e m s .   T h e y   pr o v e t o   be   v e r y   e ff e c t i v e   a n p r o m i s i n t e c hn i que s   i n   i n dus t ri a l   s i m ul a t i o n   m o de l i n (S M ) ,   c o m b i na t o ri a l   o pt i m i z a t i o n   (CO ),   a n d   m a c h i n e   l e a rni n g   (M L ).   T hi s   i s   due   t o   t h e   c a pa b i l i t i e s   o f   a   m e t a h e u r i s t i c   t o   a d a p t   t o   a   p r o b l e m ’s   Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       A ppl y i n t he   bi b ang - b i c r un c m e t ah e ur i s t i c   …  ( Y ous e f   K .   Q aw qz e h )   2485   s pe c i f i c a t i o n s   v i a   pa ra m e t e t u ni n g   a n d   i n p ut / o ut pu t   a na l y s i s .   D ue   t i m e ,   M e t a h e u r i s t i c s   h a v e   b e c o m e   e ve n   m o r e   s o phi s t i c a t e i de a l i ng  w i t l a r ge - s i z e d   p r o b l e m   s c e n a ri o s   o r   ra t h e r   huge   d a t a s e t s .   It   i s   w e l l   k n o w n   t ha t   t h e   d i f f i c ul t y   i n   a c h i e v i n g   a o pt i m a l   s o l ut i o f o r   a n y   o pe r a t i o na l   p r o b l e m ,     i n   m a n y   c a s e s ,   i s   a   c o n s i de r a b l e   c ha l l e n ge .   T h e r e f o r e ,   t h e   l a s t   de c a de   ha s   s e e n   t h e   a ppl i c a t i o n   o f   n u m e r o us   m e t a h e u r i s t i c s   i s o l v i ng  num e r o us   o pe r a t i o na l   p r o b l e m s   s uc h   a s   CO   a n d   M L .   T w o   c l a s s e s   of   m e t a h e u r i s t i c s   a s   m e n t i o n e by   [1 ]   a r e   po pul a t i o n - b a s e a nd  l o c a l   s e a r c h   m e t a h e u r i s t i c s .   G e n e t i c   a l go ri t hm   [2 a nd  t h e   a n t   c o l o n y   o pt i m i z a t i o [3 ]   a r e   a m o n g   t h e   ge n e ra l l y   ut i l i z e d   p o pul a t i o n - b a s e m e t a h e u r i s t i c s   i s o l v i ng  t h e s e   pr o b l e m s .   T h e r e   ha v e   b e e n   c o m p r e h e n s i v e   i n v e s t i ga t i o n s   o po pul a t i o n - b a s e m e t a h e u r i s t i c s .   T hi s   t y pe   o m e t a h e u r i s t i c s   i s   po pul a due   t o   i t s   a b i l i t y   t o   e xpl o r e   s e a r c s pa c e   e xp l o ra t i o n ,   a s i de   f r o m   b e i n g   e a s i l y   c o m b i n e w i t l o c a l   s e a r c m e t h o ds   f o r   i m p r o v i n g   t h e   p r o c e s s   o f   s o l ut i o e xpl o i t a t i o n   [4 ] .   A m o n g   t h e   ge n e r a l   m e t h o ds   o f   l o c a l   s e a r c m e t h o ds   us e o t h e   p r o b l e m   i n c l u de   s i m ul a t e a nn e a l i ng  [5 ]   a nd  t a b u   s e a r c [6 ] T h e i r   us a ge   i s   f a c t o r e by   t h e i r   a b i l i t y   i e xpl o i t i ng  t h e   s o l ut i o n   s pa c e .     T h e   s t r e n g t o f   po pul a t i o n - b a s e d   m e t a h e u r i s t i c s   i s   b e i n g   a n c h o r e b y   t h e   a b i l i t y   t o   r e c o m b i n e   s o l ut i o n s   i n   a c qui ri n n e w   o n e s .   W i t hi n   po pul a t i o n - b a s e a l go r i t hm s ,   t h e   r e c o m b i n a t i o n   o f   e l i t e   s o l ut i o n s   i s   i m p l i c i t l y   c o n duc t e d.   T hi s   e n t a i l s   m o v i n g   a n d   s w a ppi n of   a s s i gnm e n t s   w i t hi n   a   s o l ut i o t ha t   de n o t e s     t h e   e xc h a nge   o f   i n f o r m a t i o b e t w e e n   ge n e r a t i o n s   o f   a   go o qua l i t y   s o l ut i o n   [1 ] .   T h i s   r e f e r s   t o   t h e   ge n e r a t i o of   n e w   s o l ut i o n s   v i a   a   di s t ri b ut i o n   o v e r   t h e   s e a r c h   s pa c e   w h i c h   c o m pri s e s   a   f un c t i o n   o f   pr e v i o us   p o pul a t i o n s   t h a t   s i g ni fy   t h e   s e a r c h   e xp e r i e n c e   [1 ] .   M e a n w h i l e ,   i m p l i c i t ’  m e a n s   t ha t   a   s o l ut i o n   i s   i n di r e c t l y   s i gni f i e b y     t h e   a s s i g nm e nt s ’  f i t n e s s   v a l ue s   o r   t h e i r   c o n t ri b ut i o n ’s   v a l ue s   t o   s e a r c h   s uc h   a s   i s o l ut i o c r e a t i o n.   W i t h   i m pl i c i t   r e c o m b i n a t i o n,   [1 ]   s t a t e t ha t   t h e   p r o c e s s   of   s e a r c c o ul c o n duc t   a   gu i de s a m p l i n g   o f   t h e   s e a r c h   s pa c e .   U s i n g   t hi s   r e c o m b i na t i o n   t e c hni que ,   po t e nt i a l   a r e a s   o f   t h e   s e a r c s pa c e   c a b e   e ff e c t i v e l y   l oc a t e [ 1 ] T h e   e xpl i c i t   r e c o m b i n a t i o n   i s   o n e   m o r e   r e c o m b i n a t i o t y pe .   It   i s   e m pl o y e by   t h e   ge n e t i c   a l go r i t hm ,   m e m e t i c   (h y b r i ge n e t i c a l go r i t h m   a s   w e l l   a s   by   s c a t t e r   s e a r c h.   H e r e ,   s t r uc t u r e s o l ut i o n   r e c o m b i n a t i o n   o f   e l i t e   s o l ut i o n s   i s   c o n duc t e d   i a e xpl i c i t   m a nn e r.   T hi s   i n v o l v e s   m ov i n g   o s w a ppi ng   a s s i g n m e n t s   w i t hi a   s o l ut i o t h a t   de n o t e s   t h e   e xc ha n ge   o f   i n f o r m a t i o n   e xc h a nge   b e t w e e n   ge n e r a t i o n s   v i a   o n e   o r   m o r e   r e c o m b i n a t i o o pe r a t o r s   i n c l ud i n m u t a t i o a nd  c r o s s ove r [1 ] .   E xpl i c i t   m e a n s   t ha t   a   s o l ut i o n   i s   di r e c t l y   s i gni f i e b y     t h e   a c t ua l   a s s i g nm e n t   o t h e   s o l ut i o n s ’  a l l o c a t i o a n d   f i t n e s s   v a l ue s .   T h e   s e l e c t i o o f   t h e   s o l ut i o r e c o m b i na t i o n   i s   i n f l ue n c e by   n a t u r e   a s   w e l l   a s   t h e   c o n s t ruc t i o o f   t h e   p r o b l e m   a n d   a l s o   by   t h e   m e t a h e u r i s t i c   c h o s e n .   N o n e t h e l e s s ,   i n   i nt e n s i fy i n t h e   s e a r c h   f o r   s o l ut i o n s   o hi g h e r   qu a l i t y ,   t h e   po pul a t i o n - b a s e m e t a h e u r i s t i c   i s   r e ga rde d   a s   w e a k.   A s   s uc h,   s pe c i a l i z e m e t a h e u r i s t i c s   i n   t h e   s o l ut i o n   s p a c e   e xpl o i t a t i o   (e . g.   hi l l   c l i m b i n g)   i s   ge n e ra l l y   h y b r i di z e d   w i t h   t h e   po pul a t i o n - b a s e m e t a h e u r i s t i c s .   T h i s   i m p r o v e s   t h e   p r o c e s s   of   i nt e n s i f i c a t i o n.   I r e l a t i o t o   t h i s ,   h y b r i di z a t i o n   b e t w e e n   a   po pul a t i o n - b a s e a n o t h e r   l o c a l   s e a r c h   m e t a h e u r i s t i c s   ha s   b e e n   r e c o m m e n de d   i m a n y   s t udi e s   (e . g. ,   [1 ,   4 ,   7]) .   L o c a l   s e a r c m e t a h e u ri s t i c s   c o ul ov e r c o m e   t h e   s h o rt c o m i n ( i t h e   po pul a t i o n - b a s e d)  o f   s o l ut i o n   s pa c e   e xpl o i t a t i o by   i m p r o v i n t h e   qu a l i t y   of  s o l ut i o n   m o r e .   A l s o ,   t o   ge n e ra t e   b e t t e r   pe r f o r m a n c e   of   h y b r i m e t a h e u r i s t i c s ,   t h e   us a ge   o f   e xpl i c i t   m e m o r y   s uc a s   t h e   us e   o f   t h e   e l i t e   po o l ,   c o n t r o l   o s e a r c d i v e r s i t y ,   a n d   dy n a m i c a l l y   m a n i p ul a t i ng   t h e   po pul a t i o s i z e   a r e   a l s o   r e c o m m e nde by   [4 ]   A   g o o pe r f o r m a n c e   c a b e   a t t a i n e d   i f   di v e r s i f i c a t i o a nd  i n t e n s i f i c a t i o n   o f   t h e   s e a r c s t a y   b a l a n c e d.   A s   m e nt i o n e by   [8] ,   a   go o pe r fo r m a n c e   (w . r . t .   c o n s i s t e n c y ,   e ff i c i e n c y ,   e ffe c t i v e n e s s ,   a n d   pe rha ps   ge n e r a l i t y )   c a b e   s e e v i a   t h e   m a i n t e n a n c e   o f   b a l a n c e   b e t w e e n   t h e   s e a rc h ’s   di v e r s i f i c a t i o a nd   i nt e n s i f i c a t i o n .   T h i s   ha s   l e t o   t h e   us e   o f   t h e   b i b a n g - b i c r u n c h   (B B B C)  i o ur  s t u d y .   F ur t h e r ,   t o   a c hi e v e   be t t e r   pe r f o r m a n c e ,   t h e   us e   of   a e l i t e   po o l   c o n t a i n i n g   di v e r s e   s o l ut i o n s   o f   h i g h   qua l i t y   for   c o nt r o l l i ng  t h e   s e a r c h   i n   t e rm s   o f   di v e r s i t y ,   a n d   d y n a m i c   m a n i pu l a t i o n   o f   t h e   s i z e   o f   t h e   po pul a t i o n ,   a r e   a l s o   re c o m m e n de d   c o n s i de r e b y   [4 ] .   A s   de m o n s t r a t e i n   t h e   w o r ks   o f   [9,   10] ,   t h e   B BB c o m pri s e s   h y b r i di z a t i o w i t s o m e   m e c h a ni s m s   o f   di v e r s i f i c a t i o n     a n i n t e n s i f i c a t i o f o r   i m p r o v i n g   i t s   s o l ut i o n   s p a c e ’s   e xpl o r a t i o a nd  e xpl o i t a t i o o f   t h e ,   w h e r e ,   a n   e l i t e   po o l   a n a   l o c a l   s e a r c w e r e   us e i n   c o m b i n a t i o n   f o r   i nt e n s i fy i n t h e   s e a r c h   a r o und  e l i t e   s o l ut i o n s ,   w i t   t h e   di v e r s i t y   l e v e l   m a i nt a i n e d.   It   a l s o   po s s e s s e s   a   d y n a m i c   p o pul a t i o n   s i z e   m a ni pul a t i o b e s i de s   t h e   d i v e r s i t y   c o n t r o l   s t r a t e gy .   T h e   e l i t e   po o l   i s   ge n e r a l l y   r e f e r r e t o   a s   a a d a p t i v e   m e m o r y   s t ruc t u r e   c o n t a i n i ng  a   s e t   o f   di v e r s e   a n d   hi g h - qu a l i t y   s o l ut i o n s   t h a t   ke e v a l ua b l e   i n f o r m a t i o n   a b o ut   t he   gl o b a l   o pt i m a   i n   t h e   s ha pe   o f   a   di v e r s e   a n e l i t e   s e t   o f   s o l ut i o n s .   U s i n g   t hi s   s t r uc t u r e ,   t h e   p r o c e s s   of   s e a r c c oul d   r e c o m b i n e   s a m pl e s   f r o m   t h e   e l i t e   s e t   a nd  t h i s   a l l o w s   t h e   e xpl o i t a t i o n   o f   v a l ua b l e   i n f o r m a t i o pe rt a i n i ng  t o   t h e   gl o b a l   o pt i m a .   T h e   us e   o f   B BB i n   t hi s   s t udy   i s   f a c t o r e d   by   i t s :   e a s y   i m p l e m e n t a t i o n ,   p r o v i s i o n   o f   a   de t e r m i ni s t i c   c h o i c e   o f   po o l   o f   e l i t e   s o l ut i o n s   b o t qua l i t y   a n d i v e r s i t y   w i s e   w h i c h   c o n duc t s   a   s y s t e m a t i c   n e i g h b o rh o od  s e a r c h   w i t h i t h e   E uc l i de a n   s p a c e ,   pe r f o r m a n c e   of   ps e udo - r a n do m   d i v e r s i f i c a t i o s t r a t e gi e s   f o t h e   c o m b i n a t i o n s   o f   s t r uc t u r e d   s o l ut i o n ,   e v o l ut i o o f   a   r e n e w e d   s t ra t e gy   v i a   t h e   e xpl o i t a t i o o f   a a da pt i v e   m e m o r y   fo r   t h e   p r e s e r v a t i o o f   go o qua l i t y   a nd  di v e r s i t y ,   p r o v i s i o n   of   v a l ua b l e   i n f o r m a t i o o f   e l i t e   o di v e r s e   s o l ut i o n s   e v e n   w i t h o ut   i n i t i a l   e l i t e   po o l ,   s uppo rt   o r e p r e s e n t a t i o n   of   di r e c t   s o l ut i o w i t h i a   E uc l i de a s pa c e   w h i c c a n   b e   m a ni pul a t e e a s i l y ,   c a pa c i t y   i di s t ri b ut i ng  t h e   s e a r c h   ov e r   s e ve r a l   s o l ut i o n s   ra t h e r   t h a o nl y   o n e   s o l ut i o a s   w e l l   a s   t h e   c a p a c i t y   of   qui c k   c o n v e r ge n c e   e v e n   w h e Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   3 J u n e   2 020   :     24 84  -   2 502   2486   m ul t i p l e   l o c a l   m i ni m a   a r e   p r e s e n t   [1 1 ]   w h i c a l l o w s   t h e   s e a r c t o   qu i c kl y   l o c a t e   t h e   e l i t e   s o l ut i o n s   w i t h i di v e r s e   r e gi o n s ,   e l i t i s m   s t ra t e gy   w i t h   a   po o l   o f   o n l y   di v e r s e   s o l ut i o n s   w hi c h   i s   e n o ug f o r   t h e   s o l ut i o s p a c e   e xpl o r a t i o n,   m e a s u r i ng  E uc l i de a di s t a n c e s   f o r   s i m i l a ri t i e s   b e t w e e n   s o l ut i o n s   w h i c h   a s s i s t s   i n   po i n t i n g   t h e   e l i t e   s o l ut i o n s ,   a nd  l e s s   pa ra m e t e r i z e s t r uc t u r e   [11 ]   w h i c m e a n s   f r e e do m   f r o m   i s s ue s   o f   pa r a m e t e t u n i ng.   T h e r e f o r e ,   t hi s   s t udy   a t t e m p t s   t o   f i n a n   a n s w e r   t o   t h e   r e s e a rc h   que s t i o n   D o e s   t h e   di v e r s i t y   c o n t r o l   s t ra t e gy   i n   t h e   B BB i s   s uff i c i e n t   e n o ugh  t o   de a l   w i t h   l a rge - s i z e p r o b l e m s ? "   A s   s uc h ,   t hi s   s t udy   a i m s   t o   f ul f i l l   t h e   m a i o b j e c t i v e ,   w h i c i s   T o   t e s t   t h e   pe r f o r m a n c e   o f   BBB i t e r m s   o f   ge n e ra l i t y   a n d   c o n s i s t e n c y ,   o ve r     a   v a ri e t y   of   CO P s   (e . g.   qu a d r a t i c   a s s i g n m e n t ,   b i n   p a c ki n g ,   a n j o b   s h o s c h e dul i n p r o b l e m s a n a g a i n s t   a dv a n c e po pul a t i o n - b a s e m e t a h e u r i s t i c s .   T h e   a rra nge m e nt   o f   t h i s   p a pe r   i s   a s   f o l l ow s :   S e c t i o n   2   h i g h l i g h t s   t h e   s t udy ’s   pr o b l e m s ,   S e c t i o n   di s c us s e s   s e ve r a l   w o r ks   pe r t i n e n t   t o   t h e   s ub j e c t   un de s t udy ,   S e c t i o n   i l l us t r a t e s   t h e   p r o po s e B B - B m e t a h e u ri s t i c   a s   w e l l   a s   i t s   de s i g n,   S e c t i o n   5   e l a b o r a t e s   t h e   o ut c o m e s   of    t h e   e xpe ri m e n t ,   a n d   S e c t i o c o n c l ude s   t h e   s t u dy .         2.   P R O B L EM   S TA TE M EN T   T h i s   s e c t i o n   de m o n s t ra t e s   t h e   p r o b l e m s   c o n s i de r e i n   t h i s   s t u d y   a s   t e s t i ng  p l a t f o r m s   f o r   o u r   B B B C.     2. 1 .     Q u ad r ati c   as s i gn m e n p r o b l e m   ( Q A P )   T h e   Q A P   i s   a   s t a nda r d   a s s i g nm e n t   p r o b l e m   i l o c a t i o t h e o ry ,   a n c a t e go r i z e a s   a N P - h a rd  CO P ,   w h i c w a s   f i r s t   i nt r o duc e by   [ 12 ]   i t h e   c o n t e xt   o f   l o c a t i n " i n d i v i s i b l e   e c o n o m i c   a c t i v i t i e s " .   T h e   t e rm   qua d ra t i c   s t e m s   f r o m   t h e   f o r m u l a t i o o f   t h e   Q A P   a s   a i nt e ge o pt i m i z a t i o p r o b l e m   w i t a   q ua d ra t i c   o b j e c t i ve   f un c t i o [1 ] .   T h e   Q A P   i s   de f i n e b y   [ 13 ]   a s   t h e   p r o b l e m   o f   a s s i g n i n g   a   s e t   o f   f a c i l i t i e s   t o   a   s e t   o f   l o c a t i o n s   w i t h   gi v e n   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 nd  g i v e n   f l o w s   be t w e e n   t h e   f a c i l i t i e s .   T h e   go a l   i s   t o   pl a c e   t h e   f a c ul t i e s   o n   l o c a t i o n s   i n   s uc a   w a y   t h a t   t h e   s um   o f   pr o duc t s   b e t w e e n   f l ow s   a n d   d i s t a n c e s   i s   m i n i m a l .   A   m a t h e m a t i c a l   fo r m u l a t i o o f   t h e   Q A P   i s   s h o w n   i n   (1),   t a ke n   f r o m   [1 3 ] .      G i v e n   f a c i l i t i e s   a n d   l o c a t i o n s ,   t w o   x   m a t ri xe s   A [ a i j a n d   B [b r s ] ,   w h e r e   a i j   i s   t h e   di s t a n c e   b e t w e e n   l o c a t i o n s   i   a n d   j ,   a nd   b r s   i s   t h e   f l o w   be t w e e n   f a c i l i t i e s   a n d   s ,   Ф   i s   a a r b i t r a r y   pe rm ut a t i o o f   t h e   s e t   of   i nt e ge r s   1, . . .   . ,   n   (c o rr e s po n d i n g   t o   a a s s i g nm e nt   o f   f a c i l i t i e s   t o   l o c a t i o n s ) ,   a n d   Ф (i g i v e s   t h e   l o c a t i o o f a c i l i t y   i   i Ф .   B o t h   a   a n d   b   r e p r e s e n t   t h e   c o s t   c o n t ri b ut i o of   s i m ul t a n e o us l y   a s s i gni n f a c i l i t y   i   t o   l o c a t i o n   Ф (i a n d   f a c i l i t y   j   t o   l oc a t i o Ф (j ).   T h e   d a t a s e t s   o w h i c h   w e   w i l l   t e s t   o ur  a l go r i t hm   a r e   t a ke n   f r o m     Q A P L IB   [1 3 ]   b e n c h m a r l i b ra r y .   S o m e   da t a s e t s   s uc h   a s   t h e   e l s   de s c r i b e   di s t a n c e s   b e t w e e n   a   s e t   o f   f a c i l i t i e s   i a   h o s pi t a l   a n t h e   c o rr e s po n d i n p a t i e nt   f l o w s ,   a n t h e   b ur   i s   a m o n s e v e r a l   d a t a s e t s   c o n s i s t i ng  o f   o pt i m i z i n pl a c e m e nt s   o f   a   s e t   o f   l e t t e r s   o a   ke y bo a r d   f o r   s t e n o - t y pi s t s .     F o r   a   de t a i l e d i s c us s i o n   a nd  f o r m ul a t i o n   o f   t h e   Q A P ,   p l e a s e   re fe r   t o   t h e   o r i g i n a l   w o r ks   o f   t h e   fo un de r s   of   Q A P L I B   [1 3 ]   b e n c h m a r k   l i b r a r y   a n t h e   w o r o f   [ 14 ] .   G e ne r a l l y ,   t h e   Q A P   c o n s i s t s   o f   s e v e r a l   d i f f e r e n t   t y pe s   of   da t a s e t s   a nd  t h a t   t h e   p a r t i c ul a r   d a t a s e t s   t y p e   ha s   a   c o n s i de r a b l e   i n f l ue n c e   o t h e   pe r f o r m a n c e   o m e t a h e u r i s t i c s .   A c c o r di ng  t o ,   t h e   d a t a s e t s   o f   Q A P L I B   w h i c w e   us e   i n   t hi s   pa pe c a n   b e   c l a s s i f i e i nt o   f o ur   c l a s s e s :   -   U n s t ruc t u r e r a ndo m l y   ge n e r a t e da t a s e t :   R a n do m l y   ge n e r a t e d   a c c o r di n t o   a   u n i f o r m   di s t ri b ut i o n.   T h e s e   a r e   a m o n g   t h e   h a rde s t   t o   s o l v e .   -   G r i d - b a s e di s t a n c e   m a t ri d a t a s e t :   T h e   di s t a n c e s   a r e   d e f i n e a s   t h e   M a nha t t a n   d i s t a n c e   b e t w e e n     gri po i nt s .   -   R e a l - l i f e   da t a s e t :   S m a l l   s i z e   p r a c t i c a l   a p pl i c a t i o n s   o f   t h e   Q A P .   T h e   f l o w   m a t ri xe s   h a v e   m a n y   z e r o   e nt r i e s   a n t h e   r e m a i ni n g   e nt r i e s   a r e   c l e a rl y   n o t   u n i f o r m l y   di s t r i b ut e d.   -   R e a l - l i f e   l i ke   da t a s e t :   R a n do m l y   ge n e r a t e i n   s uc h   a   w a y   t h a t   t h e   m a t r i x   e nt r i e s   r e s e m b l e   t h e   d i s t r i b ut i o n s   fo un f o r   r e a l - l i f e   pr o b l e m s .   In  t hi s   w o r k,   w e   c o n s i de o n l y   t h e   f i r s t   c l a s s ,   u n s t r uc t u r e d   ra n do m l y   ge n e ra t e i n s t a n c e s .   A i n s t a n c e   o f   t h e   Q A P   ha s   t h e   f o l l o w i n s t ruc t u r e   o f   t hr e e   g r o ups   o f   da t a : ( i p r o b l e m   s i z e ;   a   F i g u r e   t ha t   de t e rm i n e s   t h e   n u m b e r   o f   r o w s   a n d   c o l um n s   o f   l o c a t i o n s   a nd  f a c i l i t i e s   m a t r i xe s ,   ( i i )   d i s t a n c e   m a t ri x;   a   g r o up   o f   l o c a t i o n s ,   a n (i i i )   f l ow   m a t ri x;   a   g r o up   o f   f a c i l i t i e s .                     n   i   n   j   a ij   b Ф ( i (j )     Mi ni m i z e   1   1       Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       A ppl y i n t he   bi b ang - b i c r un c m e t ah e ur i s t i c   …  ( Y ous e f   K .   Q aw qz e h )   2487   2. 2 .     B i n   p ac k i n p r o b l e m   ( B P P )   T h e   B P P   i s   a a s s i g nm e nt   p r o b l e m   i w h i c s e v e r a l   i t e m s   o f   di f fe r e nt   w e i g h t s   m us t   b e   p a c ke i nt s e v e r a l   b i n s   a l l   w i t h   t h e   s a m e   c a p a c i t y .   T h e   a i m   i s   t o   m i ni m i z e   t h e   num b e o f   b i n s   r e qui r e d.   T h e   c l a s s i c a l   o n e - di m e n s i o na l   B P P   i s   s i m i l a t o   t h e   c ut t i n g   s t o c a n t h e   k na ps a c p r o b l e m .   T h e   di f f e r e n c e   i s   t ha t   a l l   t h e   p i e c e s   m us t   b e   p a c ke d,   a nd   a u n l i m i t e d   n u m b e o f   b i n s   a r e   a v a i l a b l e .   A   m a t h e m a t i c a l   f o r m u l a t i o o f   t h e   B P P   i s   s h o w n   i ( 2 ) ,   t a ke f r o m   [15 ] .       (2)     w h e r e   i s   t h e   n u m b e r   o f   pi e c e s   (a n d   t h e r e f o r e   a l s o   t h e   m a xi m u m   a m o unt   o f   b i n s   n e c e s s a r y ),   y i   i s   a   b i n a r y   v a r i a b l e   i n di c a t i ng  w h e t h e r   b i n   i   ha s   b e e n   us e d.   F o r   a   de t a i l e di s c us s i o n   a nd  f o r m u l a t i o o f   t h e   B P P ,   p l e a s e   r e f e r   t o   t h e   o f f i c i a l   w e b s i t e   of   O RL IB   b e n c h m a r k   l i b r a r y .   T h e r e   a r e   t hr e e   g r o ups   o f   be n c hm a r k   p r o b l e m s   a r e   a v a i l a b l e   f r o m   t h e   l i t e ra t u r e   f o r   t h e   o n e - di m e n s i o n a l   b i p a c ki n g   p r o b l e m :   -   T h e   g r o up   o f   O R - L i b r a r y   (c r e a t e a n d   s t u di e d   by   [16 ] )   w h i c c o n s i s t s   o f   t w o   c l a s s e s :   u n i f o r m   (u ni f o r m l y   di s t r i b ut e d)   a n d   t ri p l e t   (b i c a pa c i t y   a n d   i t e m   s i z e   a r e   ge n e ra t e de l i b e ra t e l y ).   -   T h e   g r o up   o f   [ 17 ] .   I t   c o n t a i n s   t hr e e   s e t s .   T h e y   a r e   ge n e ra t e d   b a s e o t h e   num b e o f   t h e   i t e m s ,   b i c a p a c i t y   a n d   t h e   ra n ge s   t ha t   t h e   i t e m s ’  s i z e s   a r e   d ra w f r o m .   T h e   t hi r d   s e t S c h _S e t 3 i s   c o n s i de r e d   t o   b e   a   h a rde pr o b l e m   d a t a s e t   b e c a us e   t h e   i t e m   s i z e   i s   d ra w f r o m   a   v e ry   l a r ge   r a nge   s uc h   t ha t   n o   t w o   i t e m s   ha v e     t h e   s a m e   s i z e .   -   T h e   g r o up  o f   E U RO   S pe c i a l   I nt e r e s t   G r o up  o n   Cut t i n g   a nd  p a c ki n g .   It   r e p r e s e n t s   a   c o l l e c t i o o f   a   di f f i c ul t   da t a s e t   f r o m   a   l a r ge   n u m b e r   o f   t e s t   i n s t a n c e s .   In  t h i s   w o r k,   w e   c o n s i de o n l y   h a r d   i n s t a n c e s   s uc a s   t he   s e c o n d   g r o up  (S c h o l l ’s   t hi r d   d a t a s e t )   t o   t e s t   o ur   B B B C.     2. 3 .     Jo b   s h o p   s c h e d u l i n p r o b l e m   (JS S P )   T h e   J S S P   i s   a   s c h e dul i ng  p r o b l e m   i w h i c n u m b e r   o pe ra t i o n s ,   e a c o f   w h i c m us t   b e   p r o c e s s e o n   e xa c t l y   o n e   o f   a   n u m b e r   o f   m a c hi n e s ,   m us t   b e   s c h e du l e f o r   p r o c e s s i n g.   O pe r a t i o n s   a r e   p a r t i t i o n e i n t o   j o b s   a n t h e   p r o c e s s i n o r de r   o f   o pe r a t i o n s   w i t h i e a c h   j o b   i s   s pe c i f i e a   p ri o r i .   T h e   a i m   i s   t o   m i ni m i z e     t h e   m a ke s pa n .   W h e r e   t h e   m a ke s pa n   i s   t h e   t o t a l   l e n g t h   o t h e   s c h e dul e   w h e a l l   t h e   j ob s   h a v e   f i n i s h e pr o c e s s i n g.   A   m a t h e m a t i c a l   f o r m ul a t i o o f   t h e   J S S P   i s   s h o w i ( 3 ) ,   t a ke f r o m   [1 5 ,   18 1 9 ] .       ( 3)     w h e r e   C m a x   i s   t h e   m a x i m um   c o m pl e t i o n   t i m e   o v e r   a l l   j ob s   (m a ke s pa n).   F o a   de t a i l e d i s c us s i o n   a n d   fo r m u l a t i o o f   t h e   J S S P ,   p l e a s e   r e f e r   t o   [ 1 9 ] ,   a n d   t h e   o f f i c i a l   w e bs i t e   o f   O R L I B .   T h e   s ub j e c t s   o f   Q A P ,   B P P ,   a n d   J S S P ha v e   be e n   w i de l y   r e s e a rc h e d,   a n d   t h e y   a r e   i f a c t   v e r y   c o m m o n   pr o b l e m s   i r e a l - l i f e   a pp l i c a t i o n s .   T h e y   h a v e   b e e n   i n t e n s i v e l y   s t udi e i n   t h e   l i t e r a t u r e   w i t a   l a r ge   num b e o b e n c h m a r k   da t a s e t s   b e i n a v a i l a b l e .   A s   s uc h,   t h e y   o ffe r   a   v e r y   goo pl a t f o r m   f o r   t h e   r e s e a r c h e r s   t o   t e s t     t h e   i m p a c t   o f   m a i nt a i ni n g   a   b a l a n c e   b e t w e e n   d i v e r s i t y   a n d   q ua l i t y   of   s e a r c i t h e   B BB C.   S o ,   t h o s e   s o l ut i o n s   t o   t h e   t hr e e   p r o b l e m s   a n d   a n a l y s e s   w i l l   b e   i m p r o v e i t e rm s   o f   qua l i t y .   T hi s   s t u dy   w i l l   s e l e c t i v e l y   c o m pa r e   t h e   o ut c o m e s   of   o ur   B BB w i t t h e   o ut c o m e s   of   s o m e   m e t ho d s   do c um e n t e i t h e   a pp l i c a b l e   l i t e r a t u r e .       3.   R ELA TED   WO R K S   D i v e r s e   m e t h o do l o gi e s   h a v e   be e n   us e f o r   ha n d l i n g   di f f e r e nt   c a t e go ri e s   o f   CO P s .   T hus ,   t h e   e n s u i n g   s ub s e c t i o n s   w i l l   hi g hl i g ht   s o m e   o f   t h e   m o s t   c o m m o n l y   us e o n e s   a s   w e l l   a s   t h o s e   i nt e r e s t i ng  o n e s .   I t   s h o ul b e   n o t e t h a t   t h e r e   ha s   b e e n   a   w i de   a nd  s uc c e s s f ul   us a ge   of   di v e r s e   t y p e s   of   m e t a h e u r i s t i c s   f o r   Q A P ,   B P P ,   a nd  J S S P   s o l ut i o n.   S o m e h o w ,   t h e   us a ge   o f   t h e   o r i gi na l   B B B w a s   n o t   i de n t i f i e a t   a l l   f o r   t h i s   pu rpo s e .     T h e   l i t e r a t u r e   ha s   p r e s e nt e c o unt l e s s   m e t a h e u r i s t i c s .   A m o ng  t h e m   a r e   f o r   t h e :     3. 1 .     Q A P   N um e r o us   s t ud i e s   a r e   s t i l l   u nde r go i n g   f o r   f o ur   de c a de s   f o r   s ol v i n g   di f f e r e n t   f o r m ul a t i o n s   o f   t h e   Q A P .   F o r   s um m a ri z i n s uc h   a m o u n t ,   s o m e   b r i e f   s ur v e y s   of   s o l ut i o n   m e t h o ds   f o r   Q A P   a r e   p r e s e n t e b y   [2 0 - 22 ]   In  a dd i t i o n,   a   go o c o m pa r i s o n   o f   e vo l ut i o n a r y   a l go r i t hm s   fo r   s o l v i n t h e   Q A P   w a s   c o n duc t e by   [23 ]   F o r   s t udy i n g   e a c h   a l go r i t h m   i a   l i m i t e t i m e   s pa a nd  t o   i t s   s pe e o f   c o n v e r ge n c e ,   [24 ]   p r e s e nt e e xc e l l e nt   e xpe r i m e nt s   o f   t e s t i n G R A S P   w i t pa t h   r e l i n ki ng  a pp r o a c h   f o r   s o l v i n ge n e r a l i z e Q A P .   [3 ]   P r e s e n t e d     a   c u nn i ng  A nt   S y s t e m   w i t h   a   l o c a l   s e a r c a nd  p a r a l l e l i z a t i o n.   [ 6 ]   A pp l i e d   a n   i t e r a t e t a b s e a r c a l go ri t hm   w h i c h   o b t a i n e n e w   b e s t   r e s ul t s   a t   t h e   t i m e .   [25 ]   I n v e s t i ga t e d   t h e   e ff e c t i v e n e s s   o f   ut i l i z i n a   m e m o r y   s t r uc t u r e   of   e l i t e   s o l ut i o n s   i a   t a b s e a r c h   a l go r i t hm .           n   i   y i   Mi ni m i z e   1       Mi ni m i z e   C m a x       Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   3 J u n e   2 020   :     24 84  -   2 502   2488   3. 2 .     B P P   In  t h e   l a s t   t w o   de c a de s ,   m a n y   i nt e n s i v e   s t udi e s   w e r e   pr o po s e d   a n d   p r e s e n t e d   f o r   b o t h   o n e - di m e n s i o na l   a n t w o - di m e n s i o na l   B P P   by   [26 - 29 30 ] .   T r a d i t i o na l   e vo l ut i o n a r y   a l go r i t hm s   h a v e   b e e n   a pp l i e f o r   t h e   B P P   s uc h   a s   a n t   c o l o n y   o pt i m i z a t i o w i t a   l o c a l   s e a r c h   r o ut i ne   of   [31 - 32] ,   a n d   a   ge n e t i c   a l go r i t hm   b y   [33] .   H y pe r - h e u r i s t i c s   h a v e   a l s o   b e e n   a p pl i e d   s uc a s   [34 - 36] A pp l i e a   h y pe r - h e u ri s t i c   f ra m e w o r c a l l e CH A M P   fo r   t h e   o nl i n e   B P P   [33] .   A   u n i f i e h y pe r - h e u r i s t i c   f ra m e w o r i s   de v e l o pe by   [37] .   A   go o s ur v e y   a n c l a s s i f i c a t i o o f   a pp r o xi m a t i o a l go r i t hm s   f o r   t h e   B P P   w e r e   c o n d uc t e by   [38] .   A   h y b r i a l go r i t h m   w a s   de ve l o pe by   [39]   a n d   o b t a i n e d   s upe r i o r e s ul t s   c o m pa r e d   t o   o t h e r s .   T h e i h y b r i a pp r o a c h   ha s   a   m uc h - c us t o m i z e c o n s t r uc t i v e   s c h e m a   t h a t   m e e t s   o n l y   t h e   B P P   s pe c i f i c a t i o n s .   Co nduc t e d   a   de t a i l e e xpe ri m e n t a l   s t udy   o n   t h e   e f fe c t i ve n e s s   of   a   v a r i a b l e   n e i g h b o rh o o s e a r c t e s t e o n   t h e   v a r i a b l e - s i z e B P P   [40] .     3. 3 .     JS S P   T h e   J S S P   ha s   a t t r a c t e d   m a n y   r e s e a r c h e r s   t o   s t udy   a n d   t e s t   t he i a pp r o a c h e s   f o r   m a n y   de c a de s .   S o m e   e xa m pl e s   o f   t h o s e   s t udi e s   a r e   a n t   c o l o n y   o pt i m i z a t i o by   [ 18 ] ,   s c a t t e r   s e a r c h   [4 1] [42]   P r e s e n t e d   a   h y b r i d   po pul a t i o n - b a s e m e t a h e u ri s t i c   c a l l e e l e c t r o m a g n e t i s m - l i ke   fo r   s o l v i n a   s i ngl e   m a c h i n e   s c h e dul i ng  p r o b l e m .   A   h y b r i d   p a r t i c l e   s w a rm   o pt i m i z a t i o w a s   a pp l i e d   by   [43]   t o   a   di f f e r e n t   c l a s s   o f   t h e   p r o b l e m   k n o w n   a s   t h e   f l o w   s h o p.   [44]   P r e s e nt e d   a   h y b r i po pul a t i o n - b a s e a pp r o a c h   f o r   s o l v i n g   t h e   J S S P   w i t a   de t a i l e c o m pa ri s o n   b e t w e e n   a   ge n e t i c   a l go r i t hm   a nd  a   s c a t t e r   s e a r c h .   [4 5]   Co n d uc t e d   a e xc e l l e n t   r e v i e w   pa pe r   f o r   t h e   t y pe s   a n d   s pe c i f i c a t i o n s   o f   j ob   s c h e dul i n p r o b l e m s ,   a s   w e l l   a s   a   c o m pr e h e n s i v e   r e v i e w   of   h e u r i s t i c s   a n d   m e t a h e u r i s t i c s   de ve l o pe t o   s o l v e   t h e   p r o b l e m .   D e s pi t e   t h e   e f fe c t i ve n e s s   a n d   go o r e s ul t s   o f   t h e   a b ov e m e n t i o n e a pp r o a c h e s ,   t h e y   a r e   v e r y   pr ob l e m - s pe c i f i c   w h i c h   m a ke s   i t   ha r t o   a da pt   t o   o t h e p r o b l e m s   w i t h   di f f e r e n t   s o l ut i o n   s t ru c t u r e s .   M o s t   of   t h e m   t e s t e t h e i ge n e ra l i t y   a c r o s s   s e ve r a l   CO P s   o v a r i a b l e   i n s t a n c e s .   T hi s   e n c o ur a ge s   us   t o   t e s t   t h e   ge n e ra l i t y   of   o ur   B BB a s   w e l l .     3. 4 .     D i v e r s i ty  c o n tr o l   s tr at e gy   B a s e o n   t h e   n u m e r o us   m e t h o ds   hi g h l i g ht e p r e v i o us l y ,   i t   c a b e   s a i t h a t   t h e r e   ha v e   be e n   c o un t l e s s   e ffo r t s   o f   s o l v i n t h e   t hr e e   p r o b l e m s   e s pe c i a l l y   v i a   t h e   us e   of   di f fe r e n t   a p p r o a c h e s   i c o m b i n a t i o (h y b r i di z a t i o n ) .   F r o m   a l l   t h e   m e t h o ds   h i g h l i g h t e a b ov e ,   t w o   ke y   pr o pe r t i e s   a r e   s a l i e nt :   ( i F i r s t ,   e m pl oy     a   h e u r i s t i c   m e t h o f o a t t a i ni n g   a i ni t i a l   c a ndi d a t e   s o l ut i o n;   (i i )   s e c o n d,   h y b r i di z e   t h e   m e t a h e u r i s t i c   w i t a n o t h e h e u r i s t i c   m e t h o f o r   i m p r o v i n g   t h e   s o l ut i o du ri n g   t h e   p r o c e s s   o f   i t e r a t i o n.   T h e   i m pl e m e n t a t i o o pri m a r i l y   po pul a t i o n - b a s e h y b r i d i z a t i o h a s   y i e l de c o n s i de r a b l e   i m p r o v e m e n t s   t o w a r ds   t h e   o pt i m a l i t y   of    t h e   s o l ut i o n s .   F o r   i n s t a n c e ,   po pul a t i o n - b a s e m e t h o ds   c o m b i n e w i t h   m ul t i p l e   p h a s e   n e i g h b o rh o o s e a r c h ,   o r   gr e e dy   r a n do m i z e a da p t i v e   s e a r c h ,   o l o c a l   s e a r c h ,   a ppe a t o   b e   f a i r l y   e ffe c t i ve .   A s   s t a t e by   [4 ] s uc h   h y b r i di z a t i o n   i s   t o   e xpa n d   t h e   s t r a t e gy   of   t h e   n e i g h b o rh o o i t h e   po pul a t i o n - b a s e m e t h o d.   F urt h e r,   a n   a da pt i v e   m e m o r y   s t r uc t u r e   m a ke s   up  a   ke y   b ui l di n b l o c of   a e ff i c i e n t   a n e f fe c t i ve   h y b r i m e t a h e u r i s t i c ,   f o r   i n s t a n c e ,   t a b s e a r c a l go ri t hm s   a n d   s c a t t e r   s e a r c h .   T h e   e m p ha s i s   i s   o t h e   n o t i o n s   o m e m o r y ,   i nt e n s i f i c a t i o n   v e r s us   di v e r s i f i c a t i o n ,   a n e xp l o i t a t i o n   v e r s us   e xpl o r a t i o n .   M e m o r y   r e fe r s   t   t h e   i n f o rm a t i o g a t h e r e d   by   t h e   a l go ri t hm   o t h e   o b j e c t i ve   f un c t i o n   di s t ri b ut i o n,   a nd   i s   r e p r e s e n t a b l e   a s   c o m pl e s t r uc t u r e s   i n c l udi ng  s o l ut i o r e c o m b i n a t i o n,   f o r   i n s t a n c e   w i t h i t h e   B BB [9,   10] .   M e a n w h i l e ,   i n t e n s i f i c a t i o e xpl o i t s   t h e   a t t a i n e d   i n f o r m a t i o s o   t ha t   t h e   c u rr e n t   s o l ut i o n s   c a b e   i m p r o v e d.   G e n e r a l l y ,     t h i s   e nt a i l s   a   l o c a l   s e a r c h   r o ut i n e .   A s   f o r   d i v e r s i f i c a t i o n,   i t s   a i m   i s   t o   ga t h e r   f r e s i n f o r m a t i o v i a   s e a r c h     s pa c e   e xpl o r a t i o n.   T h e s e   c o m po n e n t s   (e . g . ,   m e m o r y ,   i nt e n s i f i c a t i o n,   di v e r s i f i c a t i o n ,   e l i t i s m ,   po pul a t i o m a n i p ul a t i o n ,   a n s o l ut i o n   r e c o m b i na t i o n a r e   n o t   a l w a y s   v i s i b l y   di s t i n c t i v e .   T h e y   a r e   a l s o   v e r y   i n t e r de pe nde nt   i   a n   a l go ri t hm .   A s   s uc h ,   i t hi s   s t u dy ,   t h e i a dv a nt a ge s   a r e   us e t hr o ug h   a   c o m pl e s t ruc t u r e   o f   da t a   t ha t   upda t e s   t h e   s e a r c h   i n f o rm a t i o n   i n   a   m o r e   e ff e c t i v e   m a nn e r ,   k n o w n   a s   t h e   e l i t e   po o l .   H e r e ,   t h e   a i m   i s   t o   f ul l y   e xpl o i t     t h e   a d a pt i v e   m e m o r y ;   i n   t h i s   s t udy ,   i t   i s   us e a s   a i m p r o v e m e t h o o f   t h e   a t t a i n e b e s t   s o l ut i o n s   f o l l ow i n t h e   c o m b i n a t i o n s .   I n   t h e   c o n t e xt   o f   t h e   r e l a t i o n s h i ps :   A   po o l   r e f e r s   t o   a   d a t a   s t ruc t u r e   e m pl o y e fo r   ke e pi n g   s e v e r a l   s o l ut i o n s   f o un t o   b e   p o s s i b l e   of   v a l ue   a l l   t hr o ug t he   s e a r c [4 6] .   A   po o l   m e m b e i s   t e r m e d   a e l i t e   s o l ut i o a nd   t h us ,   t h e   e l i t e   po o l   i s   a   n o t i o p r e s e nt a b l e   a s   a a da p t i v e   m e m o r y .   I r e l a t i o t o   t h i s ,   [47]   m a de   us e   of   t h e   n o t i o n   o f   ge n e t i c   a l go ri t hm s   o f   c o m b i n i n s o l ut i o ns   fo r   t h e   ge n e ra t i o n   o f   n e w   s o l ut i o n s   us i n a   t a b s e a r c h   a s   a   p r o c e dur e   f o r   i m p r o v e m e n t .   [48]   E m p l oy e d   t h e   t a b s e a r c h   a n d   u ni f i e t a b s e a r c h .   H e r e ,   i n f e a s i b l e   s o l ut i o n s   a r e   c o n s i de r e v i a   t h e   e xpa n s i o n   o f   t h e   o b j e c t i ve   fun c t i o us i n g   a   pe n a l t y   f un c t i o n   a n d   c o n t i nuo us   di v e r s i f i c a t i o n.   T h e   a pp r o a c t a ke b y   [49]   w a s   l i ke   [48 ,   5 0 ,   51 ] .   A l s o   us i n g   t h e   e l i t e   po o l   c o n c e pt ,   p a r t i c ul a rl y   t h e   G r a nul a r   t a b s e a r c h,   t h e y   l i m i t e d   t h e   s i z e   o f   t h e   n e i gh b o rh o o t hr o ug h   t h e   r e m o v a l   o f   e dge s   f r o m     t h e   g r a p h   t ha t   i s   n o t   l i ke l y   t o   e m e r ge   i a o pt i m a l   s o l ut i o n.   M o s t   o f   t h e   m e t h o ds   h i g hl i g ht e d   i s ub - s e c t i o n s   3 . 1 - 3. 3   c o nt a i s i m i l a s t r uc t u r e s   t o   t h e   e l i t e   po o l ,   e . g.   t h e   r e f e r e n c e   s e t   i t h e   s c a t t e r   s e a r c h   m e t a h e u ri s t i c .   H ow e ve r ,   f o r   t h e   o n e s   c l a ri f i e i t h e i s o l ut i o n   r e p r e s e n t a t i o n s ,   t h e y   do   n o t   e m pl o y   i m pl i c i t   s o l ut i o n   r e c o m b i n a t i o n,   u n l i ke   o ur  B BB C.   T hi s   c o ul b e   a   g r e a t   Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       A ppl y i n t he   bi b ang - b i c r un c m e t ah e ur i s t i c   …  ( Y ous e f   K .   Q aw qz e h )   2489   a dv a n t a ge o us   f e a t ur e   o f   o ur  B BB o ve r   o t h e m e t h o ds   i m a i nt a i ni n g   a   c l e a b a l a n c e   b e t w e e n   d i v e r s i t y   a n qua l i t y   of   t h e   s e a r c h .   [1 52 ]   de m o n s t ra t e t h a t   s o l ut i o n   r e c o m b i n a t i o a n d   a da p t i v e   m e m o r y   i h y b r i d   m e t a h e u r i s t i c s   a r e   e s s e n t i a l   f o r   e ff e c t i v e   pe r fo r m a n c e   i n   t e r m s   o f   qua l i t y   a n d   di v e r s i t y .   T o   be gi w i t h,     t h e   f a s c i n a t i n g   c o n t r i b ut i o n s   o f   t h e   s t udi e s   m e n t i o n e p r e v i o us l y ,   h a v e   a   l i n ka ge   w i t h   t h e   i m p a c t   o   t h e   a s s i g nm e n t .   O n e   w a y   o r   a n o t h e r,   t h i s   m i g h t   i m p a c t   t h e   pe r f o r m a n c e   o e v e n   t h e   s i g n i f i c a n c e   o f   a n   e l i t e   po o l .   O w i n t o   t h e i r   us a ge   o n   t h e   s a m e   d a t a s e t s ,   a   c o m pa r i s o n   w i l l   b e   m a de   b e t w e e n   s o m e   of   t h e   m e t h o ds   hi g h l i g ht e i s ub - s e c t i o n s   3. 1 - 3. 3   a n d   o u r   B B B C.   T h e   pe r f o r m a n c e   o f   B BB i s o l v i n g   t h e   t hr e e   p r o b l e m s   s h o ul b e   a s s e s s e b e c a us e   i t   w o ul b e   w o r t h w h i l e   t o   do   s o .       4.   A P P LY I N G   T H E   BBB C   T O   O P s   B a s e o n   t h e   f a c t s   a nd  p r o pe r t i e s   m e n t i o n e i s e c t i o 1,   w e   h a v e   i m pl e m e n t e d   o ur  B BB C   m e t a h e u r i s t i c   (f r o m   [ 53 ] )   f o r   m o r e   i n v e s t i ga t i o o f   i t s   c a pa b i l i t i e s   a nd  e f f e c t i v e n e s s .   T h e   B B B i s   c o n s i de r e a s   o n e   o f   t h e   e vo l ut i o n a r y   a l go r i t hm s   w h i c h   a r e   w i de l y   us e f o r   m a na gi ng  O P s   i n c l ud i n CO P s .   H ow e v e r ,     t h e   B BB i s   s t i l l   o b s c ur e t o   a   l a rge   po rt i o o f   t h e   O P s ’  f a m i l y .     4 . 1 .     BBB C   d e s c r i p t i o n   Ini t i a l l y   i nt r o duc e by   [5 4,   55 ] ,   B B - B i s   e s s e n t i a l l y   a   s e a r c a l go r i t hm   i n s pi r e d   by   t h e   u ni v e r s e   e vo l ut i o n   t h e o r y   w h i c h   r e v o l ve s   a r o u n e xpa n s i o n   a n d   s hri n ki ng.   A s   de s c r i b e by   [11 ] ,   t h i s   a l go r i t h m   i s   pri m a r i l y   c h a ra c t e ri z e b y   a   f a s t   s e a r c s pa c e   e xpl o ra t i o a nd  a gg r e s s i v e   e xpl o i t a t i o o f   s o l ut i o n   s p a c e .   T h i s   i s   s i g ni f i e by   t h e   s hri n k i n g   o f   t h e   po pul a t i o i t e r m s   o f   s i z e .   T h e   w o r ks   p r e s e nt e b y   [5 4 ]   a nd   [11 ]   pr o v i de   t h e   de t a i l s .   T hi s   r e s e a r c h   c o m p r i s e s   f u r t h e i n v e s t i ga t i o n   o t h e   e f f e c t   o f   t h e   d i v e r s i t y   c o n t r o l   f o l l ow i n   t h e   i n c l us i o o f   t h e   pe r f o r m a n c e   a n d   ge n e ra l i t y   o f   t h e   B BB C   m e t a h e u r i s t i c   (f r o m   [11] )   b y   h a v i n g   i t   t e s t e d   o l a r ge - s i z e d a t a s e t s   o f   Q A P ,   B P P ,   a n d   J S S P .   F i gu r e   1   w h i c c o m pri s e s   a   ge n e ri c   ps e udo - c o de   of   o ur   B B - B C   c a b e   r e f e r r e d .   T h e r e   a r e   m a n y   o t h e r   m e t h o ds   i n s p i r e by   na t u r e   t ha t   ha v e   be e n   a pp l i e d   t o   t h e   Q A P ,   B P P ,   a n J S S P ,   s uc a s   ge n e t i c   a l go r i t hm ,   a n t   c o l o n y   o pt i m i z a t i o n,   p a r t i c l e   s w a rm   o pt i m i z a t i o n,   s c a t t e s e a r c h ,   l o c a l   s e a r c h ,   h y b r i ds ,   a nd  h y pe r - h e uri s t i c s .   T h e   B B - B h a s   b e e a p pl i e d   t o   a   l i m i t e num b e o f   c o m b i n a t o r i a l   o pt i m i z a t i o p r o b l e m s .   F o r   e xa m pl e ,   [ 54 ]   f i r s t   p r o po s e d   a n a ppl i e t h e   o ri gi na l   B BB t o   t h e   t r us s   o pt i m i z a t i o p r o b l e m ,   a n d   c o m pa r e d   i t   a g a i n s t   t h e   ge n e t i c   a l g o r i t hm   (G A )   a nd   a i m p r o v e v e r s i o o f   i t   c a l l e c o m b a t - G A .   T h e y   s h o w e t h a t   t h e   B BB h a d   o ut pe r f o r m e t h e   c o m b a t - G A   i m o s t   o f   t h e   t e s t   f un c t i o n s   i n s t a n c e s   i n   t e rm s   o f   qua l i t y   a nd  s pe e d.   I n   a n o t h e r   w o r k ,   [56 ]   c o m pa r e t h e   B BB t o   pa rt i c l e   s w a rm   o pt i m i z a t i o (P S O ) ,   h a rm o n y   s e a r c (H S a n d   a n t   c o l o n y   opt i m i z a t i o (A CO )   o v e r   t h e   s i z e   o pt i m i z a t i o o s pa c e   t r us s e s .   T h e y   s h o w e t ha t   t h e   pe r f o r m a n c e   o f   t h e   B BB de m o n s t ra t e s   s upe ri o r i t y   ov e r   P S O ,   H S ,   a n d   A CO   i n   c o m put a t i o na l   t i m e   a n d   qu a l i t y   of   s o l ut i o n s .   T h e   BB B w a s   a l s o   a ppl i e t o   s e v e r a l   o pt i m i z a t i o pr o b l e m s ,   s uc h   a s   t a r ge t   t ra c ki n g   f o r   u n de r w a t e v e h i c l e   de t e c t i o n   a n d   t ra c ki n g   [1 1 ] ;   a n d   e n g i n e e ri n g   o pt i m i z a t i o [ 57 ] .   L a t e l y ,   [9]   a p pl i e d   a e nha n c e v e r s i o o f   t h e   B B B t o   s o l ve   c o ur s e   t i m e t a b l i ng  p r o b l e m s ,   w h e r e   i t   o ut pe r f o r m e s e v e r a l   s i m i l a r   m e t h o ds   a n d   s h o w e a   c o n s i s t e n t   a n d   f a s t   c o n v e r ge n c e   t o w a r ds   o pt i m a l i t y .   A c c o r di n g   t o   [10]   t e s t e t h e   s a m e   B B B o n   t hr e e   c l a s s e s   of   CO P s ;   e . g.   v e h i c l e   r o ut i n g,   t ra v e l i n g   s a l e s m a n,   k n a ps a c p r o b l e m s .   I t   p r o v e t h a t   i t   i s   e f f e c t i ve   a n c o n s i s t e nt   i s o l v i n t h e s e   p r o b l e m s   t o pt i m a l i t y   i m o s t   c a s e s .   T h e   B B B h a s   b e e n   a pp l i e d   t w i c e   fo r   t h e   d a t a   c l us t e ri n g   p r o b l e m   by   [ 58 5 9 ] .   It   s h o w e goo pe r f o r m a n c e   a s   w e l l   a s   ge n e r a t e go o qua l i t y   r e s ul t s .           F i gu r e   1.   ge n e ri c   ps e udo   c o de   of   o ur   B B B C   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   3 J u n e   2 020   :     24 84  -   2 502   2490   A s   m e nt i o n e d ,   B BB i s   g r o un de o a   t h e o r y   r e l a t i n t o   u ni v e r s e   e vo l ut i o n   i n   t h e   r e a l m s   o f   ph y s i c s   a n d   a s t r o n o m y .   T h e   t h e o r y   e l uc i da t e s   t h e   c r e a t i o n,   e v o l ut i o a nd  t h e   e n d i n g   o f   t h e   u n i v e r s e .   B BB t h e o r y   c o m pr i s e s   t w o   p h a s e s ,   n a m e l y   t h e   b i b a n g   (B B a n d   t h e   b i c r u n c h   (B C).   T h e   B B   pha s e   c o m pri s e s   a   s e t   o pr o c e dur e s   o f   e n e r gy   di s s i pa t i o i n a t u r e   w i t r e ga rd   t o   d i s o r de ri n g   a nd   r a ndo m n e s s   w h i l e   t h e   B p ha s e   i n v o l ve s   a   p r o c e dur e   t ha t   a r b i t ra r i l y   di s pe n s e s   pa rt i c l e s   a n d   dra w s   t h e s e   p a r t i c l e s   i nt o   a o r de r.   T h e   p ha s e s   o BB   a n B b o t h   s i g n i f y   l a r ge   e xp l o r a t i o n   o f   s e a r c s pa c e   a nd   b e s t   e xpl o i t a t i o n   o f   s o l ut i o n   s p a c e ,   r e s pe c t i v e l y .   T h e   B B   ph a s e   (a . k. a .   e n e r gy   di s s i pa t i o n i n v o l ve s   t h e   ra n d o m   c r e a t i o n   o f   a n   i n i t i a l   po pul a t i o n   o f   fe a s i b l e   s o l ut i o n s ,   a nd  t h i s   i s   a ki t o   G A   i t e rm s   o f   t h e   c r e a t i o o f   a   ra n do m   i n i t i a l   po pul a t i o n .     G ra dua l l y ,   t h e   po pul a t i o n s   ge n e r a t e i n   t h e   B B   pha s e   w i l l   b e   r e duc e i n   t h e   B p ha s e .   S uc h   r e duc t i o i s   f o de c r e a s i n g   t h e   c o m put a t i o na l   t i m e   a n d   a t t a i ni n g   f a s t   c o n v e r ge n c e ,   w hi l e   t h e   s o l u t i o n s   di v e r s i t y   r e m a i n s   t h e   s a m e .   T h e   c o s t   f un c t i o v a l ue   o f   a   s o l ut i o w i t h i t h e   po pul a t i o s i g n i f i e s   a   m a s s ,   a n d   a s   r e m a rke by   [54 ] t h e   b e s t   s o l ut i o n   i s   s i g ni f i e a s   t h e   c e n t e r   o f   m a s s   w h i c h   w i l l   a t t ra c t   o t h e r   s o l ut i o n s .   S uc h   a   s t a t e   i s   a t t ri b ut a b l e   t o   t h e   n o t i o t ha t   s o l ut i o n s   w i t b i gge r   m a s s a r e   a r e   po s s i b l y   m uc h   c l o s e r   t o   t h e   c e nt e o f   t h e   s e a r c h   s p a c e     (t h e   u ni v e r s e ),   o t o   t h e   po i n t   i w h i c t h e   c o n v e r ge n c e   o f   t he   b i c r u n c w i l l   o c c ur.   A c c o r di n t o   [11 ] ,   t h e   B B B s pe c i f i c a l l y   w o r ks   w i t v a ri a b l e   po pul a t i o s i z e ,   f o r   i n s t a n c e ,   s t e l l a ob j e c t s .   B BB c a m a i nt a i s e a r c di v e r s i t y .   T h us ,   t h e   p r o b l e m   o f   b e i n t r a ppe i n   a   l o c a l   o pt i m u m   c a n   b e   pr e v e n t e d   w h i l e   c o n v e r ge n c e   w i t h i a   r e a s o n a b l e   s pe e c a b e   o b t a i n e d   [57 ] .   B BB i s   a ki t o   m e m e t i c   a l go ri t hm s   b ut   t h e r e   i s   n o   c o m b i na t i o o f   s o l ut i o n s   (e . g.   c r o s s ove r i n   B B B C,   w h i l e   t h e   m u t a t i o n   i s   de n o t e d   by   pe r t u r b a t i o n s   o f   s o l ut i o n.   T o   de m o n s t ra t e   t h e   c ha r a c t e ri s t i c s   o f   o ur  B BB C,   a   s um m a ri z e d   c o m pa r i s o b e t w e e n   m e m e t i c ,   o r i g i na l   B BB C,   a n d   o ur  B B B a l go r i t hm s   a r e   hi g hl i g ht e i n   T a b l e   1 .       T a b l e   1 .   A   c o m pa r i s o b e t w e e n   m e m e t i c   a l go ri t hm   a n d   B BBC   F e a t u r e s   T ra d i t i o n a l   M e m e t i c   O ri g i n a l   BBBC   O u BBBC   P o p u l a t i o n   Ch r o m o s o m e s   L a r g e   s i z e   S t e l l a o b j e c t s   L a r g e   s i z e   S t e l l a o b j e c t s   L a r g e   s i z e   Re p ro d u c t i o n   P ro b a b i l i s t i c   s e l e c t i o n   i n   H a m m i n g   s p a c e   P ro b a b i l i s t i c   s e l e c t i o n   i n   E u c l i d e a n   s p a c e   P ro b a b i l i s t i c   s e l e c t i o n   i n   E u c l i d e a n   s p a c e   Co m b i n a t i o n   Ra n d o m i z e d   Cr o s s o v e   a n d   M u t a t i o n   N o ,   M u t a t i o n   i s   a   p e rt u r b a t i o n   N o ,   M u t a t i o n   i s   a   p e rt u r b a t i o n   E v o l u t i o n   S u rv i v a l   o f   t h e   fi t t e s t   S t r o n g e s t   g ra v i t a t i o n a l   p o l e   S t r o n g e s t   g ra v i t a t i o n a l   p o l e   L o c a l   s e a r c h   S i g n i fi c a n t   i n t e n s i fi c a t i o n   S i g n i fi c a n t   i n t e n s i fi c a t i o n   S i g n i fi c a n t   i n t e n s i fi c a t i o n   S e a r c h   u p d a t e   Ra n d o m i z e d   s e l e c t i o n   P s e u d o -   ra n d o m   s e l e c t i o n   P s e u d o - ra n d o m   s e l e c t i o n   M e m o r y   u s e   N o ,   o n l y   t h e   P o p u l a t i o n   p o o l   N o ,   o n l y   t h e   P o p u l a t i o n   p o o l   A d a p t i v e   e x p l i c i t   m e m o r y   (e . g .   e l i t e   p o o l )   S e a r c h   e x p e ri e n c e   L i m i t e d   i n fo r m a t i o n   a b o u t     s o l u t i o n ’s   c o m p o n e n t s   L i m i t e d   i n fo r m a t i o n   a b o u t   s o l u t i o n ’s   c o m p o n e n t s   In fo r m a t i o n   a b o u t   t h e   s o l u t i o n s   c o m p o n e n t s   v i a   t h e   e l i t e   p o o l   D i v e r s i f i c a t i o n   M u t a t i o n   E u c l i d e a n   d i s t a n c e s   E u c l i d e a n   d i s t a n c e s ,   P e rt u r b a t i o n   (D i v e r s e   r e p l a c e m e n t )   In t e n s i f i c a t i o n   S e l e c t i o n ,   Cr o s s o v e r,   R e p l a c e m e n t   Ce n t r e   o f   m a s s   Ce n t r e   o f   m a s s , L o c a l   S e a rc h   S o l u t i o n   r e c o m b i n a t i o n   E x p l i c it   Im p l i c i t   Im p l i c i t       In   e s s e n c e ,   o ur   B B B pr e s e n t e i n   t h i s   s t udy   i s   di s t i n c t   f r o m   t h e   o r i g i n a l   B B B t h a t   [5 4 ]   ha i n t r o duc e d,   p a r t i c ul a rl y   w i t r e s pe c t   t o   i t s   r e p r e s e n t a t i o o f   e xpl o r a t i o a nd  e xp l o i t a t i o p ha s e s   (s o l ut i o n   c o n s t r uc t i o a n d   i m p r o v e m e n t ).   I pa rt i c ul a r,   a a s s e m b l y   of   e l i t e   s o l ut i o n s   f o r   t h e   c r e a t i o n   o f   a   n e w   pr o m i s i n g   po pul a t i o n   i s uc c e s s i v e   BB   p h a s e s   i s   e xpl o i t e i t hi s   s t udy .   H e r e ,   t h e   e l i t e   c o l l e c t i o n   c o m pr i s e s   s o l ut i o n s   o go o qua l i t y .   O n   t h e   o t h e h a nd,   t h e   o r i g i n a l   B B B r e c o n s t ruc t s   n e w   s o l ut i o n s   f r o m   s c ra t c i t h e   c r e a t i o of  t h e   n e w   ge n e ra t i o n.   A l s o ,   v a r i a b l e   n e i g h b o rh o o s t r uc t u r e s   a n s i m p l e   de s c e n t   h e u r i s t i c   (a s   a   l o c a l   s e a r c h a r e   us e i n   t hi s   s t udy ,   O t h e   o t h e ha n d,   [5 4 ]   s c r u t i ni z e d   s o l ut i o n   n e i g h b o r s   e m p l oy i n e i t h e g r e e d y   de s c e n t   o r   s t e e pe s t   de s c e n t .   A dd i t i o n a l l y ,   i n   de t e r m i n i ng  t h e   b o un da ri e s   (a l l o w a b l e   s pa c e of   t h e   s uc c e s s i v e   p o pul a t i o n ,   t h i s   s t udy   e m pl oy s   t h e   qu a l i t y   of   t h e   p r o duc e s o l ut i o n s   a n d   t h e   m i ni m u m   E uc l i de a d i s t a n c e   i r e p r e s e n t i n g   t h e   c e n t e r   o f   m as s ,   t ha t   i s ,   t h e   b e s t   qua l i t y   s o l ut i o n,   a n d   m a xi m u m ,   m i n i m u m   c o s t   v a l ue s   o f   s o l ut i o n s   w i t h i t h e   e l i t e   po o l   w h i c h   c o nt a i n s   s o l ut i o n s   o f   l oc a l   o pt i m a .   Co m pa r a t i v e l y ,   i n   t h e   o r i g i n a l   B B B C,   t h e   po s i t i o n s   o s o l ut i o n s   w h i c a r e   de n o t e b y   t h e   E uc l i de a d i s t a n c e s   a n d   t he   po pul a t i o di s t ri b ut i o n ’s   s t a n d a r d   de v i a t i o a r e   c o m put e r e l a t i v e l y   t o   t h e   c e nt e r   o f   m as s   w i t h i t h e   s e a r c s p a c e ,   a nd  t h e   m a g ni t u de   o f   gra v i t a t i o na l   a t t ra c t i o n   t h a t   i m pa c t s   t h e   po pul a t i o n   t o   c o n v e r ge   t o w a r t h e   c e n t e r   o f   m as s   w i t h i n   t h e   E uc l i de a n   s p a c e   [54 ]   T h e   b o un d a r y   of   t h e   s e a r c s pa c e   w a s   i n i t i a l l y   a s c e r t a i n e u s i ng   t h e   s um m a t i o o f   t h e   E uc l i de a d i s t a n c e s   of  a l l   s o l ut i o n s   w i t hi n   t h e   po pul a t i o n.   S o m e h o w ,   t o   e ff i c i e nt l y   c o n t r o l   n e w   s o l ut i o n s ’  p r o duc t i o n   w i t hi n     a   de s i ra b l e   qua l i t y   l i m i t s   f o r   t h e   c o n v e r ge n c e   t o w a r d   go o qu a l i t y   s o l ut i o n s ,   t h e   m e a s u r e m e n t   o f   t h e   E uc l i de a n   di s t a n c e   o f   t h e   e nt i r e   po pul a t i o i s   a l s o   c o n s i de r e d.     Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       A ppl y i n t he   bi b ang - b i c r un c m e t ah e ur i s t i c   …  ( Y ous e f   K .   Q aw qz e h )   2491   T h e   E uc l i de a di s t a n c e   a s s i s t s   i t h e   de t e rm i na t i o o f   t h e   s e a r c s pa c e ’s   b o un da ri e s   a n d   di s t r i b ut i o n .   A c t ua l l y ,   i B B B C,   t h e   E uc l i de a di s t a n c e   i s   i rr e pl a c e a b l e .   In  o t h e r   w o r ds ,   n o   o t h e d i s t a n c e   m e a s u r e m e nt s ,   fo r   i n s t a n c e ,   t h e   M a nh a t t a n   di s t a n c e ,   c a b e   us e i n   t h i s   c o n t e xt .   N o rm a l l y ,   t h e   d i s t ri b ut i o o f   t h e   n e w   off s pr i n gs   f o r   t h e   s uc c e s s i ve   i t e r a t i o BB   p ha s e   a s   w e l l   a s   i n   BC   p ha s e ,   i s   a r o u n d   t h e   c e nt e r   of   m as s   ( C c   (a s   i [5 4 ] s e e   (4) :         (4)     H e r e ,   C i n ew   de n o t e s   t h e   n e w   p r o duc e s o l ut i o i ;   w h i l e   σ   s i g ni f i e s   a   s t a n da rd  de v i a t i o o f   a   n o r m a l   d i s t r i b ut i o n.   T h e   s t a n da rd  de v i a t i o de c r e a s e s   f o l l ow i n t h e   e l a ps e   o f   i t e ra t i o n s   b a s e o t h e   f o r m ul a   b e l ow   ( 5)  [54 ]         (5)     H e r e ,   r   r e p r e s e n t s   a   r a n do m   n u m b e r   b e t w e e n   [0 , 1] ,   α   de n o t e s   a   r a t e   o f   r e duc t i o o f   t h e   s e a r c s pa c e   s i z e ,   C m a x   a n C m i n   r e p r e s e n t   t h e   e l i t e   po o l ’s   uppe r   a nd  l o w e r   bo un da ri e s   w h i l e   k   r e p r e s e nt s   t h e   n u m b e r   o f   BB   p ha s e   i t e ra t i o n s .   A s   s uc h ,   t h e   p r o duc t i o n   o f   t h e   n e w   off s pr i n g   i s   a c c o r di n t o   ( 4 )   w i t hi n   t h e   uppe r   a n d   l o w e r   l i m i t s .   T h e   p r o duc t i o o f   of fs pr i n gs   i s   v i a   t h e   pe r f o r m a n c e   o f   s o m e   pe r t u r b a t i o n s   t o   t h e   s o l ut i o n s   i t h e   e l i t e   po o l .   It   i s   n e c e s s a r y   t o   ha v e   l o w e r   a nd  uppe b o un d a r i e s   t o   e na b l e   c o n t r o l   t o   t h e   d i s t r i b ut i o o f   s o l ut i o n s .     In  t h i s   pa pe r,   o ur  p r e l i m i n a r y   e xpe r i m e nt s   s h o w e t h a t   r   ha s   n o   s i g n i f i c a n t   i m p a c t   o t h e   p r o c e s s   of   po pul a t i o r e duc t i o n .   T hus ,   i t   i s   t a ke n   o ut   by   h a v i n g   i t s   v a l ue   f i xe t o   1.   In  t h e   l a s t   pa rt   o f   t h e   B p ha s e   s i g ni f i e by   t h e   r e duc t i o o f   t h e   po pul a t i o s i z e   t o   o n e   s o l ut i o n,   a   n e w   ge n e ra t i o i s   c r e a t e f r o m   t h e   e a r l i e r   ge n e ra t i o n s ’  e l i t e   po o l   w i t h   a   s i m i l a po pul a t i o s i z e   ( a s   i t h e   f i r s t   ge n e ra t i o n ) ,   b e gi nni n g   w i t t h e   e a r l i e C c .   H e r e ,   t hr o ug h   s h a ki n gs   pe r f o r m e t o   t h e   s o l ut i o n,   a   n e w   po pul a t i o f r o m   t h e   e l i t e   po o l   i s   r e c r e a t e d   by   t h e   a l go r i t h m   w h e r e   t h e   m a xi m um   a n d   m i n i m u m   o f   t h e   e a r l i e ge n e r a t i o n ’s   s o l ut i o n s   c o s t   v a l ue s   b e c o m e   t h e   l i m i t s   e . g .   b o un de d   w i t h   ( 4 ) .   T h e   i n c l us i o o f   po t e n t i a l   go o qua l i t y   s o l ut i o n s   i s   a s s ur e d   t hr o ug t h e   a l l o w a n c e   o f   a e xt e n de d   l o w e r   b o u n d ,   m e a ni n g   t h a t ,   t h e   e nh a n c e s o l ut i o n s   a r e   a l l   a l l o w e e ve n   t h o s e   o ut s i de   t h e   b o un d ,   w h i l e   t h e   uppe r   l i m i t   i s   l i m i t e s o   t h a t   t h e   o b t a i nm e nt   o f   w o r s e   s o l ut i o n   c a b e   l i m i t e d .     In  t h i s   pa pe r,   o ur  B B B s t a rt s   w i t t h e   c o n s t r uc t i o p ha s e   k n o w n   a s   t h e   B B   p ha s e   o   t h e   di v e r s i f i c a t i o n   p ha s e .   T hi s   p ha s e   c o m pr i s e s   t h e   c o n s t ruc t i o n   o f   a   po pul a t i o n   o f   N pop   p r e l i m i na r y   c a n di da t e   s o l ut i o n s   C i   f r o m   s c ra t c h   ( S t e 1 f o r   t h e   f i r s t   ge n e r a t i o n .   F o r   t h e   s uc c e e di n BC   p ha s e ,   t h e   n e w   po pul a t i o n   i s   c r e a t e d   f r o m   t h e   e l i t e   po o l ,   b ut   t h e   e l i t e   s o l ut i o n s   t h e m s e l v e s   a r e   n o t   i n c l u de i t h e   n e w   po pul a t i o n.   D u ri n t h i s   s t e p,   s h a ki n g   i s   pe r f o r m e t o   s o l ut i o n s   i t h e   po o l   c o n f i ne by   t h e   uppe r   a n d   l o w e r   c o s t   v a l ue s   o f   s o l ut i o n s   w i t h i t h e   e l i t e   po o l .   T a b l e   i l l us t ra t e s   t h e   c o n s t r uc t i v e   h e u ri s t i c s   us e i n   t h e   c o n s t r uc t i o p ha s e .         T a b l e   2 .   Co n s t r uc t i v e   h e u r i s t i c s   us e i o u r   B B B C   P ro b l e m   Co n s t ru c t i v e   H e u ri s t i c   QAP   N e a r e s t   N e i g h b o (N N h e u ri s t i c :   V i s i t   e i t h e t h e   c l o s e s t   n e i g h b o o t h e   s e c o n d   o t h i rd   c l o s e s t   n e i g h b o r s ,   w i t h   a   s e l e c t i o n   p ro b a b i l i t y   o 1 / 3   f o r   e a c h   n e i g h b o r .     BP P   Bi n - o ri e n t e d   F F D + B2 F :   Bi n - o ri e n t e d   (i m p ro v e d f i r s t - f i t - d e c r e a s i n g   ( i t e ra t e d   i t e m s   p a c k i n g   i n t o   t h e   b i n   o f   t h e   s m a l l e s t   i n d e x   w i t h   s u ffi c i e n t   c a p a c i t y w i t h   b e s t - 2 - f i t   (i t e ra t e d   F F D   u n t i l   t h e   b i n   i s   fi l l e d )   J S S P   D i s p a t c h i n g   ( o r   P ri o ri t y Ru l e s :   S h o rt e s t   R e m a i n i n g   P ro c e s s i n g   T i m e   (S R P T );   a n   o p e ra t i o n   w i t h   s h o rt e s t   re m a i n i n g   j o b   p r o c e s s i n g   t i m e .       A l s o ,   du r i ng  t hi s   s t e ( St e 1 ),   m e a s u r e m e nt   i s   m a de   t o   t he   E uc l i de a di s t a n c e s   a m o n g   s o l ut i o n s   w i t h i t h e   po pul a t i o n .   T hi s   i s   f o r   e s t a b l i s hi n g   a   di v e r s i t y   c ont r o l   o v e r   t h e   s e a r c h   a n d   f o r   e s t i m a t i n g   a e l i t e   s o l ut i o i t e r m s   o f   i t s   a t t ra c t i v e n e s s .   H e r e ,   i t   i s   po s s i b l e   t ha t   t h e   d i v e r s i t y   o f   s e a r c i s   b o un de t o   a   c e r t a i de gr e e   b a s e o n   t h e   d i f fe r e n c e s   b e t w e e n   s o l ut i o n s   qu a l i t y   va l ue s .   A s   a e xa m p l e ,   a   di f f e r e n c e   b e t w e e n   t w o   s o l ut i o n s   na m e l y   C i   a nd  C i + 1   i s   de n o t e by   t h e   di f f e r e n c e   o (di s t a n c e   d b e t w e e n   t h e   v a l ue s   o f   f i t n e s s   t h o s e   s o l ut i o n s   ( d   ( C i C i + 1 )   =   f   ( C i ) - f   ( C i + 1 ) ).   W o r de s i m p l y ,   a   l a r ge di f f e r e n c e   b e t w e e n   C i   a nd  C i + 1   de n o t e s   t h e   hi g h e r   p r o b a b i l i t y   of   s o l ut i o n s   t o   e n c i r c l e   e a c h   o t h e r   i n   t h e   f o l l ow i n i t e r a t i o n.   S uc h   o c c urr e n c e   i s   t a ke i nt a c c o un t   s o   t ha t   t h e   s e a r c i s   n o t   di v e r s i f i e d   t o o   m uc h,   a n d   t h us ,   t h e   c o n v e r ge n c e   i s   t o w a r d   s o l ut i o n s   o f   goo d   qua l i t y   e ff e c t i v e l y   a s   w e l l   a s   e f f i c i e n t l y .   S o l ut i o w i t t h e   b e s t   q ua l i t y   w i t t h e   m i n i m u m   E uc l i de a d i s t a n c e ,   a s   t h e   C c   i s   c h o s e n   i t hi s   s t udy .   T h e   m o s t   d i v e r s e   s o l ut i o c o m p r i s e s   a   s o l ut i o w i t a   l a r ge m a x i m u m   di s t a n c e .   S uc a   s o l ut i o m a y   c o n t a i s t r uc t u r e   a nd   f i t n e s s   c o s t s   t ha t   a r e   t o t a l l y   di f f e r e n t   f r o m   t h e   e l i t e   s o l ut i o n s .   T h e   c o m put a t i o o f   E uc l i de a d i s t a n c e s   a m o n g   s o l ut i o n s   i t h e   po pul a t i o a s   s h o w i 6 ,   a s   w e l l   a s   new CC c i  m a x m i n () , 0 1 r C C kk Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   3 J u n e   2 020   :     24 84  -   2 502   2492   t h e   d i s t a n c e s   b e t w e e n   s o l ut i o n s   i t h e   po pul a t i o a n d   s o l ut i o n s   i t h e   e l i t e   po o l   a s   de m o n s t r a t e i 7   a r e     a s   f o l l ow s   (s i m i l a r   t o   [54 7] ):         (6)       w h e r e   i   ϵ  N p o p   { C 1 C 2 …, C N }         (7)       H e r e :   d m i n ( p q de n o t e s   t h e   di s t a n c e   b e t w e e n   e a c h   s o l ut i o n   ( p )   i n   t h e   po pul a t i o n   a nd  e v e r y   s o l ut i o n   ( q p r e s e n t l y   i n   t h e   e l i t e   po o l   (b e s t   qua l i t y   s o l ut i o n s   C b e s t ,   o n e   o m o r e   C c   a l s o   i n c l ude d) .   F o i n s t a n c e ,   a   d i s t a n c e   b e t w e e n   t w o   s o l ut i o n s   i s   s t a t e d   a s   ( f ( p 1 ) - f ( p 2 )),   w h e r e   a   s o l ut i o n ’s   f i t n e s s   v a l ue   (qu a l i t y i s   s ub t ra c t e f r o m     t h e   o t h e r,   w h i l e   t h e   di s t a n c e   b e t w e e n   a   s o l ut i o a n d   a   C c   i s   c om put e d   a s   ( f ( p i ) - f ( q i ))   [7 ] .   T h e   E uc l i de a di s t a n c e   b a s i c a l l y   l oo ks   i n t o   t h e   s qua r e   r o o t   o f   di ff e r e n c e s   b e t w e e n   s o l ut i o n s .   [7]   M e n t i o n e d   t h a t   i t h e   n a t u r e - i n s p i r e a l go ri t hm s ,   t h e   po pul a t i o n   d i v e r s i t y   o r   t h e   s o l ut i o n   s p a c e ’s   de n s i t y   e s t i m a t o r   i s   a s s e s s a b l e   w i t h   t h e   s um   o   t h e   E uc l i de a d i s t a n c e s   b e t w e e n   a   s o l ut i o a n d   w i t t he   r e s t   o f   o t h e s o l ut i o n s   i n   t h e   po pul a t i o a s     a n   a s s e s s m e n t   o f   h o w   m uc t ha t   c a n d i da t e   s o l ut i o c o n t r i b ut e s   t o   t h e   di v e r s i t y .   T h e   a t t ra c t i v e n e s s   o f   a   s o l ut i o n   c o n t a i ni n g   a   m i n i m u m   di s t a n c e   f r o m   t h e   e l i t e   s o l ut i o i s   g r e a t e r   t o w a r t ha t   e l i t e   s o l ut i o n   ( C c ).   O v e r   t i m e ,   o u B B B do c um e n t s   t h e   di v e r s i t y   of   t h e   po pul a t i o n.   T h e   c a l c ul a t i o i t e rm s   o f   ( 6)  c o m pr i s e s   t h e   m i ni m u m   a v e ra ge   di s t a n c e   o f   a   s o l ut i o f r o m   a l l   o t h e s o l ut i o n s   w i t h i t h e   po pul a t i o n,   w h i c i s   a l s o   t e r m e b [6 0 ]   a s   t h e   a v e r a ge   d i s t a n c e   f r o m   a l l   c a n d i da t e   s o l ut i o n s .   I t e r m s   o f   ( 7 ) ,   t h e   c o m put a t i o n   c o m pr i s e s   t h e   m i n i m u m   di s t a n c e   b e t w e e n   a   s o l ut i o i t h e   p o pul a t i o n   a n d   t h e   C c   w h i c i s   a l s o   t e rm e b y   [ 6 0 ]   a s   t h e   di s t a n c e   f r o m   t h e   b e s t   c a n d i d a t e   s o l ut i o o f   t h e   po pul a t i o n .   [ 6 0 ]   F u r t h e r   m e n t i o n e t ha t   t h e   p r o b l e m   o ge t t i n g   t ra ppe d   i l o c a l   o pt i m a   c a a l s o   b e   pr e v e n t e d.   St e p   2   i n v o l ve s   t h e   BC   p ha s e   (i m p r o v e m e n t w hi c i s   a l s o   k n o w n   a s   t h e   i nt e n s i f i c a t i o p h a s e   o   a   l o c a l   s e a r c m o v e .   F i r s t ,   s e v e r a l   n e i g h b o r s   o f   a l l   s o l ut i o n s   i t h e   po pul a t i o pl us   C c   a r e   p r o duc e t hr o ug s i m pl e   pe r t u r b a t i o n s .   T h e   b e s t   of fs pr i n g   w i l l   r e p l a c e   e a c h   s o l ut i o n.   T hi s   r e s ul t s   i b e t t e r   qu a l i t y   s o l ut i o n s   i t h e   f o l l ow i n g   po pul a t i o n,   w h i l e   t h e   di v e r s i t y   of   t h e   s e a r c re m a i n s   t h e   s a m e .   S uc i s   do n e   s o   t h a t   p r e m a t u r e   c o n v e r ge n c e   of   t h e   s e a r c c a n   b e   pr e v e n t e d ,   t ha t   i s ,   t h e   s e a r c h   di v e r s i t y   i s   c o n s e r v e by   t h e   r e t a i ni n s o m e   of  t h e   po o r - qu a l i t y   s o l ut i o n s ,   c o n s i de r i ng   t ha t   s o m e   o f   t h e s e   a r e   t a ke o ut   f r o m   t h e   po pul a t i o t ha t   w e n t   b e y o n t h e   uppe r   b o un d a r y .   T h e   e n t i r e   B BB c y c l e   d e n o t e s   t h e   b a l a n c e   be t w e e n   di v e r s i t y   a n qua l i t y   of   t h e   s e a r c h.   H e r e ,   t h e   BC   p h a s e   (s o l ut i o s p a c e   e xpl o i t a t i o n )   g ra dua l l y   s hri n ks   t h e   po pul a t i o i nt o   a   s i ngl e   e l i t e   s o l ut i o n .   O t h e   o t h e r   ha n d ,   t h e   b i g   b a ng  (s e a r c h   s p a c e   e xpl o ra t i o n )   p r o duc e s   a e n t i r e l y   n e w   po pul a t i o o f   di v e r s e   s o l ut i o n s   f r o m   a m o n g   t h o s e   w i t h i t h e   e l i t e   po o l .   St e p   3   c o m pri s e s   t h e   de t e rm i na t i o n   o f   C c   a c c o r di n t o   t h e   di s c o ve r e b e s t   s o l ut i o n   c o s t   v a l ue   ( C b e s t a n t h e   m i n i m u m   a v e r a ge   d i s t a n c e   f r o m   t h e   r e m a i n de r   o f   t h e   po pul a t i o n .   T h e   us e   o f   a   s i m pl e   de s c e n t   h e u r i s t i c   i s   f o r   a   p r e de f i n e d   n u m b e r   o f   n o n - i m p r o v e m e n t   i t e ra t i o n s   ( S t e p   4 t o   f u r t h e r   i m p r o v e   C c .   M e a n w hi l e ,   St e p   5   i n v o l ve s   c r e a t i ng  a n d   u pda t i n g   t h e   e l i t e   po o l   (c o l l e c t i o n ).   H e r e ,   t h e   b e s t   s o l ut i o n s   C c o f   t h e   e a r l i e ge n e r a t i o n s   a r e   ke pt   w i t hi n   t h e   e l i t e   po o l   a n d   us e a s   r e f e r e n c e   s o l ut i o n s   fo r   t h e   BB   p ha s e   i n   s uc c e e di n g   i t e ra t i o n s .   F i xe d - s i z e   o f   t h e   e l i t e   po o l   i s   us e d   i t h i s   s t udy ;   du r i ng   t h e   f i r s t   i t e ra t i o n ,   s e v e r a l   go o s o l ut i o n s   w e r e   c h o s e t o   b e   a dde i n t o   t h e   po o l .   E v e r y   i t e ra t i o n   t h e   e l i t e   po o l   i s   up da t e d,   a nd  t h i s   i s   do n e   t hr o ug t h e   r e pl a c e m e n t   of    t h e   w o r s t   s o l ut i o c o s t   i t h e   p r e s e n t   C c   a n d   s o l ut i o n s .   A s   c a b e   s e e n   ( 4) ,   t h e   r e duc t i o n   o f   t h e   po pul a t i o n   s i z e   ( St e p   6 )   l e a ds   t o   a   g ra du a l   c o n v e r ge n c e   o f   t h e   s e a r c i nt o   a   s i n g l e   s o l ut i o n .   H e r e ,   po o r   q ua l i t y   s o l ut i o n s   a r o und  C c   a r e   t a ke o ut .   T h e   BC   p ha s e   i s   do n e   o v e r   a n d   o v e r   u n t i l   s i n gul a r i t y   i s   a c h i e v e (i . e . ,   t h e   po pul a t i o n   s i z e   i s   s hr u nk  t o   a   s i n gl e   s o l ut i o n ) .   A   n e w   BB   p ha s e   s t a rt s   a f t e r   t h e   r e duc t i o n   o f   t h e   po pul a t i o n   s i z e   i n t o   a   s i n gl e   s o l ut i o n   i t h e   BC   p ha s e   ( St e p   7 ).   H e r e ,   t h e   f i r s t   s t e p   i s   r e pe a t e d;   a   n e w   po pul a t i o n   i s   p r o duc e f r o m   t h e   e l i t e   po o l   v i a   t h e   a ddi t i o of  e l i t e   s o l ut i o n s   i nt o   t h e   n e w   po pul a t i o n   a n t h e   c r e a t i o n   o f   s e v e r a l   n e i g h b o r s   f r o m   t h e m   f o r   t h e   e s t a b l i s h m e n t   of   t h e   n e w   po pul a t i o n ,   i n s t e a d   o f   c r e a t i n g   n e w   s o l ut i o n s   f r o m   n o t h i ng   a s   w a s   l a i d   do w n   by   [ 51] .   A l l   C c   s o l ut i o n s   (i n   t h e   e l i t e   po o l a r e   i n c l ude i t h e   n e w   po pul a t i o n   i f   t h e   e l i t e   po o l   i s   c o m pl e t e l y   o c c upi e d.   T h e   pu r po s e   of  c o n duc t i n g   t hi s   s t e p   i s   t o   s us t a i a   hi g h e di v e r s i t y   l e ve l   s o   t h a t   p r e m a t u r e   c o n v e r ge n c e   c a b e   a v o i de d.   H ow e ve r ,   i t h e   i ni t i a l   b i g   b a n gs   w h e r e   t h e   e l i t e   po o l   i s   y e t   t o   b e   C c   s o l ut i o n s   o b t a i n e d   f r o m   e a rl i e b i b a n gs ,   c e n t e r s   of   m as s   i t h e   e l i t e   po o l   w e r e   a l l   e xc l ude d   f r o m   t h e   n e w   po pul a t i o n.   T h e   p r o c e s s e s   of   s e a r c i o u r   BB B a r e   do n e   o ve r   a n d   o v e r   unt i l   t h e   s t o ppi n c ri t e r i o i s   s a t i s f i e d.   I n   o t h e r   w o r ds ,   t h e   p r o c e s s e s   w i l l   s t o p   w h e e i t h e t h e   m a xi m um   num b e o f   i t e ra t i o n s   i s   a c h i e v e d,   o w h e n   t h e   b e s t   qu a l i t y   s o l ut i o i s   l o c a t e d.   L a s t l y ,   BB B r e t u rn s   t h e   b e s t - di s c ov e r e s o l ut i o ( St e 8 ).   2 ( , ) ( ) 11 m i n 1 N d C C C C ii ii i   2 ( , ) ( ) m i n 1 n d p q p q ii i  Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       A ppl y i n t he   bi b ang - b i c r un c m e t ah e ur i s t i c   …  ( Y ous e f   K .   Q aw qz e h )   2493   In  t h i s   w o r k,   n e i g h b o rh o o s t r uc t u r e s   ( N s )   a r e   r a ndo m l y   e m pl oy e t o   t h e   e nt i r e   po pul a t i o N p o p C c   i s   i n c l ude (i . e .   i n   S t e 1   a n d   St e 3 ) .   A   nu m b e o f   n e i g h b o r s   a r e   c r e a t e f o r   e ve r y   C c s o l ut i o n   a t   e a c i t e ra t i o n .   H e r e ,   t h e   b e s t   n e i g h b o r   i s   s e l e c t e a s   a   r e p l a c e m e nt   t o   i t s   pa r e n t   s o l ut i o f o r   t h e   e n s ui n g   ge n e r a t i o o f   N n ew p o p T a b l e   3   i l l us t ra t e s   t h e   N s   e m p l oy e i o ur  B BB fo r   e a c h   p r ob l e m .       Tab l e   3 .   P r o b l e m   s pe c i f i c   n e i g h b o rh o o ds   N s   QAP   BP P   J S S P   D e s c ri p t i o n   N 1   S w a p   t h e   l o c a t i o n s   o f   t w o   f a c i l i t i e s   i n   t h e   s a m e   a s s i g n m e n t .   S e l e c t   i t e m s   f ro m   t h e   b i n   w i t h   t h e   l a rg e s t   re s i d u a l   c a p a c i t y   a n d   t ry   t o   s h i f t   t h e m   t o   t h e   re s t   o f   t h e   b i n s .   Re v e rs   a   s e t   o f   j o b s   o f   ra n d o m   l e n g t h   i n   a   m a c h i n e .   N 2   T ra n s f e a   f a c i l i t y   i n   o n e   l o c a t i o n   t o   a n o t h e i n   t h e   s a m e   a s s i g n m e n t .   M o v e   h a l f   t h e   i t e m s   ra n d o m l y   s e l e c t e d   f ro m   t h e   c u rre n t   b i n   t o   a   n e w   b i n   i f   t h e   n u m b e o f   i t e m s   i n   t h e   c u rre n t   b i n   e x c e e d s   t h e   a v e ra g e   i t e m   n u m b e r p e b i n .   S w a p   t w o   j o b s   f ro m   t h e   s a m e   m a c h i n e .   N 3   S w a p   t h e   l o c a t i o n s   o f   t h re e   f a c i l i t i e s   i n   t h e   s a m e   a s s i g n m e n t .   S e l e c t   t h e   l a rg e s t   i t e m   f ro m   t h e   b i n   w i t h   t h e   l a rg e s t   re s i d u a l   c a p a c i t y   a n d   e x c h a n g e   t h i s   i t e m   w i t h   a n o t h e s m a l l e i t e m   (o s e v e ra l   i t e m s   w h o s e   c a p a c i t y   s u m   i s   s m a l l e r)  f ro m   a n o t h e ra n d o m l y   s e l e c t e d   n o n - f u l l y - f i l l e d   b i n .   T ra n s f e a   j o b   f ro m   i t s   p o s i t i o n   i n   o n e   m a c h i n e   t o   a n o t h e p o s i t i o n   i n   t h e   s a m e   m a c h i n e .   N 4   T ra n s f e t w o   f a c i l i t i e s   i n   t w o   l o c a t i o n s   t o   a n o t h e r   l o c a t i o n   i n   t h e   s a m e   a s s i g n m e n t .   S i m i l a t o   N 3 ,   b u t   ra n d o m l y   s e l e c t   t w o   n o n - f u l l y - f i l l e d   b i n s   w i t h   a   p ro b a b i l i t y   p ro p o rt i o n a l   t o   t h e   n u m b e o f   t h e i re s i d u a l   c a p a c i t i e s .   S w a p   t h re e   j o b s   f ro m   t h e   s a m e   m a c h i n e .   N 5   Re v e rs   a   s e t   o f   f a c i l i t i e s   i n   t h e   s a m e   a s s i g n m e n t .   S e l e c t   t h e   b i g g e s t   i t e m   f ro m   a   p ro b a b i l i s t i c a l l y   s e l e c t e d   b i n .     T ra n s f e t w o   j o b s   f ro m   t h e i p o s i t i o n s   i n   o n e   m a c h i n e   t o   a n o t h e p o s i t i o n   i n   t h e   s a m e   m a c h i n e .       A n y   l o c a l   s e a r c r o ut i n e   c a n   b e   e m pl oy e i n   o u r   B B B C.   A   l o c a l   s e a r c h   i s   e m p l oy e t o   i m p r o ve     t h e   qu a l i t y   o f   s o l ut i o n s   b y   e xpl o r i n g   t h e i n e i g h b o rh o o ds   w i t h o ut   s a c r i f i c i n g   t h e   d i v e r s i t y   o f   t h e   s e a r c h .     A   s i m pl e   e xp l o ra t i o o f   s o m e   n e i g h b o rh o o ds   of   a   s o l ut i o (e . g.   s i m pl e   s ha ki ng  o f   a s s i g nm e n t s   i c a s e   o f   Q A P ,   o r   b i n s   i c a s e   o f   B P P ,   o r   m a c hi n e s   i c a s e   o f   J S S P i s   e m pl oy e i t h e   BC   p ha s e ,   a s   i t   m a y   be   s uff i c i e n t   e n o ugh  t o   e s c a pe   t h e   l o c a l   o pt i m a .   T hr o ug o ur   e xpe r i m e n t s ,   w e   ob s e r v e t ha t   e m pl o y i n N s   i T a b l e   3   i s   qu i t e   s uff i c i e n t   a n d   f a s t   t o   e xp l o r e   s o m e   go o n e i g h b o r s   o f   a e l i t e   s o l ut i o n.   G e n e ra l l y ,   t h e   s t r uc t u r e s   o   t h e   n e i g h b o rh o o c o m pr i s e   r e l o c a t i n g   a   r a ndo m l y   c h o s e n   n e i g h b o r   s o l ut i o n   a r o u n o n e   C c ;   s w a ppi ng  t w ra n do m l y   c h o s e n e i g h b o s o l ut i o n s   f r o m   t w o   r a ndo m l y   c h o s e C c ,   a n d   s w a ppi ng   a l l   n e i g h b o s o l ut i o n s   a r o u n t w o   r a ndo m l y   c h o s e n   C c .   A s   a   s ub s t a n t i a l   m e c h a ni s m   i n t e n s i f i c a t i o n ,   a   s i m p l e   de s c e n t   h e uri s t i c   l o c a l   s e a r c h   i s   us e d.   T h i s   i m p r o v e s   t h e   qu a l i t y   of   s o l ut i o n s   a s   t h e i n e i g h b o r hoo ds   a r e   e xpl o r e d   w i t h o ut   f o r e go i n g   t h e   di v e r s i t y   of   t h e   s e a r c h.   I t h e   BC   p ha s e ,   a   s i m pl e   e xp l o r a t i o n   o f   s e ve r a l   n e i g h b o rh o o ds   of   a   s o l ut i o i s   us e d.   F o r   i n s t a n c e ,   s i m pl e   s ha k i n i s   pe r f o r m e d,   s e e   T a b l e   3 .   T hi s   m a y   be   s uff i c i e nt   i n   e s c a pi ng  t h e   l o c a l   o pt i m a .       5.   C O M P U TA TI O N A L   R ES U LTS   A N D   D I S C U S S I O N   O ur  B B B i s   a l s o   c o m p r i s e t o   e xpe ri m e n t   t h e   i m p a c t   o f   us i ng  a e l i t e   po o l   t o ge t h e w i t h   i t s   r e c o m b i n a t i o o f   i m p l i c i t   s o l ut i o n.   T hi s   m e a n s   t ha t   c o m pa ri s o n   w i l l   a l s o   b e   m a de   b e t w e e n   t hi s   m e t h o a n o t h e r s   t ha t   a l s o   e m pl o y   e xpl i c i t   r e c o m b i n a t i o n .   A s   s uc h ,   t he   a i m   o f   t h i s   s t udy   i s   t o   i n v e s t i ga t e   t h e   e ff e c t   of    t h e   e l i t e   po o l   o n   t h e   pe r f o r m a n c e   of   t h e   B BB a n h o w   i t   m a i n t a i n e a   b a l a n c e   b e t w e e n   qua l i t y   a n d i v e r s i t y .   W i t h   t h e   us e   o f   a n   e l i t e   po o l ,   t h e   pe r f o r m a n c e   o f   t h e   B B B m e t a h e u r i s t i c ,   i t e rm s   o f   c o n s i s t e n c y ,   e ff i c i e n c y ,   e ffe c t i ve n e s s   a s   w e l l   a s   a   ge n e ra l i t y ,   i s   e xa m i n e d   by   ha v i n g   t h e   m e t h o t e s t e o n   Q A P ,   B P P ,   a n d   J S S P .     5. 1 .     Ex p e r i m e n ta l   s e tu p   T h e   p a r a m e t e t u ni n g   o f   o ur  B BB i s   a   c o m b i na t o ri a l   p r o b l e m   i t s e l f .   I t   i s   qu i t e   e a s y   t o   f i n   a n   a p p r o xi m a t e   o pt i m um   f o r   a   gi v e n   p a r a m e t e r ,   b ut   s i n c e   t h e y   a r e   a l l   c o rr e l a t e d,   t h e   p r o b l e m   be c o m e s   h a r de r   a n hi g hl y   n o n - l i n e a r.   T h us ,   w e   foc us e o n   t e s t i n di f f e r e n t   ge n e ra l   i m p r o v e m e n t s   f o r   t h e   B B B r a t h e t ha f i n e - t u ni n g   e a c pa ra m e t e i o r de t o   ge t   a   s l i g h t   i m p r o v e m e nt   f o r   a   p a rt i c ul a i n s t a n c e .   It   i s   po s s i b l e   t ha t   b e t t e r   s o l ut i o n s   w o ul b e   f o un by   us i n a   s e t   o f   i n s t a n c e - de pe n de n t   p a ra m e t e r s .   H ow e v e r ,   o ur   a i m   i s   t o   de s i g n   a   r o b us t   s o l v e r   t h a t   i s   a b l e   t o   e ff i c i e n t l y   s o l ve   a   l a r ge   v a r i e t y   of   i n s t a n c e s .   T o   t e s t   t h e   c o n s i s t e n c y   of   o ur   B B B C,   i t   w a s   ru 10   t i m e s   f o r   e v e r y   i n s t a n c e   f r o m   e a c b e n c h m a r k   da t a s e t   w i t a   n u m b e r   o f   i t e r a t i o n s   a s   a   s t o ppi n g   r e qui r e m e nt   w hi c i s   r e l a xe r u nni n g   t i m e ,   o a   p r e de f i n e d   r u nni n g   t i m e   i s e c o n ds   ( de pe n ds   o i n s t a n c e ’s   s i z e ) ,   o o n c e   t h e   o pt i m a l   s o l ut i o i s   f o un d.   A   pl a t f o r m   o f In t e l   Co r e   i 7   2 . 30  G H z   p r o c e s s o r ,   8G B   R A M ,   a n d   J a v a   N e t B e a n s   ID E   v 8. 2   w a s   e m pl oy e fo r   t h e   e xpe r i m e nt s .   Evaluation Warning : The document was created with Spire.PDF for Python.