Với khả năng hiện nay, máy tính đã giúp con người giải quyết được rất nhiều bài toán khó mà trước kia thường bó tay. Mặc dù vậy vẫn còn một số lớn các bài toán thú vị nhưng chưa có thuật giải hợp lý để giải chúng. Trong số đó các bài toán tối ưu thường gặp trong thực tiễn.
Trước kia để giải những bài toàn tối ưu người ta thường dùng những phương pháp cổ điển như: leo đồi, mô phỏng luyện thép… Với những bài toán có không gian tìm kiếm nhỏ. Thì những phương pháp trên có thể giải quyết tốt. Nhưng với không gian tìm kiếm lớn, thì những phương pháp trên không hiệu quả. Vì vậy, điều kiện đòi hỏi chúng ta phải có những phương pháp mới để có thể giải quyết tốt những bài toán dạng trên. Ngày nay để giải bài toán tối ưu, chúng ta có thể dùng ”giải thuật di truyền” .
Áp dụng giải thuật di truyền vào bài toán sắp xếp thời khóa biểu
Vấn đề của bài toán khá phức tạp về mặt ràng buộc, nhưng phương pháp chia để trị vẫn là biện pháp hữu hiệu trong mọi vấn đề phức tạp. Ở đây cũng vậy, theo phân cấp các ràng buộc mà ta giải quyết bài toán xếp thời khóa biểu này thành hai giai đoạn khác nhau:
-
Giai đoạn 1: nhằm giải quyết thành phần ràng buộc ở mức lớp học, với các vấn đề cơ bản phức tạp của những đối tượng liên quan tới việc học của lớp. Khi đã có được kết quả cuối cùng là lịch học cho từng lớp một cách hoàn chỉnh, chúng sẽ được dùng làm thông tin cho giai đoạn sau.
-
Giai đoạn 2 : tổng hợp lại các ràng buộc còn lại và đã được đơn giản hóa trong giai đoạn trước. Kết quả của giai đoạn này chính là mục tiêu cuối cùng của bài toán. Đó là lịch học của các lớp trong một cơ sở.
Cả hai giai đoạn tuy có mục tiêu và dữ liệu khác nhau, nhưng về cách giải quyết có tính tương tự nhau, nên không khác gì nhiều khi áp dụng vào mô hình thuật giải di truyền.
Đồ án nghiên cứu Thuật toán di truyền và ứng dụng sắp xếp thời khóa biểu C# + Báo cáo của chúng mình tuy chưa được hoàn thiện, nhưng có báo cáo mô tả chi tiết thuật toán di truyền nên vẫn chia sẻ, các bạn download về để tham khảo và hoàn thiện thêm nhé!
THÔNG TIN TÁC GIẢ
Trần Thị Khuyên
Nguyễn Thị Quỳnh Nga
Nguồn: Sharecode.vn