改進的混合遺傳算法求解影片遞送問題.pdf

1、內(nèi)蒙古大學(xué)碩士學(xué)位論文改進的混合遺傳算法求解影片遞送問題姓名：王敏申請學(xué)位級別：碩士專業(yè)：計算數(shù)學(xué)指導(dǎo)教師：行飛20050101I M P R O V E D H Y B R I D G E N E T I C A L G O R I T H MF O R T H E F I L M C O P Y D E L I V E R E R P R O B L E MA B S T R A C TT h e F i l mC o p y D

2、e l i v e r e rP r o b l e m f i nb r i e fF D P Ii S o n e o ft h et y p i c a lN P —H a r dp r o b l e m si nc o m b i n a t o r i a lp r o b l e m ．G e n e r a l l yi t i S h a r dt o e x a c t l y g e t ao p t i m u

3、ms o l u t i o n ，S Ot h ef a s ta n de f f e c t i v ea p p r o x i m a t ea l g o r i t h mh a v eb e e nn e e d e d t os o l v et h ep r o b l e mi nr e a s o n a b l et i m e ．T h eF i l mC o p yD e l i v e r e rP r

4、o b l e mi S t h ee x t e n s i o no ft h eT r a v e l i n gS a l e s m a nP r o b l e ma n dt h eM u l t i p l eT r a v e l i n gS a l e s m a nP r o b l e m ，a n di t i S s i g n i f i c a n c ei nt h e o r ya n dp r a

5、 c t i c e ．G e n e t i cA l g o r i t h mi S a r a n d o ms e a r c ha n do p t i m i z a t i o nm e t h o db a s e do nn a t u r a l s e l e c t i o n a n dg e n e t i cm e c h a n i s mo ft h el i v i n gb e i n g s ．

6、T h e yh a v eb e e nw i d e l ya p p l i e dt om a n y f i e l d s ．T h e p a p e r , a c c o r d i n g t o t h e c h a r a c t e r o f F D P , p u t s f o r w a r d s a G e n e t i cA l g o r i t h mo fu s i n gan e w

7、c r o s s o v e ro p e r a t o r ．A l li n d i v i d a l sa r ef e a s i b l et oe n h a n c et h e c o m p u t e s p e e d ．T h r o u g hc o m p a r e a n da n a l y s i s ，w eg e t as a t i s f i e d i m p r o v e dh y

8、 b r i dG e n e t i cA l g o r i t h m w i t h ( 肛+ ^ ) s e l e c t ，e d g ep r o b a b i l i t yr e c o m b i n ea n d2 - o p tl o c a ls e a r c h ．I tc a n q u i c k l yc o n v e r g et ot h eg l o b a lo p t i m u m

9、s o l u t i o n ．T l l ei m p r o v e da I g o r i t h ma c c e l e r a t e s c o n v e r g e n c er a t eg r e a t l y a n d a l s o i n c r e a s et h ea b i l i t yt of i g h tp r e m a t u r eb yi n t r o d u c i n g

10、g r a f t e dG e n e t i c A l g o r i t h m ．S i m u l a t i o nr e s u l t sb yc o m p u t e rs h o wt h a tt h e n e wa l g o r i t h mi S e 幣c i e n ta n da s c e n d a n t ，a n dt h a tt h en e w a l g o r i t h mD

11、o w e r f u l ys e a r c hf o rt h eo p t i m u m s o l u t i o no f F D P ．K E Y W O R D S ：g e n e t i c a l g o r i t h m ．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 ，t h e f i l m c o P Yd e l i v e r e rp r o