早稲田大学大学院情報生産システム研究科
博 博 博
博 士士士士 論論論論 文文 概文文 概概概 要要要要
論 論論
論 文 文文 文 題題 題題 目目目目
S t u d S t u d S t u d
S t u d y y y y o n G e n e t i c N e t w o r k o n G e n e t i c N e t w o r k o n G e n e t i c N e t w o r k o n G e n e t i c N e t w o r k P r o g r a m m i n g
P r o g r a m m i n g P r o g r a m m i n g
P r o g r a m m i n g ---- b a s e d C o n t r o l l e r s o f b a s e d C o n t r o l l e r s o f b a s e d C o n t r o l l e r s o f b a s e d C o n t r o l l e r s o f E l e v a t o r G r o u p S y s t e m s
E l e v a t o r G r o u p S y s t e m s E l e v a t o r G r o u p S y s t e m s E l e v a t o r G r o u p S y s t e m s
申 請 者
ZHOU, Jin
情報生産システム工学専攻 進化型計算システム研究
２ ０ ０ ８ 年 １ ２ 月
2
A r t i f i c i a l I n t e l l i g e n c e ( A I ) h a s b e e n p r o p o s e d i n t h e m i d d l e o f t h e 2 0 t h c e n t u r y, a t t e m p t i n g t o c r e a t e m a c h i n e s w i t h “ i n t e l l i g e n c e ” s u c h a s r e a s o n i n g , k n o w l e d g e , p l a n n i n g , l e a r n i n g , c o m m u n i c a t i o n , p e r c e p t i o n a n d t h e a b i l i t y t o m o v e a n d m a n i p u l a t e t h e o b j e c t s t h a t h u m a n b e i n g s h a v e a c q u i r e d d u r i n g t h e i r l i f e . Wi t h t h e r a p i d d e v e l o p m e n t o f c o m p u t e r s i n t h e p a s t s e v e r a l d e c a d e s , A I a c h i e v e d i t s g r e a t e s t s u c c e s s e s i n t h e 1 9 9 0 s a n d e a r l y 2 1 s t c e n t u r y t h r o u g h o u t a w i d e r a n g e o f f i e l d s i n c l u d i n g m e d i c a l d i a g n o s i s , s t o c k t r a d i n g , r o b o t c o n t r o l , l a w, s c i e n t i f i c d i s c o v e r y, e t c . S o f a r, m a n y a p p r o a c h e s i n t h e f i e l d o f A I , s u c h a s e v o l u t i o n a r y c o m p u t a t i o n , N e u r a l N e t w o r k s ( N N s ) a n d F u z z y L o g i c s ( F L ) , h a v e b e e n p r o p o s e d a n d s t u d i e d c o l l e c t i v e l y b y t h e e m e r g i n g d i s c i p l i n e o f c o m p u t a t i o n a l i n t e l l i g e n c e .
A m o n g t h e m , t h e r e i s e v o l u t i o n a r y c o m p u t a t i o n w h i c h m a i n l y c o m p r i s e s G e n e t i c A l g o r i t h m s ( G A ) , E v o l u t i o n a r y P r o g r a m m i n g ( E P ) , E v o l u t i o n S t r a t e g y ( E S ) , G e n e t i c P r o g r a m m i n g ( G P ) a n d l e a r n i n g c l a s s i f i e r s y s t e m s . T h e m e c h a n i s m s o f e v o l u t i o n a r y c o m p u t a t i o n w e r e i n s p i r e d b y b i o l o g i c a l e v o l u t i o n s u c h a s r e p r o d u c t i o n , m u t a t i o n , r e c o m b i n a t i o n , n a t u r a l s e l e c t i o n a n d s u r v i v a l o f t h e f i t t e s t . I n t h i s a p p r o a c h , t h e b e s t s o l u t i o n f o r t h e p r o b l e m i s s e l e c t e d a f t e r t h e i t e r a t i v e p r o g r e s s ( s o - c a l l e d e v o l u t i o n a r y p r o g r e s s ) , w h e r e a l l c a n d i d a t e s o l u t i o n s c o m p e t e w i t h e a c h o t h e r g e n e r a t i o n b y g e n e r a t i o n . U p t o n o w, m a n y s t u d i e s h a v e b e e n r e p o r t e d f o r a p p l y i n g e v o l u t i o n a r y c o m p u t a t i o n t o o p t i m i z a t i o n p r o b l e m s i n s o m e c o m p l i c a t e d s y s t e m s . Wi t h i t s e f f i c i e n c y a n d e f f e c t i v e n e s s v e r i f i e d b y e x p e r i m e n t s , e v o l u t i o n a r y c o m p u t a t i o n h a s b e e n a d o p t e d i n m o r e a n d m o r e r e a l s y s t e m d e v e l o p m e n t s .
O n t h e o t h e r h a n d , t h e e l e v a t o r g r o u p s y s t e m h a s b e e n w i d e l y s t u d i e d a s a l a r g e - s c a l e s t o c h a s t i c d y n a m i c o p t i m i z a t i o n p r o b l e m s i n c e t h e a p p e a r a n c e o f t h e h i g h - r i s e b u i l d i n g s . U n l i k e s o m e o t h e r t r a n s p o r t a t i o n s y s t e m s l i k e t r a i n s y s t e m s w h i c h r u n o n a p r e - s c h e d u l e d t i m e t a b l e , t h e e l e v a t o r g r o u p s y s t e m s h o u l d m a k e d e c i s i o n s o n - l i n e b a s e d o n t h e s t o c h a s t i c a n d i n c o m p l e t e i n f o r m a t i o n o n t h e t r a f f i c s i t u a t i o n i n b u i l d i n g s . D u e t o i t s v a s t s t a t e s p a c e , s i g n i f i c a n t u n c e r t a i n t y a n d n u m e r o u s r e s o u r c e c o n s t r a i n t s , i t i s h a r d t o m a n a g e e l e v a t o r g r o u p s y s t e m s u s i n g c o n v e n t i o n a l c o n t r o l m e t h o d s . Wi t h t h e a d v e n t o f t h e b o o m i n g r e s e a r c h o n A I t e c h n o l o g i e s i n t h e l a t e 2 0 t h c e n t u r y, m a n y A I - b a s e d a p p r o a c h e s i n t h i s d o m a i n h a v e b e e n p r o p o s e d a n d , a s a r e s u l t , l o t s o f e l e v a t o r c o m p a n i e s h a v e r e l e a s e d t h e i r n e w p r o d u c t i o n s u s i n g t h e s e a p p r o a c h e s . T h e p r o g r e s s
3
i n t h e r e s e a r c h o f A I t e c h n o l o g i e s m a k e s i t p o s s i b l e a n d v a l u a b l e t o a p p l y t h e l a t e s t p r o p o s a l t o t h e f i e l d o f t h e e l e v a t o r g r o u p s y s t e m . N o w a d a y s t h e u t i l i z a t i o n o f A I a n d e x p e r t s y s t e m s i n t h e c o n t e x t o f t h e e l e v a t o r s y s t e m c o n t r o l i s c o n c e i v a b l y a n i n d i s p e n s a b l e t r e n d . T h e d e v e l o p m e n t o f t h e e l e v a t o r g r o u p s y s t e m s , i n t h e l a t e 2 0 t h c e n t u r y, b e n e f i t e d f r o m t h e a d v a n c e m e n t o f A I t e c h n o l o g i e s , a n d m a n y A I - b a s e d e l e v a t o r g r o u p s y s t e m s h a v e b e e n p r o p o s e d . Ty p i c a l l y, G e n e t i c A l g o r i t h m s ( G A ) , E v o l u t i o n a r y S t r a t e g y ( E S ) , F u z z y L o g i c ( F L ) a n d N e u r a l N e t w o r k s ( N N s ) h a v e b e e n e m p l o y e d .
A s t h e e a r l y s t u d y o f t h i s d i s s e r t a t i o n , G N P w i t h R L i s f i r s t l y p r o p o s e d t o a p p l y t o t h e e l e v a t o r g r o u p s y s t e m w i t h s i n g l e d e c k i n e a c h s h a f t c a l l e d S i n g l e - D e c k E l e v a t o r S y s t e m s ( S D E S ) f o r b e t t e r p e r f o r m a n c e s . T h i s a p p r o a c h i s t h e n e x t e n d e d t o D o u b l e - D e c k E l e v a t o r S y s t e m ( D D E S ) c o n s i d e r i n g t h e s p e c i f i c f e a t u r e s o f t h e s y s t e m s . A l l s i m u l a t i o n s , i n t h e f o r m e r s t u d i e s , a r e b a s e d o n t h r e e t y p i c a l t r a f f i c p a t t e r n s o f o f f i c e b u i l d i n g s f o r s i m p l i c i t y. H o w e v e r, s i n c e t h e t r a f f i c p a t t e r n u s u a l l y k e e p s c h a n g i n g d u r i n g a d a y, a t r a f f i c f l o w - a d a p t i v e c o n t r o l l e r f o r D D E S u s i n g G N P i s p r o p o s e d a s a s e q u e n t i a l s t u d y. F i n a l l y, t h e a t t e n t i o n i s f o c u s e d o n t h e l i g h t t r a f f i c m o d e o f D D E S , w h e r e s o m e i d l e c a g e s e m e r g e , a n d a n i d l e c a g e a s s i g n m e n t a l g o r i t h m e m b e d d e d c o n t r o l l e r f o r D D E S i s p r o p o s e d .
I n c h a p t e r 2 , G N P w i t h R L i s i n t r o d u c e d i n t o E l e v a t o r G r o u p S u p e r v i s o r y C o n t r o l S y s t e m ( E G S C S ) f o r f a s t e r t r a i n i n g a n d b e t t e r p e r f o r m a n c e s d u r i n g t h e t a s k e x e c u t i o n p e r i o d . T h e r e a r e s i x s u b - n o d e s i n m a c r o - n o d e s , w i t h e a c h s u b - n o d e b e i n g d e f i n e d b y o n e o f s i x e v a l u a t i o n i t e m s . T h e r e i n f o r c e m e n t l e a r n i n g p r o c e s s i s b a s e d o n t h e ; - g r e e d y p o l i c y a n d a r e w a r d f u n c t i o n d e f i n e d b y t h e p a s s e n g e r w a i t i n g t i m e . To v e r i f y t h e e f f i c i e n c y o f t h e p r o p o s e d m e t h o d , f i t n e s s c u r v e s a n d t e s t r e s u l t s a r e c o m p a r e d w i t h t h e m e t h o d u s i n g o r i g i n a l G N P o n t h r e e t y p i c a l t r a f f i c p a t t e r n s ( i . e . , u p - p e a k t i m e , r e g u l a r a n d d o w n - p e a k t i m e ) . M o r e o v e r, t h e p e r f o r m a n c e s c o m p a r i s o n i s a l s o m a d e w i t h o t h e r t w o c o l l e c t i v e m e t h o d s ( AT, T H V ) u n d e r v a r y i n g t r a f f i c d e n s i t i e s f r o m 3 0 0 p e r s o n s p e r h o u r t o m o r e t h a n 2 1 0 0 .
I n c h a p t e r 3 , w i t h t h e a p p l i c a b i l i t y a n d a v a i l a b i l i t y o f a p p l y i n g G N P w i t h R L t o t h e s i n g l e - d e c k e l e v a t o r g r o u p s y s t e m s v e r i f i e d i n t h e l a s t c h a p t e r, G N P w i t h R L i s p r o p o s e d t o e n h a n c e t h e D o u b l e - D e c k E l e v a t o r S y s t e m ( D D E S ) u s i n g G N P. U n l i k e w h a t i s i m a g i n e d , t h e a l g o r i t h m o f u s i n g G N P
4
w i t h R L i n s i n g l e - d e c k e l e v a t o r g r o u p s y s t e m s c a n n o t b e d i r e c t l y a p p l i e d t o D D E S w h i c h i s m o r e c o m p l e x b e c a u s e o f i t s s p e c i f i c f e a t u r e s . A n e w a l g o r i t h m i s d e v e l o p e d f o r D D E S , a n d i t s e f f i c i e n c y i s v e r i f i e d b y c o m p a r i n g w i t h a h e u r i s t i c m e t h o d a n d T H V m e t h o d a s w e l l a s t h e o n e u s i n g G N P w i t h o u t R L . I n a d d i t i o n , t h e e f f e c t i v e n e s s o f t h e s p a c e s a v i n g u s i n g G N P w i t h R L i s c l a r i f i e d b a s e d o n t h e c o m p a r i s o n s w i t h s i n g l e - d e c k e l e v a t o r s y s t e m s .
I n c h a p t e r 4 , a D D E S c o n t r o l l e r u s i n g G N P i s p r o p o s e d t o a d a p t t o t h e v a r y i n g t r a f f i c f l o w s d u r i n g a w o r k d a y i n t h e b u i l d i n g s . B y c o n t r a s t w i t h t h e a p p r o a c h e s i n t h e f o r m e r s t u d i e s , a t r a f f i c i d e n t i f i c a t i o n p a r t i s i n t r o d u c e d i n t o t h e D D E S c o n t r o l l e r u s i n g G N P, w h e r e c a g e a s s i g n m e n t f u n c t i o n i s t o b e l o c a l i z e d b a s e d o n a t y p i c a l v a r y i n g t r a f f i c f l o w a f t e r t h e e v o l u t i o n a r y p r o c e s s e n d s . A n o t h e r a p p r o a c h o p t i m i z e d b y G A , w h e r e t h e c o n t r o l l e r i s s w i t c h e d b e t w e e n t h r e e G N P c o n t r o l l e r s o p t i m i z e d u n d e r t h r e e t r a f f i c p a t t e r n s r e s p e c t i v e l y, i s d e v e l o p e d t o c o m p e t e w i t h t h e p r o p o s e d m e t h o d . T h e b e t t e r p e r f o r m a n c e s o f t h e p r o p o s e d m e t h o d o v e r t h e s w i t c h i n g m e t h o d a n d o t h e r t w o m e t h o d s v e r i f y t h e e f f e c t i v e n e s s o f t h e p r o p o s a l . To a n a l y z e t h e c o n t r o l r u l e s o f t h e p r o p o s e d m e t h o d , t h e g e n e o f o n e o f t h e b e s t i n d i v i d u a l s i s s t u d i e d a s w e l l a s t h e j u d g m e n t r e s u l t b a s e d o n t h e i n d i v i d u a l i n t h e t e s t p r o c e s s .
I n c h a p t e r 5 , i n o r d e r t o i m p r o v e t h e p e r f o r m a n c e s o f D D E S i n t h e l i g h t t r a f f i c m o d e , t h e D D E S c o n t r o l l e r u s i n g G N P i n t h e p r e v i o u s c h a p t e r i s e x t e n d e d t o e m b e d t h e i d l e c a g e a s s i g n m e n t b a s e d o n t h e c a g e i d l i n g e v e n t a n d t i m e r. W h e n a c a g e b e c o m e s i d l e o r t h e t i m e r t r i g g e r s a t i m e - u p , a l l f l o o r s a r e e v a l u a t e d f o r t h e d e s t i n a t i o n o f t h e d i s p a t c h o f t h e i d l e c a g e . T h r e e i t e m s o f t h e e l e v a t o r g r o u p s y s t e m s a r e p r o p o s e d t o m a k e t h e e v a l u a t i o n . To v e r i f y t h e e f f i c i e n c y o f t h e p r o p o s a l , t h e p e r f o r m a n c e s a r e c o m p a r e d w i t h t h e m e t h o d w i t h o u t i d l e c a g e a s s i g n m e n t a s w e l l a s s e v e r a l o t h e r h e u r i s t i c m e t h o d s i n c l u d i n g t h e m e t h o d s w i t h f i x e d d i s p a t c h m e n t t o s o m e c e r t a i n f l o o r s . S o m e e x p e r i m e n t s a r e m a d e u n d e r v a r y i n g p a s s e n g e r d e n s i t i e s f r o m 2 0 0 p e r s o n s p e r h o u r t o 2 7 0 0 , a n d t h e s i m u l a t i o n r e s u l t s c o n f i r m e d t h a t t h e p r o p o s e d m e t h o d w o r k s e f f i c i e n t l y i n t h e l i g h t t r a f f i c m o d e i m p r o v i n g t h e p e r f o r m a n c e s v e r y l i t t l e a s s u p p o s e d i n a d v a n c e .
I n c h a p t e r 6 , s o m e c o n c l u s i o n s a b o u t t h e p r o p o s e d a l g o r i t h m s i n t h i s t h e s i s a r e d r a w n b a s e d o n t h e s i m u l a t i o n r e s u l t s .
