Luận văn:Giải bài toán tìm đường đi ngắn nhất bằng thuật toán song song meta-heuristic

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

120
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo luận văn - đề án 'luận văn:giải bài toán tìm đường đi ngắn nhất bằng thuật toán song song meta-heuristic', luận văn - báo cáo, thạc sĩ - tiến sĩ - cao học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Giải bài toán tìm đường đi ngắn nhất bằng thuật toán song song meta-heuristic

-1- -2- B GIÁO D C VÀ ĐÀO T O Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Đ I H C ĐÀ N NG LÊ NG C QUANG Ngư i hư ng d n khoa h c: PGS.TSKH. Tr n Qu c Chi n GI I BÀI TOÁN TÌM ĐƯ NG ĐI NG N NH T Ph n bi n 1: B NG THU T TOÁN SONG SONG PGS.TS. Võ Trung Hùng META-HEURISTIC Ph n bi n 2: TS. Hoàng Th Lan Giao Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 Lu n văn s ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p Th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 04 tháng 03 năm 2012. TÓM T T LU N VĂN TH C SĨ K THU T * Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng Đà N ng - Năm 2012 - Trung tâm H c li u, Đ i h c Đà N ng.
-3- -4- M Đ U 3. Đ i tư ng và ph m vi nghiên c u Đ i tư ng nghiên c u 1. Lý do ch n ñ tài - Nghiên c u các gi i thu t ki n Bài toán t i ưu t h p là d ng bài toán có ñ ph c t p tính - Mô hình tính toán song song Message Passing Interface toán cao thu c l p NP khó. S ra ñ i c a gi i thu t Meta-Heuristic - Thu t toán ki n song song ñã gi i quy t các bài toán v i hi u qu cao cho k t qu l i gi i g n Ph m vi nghiên c u t i ưu như h gi i thu t ki n (Ant Algorithm), gi i thu t luy n thép - T p trung nghiên c u thu t toán song song áp d ng vào gi i SA (Simulated Annealing), gi i thu t di truy n GA (Genetic thu t ki n. Algorithm). - Vi c th nghi m ñ i v i bài toán ngư i du l ch - Travelling V i ñ ph c t p tính toán cao c a các bài toán t i ưu t h p Salesman problem (TSP) ñư c s d ng là thư vi n chu n TSPLIB cũng như ñòi h i v m t th i gian, vi c gi i các bài toán này v i tính 4. Phương pháp nghiên c u ch t tu n t c a gi i thu t s g p ph i nh ng v n ñ v th i gian th c Phương pháp tài li u: hi n chương trình, t c ñ x lý, kh năng lưu tr c a b nh , x lý Nghiên c u lý thuy t v thu t toán ki n, các v n ñ song d li u v i quy mô l n... Kích thư c bài toán tăng lên và không gian song hóa. Trên cơ s lý thuy t nghiên c u ñư c s v n d ng k t qu tìm ki m càng l n yêu c u c n ph i song song hóa các gi i thu t ñ tìm ki m t i ưu c a thu t ki n song song vào bài toán ngư i du l ch. tăng t c ñ và hi u qu c a gi i thu t. Phương pháp th c nghi m M c ñích c a ñ tài là gi i quy t bài toán tìm ñư ng ñi ng n Xây d ng chương trình và ñánh giá k t qu th nghi m v i nh t b ng thu t toán ki n song song nh m phát huy s c m nh c a bài các mô hình song song. toán. Trên cơ s ñó s ñưa ra k t qu ñánh giá hi u qu c a thu t toán 5. Ý nghĩa khoa h c và th c ti n c a ñ tài ki n trên các mô hình song song. Nghiên c u và gi i thi u thu t toán ñàn ki n và thu t toán 2. M c ñích nghiên c u ñàn ki n song song trong vi c gi i bài toán tìm ñư ng ñi ng n nh t và Các m c tiêu c th g m: ng d ng thu t toán vào bài toán ngư i du l ch. - Nghiên c u v gi i thu t Meta-Heuristic ñ c bi t là h các 6. C u trúc lu n văn gi i thu t ki n N i dung chính c a lu n văn này ñư c chia thành ba chương - Nghiên c u v các v n ñ song song hóa và gi i thu t ñàn v i n i dung như sau: ki n song song. Chương 1 – Cơ s lý thuy t: N i dung chính là tìm hi u, - Áp d ng gi i thu t ki n song song vào bài toán tìm ñư ng nghiên c u lý thuy t liên quan ñ n v n ñ nghiên c u v lý thuy t ñ ñi ng n nh t. th , các v n ñ l p trình song song, thu t toán ñàn ki n .
-5- -6- Chương 2 – Thu t toán ki n song song: T thu t toán t i CHƯƠNG 1 ưu ñàn ki n tu n t th c hi n chuy n sang thu t toán t i ưu ñàn ki n CƠ S LÝ THUY T song song trên mô hình truy n thông ñi p. Chương 3 – Phân tích, xây d ng và cài ñ t chương trình: 1.1. CÁC KHÁI NI M CƠ B N V Đ TH Phân tích ch c năng và xây d ng chương trình ng d ng vào bài toán 1.1.1. Đ nh nghĩa ñ th ngư i du l ch ñ ng th i ti n hành ch y th nghi m, ñánh giá k t qu . 1.1.2. Tính liên thông c a ñ th 1.1.3. Đ th Euler và ñ th Hamilton Đ nh nghĩa 1.13. Chu trình (tương ng ñư ng ñi) ñơn ch a t t c các c nh (ho c cung) và các ñ nh c a ñ th (vô hư ng ho c có hư ng) G ñư c g i là chu trình (tương ng ñư ng ñi) Euler. M t ñ th liên thông (liên thông y u ñ i v i ñ th có hư ng) có ch a m t chu trình (tương ng ñư ng ñi) Euler ñư c g i là ñ th Euler (tương ng n a Euler). Đ nh nghĩa 1.14. Chu trình (tương ng ñư ng ñi) sơ c p ch a t t c các ñ nh c a ñ th (vô hư ng ho c có hư ng) G ñư c g i là chu trình (tương ng ñư ng ñi) Hamilton. M t ñ th có ch a m t chu trình (tương ng ñư ng ñi) Hamilton ñư c g i là ñ th Hamilton (tương ng n a Hamilton). 1.1.4. Bi u di n ñ th trên máy tính 1.1.4.1. Ma tr n k , ma tr n tr ng s 1.1.4.2. Danh sách c nh (cung) 1.1.4.3. Danh sách k 1.2. TÍNH TOÁN SONG SONG VÀ CÁC V N Đ SONG SONG HÓA 1.2.1. Mô hình máy tính song song M t h th ng máy tính song song là m t máy tính v i nhi u hơn m t b x lý cho phép x lý song song. D a vào s phân bi t k t n i gi a các b x lý (hay thành ph n x lý), gi a
-7- -8- b x lý và b nh mà có r t nhi u lo i ki n trúc máy tính song 1.3.1. Các khái ni m cơ b n song khác nhau. Nhưng theo nguyên t c phân lo i c a Flynn thì 1.3.2. Các ñ c tính cơ b n c a m t chương trình MPI có hai ki n trúc máy tính song song song thông d ng sau: 1.3.3. Trao ñ i thông tin ñi m – ñi m 1.2.1.1. Mô hình Đơn dòng l nh ña d li u – SIMD K thu t truy n thông cơ b n c a MPI là s chuy n giao d 1.2.1.2. Mô hình ña l nh ña d li u - MIMD li u gi a hai x lý, m t bên g i và m t bên nh n, chúng ta g i hình 1.2.2. Mô hình l p trình song song th c này là Point to Point (ñi m - ñi m). H u h t các c u trúc x lý M t mô hình l p trình song song là s d ng m t t p các c a chu n MPI ñ u d a trên truy n thông Point to Point. k thu t ph n m m ñ th hi n các gi i thu t song song và ñưa 1.3.3.1. Các thông tin c a thông ñi p ng d ng vào th c hi n trong h th ng song song. Mô hình bao 1.3.3.2. Các hình th c truy n thông g m các ng d ng, ngôn ng , b biên d ch, thư vi n, h th ng 1.3.4. Các ki u d li u ñã ñư c ñ nh nghĩa c a MPI truy n thông và vào/ra song song. Hi n nay có r t nhi u mô hình 1.4. T I ƯU T H P VÀ BÀI TOÁN NGƯ I DU L CH l p trình song song: Đa lu ng (Threads), Truy n thông ñi p 1.4.1. Bài toán T i ưu t h p (Message Passing), Song song d li u (Data Parallel), Lai Bài toán t i ưu hóa t h p liên quan t i vi c tìm giá tr cho (Hybird). các bi n s r i r c như l i gi i t i ưu mà có lưu ý t i hàm m c tiêu 1.2.3. Các chi n lư c song song hóa thu t toán (objective function) cho trư c. Bài toán có th là bài toán tìm c c ñ i 1.2.3.1. Song song hóa k t qu ho c tìm c c ti u. M t cách thông thư ng, bài toán t i ưu hoá t h p 1.2.3.2. Song song hóa ñ i di n ñư c cho dư i d ng b 3 (S, f, ). Trong ñó S là t p các l i gi i ng 1.2.3.3. Song song hóa chuyên bi t c viên, f là hàm m c tiêu (hàm này gán giá tr f(s) cho m i l i gi i 1.3. MÔ HÌNH TRUY N THÔNG ĐI P - MPI ng c viên s ∈ S), và là t p các ràng bu c c a bài toán. Các l i MPI - Message Passing Interface - là thư vi n truy n thông gi i thu c t p S ⊆ S th a mãn t p các ràng bu c * g i là l i gi i ñi p tiêu chu n d a trên s ñ ng thu n c a di n ñàn MPI v i hơn 40 kh thi. M c tiêu bài toán là tìm ra m t l i gi i kh thi t i ưu toàn c c t ch c tham gia bao g m c các nhà cung c p, các nhà nghiên c u, s*. V i các bài toán t i ưu hóa c c ti u là tìm l i gi i s* v i giá nh các nhà phát tri n thư vi n ph n m m và ngư i s d ng. Đó là m t nh t, nghĩa là f(s*) ≤ f(s) v i m i l i gi i s ∈ S. Ngư c l i bài toán thư vi n các hàm (trong C) ho c ti n trình con (trong Fortran) cho t i ưu hóa c c ñ i là tìm l i gi i s* v i giá l n nh t, nghĩa là f(s*) ≥ phép b n chèn vào trong code ñ th c hi n trao ñ i d li u gi a các f(s) v i m i l i gi i s ∈ S. Bài toán t i ưu hóa t h p có th chia 2 ti n trình. M c tiêu c a MPI là cung c p m t tiêu chu n ñư c s lo i: Bài toán tĩnh và bài toán ñ ng. d ng r ng rãi ñ vi t các chương trình chuy n gói tin ñ m b o tính di ñ ng, hi u qu và linh ho t.
-9- -10- 1.4.2. Bài toán Ngư i du l ch ñư ng, m t ñ mùi càng l n thì chúng càng có xu hư ng ch n. D a 1.4.2.1. Phát bi u bài toán vào hành vi tìm ki m này mà ñàn ki n tìm ñư c ñư ng ñi ng n nh t Có m t ngư i du l ch hay m t ngư i giao hàng c n ñi giao t t ñ n ngu n th c ăn và sau ñó quay tr v t c a mình. hàng t i n thành ph . Anh ta xu t phát t m t thành ph nào ñó, ñi 1.5.3. Đàn ki n nhân t o qua các thành ph khác ñ giao hàng và tr v thành ph ban ñ u. Đàn ki n nhân t o (Artificial Ants) mô ph ng các ho t ñ ng M i thành ph ch ñ n m t l n, và kho ng cách t m t thành ph ñ n c a ñàn ki n t nhiên và có m t s thay ñ i, ñi u ch nh so v i ñàn các thành ph khác ñã ñư c bi t trư c. Hãy tìm m t chu trình (m t ki n t nhiên ñ tăng tính hi u qu c a thu t toán. Các tính ch t c a ñư ng ñi khép kín th a mãn ñi u ki n trên) sao cho t ng ñ dài các ñàn ki n nhân t o như sau: c nh là nh nh t. - Ngoài thông tin pheromone thì ñàn ki n nhân t o còn s 1.4.2.2. Phân lo i bài toán d ng thông tin heuristic trong xây d ng lu t di chuy n c a 1.4.2.3. Các phương pháp ti p c n gi i bài toán TSP chúng. Có nhi u hư ng ñ ti p c n bài toán TSP như thi t k thu t - Ki n nhân t o có b nh ñ lưu thông tin c a ki n nh m toán tìm l i gi i chính xác, thu t toán x p x , thu t toán Heuristic và m c ñích xác ñ nh hành trình ñã ñi qua và ñ tính toán ñ dài gi i quy t các trư ng h p ñ c bi t. c a hành trình ñó. 1.5. T NG QUAN V THU T TOÁN KI N - Lư ng thông tin mùi pheromone ñư c thêm vào b i ki n 1.5.1. Gi i thi u chung nhân t o là hàm c a ch t lư ng l i gi i mà chúng tìm ñư c. T i ưu hóa thu t toán ñàn ki n (Ant Colony Optimization - Ki n nhân t o thư ng ch th c hi n tăng lư ng thông tin mùi ACO) là m t trong các thu t toán MetaHeuristic ñư c thi t k ñ gi i sau khi ñã hoàn thành l i gi i. quy t các bài toán t i ưu t h p, s d ng phương pháp tính xác su t - Ki n nhân t o s d ng cơ ch bay hơi thông tin pheromone ñ tìm ñư ng ñi ng n nh t c a ñ th . H th ng ACO l n ñ u tiên ñ tránh b t c trong bài toán t i ưu c c b . ñư c Marco Dorigo gi i thi u trong lu n văn c a mình vào năm 1.5.4. Các nguyên t c c a thu t toán ki n 1992, và ñư c g i là H th ng ki n (Ant System, hay AS). 1.5.2. Đàn ki n t nhiên Ki n là lo i cá th s ng b y ñàn. Chúng giao ti p v i nhau thông qua mùi mà chúng ñ l i trên hành trình mà chúng ñi qua. M i ki n khi ñi qua m t ño n ñư ng s ñ l i trên ño n ñó m t ch t mà chúng ta g i là mùi. S lư ng mùi s tăng lên khi có nhi u ki n cùng ñi qua. Các con ki n khác s tìm ñư ng d a vào m t ñ mùi trên
-11- -12- CHƯƠNG 2 chúng ñã ñi qua. G n v i m i c nh (i,j) n ng ñ v t mùi τ ij và thông T I ƯU ĐÀN KI N VÀ THU T TOÁN KI N SONG SONG s heuristic η ij trên c nh ñó. 2.1. T I ƯU ĐÀN KI N –ACO Ban ñ u n ng ñ mùi trên m i c nh (i,j) ñư c kh i t o b ng 2.1.1. Thu t toán Ant System (AS) m t h ng s c, ho c ñư c xác ñ nh theo công th c: 2.1.1.1. Quy t c di chuy n c a ki n m τ ij = τ 0 = , ∀(i, j ) (2.3) Trong thu t toán AS, ki n xây d ng m t ñư ng ñi b t ñ u t i C nn m t ñ nh ñư c ch n ng u nhiên. Vi c c p nh t pheromone ñư c ti n hành như sau: T i ñ nh i, m t con ki n k s ch n ñ nh j chưa ñư c ñi qua - Đ u tiên t t c pheromone trên các cung s ñư c gi m ñi trong t p láng gi ng c a i theo công th c sau: b i m t lư ng: pij = k (τ ij )α (ηij )β , j ∈ N k (2.1) τ ij ← (1 − ρ ).τ ij (2.4) ∑l∈N (τ il ) (ηil ) α β i k i V i ρ trong kho ng (0,1) là t c ñ bay hơi c a pherromone. - Ti p theo m i con ki n trong ñàn s ñ t thêm m t lư ng Trong ñó: thông tin pheromone trên nh ng cung mà chúng ñã ñi qua pijk : xác su t con ki n k l a ch n c nh (i,j) trong hành trình c a chúng. τ ij : n ng ñ v t mùi trên c nh (i,j) m α : h s ñi u ch nh nh hư ng c a τ ij τ ij ← τ ij + ∑ ∆τ ij k (2.5) η ij : thông tin heuristic giúp ñánh giá chính xác k =1 s l a ch n c a con ki n khi quy t ñ nh ñi t ñ nh i qua ñ nh j và Trong ñó: ∆τ ij là lư ng pheromone mà con ki n k ñ t lên k ñư c tính theo công th c: c nh mà nó ñã ñi qua và ñư c tính như sau: η ij = 1 (2.2) 1 / C k , n u ki n k qua cung (i,j) d ij ∆τ = k ij (2.6) 0 , ngư c l i dij : kho ng cách gi a ñ nh i và ñ nh j β : h s ñi u ch nh nh hư ng c a η ij V i: C k là ñ dài ñư ng ñi c a con ki n th k sau khi hoàn Nik : t p các ñ nh láng gi ng c a i mà con ki n k thành ñư ng ñi, t c là b ng t ng các cung thu c ñư ng ñi mà chưa ñi qua ki n ñã ñi qua. 2.1.1.2. Quy t c c p nh t thông tin mùi Trong quá trình di chuy n tìm ñư ng ñi c a ñàn ki n, chúng th c hi n vi c c p nh t thông tin mùi trên nh ng ño n ñư ng mà
-13- -14- 2.1.2. Thu t toán Ant Colony System (ACS) C p nh t thông tin mùi c c b : 2.1.2.1. Quy t c di chuy n c a ki n Công th c như sau: Trong thu t toán ACS, con ki n k ñang ñ nh i, vi c ki n τ ij ← (1 − ρ )τ ij + ρτ 0 (2.9) ch n ñ nh j ñ di chuy n ñ n ñư c xác ñ nh b ng qui lu t như sau: V i: - Cho q0 là m t h ng s cho trư c (0 ≤ q0 ≤ 1) - ρ : là tham s bay hơi n m trong kho ng (0,1) - Ch n ng u nhiên m t giá tr q trong kho ng [0, 1] - τ0 = 1 - N u q ≤ q0 ki n k ch n ñi m j di chuy n ti p theo d a trên nC nn giá tr l n nh t c a thông tin mùi và thông tin heuristic có trên c nh - n : là s ñ nh hay s thành ph tương ng v i công th c: - Cnn: chi u dài hành trình cho b i phương pháp tìm ki m g n j = arg l∈N k max τ il (η il ) i ( β ) (2.7) nh t (nearest neighbor – nn). 2.1.3. Thu t toán Max-Min Ant System (MMAS) - N u q > q0 ki n k s ch n ñ nh j chưa ñư c ñi qua trong t p Lu t di chuy n c a ki n ñư c th c hi n tương t như trong láng gi ng c a i theo m t qui lu t phân b xác su t ñư c xác ñ nh thu t toán ACS d a trên công th c (2.7). theo công th c sau: 2.1.3.1. Quy t c c p nh t thông tin mùi pij = k (τ ) (η ) ij α ij β , j ∈ N ik Thu t toán MMAS th c hi n vi c c p nh t thông tin mùi khi ∑ (τ ) (η ) α β toàn b ki n trong ñàn hoàn thành l i gi i và lư ng thông tin mùi ch l∈N ik il il c p nh t trên các c nh thu c l i gi i t i ưu nh t. Ban ñ u cũng th c 2.1.2.2. Quy t c c p nh t thông tin mùi hi n bay hơi thông tin mùi trên các c nh thu c lơi gi i t i ưu v i m t C p nh t thông tin mùi toàn c c: lư ng ñư c xác ñ nh t i công th c (2.4). M t con ki n có ñư ng ñi t t nh t sau m i l n l p thì ñư c Lư ng pheromone trên m t c nh ñư c xác ñ nh như sau : phép c p nh t thông tin pheromone. Vi c c p nh t ñư c th c hi n theo công th c sau: τ ij ← τ ij + ∆τ ij best τ ij ← (1 − ρ )τ ij + ρ∆τ ij bs (2.8) 1 / Cbest n u ki n qua c nh (i,j) v i ∆τ ij =  best V i ∆τ ij = 1 bs là lư ng pheromone ñ t lên c nh (i,j) 0 ngư c l i C bs mà ki n ñi qua. Cbest là ñ dài ñư ng ñi ng n nh t c a con ki n th k sau khi Cbs là ñ dài ñư ng ñi t t nh t c a con ki n th k sau khi c ñàn hoàn thành ñư ng ñi. hoàn thành ñư ng ñi, t c là b ng t ng các cung thu c ñư ng ñi t t nh t mà ki n ñã ñi qua.
-15- -16- 2.1.3.2. Kh i t o và kh i t o l i thông tin mùi - aki : nh n giá tr True, False tương ng v i con ki n k ñã Thu t toán MMAS ñã thêm vào giá tr c n trên và giá tr c n thăm ho c chưa ñi qua ñ nh i dư i cho thông tin pheromone g i là τmin và τmax . Các bư c xây d ng thu t toán như sau: Sau m i l n c p nh t giá tr thông tin mùi τ ij , n u Đ u vào: τ ij < τ min thì s gán τ ij = τ min và n u τ ij > τ max thì gán τ ij = τ max . Đ th G=(V,E), v i t p ñ nh V và t p c nh E, ma tr n tr ng Giá tr c n trên τ max thư ng ñư c thi t l p v i công th c sau: s D = d[i,j], v i i, j ∈ V. τ max = 1 ρC S lư ng ki n m. best Đ u ra: ñư ng ñi S v i kho ng cách ng n nh t CS Giá tr c n dư i τ min ñư c xác ñ nh b ng công th c Các bư c τmin = τmax / 2n. Bư c 1: Kh i t o 2.2. THU T TOÁN KI N CHO BÀI TOÁN NGƯ I DU L CH Kh i t o các tham s NC, β, α, ρ, s lư ng ki n m và s ñ nh n Áp d ng thu t toán ki n vào bài toán ngư i du l ch v i các Kh i t o ñ dài ñư ng ñi ng n nh t Cbest là h ng s thông s c a ki n như sau: Tính ñ dài ñư ng ñi ng n nh t Cnn - m: s lư ng ki n Tính giá tr τ max = 1 - τ ij : n ng ñ v t mùi trên c nh (i,j) ρC nn và τ min = τ max / 2n - ρ : là tham s bay hơi n m trong kho ng (0,1) Kh i t o giá tr q0 v i (0 ≤ q0 ≤ 1) - pijk : xác su t con ki n k l a ch n c nh (i,j) Kh i gán ñi u ki n k t thúc stop := 1 -α : h s ñi u ch nh nh hư ng c a τ ij Thi t l p ma tr n pheromone trên t t c các c nh - η ij : thông tin heuristic giúp ñánh giá chính xác s l a for i:=1 to n do ch n c a ki n ñi t ñ nh i t i ñ nh j for j:=1 to n do τ ij = τ max -β : h s ñi u ch nh nh hư ng c a η ij Bư c 2: Xây d ng ñư ng ñi c a ki n - Nik : t p các ñ nh láng gi ng c a i mà con ki n k chưa ñi Trư ng h p hoàn thành xong t t c các bư c l p: stop > NC thì qua xu t ra ñư ng ñi ng n nh t và k t thúc - ∆τ k ij là lư ng pheromone mà con ki n k ñ t lên c nh mà nó 2.1 Thi t l p các ñ nh khi ki n chưa ñi qua nh n giá tr false ñã ñi qua for k:=1 to m do - NC : là s bư c l p c a thu t toán for i:=1 to n do aki:= false - Sk : ñư ng ñi c a ki n k ( t p các ñ nh mà ki n k ñi qua) Thi t l p ñư ng ñi c a ki n S k = φ - q : là giá tr ng u nhiên trong kho ng [0, 1] 2.2 Ch n ng u nhiên v trí xu t phát c a ki n
-17- -18- for k:=1 to m do for j:=i to n do τ ij := (1 − ρ )τ ij for i:=1 to n do 4.2 Thêm thông tin mùi trên các c nh thu c ñư ng ñi t t nh t r ← random{ ..n} 1 Sk,best 1 B sung r vào ñư ng ñi Sk:={r}, akr:= true; Tính giá tr pheromone ∆τ = C Gán ñ dài ñư ng ñi Ck:=0 N u c nh (i, j ) ∈ S k best thì τ ij := best + ∆τ τ ij 2.3 Xác ñ nh ñ nh ñ n ti p theo c a ki n k Ki m tra thông tin pheromone v i c n trên và c n dư i - Ch n ng u nhiên m t giá tr q: q ← random{0..1} N u τij < τmin thì τij = τmin - N u q ≤ q0 ki n k ch n ñi m u di chuy n ti p theo v i N u τij > τmax thì τij = τmax r ( u = arg l∈N k max τ rl (η rl ) β ) Tăng giá tr stop:=stop+1. 2.3. SONG SONG HÓA THU T TOÁN KI N - N u q > q0 ki n k s ch n ñ nh u chưa ñư c ñi qua trong t p 2.3.1. T ng quan thu t toán ki n song song láng gi ng c a r theo công th c sau: p ru = k (τ ru )α (η ru )β , u ∈ N k Trong lu n văn này trình bày chi ti t hai chi n lư c song ∑l∈N (τ rl ) (η rl ) α β r song hóa thu t toán ki n c a B. Bullnheimer, G. Kotsis, C. Strauss là k r song song ñ ng b và song song b t ñ ng b m t ph n. - Ch n ñ nh u là ñ nh ti p theo, b sung ñ nh u vào Sk 2.3.2. Thu t toán song song ñ ng b Sk:= {r, u} 2.3.2.1. Ý tư ng thu t toán - Tăng ñ dài ñư ng ñi Ck:=Ck + dru Thu t toán s d ng mô hình Master/Slave trên ki n trúc b - Gán aku:=true nh phân tán g m m t vi x lý ñ m nh n vai trò Master và các vi x Bư c 3: Xác ñ nh ñư ng ñi ng n nh t lý còn l i là Slave. M i m t Slave ñư c gán cho m t tác t ki n và Ta có Ck là ñ dài ñư ng ñi c a con ki n k v i k=[1..m] thu th c hi n nhi m v xây d ng m t ñư ng ñi. Master có nhi m v kh i ñư c t bư c 2. t o các thông tin ban ñ u, c p nh t thông tin pheromone toàn c c N u Ck < Cbest thì hi u ch nh Cbest:=Ck nh n t các Slave và ñưa ra k t qu t i ưu. Bư c 4: C p nh t thông tin mùi 2.3.2.2. Các bư c thu t toán T i bư c này, ch c p nh t thông tin mùi trên ñư ng ñi c a Đ i v i Master con ki n k có giá tr Ck nh nh t thu ñư c t bư c 3, t c là giá tr Bư c 1: Kh i t o Cbest G i các tham s ñ n m i Slave 4.1 Bay hơi thông tin mùi trên các c nh G i ma tr n d và pheromone τ ñ n m i Slave for i:=1 to n do Bư c 2: Xác ñ nh ñư ng ñi ng n nh t c a ki n
-19- -20- Bư c 3: C p nh t thông tin Pheromone Đ i v i Slave Đ i v i Slave Bư c 1: Nh n các tham s t Master Bư c 1: Nh n các tham s t Master Bư c 2: Xây d ng ñư ng ñi cho ñàn ki n Bư c 2: Xây d ng ñư ng ñi N u step > T thì d ng và chuy n sang bư c 3 Bư c 3: G i ñư ng ñi Sk và ñ dài ñư ng ñi Ck v Master 2.1 Kh i t o thành ph xu t phát c a m i ki n t i m i Slave 2.3.2.3. Sơ ñ thu t toán 2.2 Xây d ng ñư ng ñi cho t ng ki n 2.3.3. Song song b t ñ ng b m t ph n 2.3 C p nh t ma tr n pheromone c c b 2.3.3.1. Ý tư ng thu t toán Bư c 4: G i ñư ng ñi Sk và ñ dài ñư ng ñi Cbest v Trong chi n lư c này s lư ng ki n m nhi u hơn s vi x lý Master P, (P < m). Như v y, m i Slave ñ m nh n th c hi n xây d ng ñư ng 2.3.3.3. Sơ ñ thu t toán ñi cho m t ñàn ki n v i s lư ng là m/P. Vi c phân chia theo chi n 2.3.4. Hi u qu c a thu t gi i song song lư c này là gi m ñáng k chi phí truy n thông gi a Master và Slave. Vi c xem xét hi u qu c a thu t gi i song song thư ng căn 2.3.3.2. Các bư c thu t toán c vào các y u t như: th i gian thi hành, t c ñ (Speedup), hi u su t Đ i v i Master (efficienly), chi phí (Cost) và qui mô (Scaling). Bư c 1: Kh i t o 2.3.4.1. Chi phí Bư c 2: Xác ñ nh ñư ng ñi ng n nh t Ký hi u T0 là hàm overhead, ta có: Trư ng h p stop > NC thì xu t ra ñư ng ñi ng n nh t và k t T0 = pTP – TS thúc 2.3.4.2. T c ñ 2.1 G i các tham s ñ n m i Slave T c ñ ký hi u S = TS/TP. G i ma tr n d và pheromone τ ñ n m i Slave 2.3.4.3. Hi u su t 2.2 Nh n ñư ng ñi Sk ñ dài ñư ng ñi Ck t các Slave Hi u su t là ñ ño th i gian mà ph n t x lý (PE) s d ng 2.3 Xác ñ nh ñư ng ñi ng n nh t h u ích, là t s gi a t c ñ (Speedup) và s ph n t x lý PE (E = N u Ck < Cbest thì Cbest := Ck S/p). Bư c 3: C p nh t thông tin Pheromone 3.1 Bay hơi thông tin mùi trên các c nh 3.2 Thêm thông tin mùi trên các c nh thu c ñư ng ñi ng n nh t Sk,best 3.3 G i ma tr n Pheromone τ m i cho Slave
-21- -22- CHƯƠNG 3 3.1.2.3. C p nh t Pheromone PHÂN TÍCH, XÂY D NG VÀ CÀI Đ T CHƯƠNG TRÌNH Có hai giai ño n chính trong ch c năng c p nh t thông tin 3.1. Đ C T C U TRÚC D LI U VÀ CÁC CH C NĂNG pheromone ñó là th c hi n bay hơi trên các cung và c p nh t thông CHÍNH C A CHƯƠNG TRÌNH tin pheromone m i trên các cung thu c ñư ng ñi t t nh t c a ki n. 3.1.1. C u trúc d li u Trong thu t toán MMAS có b sung thêm giá tr c n trên và giá tr 3.1.1.1. Các thông s chính c n dư i c a thông tin pheromone nên có ch c năng ki m tra các giá Trong ph n này mô t c u trúc d li u c a các thông s chính tr này. c a chương trình. Chương trình s d ng mã ngu n thu t toán ki n 3.1.2.4. Th c hi n song song tu n t ACOTSP.V1.01 tham kh o trong [15] và phát tri n thành Vi c th c hi n song song trong lu n văn này là cho p tác t chương trình song song. Chương trình s d ng các t p tin gr24.tsp, ki n ho c ñàn ki n ti n hành tìm ñư ng ñi hay xây d ng gi i pháp st70.tsp, kroA100.tsp trong thư vi n TSPLIB [13] ñ ñánh giá k t cho mình trên p b vi x lý. qu th nghi m. Bài toán ñư c xây d ng ch y trên ki n trúc b nh phân tán 3.1.1.2. C u trúc d li u c a ki n v i mô hình song song truy n thông ñi p, s d ng thư vi n MPI. 3.1.1.3. Ki u d li u c a MPI 3.2. NGÔN NG L P TRÌNH VÀ MÔI TRƯ NG PHÁT 3.1.2. Các ch c năng chính TRI N NG D NG 3.1.2.1. Kh i t o d li u Ngôn ng l p trình ñư c s d ng là ngôn ng C, trình biên Ch c năng kh i t o d li u bao g m các hàm kh i t o cho d ch là GCC (GNU C compiler), ph n m m h tr phát tri n ng c u trúc d li u ñã nêu trong ph n 3.1.1 Đ u tiên s th c hi n ñ c các d ng là CodeBlocks. Thư vi n chu n ñ c t truy n thông ñi p s d li u t t p tin trong TSP, sau ñó t o l p ma tr n tr ng s , danh d ng trong chương trình là b n MPICH2. sách các láng gi ng, kh i t o thông tin Heuristic, kh i t o c u trúc 3.3. K T QU TH C NGHI M CHƯƠNG TRÌNH ki n và kh i t o m t s bi n b sung ñ theo dõi th c hi n thu t toán. 3.3.1. Th c nghi m chương trình 3.1.2.2. Xây d ng dư ng ñi 3.3.2. Đánh giá k t qu Ch c năng xây d ng ñư ng ñi cho ki n ñư c th c hi n thông 3.3.2.1. Đánh giá chương trình song song qua 3 giai ño n riêng bi t. Đ u tiên m i ki n s ñư c phân b ng u - Chương trình song song không phá v c u trúc c a thu t nhiên t i m t thành ph xu t phát, sau ñó ki n xây d ng m t ñư ng toán tu n t cho nên ch t lư ng l i gi i c a nó tương t như chương ñi qua t t c các thành ph b ng cách xác ñ nh v trí thành ph di trình tu n t . chuy n ti p theo và cu i cùng là tr v l i v trí xu t phát và tính ñ - Chương trình ch th c hi n song song bư c xây d ng gi i dài ñư ng ñi hoàn thành. pháp ñư ng ñi c a ki n.
-23- -24- - Chương trình không th c hi n c u trúc liên k t m ng trao B ng 3.2 Th i gian trung bình tìm ra gi i pháp t i ưu trên s vi ñ i thông tin gi a các ñàn ki n, chi phí truy n thông gi a x lý Master/Slave l n, th i gian th c hi n ph thu c vào c u hình máy S vi x lý 2 4 6 tính ch y chương trình. 15 5 10 3.3.2.2. Đánh giá k t qu th c hi n 12 9 7 - K t qu c a chương trình tu n t và song song là tương t Th i gian cho 21 15 11 nhau căn c trên các t p tin k t qu xu t ra c a chương trình. m i vòng l p 29 33 13 - Qua th c nghi m, th i gian th c hi n thu t toán song song (giây) 19 10 8 tìm ki m k t qu t i ưu nhanh hơn so v i tìm ki m b ng thu t toán 10 7 6 tu n t và t l ph thu c vào s lư ng vi x lý s d ng. 17 5 7 - Khi s lư ng b vi x lý tăng lên thì th i gian trung bình ñ Trung bình 17.57 12 8.85 tìm ra gi i pháp t i ưu s gi m. - Đ i v i cùng s lư ng các b vi x lý thì th i gian trung B ng 3.3 Hi u su t tương ng v i các d li u c a bài toán TSP bình ñ tìm ra gi i pháp t i ưu t i m i vòng l p khác nhau cũng khác nhau, ñư c mô t b ng 3.1. Hi u su t th c hi n Bài toán TSP 2 4 6 B ng 3.1 T c ñ th c hi n tương ng v i các d li u c a bài toán Gr24.tsp 0.4 0.175 0.116 TSP St70.tsp 0.63 0.307 0.205 T c ñ th c hi n Bài toán TSP kroA100.tsp 0.705 0.342 0.228 2 4 6 Gr24.tsp 0.8 0.7 0.7 St70.tsp 1.27 1.23 1.23 kroA100.tsp 1.41 1.37 1.37
-25- -26- K T LU N VÀ HƯ NG PHÁT TRI N - Lu n văn ch t p trung nghiên c u thu t toán ñàn ki n trong 1. K t lu n h P-Meta heuristic, chưa nghiên c u các thu t toán khác ( như thu t Nh ng k t qu nghiên c u c a lu n văn cho phép rút ra nh ng toán ñàn ong ) ñ có nh ng so sánh ñánh giá. k t lu n: - Trong vi c song song hóa thu t toán ñàn ki n, chưa tìm V lý thuy t hi u v quá trình trao ñ i thông tin mùi và gi i pháp gi a các ñàn - Tìm hi u ñư c thu t toán ñàn ki n trong vi c xác ñ nh ñư ng ñi ki n trong vi c xây d ng ñư ng ñi. ng n nh t b ng phương pháp tính xác su t gi a các ñi m di chuy n V th c nghi m d a trên các thông tin v ñ dài ñư ng ñi, thông tin heuristic và - M c dù ñã phân tích ñư c các nhóm ch c năng nhưng còn thông tin mùi pheromone mà các con ki n ñ l i trên ñư ng ñi trong nhi u ch c năng chưa cài ñ t hoàn ch nh ho c ñã cài ñ t nhưng chưa quá trình di chuy n. ki m tra th nghi m trong th c t . - Hi u ñư c các phương pháp ti p c n t i ưu thu t toán ñ nâng - Chương trình ch m i song song hóa ñư c m t ph n d a cao ñ chính xác cho thu t toán ki n, c th là c i ti n quy lu t di theo ý tư ng ñã nêu, chưa th c nghi m trên ki n trúc song song b chuy n c a ki n và qui lu t c p nh t thông tin mùi pheromone th nh chia s ñ có ñánh giá hi u qu c a thu t toán trên các lo i ki n hi n thu t toán Ant Colony System và Max-Min Ant System. trúc khác nhau. - Hi u ñư c các chi n lư c song song hóa thu t toán và th c hi n - Chương trình còn tính ch t mô ph ng chưa ph i là m t ng song song hóa thu t toán ki n trên ki n trúc b nh phân tán và mô d ng c th . hình song song Master/Slave. Qua ñó ñánh giá ñư c thu t toán d a 2. Hư ng phát tri n trên các tiêu chí v t c ñ , hi u su t và chi phí. V lý thuy t V th c nghi m - Ti p t c nghiên c u sâu thêm v thu t toán ñàn ki n v i Phân tích và mô t ñư c các nhóm ch c năng c a chương trình nh ng phương pháp t i ưu hóa ñư c c i ti n áp d ng trong các bài ng d ng. Đây là cơ s ñ ti p t c phát tri n ñ tài trong tương lai. toán t i ưu hóa t h p ph c t p. Cài ñ t thành công chương trình th c nghi m tìm ñư ng ñi ng n - Nghiên c u m t s thu t toán thu c toán thu c h P-Meta nh t c a thu t toán ki n áp d ng vào bài toán ngư i du l ch trên môi heuristic và song song hóa ñ so sánh, ñánh giá tính chính xác và trư ng song song. Chương trình ñư c ki m tra v i d li u ñ u vào m c ñ hi u qu gi a các thu t toán meta heuristic. ñư c khai thác t thư vi n TSPLIB. V th c nghi m Đánh giá ưu ñi m và h n ch c a ñ tài - Ti p t c cài ñ t các ch c năng còn thi u, ñ c bi t là b sung V lý thuy t ch c năng trao ñ i thông tin gi a các ñàn ki n trên các mô hình liên k t m ng khác nhau.