CẢI TIẾN TOÁN TỬ ĐỘT BIẾN TRONG THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ GIẢI BÀI TOÁN CÂY KHUNG PHÂN CỤM ĐƯỜNG ĐI NGẮN NHẤT

Tóm tắt

Bài toán cây khung phân cụm đường đi ngắn nhất được ứng dụng nhiều trong tối ưu hệ thống tưới tiêu nông nghiệp, hệ thống cáp mạng và mạng lưới phân phối hàng hóa, dịch vụ. Do bài toán cây khung phân cụm đường đi ngắn nhất thuộc lớp bài toán NP-Khó nên các hướng tiếp cận gần đây thường sử dụng các thuật toán xấp xỉ để tìm lời giải, trong đó, hướng tiếp cận sử dụng kết hợp giữa thuật toán tiến hóa đa nhân tố và thuật toán tham lam ngẫu nhiên tìm được kết quả tối ưu trên nhiều bộ dữ liệu. Tuy nhiên, toán tử đột biến trong hướng tiếp cận này vẫn còn hạn chế khi luôn cố định số lần thay thế cạnh mới trên cá thể. Để khắc phục hạn chế trên, nghiên cứu đề xuất toán tử đột biến có khả năng thay đổi số lần thay thế cạnh mới trên cá thể trong mỗi lần thực hiện, cũng như có khả năng thay thế nhiều cạnh mới trên cá thể. Để chứng minh hiệu quả của đề xuất, nghiên cứu đã tiến hành thực nghiệm các thuật toán trên nhiều bộ dữ liệu khác nhau. Kết quả thực nghiệm đã chỉ ra tính hiệu quả của toán tử được đề xuất.