- ỨNG DỤNG GIẢI THUẬT TỐI ƯU BẦY Đ-N ỨNG DỤNG GIẢI THUẬT TỐI ƯU BẦY Đ-N ỨNG DỤNG GIẢI THUẬT TỐI ƯU BẦY Đ-N Ứ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Ễ V-O B-I TOÁN CỰC TIỂU HÓA ĐỘ TRỄ V-O B-I TOÁN CỰC TIỂU HÓA ĐỘ TRỄ V-O B-I TOÁN CỰC TIỂU HÓA ĐỘ TRỄ. - Tóm tắ ắ ắ ắtttt: 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ế. - 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. - 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 Từ ừ ừ ừ khóa khóa khóa: Cực tiểu hóa ñộ trễ, Minimum Latency Problem, MLP, Giải thuật di truyền, Tối khóa ưu bầy ñàn, PSO.. - 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:. - 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ì. - 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.. - 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. - 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. - 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. - 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:. - X i K : Vị trí cá thể thứ i tại thế hệ thứ K. - X i K + 1 : Vị trí cá thể thứ i tại thế hệ thứ K+1. - V i K : Vận tốc cá thể thứ i tại thế hệ thứ K. - V i K + 1 : Vận tốc cá thể thứ i tại thế hệ thứ K +1. - V i Pbest : Vận tốc theo P best. - V i Gbest : Vận tốc theo G best. - P best i : Vị trí tốt nhất của cá thể thứ i trong thế hệ. - G best i : 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: G best 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à L best. - 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:. - Giả mã của thuật toán PSO ñược mô tả như dưới ñây:. - Khởi tạo particle. - //Khởi tạo quần thể Do. - Tính vận tốc dịch chuyển theo công thức (1) Dịch chuyển Particle theo công thức (2) EndFor. - Trên ñây là thuật toán PSO nguyên bản [4] còn có tên là tối ưu toàn cục trong ñó vận tốc dịch chuyển mỗi phần tử sẽ phụ thuộc trên hai yếu tố: vị trí phần tử tốt nhất trong thế hệ hiện tại Pbest và vị trí phần tử tốt nhất từng ñạt ñược trong các thế hệ từ trước tới giờ Gbest. - Sau này có thêm một số cải tiến với ñề xuất ñưa thêm yếu tố cục bộ là ngoài hai yếu tố Pbest và Gbest thì sự dịch chuyển của cá thể sẽ phụ thuộc thêm bởi một yếu tố là vị trí tốt nhất lân cận nó gọi là Lbest. - Khi ñó vecto vận tốc sẽ ñược tính theo công thức sau:. - Một ñề xuất cải tiến khác cũng rất triển vọng ñó là sự dịch chuyển của phần tử ngoài hai yếu tố Pbest và Gbest thì còn thêm một yếu tố thứ ba ñó là vecto dịch chuyển của cá thể ñó ở thế hệ trước. - Khi ñó công thức tính vận tốc sẽ ñược viết lại là:. - 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.. - THUẬT TOÁN PSO ĐỀ XUẤT. - 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). - 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.. - 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. - 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. - 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.. - 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ố C 1 = C 2 = C 3 = 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). - 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.. - 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ộ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.. - 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.. - Tệp dữ liệu OPT. - 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. - 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.. - 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.. - 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.. - APPLYING PARTICLE SWARM OPTIMIZATION FOR MINIMUM LATENCY PROBLEM
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt