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ó. | 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 gửi phản biện chỉnh sửa và duyệt ñăng ngày Liên hệ tác giả Lê Chí Chung Email lcchung@ 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 .
