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. | TẠP CHÍ KHOA HỌC ĐẠI HỌC TÂY BẮC Phạm Đình Thành và nnk 2021 Khoa học Tự nhiên và Công nghệ 22 93 - 103 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 Phạm Đình Thành1 Mai Văn Tám1 Lưu Thị Xuân2 Nguyễn Hữu Cường1 Đặng Thị Vân Chi1 1Trường Đại học Tây Bắc 2Trường Cao đẳng Y Tế Sơn La 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. Từ khóa Thuật toán tiến hóa đa nhân tố cây khung phân cụm đường đi ngắn nhất tối ưu tổ hợp. 1. Giới thiệu quan trọng trong thực tiễn và nhận được Bài toán tìm cây khung có chi phí nhiều sự quan tâm nghiên cứu. nhỏ nhất Minimal-Cost Spanning Tree - Do CluSPT thuộc lớp bài toán NP-Khó 5 MCST trên đồ thị có trọng số là một trong nên các hướng tiếp cận thường sử dụng các các bài toán nổi tiếng trong lĩnh vực tối ưu thuật toán xấp xỉ. Trong những năm gần rời rạc cũng như trong khoa học máy tính. đây các thuật toán có ý tưởng bắt nguồn từ Bài toán MCST được ứng dụng trong nhiều tự nhiên được sử dụng rộng rãi để giải các lĩnh vực thực .
