Ứ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ễ

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ó.
Nội dung trích xuất từ tài liệu:
Ứ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.vn1. ĐẶT VẤN ĐỀ Bài toán cực tiểu hóa ñộ trễ (MLP – Minimum Latency Problem) ñược phát biểu dướidạ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ử Plà ñườ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áccạ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à ñã ñượcchứ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ỘIkhô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ảibà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ệmtrê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ếmTABU [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áncự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 rangẫ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ệmtố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 ñànchim ñ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ôngbiế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êulầ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ữngcon 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ầysẽ 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ántố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ệmcủ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 (currentoptimum 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ằngcá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ốtnhấ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á ...