基于Delaunay三角剖分的TSP問題求解研究.pdf

1、大連海事大學碩士學位論文基于Delaunay三角剖分的TSP問題求解研究姓名：任保營申請學位級別：碩士專業(yè)：計算機科學與技術(shù)（計算機軟件與理論）指導(dǎo)教師：蔣波20100601英文摘要A S t u d y o f A p p r o a c h t oS o l v e t h e T S P B a s e d o n D e l a u n a yT r i a n g u l a t i o nA b s t r a c tT S

2、 P i s n o to n l ya t y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ，b u ta l s oa N P - h a r dp r o b l e m ，w h i c hi s e a s y - t o —d e s c r i b eb u td i f f i c u l tt o d e a lw i t

3、 h ．F o ral o n gt i m e ，p e o p l eh a v eb e e nl o o k i n gf o ra ne f f i c i e n t ，f a s ta p p r o x i m a t i o n a l g o r i t h mt os o l v ea L a r g e - s c a l ep r o b l e m a c c u r a t e l y i n ar e a

4、 s o n a b l et i m e ．S o f a r , a l o t o f e f f i c i e n t a n dp r a c t i c a la l g o r i t h m s h a v e b e e n d e s i g n e d a n d t h e a n t c o l o n y s y s t e m i s o n eo ft h e b e t t e rp e r f o

5、r m a n c e a n d t h e m o s t r e p r e s e n t a t i v ea l g o r i t h m ．T h i s a r t i c l ew i l lm a i n l y s t u d y t h e s o l u t i o no f T S P b a s e d o nD e l a u n a y t r i a n g u l a t i o n ．T os

6、o l v et h es h o r t c o m i n g so f t h ec l a s s i c a la l g o r i t h m s ，w h i c ha r es o l v i n g s l o wa n d l o wa c c u r a c y , t h i s p a p e rg i v i n ga s o l u t i o n ：m a d e u s e o f t h eg o

7、o d c h a r a c t e r i s t i c so f D e l a u n a yt r i a n g u l a t i o nt od e t e r m i n ec a n d i d a t e s e ts t r a t e g y , g i v e a l li m p r o v e da l g o r i t h m ，u s i n g t h eM A X - M I N a n t

8、c o l o n y s y s t e m t O a v o i df a l l i n g i n t o t h e l o c a l s e a r c h ，a n d u s e t h et e c h n o l o g i e s ：r e c o n s t r u c t i o nt h r o u g h t h eu s eo f 2 - o p t i o n sf o rs o l v i n g

9、p a t h ，i m p r o v i n gt h eu p d a t e m e t h o do f p h e r o m o n e a n d o p t i m i z i n g t h ep r e f e r e n c e s t o f u r t h e r i m p r o v et h ep e r f o r m a n c e o f t h ea l g o r i t h m ．T o v

10、 e n f y t h e a l g o r i t h mp e r f o r m a n c e ，t h i s p a p e r u s et h e T S P L I B e x p e r i m e n t a l d a t at oc o m p a r e a n da n a l y s e t h e r u n n i n g r e s u l t so f t h ei m p r o v e d

11、a l g o r i t h mp r o p o s e di nt h i sp a p e r , b a s i ca n t c o l o n ys y s t e m ，M A X - M I Na n tc o l o n ys y s t e m ，d y n a m i ca d a p t i v ea n tc o l o n ys y s t e m ．T h er e s u l t s s h o wt

12、h a t t h ep e r f o r m a n c eo ft h ei m p r o v e d a l g o r i t h mp r o p o s e di nt h i sp a p e r i s r e l a t i v eo p t i m u m ，f o rs o m e s p e c i f i cT S P , t h e a l g o r i t h mC a no b t a i na n

13、o p t i m a ls o l u t i o n ，b ya n i n s t a n c eo f T S P ’u s i n g t h em a t l a bs i m u l a t i o n t oV 謝匆t h ee f f e c t i v e n e s so f t h ei m p r o v e da l g o r i t h m ．K e y W o r d s ：T S P ；V o r o