Ứng dụng giải thuật tối ưu bầy đàn vào bài toán cực tiểu hóa độ trễ

Chia sẻ: ViJichoo _ViJichoo | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

38
lượt xem 1
download

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

Bài toán cực tiểu hóa độ trễ (Minimum Latency Problem – MLP) là một trong những bài toán tối ưu tổ hợp có nhiều ứng dụng trong thực tế. Trong trường hợp tổng quát, MLP đã được chứng minh là NP-khó.

Chủ đề:

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

Lưu

Nội dung Text: Ứng dụng giải thuật tối ưu bầy đàn vào bài toán cực tiểu hóa độ trễ

TẠP CHÍ KHOA HỌC − SỐ 18/2017 15 ỨNG DỤNG GIẢI THUẬT TỐI ƯU BẦY Đ-N V-O B-I TOÁN CỰC TIỂU HÓA ĐỘ TRỄ Lê Chí Chung Trường Đại học Thủ ñô Hà Nội Tóm tắtắt: Bài toán cực tiểu hóa ñộ trễ (Minimum Latency Problem – MLP) là một trong những bài toán tối ưu tổ hợp có nhiều ứng dụng trong thực tế. Trong trường hợp tổng quát, MLP ñã ñược chứng minh là NP-khó. Hiện nay có nhiều công trình giải bài toán theo hướng tiếp cận gần ñúng nhất là theo hướng phỏng sinh học. Lời giải thu ñược từ những công trình này là rất có triển vọng. Với mục ñích kiểm chứng hiệu quả của thuật toán theo hướng tiếp cận này, bài báo trình bày thuật toán giải bài toán MLP bằng giải thuật tối ưu bầy ñàn (Particle Swarm Optimize - PSO) với mong muốn thu ñược lời giải tốt hơn những công trình trước. Từ khóa: khóa Cực tiểu hóa ñộ trễ, Minimum Latency Problem, MLP, Giải thuật di truyền, Tối ưu bầy ñàn, PSO. Nhận bài ngày 18.8.2017; gửi phản biện, chỉnh sửa và duyệt ñăng ngày 10.9.2017 Liên hệ tác giả: Lê Chí Chung; Email: lcchung@daihocthudo.edu.vn 1. ĐẶT VẤN ĐỀ Bài toán cực tiểu hóa ñộ trễ (MLP – Minimum Latency Problem) ñược phát biểu dưới dạng ñồ thị như sau: Cho trước ñồ thị ñầy ñủ G = (V,E) với trọng số không âm trên mỗi cạnh e∈E. Giả sử P là ñường ñi qua tất cả các ñỉnh thuộc V, mỗi ñỉnh ñi qua ñúng một lần. Độ trễ của ñường ñi ñược ñịnh nghĩa như sau: Cho trước ñỉnh xuất phát s, ñộ trễ của ñỉnh v bất kì trên ñường ñi P là tổng ñộ dài các cạnh từ s tới v trên P. Độ trễ của ñường ñi T chính là tổng các ñộ trễ của các ñỉnh nằm trên ñường ñi P. Bài toán cực tiểu hóa ñộ trễ ñặt ra: Cho trước ñỉnh xuất phát s, hãy tìm ñường ñi ñơn ñi qua tất cả các ñỉnh sao cho ñộ trễ của ñường ñi là nhỏ nhất. Bài toán cực tiểu hóa ñộ trễ là bài toán có nhiều ứng dụng trong thực tiễn và ñã ñược chứng minh trong trường hợp tổng quát là bài toán NP- khó nghĩa là ngoại trừ P = NP thì
16 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI không có thuật toán nào giải ñược nó với thời gian ña thức. Có nhiều cách tiếp cận ñể giải bài toán này. Hiện nay có 3 hướng tiếp cận ñể giải quyết bài toán: − Phát triển thuật toán ñúng tìm lời giải tối ưu như quy hoạch ñộng [8], Branchcut, Branchprice và Branchcutprice [9, 10]. − Thuật toán ñúng cận tỉ lệ α (α – approximation algoirthm) [11]. − Phát triển thuật toán meta heuristic với ñộ phức tạp không quá lớn và thực nghiệm trên các bộ dữ liệu chuẩn như thuật toán di truyền [1], phỏng luyện kim [13], tìm kiếm TABU [14]. Bài báo này ñề cập tới việc sử dụng thuật toán tối ưu bầy ñàn ñể giải quyết bài toán cực tiểu hóa ñộ trễ với mục ñích tăng chất lượng lời giải. 2. GIẢI THUẬT TỐI ƯU HÓA BẦY ĐÀN Particle Swarm Optimization (PSO) là một kĩ thuật tối ưu hóa dựa trên việc chọn ra ngẫu nhiên một quần thể và sau ñó tiến hóa các cá thể qua nhiều thế hệ ñể ñạt ñược nghiệm tối ưu. PSO ñược ñề xuất bởi James Kennedy và Russell Eberhart [5] vào năm 1995. Từ ñó, PSO ngày càng phổ biến ñối với các nhà nghiên cứu và học viên, nó trở thành một kỹ thuật mạnh mẽ và hiệu quả ñể giải quyết các vấn ñề tối ưu khó khăn Ý tưởng chính của PSO xuất phát từ tình huống trong tự nhiên. Giả sử có một ñàn chim ñang tìm kiếm thức ăn trong một vùng nào ñó. Ban ñầu tất cả các con chim không biết thức ăn ở ñâu. Tuy nhiên chúng sẽ dần biết thức ăn cách chúng bao xa sau bao nhiêu lần bay ñi bay lại. Bởi lẽ, muốn tìm thấy thức ăn nhanh nhất tốt hơn cả là theo sau những con chim gần thức ăn nhất. Nghĩa là sau khi biết ñược thức ăn gần con chim nào thì cả bầy sẽ xích lại gần con chim ấy. PSO phỏng theo kịch bản này và sử dụng ñể giải các bài toán tối ưu. Trong PSO thì mỗi giải pháp của bài toán chính là một con chim trong ý tưởng trên, ñược gọi là particle. Mỗi particle có một giá trị thích nghi (fitness value), ñược ñánh giá bằng hàm ño ñộ thích nghi (fitness function), và một vận tốc ñể ñịnh hướng việc di chuyển (bay-flying) ñể tìm kiếm. Các particle sẽ duyệt không gian tìm kiếm (không gian nghiệm của bài toán) bằng cách xích lại gần các particle có ñiều kiện tốt nhất hiện thời (current optimum particles). Trong một tập các cá thể chọn ra ngẫu nhiên (còn gọi là bầy ñàn), mỗi cá thể sẽ bằng cách di chuyển tới vị trí khác trong không gian tìm kiếm cho ñến khi tìm ñược vị trí tốt nhất. Khái niệm về sự thay ñổi vị trí ấy ñược khái quát trong hình sau:
TẠP CHÍ KHOA HỌC − SỐ 18/2017 17 Trong ñó: − X iK : Vị trí cá thể thứ i tại thế hệ thứ K − X iK +1 : Vị trí cá thể thứ i tại thế hệ thứ K+1 − Vi K : Vận tốc cá thể thứ i tại thế hệ thứ K − Vi K +1 : Vận tốc cá thể thứ i tại thế hệ thứ K +1 − Vi Pbest : Vận tốc theo Pbest − Vi Gbest : Vận tốc theo Gbest − Pbesti : Vị trí tốt nhất của cá thể thứ i trong thế hệ − Gbesti : Vị trí tốt nhất của cá thể trong cả quần thể Như thế PSO ñược khởi tạo bởi một nhóm ngẫu nhiên các cá thể và tìm kiếm giải pháp tối ưu bằng việc thay ñổi vị trí các cá thể ñể chúng có thể tiến lại gần những cá thể tối ưu hơn. Quá trình cứ lặp ñi lặp lại cho ñến khi sự thay ñổi của các cá thể là không ñáng kể. Trong mỗi vòng lặp (một thế hệ), một cá thể particle ñược cập nhật bởi hai giá trị: − Giá trị thứ nhất: Pbest là cá thể tốt nhất ñạt ñược tới thời ñiểm hiện tại hay là cá thể có fitness value tốt nhất trong thế hệ hiện tại − Giá trị thứ hai: Gbest là cá thể tốt nhất ñạt ñược trong các cá thể tối ưu của mỗi lần lặp. Đây có thể coi là cá thể có ñộ thích nghi cao nhất trong toàn không gian tìm kiếm. − Khi một cá thể có ñộ thích nghi tốt nhất so với những cá thể lân cận thì có thể coi ñây là tối ưu cục bộ gọi là Lbest Trong nguyên bản do Eberhart và Kennedy ñưa ra, các phần tử trong PSO sẽ duyệt không gian bài toán bằng cách theo sau các phần tử có ñiều kiện tốt nhất hiện thời (ñộ thích nghi lớn nhất). Cụ thể là sau mỗi khoảng thời gian rời rạc, vận tốc và vị trí của mỗi phần tử ñược cập nhật theo các công thức: V[] = v[] + c1 * rand()*(pbest[] – present[]) + C2 * ran()*(gbest[] – present[]) (1) Present[] = present[] + v[] (2)
18 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI Trong ñó: − V[] : vecto mô tả vận tốc dịch chuyển của cá thể − Present[]: là vecto mô tả cá thể hiện tại − Rand() trả về kết quả là 0 hoặc 1. Nghĩa là cá thể chọn ngẫu nhiên dịch chuyển theo Pbest hay Gbest. − C1 và C2 là tham số gia tốc hay là tham số học. Nó có ý nghĩa ñể tăng nhanh quá trình dịch chuyển. Việc lựa chọn giá trị cho 2 tham số này cũng cần cẩn trọng ñể tránh gia tốc nhanh quá sẽ làm quá trình lựa chọn cá thể tốt bị rơi vào best cục bộ. Giả mã của thuật toán PSO ñược mô tả như dưới ñây: 1 Khởi tạo particle; //Khởi tạo quần thể 2 Do 3 ForEach particle 4 Tính FitnessValue() 5 If Particle.FitnessValue < Pbest.FitnessValue then 6 Pbest = Particle; 7 EndIf 8 If Pbest
TẠP CHÍ KHOA HỌC − SỐ 18/2017 19 Khi ñó công thức tính vận tốc sẽ ñược viết lại là: v[] = v[] + c1.rand(). (pbest[] - present[]) + c2.rand() * (gbest[] - present[]) + c3.rand() * (forward[] - present[]) (1’’) Giải thuật PSO có thể ñược xem như là một tập hợp các vectơ có quỹ ñạo dao ñộng xung quanh một khu vực ñược xác ñịnh bởi từng vị trí của cá thể tốt nhất trước ñó và vị trí tốt nhất của một số cá thể khác. Gbest giúp bầy hội tụ nhanh, tất cả các cá thể ñược thu hút ñồng thời. Tuy nhiên, nếu Gbest không phải là cá thể tốt nhất, thì ñàn không thể khám phá khu vực khác, do ñó, bầy ñàn có thể bị mắc kẹt và thuật toán hội tụ sớm. 3. THUẬT TOÁN PSO ĐỀ XUẤT Ý tưởng Chúng tôi ñề xuất sử dụng thuật toán tối ưu bầy ñàn có cải tiến ñể giải quyết bài toán cực tiểu hóa ñộ trễ (Minimum Latency Problem – MLP). Chúng ta sẽ bắt ñầu bằng việc khởi tạo một tập các phương án(bầy ñàn) mà mỗi phương án thể hiện một. Theo quá trình của thuật toán PSO, ta dịch chuyển bầy ñàn qua nhiều vòng lặp rồi tìm ra phương án tốt nhất chấp nhận ñược. Thuật toán − Lược ñồ thuật toán Thuật toán PSO phải xác ñịnh các thủ tục chính sau ñây: Khởi tạo bầy ñàn, lựa chọn Pbest, cập nhật cho Gbest, xác ñịnh vectơ dịch chuyển cho mỗi cá thể dựa trên tiêu chí ñã chọn, dịch chuyển cá thể theo vectơ. Quá trình lặp lại cho ñến khi thỏa mãn ñiều kiện dừng của thuật toán. Trong bài báo này chúng tôi ñề xuất ñiều kiện dừng của thuật toán là sau 10 vòng lặp mà Pbest và Gbest không thay ñổi nhiều.
20 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI − Khởi tạo quần thể Vì ñồ thị ñã cho là ñồ thị ñầy ñủ và yêu cầu là ñường ñi ñơn xuất phát từ một ñỉnh s bất kì cho trước ñi qua các ñỉnh của ñồ thị nên ta sẽ mã hóa một phương án là mỗi cá thể là một chuỗi hoán vị 1. . . Trong ñó 1..n là chỉ số các ñỉnh trong ñồ thị INPUT và mỗi chuỗi
TẠP CHÍ KHOA HỌC − SỐ 18/2017 21 sẽ bắt ñầu bằng ñỉnh s. Số lượng tối ña các phương án trong không gian nghiệm của bài toán là (n-1)!. Độ thích nghi của cá thể sẽ ñược tính là tỉ lệ nghịch với ñộ trễ của chuỗi hoán vị ñã khởi tạo. Như vậy cá thể nào càng có ñộ thích nghi càng cao thì sẽ càng gần với nghiệm của bài toán. Số lượng hay kích thước ban ñầu của quần thể là m, ñóng vai trò quan trọng trong giải thuật vì kích thước quần thể quyết ñịnh sự hội tụ nhanh hay chậm của giải thuật, và khả năng thoát ra khỏ những cực trị ñịa phương của quần thể. Kích thước quần thể nhỏ thì giải thuật sẽ hội tụ nhanh nhưng thường sẽ cho ra kết quả là các cực trị ñịa phương chứ không phải là cực trị toàn cục. Vì với số lượng cá thể ít thì quần thể dễ mắc vào những cực trị ñịa phương và khó thoát ra ñược. Tuy nhiên, số lượng cá thể quá lớn lại làm thuật toán tốn nhiều thời gian, hội tụ chậm. Với bài toán cực tiểu hóa ñộ trễ, chúng tôi chọn số lượng cá thể là m=30. Về phương pháp khởi tạo quần thể cũng có nhiều cách khác nhau. Phương pháp ñơn giản nhất là random(). Như thế ta sẽ có 30 chuỗi hoán vị 1. . . − Xác ñịnh Pbest và Gbest Xác ñịnh Pbest thể hiện qua giả mã sau: 1 DelayNode(i) 2 Begin 3 For j = 1 to i-1 do 4 Begin 5 DelayNode = DelayNode + Distance(j,j+1) 6 End; 7 Return DelayNode; 8 END; 9 10
11 Tính FitnessValue ForEach Particle Begin DelayPath(Particle); If Particle.DelayPath()< Pbest.DelayPath() then Pbest = Particle; END; If Pbest < Gbest then Gbest = Pbest Xác ñịnh Pbest và Gbest
22 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI − Tính vectơ vận tốc và dịch chuyển cá thể Như ñã trình bày thì PSO hiện nay có một số cải tiến so với phiên bản gốc [4]. Để cải tiến trong việc tính toán vectơ vận tốc, cần dựa trên ba yếu tố: + Vị trí phần tử Gbest: Đại diện cho vị trí tối ưu cả bầy ñàn + Vị trí phần tử Pbest: ñại diện cho sự dịch chuyển bầy ñàn thời ñiểm hiện tại + Vectơ dịch chuyển từ vòng lặp trước Vấn ñề là ta sẽ tính vectơ dịch chuyển cho từng yếu tố như thế nào. Trong bài báo này, chúng tôi tính vectơ dịch chuyển bằng cách dựa trên các khoảng cách từ mỗi ñỉnh tới ñỉnh xuất phát. Theo ñề xuất này chúng ta so khớp từng cặp ñỉnh của hai cá thể. Mỗi ñỉnh cách ñỉnh xuất phát với khoảng cách là bao nhiêu thì lấy hiệu làm hệ số cho vectơ dịch chuyển. Nghĩa là sử dụng chính khoảng cách từ các ñỉnh tới ñỉnh A làm vectơ ñại diện. Giả sử ta ñang xét phần tử X có vectơ cùng tên ñang cần dịch chuyển về phía Pbest và Gbest cùng với một vectơ dịch chuyển của X từ vòng lặp trước. Sau cùng ta tính vectơ dịch chuyển của X tại vòng lặp này theo công thức (1) với hệ số C1 = C2 = C3 = 2; Sau khi có ñược vectơ dịch chuyển, ta dịch chuyển phần tử X thực chất là ñổi vị trí các ñỉnh trong chuỗi hoán vị sao cho nó tiếp cận càng gần với mục tiêu càng tốt. Do ñó ñể dịch chuyển cá thể hiện tại ta xét từng giá trị tương ứng trên vectơ. Vectơ dịch chuyển có n giá trị ñầu tiên luôn là 0 (vì ñỉnh xuất phát là cố ñịnh). Số ñỉnh cần chọn còn lại là n – 1 ñỉnh. Chúng ta có chiến lược như sau: Chọn ñỉnh tương ứng trong số ñỉnh còn lại mà có khoảng cách tới ñỉnh xuất phát gần nhất với giá trị tương ứng trong vectơ dịch chuyển. 4. THỰC NGHIỆM Bộ dữ liệu kiểm thử Dữ liệu kiểm thử ñược lấy từ thư viện dữ liệu chuẩn ñã ñược sử dụng rộng rãi trong các bài toán tối ưu. Dữ liệu chúng tôi chọn ñể kiểm thử cho ñề xuất trong công trình này là bộ TSPLIB [12]. Đây là bộ dữ liệu kiểm thử cho bài toán người bán hàng nhưng thỏa mãn ñiều kiện ñầu vào cho bài toán MLP. Đây là một thư mục các tệp dữ liệu. Mỗi tệp lưu trữ tọa ñộ các ñỉnh. Một tệp cùng tên với ñuôi mở rộng tour chứa chuỗi ñỉnh là ñường ñi ngắn nhất mà tới thời ñiểm hiện tại ñã tìm ñược. Dựa theo chuỗi ñỉnh này chúng ta cũng có thể tính ra tổng ñộ trễ của hành trình. Đây là ñối trọng ñể ta ñánh giá hiệu quả của thuật toán. Bộ dữ liệu khá phong phú nên chúng tôi chọn ra một số tệp dữ liệu ñại diện có kích thước không quá lớn (số ñỉnh 50-100) và ñộ phân bố ñều.
TẠP CHÍ KHOA HỌC − SỐ 18/2017 23 Kết quả thực nghiệm Dữ liệu chọn thử nghiệm và kết quả thử nghiệm thể hiện dưới bảng sau, trong ñó, kết quả bằng thuật toán GA ñược lấy từ [1,2 ]. OPT và BestSol lần lượt là ñộ trễ cực tiểu của bộ dữ liệu chuẩn và ñộ trễ cực tiểu ñược giải bằng các thuật toán GA và PSO. T là thời gian chạy của thuật toán tính bằng phút. GA PSO Tệp dữ liệu OPT BestSol T eil51 6140 6140 2,5 6232 1,6 eil76 5894 5894 2,6 6002 1,7 st70 7801 7801 2,5 8235 2,4 kroA100 239680 241012 2,6 242302 2,5 5. KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO Bài toán MLP là một bài toán thuộc lớp NP- khó ñang ñược quan tâm giải quyết. Hướng tiếp cận giải bài toán theo thuật toán tối ưu bầy ñàn có kết quả khá khả quan. Mặc dù kết quả thực nghiệm còn thấp có thể do thuật toán ñề xuất theo mô hình cổ ñiển có thể bị rơi vào cực trị ñịa phương và bầy ñàn không thể thoát ra ñược. Trong những bài báo tiếp theo, chúng tôi sẽ tiếp tục cải thiện kết quả bằng cách khắc phục sự hội tụ sớm và nâng cao chất lượng lời giải. TÀI LIỆU THAM KHẢO 1. Ban Hà Bằng, Nguyễn Đức Nghĩa (2009), “Giải thuật di truyền giải bài toán cực tiểu hóa ñộ trễ”, Tạp chí Khoa học và Công nghệ các trường Kĩ thuật, Số 71. 2. Ban Hà Bằng, Nguyễn Đức Nghĩa (2013), “Thuật toán di truyền lai ghép thuật toán ñàn kiển giải bài toán cực tiểu hóa ñộ trễ”, Tạp chí Tin học và Điều khiển học, Số 3, T.29. 3. Nguyễn Gia Như (2014), Một số thuật toán tiến hóa giải bài toán tối ưu trong mạng máy tính Luận án Tiến sĩ Toán học, Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội. 4. Y. Shi & R. Eberhart (1998), “A modified particle swarm optimizer”, IEEE 1998 International Conference. 5. Yuhui Shi and Russhell C.Eberhart (1998), “Parameter Selection In Particle Swarm Optimization”, Springer-Verlag London, UK. 6. James Kennedy and Russell Eberhart (1995), “Particle Swarm Optimization”, IEEE International Conference on Neural Network.
24 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 7. Rene Sitter (2002), “The Minimum Latency Problem Is NP-Hard for Weighted Trees”, Integer Programming and Combinatorial Optimization. 8. Michel Goemans Jon Kleinberg (1998), “An improved approximation ratio for the minimum latency problem”, Mathematical Programming, Vol.82. 9. R. Bellman (2003), “Dynamic Programming”, Dover Publications Inc. 10. G. L. Nemhauser and L. A. Wolsey (1998), “Interger and Combinatorial Optimization”, Wiley-Interscience. 11. F. Rossi, P. Van Beek, and T. Walsh (2006), “Eds. Handbook of Constraint Programming”, Elsevier. 12. V. Vazirani (2001), “Approximation Algorithms”, Springer publisher.Https://www.iwr.uni- heidelberg.de/groups/comopt/software/TSPLIB95/ APPLYING PARTICLE SWARM OPTIMIZATION FOR MINIMUM LATENCY PROBLEM Abstract: Minimum Latency Problem – MLP is one of the class of combinational optimization problems that has many practical applications. In the general case, the MLP is proved to be NP-hard. In fact, there are many the approaches to solve the problem. One of them is using meta-heuristic. This algorithms imitate follow a action of some swarm in the nature. In this paper, we propose are apply algorithm particle swarm optimization for solve MLP with a lager size. The results show that is an efficient approaches for minimum latency problems. Keywords: Minimum latency problems, Particle Swarm Optimization, meta – heuristic, GA – Genetic Algorithm.