Một cách tiếp cận thuật toán gen để giải bài toán phủ tập hợp

Bài toán phủ tập hợp (Set Covering Problem - SCP) là một mô hình toán học cho 11111011 ứng dụng quan trọng như lập lịch biểu [6], quy hoạch dịch vụ, phân tích dữ liệu logic, đơn giản hóa biểu thức Boolean [8]SCP là bài toán NP đầy đủ [4] nên việc xây dựng thuật toán tìm nghiệm tối ưu hay nghiệm xấp xỉ là rất khó khăn. Tuy nhiên cấu trúc các thể hiện của bài toán trong thế giới thực cung cấp thêm những thông tin ngữ cảnh cho phép giải quyết bài toán SCP kích thước khá lem (vài trăm dòng và vài triệu cột) với nghiệm đạt được sai khác so với nghiệm tối ưu chi khoảng 1% trong khoảng thời gian tính toán chấp nhận được [8]. Các phương pháp giải bài toán SCP trong thực tế dựa trên nhiều cách tiếp cận khác nhau và có thể phân loại thành các lớp như lớp thuật toán dựa trên lý thuyết quy hoạch tuyến tính, lớp các thuật toán heuristics và lớp các thuật toán branch-and-bound [7-13]. Dưới đây chúng ta sẽ đưa ra phát biểu hình thức của bài toán và đề xuất thuật toán dựa trên nguyên lý của thuật toán gen (GA) để giải bài toán SCP.