Trong bài báo này sẽ trình bày một thuật toán meta-heuristic (ACO-GA) lai ghép giữa thuật toán di truyền (GA) và thuật toán đàn kiến (ACO). Thuật toán đàn kiến đóng vai trò khởi tạo quần thể cho thuật toán di truyền. Trong khi đó, thông tin di truyền từ thuật toán di truyền giúp định hướng cá thể kiến chọn đường đi tốt hơn ở lần khởi tạo quần thể kế tiếp. | Tạp chí Tin học và Điều khiển học, , (2013), 285–297 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Ễ BAN HÀ BẰNG, NGUYỄN ĐỨC NGHĨA Viện Công nghệ Thông tin và Truyền thông - Đại học Bách khoa Hà Nội Email: (BangBH, NghiaND) Tóm t t. Bài toán cực tiểu hóa độ trễ thuộc lớp bài toán tối ưu hóa tổ hợp có nhiều ứng dụng trong thực tiễn. Trong trường hợp tổng quát, bài toán được chứng minh thuộc lớp NP-khó và ngoại trừ P = NP, không tồn tại lược đồ xấp xỉ với thời gian đa thức để giải nó. Bởi vậy, việc phát triển các thuật toán gần đúng là hướng tiếp cận phù hợp để giải bài toán. Trong bài báo này sẽ trình bày một thuật toán meta-heuristic (ACO-GA) lai ghép giữa thuật toán di truyền (GA) và thuật toán đàn kiến (ACO). Thuật toán đàn kiến đóng vai trò khởi tạo quần thể cho thuật toán di truyền. Trong khi đó, thông tin di truyền từ thuật toán di truyền giúp định hướng cá thể kiến chọn đường đi tốt hơn ở lần khởi tạo quần thể kế tiếp. Thêm vào đó, để duy trì tính đa dạng trong quần thể kiến, thuật toán sử dụng ba loại kiến với các đặc tính tìm kiếm đường đi khác nhau. Thực nghiệm thuật toán đã được thực hiện trên các bộ dữ liệu chuẩn. Kết quả thực nghiệm cho thấy thuật toán đưa ra lời giải với cận tỷ lệ tốt hơn so với các thuật toán meta-heuristic hiện biết trên nhiều bộ dữ liệu. T khóa. Bài toán cực tiểu hóa độ trễ-MLP, meta-heuristic, ACO, GA. Abstract. Minimum Latency Problem is a class of combinatorial optimization problems that have many practical applications. In the general case, the problem is proven to be NP-hard. Therefore, using a meta-heuristic algorithm is a suitable approach for solving this problem. In this paper, we propose a meta-heuristic algorithm which combines Ant Colony (ACO) and Genetic Algorithm (GA). In our algorithm, ACO generates a population for GA. Meanwhile, the genetic information of GA helps ants to create a better population in the next step. In addition, to maintain the .
