I AE I nte rna t io na l J o urna l o f   Art if icia l In t ellig ence   ( I J - AI )   Vo l.   6 ,   No .   3 Sep tem b er   2017 ,   p p .   1 39 ~ 1 4 2   I SS N:  2252 - 8938 ,   DOI : 1 0 . 1 1 5 9 1 /i j ai. v 6 . i3 . p p 1 39 - 14 2          139       J o ur na l ho m ep a g e h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I J AI   M ulti - O pera tor  G ene tic  Alg o rith m   for Dyn a m ic  O pti m i z a tion  Proble m s       Al - kh a f a j i A m e n   Un iv e rsit y   of   Tec h n o lo g y ,   Ba g h d a d ,   Ira q       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   J u n   1 4 ,   201 7   R ev i s ed   A u g   1 6 ,   2 0 1 7   A cc ep ted   A u g   2 9 ,   2 0 1 7       M a in tain i n g   p o p u lati o n   d iv e rsity   is  th e   m o st  n o tab le  c h a ll e n g e   in   so lv in g   d y n a m ic  o p ti m i z a ti o n   p ro b lem s   (DO P s).  T h e re f o re ,   th e   o b jec ti v e   o f   a n   e ff ici e n d y n a m ic  o p ti m iz a ti o n   a lg o rit h m   is  to   trac k   th e   o p ti m u m   in   th e se   u n c e rtain   e n v iro n m e n ts,   a n d   to   lo c a te  th e   b e st  so lu ti o n .   I n   th is   w o rk ,   we   p ro p o se   a   f ra m e w o rk   th a is  b a s e d   o n   m u lt o p e ra to rs   e m b e d d e d   in   g e n e ti c   a lg o rit h m ( GA a n d   th e se   o p e ra to rs  a re   h e u risti c   a n d   a rit h m e ti c   c ro ss o v e rs   o p e ra to rs.  T h e   ra ti o n a le  b e h i n d   t h is  is  to   a d d re ss   th e   c o n v e rg e n c e   p ro b le m   a n d   t o   m a in tain   t h e   d iv e rsity .   T h e   p e rf o rm a n c e   o f   th e   p r o p o se d   f ra m e w o rk   is   tes ted   o n   th e   w e ll - k n o w n   d y n a m ic   o p ti m iza ti o n   f u n c ti o n i. e . ,   On e M a x ,   P late a u ,   Ro y a Ro a d   a n d   De c e p ti v e .   E m p iri c a r e su lt s sh o w   th e   su p e rio rit y   o th e   p r o p o se d   a lg o rit h m   w h e n   c o m p a re d   to   sta te - of - th e - a rt  a lg o rit h m f ro m   th e   li tera tu re .   K ey w o r d :   A r it h m etic  cr o s s o v er   o p er ato r     D y n a m ic o p ti m iza ti o n   f u n c ti o n s     E v o lu tio n ar y   al g o r ith m s   Gen etic  al g o r ith m     Heu r is tic  cr o s s o v er     Co p y rig h ©   2 0 1 7   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Al - k h a f aj i A m e n ,   Un i v er s it y   of   T ec h n o lo g y ,   6 2   s tr ee t,  A l k ar ad a,   B ag h d ad ,   I r aq .   E m ail:  a m en k h ab ee r @ g m a il.c o m       1.   I NT RO D UCT I O N     I n   t h r ec en d ec ad es,  d y n a m ic  o p ti m is a tio n   p r o b le m s   ( DOP s )   h av e   b ee n   o n o f   th m aj o r   in ter esti n g   r esear ch   s u b j ec ts ,   d u to   th f ac t h at  DOP s   r ep r esen r ea w o r ld   o p ti m is atio n   s ce n ar io s   [ 1 ] .   T h p o s s ib ilit y   o f   p r o b le m   ch an g i n g   o v er   ti m i n f l u en ce s   o n   t h f u n ctio n all y   a n d   b eh av er   o f   an   o p ti m a s o lu tio n .   T h er ef o r e,   th er is   n ee d   to   d esig n   an   ef f ec ti v e   E v o lu tio n ar y   Alg o r it h m   ( E A)   to   h an d le  DOP s .   I n d ee d ,   th n atu r e   o f   E in   g en er atin g   d i f f er en t   s o lu tio n s   i n   e v er y   s i n g le   ev o l u tio n   h e lp s   E A   to   ad ap w it h   ch an g es   o f   DOP s .   B y   e m p lo y in g   an   E A   s u c h   a s   g e n etic  alg o r ith m   ( G A ) ,   th e   DOP s   w i ll  b s o l v ed   [ 2 ,   3 ] E x is ti n g   s t u d ies  s h o w   th at   a d ap tiv alg o r it h m s   t h at  u s d iv er s it y   m ain tain i n g   m et h o d s   h a v b ee n   w id el y   d ev elo p ed   to   ad d r ess   DOP s   [ 4 ] .   T h is   p ap er   aim s   to   d ev elo p   cr o s s o v er   o p er ato r   f o r   GA   in   o r d er   to   ef f ec tiv el y   ad d r ess   DOP s .   E s s en tiall y ,   t h d ep en d e n c y   o f   G o n   g e n etic   o p er ato r s   g e n er all y   an d   cr o s s o v er   o p er ato r s   p r ac ticall y   ef f ec t   its   p er f o r m an ce   [ 4 ] .   Yet,   th ch an ce   o f   r ep r o d u ctio n   n e o f f s p r in g   w ill  b lo s in   ca s e   o f   h av i n g   id e n tic al  ch r o m o s o m e s   ( p ar en t s )   t h at   h av e   b ee n   s elec ted   f o r   t h cr o s s o v er   o p er a to r   d u r in g   t h ev o l u tio n   s ta g e.   Hen ce ,   th d iv er s i f y i n g   t h s el ec tin g   cu t - p o in r ath er   th a n   u s in g   f i x ed   o n es  co u ld   o v er co m th is   id en tica ca s e   o f   f ail u r e.   T h is   p ap er   in tr o d u ce s   h y b r id   ad ap ti v cr o s s o v er   o p er ato r   b ased   o n   p r e - ev al u ated   c h r o m o s o m e s   b ef o r p ass in g   i n d iv id u als  to   t h n e x s tag e.   T h id ea   o f   t h is   w o r k   i s   to r ed u ce   co m p u tatio n   ti m e,   r ed u ce s   t h r an d o m   ch a n ce   o f   co m b i n e s   g en s   o f   t w o   ch r o m o s o m e s   an d   en h a n ce   th r es u lt s   to w ar d   b etter   s o lu tio n .   T o   ac co m p lis h   th i s   ai m   an d   t o   r esp o n d   t o   a   r ec en ca ll  f o r   r esear ch   to   ad d r ess   DOP s ,   w h a v to   r ec all  th w ell - k n o w n   d y n a m i o p ti m is at io n   f u n ct io n s   s u ch   as,  On e - m a n ,   P latea u ,   R o y al   R o ad   an d   Dec ep tiv e,   in   o r d er   to   ex a m i n t h e f f ec t iv e n e s s   o f   t h p r o p o s ed   m et h o d .   E x p er im e n tal  r es u lt s   s h o w   t h at  t h p r o p o s e d   alg o r ith m   i s   ab le  to   ac h iev c o m p eti tiv r es u lt s   w h en   co m p ar ed   to   o th er   av ailab le  m eth o d s .   T h r est  o f   th is   p ap er   is   o r g an ized   as  f o llo w s .   I n   s ec tio n   2 ,   th p r o p o s ed   m et h o d   in   th i s   s t u d y   i s   g i v e n .   Nex s ec tio n   d ea l s   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   201 7   :   1 39     14 2   140   w it h   th e   e x p er i m e n tal  r e s u l ts   an d   r ele v a n d is c u s s io n .   Fi n all y ,   s ec tio n   4   co n c lu d es   t h e   r esu l ts   w it h   s o m r ec o m m e n d atio n s   o n   th f u tu r w o r k .       2.   P RO P O SE M E T H O D   I n   th i s   p ap er ,   w p r o p o s h y b r id   cr o s s o v er   o p er ato r   f o r   GA   to   ef f ec ti v el y   s o l v DOP s .   T h d e p en d en c y   o f   G A   o n   g en et ic  o p er ato r s   g en er all y   an d   cr o s s o v er   o p er ato r s   p r ac ti ca ll y   ef f ec o n   its   p er f o r m a n ce   [ 1 ] .   Ho w e v er ,   th ch an ce   o f   r ep r o d u ctio n   n e w   o f f s p r in g   w ill  b lo s i n   ca s o f   h a v in g   id en tical  ch r o m o s o m e s   ( p ar en t s )   th at  h av b ee n   s elec ted   f o r   cr o s s o v er   o p e r ato r   d u r in g   t h ev o lu ti o n   s tag e.   He n ce ,   th e   d iv er s i f y i n g   t h cu t - p o in s ele ctio n   in s tead   o f   u s i n g   f i x ed   o n es c o u ld   o v er co m t h is   id en tic al  ca s o f   f ail u r as  w ell   as  a v o id in g   th r a n d o m   c o m b i n atio n   o f   t h g en s   o f   t h s elec ted   t w o   c h r o m o s o m es.  T h is   p ap er   p r esen ts   h y b r id   ad ap tiv cr o s s o v er   o p er ato r   b ased   o n   p r e - ev alu a ted   ch r o m o s o m e s   b ef o r p ass in g   in d iv id u als  to   th e   n ex s ta g e.   B asicall y ,   it  u s e s   t w o   t y p e s   o f   cr o s s o v er   as  w i ll  b ex p lain ed   b elo w :     2 . 1 .     H euristic   cr o s s o v er   o pera t o ( H CO )   HC s h i f t s   m ar g i n all y   c h i ld   f r o m   w o r s f it n es s   v alu to   th b e s f it n es s   v a lu o f   p ar en [ 2 ] .   T h is   s h i f ti n g   i s   b ased   o n   R atio n   v alu w h ic h   is   r an d o m   v alu b et w ee n   0 s   an d   1 s .   I n d ee d ,   th v alu o f   R atio n   co u ld   b s etti n g   i n   b y   d ef au lt.  I f   b o th   P 1   an d   P2   ar e   p ar en ts   an d   P 1   h as  b etter   f itn es s   v al u th a n   P 2 ,   th en   1 . 2   w ill  b s etti n g   as   R atio n   v al u [ 1 ] .   T h n e w   o f f s p r in g   w ill  b g e n er ated   b as ed   o n   th e   f o llo w in g   eq u atio n :     Of f s p r in g s =B est P ar en t +   β    ( B est P ar en   W o r s t P a r e n t) .     2 . 2 .     Arit h m et ic  Cro s s o v er   ( ACO )   AC r et u r n s   a n   o f f s p r in g   t h a ar h o ld   m ea n   f it n es s   o f   t wo   in d iv id u als   [ 1 ] .   Alp h i s   a   tin y   v al u b et w ee n   [ 0 ,   1 ]   g en er ated   r an d o m l y .   I f   C h r o m o s o m e1   an d   C h r o m o s o m e2   ar p ar en ts ,   an d   C h r o m o s o m e1   h a s   th b est f itn e s s ,   t h o f f s p r in g   w it h   b g e n er ate  as  f o llo w s :     Offs p r in g   *   B est P a r en t +  ( 1 - α ) *   W o r s t P a r en t.     2 . 3 .     H y brid Cr o s s o v er   O pera t o ( H YCO )   Un d o u b ted l y ,   t h e f f ec t iv e n es s   o f   cr o s s o v er   i s   d ep en d s   o n   t h r esu lts   o f   s elec ted   p ar en [ 1 ] .   Du to   th n at u r o f   ev o l u tio n   t h n ec ess it y   to   p r o d u ce   b etter   s o lu tio n   i s   r ep r esen ted   in   th i s   s t ag e.   Ou r   p r o p o s e d   o p er ato r   in v esti g ates   t h ad v an tag e s   o f   H C w it h   AC cr o s s o v er .   B o th   o f   t h e m   e x a m i n t h f it n es s   o f   ch r o m o s o m e   b ef o r co m b i n i n g   t h e m .   T h r an d o m   s elec tio n   to   cu t - p o in t   in v o k e s   at   f ir s s tep .   Ou r   id ea   i s   to   en h a n ce   t h m at in g   p r o ce s s .   T h co m p lete  p r o ce d u r is   p r esen ted   in   Fi g u r 1 .           Fig u r 1 .   P s eu d o - C o d f o r   Mu lti - C r o s s o v er - B ased   HC & AC       H YCO   pa ra m et rize :   1.   R atio n   i s   f i x ed   v al u e:  =1 . 2 .   2.   A lp h r an d o m   v alu b et w ee n   [ 0 ,   1 ] .   3.   CP   is   cr o s s o v er   p o s s ib ilit y .   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Mu lti - Op era to r   Gen etic  A lg o r ith fo r   Dyn a mic  Op timiz a tio n   P r o b lems   ( A l - kh a fa ji A men )   141   As  s h o w n   i n   Fi g u r 1 ,   th e   h y b r id   cr o s s o v er   b ased   o n   co m b in in g   t h f ea t u r es  o f   t w o   c h r o m o s o m e s   b y :   1.   I f   th e   p ar en i s   m o r w o r t h   th a n   p ar en t h e n   t h o f f s p r in g   w ill  b i n f lu e n ce d   b y   t h e   b etter   o n ce   b y   in cl u d in g   its   f ea t u r es i n s id t h eir   g en s .   2.   I f   b o th   o f   ch r o m o s o m e s   h a v s i m ilar   q u alit y ,   th e n   th e   n e w   o n w il h as  co m b in atio n   o f   t w o   ch r o m o s o m e s   b y   e m p lo y   ar i t h m e tic  cr o s s o v er   w h ic h   g en e r ates  h y b r id   s o lu tio n s   th at   ef f ec ted   b y   b o t h   p ar en ts .       3.   RE SU L T A ND  AN AL Y SI S   I n   t h is   s ec tio n ,   t h p er f o r m an ce   o f   o u r   p r o p o s ed   alg o r ith m   MCO  i s   ev a lu ated   u s in g   f o u r   b in ar y   te s t   f u n ctio n s ,   w h ich   ar On eM a x ,   P latea u ,   R o y al  R o ad   an d   Dec ep tiv [ 4 ] .   T h ese  f u n ct io n s   o r ig i n all y   ar e   s tatio n ar y   a n d   h a v b ee n   w id el y   u s ed   b y   m a n y   r esear ch er s   to   ev alu ate  th p er f o r m an ce   o f   th eir   alg o r it h m s .   I n   th is   p ap er ,   w e   u s ed   d y n a m ic  g e n er ato r   p r o p o s ed   b y   [ 5 ,   6 ]   to   g en er ate  d y n a m ic   en v ir o n m e n t s .   T h p ar am eter   v alu e s   o f   t h p r o p o s ed   m et h o d   ar p r esen ted   in   T ab le  1 .       T ab le  1 .   P ar am eter s   s e tti n g s   P a r a me t e r   V a l u e   P o p u l a t i o n   S i z e   S o l u t i o n   s i z e   N u mb e r   o f   i t e r a t i o n s   T   P   50   1 0 0   1 0 0   1 0 0   0 . 9       T o   ass u r f air   co m p ar is o n   w i th   t h s tate - of - th e - ar ap p r o ac h es,  t h p ar a m eter s   T   ( w h ic h   r ep r esen ts   th p er io d icall y   o f   ch a n g e s )   an d   P   ( w h ic h   r ep r esen ts   t h e   a m o u n o f   ch a n g e)   ar s et  b ased   o n   th w o r k   r ep o r ted   in   [ 4 ] .   T h p r o p o s ed   m et h o d   is   co m p ar ed   ag ain s t h f o llo w i n g   al g o r ith m s   t h at  h a v b ee n   p r o p o s ed   in   th e   s cien t if ic  l iter atu r e:       T ab le  2 .   R esu lts   C o m p ar is o n   F u n c t i o n   n a me   M O C   P o p - HC   M I G A   M EG A   A H M A   M R I G A   O n e M a x   9 9 . 4   8 6 . 3 5   9 4 . 0   7 9 . 3   9 5 . 8 9   8 0 . 8   P l e a t e a u   9 9 . 5   7 4 . 2 1   -   -   6 2 . 8 8   -   R o y a l   R o a d   9 9 . 7   5 1 . 1 1   -   -   5 2 . 5 2   -   D e c e p t i v e   9 7 . 9   7 2 . 5 6   7 1 . 1   8 3 . 1   8 5 . 7 5   6 8 . 6   N o t e :   v a l u e s i n   b o l d   f o n t   i n d i c a t e   t h e   b e st   r e su l t s.   - :   n o   r e su l t s re p o r t e d .         P o p - HC : A n   E v o l u tio n ar y   Hil l Cl i m b in g   A l g o r ith m   f o r   D y n a m ic  Op ti m is a tio n   P r o b lem s   [ 7 ] .   MI GA : G e n etic  al g o r ith m   w i t h   m e m o r y   b ased   i m m i g r a n ts   [ 6 ] .   ME GA:  m e m o r y - e n h a n ce d   G en etic  al g o r ith m   [ 8 ] .   A HM A:  Me m etic  al g o r ith m   with   t h A HC   o p er ato r   [ 1 ] .   MRIG A : G e n etic  al g o r ith m   with   m e m o r y   a n d   r an d o m   i m m i g r an t s   s c h e m e s   [ 6 ]   T ab le  2   co n tain s   th r es u lt s   o f   th p r o p o s ed   alg o r ith m   a n d   s t ate - of - t h ar t a lg o r it h m s .   A   clo s s cr u ti n y   o f   T ab le  2   r ev ea ls   th at,   o u o f   all  f o u r   in s ta n ce s ,   t h p r o p o s ed   alg o r ith m   o u tp er f o r m s   t h o th er   alg o r it h m s   o v er   th r ee   in s tan ce s .   No te  th at,   th m et h o d s   in   co m p ar is o n   h er d id   n o t   atte m p o n   all  test   f u n c tio n s .   MO C   is   ab le  to   p r o d u ce   b etter   r esu lts   th a n   all  alg o r it h m s   in   3   in s tan ce s ,   an d   ca n   b co n s id er ed   as  co m p etiti v r esu lt s   ac r o s s   O n eM ax   f u n cti o n .   W b eliev e   t h is   is   d u to   t h u s e   o f   th e   MO C   in   o r d er   to   p r eser v th d iv er s i t y   d u r i n g   t h s ea r c h   p r o ce s s .       4.   CO NCLU SI O N   I n   th i s   p ap er   m u lt i - cr o s s o v e r   o p er ato r   w h ic h   h y b r id is es  t h h eu r i s tic  cr o s s o v er   w i th   t h ar ith m etic  cr o s s o v er   to   ef f ec ti v el y   s o lv e   d y n a m ic  o p ti m i s atio n   p r o b lem s   h a s   b ee n   p r ese n ted .   T h r esu lt s   o f   t h is   s t u d y   in d icate   t h at  t h d i v er s it y   o f   p o p u latio n s   n ee d   to   m ec h a n is m   th a ca n   p er - ev a lu ate   th e   g en s   b ef o r m ati n g   th e m .   T h p er f o r m a n ce   o f   t h p r o p o s ed   alg o r ith m   is   as s es s ed   o n   t h d y n a m ic   o p ti m i s at io n   f u n ctio n s .   T h ex p er i m e n tal  r es u lt s   s h o w   th at  th p r o p o s ed   m et h o d   o b tain ed   co m p etiti v r es u lt s   w h e n   co m p ar e d   to   th e   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   201 7   :   1 39     14 2   142   m et h o d s   in   th li ter atu r e.   Fu r th er   w o r k   n ee d s   to   b d o n t o   estab lis h   w h eth er   e m p lo y i n g   an o t h er   t y p o f   ev o lu tio n ar y   al g o r ith m   o r   u s i n g   lo ca l sear ch   al g o r ith m   is   e f f ec ti v in   g etti n g   b etter   s o lu tio n s .       RE F E R E NC E S   [1 ]   W a n g   H,  W a n g   D,  Ya n g   S   (2 0 0 9 A   m e m e ti c   a lg o rit h m   w it h   a d a p ti v e   h il c li m b in g   stra teg y   f o d y n a m ic   o p ti m i z a ti o n   p r o b lem s.  S o f Co m p u ti n g   -   A   F u sio n   o f   F o u n d a ti o n s,  M e th o d o l o g ies   a n d   Ap p li c a ti o n s   1 3   (8 ):   763 - 7 8 0 .   DOI :1 0 . 1 0 0 7 /s0 0 5 0 0 - 0 0 8 - 0 3 4 7 - 3 .   [2 ]   T a lb EG  (2 0 0 2 A   T a x o n o m y   o f   H y b rid   M e tah e u risti c s.  J o u rn a o He u ristics   8   (5 ):5 4 1 - 5 6 4 .   DOI :1 0 . 1 0 2 3 /a: 1 0 1 6 5 4 0 7 2 4 8 7 0   [3 ]   Ya n g   S ,   On g   YS,   Jin   Y (2 0 0 7 E v o lu ti o n a ry   c o m p u tatio n   i n   d y n a m ic   a n d   u n c e rtain   e n v iro n m e n ts,   v o 5 1 .   S p ri n g e r - Ver la g ,   Ber li n   He id e l b e rg .,   [4 ]   S h e n g x ian g   No n - sta ti o n a ry   p ro b lem   o p ti m iza ti o n   u si n g   th e   p rim a l - d u a g e n e ti c   a lg o rit h m .   I n Ev o l u ti o n a ry   Co m p u tatio n ,   CEC.   T h e   C o n g re ss   o n ,   8 - 1 2   De c .   2 0 0 3   2 0 0 3 .   p p   2 2 4 6 - 2 2 5 3   Vo l. 2 2 4 3 .   [5 ]   Ya n g   S ,   Ya o   (2 0 0 5 Ex p e ri m e n tal  stu d y   o n   p o p u latio n - b a s e d   in c re m e n ta lea rn in g   a lg o rit h m f o d y n a m ic   o p ti m iza ti o n   p r o b lem s.  S o f Co m p u ti n g   -   A   F u sio n   o f   F o u n d a ti o n s,  M e th o d o l o g ies   a n d   Ap p li c a t io n s   9   (1 1 ):   8 1 5 - 8 3 4 .   DOI :1 0 . 1 0 0 7 /s 0 0 5 0 0 - 0 0 4 - 0 4 2 2 - 3   [6 ]   Ya n g   S   (2 0 0 8 G e n e ti c   a lg o ri th m w it h   m e m o r y - a n d   e li ti sm - b a se d   imm i g ra n ts  in   d y n a m ic   e n v iro n m e n ts.   Evo lu ti o n a ry   Co mp u t a ti o n   1 6   ( 3 ): 3 8 5 - 4 1 6 .   [7 ]   T u rk y   Ay a d ,   S a lw a n A ,   a n d   Ba rr y   M c .   ' A n   Ev o lu ti o n a ry   Hill   Cli m b in g   A l g o rit h m   F o Dy n a m ic  Op ti m isa ti o n   P r o b lem s' .   M IS TA   (2 0 1 3 ):  3 .   P ri n t.   [8 ]   Ya n g   S   M e m o r y - b a se d   i m m ig r a n ts  f o g e n e ti c   a lg o rit h m s in   d y n a m ic  e n v iro n m e n ts.   In Pro c .   o th e   Ge n e ti c   a n d   Evo l.   C o mp u t.   Co n f . ,   v o l.   2 ,   p p , G ECCO,   2 0 0 5 .   A CM ,   p p   1 1 1 5 - 1 1 2 2 .   Evaluation Warning : The document was created with Spire.PDF for Python.