基于遺傳算法的課程表問題研究.pdf

1、東北大學碩士學位論文基于遺傳算法的課程表問題研究姓名：熊焱申請學位級別：碩士專業(yè)：應用數(shù)學指導教師：張慶靈;李大衛(wèi)20030601查! ! 壟蘭翌主蘭堡墮圭 一———————壘坐! ! 堅R e s e a r c h o n L e c t u r eT i m e t a b l i n g P r o b l e m B a s e d o nG e n e t i cA l g o r i t h mA b s t r a c

2、tL e c t u r et i m e t a b l i n gp r o b l e m i so n e o f t h et i m e t a b l i n gp r o b l e m s ．I tp e r h a p s i so n eo ft h e g r e a t e s t p r o b l e m st o b e s o l v e d a t t h e b e g i n n i n go f

3、e a c h t e r m ．L e c t u r et i m e t a b l i n gp r o b l e mi st h ep r o b l e m o f a s s i g n i n gt i m e sa n d p l a c et om a n ys e p a r a t el e c t u r e s t u t o r i a l s e r e ．t o s a r i s f y s e v

4、 e r a l c o n s t r a i n t s c o n c e r n i n g c a p a c i t i e s a n dl o c a t i o n s o fa v a i l a b l e r o o m s ，f r e e —t i m e n e e d sa n do t h e r s u c h c o n s i d e r a t i o n f o rl e c t u r e

5、r s ，a n dr e l a t i o n s h i p sb e t w e e np a r t i c u l a rc o u r s e s ．A se d u c a t i o n a li n s t i t u t i o n sa r ec h a l l e n g e d t o g r o wi n n u m b e ra n dc o m p l e x i t yw i t ho f t e n

6、 n oc o r r e s p o n d i n gi n c r e a s ei nr e s o u r c e sd u et ou s u a lb u d g e tc o n s t r a i n t s ，t h e i ro p e r a t i o n sn e e dt ob es t r e a m l i n e dm o r ea n dm o r ee f f i c i e n c yw h i

7、 l em i n i m i z i n gr e s o u r c e su s a g e ．O v e rt h el a s t4 0y e a r s ．m a n ya p p r o a c h e sa n dm o d e l sh a v eb e e n p r o p o s e df o rd e a l i n gw i t hav a r i e t yo f t h et i m e t a b l

8、i n gp r o b l e m s ，s u c ha si n t e g e rp r o g r a m m i n g ，g r a p hc o l o r i n g ，h e u r i s t i c ss e a r c h m e t h o d s a n d e v o l u t i o n a r y a l g o r i t h m s ．G e n e t i ca l g o r i t h m

9、 i s ar a n d o mo p t i m i z a t i o na n ds e a r c ht e c h n i q u e ．I th a sb e e na p p l i e d t oa v a r i e t yo f c o m p l e x p r o b l e m s ．L e c t u r et i m e t a b l i n gp r o b l e m i sc o u l d b

10、es o l v e d b y g e n e t i ca l g o r i t h m q u i t es u c c e s s f u l l y ．I nt h i s p a p e r , ab r i e fi n t r o d u c t i o nt o s o m ea p p r o a c h e s t o L e c t u r et i m e t a b l i n gp r o b l e m

11、 i s g i v e n ．T h e n ，s u r v e ya b o u t g e n e t i ca l g o r i t h m O D t h eb a s eo f m a t h e m a t i c s ，g e n e t i co p e r a t o r sa n d r e l e v a n ta n a l y s i si st h o r o u g h l yp r e s e n

12、t e d ．T h i r d ，w ep r o p o s e am o d e l a c c o r d i n g t ot h ec h a r a c t e r i s t i c so f U n i v e r s i t yt i m e t a b l i n g p r o b l e m a n d s o l v e db y g e n e t i c a l g o r i t h m ．F o r

13、i m p r o v i n g t h e s o l u t i o n q u a l i t y a n d i n c r e a s i n g t h ec o m p u t a t i o n a l e f f i c i e n c y ，t h e b e s t t i m e s l o t - f i n d i n g a l g o r i t h m i s p r o p o s e d a n

14、dc o m b i n e dw i t hg e n e t i ca l g o r i t h m ．T w ok i n d so f c o d e sa n da n e w k i n do f c r o s s o v e ra r eg i v e ni nt h i sp a p e r ．F i n a l l y ，t h ee x p e r i m e n t sv e r i f yt h a tt h

15、 i sm e t h o d i su s e f u lt os o l v e t h eu n i v e r s i t yt i m e t a b l i n g p r o b l e m ．K e y W o r d s ：t i m e t a b l i n gp r o b l e m ，l e c t u r et i m e t a b l i n gp r o b l e m ，g e n e t i ca