I n d on e s i an   Jo u r n al   o El e c t r i c al   En gi n e e r i n g   an d   C o m p u te r   S c i e n c e   V o l .   20 ,   N o .   3 D e c e m b e r   20 20 ,   pp .   1556 ~ 1568   IS S N :   2502 - 4752 ,   D O I :   10. 1 1591 / i j e e c s . v 20 .i 3 . pp 155 6 - 1568        1556       Jou r n al   h o m e pa ge ht t p: / / i j e e c s . i a e s c or e . c om   N e w   h y b r i d   f l o w e r   p o l l i n a t i o n   a l g o r i t h m   w i t h   d r a g o n f l y   a l g o r i t h m   a n d   j a c c a r d   i n d e x   t o   e n h a n c e   so l v i n g   u n i v e r si t y   c o u r s e   t i m e t a b l e   p r o b l e m       M a.   S h i e l a   C .   S ap u l 1 ,   R ac h s u d S e tth aw o n g 2 ,   P i s al   S e tth aw o n g 3   1, 2 C o m put e r   S c i e nc e   D e pa r t m e nt ,   A s s um pt i o U n i v e r s i t y ,   T ha i l a nd   3 M a na g e m e n t   I nf o r m a t i o n   S y s t e m s   D e pa r t m e n t ,   A s s um p t i o U n i v e r s i t y ,   T ha i l a nd       A r ti c l e   I n fo     A B S TR A C T   Ar t i c l e   h i s t or y :   R e c e i v e A pr   3 ,   20 20   R e v i s e J un   6 ,   2020   A c c e pt e J un   20 ,   2020       U ni v e r s i t y   c o ur s e   t i m e t a b l e   p r o bl e m   ( U C T P )   i s   o ne   o f   t he   pr o bl e m s   o w hi c m a ny   r e s e a r c he s   ha v e   b e e n   c o nduc t e o v e r   t h e   y e a r s   b e c a us e   o f   i t s   i m po r t a nc e   i a c a de m i c   i ns t i t ut i o ns .   A   na t u r e - i n s p i r e m e t a he u r i s t i c   o pt i m i z a t i o a l g o r i t hm ,   f l o w e r   po l l i na t i o a l g o r i t hm   ( F P A )   ha s   be e a da p t e d ,   s o - c a l l e a da pt e F P A   ( A F P A ) ,   t o   c o pe   w i t U C T P   i t h e   pr e v i o us   w o r k.   H o w e v e r ,   A F P A   s uf f e r s   f r o m   t he   s t a g na t i o pr o b l e m   b e c a us e   o f     t he   no n - di v e r s i t y   i t he   po pul a t i o n .   T o   i m pr o v e   t he   di v e r s i t y   of     t he   po pul a t i o n,   t hi s   w o r i nt r o duc e s   ne w   H y br i F P A   w i t t w o   v a r i a n t s :   J F P A   pr o v i de t he   J a c c a r i nde x   t o   d e t e r m i ne   s i m i l a r i t i e s   a m o ng   c a t e g o r i c a l   da t a   a nd  t he   g r e e dy   s e l e c t i o m e c ha ni s m   t o   i m p r o v e   t he   s e l e c t i o o f     t he   r a ndo m   s o l ut i o n a nd  D F P A   a ppl i e t he   n a v i g a t i o na l   c ha r a c t e r i s t i c s   o f   t he   dr a g o nf l y   a l g o r i t hm   ( D A )   t o   he l i t he   ne i g hbo r ho o r e l a t i o ns hi p .     T h e   r e s u l t s   i t h i s   s t u dy   i n d i c a t e   t h a t   t h e   p r o po s e a l g o r i t hm s   h a v e   b e t t e r   e x p l o r a t i o a b i l i t y   a n f a s t   c o nv e r g e nc e   r a t e   i c o m p a r i s o t o   pr e v i o u s   a p p r o a c h e s ;   J F P A   o u t p e r f o r m s   A F P A   i o u t   o f   d a t a s e t s   f o r   bo t s m a l l   a nd   l a r g e   d a t a s e t s ,   a n D F P A   o ut p e r f o r m s   A F P A   a nd  G A   i a l l   d a t a s e t s   w h i l e   i t   o ut p e r f o r m s   P S O   i n   3   o u t   o f   4   s m a l l   da t a s e t s   a n d   2   c o m p l e x   l a r g e   d a t a s e t s .   Ke y w or d s :   Co ur s e   t i m e t a b l e   D ra go n f l y   a l go r i t h m   F l ow e r   po l l i na t i o a l go r i t hm   J a c c a r d   i n de x   M e t a h e uri s t i c   O pt i m i z a t i o n   C opy r i gh t   ©   20 20   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 :   M a .   S h i e l a   C .   S a pu l ,   A s s um pt i o n   U ni v e r s i t y ,   B a ngko k,   T h a i l a n d .   E m a i l :   p5919 398 @ a u . e du       1.   I N TR O D U C TI O N   In   e a c h   a c a de m i c   s e m e s t e r ,   u ni v e r s i t i e s   o r   c o l l e ge s   m us t   f a c e   t h e   p r o b l e m   of   s c h e dul i n t h e i r   r e s o ur c e s .   T h e   s c h e dul i n p r o b l e m   i s   a   b r o a de r   c l a s s   o f   c om b i na t o r i a l   o pt i m i z a t i o p r o b l e m s   of   a l l o c a t i n r e s o ur c e s   t o   e ve n t s .   O n e   t y pi c a l   s c h e dul i n p r o b l e m   i s   t h e   t i m e t a b l e   p r o b l e m .   T i m e t a b l e   s c h e dul i ng  i c o n s i de r e a   di f f i c ul t   p r o b l e m   b e c a us e   t h e y   a r e   m a de   c o m pl i c a t e by   t h e   v a r i a t i o n s   i t h e   c o n s t r a i n t s   a n d   due   t o   t h e   n a t u r e   of   t h e   pr o b l e m   t o   s o l v e .   In   s o l v i n o pt i m i z a t i o n   p r o b l e m s ,   t h e   m a j o r   go a l   i s   t o   s e a r c h   t h e   b e s t   po s s i b l e   w a y   t f i n t h e   o pt i m um   s o l ut i o n,   a n t h e   s e a r c hi n p r o c e s s   s h o ul b e   c o m pl e t e i n   t h e   s h o r t e s t   a m o u n t   o f   i t e r a t i o o r   s h o r t e s t   po s s i b l e   t i m e .   T hi s   p a pe r   f o c us e s   o n   a ut o m a t i c a l l y   s o l v i n t h e   u ni v e r s i t y   c o ur s e   t i m e t a b l e   (U CT P i n   t h e   o pt i m a l   t i m e   b e c a us e   t r a di t i o n a l l y   a c a de m i c   i n s t i t ut i o n s   m a nua l l y   s o l ve   t i m e t a b l e   pr o b l e m s ,   w h i c h   t a ke s   da y s   o r   w e e ks   t o   s a t i s fy   t h e   c o n s t r a i nt s   a nd  c o m pl y   w i t h   t h e   n a t u r e   of    t h e   p r o b l e m .   T h e   p r o b l e m   c o n s i s t s   o f   a s s i gn i n g   a p p r o pri a t e   c o ur s e s   t o   l e c t ur e r s   a n o t h e r   r e s o ur c e s     (r o o m ,   da y   a n t i m e w h i l e   m a x i m i z i n gi v e n   c o n s t r a i n t s .   T h e   pr o po s e s o l ut i o n   s h o ul d   s a t i s fy   bo t h   ha r d   a n s o f t   c o n s t r a i n t s .   H a r c o n s t ra i nt s   a r e   c o n s t ra i nt s   t ha t   m u s t   b e   s a t i s f i e n o   m a t t e r   w ha t   t o   ob t a i n   a   f e a s i b l e   t i m e t a b l e .   T h e r e   a r e   t w o   m a i n   ha r c o n s t ra i nt s :   l e c t u r e c o n s t r a i n t   a n d   s c h e dul i n c o n s t r a i n t s .     L e c t ur e r   c o n s t r a i n t   i m p l i e s   t h a t   a   l e c t u r e r   c a n   t e a c h   a   s ub s e t   of   c o ur s e s .   S c h e dul i ng  c o n s t r a i n t s   i m pl y   t h a t   t w o r   m o r e   c o ur s e s   c a nn o t   b e   a s s i gn e t o   a   l e c t u r e r   a t   t h e   s a m e   t i m e ,   a nd  t w o   o r   m o r e   c o ur s e s   c a nn o t   b e   a s s i g n e t o   t h e   s a m e   r o o m   a t   t h e   s a m e   t i m e .   S o f t   c o n s t r a i nt s ,   o n   t h e   o t h e r   ha n d ,   a r e   de s i r e t o   b e   s a t i s f i e d   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752     Ne w   hy br i f l ow e r   pol l i na t i o a l gor i t hm   w i t dr a gonf l y   al go r i t hm   a nd  j a c c ar d . . .   ( Ma .   S hi e l a   C.   Sa pul )   1557   o n l y ,   b ut   i f   do n e   s o ,   i t   do e s   n o t   s t o t h e   t i m e t a b l e   f r o m   b e i ng   a   v a l i s o l ut i o n,   s uc h   s o f t   c o n s t ra i nt   i n c l ude i n   t h i s   s t udy   i s   t o   i n c l ude   t h e   m i n i m u m   o r   m a xi m u m   n um b e r   o f   c o ur s e s   s h o ul be   t a ke n   o r   t h e   t o t a l   n um b e r   o t e a c hi n l o a a s s i g nm e nt s   a   l e c t u r e i s   a l l o w e d .   T h e   e xi s t i n s o l ut i o n   t e c hn i que s   fo r   t i m e t a b l e   pr o b l e m s   ra n ge   f r o m   t h e   m a n u a l   ge n e ra t i o n   o   a   t i m e t a b l e   [1]  t o   m e t a h e u ri s t i c   a l go ri t hm s .   T h e   m a nua l   ge n e r a t i o n   o f   t h e   t i m e t a b l e   i s   t e di o us   a n d     time - c o n s um i n g   a n d   i t   do e s   n o t   gu a r a nt e e   t ha t   a n   o pt i m a l   c o ur s e   t i m e t a b l e   h a s   b e e n   ge n e r a t e d.     M e t a - h e u r i s t i c   a l go ri t hm s ,   o n   t h e   o t h e r   h a nd,   c a n   f i nd  go o d   s o l ut i o n s   w i t h   l e s s   c o m put a t i o na l   e ff o r t   c o m pa r e w i t h   t r a d i t i o na l   t e c hni que s .   M e t a h e u ri s t i c   a l go r i t hm s   s uc h   a s   ge n e t i c   a l go ri t hm   (G A a nd  pa rt i c l e   s w a r m   o pt i m i z a t i o n   (P S O ha v e   b e e n   r e po r t e t o   b e   a b l e   t o   s o l ve   m a n y   o pt i m i z a t i o n   p r o b l e m s .   G A   w a s   f i r s t   us e f o r   a   t i m e t a b l i n p r o b l e m   i n   1992  [2]  a n h a s   b e e n   a ppl i e t o   v a r i o us   s c h e dul i ng  p r o b l e m s   [3 - 6].     P S O   h a s   t i e s   w i t h   ge n e t i c   a l go ri t hm   a nd  e vo l ut i o n a r y   a l go r i t hm s   [7]  a n ha s   b e e n   us e a l s o   fo r   s o l v i n g     t h e   v a r i o us   t i m e t a b l i n p r o b l e m s   [8 - 10].   F P A   i s   a n o t h e r   m e t a - h e u r i s t i c   a l go ri t hm   i nt r o duc e t s o l ve   ge n e r a l   o pt i m i z a t i o p r o b l e m s   l i ke   f i n d i n s o l ut i o n s   f o r   m a t h e m a t i c a l   e qu a t i o n s   [1 1].   It   h a s   b e e n   f o r m ul a t e f o r   m ul t i - o b j e c t i ve   o pt i m i z a t i o n   a p pl i c a t i o n s   by   m i m i c ki n t he   po l l i na t i o n   p r o c e s s   of   f l ow e r i n p l a nt s   [12] .     It   h a s   e n t i c e t h e   i nt e r e s t   o f   s e ve r a l   r e s e a r c h e r s   b e c a us e   of   i t s   c ha r a c t e r i s t i c s ;   l i ke   i t   us e s   f e w e r   pa ra m e t e r s   a n ha s   s h o w n   go o r e s ul t s   w h e n   a pp l i e t o   v a r i o us   o pt i m i z a t i o n   p r o b l e m s .   In  t h e   s u r v e y   s t ud y   of   [ 13 ],     t h e y   fo un o ut   t h a t   t h e   n u m b e r   o pa ra m e t e r s   c a n   a f f e c t   t h e   c o m pl e xi t y   of   a n   a l go ri t hm .   A n o t h e r   s i m i l a r   s ur v e y   s t ud y   o n   m e t a h e u r i s t i c   a l go r i t h m s   t ha t   ha v e   a do pt e a   l a rge   n u m b e r   of   pa r a m e t e r s   c a n   b e     a   d i s a dv a n t a ge   b e c a us e   i t   r e qu i r e s   t ha t   t h e   pa ra m e t e r s   us e m us t   b e   t u n e f o r   t h e   o pt i m a l   t a s [ 14 ].     F P A   w a s   o r i gi na l l y   d e s i gn e t o   s o l v e   c o n t i n uo us   o pt i m i z a t i o n   p r o b l e m s ,   by   m o di fy i n t h e   F P A ;     i t   i s   po s s i b l e   t s o l ve   a   s ubs e t   of   t h e   U CT P   pr o b l e m   a n pr o m i s i n r e s ul t s   p r o v e s   t h a t   F P A   c a n   b e   us e d   e ffe c t i ve l y   t o   s o l v e   a   c o m b i n a t o r i a l   p r o b l e m   l i ke   U CT P   [15] .   F P A   a l s o   s u ff e r s   f r o m   a   l a c of   a   g o o d   b a l a n c e   b e t w e e n   e xpl o r a t i o n   a n e xp l o i t a t i o n   o pt i m i z a t i o n   p r o c e s s   w h i c h   m a y   l e a t o   a   n o n - di v e r s e   po pul a t i o n.     A   l o t   o f   r e s e a r c h e r s   h a v e   p r o po s e v a r i o us   s t ra t e gi e s   t o   e nha n c e   F P A   pe r f o r m a n c e   a n d   i t s   i m pl e m e nt a t i o t o   v a r i o us   o pt i m i z a t i o p r o b l e m s ;   a   s t udy   o n   f l e xi b l e   j o b   s h o s c h e dul i n g   p r o b l e m s   w h e r e i t h e   c r o s s ove r   o pe r a t o r   o f   G A   a n t a b m e t h o a r e   a pp l i e t o   e nh a n c e   t he   s e a r c h   c a pa b i l i t y   o F P A   [16].   A n o t h e r   s t u d y   s h o w s   t h a t   w h e n   F P A   i s   c o m b i n e w i t h   o t h e r   a l go r i t h m s ,   i t   c a n   o ut pe r f o r m   t h e   c o m b i n e a l go r i t h m   a n c a i m p r o v e   i t s   s p e e a n c o n v e r ge n c e   r a t e   [17] .   B e c a us e   t h e   po pul a t i o n   s i z e   m a y   a f fe c t   t h e   r e s ul t s   of    t h e   ge n e r a t i o n   o f   t h e   po pul a t i o n ,   m u t a t i o n   o pe r a t o r s   w e re   i nt r o duc e i n   F P A   [18] .   A n o t h e r   s t udy   t h a t   s ugge s t s   t ha t   F P A ’s   pe r f o r m a n c e   c a n   b e   i m pr o v e by   i nt r o duc i n t h e   c l o na l   o pe r a t o r   f r o m   t h e   Cl o n a l   S e l e c t i o n   A l go r i t hm   (CS A a nd  r e pl a c i ng  t h e   l e vy   f l i g h t   us i n t h e   u n i f o r m   ra n do m   di s t ri b ut i o n   t o   i m p r o ve   t h e   gl o b a l   po l l i n a t i o n   p r o c e s s   a n c o n t i n uo us   c h e c ki n o f   t h e   b e s t   s o l ut i o n   c a n   a v o i be i n t r a p pe i n   l o c a l   o pt i m a   [1 9].   I n   t h e   s ur v e y   s t ud y   o n   m e t a h e u ri s t i c   a l go ri t hm s   [14]  a l s o   c o n c l ude i n   t h e i r   f i ndi n gs   t ha t   a ppl y i n g   a   c o m b i na t i o n   o f   t w o   m e t a h e u r i s t i c s   c a n   i m p r o v e   a n o t h e m e t a h e u r i s t i c   a l go ri t hm ’s   pe r f o r m a n c e .   T o   t h e   b e s t   of   o ur   i n v e s t i ga t i o n,   t h e   m a j o r i t y   of   t h e   s t ud i e s   p r e s e nt e f o r   s o l v i n o pt i m i z a t i o p r o b l e m s   us i n F P A   a r e   a p pl i e d   t o   e n g i n e e ri n a n d   i ndus t r y - r e l a t e d   p r o b l e m s   [20 - 23] .   D e s pi t e   t h e   e nha n c e m e n t s   a nd  r e l a t e w o r ks   o n   F P A   m e n t i o n e i t hi s   s t u dy ,   F P A   h a s   c e r t a i l i m i t a t i o n s   o r   i s s ue s :   F P A   c a nn o t   de a l   d i r e c t l y   w i t c o m b i na t o ri a l   p r o b l e m s   l i ke   U CT P ,   t h e   e xpl o ra t i o n   a b i l i t y   of   F P A   i s   d e pe n de n t   o n   t h e   l e vy   f l i ght   w h i c h   c a n   b e   a ggr e s s i v e   a n c a n   c a us e   l a r ge   s t e ps   a nd  a   n o n - di v e r s e   po pul a t i o n   m a y   l e a t o   l oc a l   o pt i m a   a nd    t h e   pa ra m e t e s e t t i ngs   i a n   F P A   m a y   a ff e c t   a l s o   t h e   pe r f o r m a n c e   o f   t h e   a l go ri t hm .   T h e   m a i c o n t r i b ut i o n   o f   t hi s   p a pe i s   t o   de s i gn  a n d   de v e l o t w o   n e w   h y b r i f l o w e r   po l l i na t i o a l go ri t hm s :   J F P A   a n D F P A ,   w h i c h   i m p r o v e   t h e   pe r f o r m a n c e   of   a da pt e d - f l ow e r   po l l i n a t i o n   (A F P A a l go ri t hm   [ 15 i n   s o l v i n t h e   l e c t ur e r - c o ur s e   a s s i g nm e n t   p r o b l e m   a n e x t e n o u r   w o r t o   s o l v i n u ni v e r s i t y   c o ur s e   t i m e t a b l e   p r o b l e m   (U CT P ).   A F P A   h a s   de m o n s t ra t e t ha t   F P A   c a b e   a da pt e t o   s o l ve   a   c o m b i n a t o r i a l   pr o b l e m .   H ow e v e r ,   a c c o r di n t o   o ur   o b s e r v a t i o n,   A F P A   h a s   l i m i t a t i o n s .   I t   s uf fe r s   f r o m   a   n o n - di v e r s e   po pul a t i o n   w h e n   t h e   po pul a t i o n   i s   t o o   s i m i l a r   t h a t   m a y   r e s ul t   i n   a   l o w   c o n v e r ge n c e   r a t e   o r   b e i n r e s t r a i n e t o   t h e   l o c a l   o pt i m a .   A n o t h e r   po s s i b l e   c a us e   of   t h e   l a c o f   di ve r s i t y   i n   t h e   po pu l a t i o i s   t h e   i n e f fe c t i ve n e s s   of    t h e   pa r a m e t e r   s e t t i n gs .   T o   ov e r c o m e   t h e   l i m i t a t i o n s   o f   A F P A ,   t h e   t w o   h y b r i F P A   a l go ri t hm s :   J F P A   a n D F P A ,   w h i c h   a r e   c a pa b l e   o f   di v e r s i fy i n t h e   po pul a t i o n ,   a r e   i n t r o duc e d.   A   s i m i l a ri t y   f a c t o r   i s   p r o po s e i n   J F P A   t f a c i l i t a t e   t h e   s e a r c h i ng  p r o c e s s   w h e n   c o m pa r i ng  da t a .   T hi s   f a c t o r   h e l ps   c o n t r o l   di v e r s i t y   b y   m e a s u r i n g   t h e   s i m i l a r i t y   a n d   di s s i m i l a ri t y   of   t w o   i n d i v i dua l   s o l ut i o n s   i a dd i t i o t o   t ra di t i o na l   f i t n e s s     v a l ue   [ 24 ] .   S i n c e   t h e   i n di v i du a l   ge n o m e s   of   U CT P   a r e   pr e s e nt e d   a s   a   c a t e go r i c a l   d a t a ,   w e   i n t r o duc e d     a   J a c c a rd  i n de t o   f i n t h e   s i m i l a ri t i e s   o f   c a t e g o r i c a l   da t a .   T h e r e f o r e ,   JFPA   t a ke s   i nt o   a c c o un t   n o t   o n l y     t h e   f i t n e s s   of   t h e   i n di v i du a l   s o l ut i o n s   b ut   a l s o   t h e   di v e r s i t y   a m o n t h e m .   T o   i m p r o v e   t h e   s e l e c t i o n   o   t h e   r a ndo m   s o l ut i o i t h e   l o c a l   po l l i n a t i o a   s e l e c t i o n   f a c t o r   i s   e m b e dde a l s o   i n   J F P A .   A c c o r di ng  t o   [ 25 a l go ri t hm s   di v e r s i t y   pr o b l e m   oc c ur s   i f   t h e   a l go r i t h m ’s   o pt i m i z a t i o n   p r o c e s s   c a nn o t   b a l a n c e   b e t w e e n   e xpl o r a t i o n   a n e xpl o i t a t i o n .   A   go o b a l a n c e   b e t w e e n   e x pl o r a t i o n   a n e xp l o i t a t i o n   i s   a n o t h e r   i m po rt a nt   c r i t e ri o n   f o r   t h e   pe r f o r m a n c e   of   t h e   a l go r i t h m   [1 4].   A n o t h e r   r e a s o n   f o r   n o n - di v e r s e   po pul a t i o n   i s   t h a t     t h e   pa r a m e t e r   c h o i c e   c a n   i n f l ue n c e   t h e   a l go r i t hm ’s   pe r f o r m a n c e   [ 26 ] .   T o   b a l a n c e   A F P A ’s   e xpl o r a t i o n   a n d   e xpl o i t a t i o n   p r o c e s s ,   t h e   o t h e r   p r o po s e d   a l go r i t h m   D F P A   ut i l i z e s   t h e   n a v i ga t i o n a l   b e h a v i o ra l   c h a ra c t e ri s t i c s   Evaluation Warning : The document was created with Spire.PDF for Python.
                     IS S N :   25 02 - 475 2   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   20 ,   N o .   3 D e c e m be r   2 020   :   1556   -   1568   1558   of   t h e   D ra go n f l y   a l go r i t h m   t ha t   m i m i c s   t h e   s w a rm i ng  b e ha v i o r s   o f   dr a go n f l i e s ,   w h i c h   a r e   s i m i l a a l s o   t   t h e   e xpl o ra t i o a n d   e xpl o i t a t i o p h a s e s   o f   o pt i m i z a t i o [ 27 - 2 9] .       2.   R ES EA R C H   M ET H O D   2 . 1 .       Th e   a d ap te d   F P A   (A F P A )   A F P A   i nt ro d u c e i [ 1 3 ]   a i m s   t o   s o l v e   t he   l e c t u re r - c o u rs e   a s s i g nm e nt ,   w hi c i s   c o ns i d e re d   a s     a   c o m b i na t o ri a l   p ro b l e m .   I t   p ro v i de d   a   d i s c re t e   re p re s e nt a t i o o f   t he   s o l u t i o b y   d e f i ni ng   t he   p o s i t i o o f     t he   f l o w e rs   a s   a   c o m b i na t o ri a l   s e t   o f   re s o u rc e s   a s s i g ne d   t o   a e v e nt .   F o t he   f l o w e p o l l i na t i o p ro c e s s ,   i t   p re s e nt s   t he   re d e s i g ni ng   o f   t he   s t e p   s i z e   o t he   s c a l i ng   f a c t o f o u p d a t i ng   t he   c a nd i d a t e   s o l u t i o ns   p o s i t i o n.   A l s o ,   i t   a p p l i e s   t he   G A   o pe ra t o rs   t o   p ro v i de   t he   f l o w e c o ns t a nc y   o pe ra t o rs .   T he   p s e u d o c o de   o f   A F P A   i s   g i v e i F i g u re   1 .     I g e ne r a t i ng   t he   i ni t i a l   p o p u l a t i o ( l i ne   1 ) ,   t he   A F P A   ra nd o m l y   a s s i g ns   t he   re s o u rc e s   t o   e v e nt s   l i k e   i t he   c a s e   of   a s s i g ni ng   c o u rs e s   t o   t he   l e c t u re a nd   a s s i g ni ng   ro o m ,   d a y ,   a nd   t i m e   t o   t he   c o u rs e - l e c t u re a s s i g nm e n t .   T he n,     t he   a l g o ri t hm   u t i l i z e s   t he   s e l e c t i o o pe ra t o i g e t t i ng   t he   f i t t e s t   f l o w e s o l u t i o ( X b e s t ) ,   t he   c u rre nt   f l o w e s o l u t i o n   ( X i   t ) ,   a nd   a   ra nd o m   f l o w e s o l u t i o i t he   c u rre nt   i t e r a t i o ( X j ) .   M u t a t i o ( l i ne s   1 0   a nd   2 2 )   a nd   c ro s s o v e ( l i ne s   1 2 ,   1 4 ,   1 6 ,   2 4 ,   2 6 ,   a nd   2 8 )   o p e ra t o rs   o f   t he   G A   a re   u s e d   a s   t he   f l o w e c o ns t a nc y   o pe ra t o rs   o f   A F P A .       1   I ni t i a l i z e   a   po pul a t i o n   o f   n   f l o w e r s / po l l e n   g a m e t e s   w i t h   r a ndo m   s o l ut i o ns     2   F i nd   t he   be s t   s o l u t i o X b e s t   i n   t h e   i n i t i a l   po pul a t i o n   3   D e f i ne   a   s w i t c pr o ba b i l i t y   p   ϵ   [ 0, 1]   4   W H I L E   ( t   m ax ge n e r a t i on )   5      F O R   i = 1:   n   6         IF   ( r an d < p )   T H E N   7         DO   g l o ba l   po l l i na t i o   8         gp = fv ( X b e s ) fv ( X i   t )   9           I F   ( gp < pr 1 )   T H E N   10             X i   t+ 1 = m u t a t i o nO ne C l a s s   ( X i   t )   11           E L S E   I F   ( gp < pr 2 )   T H E N   12             X i   t+ 1 = c r o s s O v e r H a l f W o r kl o a d( X i   t ,   X b e s t )   13           E L S E   I F   ( gp < pr 3 )   T H E N   14             X i   t+ 1 = c r o s s O v e r H a l f nW o r kl o a d( X i   t , X b e s t )   15           E L S E     16             X i   t+ 1 = c r o s s O v e r nW o r kl o a d ( X i   t ,   X b e s t )   17           E N D I F   18         E L S E   19        DO   l o c a l   po l l i na t i o   20         lp = fv ( X j   t ) fv ( X i   t )   21           I F   ( lp < pr 1 )   T H E N   22             X i   t+ 1 = m u t a t i o nO ne C l a s s   ( X i   t )   23           E L S E   I F   ( lp < pr 2 T H E N   24             X i   t+ 1 = c r o s s O v e r H a l f W o r kl o a d( X i   t ,   X j )   25           E L S E   I F   ( lp < pr 3 T H E N   26             X i   t+ 1 = c r o s s O v e r H a l f nW o r k l o a d( X i   t , X j )   27           E L S E     28             X i   t+ 1 = c r o s s O v e r nW o r kl o a d ( X i   t ,   X j )   29           E N D I F   30        E N D   I F       31        IF   ( fv ( X i   t+ 1 ) > fv ( X i   t ) )   T H E N   32             fv ( X i   t ) = fv ( X i   t+ 1 )   33        F i nd   a n u pda t e   t he   be s t   s o l u t i o X b e s t     34       E N D   F O R   35   E N D   W H I L E     F i gu r e   1 .   P s e udo c o de   of   A F P A       T he   ra nd o m   v a l u e   r a n d   a nd   t he   s w i t c p ro b a b i l i t y   p   a re   u s e d   t o   c o nt ro l   t he   s w i t c hi ng   b e t w e e t he   g l o b a l   a nd   l o c a l   p o l l i na t i o p ro c e s s ,   a nd   a t   t he   s a m e   t i m e   d e t e rm i ne   t he   f l o w e c o ns t a nc y   o p e ra t i o t ha t   t he   i nd i v i d u a l   f l o w e s e rv e s   ( l i ne   6 ) .   T he   f i t ne s s   v a l u e   fv   a s   s ho w i n   1   i s   d e ri v e d   b y   ge t t i ng   t he   nu m b e o f   v i o l a t i o ns   i n   s a t i s f y i ng   t he   c o ns t r a i nt s   f o e a c s o l u t i o n;   t he   a n t i c i p a t e d   re s u l t   e q u a l   t o   1 . 0   i nd i c a t i ng   a n   o p t i m a l   s o l u t i o i t he   p o p u l a t i o n .     Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752     Ne w   hy br i f l ow e r   pol l i na t i o a l gor i t hm   w i t dr a gonf l y   al go r i t hm   a nd  j a c c ar d . . .   ( Ma .   S hi e l a   C.   Sa pul )   1559   fv   = ( 1 . 0     (     ) )     (1)     D uri n gl o b a l   a nd  l o c a l   po l l i na t i o n,   t h e   s t e s i z e   f o r   b o t h   po l l i na t i o gp   (l i n e   8)   a nd  lp   ( l i n e   2 0)  i s   de r i v e by   ge t t i n t h e   di f fe r e n c e   of   t h e   f i t n e s s   v a l ue s   of   t w o   f l ow e r   s o l ut i o n s a   s e t   o f   pa r a m e t e r s   pr 1 ,   pr 2 a n pr 3   a r e   us e t o   de t e r m i n e   h o w   A F P A   w i l l   b e h a v e ,   i n   o t h e r   w o r ds ,   s e l e c t i n a   G A   o pe r a t o r   f o r   po l l i n a t i o n.   AFPA   h a s   s o m e   d ra w b a c ks   i n   ge t t i n g   t h e   a l go ri t hm   s t uc i l o c a l   o pt i m a   s i n c e   t h e   F P A   ha s     t h e   w e a kn e s s   of   h a v i ng  t o   us e   a   di v e r s e   p o pul a t i o n ;   i n   p a r t i c ul a r,   b o t h   l o c a l   (l i n e   19)  a n g l o b a l   pr o c e s s e s   (l i n e   7)  us e   t h e   s a m e   s c a l i n f a c t o r .   T o   s o l v e   t h i s   di v e r s i t y   pr ob l e m ,   w e   s h o ul d   pr o v i de   a   g oo b a l a n c e   b e t w e e n   t h e   gl o b a l   a nd  l o c a l   p r o c e s s   duri n t h e   s e a r c h   p r o c e s s .     2 . 2 .     V ar i ati o n s   o F P A   fo r   U C TP   T o   a dd r e s s   t h e   l i m i t a t i o n s   o f   A F P A   a s   di s c us s e i t h e   p re v i o us   s e c t i o n ,   t hi s   w o r p r o po s e s   t w h y b r i di z a t i o n s   o f   A F P A :   h y b r i A F P A   w i t h   s i m i l a ri t y   i n de x   us i n J a c c a r d   i n de a n s e l e c t i o f a c t o r   (J F P A )   a n h y b r i A F P A   w i t h   na v i ga t i o na l   c ha r a c t e r i s t i c s   o f   t h e   d ra go n f l y   (D F P A ) .   J F P A   a ppl i e s   t h e   J a c c a r d   i n de x   a s   a n o t h e r   s c a l i n f a c t o r   t o   e nha n c e   t h e   l o c a l   po l l i na t i o pr o c e s s .   J a c c a r i n de p r o v i de s   t h e   s i m i l a ri t y   m e a s u r e m e nt   o f   t h e   i n f o r m a t i o n   c o nt a i n e f o r   e a c h   f l ow e r   s o l ut i o n.   T hi s   s c a l i n f a c t o r   d i c t a t e s   h o w   t h e   l o c a l   po l l i n a t i o w i l l   b e ha v e   a n t h i s   h e l ps   t h e   po l l i na t i o n   p r o c e s s   t h e   c h a n c e   t ha t   f l ow e r   s o l ut i o n s   m a y   ha v e     t h e   be s t   i n f o r m a t i o n   t o   e xc h a n ge .   T h e   s e l e c t i o n   f a c t o r   h e l ps   i m p r o v e   t h e   s e l e c t i o n   o t h e   b e s t   r a ndo m   f l ow e r .   T h e   ps e udo c o de   of   J F P A   i s   gi v e n   i F i gu r e   2.       1   I ni t i a l i z e   a   po pul a t i o n   o f   n   f l o w e r s / po l l e n   g a m e t e s   w i t h   r a ndo m   s o l ut i o ns     2   F i nd   t he   be s t   s o l u t i o X b e s t   i n   t h e   i n i t i a l   po pul a t i o n   3   D e f i ne   a   s w i t c pr o ba b i l i t y   p   ϵ   [ 0, 1]   4   W H I L E   ( t < m axg e n e r a t i o n )   5      F O R   i = 1:   n   6         IF   ( r an d   <   p )   T H E N   7           DO   g l o ba l   po l l i n a t i o   8           gp = fv ( X b e s ) fv ( X i   t )   9           I F   ( gp pr )   T H E N   10               X i   t+ 1 = m ut a t i o nO ne C l a s s ( X i   t )   11           E L S E     12               X i   t+ 1 = c r o s s O v e r H a l f W o r kl o a d ( X i   t ,   X b e s t )   13                   E N D I F   14         E L S E   15           DO   l o c a l   po l l i n a t i o   16           R a ndo m l y   c hoo s e   X us i ng   t h e   s e l e c t i o f a c t o r   17           lp = sf ( X j , X i )   / /   us i ng   E q .   2   18           I F   ( lp > s i m _t h )   T H E N   19             X i   t+ 1 = m u t a t i o nO ne C l a s s   ( X i   t )   20           E L S E     21             X i   t+ 1 = c r o s s O v e r H a l f W o r kl o a d( X i   t ,   X j )   22           E N D I F   23         E N D   I F       24         IF   ( fv ( X i   t+ 1 ) > fv ( X i   t ) )   T H E N   25             fv ( X i   t ) = fv ( X i   t+ )   26           F i nd   a nd   up da t e   t he   be s t   s o l u t i o n   X b e s t   27      E N D   F O R   2 8   E N D   W H I L E     F i gu r e   2 .   P s e udo c o de   of   J F P A       D uri n gl o b a l   a n l o c a l   po l l i n a t i o n,   t h e   gp   a n d   lp   a r e   us e t o   d e r i v e   t h e   s t e s i z e   of    t h e   po l l i n a t i o n ;   gp   us e s   t h e   f i t n e s s   v a l ue   t o   de t e r m i n e   t h e   s t e s i z e   o f   t h e   po l l i n a t i o n   ( l i n e   8) ,   a nd   lp   us e s     t h e   s i m i l a ri t y   f a c t o r   t o   de t e rm i n e   t h e   s t e s i z e   o f   t h e   po l l i n a t i o n   (l i n e   17 ).   T h e   s i m i l a r i t y   f a c t o r   sf   i s     de f i n e i ( 2 ) .      = ( + + ) ,   (2)     Evaluation Warning : The document was created with Spire.PDF for Python.
                     IS S N :   25 02 - 475 2   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   20 ,   N o .   3 D e c e m be r   2 020   :   1556   -   1568   1560   w h e r e   d   a r e   t h o s e   i n s t a n c e s   w h e r e   X i   a n X j   b o t h   h a v e   a   v a l ue   of  1,   a r e   t h o s e   i n s t a n c e s   w h e r e   t h e   a t t r i b ut e   of   X i   i s   a n d   t h e   a t t r i b ut e   o f   X j   i s   a n d   a r e   t h o s e   i n s t a n c e s   w h e n   t h e   a t t ri b ut e   o f   X i   i s   1   a n d   t h e   a t t r i b ut e   o X j   i s   0.   A l s o ,   t h e   pa ra m e t e r s   pr   a nd   s i m _t h   a r e   us e t o   s e l e c t   a   G A   o pe r a t o r   (s w a m ut a t i o n   o r   a   c r o s s ov e r fo r   po l l i na t i o n.   It   s h o ul b e   n o t e t ha t   J F P A   e xc l ude s   s o m e   o pe r a t o r s   o f   A F P A :   c r o s s O v e r H a l f n W o r kl o a d()   a n c r o s s O v e r n W o r kl o a d()   b e c a us e   b a s e o n   t h e   e xpe r i m e nt a l   r e s ul t s   ob s e r ve d,   t h e s e   o pe r a t o r s   do   n o t   h e l p     a   l o t   i p r o v i di n a   di v e r s e   po pul a t i o n .   F o r   D F P A ,   n e i g h b o r h o o s e l e c t i o n   i s   i m po rt a nt   b e c a us e   i t   w i l l   i m p r o v e   s e a r c h   e ff i c i e n c y   a n d   i n c r e a s e   po pul a t i o n   di v e r s i t y .   T o   a c c o m pl i s h   t h i s   D F P A   e m b e ds   t h e   D A ’s   n a v i ga t i o na l   b e h a v i o r   w i t h   F P A   a n a l s o   di v i de s   t h e   po pul a t i o n   i nt o   a   s e t   o f   s ub p o pul a t i o n s   by   f i n di n t h e   s i m i l a r i t y   b e t w e e n   a l l   s o l ut i o n s   t o   di s t r i b ut e   t h e   s o l ut i o n s   i n t o   d i f f e r e n t   n e i g h b o r s .   A s   s h o w n   i n   F i gu r e   3 ,   t h e   a l go ri t hm   i ni t i a l l y   f i n ds     t h e   s i m i l a ri t y   of   t h e   s o l ut i o n s   t o   c r e a t e   o r   upd a t e   t h e   r a di us   of   t h e   c l us t e r s   o r   n e i g h b o r s   (l i n e s   a nd  8).   D uri n g l o b a l   a nd  l o c a l   po l l i na t i o n t h e   upd a t e   o f   t h e   n e w   f l ow e r   s o l ut i o n   X i   t+ 1   de pe n ds   o n   t h e   n e i g h b o rh o o d   r e l a t i o n s h i o f   X i If   X i   h a s   n e i g h b o r s ,   t h e n   b o t h   t h e   di re c t i o n   X ,   a nd  t h e   po s i t i o n   of  X i   a r e   upd a t e d     ( l i n e s   14   a nd  21).   O t h e r w i s e ,   o nl y   t h e   po s i t i o i s   u pda t e d.       1   I ni t i a l i z e   a   po pul a t i o n   o f   n   f l o w e r s / po l l e n   g a m e t e s   w i t h   r a ndo m   s o l ut i o ns     2   F i nd   t he   be s t   s o l u t i o X b e s t   i n   t h e   i n i t i a l   po pu l a t i o n   3   D e f i ne   a   s w i t c pr o ba b i l i t y   p   ϵ   [ 0, 1]   4   D e t e r m i n e   ho w   m a ny   c l us t e r s   C   5   W H I L E   ( t < m axg e n e r a t i o n )   6      R a ndo m l y   s e l e c t   t he   v e c t o r   o r   c e n t e r   po i n t   f o r   e a c h   c l us t e r   C 1 ,   C 2 ,   …,   C n     7      D e t e r m i ne   t h e   s i m i l a r i t y   v a l ue s   sv ( X i )   i C 1 ,   C 2 , …,   C   8      U p da t e   t h e   ne i g hbo r i ng   r a d i us   by   a s s i g n   X i   t o   a   c l u s t e r   C i     9      D e t e r m i ne   t h e   X b e s t,   X w o r s t,   X f l o w b e s   10      F O R   i = 1: n   11               IF   ( r an d   < p )   T H E N   12                 DO   g l o ba l   po l l i n a t i o   13                 I F   t he   X i   h a s   a t   l e a s t   o ne   ne i g hbo r     14     U pda t e   X   i   t+ 1   a nd   X   i   t+ 1 // us i ng   an d   9 ,   r e s pe c t i v e l y   15     E L S E     16     X   i   t+ 1 = m ut a t i o nO ne C l a s s   ( X i   t )   17     E N D   I F   18               E L S E   19     DO   l o c a l   po l l i na t i o   20     I F   t he   X i   ha s   a t   l e a s t   o ne   ne i g hbo r     21                     U pda t e   i   t+ a nd   X   i   t+ 1 // u s i ng   and   9 ,   r e s pe c t i v e l y   22     E L S E   23     X   i   t+ 1 =   m u t a t i o nO ne C l a s s   ( X i   t )   24     E N D   I F   25              E N D   I F   26               IF   ( fv ( X i   t+ 1 ) > fv ( X i   t ) )   T H E N   27     fv ( X i   t ) = fv ( X i   t+ 1 )   28      E N D   F O R   29   E N D   W H I L E     F i gu r e   3 .   P s e udo c o de   of   DFPA       D ue   t s pa c e   l i m i t a t i o n ,   w e   d o   n o t   pr o v i de   t h e   t r a d i t i o n a l   o pe r a t o r s   o D A ,   b ut   i t   c a n   b e   r e f e r r e t i n   [27] .   D ra go n f l y   A l go r i t hm   (D A upd a t e s   t h e   d i r e c t i o n   a nd  po s i t i o n   o f   t h e   i ndi v i du a l   f l o w e r s   de pe n ds   o n   f i ve   n a v i g a t i o n a l   b e ha v i o r a l   c h a ra c t e ri s t i c s   o f   t h e   d r a go nf l i e s :   s e pa ra t i o S ,   a l i g nm e n t   A ,   c o h e s i o C a t t ra c t i o n   F ,   a n de s t ruc t i o n   a s   de t e rm i n e i n   3 7 ,   r e s pe c t i v e l y .   T h e   S e pa ra t i o n   S   o pe r a t o r   p r o v i de s   c o l l i s i o n   a v o i da n c e   of   t h e   s o l ut i o n s   fo un i n   t h e   n e i g h b o r ,   a n e a c h   n e i g h b o r   a v o i ds   c o l l i di n w i t h   o t h e r s   i t h e   n e i g h b o rh o o by   de t e r m i ni n t h e   s i m i l a r i t y   of   t h e i r   s o l ut i o n s .   T hi s   o pe r a t i o w i l l   b e   r e pe a t e b e t w e e n   X i   a n i t s   e nt i r e   n e i g h b o r   X j .   If   s i m i l a ri t y   v a l ue   sv ( X i ,   X j )   i s   g r e a t e t ha 0. 5 ,   t h e n   pe r f o r m   t h e   3.     S   =   c r o s s o v e r Ha l f Wo r kl o a d S w a p   ( , ) ,   ( 3)     w h e r e   c r o s s o v e r H a l f W o rk l o a dS w a p ( X i ,   X j )   s e l e c t s   ra ndo m l y   ha l f   o f   t he   ge n o m e s   f r o m   t he   w o rk l o a f r o m   X i ’s   ne i g h b o r   X j   a nd  i f   t h e y   a r e   f o u nd  i X i ,   t h e t he y   a r e   s w a ppe d .   p ro v i de s   t he   A l i g nm e nt   o pe ra t o r   t o   e n s u r e   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752     Ne w   hy br i f l ow e r   pol l i na t i o a l gor i t hm   w i t dr a gonf l y   al go r i t hm   a nd  j a c c ar d . . .   ( Ma .   S hi e l a   C.   Sa pul )   1561   t ha t   s o l ut i o ns   a r e   m o v i ng   t o w a rd s   t h e   s a m e   b e s t   f l o w e r   s o l u t i o n   i t h e   ne i g hb o rh o o d ,   w h e r e i t h e   i n f o rm a t i o f r o m   t h e   b e s t   f l o w e X fl o w b e s t   i t he   c u rre nt   c l us t e i s   s ha re d   w i t h   t h e   c u rre nt   f l o w e X i   o f   t h e   s a m e   c l us t e r.   A   =   c r o s s o v e r H a l f Wo r kl o a dA ( , ) ,   ( 4)     w h e r e   c r o s s o ve r H a l f W o r kl o a dA ( X i ,   X f l o w b es t )   s e l e c t s   r a ndo m l y   h a l f   of   t h e   ge n o m e s   f r o m   t h e   w o r kl o a f r o m   t h e   be s t   s o l ut i o n   X fl o w b e s t   i n   t h e   n e i g h b o r h o o d   a n l o c a t e s   t h e   o c c urr e n c e   i n   X i ,   a nd  r e pl a c e   ha l f   of   t h e   ge n o m e s   a t   t h e   s a m e   ra n do m   po s i t i o n   a s   i n d i c a t e i n   X fl o w b e s t .   p r o v i de s   t h e   Co h e s i o n   o pe r a t o r i t   m a i nt a i n s   a   f o r m   of  n e i g h b o rh o o d,   a l l   t h e   s o l ut i o n s   i t h e   s a m e   n e i g h b o r h o o e xc h a nge   i n f o r m a t i o n.     =   c ro s s ov e r H a l f W or kl o a dC( , ),     (5)     w h e r e   t h e   c r o s s ov e r H a l f W o r kl o a dC( X i ,   X j )   s e l e c t s   ra n do m l y   h a l f   o f   t h e   ge n o m e s   f r o m   t h e   w o r kl o a f r o m     t h e   n e i g h b o rh o o X j   a nd  l o c a t e   t h e   o c c urr e n c e   i n   X i a nd  r e pl a c e s   ha l f   of   t h e   ge n o m e s   a t   t h e   s a m e   r a n do m   po s i t i o n   a s   i n d i c a t e i n   X j .   6   p r o v i de s   t h e   A t t r a c t i o n   o pe ra t o c r os s ov e r ,   e n s u r e s   t ha t   t h e   c u rr e n t   f l o w e r   s o l ut i o n   X i   t e n ds   t o   m o v e   t ow a r ds   t h e   f o o s o ur c e   o r   t he   b e s t   f l ow e r   X b es t   i t h e   e n t i r e   po pul a t i o n   by   e xc h a n g i n g   i n f o r m a t i o n   f r o m   t h e   b e s t   f l ow e r   i n   t h e   e n t i r e   po pul a t i o n.     F   =   c ro s s o ve r H a l f W o r kl o a dF ( ,  ) ,   (6)     w h e r e   c r o s s ov e r H a l f W o r kl o a dF ( X i ,   X b es t )   s e l e c t s   ra n do m l y   h a l f   of   t h e   ge n o m e s   f r o m   t h e   w o r kl o a f r o m     t h e   b e s t   f l ow e r   X b es t   i n   t h e   po pul a t i o n   a n l o c a t e   t h e   o c c ur r e n c e   i n   X i a nd  r e pl a c e s   ha l f   of   t h e   ge n o m e s   a t     t h e   s a m e   ra n do m   p o s i t i o a s   i ndi c a t e d   i n   X b es t   7   p r o v i de s   t h e   D e s t r uc t i o o pe r a t o r;   i t   e n s u r e s   t ha t     t h e   c urr e nt   f l o w e r   s o l ut i o n   i s   ke p t   a w a y   f r o m   t h e   w o r s t   s o l ut i o n .     D   =   c r o s s o ve r H a l f W or kl o a dR a n do m S w a p( ,   ) ,   (7)     w h e r e   c r o s s ov e r H a l fW o r kl o a dR a n do m S w a p ( X i ,   X w o r s t )   s e l e c t s   r a ndo m l y   h a l f   of   t h e   ge n o m e s   f r o m     t h e   w o r kl o a f r o m   t h e   w o r s t   s o l ut i o n   X w o r s t   i n   t h e   po pul a t i o n   a nd  i f   t h e y   a r e   fo un i n   X i   t h e n   t h e y   a r e   s w a ppe by   s e l e c t i ng  a   n e w   r a ndo m   ge n o m e   i n   X i .   D u ri n t h e   gl o b a l   a n l o c a l   po l l i na t i o n,   t h e   X   s e r v e s   a s   s t e v e c t o r   fo r   m o di fy i n d i r e c t i o n   o f   t h e   f l o w e r   s o l ut i o n s   a s   s h o w n   i n   8,   a n d   t h e   n e w   po s i t i o n   o f   X i   o   t h e   f l ow e r s   c a n   b e   de ri v e i n   9 .     + 1       +   +   +       (8)     + 1 =     + 1     (9)       3.   R ES U LTS   A N D   A N A L Y S I S   T o   a s s e s s   t h e   pe r f o r m a n c e   of   t h e   pr o po s e i m pr o v e m e n t s   of   F P A ,   w e   c o m pa r e t h e   r e s ul t s   w i t h   o t h e m e t a - h e u r i s t i c   a l go ri t hm s G e n e t i c   A l go ri t hm   ( GA )   a n d   P a rt i c l e   S w a rm   O p t i m i z a t i o ( PSO )   T h e   pe r f o r m a n c e   o t h e   a l go r i t h m s   w a s   e xa m i n e c o n c e rn i n g   di f fe r e nt   l e v e l s   of   c o n s t ra i nt   c o m pl e xi t y   f r o m   l o w   t o   h i g h .   W e   p r o v i de fo ur   s e t s   o f   c o n s t r a i n t s   w i t h   c o m pl e xi t y   e qua l   10%,   30% ,   5 0% ,   a nd  60 f o r     t h e   l e c t ur e r - c o ur s e   a s s i gnm e n t ,   r e s pe c t i v e l y ;   t h e   l ow e r   t he   c o m pl e xi t y   o t h e   pr o b l e m   w a s ,   t h e   h i g h e   t h e   pe r c e n t a ge   of   fe a s i b l e   c o ur s e s   t h a t   a   l e c t u r e r   c o ul t e a c h   t o .   T h e   da t a s e t   c o n s i s t s   of   t w o   c a t e go r i e s o n e   fo r   s m a l l   s c a l e   s a m pl e   s i z e   (6 c o ur s e s   of fe r e i n   a   s e m e s t e r ,   15  l e c t u r e r s ),   a n d   a n o t h e r   o n e   f o r   l a rge   s c a l e   s a m pl e   s i z e   (200  c o ur s e s   off e r e i n   a   s e m e s t e r,   50  l e c t u r e r s ),   a n a   s e t   o f   c o n s t r a i n t s .   F o r   e a c h   t e s t ,     t h e   m a x i m u m   i t e ra t i o n   n u m b e r s   w e r e   s e t   t o   1000  a n 3000 ,   r e s pe c t i v e l y ;   t h e   n u m b e r s   o f   p o pul a t i o n   w e r e   s e t   t o   10,   50   a n d   100 ,   r e s pe c t i v e l y .   T h e   r e s ul t s   a r e   e v a l ua t e i t e rm s   o f   t h e   f o l l ow i n g:   f i t n e s s   v a l ue ,     m a ge n e r a t i o n s   o r   i t e r a t i o n s ,   h o w   t h e   s i z e s   of   t h e   da t a s e t s   a ff e c t   t h e   pe r f o r m a n c e   of   t h e   a l go r i t hm   h o w   t h e   po pu l a t i o n   c a a f f e c t   t h e   pe r f o r m a n c e   i n   t e r m s   o c o m pl e xi t y ,   a n h o w   t h e   c o m pl e xi t y   c o n s t r a i n t   c a a f f e c t   t h e   b e ha v i o r   o f   t h e   a l go r i t hm .   T a b l e s   a nd  s um m a r i z e   t h e   c o n v e r ge n c e   r a t e   o f   t h e   b e n c h m a r ke a l go r i t h m s :   G A ,   P S O ,     a n A F P A ,   a n t h e   t w pr o po s e a l go r i t h m s :   J F P A   a n D F P A .   It   s h o ul b e   n o t e t ha t   t h e   n u m b e r s   l i s t e i T a b l e s   a nd  a r e   t h e   m a xi m um   f i t n e s s   v a l ue   ( f v ge n e ra t e d   a t   t h e   c o rr e s po n di ng  i t e r a t i o ( ge n) .   T h e   r e s ul t s   t h a t   a r e   o pt i m a l   f o r   e a c h   t e s t   c a s e   a r e   h i g hl i g ht e i n   b o l t o   h e l d i s pl a y   t h e   b e s t   a pp r o a c h.   E x pe ri m e n t   r e s ul t s   i n   T a b l e s   a n s h o w s   t h a t   D F P A   t e n ds   t o   f i n t he   o pt i m a l   s o l ut i o n   f a s t e t ha n   t h e   b e n c hm a rke a l go ri t hm s   a n o f   t h e   o t h e p r o po s e a l go r i t hm   J F P A   a t   hi g h e r   c o m pl e xi t y .   W e   f ur t h e r   pe r f o r m   t h e   de t a i l e a n a l y s i s   a n c o m pa r i s o n   o f   t h e   a l go r i t hm s :   P S O ,   A F P A ,   J F P A ,   a n D F P A   a s   de pi c t e i F i gu r e   t o   23.     It   i s   r e m a r ke t ha t   t h e   e xpe ri m e n t a l   r e s ul t s   o f   G A   a r e   e xc l u de f r o m   t h e   a n a l y s i s   a n c o m pa ri s o n   b e c a us e   i t   do e s   n o t   r e a c t h e   gl o b a l   o pt i m a l   v a l ue   ( fv = 1. 0) .   Evaluation Warning : The document was created with Spire.PDF for Python.
                     IS S N :   25 02 - 475 2   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   20 ,   N o .   3 D e c e m be r   2 020   :   1556   -   1568   1562   T a b l e   1 .   S u m m a r y   of   f i t n e s s   v a l ue   a nd  ge n e r a t i o n u m b e r   (s m a l l   s c a l e   d a t a s e t )   P o p   S i z e   Co m p l e x i t y   L e v e l   GA   PSO   A F P A   J F P A   D F P A   F V   G e n   F V   G e n   F V   G e n   F V   G e n   F V   G e n   10   10   1 . 0 0   707   1 . 0   18   1 . 0 0   22   1 . 0   23   1 . 0   14   30   0 . 8 8   199   1 . 0   52   1 . 0 0   175   1 . 0   110   1 . 0   56   50   0 . 7 0   8 60   1 . 0   332   1 . 0 0   360   1 . 0   335   1 . 0   191   60   0 . 5 8   979   1 . 0   632   1 . 0 0   932   1 . 0   554   1 . 0   587   50   10   1 . 0 0   117   1 . 0   2   1 . 0 0   4   1 . 0   4   1 . 0   2   30   0 . 9 0   121   1 . 0   40   1 . 0 0   122   1 . 0   63   1 . 0   42   50   0 . 7 3   115   1 . 0   295   1 . 0 0   210   1 . 0   299   1 . 0   147   60   0 . 6 2   129   1 . 0   497   1 . 0 0   506   1 . 0   356   1. 0   293   100   10   1 . 0 0   53   1 . 0   1   1 . 0 0   2   1 . 0   1   1 . 0   1   30   0 . 9 3   789   1 . 0   19   1 . 0 0   52   1 . 0   52   1 . 0   34   50   0 . 7 7   316   1 . 0   154   1 . 0 0   199   1 . 0   169   1 . 0   132   60   0 . 6 5   337   1 . 0   488   1 . 0 0   338   1 . 0   295   1 . 0   252       T a b l e   2 .   S u m m a r y   of   f i t n e s s   v a l ue   a nd  ge n e r a t i o n u m b e r   ( l a r ge   s c a l e   da t a s e t )   P o p   S i z e   Co m p l e x i t y   L e v e l   GA   PSO   A F P A   J F P A   D F P A   F V   G e n   F V   G e n   F V   G e n   F V   G e n   F V   G e n   10   10   0 . 9 7   12   1 . 0 0   97   1 . 0 0   495   1 . 0   433   1 . 0   127   30   0 . 8 0   2256   1 . 0 0   527   1 . 0 0   1343   1 . 0   885   1 . 0   768   50   0 . 6 2   1062   1 . 0 0   1813   1 . 0 0   2362   1 . 0   2119   1 . 0   1676   60   0 . 5 2   838   0 . 9 8   1822   0 . 9 8   2709   1 . 0   2784   1 . 0   2776   50   10   0 . 9 8   2751   1 . 0 0   65   1 . 0 0   349   1 . 0   287   1 . 0   98   30   0 . 8 2   742   1 . 0 0   417   1 . 0 0   954   1 . 0   789   1 . 0   516   50   0 . 6 4   1600   1 . 0 0   1483   1 . 0 0   1964   1 . 0   1925   1 . 0   1188   60   0 . 5 3   873   0 . 9 9   2662   0 . 9 9   2852   1 . 0   2572   1 . 0   2615   100   10   0 . 9 8   1773   1 . 0 0   40   1 . 0 0   293   1 . 0   212   1 . 0   69   30   0 . 8 3   430   1 . 0 0   235   1 . 0 0   754   1 . 0   748   1 . 0   375   50   0 . 6 6   314   1 . 0 0   1197   1 . 0 0   1686   1 . 0   1883   1 . 0   824   60   0 . 5 6   2035   0 . 9 9   2545   0 . 9 9   2642   1 . 0   2836   1 . 0   1995       F i g u re s   4   t o   6   s ho w   a   c o m p a r i s o o f   ho w   t he   a l g o r i t h m s   b e h a v e   ( c o m p l e x i t y   b e ha v i o r)   f o s m a l l   d a t a s e t ;   i t   c a b e   o b s e rv e d   i t h e   re s u l t s   t h a t   i nc re a s i n g   t he   p o p u l a t i o s i z e   i m p ro v e s   t he   c o nv e r g e nc e   ( l e s s   n u m b e o f   i t e r a t i o ns .   D F P A   t e nd s   t o   i m p ro v e   i t s   n u m b e o f   i t e ra t i o ns   d e s p i t e   i nc r e a s i n g   t he   l e v e l   o f   c o m p l e x i t y   a n d   s i nc e   t h e   i t e r a t i o ns   a re   i m p ro v i n g   i n   D F P A   i t   a l s o   f i n d s   t he   o p t i m a l   s o l u t i o n   f a s t e r   t h a n   t he   b e nc h m a r k e d   a l g o r i t h m s   a n d   o f   J F P A .   F i g u re s   7   t o   9   s ho w   t ha t   t he   P S O   a nd   A F P A   s u f f e rs   w he i t   i s   t e s t e d   o l a rg e   d a t a   s e t ,   b o t a l g o ri t hm s   w e re   no t   a b l e   t o   a c hi e v e   t he   g l o b a l   o p t i m u m   v a l u e   (f v = 1 . 0 )   i t he   m o s t   c o ns t ra i nt   c o m p l e x i t y   l e v e l   ( 6 0 % ) ;   i nc re a s i ng   t he   p o p u l a t i o s i z e   d i d   no t   i m p ro v e   t he   nu m b e o f   i t e ra t i o ns   ( d e c re a s i ng ) ,   a nd   i nc re a s i ng   t he   nu m b e o f   i t e ra t i o ns   d i d   no t   a l s o   he l p   i n   a c h i e v i ng   t he   m a x i m u m   v a l u e .   D F P A ,   o t he   o t he h a nd ,   i nc re a s i ng   t he   s i z e     o f   t he   d a t a s e t   a nd   i nc re a s i ng   t he   c o ns t ra i nt   c o m p l e x i t y   l e v e l   t e nd   t o   i m p ro v e   t he   nu m b e o f   i t e ra t i o ns ;     a s   t he   p o p u l a t i o s i z e   i s   i nc re a s e d ,   D F P A   c a f i nd   t he   m a x i m u m   v a l u e   f a s t e t h a t he   b e nc hm a rk e d   a l g o ri t h m s .             F i gu r e   4 .   Co m p l e xi t y   b e h a v i o r   (s m a l l   s c a l e   da t a   s e t ,   po pul a t i o n   s i z e = 10)     F i gu r e   5 .   Co m p l e xi t y   b e h a v i o r   (s m a l l   s c a l e   da t a   s e t ,   po pul a t i o n   s i z e = 50)       T he   re s u l t s   c a b e   s ho w e d   i F i g u re s   1 0   t o   1 t ha t   t he   p o p u l a t i o s i z e   i nf l u e nc e s   t he   a l g o ri t hm s   p e rf o rm a nc e   a s   i n d i c a t e d   b y   t he   nu m b e o f   i t e ra t i o ns .   I nc re a s i ng   t he   p o p u l a t i o m a y   he l p ,   b u t   w he t he   c o m p l e x i t y   c o ns t r a i nt s   a re   a d d e d ,   i t   m a y   no t   he l p   i m p ro v e   t he   nu m b e o f   i t e ra t i o ns   a s   t he   c o m p l e x i t y   l e v e l   i s   i nc re a s e d .   F o a l l   Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752     Ne w   hy br i f l ow e r   pol l i na t i o a l gor i t hm   w i t dr a gonf l y   al go r i t hm   a nd  j a c c ar d . . .   ( Ma .   S hi e l a   C.   Sa pul )   1563   t he   t e s t   re s u l t s   s ho w i F i g u re s   1 0   t o   1 3 ,   D F P A   p e rf o rm s   b e t t e w he t he i t s   p o p u l a t i o s i z e   a nd   c o m p l e x i t y   l e v e l   a re   i nc re a s e d .   A s   i nd i c a t e d ,   i t   h a s   l e s s   i t e ra t i o c o m p a re d   w i t h   t he   a l g o r i t hm s   m e nt i o ne d   i t he   f i g u re s .               F i gu r e   6 .   Co m p l e xi t y   b e h a v i o r   ( s m a l l   s c a l e   da t a   s e t ,   p o pul a t i o n   s i z e = 100)             F i gu r e   7 .   Co m p l e xi t y   b e h a v i o r   ( l a r ge   s c a l e   da t a   s e t ,   po pul a t i o n   s i z e = 10)         F i gu r e   8 .   Co m p l e xi t y   b e h a v i o r   ( l a r ge   s c a l e   da t a   s e t ,   po pul a t i o n   s i z e = 50)           F i gu r e   9 .   Co m p l e xi t y   b e h a v i o r   ( l a r ge   s c a l e   da t a   s e t ,   po pul a t i o n   s i z e = 100)             F i gu r e   10 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pul a t i o n   s i z e s c o m pl e xi t y   l e ve l = 10   ( s m a l l   s c a l e   da t a   s e t )     F i gu r e   11 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pul a t i o n   s i z e s c o m pl e xi t y   l e ve l = 30   ( s m a l l   s c a l e   da t a   s e t )   Evaluation Warning : The document was created with Spire.PDF for Python.
                     IS S N :   25 02 - 475 2   In do n e s i a J   E l e c   E ng  &   Co m S c i ,   V o l .   20 ,   N o .   3 D e c e m be r   2 020   :   1556   -   1568   1564         F i gu r e   12 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pul a t i o n   s i z e s c o m pl e xi t y   l e ve l = 5 0   ( s m a l l   s c a l e   da t a   s e t )     F i gu r e   13 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pu l a t i o n   s i z e s c o m pl e xi t y   l e ve l = 60   ( s m a l l   s c a l e   da t a   s e t )       O n e   w a y   t o   t e s t   t h e   pe r f o r m a n c e   of   t h e   a l go ri t hm   f o r   v a r i o us   p o p ul a t i o n   s i z e s   i s   t o   t e s t   w h e t h e   t h e   s i z e   of   t h e   da t a s e t   a f f e c t s   i t s   pe r f o r m a n c e .   R e s ul t s   i n   F i gu r e s   14  t o   17  s h ow s   t h a t   a   l a r ge   da t a s e t   m a y   a f fe c t   t h e   pe r f o r m a n c e   of   t h e   a l go r i t hm   a s   i n d i c a t e by   a   h i g h e r   n u m b e r   of   i t e r a t i o n s   r e qui r e t o   r e a c   t h e   gl o b a l   m a x i m um   v a l ue .   It   s h o ul b e   a dd r e s s e t h a t   i F i gu r e   17  P S O   a n A F P A   d i n o t   p r o v i de   a o pt i m a l   s o l ut i o n   f o r   t h e   l a r ge   s c a l e   da t a s e t   w i t h   c o m pl e xi t y   l e ve l   e qua l   60   (a s   r e f e rr e i n   de t a i l e r e s ul t   i n   T a b l e   2) ,   t h e r e f o r e ,   t h e   f i gu r e   s h o w s   t h e   m a xi m um   n um b e of   i t e r a t i o n   t ha t   t h e y   c a n   a c hi e v e   t h e i h i g h e s t   f i t n e s s   v a l ue s   (l e s s   t h a n   1 . 0) .   T h e   da s h   b a r   i n   F i gu r e   17  i ndi c a t e s   n o n - o pt i m a l   r e s ul t s   (f v < 1. 0).   I n c r e a s i n g     t h e   s i z e   o f   t h e   po pul a t i o n   m a y   h e l a c hi e v e   t h e   o pt i m a l   s o l u t i o n,   b ut   i t   r e qui r e s   s e v e r a l   i t e r a t i o n s .   It   c a a l s b e   ob s e r v e f r o m   t h e   t e s t   r e s ul t s   t ha t   i n c r e a s i n g   t h e   po pul a t i o n   s i z e   m a y   n o t   h e l a t   a l l   s o m e   a l go ri t hm s   (P S O   a n A F P A a c hi e v e   t h e   o pt i m a l   s o l ut i o n   b e c a us e   of   t h e   c o n s t ra i nt   c o m pl e xi t y .   D e s pi t e   t h e   c o n s t ra i nt   f a c t o i i m p r o v i n g   t h e   r e s ul t s   by   i n c r e a s i ng  t h e   po pul a t i o n ,   a m o n g   t h e   a l go r i t hm s   p r e s e nt e i t h e   F i gu r e s ,   D F P A   pr o v i de b e t t e r   r e s ul t s   i t h e   m o s t   c o n s t r a i nt   c o m pl e xi t y   l e v e l .   R e f e r r i ng  t o   t h e   r e s ul t s   i n   T a b l e s   a n d   2 ,   F i gu r e s   t o   17  i t   c a b e   ob s e r v e t h a t   i n c r e a s i ng  t h e   po pu l a t i o n   s i z e   s i g n i f i c a n t l y   i m pr o v e s   t h e   num b e r   o i t e ra t i o n s ,   a n r e f e r ri n t o   T a b l e   2,   i n c r e a s i n a l s o   t h e   n u m b e r   of  i t e r a t i o n s   a l l o w s   t h e   a l go ri t hm   t o   a c h i e v e   t h e   m a x i m um   f i t n e s s   v a l ue   f o r   l a r ge   s c a l e   da t a s e t .   I t   h a s   b e e n   o bs e r v e i n   F i gu r e s   10  t o   16 ,   i n c r e a s i n g     t h e   po pul a t i o n   s i z e   i n c r e a s e s   t h e   c ha n c e   of  f i n d i n t h e   o pt i m a l   s o l ut i o n.   H ow e v e r ,   fo r   s o m e   a l go r i t h m s   (P S O   a n A F P A i n c r e a s i ng   t h e   po pul a t i o n   s i z e   m a y   n o t   i m p r o ve   t h e   s o l ut i o n   o r   t h e   c o n ve r ge n c e   ra t e   b e c a us e   po pul a t i o n   s i z e   de pe n ds   o n   o t h e r   pa ra m e t e r s   l i ke   t h e   di f f i c ul t y   of   t h e   pr o b l e m   o r   t h e   c o m pl e xi t y   l e v e l .   A l s o ,   i n c r e a s i ng  t h e   n u m b e r   o f   i t e r a t i o n s   di n o t   m a ke   s o m e   a l g o r i t hm s   (P S O   a n d   A F P A t o   f i n t h e   m a x i m um   f i t n e s s   v a l ue   i n   t h e   l a r ge   s c a l e   da t a s e t   e s pe c i a l l y   fo r   t h e   m o s t   c o m pl e da t a s e t .   T h e   pe r f o r m a n c e   of   a n   a l go r i t h m   c a n   b e   t e s t e i n   t e rm s   o f   t h e   e xe c ut i o n   t i m e .   F i gu r e s   18  t o   20   de s c r i b e   t h e   pe r f o r m a n c e   of   t h e   a l go r i t hm s   f o r   s m a l l   s c a l e   da t a   s e t   a t   1000  i t e r a t i o n s .   I n   p a r t i c ul a r,     i n c r e a s i ng  t h e   po pul a t i o s i z e   w i l l   r e s ul t   i n   a n   a l go r i t h m ’s   e xe c ut i o n   t i m e   l o n ge r.   I n c r e a s i n g   t h e   po pul a t i o n   s i z e   a n d   i n c r e a s i n g   t h e   c o m pl e xi t y   l e ve l   t e n n o t   t o   i m pr o v e   t h e   e xe c ut i o n   t i m e .   T h e   t w o   pr o po s e d     t w o - h y b r i F P A   r e l a t i v e l y   t a ke s   a   l o n ge r   t i m e   c o m pa r e d   w i t h   t h e   A F P A ,   t h i s   i s   due   t o   t h e   a ddi t i o na l   o pe r a t i o n s   t o   b e   pe r f o r m e du r i ng  l o c a l   po l l i na t i o n   i n   J F P A ,   a nd  a s   t h e   o pt i m i z a t i o n   p r o g r e s s e s   i n   D F P A   t h e r e   i s   a   c o n s t a n t   upd a t e   o f   t h e   n e i g h b o rh o o i n   b o t l o c a l   a n d   g l o b a l   po l l i na t i o n .             F i gu r e   14 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pul a t i o n   s i z e s c o m p l e xi t y   l e ve l = 10    ( l a r ge   s c a l e   da t a   s e t )     F i gu r e   15 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pul a t i o n   s i z e s c o m pl e xi t y   l e ve l = 30    ( l a r ge   s c a l e   da t a   s e t )     Evaluation Warning : The document was created with Spire.PDF for Python.
In do n e s i a J   E l e c   E ng  &   Co m S c i     IS S N :   2502 - 4752     Ne w   hy br i f l ow e r   pol l i na t i o a l gor i t hm   w i t dr a gonf l y   al go r i t hm   a nd  j a c c ar d . . .   ( Ma .   S hi e l a   C.   Sa pul )   1565         F i gu r e   16 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pul a t i o n   s i z e s c o m pl e xi t y   l e ve l = 50   ( l a r ge   s c a l e   da t a   s e t )     F i gu r e   17 .   A l go ri t hm s   b e h a v i o f o r   v a r i o us   po pul a t i o n   s i z e s c o m pl e xi t y   l e ve l = 60   ( l a r ge   s c a l e   da t a   s e t )             F i gu r e   18 .   E xe c ut i o t ime   ( s m a l l   s c a l e   da t a   s e t ,   po pul a t i o n   s i z e = 10)     F i gu r e   19 .   E xe c ut i o t ime   (s m a l l   s c a l e   da t a   s e t ,   po pul a t i o n   s i z e = 50)           F i gu r e   20 .   E xe c ut i o t ime   ( s m a l l   s c a l e   da t a   s e t ,   po pul a t i o s i z e = 100)       A n o t h e w a y   t o   t e s t   t h e   pe r f o r m a n c e   o f   t h e   a l go r i t hm   i n   t e rm s   o f   t h e   e xe c ut i o t i m e   i s   f o r   v a r i o us   po pul a t i o n   s i z e s   i s   t o   t e s t   w h e t h e r   t h e   s i z e   of   t h e   da t a s e t   a f fe c t s   i t s   pe r fo r m a n c e .   R e s ul t s   i n   F i g u r e s   21  t o   23   s h o w s   t h a t   a   l a r ge   d a t a s e t   m a y   a ffe c t   t h e   e xe c ut i o n   t i m e   a s   i n di c a t e by   t h e   hi g h e r   n u m b e r   o f   t h e   e xe c ut i o n   t i m e .   G e n e r a l l y ,   i n c r e a s i ng  t h e   po pul a t i o n   s i z e   a s   w e l l   a s   t h e   s i z e   of   t h e   da t a   a n t h e   n u m b e r   o f   i t e r a t i o n s   c a i n c r e a s e   t h e   e xe c ut i o n   t i m e   f o r   a l l   a l go ri t hm s .   T h e   t w o   pr o po s e t w o - h y b r i F P A   r e l a t i v e l y   t a ke s   a   l o n ge r   t i m e   c o m pa r e w i t h   t h e   A F P A ;   t hi s   i s   due   t o   t h e   s a m e   r e a s o a s   s t a t e i F i g u r e s   18   t o   20 .   Evaluation Warning : The document was created with Spire.PDF for Python.