T E L K O M N I K A ,   V o l . 1 0 ,   N o . 4 ,   D e c e m b e r   2 0 1 2 ,   p p .   6 2 9 ~ 6 3 6   I S S N :   1 6 9 3 - 6 9 3 0   a c c r e d i t e d   b y   D G H E   ( D I K T I ) ,   D e c r e e   N o :   5 1 / D i k t i / K e p / 2 0 1 0         6 2 9       R e c e i v e d   J u l y   1 6 ,   2 0 1 2 ;   R e v i s e d   O c t o b e r   2 6 ,   2 0 1 2 ;   A c c e p t e d   N o v e m b e r   9 ,   2 0 1 2   A n   I m p r o v e d   R o b o t   P a t h   P l a n n i n g   A l g o r i t h m       X u e s o n g   Y a n 1 ,   Q i n g h u a   W u 2 ,3 , H a m m i n   L i u 1 ,4   1 Sc h o o l   o f   C o m p u t e r   S c i e n c e ,   C h i n a   U n i v e r s i t y   o f   G e o s c i e n c e s ,   W u h a n ,   C h i n a   2 H u b e i   Pr o v i n c i a l   K e y   L a b o r a t o r y   o f   I n t e l l i g e n t   R o b o t ,   W u h a n   I n s t i t u t e   o f   T e c h n o l o g y ,   W u h a n ,   C h i n a   3 Sc h o o l   o f   C o m p u t e r   S c i e n c e   a n d   En g i n e e r i n g ,   W u h a n   I n s t i t u t e   o f   T e c h n o l o g y ,   W u h a n ,   C h i n a   4 W u h a n   I n s t i t u t e   o f   Sh i p b u i l d i n g   T e c h n o l o g y ,   W u h a n ,   C h i n a   e - m a i l : y a n x s 1 9 9 9 @ 1 2 6 . c o m       A b s t r a k   R o b o t   p a t h   p l a n n i n g   a d a l a h   m a s a l a h   N P . M e t o d e   o p t i m a s i   t r a d i s i o n a l   t i d a k   e f e k t i f   u n t u k   m e n g a t a s i n y a .   Al g o r i t m a   g e n e t i k a   t r a d i s i o n a l   t e r j e b a k   k e   d a l a m   m i n i m u m   l o k a l   d e n g a n   m u d a h .   O l e h   k a r e n a   i t u ,   d i d a s a r k a n   p a d a   a l g o r i t m a   g e n e t i k a   y a n g   s e d e r h a n a   d a n   m e n g g a b u n g k a n   i d e o l o g i   d a s a r   m e t o d e   d e s a i n   o r t h o g o n a l   k e m u d i a n   d i t e r a p k a n   k e   i n i s i a l i s a s i   p o p u l a s i ,   m e n g g u n a k a n   m e k a n i s m e   e l i t   a n t a r g e n e r a s i ,   s e r t a   p e n g e n a l a n   o p e r a t o r   p e n c a r i a n   a d a p t i f   l o k a l   u n t u k   m e n c e g a h   t e r j e b a k   k e   d a l a m   m i n i m u m   l o k a l   d a n   m e n i n g k a t k a n   k e c e p a t a n   k o n v e r g e n s i   u n t u k   m e m b e n t u k   a l g o r i t m a   g e n e t i k   b a r u .   M e l a l u i   s e r a n g k a i a n   p e r c o b a a n   n u m e r i k ,   a l g o r i t m a   b a r u   t e l a h   t e r b u k t i   e f i s i e n .   Ka m i   j u g a   m e n g g u n a k a n   a l g o r i t m a   y a n g   d i u s u l k a n   u n t u k   m e m e c a h k a n   m a s a l a h   r o b o t   p a t h   p l a n n i n g   d a n   h a s i l   p e n e l i t i a n   m e n u n j u k k a n   b a h w a   a l g o r i t m a   b a r u   t e r b u k t i e f i s i e n   u n t u k   m e m e c a h k a n   m a s a l a h   r o b o t   p a t h   p l a n n i n g   d a n   j a l a n   t e r b a i k   b i a s a n y a   d a p a t   d i t e m u k a n .     K a t a   k u n c i :   o p t i m a l i s a s i   f u n g s i ,   a l g o r i t m a   g e n e t i k a ,   i n i s i a l i s a s i   o r t o g o n a l ,   p e r e n c a n a a n   r o b o t   j a l a n       A b s t r a c t   R o b o t   p a t h   p l a n n i n g   i s   a   N p r o b l e m .   T r a d i t i o n a l o p t i m i z a t i o n   m e t h o d s   a r e   n o t   v e r y   e f f e c t i v e   t o   s o l v e   i t .   T r a d i t i o n a l   g e n e t i c   a l g o r i t h m   t r a p p e d   i n t o   t h e   l o c a l   m i n i m u m   e a s i l y .   T h e r e f o r e ,   b a s e d   o n   a   s i m p l e   g e n e t i c   a l g o r i t h m   a n d   c o m b i n e   t h e   b a s e   i d e o l o g y   o f   o r t h o g o n a l   d e s i g n   m e t h o d   t h e n   a p p l i e d   i t   t o   t h e   p o p u l a t i o n   i n i t i a l i z a t i o n ,   u s i n g   t h e   i n t e r g e n e r a t i o n a l   e l i t e   m e c h a n i s m ,   a s   w e l l   a s   t h e   i n t r o d u c t i o n   o f   a d a p t i v e   l o c a l   s e a r c h   o p e r a t o r   t o   p r e v e n t   t r a p p e d   i n t o   t h e   l o c a l   m i n i m u m   a n d   i m p r o v e t h e   c o n v e r g e n c e   s p e e d   t o   f o r m   a   n e w   g e n e t i c   a l g o r i t h m .   T h r o u g h   t h e   s e r i e s   o f   n u m e r i c a l   e x p e r i m e n t s ,   t h e   n e w   a l g o r i t h m   h a s   b e e n   p r o v e d   t o   b e   e f f i c i e n c y . W e   a l s o   u s e   t h e   p r o p o s e d   a l g o r i t h m   t o   s o l v e   t h e   r o b o t   p a t h   p l a n n i n g   p r o b l e m   a n d   t h e   e x p e r i m e n t   r e s u l t s   i n d i c a t e d   t h a t   t h e   n e w   a l g o r i t h m   i s   e f f i c i e n c y   f o r   s o l v i n g   t h e   r o b o t   p a t h   p l a n n i n g   p r o b l e m s   a n d   t h e   b e s t   p a t h   u s u a l l y   c a n   b e   f o u n d .       K e y w o r d s :   f u n c t i o n   o p t i m i z a t i o n ,   g e n e t i c   a l g o r i t h m ,   o r t h o g o n a l   i n i t i a l i z a t i o n ,   r o b o t   p a t h   p l a n n i n g         1 .   I n t r o d u c t i o n   A u t o n o m o u s   r o b o t s   a r e   d e v e l o p e d   t o   p e r f o r m   h i g h   l e v e l   t a s k   w i t h o u t   f u r t h e r   h u m a n o p e r a t i o n .   T o   a c c o m p l i s h   t h e s e   t a s k s   t h e   r o b o t s   n e e d   t o   m o v e   i n   t h e   r e a l   w o r l d .   I n c o n s e q u e n c e ,   o n e   o f   t h e   m o r e   i m p o r t a n t   p r o b l e m s   t o   b e   s o l v e d   i n   t h e   d e s i g n   o f a u t o n o m o u s   r o b o t s   i s   t h e   p a t h   p l a n n i n g .   T h e s e   p l a n n i n g   p r o b l e m s   c a n   i n v o l v e g e o m e t r i c   w o r k s p a c e ,   c o n s t r a i n t s   a n d   a d d i t i o n a l   c o m p l e x   f e a t u r e s   s u c h   a s   i n c o m p l e t e k n o w l e d g e ,   m o v i n g   o b s t a c l e s ,   s e n s i n g   a n d   m o d e l   u n c e r t a i n t i e s ,   u n p r e d i c t a b i l i t y , k i n e m a t i c s ,   m u l t i p l e   r o b o t s   a n d   g o a l s .   I n   t h e   l a s t   d e c a d e ,   p a t h   p l a n n i n g   h a s   r e c e i v e d c o n s i d e r a b l e   a t t e n t i o n   f r o m   r o b o t i c   c o m m u n i t i e s   s i n c e   t h i s   f u n d a m e n t a l   o p e r a t i o n r e q u i r e s   t h e   s o l u t i o n   o f   a   v a r i e t y   o f   t h e o r e t i c a l   a n d   p r a c t i c a l   p r o b l e m s .   U n t i l   n o w ,   t h e   r e s e a r c h   i n   r o b o t   p a t h   p l a n n i n g   h a s   f o c u s e d   o n   f i n d i n g o p t i m a l   r o u t e s   f r o m   s t a r t   t o   g o a l .   T h e   o p t i m a l i t y   i s   u s u a l l y   m e a s u r e d   i n   t e r m s   o f t r a v e l e d   d i s t a n c e s   [ 1 ] .   O t h e r   m e a s u r e s   a r e   a l s o   u s e d ,   e . g .   c o n f i d e n c e   v a l u e   [ 2 ] .   F o r p l a n e t a r y   r o v e r s   t h e   e f f i c i e n c y   o f   p a t h   i s   o f t e n   e x p r e s s e d   i n   t e r m s   o f   s l o p e   o r r o u g h n e s s   o f   t h e   s u r f a c e   [ 3 ,   4 ] .   R o b o t   p a t h   p l a n n i n g   i s   a   N P   p r o b l e m [ 5 ] ,   t r a d i t i o n a l o p t i m i z a t i o n   m e t h o d s   a r e   n o t   v e r y   e f f e c t i v e   t o   i t , w h i c h   a r e   e a s y   t o   p l u n g e   i n t o   l o c a l   m i n i m u m .   A   l o t   o f   a l g o r i t h m s   h a v e   b e e n   p r o p o s e d   t o   s o l v e   N P   p r o b l e m .   S o m e   o f   t h e m   ( b a s e d   o n   d y n a m i c   p r o g r a m m i n g   o r   b r a n c h   a n d   b o u n d   m e t h o d s )   p r o v i d e   t h e   g l o b a l   o p t i m u m   s o l u t i o n .   O t h e r   a l g o r i t h m s   a r e   h e u r i s t i c   o n e s ,   w h i c h   a r e   m u c h   f a s t e r ,   b u t   t h e y   d o   n o t   g u a r a n t e e   t h e   o p t i m a l   s o l u t i o n s . T h e   m o s t   p o p u l a r   e v o l u t i o n a r y   Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   1 0 ,   N o .   4 ,     D e c e m b e r   2 0 1 2   :     6 2 9 6 3 6   6 3 0 m o d e l   u s e d   i n   t h e   c u r r e n t   r e s e a r c h   i s   G e n e t i c   A l g o r i t h m s   ( G A ) ,   o r i g i n a l l y   d e v e l o p e d   b y   J o h n   H o l l a n d [ 6 ] .   T h e   G A   r e p r o d u c t i o n   o p e r a t o r s ,   s u c h   a s   r e c o m b i n a t i o n   a n d   m u t a t i o n ,   a r e   c o n s i d e r e d   a n a l o g o u s   t o   t h e   b i o l o g i c a l   p r o c e s s   o f   m u t a t i o n   a n d   c r o s s o v e r   r e s p e c t i v e l y   i n   p o p u l a t i o n   g e n e t i c s .   T h e   r e c o m b i n a t i o n   o p e r a t o r   i s   t r a d i t i o n a l l y   u s e d   a s   t h e   p r i m a r y   s e a r c h   o p e r a t o r   i n   G A   w h i l e   t h e   m u t a t i o n   o p e r a t o r   i s   c o n s i d e r e d   t o   b e   a   b a c k g r o u n d   o p e r a t o r ,   w h i c h   i s   a p p l i e d   w i t h   a   s m a l l   p r o b a b i l i t y .   T r a d i t i o n a l l y ,   G A   u s e s   a   b i n a r y   s t r i n g   r e p r e s e n t a t i o n   o f   c h r o m o s o m e s   w i t h   c o n c e n t r a t i o n   o n   t h e   n o t i o n   o f   ' s c h e m a t a ' .   A   s c h e m a   i s   a   t e m p l a t e   t h a t   a l l o w s   e x p l o r i n g   t h e   s i m i l a r i t y   a m o n g   c h r o m o s o m e s .   G e n e t i c   A l g o r i t h m s   m o d e l   e v o l u t i o n   a s   a   s e a r c h   f o r   s t r u c t u r e s   o r   b u i l d i n g   b l o c k s   t h a t   p e r f o r m   w e l l   i n   a   g i v e n   e n v i r o n m e n t .   T h e r e f o r e ,   t h e   r e c o m b i n a t i o n   a n d   m u t a t i o n   o p e r a t o r s   f o c u s   o n   a n   i n d i v i d u a l ' s   s t r u c t u r e ,   n o t   t h e   s t r u c t u r e ' s   i n t e r p r e t a t i o n .   T h e   r e s u l t s   o f   a p p l y i n g   r e p r o d u c t i o n   o p e r a t i o n   i n   G A   g e n e r a t e   s o l u t i o n s   t h a t   s h a r e   s t r u c t u r a l   s i m i l a r i t i e s   w i t h   t h e i r   p a r e n t s   b u t   m a y   h a v e   s i g n i f i c a n t l y   d i f f e r e n t   i n t e r p r e t a t i o n s .   H o w e v e r ,   m a n y   r e c e n t   a p p l i c a t i o n s   o f   G A   h a v e   u s e d   o t h e r   r e p r e s e n t a t i o n   s u c h   a s   g r a p h s ,   L i s p   e x p r e s s i o n s ,   o r d e r e d   l i s t ,   a n d   r e d - v a l u e d   v e c t o r s .     t = 0 ;   i n i t i a l i z e   P ( t )   e v a l u a t e   s r r u c t u r e s   i n   P ( t )   r e p e a t   t =   t + 1   s e l e c t -   r e p r o d u c t i o n   C ( t ) f r o m :   P ( t - 1 )   c o m b i n e   a n d   m u t a t e   s t r u c t u r e s   i n   C ( t ) f o r m i n g   C ' ( t ) ;   e v a l u a t e   s t r u c t u r e s   i n   C ' ( t )   s e l e c t - r e p l a c e   P ( t )   f r o m   C   ' ( t )   a n d   P ( t +   1 ) ;   U n t i l   (   t e r m i n a t i o n   c o n d i t i o n   s a t i s f i e d   ) .     T h e   a b o v e   c o d e   g i v e s   t h e   b a s i c   a l g o r i t h m i c   s t e p s   f o r   G A .   A f t e r   t h e   i n i t i a l   p o p u l a t i o n   o f   i n d i v i d u a l s   i s   g e n e r a t e d   ( u s u a l l y   r a n d o m l y )   a n d   i n d i v i d u a l s '   s t r u c t u r e s   a r e   e v a l u a t e d ,   t h e   l o o p   i s   e n t e r e d .   T h e n   a   s e l e c t i o n   b u f f e r   C ( t )   i s   c r e a t e d   t o   a c c o m m o d a t e   t h e   s e l e c t e d   c o p i e s   f r o m   P ( t - l ) ,   " s e l e c t - r e p r o d u c t i o n " .   I n   t h e   H o l l a n d   o r i g i n a l   G A ,   i n d i v i d u a l s   a r e   s e l e c t e d   p r o b a b i l i s t i c a l l y   b y   a s s i g n i n g   e a c h   i n d i v i d u a l   a   p r o b a b i l i t y   p r o p o r t i o n a l   t o   i t s   s t r u c t u r a l   f i t n e s s .   T h u s ,   b e t t e r   i n d i v i d u a l s   a r e   g i v e n   m o r e   o p p o r t u n i t y   t o   p r o d u c e   o f f s p r i n g .   N e x t   t h e   v a r i a t i o n   o p e r a t o r s   ( m u t a t i o n   a n d   c r o s s o v e r )   a r e   a p p l i e d   t o   t h e   i n d i v i d u a l s   i n   C ( t )   b u f f e r   p r o d u c i n g   o f f s p r i n g   C ( t ) .   A f t e r   e v a l u a t i n g   t h e   s t r u c t u r a l   f i t n e s s   o f   C ( t ) ,   t h e   s e l e c t i o n   m e t h o d   i s   a p p l i e d   t o   s e l e c t   r e p l a c e m e n t   f o r   P ( t )   f r o m   C ' ( t )   a n d   P ( t - 1 ) .   I n   g e n e r a l ,   g e n e t i c   a l g o r i t h m s   a r e   u s u a l l y   u s e d   t o   s o l v e   p r o b l e m s   w i t h l i t t l e   o r   n o   d o m a i n   k n o w l e d g e ,   N P - c o m p l e t e   p r o b l e m s ,   a n d   p r o b l e m s   f o r   w h i c h   n e a r o p t i m u m   s o l u t i o n   i s   s u f f i c i e n t .   T h e   G A   m e t h o d s   c a n   b e   a p p l i e d   o n l y   i f   t h e r e   e x i s t   a r e a s o n a b l e   t i m e   a n d   s p a c e   f o r   e v o l u t i o n   t o   t a k e   p l a c e .       2 .   I m p r o v e d   G e n e t i c   A l g o r i t h m   I n   o u r   a l g o r i t h m ,   t h e   c o d e   r e p r e s e n t a t i o n   w e   u s e   t h e   r e a l   c o d i n g ,   t h e   r e a l   c o d i n g   m e t h o d   h a s   a d v a n t a g e s   c o m p a r e d   w i t h   t h e   b i n a r y   c o d i n g   i n   t h e   f u n c t i o n   o p t i m i z a t i o n   p r o b l e m s ,   b e c a u s e   t h e   r e a l c o d i n g   c a n   s o l v e   t h e   " H a m m i n g   c l i f f " p r o b l e m   w h i c h   t h e   b i n a r y   c o d i n g   h a s   n o   i d e a   t o   s o l v e   i t ,   a n d   t h e n   t h e   e n c o d i n g ,   t h e   d e c o d i n g a n d   t h e   c a l c u l a t i o n   o f   t h e   f i t n e s s   f u n c t i o n   i s   m o r e   c o n v e n i e n t   w h e n   w e   u s e   t h e   r e a l c o d i n g .     2 . 1   I n i t i a l i z e   P o p u l a t i o n   T h e   t r a d i t i o n a l   m e t h o d   o f   g e n e t i c   a l g o r i t h m   i s   r a n d o m l y   i n i t i a l i z e d   p o p u l a t i o n ,   t h a t   i s ,   g e n e r a t e   a   s e r i e s   o f   r a n d o m   n u m b e r s   i n   t h e   s o l u t i o n   s p a c e   o f   t h e   q u e s t i o n .   D e s i g n   t h e   n e w   a l g o r i t h m ,   w e   u s i n g   t h e   o r t h o g o n a l   i n i t i a l i z a t i o n [ 7 ]   i n   t h e   i n i t i a l i z a t i o n   p h a s e .   F o r   t h e   g e n e r a l   c o n d i t i o n ,   b e f o r e   s e e k i n g   o u t   t h e   o p t i m a l   s o l u t i o n   t h e   l o c a t i o n   o f   t h e   g l o b a l   o p t i m a l   s o l u t i o n i s   i m p o s s i b l e   t o   k n o w ,   f o r   s o m e   h i g h - d i m e n s i o n a l   a n d   m u l t i - m o d e   f u n c t i o n s   t o   o p t i m i z e ,   t h e   f u n c t i o n   i t s e l f   h a s   a   l o t   o f   p o l e s ,   a n d   t h e   g l o b a l   o p t i m u m   l o c a t i o n   o f   t h e   f u n c t i o n   i s   u n k n o w n .   I f   t h e   i n i t i a l   p o p u l a t i o n   o f   c h r o m o s o m e s   c a n   b e   e v e n l y   d i s t r i b u t e d   i n   t h e   f e a s i b l e   s o l u t i o n   s p a c e ,   t h e   a l g o r i t h m   c a n   e v e n l y   s e a r c h   i n   t h e   s o l u t i o n   s p a c e   f o r   t h e   g l o b a l   o p t i m u m .   O r t h o g o n a l   i n i t i a l i z a t i o n   i s   t o   u s e   t h e   o r t h o g o n a l   t a b l e   h a s   t h e   d i s p e r s i o n   a n d   u n i f o r m i t y   c o m p a r a b l e ;   t h e   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L K O M N I K A     I S S N :   1 6 9 3 - 6 9 3 0       A n   I m p r o v e d   R o b o t   P a t h   P l a n n i n g   A l g o r i t h m   ( X u e s o n g   Y a n )   6 3 1   i n d i v i d u a l   w i l l   b e   i n i t i a l i z e d   u n i f o r m l y   d i s p e r s e d   i n t o   t h e   s e a r c h   s p a c e ,   s o   t h e   o r t h o g o n a l   d e s i g n   m e t h o d   c a n   b e   u s e d   t o   g e n e r a t e   u n i f o r m l y   d i s t r i b u t e d   i n i t i a l   p o p u l a t i o n .     2 . 2   I n t e r g e n e r a t i o n a l   E l i t e   M e c h a n i s m   G e n e t i c   a l g o r i t h m   i s   u s u a l l y   c o m p l e t e   t h e   s e l e c t i o n   o p e r a t i o n   b a s e d   o n   t h e   i n d i v i d u a l ' s   f i t n e s s   v a l u e ,   i n   t h e   m e c h a n i s m   o f   i n t e r g e n e r a t i o n a l   e l i t e , t h e   p o p u l a t i o n   o f   t h e   f r o n t   g e n e r a t i o n   m i x e d   w i t h   t h e   n e w   p o p u l a t i o n   w h i c h   g e n e r a t e   t h r o u g h   c r o s s o v e r   a n d   m u t a t i o n   o p e r a t i o n s ,   i n   t h e   m i x e d   p o p u l a t i o n   s e l e c t   t h e   o p t i m u m   i n d i v i d u a l s   a c c o r d i n g   t o   a   c e r t a i n   p r o b a b i l i t y . T h e   s p e c i f i c   p r o c e d u r e   i s   a s   f o l l o w s :   S t e p   1   :   U s i n g   c r o s s o v e r   a n d   m u t a t i o n   o p e r a t i o n s   f o r   p o p u l a t i o n   P 1   w h i c h   s i z e   i s   N   t h e n   g e n e r a t i n g t h e   n e x t   g e n e r a t i o n   o f   s u b - p o p u l a t i o n s   P 2 ;   S t e p   2   :   T h e   c u r r e n t   p o p u l a t i o n   P 1   a n d   t h e   n e x t   g e n e r a t i o n   o f   s u b - p o p u l a t i o n s   P 2   m i x e d   t o g e t h e r   f o r m   a   t e m p o r a r y   p o p u l a t i o n ;   S t e p   3   :   T e m p o r a r y   p o p u l a t i o n   a c c o r d i n g   t o   f i t n e s s   v a l u e s   i n   d e s c e n d i n g   o r d e r ,   t o   r e t a i n   t h e   b e s t   N   i n d i v i d u a l s   t o   f o r m   n e w   p o p u l a t i o n s   P 1 .   T h e   c h a r a c t e r i s t i c   o f   t h i s   m e c h a n i s m   i s   m a i n l y   i n   t h e   f o l l o w i n g   a s p e c t s .   F i r s t   i s   r o b u s t ,   b e c a u s e   o f   u s i n g   t h i s   s e l e c t i o n   s t r a t e g y ,   e v e n   w h e n   t h e   c r o s s o v e r   a n d   m u t a t i o n   o p e r a t i o n s   t o   p r o d u c e   m o r e   i n f e r i o r   i n d i v i d u a l s ,   a s   t h e   r e s u l t s o f   t h e   m a j o r i t y   o f   i n d i v i d u a l   r e s i d u e s   o f   t h e   o r i g i n a l   p o p u l a t i o n ,   d o e s   n o t   c a u s e   l o w e r   t h e   f i t n e s s   v a l u e   o f   t h e   i n d i v i d u a l . T h e   s e c o n d   i s   i n   g e n e t i c   d i v e r s i t y   m a i n t a i n i n g ,   t h e   o p e r a t i o n   o f   l a r g e   p o p u l a t i o n s ,   y o u   c a n   b e t t e r   m a i n t a i n   t h e   g e n e t i c   d i v e r s i t y   o f   t h e   p o p u l a t i o n   e v o l u t i o n   p r o c e s s . T h i r d   i s   i n   t h e   s o r t i n g   m e t h o d ,   i t   i s   g o o d   t o   o v e r c o m e   p r o p o r t i o n a l   t o   a d a p t   t o   t h e   c a l c u l a t i o n   o f   s c a l e .     2 . 3   A d a p t i v e   L o c a l   S e a r c h   O p e r a t o r   L o c a l   s e a r c h   o p e r a t o r   h a s   a   s t r o n g   l o c a l   s e a r c h   a b i l i t y ,   a n d   t h e n   c a n   s o l v e   t h e   s h o r t c o m i n g s   o f   g e n e t i c   a l g o r i t h m   h a s   t h e   w e a k   a b i l i t y   f o r   t h e   l o c a l   s e a r c h .   A n d   t h e   p o p u l a t i o n   a c c o r d i n g   t o   t h e   c u r r e n t   s t a t e   o f   a d a p t i v e   e v o l u t i o n   o f   t h e   l o c a l   s e a r c h   s p a c e   a d a p t i v e   l o c a l   s e a r c h   o p e r a t o r   w i l l   u n d o u b t e d l y   g r e a t l y   e n h a n c e   t h e   a b i l i t y   o f   l o c a l   s e a r c h .   I n   t h e   i n i t i a l   s t a g e   o f   t h e   e v o l u t i o n ,   t h e   c u r r e n t   o p t i m a l   s o l u t i o n   f r o m   t h e   g l o b a l   o p t i m u m   r e g i o n   i s   s t i l l   r e l a t i v e l y   f a r   a w a y ,   t h i s   t i m e   t h e   a d a p t i v e   l o c a l   s e a r c h   o p e r a t o r   t o   r e q u i r e   s e a r c h   a   l a r g e   n e i g h b o r h o o d     s p a c e   t o   f i n d   m o r e   o p t i m a l   s o l u t i o n ,   i t   c a n   m a i n t a i n   t h e   p o p u l a t i o n   d i v e r s i t y .   W h e n   t h e   p o p u l a t i o n   h a s   e v o l v e d   t o   t h e   r e g i o n   c o n t a i n i n g   t h e   g l o b a l   o p t i m u m ,   t h e   a d a p t i v e   l o c a l   s e a r c h   o p e r a t o r   t o   r e q u i r e   a   r e l a t i v e l y   s m a l l   a r e a   t o   s e a r c h   i n   o r d e r   t o   i m p r o v e   t h e   a c c u r a c y   o f   t h e   g l o b a l   o p t i m a l   s o l u t i o n .   I n   o u r   a l g o r i t h m ,   t h e   a d a p t i v e   l o c a l   s e a r c h   o p e r a t o r   i s   t h e   a d a p t i v e   o r t h o g o n a l   l o c a l   s e a r c h   o p e r a t o r .   A d a p t i v e   o r t h o g o n a l   l o c a l   s e a r c h   o p e r a t o r   i s   a i m e d   a t   t h e   n e i g h b o r h o o d   o f   a   p o i n t   t o   s e a r c h ,   s o   t h e   k e y   p o i n t   i s   t o   i d e n t i f y   a   p o i n t   a s   t h e   c e n t e r   o f   t h e   h y p e r c u b e ,   t h e   h y p e r c u b e   i n   t h e   o r t h o g o n a l   t e s t ,   e x p e c t   t o   b e   b e t t e r   s o l u t i o n .     2 . 4   F r a m e w o r k   o f   A l g o r i t h m   I n   t h i s   p a p e r ,   w e   d e s i g n   t h e   i m p r o v e d   g e n e t i c   a l g o r i t h m   w i t h   t h e   r e a l   e n c o d i n g ,   o r t h o g o n a l   i n i t i a l i z a t i o n ,   c o m b i n e d   w i t h   t h e   r o u l e t t e   s e l e c t i o n   a n d   t h e   a d a p t i v e   l o c a l   s e a r c h   o p e r a t o r ,   u s i n g   t h e   i n t e r g e n e r a t i o n a l   e l i t i s t   m e c h a n i s m . T h e   f r a m e w o r k   o f   t h e   a l g o r i t h m   a s   f o l l o w s :   S t e p   1   :     I n i t i a l i z e   a   p o p u l a t i o n   P   u s i n g   t h e   o r t h o g o n a l   i n i t i a l i z a t i o n   m e t h o d ,   t h e   s c a l e   i s   N ,   a n d   e v a l u a t e   t h e   i n d i v i d u a l s   i n   t h i s   p o p u l a t i o n ;   S t e p   2   :     U s i n g   t h e   r o u l e t t e   s e l e c t i o n   m e t h o d ,   s e l e c t   t w o   p a r e n t   i n d i v i d u a l s   f r o m   t h e   p o p u l a t i o n   P   r e s p e c t i v e l y   t h e n   u s i n g   t h e   c r o s s o v e r   o p e r a t i o n   t o   g e t   a n   o p t i m a l   i n d i v i d u a l ,   t h e n   u s i n g   t h e   i n t e r g e n e r a t i o n a l   e l i t i s t   m e c h a n i s m   f o r   t h i s   i n d i v i d u a l   g e n e r a t e   a   s u b - i n d i v i d u a l ,   a n d   b r i n g   t h i s   i n d i v i d u a l   i n t o   t h e   n e w   p o p u l a t i o n   p o o l   P ' ,   r e p e a t   t h e   s t e p 2   u n t i l   t h e   n e w   p o p u l a t i o n   p o o l   P ' s i z e   i s   N ;   S t e p   3   :     E v a l u a t e   t h e   n e w   p o p u l a t i o n   P ' ,   t h e n   c o m b i n e d   t h e   n e w   p o p u l a t i o n   P '   w i t h   t h e   p o p u l a t i o n s   P   a n d   f o r m   a   t e m p o r a r y   p o p u l a t i o n ;   S t e p   4   :     S o r t   t h e   t e m p o r a r y   p o p u l a t i o n   a c c o r d i n g   t o   t h e   f i t n e s s   v a l u e   o f   t h e   i n d i v i d u a l s   i n   d e s c e n d i n g   o r d e r ;   r e t a i n   t h e   b e s t   N   i n d i v i d u a l s   t o   f o r m   t h e   n e x t   g e n e r a t i o n   p o p u l a t i o n   P ;   S t e p   5   :     I f   n o t   s a t i s f y   t h e   t e r m i n a t i o n   c o n d i t i o n ,   s w i t c h   t o   s t e p 2 ,   o t h e r w i s e ,   e n d   o f   t h e   a l g o r i t h m .     Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   1 0 ,   N o .   4 ,     D e c e m b e r   2 0 1 2   :     6 2 9 6 3 6   6 3 2 2 . 5   E x p e r i m e n t   V e r i f y   I n   o r d e r   t o   v e r i f y t h e   i m p r o v e m e n t   o f   t h e   n e w   a l g o r i t h m ,   w e   u s e   b e n c h m a r k s   f u n c t i o n   t o   t e s t   t h e   a l g o r i t h m s   p e r f o r m a n c e   a n d   c o m p a r e   t h e   r e s u l t s   w i t h   t r a d i t i o n a l   g e n e t i c   a l g o r i t h m .   S p e c i f i c   d e t a i l s   o f   t h e   t e s t   f u n c t i o n   s e e   T a b l e   1 .   I n   t h e   t a b l e   1 ,   n   b e h a l f   o f   t h e   d i m e n s i o n   n u m b e r   o f   t h e   f u n c t i o n , S   b e h a l f   o f   t h e   r a n g e   o f   v a r i a b l e s ,   m i n f   b e h a l f   o f   t h e   m i n i m i z a t i o n   o f   t h e   f u n c t i o n .       T a b l e 1 .   T e s t   F u n c t i o n   T e s t   F u n c t i o n   n   S   m i n f   2 1 1 ( ) n i i f x x = =   3 0   ( - 1 0 0 , 1 0 0 )   0   = × = 5 1 2 6 ) ( i i x x f   3 0   ( - 5 . 1 2 ,   5 . 1 2 )   0   ( ) 1 , 0 ) ( 4 1 3 U x i x f i n i + × = =   3 0   ( - 1 . 2 8 , 1 . 2 8 )   0   2 4 1 1 1 0 0 1 ( ) ( 1 0 0 ) c o s ( ) 1 4 0 0 0 n n i i i i x f x x i = = - = - - + Õ   3 0   ( - 3 0 0 . 0 , 3 0 0 . 0 )   0   2 5 1 1 1 1 ( ) 2 0 e x p ( 0 . 2 ) e x p ( c o s ( 2 ) ) 2 0 n n i i i i f x x x e n n p = = = - × - × - × × + +   3 0   ( - 3 2 . 0 , 3 2 . 0 )   0   2 2 2 6 1 1 ( ) 1 0 0 ( ( ) ( 1 ) ) n i i i i f x x x x + = = - + -   3 0   ( - 2 . 0 4 8 , 2 . 0 4 8 )   0   7 1 ( ) s i n ( ) n i i i f x x x = = -   3 0   ( - 5 0 0 , 5 0 0 )   - 1 2 5 6 9 . 5     T a b l e   2 .   N e w   a l g o r i t h m   a n d   G A   e x p e r i m e n t   F u n c t i o n   A l g o r i t h m   B e s t   V a l u e   W o r s t   V a l u e   S t a n d a r d   d e v i a t i o n   ) ( 1 x f   G A   1 4 9 5 . 7 1   7 0 3 2 . 8 9   2 0 1 . 0 3 8   I m p r o v e d   G A   4 . 1 3 7 3 1 E - 2 9   1 . 0 8 8 2 E - 2 4   2 . 2 8 0 1 5 E - 2 6   ) ( 2 x f   G A   0   0   0   I m p r o v e d   G A   0   0   0   ) ( 3 x f   G A   0 . 0 0 1 7 7 0 9 4   0 . 0 0 8 3 3 9 6 3   0 . 0 0 0 2 1 0 0 5 5   I m p r o v e d   G A   0 . 0 0 1 9 3 5 6 5   0 . 0 1 0 3 5 9 5   0 . 0 0 0 2 5 9 9 0 3   4 ( ) f x   G A   7 2 . 5 0 6 9   1 2 3 . 9 5 4   1 . 5 2 2 8 9   I m p r o v e d   G A   2 . 1 8 5 5 9 E - 1 2   8 . 6 3 1 9 4 E - 2 5   0 . 0 0 1 7 7 5 1 2   5 ( ) f x   G A   - 3 . 1 9 7 4 4 E - 1 4   4 . 4 2 2 9   0 . 1 4 8 4 1 8   I m p r o v e d   G A   - 3 . 1 9 7 4 4 E - 1 4   1 . 5 0 2 2 9   0 . 0 7 4 9 5 0 9   6 ( ) f x   G A   1 . 8 4 8 8 9 E - 2 8   8 . 6 3 1 9 4 E - 2 5   1 . 8 3 9 9 1 E - 2 6   I m p r o v e d   G A   2 . 5 5 1 4 7 E - 2 8   1 . 2 0 4 0 1 E - 2 3   2 . 4 1 6 7 8 E - 2 5   7 ( ) f x   G A   - 5 0 3 8 . 6 2   - 3 2 3 3 . 1 3   5 4 . 0 1 2 3   I m p r o v e d   G A   - 9 5 3 5 . 1 9   - 8 2 0 3 . 5 6   4 5 . 1 6 6 1     T h e   t w o   a l g o r i t h m s   o f   t h e   s a m e   e x p e r i m e n t a l   p a r a m e t e r s   s e t .   E a c h   f u n c t i o n   i n   T a b l e   1   i s   r u n   5 0   t i m e s   w i t h   t h e   t w o   a l g o r i t h m s ,   t h e i r   e x p e r i m e n t a l   r e s u l t s   s u c h   a s   T a b l e   2 .   B y   a n a l y z i n g   t h e   e x p e r i m e n t a l   r e s u l t s   w e   k n o w ,   i n   s o l v i n g   f u n c t i o n   f 1 ,   f 4   a n d   f 7 ,   u s e   t h e   g e n e t i c   a l g o r i t h m   i s   e a s i l y   i n t o   l o c a l   o p t i m u m ,   b u t   u s e   t h e   n e w   a l g o r i t h m ,   c o n v e r g e n c e   s o o n ,   a n d   f i n d   a   b e t t e r   s o l u t i o n ,   t h e   a v e r a g e   f i t n e s s   a n d   t h e   b e s t   f i t n e s s   w a s   b o t h   s u p e r i o r   t o   g e n e t i c   a l g o r i t h m .   F o r   t h e   f u n c t i o n   f 2 ,   t h e   n e w   a l g o r i t h m   a n d   G A   a l l   c a n   f i n d   t h e   g l o b a l   o p t i m a l ,   t h e s e   t w o   a l g o r i t h m   f o r   t h i s   t e s t   f u n c t i o n   i s   v e r y   e f f e c t i v e .   F o r   f u n c t i o n   f 5 ,   t h e   t w o   a l g o r i t h m s   c a n   f i n d   t h e   b e s t   s o l u t i o n s   a r e   t h e   s a m e   ( s e e   T a b l e   2 ) ,   a n d   t h e   n e w   a l g o r i t h m   t o   g e t   t h e   b e s t   v a l u e   o f   t h e   a v e r a g e   i s   b e t t e r   t h a n   G A   a l g o r i t h m .     I n   s u m ,   w e   c a n   s e e   t h a t   i n   s o l v i n g   f u n c t i o n   f 1 ,   f 4 ,   f 5   a n d   f 7 ,   t h e   n e w   a l g o r i t h m   m o r e   e f f i c i e n t   t h a n   G A   a l g o r i t h m , i n   s o l v i n g   o t h e r   f u n c t i o n ,   t h e   p e r f o r m a n c e   a l m o s t   s a m e   o f   t h e   t w o   a l g o r i t h m s .   I n   s h o r t ,   t h i s   n e w   a l g o r i t h m   h a s   t h e   f o l l o w i n g   v a l u e :   b e t t e r   g l o b a l   s e a r c h   c a p a b i l i t y .       3 .   R o b o t   P a t h   P l a n n i n g   A l g o r i t h m   B a s e d   o n   I m p r o v e d   G A   W e   h a v e   c h o s e n   g e n e t i c   a l g o r i t h m s   t o   g e n e r a t e   r o b o t   p a t h   m a i n l y   f o r   t w o r e a s o n s :   f i r s t l y ,   t h e y   a r e   a   p o w e r f u l   t o o l   f o r   s e a r c h i n g   i n   h i g h   d i m e n s i o n a l   s p a c e s , l i k e   i n   t h i s   c a s e .   S e c o n d l y ,   t h e   m e t h o d   i m p o s e s   f e w   m a t h e m a t i c a l   c o n s t r a i n t s   i n t h e   s h a p e   o f   t h e   f u n c t i o n   t o   o p t i m i z e .   I n   t h i s   w a y ,   t h i s   m e t h o d   i s   a p p l i c a b l e   t o   t h e g e n e r a t i o n   o f   a   w i d e   r a n g e   o f   b e h a v i o r s   ( o b s t a c l e   a v o i d i n g ,   w a l l   f o l l o w i n g ,   e t c . ) .   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L K O M N I K A     I S S N :   1 6 9 3 - 6 9 3 0       A n   I m p r o v e d   R o b o t   P a t h   P l a n n i n g   A l g o r i t h m   ( X u e s o n g   Y a n )   6 3 3   3 . 1   R o b o t   P a t h   P l a n n i n g   P r o b l e m   R o b o t   p a t h   p l a n n i n g   c a n   g e n e r a l l y   b e   c o n s i d e r e d   a s   a   s e a r c h   i n   a   c o n f i g u r a t i o n   s p a c e   d e f i n e d   i n   w h a t   i s   k n o w n   a s   t h e   c o n f i g u r a t i o n   s p a c e   f o r m u l a t i o n   [ 8 - 1 0 ] :   L e t   A   b e   a   s i n g l e   r i g i d   o b j e c t ,   m o v i n g   i n   a   E u c l i d e a n   s p a c e   N W Â = ,   N   =   2   o r   3 .   L e t   O 1   ,   , O n   b e   f i x e d   r i g i d   o b j e c t s   d i s t r i b u t e d   i n   W .   T h e   O i   ´ s   a r e   c a l l e d   o b s t a c l e s .   I f   A   i s   d e s c r i b e d   a s   a   c o m p a c t   s u b s e t   o f   W ,   a n d   t h e   o b s t a c l e s   O 1   ,   , O n   a r e   c l o s e d   s u b s e t s   o f   W ,   a   c o n f i g u r a t i o n   o f   A   i s   a   s p e c i f i c a t i o n   o f   t h e   p o s i t i o n   o f   e v e r y   p o i n t   i n   A   w i t h   r e s p e c t   t o   F W   ,   w h e r e   F W   i s   a   C a r t e s i a n   c o o r d i n a t e   s y s t e m .   T h e   c o n f i g u r a t i o n   s p a c e   o f   A   i s   t h e   s p a c e   d e n o t e d   b y   C ,   w i t h   a l l   p o s s i b l e   c o n f i g u r a t i o n s   o f   A .   T h e   s u b s e t   o f   W   o c c u p i e d   b y   A   a t   c o n f i g u r a t i o n   q   i s   d e n o t e d   b y   A ( q )   .   A   p a t h   f r o m   a n   i n i t i a l   c o n f i g u r a t i o n   q i n i t   t o   a   g o a l   c o n f i g u r a t i o n   q g o a l   i s   a   c o n t i n u o u s   m a p   C ® ] 1 , 0 [ : t   w i t h   i n i t q = ) 0 ( t a n d   g o a l q = ) 1 ( t .   T h e   w o r k s p a c e   c o n t a i n s   a   f i n i t e   n u m b e r   o f   o b s t a c l e s   d e n o t e d   b y   O i   w i t h   i = 1 , , n   .   E a c h   o b s t a c l e   O i   ,   m a p s   i n   C   t o   a   r e g i o n   { } 0 ) ( ) ( ¹ Ç Î = i i O q A C q B C   w h i c h   i s   c a l l e d   C   o b s t a c l e   T h e   u n i o n   o f   a l l   t h e   C   o b s t a c l e   i s   t h e   C   o b s t a c l e   r e g i o n ,   ) ( 1 i n i O C U =   a n d   t h e   s e t   } = Ç Î = = = = 0 ( ) ( \ ) ( \ C 1 1 i n i i n i fr e e O U q A C q O C U c i s   c a l l e d   t h e   f r e e   s p a c e .   A   f r e e   c o l l i s i o n   p a t h   b e t w e e n   t w o   c o n f i g u r a t i o n s   i s   a n y   c o n t i n u o u s   p a t h f r e e ] 1 , 0 [ : C ® t .   T h e   c o n f i g u r a t i o n   s p a c e   i s   a   p o w e r f u l   c o n c e p t u a l   t o o l   b e c a u s e   i t   s e e m s   t o   b e   t h e   n a t u r a l   s p a c e   w h e r e   t h e   p a t h   p l a n n i n g   p r o b l e m   l i v e s .   T h i s   i s   m a i n l y   b e c a u s e   a n y   t r a n s f o r m a t i o n   o f   a   r i g i d   o r   a r t i c u l a t e d   b o d y   b e c o m e s   a   p o i n t   i n   t h e   c o n f i g u r a t i o n   s p a c e .   F r o m   m a t h e m a t i c a l   p o i n t   o f   v i e w [ 1 1 ] ,   r o b o t   p a t h   p l a n n i n g   p r o b l e m   c a n   b e   e x p r e s s e d   a s   a   f i n d   t h e   o p t i m a l   v a l u e   o f   t h e   g o a l   f u n c t i o n ,   t h e   g o a l   f u n c t i o n   i s   t h e   c o s t   o f   t h e   p a t h   p l a n n i n g ,   c o n s t r a i n t s   c o n d i t i o n   i s   t o   a v o i d   c o l l i s i o n   w i t h   t h e   o b s t a c l e s ,   s o   t h e   m a t h e m a t i c   m o d e l   o f   t h e   r o b o t   p a t h   p l a n n i n g   c a n   e x p r e s s i o n   i n   t h e   f o l l o w i n g   e q u a t i o n .     m i n ( ) . . ( ) 1 , 2 , n i i f X X R s t g X b i p Î £ = L   ( 1 )     w h e r e   t h e   ( ) f X i s   t h e   g o a l   f u n c t i o n ,   ( ) i g X i s   t h e   c o n s t r a i n t s   c o n d i t i o n   a n d   p   d e n o t e s   t h e   n u m b e r s   o f   t h e   c o n s t r a i n t s   i n e q u a t i o n .     3 . 2   P a t h   R e p r e s e n t a t i o n   I n   o u r   a l g o r i t h m ,   t o   f a c i l i t a t e   t h e   c o d i n g   o f   i n d i v i d u a l   a n d   g e n e t i c   o p e r a t i o n ,   t h e   h e a d   p o i n t   o f   t h e   o b s t a c l e s ,   t h e   s t a r t   p o i n t   a n d   t h e   g o a l   p o i n t   a r e   a l l   c a l l e d   h e a d   p o i n t ,   g i v e   t h e s e   h e a d   p o i n t s   t h e   N u m b e r ,   t h o u g h   a   p a t h   c a n   b e   d e n o t e d   a   h e a d   p o i n t s   s e q u e n c e ,   w h i c h   t h e   s t a r t   h e a d   p o i n t   i s   v 1 ,   a n d   t h e   g o a l   h e a d   p o i n t   i s   v k .   E a c h   i n d i v i d u a l   i n   t h e   p o p u l a t i o n   r e p r e s e n t s   a   p a t h   s t a r t i n g   f r o m   t h e   i n i t i a l p o i n t   a n d   t r y i n g   t o   r e a c h   t h e   f i n a l   p o i n t . I n   t h i s   a l g o r i t h m ,   w e   u s e   l i s t   d e n o t e   t h e   p a t h   c h r o m o s o m e   w h i c h   c a n   f a c i l i t a t e   t h e   i n s e r t   a n d   d e l e t e   o p e r a t i o n   i n   t h e   p r o c e s s   o f   t h e   p a t h   e v o l u t i o n .   A   s i n g l e   l i s t   d e n o t e   a   p a t h ,   e a c h   l i s t   h a s   a   h e a d   p o i n t ,   a l l   o f   t h e   h e a d   p o i n t   f o r m   t h e   h e a d   a r r a y .   S o ,   t h e   g e n e   o f   t h e   c h r o m o s o m e ( t h e   e l e m e n t   o f   t h e   l i s t )   d e n o t e s   t h e   p o i n t   o f   t h e   p a t h .   T h e   F i g u r e   1   i s   t h e   c h r o m o s o m e r e p r e s e n t a t i o n   o f   o u r   a l g o r i t h m .       F i g u r e   1 .   C h r o m o s o m e r e p r e s e n t a t i o n     W h e r e ,   i n   t h e   h e a d   p o i n t ,   E l e N u m   d e n o t e s   t h e   n u m b e r   o f   t h e   g e n e   i n   t h e   c h r o m o s o m e ,   I n t e r N u m   d e n o t e s   t h e   n u m b e r   o f   t h e   c r o s s   a b o u t   t h e   c h r o m o s o m e   a n d   t h e   o b s t a c l e s ,   L e n g t h   d e n o t e s   t h e   l e n g t h   o f   t h e   c h r o m o s o m e ;   w h e r e   i n   e a c h   g e n e ,   O b j N u m   d e n o t e s   t h e   s e r i a l   Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   1 0 ,   N o .   4 ,     D e c e m b e r   2 0 1 2   :     6 2 9 6 3 6   6 3 4 n u m b e r o f   t h e   o b s t a c l e ,   P n t N u m   d e n o t e s   t h e   n u m b e r   o f   t h e   g e n e   i n   t h e   o b s t a c l e   O b j N u m ,   V a l u e   d e n o t e s   t h e   l o c a t i o n   o f   t h e   g e n e   i n   t h e   h e a d   p o i n t   s e q u e n c e .     3 . 3   F i t n e s s   F u n c t i o n   F i n d   f i t n e s s   f u n c t i o n   i s   a n   i m p o r t a n t   p a r t   o f   g e n e t i c   a l g o r i t h m s . F o r   t h e   r o b o t   p a t h   p l a n n i n g   p r o b l e m , i f   t h e   f i t n e s s   f u n c t i o n o n l y   c o n s i d e r   t h e   l e n g t h   o f   t h e   i n d i v i d u a l   p a t h   i s   n o t   e n o u g h ,   t a k i n g   i n t o   a c c o u n t   t h e   s i t u a t i o n   o f   t h e   o b s t a c l e s   c r o s s   w i t h   i n d i v i d u a l   p a t h s .   F o r   t h i s   r e a s o n ,   i n   o u r   a l g o r i t h m   f i t n e s s   f u n c t i o n   m e a s u r e s   t h e   o p t i m a l i t y   o f   e a c h   p a t h   c o n s i d e r i n g   t w o   f a c t o r s : t h e   d i s t a n c e   b e t w e e n   t h e   f i n a l   r o b o t   p o s i t i o n   a n d   t h e   g o a l   p o i n t   a n d   t h e   c r o s s   s i t u a t i o n   w h i c h   t h e   i n d i v i d u a l   h a v e   n o   c r o s s   w i t h   t h e   o b s t a c l e s .   F i t n e s s   f u n c t i o n   e q u a t i o n   a s   s h o e n   i n     f o l l o w i n g   e q u a t i o n .     = - = + 1 2 1 1 ) , ( 1 ) ( d d i i i i v v d S f   ( 2 )   w h e r e   2 1 , d d v v   i s   t h e   l o c a t i o n   o f   t h e   i n i t i a l   p o i n t   s   a n d   t h e   g o a l   p o i n t   g   i n   t h e   c h r o m o s o m e   S i .     3 . 4 A l g o r i t h m   F r a m e w o r k   F o l l o w i n g   p r o v i d e s   a   m o r e   d e t a i l e d   d e s c r i p t i o n   o f   t h e   w h o l e   r o b o t   p a t h   p l a n n i n g a l g o r i t h m   b a s e   o n   i m p r o v e d   g e n e t i c   a l g o r i t h m .       R a n d o m   i n i t i a l i z a t i o n   o f   t h e   p o p u l a t i o n   P   i n i t i a l i ze ) ( t S ;   ) } ( , ) , ( ) , ( { ) ( 2 1 t S t S t S t S i L =   e v a l u a t e   ) ( t S ;   ) ) } ( ( , ) ) , ( ( ) ) , ( ( { ) ) ( ( 2 1 t S f t S f t S f t S f i L =   W h i l e   ( n o t   s a t i s f i e d   t e r m i n a t i o n   c o n d i t i o n )   d o   i = 0 ;   b e g i n       f o r   e a c h   i n d i v i d u a l   P S i Î   d o       b e g i n     i S S ¬ '   S e l e c t   ( r a n d o m l y )   a   N o d e   C   f r o m   ' S   r e p e a t   { b e g i n         i f ) ( ) ( p r a n d £             s e l e c t   t h e   n o d e   ' C f r o m   t h e   r e m a i n i n g   n o d e s   i n   ' S         e l s e           { S e l e c t   ( r a n d o m l y )   a n   i n d i v i d u a l   i n   P   a s s i g n   t o   ' C   t h e   n e x t   n o d e   t o   t h e   n o d e   C   i n   t h e   s e l e c t   i n d i v i d u a l           }         i f     ( t h e   n e x t   n o d e   o r   t h e   p r e v i o u s   n o d e   o f   n o d e   C   i n   ' S   i s   ' C )         e x i t   r e p e a t   l o o p         i n v e r t   t h e   g e n e   n o d e   f r o m   t h e   n e x t   n o d e   o f   C   t o   t h e   n o d e   ' C   i n   ' S   ' C C ¬   }   e n d   i f ) ) ( ) ' ( ( i S e v a l S e v a l £   ' S S i ¬       e n d         i = i + 1 ;             e n d   D O       P R I N T   ) ( , b e s t b e s t X f X ;   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L K O M N I K A     I S S N :   1 6 9 3 - 6 9 3 0       A n   I m p r o v e d   R o b o t   P a t h   P l a n n i n g   A l g o r i t h m   ( X u e s o n g   Y a n )   6 3 5   3 . 5   E x p e r i m e n t   R e s u l t   W e   s i m u l a t e d   t h e   r o b o t   p a t h   p l a n n i n g   a l g o r i t h m   w i t h   c o m p u t e r ,   a n d   c o m p a r e d   t h e   p l a n n e d   p a t h   w i t h   t h e   t r a d i t i o n   m e t h o d :   v i s i b i l i t y   g r a p h . F o r t h e   t w o   a l g o r i t h m s ,   w e   g e n e r a t e d   t h e   o b s t a c l e s   r a n d o m l y .   F i g u r e   2   i s t h e   v i s i b i l i t y   g r a p h   r e s u l t ,   l e f t   c o r n e r   i s   s t a r t   p o i n t   a n d   r i g h t c o r n e r   i s   i n t e n t i o n   p o i n t ,   t h e   o p t i m u m   p a t h   i s   s h o w n w i t h   g r e e n   l i n e . F i g u r e   3   i s   o u r   a l g o r i t h m   r e s u l t .   F r o m   t h e   r e s u l t   f i g u r e s ,   t h e   r e s u l t s   i n d i c a t e d   t h a t o u r   a l g o r i t h m   i s   e f f i c i e n c y   f o r   s o l v i n g   t h e   r o b o t   p a t h   p l a n n i n g   p r o b l e m s   a n d i t   c a n   f o u n d   t h e   r i g h t   a n d   o p t i m a l p a t h .   W e   a l s o   c o m p a r e d   t h e   c a l c u l a t i o n   t i m e   w i t h   t h e   t w o   m e t h o d ,   o u r   a l g o r i t h m   i s   f a s t e r   t h a n   t h e   v i s i b i l i t y   g r a p h   .       F i g u r e   2 .     T h e   v i s i b i l i t y   g r a p h   r e s u l t         F i g u r e   3 .     O u r   a l g o r i t h m   r e s u l t       4 .   C o n c l u s i o n   T h i s   p a p e r   i n t r o d u c e s   a   n e w   a l g o r i t h m   b a s e d   o n   t h e   t r a d i t i o n a l   g e n e t i c   a l g o r i t h m ,   f o r   t h e   t r a d i t i o n a l   G A   a l g o r i t h m   t h e   n e w   a l g o r i t h m   h a s   d o n e   s o m e   i m p r o v e m e n t s :   B y   i n t r o d u c i n g   g e n e t i c   s e l e c t i o n   s t r a t e g y ,   d e c r e a s e d   t h e   p o s s i b i l i t y   o f   b e i n g   t r a p p e d   i n t o   a   l o c a l   o p t i m u m .   C o m p a r e d   t h e   t r a d i t i o n a l   g e n e t i c   a l g o r i t h m ,   t h e   n e w   a l g o r i t h m   e n l a r g e s   t h e   s e a r c h i n g   s p a c e   a n d   t h e   c o m p l e x i t y   i s   n o t   h i g h .     B y   a n a l y z i n g   t h e   t e s t i n g   r e s u l t s   o f   n i n e   b e n c h m a r k s   f u n c t i o n s   o p t i m i z a t i o n ,   w e   r e a c h   t h e   c o n c l u s i o n :   i n   t h e   o p t i m i z a t i o n   p r e c i s i o n   a n d   t h e   o p t i m i z a t i o n   s p e e d ,   t h e   n e w   a l g o r i t h m   i s   e f f i c i e n c y   t h a n   t h e   t r a d i t i o n a l   g e n e t i c   a l g o r i t h m   a n d   t h e   n e w   a l g o r i t h m   i s   m o r e   e f f i c i e n t   t h a n   t r a d i t i o n a l   g e n e t i c   a l g o r i t h m   i n   c o p i n g   w i t h   t h e   f u n c t i o n   o p t i m i z a t i o n   p r o b l e m s . W e   a l s o   u s e   t h i s   p r o p o s e d   a l g o r i t h m   f o r   s o l v i n g   r o b o t   p a t h   p l a n n i n g   p r o b l e m   a n d   c o m p a r e d   t h e   e x p e r i m e n t   r e s u l t   w i t h   t r a d i t i o n a l   m e t h o d ,   t h e   e x p e r i m e n t   r e s u l t s   i n d i c a t e d   t h a t   t h e   n e w   a l g o r i t h m   i s   e f f i c i e n c y   f o r   s o l v i n g   t h e   r o b o t   p a t h   p l a n n i n g   p r o b l e m s   a n d   t h e   b e s t   p a t h   u s u a l l y   c a n   b e   f o u n d .   Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S S N :   1 6 9 3 - 6 9 3 0   T E L K O M N I K A     V o l .   1 0 ,   N o .   4 ,     D e c e m b e r   2 0 1 2   :     6 2 9 6 3 6   6 3 6 A c k n o w l e d g m e n t s   T h i s   p a p e r   i s   s u p p o r t e d   b y   t h e   P r o v i n c i a l   N a t u r a l   S c i e n c e   F o u n d a t i o n   o f   H u b e i   ( N o .   2 0 1 1 C D B 3 3 4 a n d   2 0 1 1 C D B 3 4 6 ) ,   s u p p o r t e d   b y   N a t i o n a l   C i v i l   A e r o s p a c e   P r e - r e s e a r c h   P r o j e c t   o f   C h i n a a n d t h e   F u n d a m e n t a l   R e s e a r c h   F o u n d s   f o r   N a t i o n a l     U n i v e r s i t y ,   C h i n a   U n i v e r s i t y   o f   G e o s c i e n c e s ( W u h a n ) .       R e f e r e n c e s   [ 1 ]     Y a h j a ,   S   Si n g h ,   A   St e n t z .   A n   Ef f i c i e n t   o n - l i n e   Pa t h   Pl a n n e r   f o r   O u t d o o r   M o b i l e   R o b o t s .   R o b o t i c s   a n d   Au t o n o m o u s   Sy s t e m s .   El s e v i e r   Sc i e n c e .   2 0 0 0 ;   3 2 :   1 2 9 - 1 4 3 .   [ 2 ]     U N e h m z o w ,   C O w e n .   R o b o t   N a v i g a t i o n   i n   t h e   R e a l   W o r l d :   E x p e r i m e n t s   w i t h   M a n c h e s t e r s   F o r t y   T w o   i n   U n m o d i f i e d   L a r g e   En v i r o n m e n t s . R o b o t i c s   a n d Au t o n o m o u s   S y s t e m s . El s e v i e r   S c i e n c e . 2 0 0 0 ;   3 3 :   2 2 3 - 2 4 2 .   [ 3 ]     H o w a r d ,   H   Se r a j i .   Vi s i o n - B a s e d   T e r r a i n   C h a r a c t e r i z a t i o n   a n d   T r a v e r s a b i l i t y As s e s s m e n t . J o u r n a l   o f   R o b o t i c   Sy s t e m s .   W i l e y p e r i o d i c a l s . 2 0 0 1 ;   1 8 ( 1 0 ) :   5 7 7 - 5 8 7 .   [ 4 ]     D BG e n n e r y .   T r a v e r s a b i l i t y   An a l y s i s   a n d   Pa t h   P l a n n i n g   f o r   Pl a n e t a r y   R o v e r s . Au t o n o m o u s   R o b o t s .   Kl u w e r ,   Ac a d e m i c   Pu b l i s h e r s . 1 9 9 9 ;   6 :   1 3 1 - 1 4 6 .   [ 5 ]     G   L i u ,   T   L i ,   Y   Pe n g ,   X   H o u .   T h e   a n t   a l g o r i t h m   f o r   s o l v i n g   r o b o t   p a t h   p l a n n i n g   p r o b l e m .   3 r d   I n t e r n a t i o n a l   C o n f   o n   I n f o r m a t i o n   T e c h n o l o g y   a n d   Ap p l i c a t i o n s .   I EEE  Pr e s s . 2 0 0 5 ;   2 :   2 5 - 2 7 .   [ 6 ]     J   H o l l a n d .   Ad a p t a t i o n   i n   n a t u r a l   a n d   a r t i f i c i a l   s y s t e m s .   U n i v e r s i t y   o f   M i c h i g a n   p r e s s . 1 9 7 5 .   [ 7 ]     L e u n g   Y i u - W i n g ,   W a n g   Y u p i n g .   An   o r t h o g o n a l   g e n e t i c   a l g o r i t h m   w i t h   q u a n t i z a t i o n   f o r   g l o b a l   n u m e r i c a l   o p t i m i z a t i o n .   I EEE  T r a n s a c t i o n s   o n   Ev o l u t i o n a r y   C o m p u t a t i o n .   2 0 0 1 ;   5 ( 1 ) :   4 1 - 5 3 .   [ 8 ]     L a t o m b e   J C .   R o b o t   M o t i o n   Pl a n n i n g .   Kl u w e r   Ac a d e m i c   Pu b l i s h e r s .   Bo s t o n . 1 9 9 1 .   [ 9 ]     M   Br a c h o   d e   R o d r í g u e z ,   J   Al i   M o r e n o .   H e u r i s t i c   Al g o r i t h m   f o r   R o b o t   Pa t h   Pl a n n i n g   Ba s e d   o n   R e a l   Sp a c e   R e n o r m a l i z a t i o n .   I n t e r n a t i o n a l   J o i n t   C o n f e r e n c e ,   7 t h   I b e r o - Am e r i c a n   C o n f e r e n c e   o n   AI :   Ad v a n c e s   i n   Ar t i f i c i a l   I n t e l l i g e n c e   t a b l e   o f   c o n t e n t s ,   L e c t u r e   N o t e s   i n   C o m p u t e r   Sc i e n c e ,   Sp r i n g e r - Ve r l a g   L o n d o n ,   U K . 2 0 0 0 :   3 7 9 3 8 8 .   [ 1 0 ]   Ba r r a q u a n d   J ,   L a n g l o i s   B , L a t o m b e   J C .   N u m e r i c a l   Po t e n t i a l   F i e l d T e c h n i q u e s   f o r   R o b o t   Pa t h   Pl a n n i n g .   I EEE  T r a n s a c t i o n s   o n   Sy s t e m ,   M a n   a n d   C y b e r n e t i c .   1 9 9 2 ;   2 2 ( 2 ) :   2 2 4 - 2 4 1 .   [ 1 1 ]   D u r b i n   R ,   W i l l s h a w   D .   A n   An a l o g u e   Ap p r o a c h   t o   t h e   T r a v e l i n g   Sa l e s m a n   Pr o b l e m   U s i n g   a n   El a s t i c   N e t Ap p r o a c h . N a t u r e .   1 9 8 7 ;   3 2 6 ( 6 1 1 4 ) :   6 8 9 - 6 9 1 .   [ 1 2 ]   X SY a n ,   L SKa n g   e t . a l . An   Ap p r o a c h   t o   D y n a m i c   T r a v e l i n g   Sa l e s m a n   Pr o b l e m . 3 r d I n t e r n a t i o n a l   C o n f e r e n c e   o n   M a c h i n e   L e a r n i n g   a n d   C y b e r n e t i c s . I EEE  Pr e s s ,   S h a n g h a i ,   2 0 0 4 ; 2 4 1 8 - 2 4 2 0 .   [ 1 3 ]   X SY a n , A M   Z h o u ,   L Ka n g   e t , a l . T SP  Pr o b l e m   Ba s e d   o n   D y n a m i c   En v i r o n m e n t .   5 t h W o r l d   C o n g r e s s   o n I n t e l l i g e n t   C o n t r o l   a n d   Au t o m a t i o n ,   I EEE  p r e s s ,   H a n g z h o u , C h i n a . 2 0 0 4 ; 2 2 7 1 - 2 2 7 4 .   [ 1 4 ]   M J .   R e n d a s , W T e t e n o i r e . D e f i n i t i o n   o f   e x p l o r a t o r y   t r a j e c t o r i e s   i n   r o b o t i c s u s i n g   g e n e t i c   a l g o r i t h m s . 1 0 t h I n t e r n a t i o n a l   C o n f e r e n c e   i n   I n d u s t r i a l   a n d En g i n e e r i n g   Ap p l i c a t i o n s   o f   Ar t i f i c i a l   I n t e l l i g e n c e   a n d   Ex p e r t   Sy s t e m s . 1 9 9 7 ;   2 1 1 - 2 1 6 .   [ 1 5 ]   J X i a o ,   Z   M i c h a l e w i c z ,   L   Z h a n g ,   K   T r o j a n o w s k i .   Ad a p t i v e   e v o l u t i o n a r y p l a n n e r / n a v i g a t o r   f o r   r o b o t s . I EEE  T r a n s .   o n   E v o l u t i o n a r y   C o m p u t a t i o n . 1 9 9 7 ;   1 ( 1 ) :   1 8 - 2 8 .   [ 1 6 ]   G e n g q i a n L i u ,   T i e j u n L i ,   Y u q i n g Pe n g ,   X i a n g d a n H o u .   T h e   An t   A l g o r i t h m   f o r   S o l v i n g   R o b o t   Pa t h   Pl a n n i n g   Pr o b l e m . 3 r d I n t e r n a t i o n a l   C o n f e r e n c e   o n   I n f o r m a t i o n   T e c h n o l o g y   a n d   Ap p l i c a t i o n s ,   I EEE  Pr e s s . 2 0 0 5 ;   2 :   2 5 - 2 7 .   [ 1 7 ]   X SY a n ,   H u i   L i   e t . a l . F a s t   E v o l u t i o n a r y   A l g o r i t h m   f o r   C o m b i n a t o r i a l   O p t i m i z a t i o n   Pr o b l e m s . 4 t h   I n t e r n a t i o n a l   C o n f e r e n c e   o n   M a c h i n e   L e a r n i n g   a n d   C y b e r n e t i c s . I EEE  Pr e s s . 2 0 0 5 ;   3 2 8 8 - 3 2 9 2 .   [ 1 8 ]   X SY a n ,   Q i n g   H u a   W u   e t . a l . N e w   O p t i m i z a i t o n   Al g o r i t h m   f o r   F u n c t i o n   O p t i m i z a t i o n . 3 r d   I n t e r n a t i o n a l   Sy m p o s i u m   o n   I n t e l l i g e n c e   C o m p u t a t i o n   Ap p l i c a t i o n s ,   L e c t u r e   N o t e s   i n   C o m p u t e r   Sc i e n c e . Sp r i n g e r   Pr e s s . 2 0 0 9 ; 1 4 4 - 1 5 0 .   [ 1 9 ]   X Y a n ,   Q H   W u .   F u n c t i o n   O p t i m i z a t i o n   Ba s e d   o n   C u l t u r a l   Al g o r i t h m s .   J o u r n a l   o f   C o m p u t e r   a n d   I n f o r m a t i o n   T e c h n o l o g y .   A c a d e m y   Pu b l i s h . 2 0 1 2 ;   2 :   1 5 2 - 1 5 8 .   [ 2 0 ]   X Y a n ,   Q H   W u ,   C   Z h a n g e t ,   a l . An   I m p r o v e d   G e n e t i c   Al g o r i t h m   a n d   I t s   Ap p l i c a t i o n . T EL KO M N I KA   I n d o n e s i a n   J o u r n a l   o f   El e c t r i c a l   En g i n e e r i n g .   2 0 1 2 ;   1 0 ( 5 ) :   1 0 8 1 - 1 0 8 6 .   [ 2 1 ]   Q H   W u ,   H M   L i u   e t ,   a l .   R e s e a r c h   o f   F u n c t i o n   O p t i m i z a t i o n   Al g o r i t h m .   T EL KO M N I KA  I n d o n e s i a n   J o u r n a l   o f   El e c t r i c a l   En g i n e e r i n g .   2 0 1 2 ;   1 0 ( 4 ) :   8 5 8 - 8 6 3 .     Evaluation Warning : The document was created with Spire.PDF for Python.