Chương 1: Trình bày tổng quan về đề tài của luận văn, phát biểu bài toán, động lực, các thách thức và đóng góp của luận văn. - Chương 2: Trình bày chi tiết về bài toán, cơ sở lý thuyết quan trọng và một số nghiên cứu liên quan đến đề tài của luận văn. - Chương 3: Mô tả chi tiết về hệ thống xếp lịch thi sử dụng Hyper-Heuristic và Học tăng cường. - Chương 4: Cài đặt hệ thống, thử nghiệm và đánh giá bộ dữ liệu ITC2007 và dữ liệu xếp lịch thi của Trường Đại học Công nghệ Đồng Nai.
- Chương 5: Kết luận. Cơ Sở Lý Thuyết Và Các Công Trình Nghiên Cứu Liên Quan 2.1 Giới thiệu Chương này giới thiệu về cơ sở lý thuyết một cách ngắn gọn của các phương pháp tiếp cận Hyper-Heuristic được sử dụng trong luận văn. Đầu tiên, học viên sẽ giới thiệu và đánh giá chi tiết các tài liệu liên quan đến thuật toán Heuristic, Meta-Heuristic, Hyper-Heuristic và Reinforcement Learning. Sau đó, đối với các vấn đề về xếp lịch thi, học viên sẽ đi tìm hiểu tổng quan chi tiết về các phương pháp nghiên cứu trước đây cũng như phân tích các công trình nghiên cứu liên quan.
Nội dung chương sẽ được chia thành hai phần: Phần đầu nói về một số cơ sở lý thuyết về Heuristic, Meta-Heuristic, Hyper-Heuristic, tổng quan về bài toán xếp lịch cũng như định nghĩa về cách tiếp cận Reinforcement Learning. Phần thứ hai sẽ trình bày tổng quan các công trình nghiên cứu liên quan, từ đó tạo tiền đề cho việc xây dựng mô hình xếp lịch thi.2 Một số cơ sở lý thuyết 2.1 Heuristic Khi gặp một bài toán thì việc tìm ra một giải pháp tối ưu toàn cục được gọi là cách tiếp cận chính xác (exact approach). Phương pháp này luôn cho ra một kết quả tối ưu toàn cục nhưng có thể sẽ mất nhiều thời gian để thực thi, đặc biệt là các bài toán thực tế khi có không gian tìm kiếm lớn và nhiều ràng buộc. Để đảm bảo tính tối ưu, các phương pháp tiếp cận chính xác cần khám phá các giải pháp trong một không gian các giải pháp với thời gian chấp nhận được.
Để giảm thiểu thời gian thực thi, thuật ngữ Heuristic được ra đời. Các phương pháp tiếp cận Heuristic có thể tìm ra các giải pháp tốt trong một khoảng thời gian ngắn. Tuy nhiên, các giải pháp được tìm ra không bắt buộc phải tối ưu, nhưng thường thỏa mãn đối với từng yêu cầu cụ thể. Các phương pháp tiếp cận theo phương pháp Heuristic thường nhanh hơn nhiều so với các phương pháp tiếp cận chính xác và có thể là phương án 6 thay thế duy nhất khi không gian tìm kiếm lớn, khi đó việc tìm kiếm ra phương pháp tối ưu toàn cục là không thể kiểm soát được khi sử dụng các phương pháp tiếp cận chính xác.
Vì lý do này, Heuristic rất phổ biến và đã được nghiên cứu rộng rãi bởi cộng đồng tối ưu hóa trong vài thập kỷ. Hai cách chính để thực hiện tìm kiếm bằng cách sử dụng phương pháp Heuristic có thể được chia thành phương pháp Heuristic xây dựng (constructive Heuristics) và phương pháp Heuristic nhiễu loạn (perturbative Heuristic): - Heuristic xây dựng là phương pháp xây dựng giải pháp từng yếu tố một cho đến khi xây dựng xong giải pháp hoàn chỉnh. Các cách tiếp cận dạng này thường có thể đưa ra các giải pháp tốt hơn nhiều so với các cách tiếp cận ngẫu nhiên, nhưng có thể sẽ bị xung đột khi tìm ra giải pháp gần với các cách tiếp cận chính xác hoặc các cách tiếp cận Heuristic nhiễu loạn. Một lợi thế của phương pháp Heuristic xây dựng là chúng thường có thể tìm ra giải pháp rất nhanh chóng.
Chính vì điều này, chúng thường được sử dụng để xây dựng một giải pháp khả thi ban đầu cho các phương pháp tiếp cận nhiễu loạn được cải thiện sau này. Một ví dụ về phương pháp Heuristic mang tính xây dựng cho bài toán tìm đường đi của người giao hàng (TSP – Traveling Salesman Problem) là tìm kiếm láng giềng gần nhất (Nearest Neighbor). Phương pháp này sẽ truy cập vào nút gần nhất ở mỗi bước cho đến khi tất cả các nút đã được truy cập. - Heuristic nhiễu loạn là một phương pháp sửa đổi một giải pháp hiện có để tạo ra một giải pháp mới.
Đây là loại Heuristic phổ biến nhất trong nghiên cứu tối ưu hóa. Việc kết hợp nhiều Heuristic nhiễu loạn thành một nhóm Heuristic là điều bình thường vì điều này đã cho thấy kết quả tốt hơn so với việc chỉ sử dụng một Heuristic duy nhất trong toàn bộ quá trình tìm kiếm [1]. Một khía cạnh quan trọng của Heuristic nhiễu loạn là mức độ nào thì nên thay đổi giải pháp, khía cạnh này được giải quyết bằng khái niệm vùng lân cận. Vùng lân cận của một giải pháp được định nghĩa là tất cả các giải pháp khả thi có thể khi sử dụng một trong các phương pháp Heuristic.
Để tránh bị mắc kẹt trong điểm tối ưu cục bộ, nếu mở rộng vùng lân cận thì sẽ có lợi hơn. Có thể đạt được một vùng lân cận rộng lớn bằng cách kết hợp tốt giữa đa dạng hóa (diversification) và tăng cường (intensification) trong phương pháp Heuristic. 7 Đa dạng hóa giúp thay đổi giải pháp, ngay cả khi nó dẫn đến giá trị khách quan kém hơn, để thoát khỏi điểm tối ưu cục bộ. Mặt khác, việc tăng cường giúp tìm ra các giải pháp nâng cao và cải thiện giá trị khách quan của giải pháp.2 Meta-Heuristic Thuật toán Meta-Heuristic (MH) còn được gọi là phương pháp Heuristic cao cấp để giải các bài toán tìm kiếm hay bài toán tối ưu với chi phí tính toán hợp lý.
Nói cách khác, MH là một tập hợp các chiến lược thông minh để nâng cao hiệu quả của các quy trình heuristic (heuristic procedures). Nó đã thành công đáng kể trong việc giải các bài toán tối ưu hóa tổ hợp phức tạp, đặc biệt là đối với các bài toán NP-khó (NP-Hard). Thuật toán MH là một minh chứng khác trong thế giới tự nhiên, đó là một phương pháp liên quan chặt chẽ đến kiến thức về sinh học, vật lý, toán học và trí tuệ nhân tạo. Thuật toán này có thể tránh các vấn đề phát sinh khi sử dụng thuật toán Heuristic truyền thống như hiện tượng tối ưu cục bộ hoặc vấn đề tạo ra một số lượng giải pháp hạn chế.
Nó được sử dụng để hướng dẫn thuật toán Heuristic truyền thống nhằm tối ưu hóa không gian tìm kiếm và chiến lược tìm kiếm để có được giải pháp tốt hơn. Với sự phát triển không ngừng của các công nghệ liên quan đến trí tuệ nhân tạo, các thuật toán MH không ngừng được cải tiến và tối ưu hóa. Hay nói cách khác, MH là một khung thuật toán không phụ thuộc vào vấn đề cấp cao, cung cấp một tập hợp các hướng dẫn hoặc chiến lược để phát triển các thuật toán tối ưu hóa Heuristic [2], nhằm mục đích tìm kiếm lời giải trong không gian tìm kiếm các giải pháp. Chúng đưa ra một số giả định về các vấn đề tối ưu hóa đang được giải quyết và do đó có thể được coi là các phương pháp tiếp cận độc lập với vấn đề, điều này có nghĩa là chúng có thể được áp dụng cho một loạt các vấn đề khác nhau.
Các MH được sử dụng rộng rãi nhất được thiết kế cho các phương pháp Heuristic nhiễu loạn và bao gồm các thuật toán như: - Luyện kim (Simulated Annealing - SA); - Tìm kiếm Tabu (Tabu Search - TS); - Tìm kiếm vùng lân cận lớn thích ứng (ALNS); 8 - Thuật toán di truyền (Genetic Algorithms - GA). Ngoài ra còn tồn tại các MH xây dựng như Lấy mẫu (Sampling) và Tìm kiếm theo tia (Beam Search - BS) cho phép các Heuristic xây dựng tìm thấy kết quả tốt hơn nhiều so với khả năng tìm kiếm mà không có MH hỗ trợ. Tương tự như các thuật toán Heuristic, nghiên cứu [3] đã xác định sự khác biệt giữa các phương pháp tối ưu hóa truyền thống và các thuật toán MH như sau: - Thuật toán MH thoải mái hơn trong các ràng buộc của bài toán tối ưu hóa; - Các phương pháp tối ưu hóa truyền thống được định hướng và chú ý nhiều hơn đến tính tối ưu của lý thuyết, trong khi thuật toán MH tập trung nhiều hơn vào hiệu quả của tính toán; - Các phương pháp tối ưu hóa truyền thống (phương pháp chính xác) không thể đảm bảo rằng thuật toán sẽ đưa ra giải pháp cho mọi vấn đề, tuy nhiên thuật toán MH có thể đạt được điều này; - Các phương pháp tối ưu hóa truyền thống dựa trên toán học chính xác, vì vậy dữ liệu chính xác được yêu cầu nghiêm ngặt, nhưng thuật toán MH thoải mái hơn về chất lượng của dữ liệu.3 Hyper-Heuristic Thuật ngữ Hyper-Heuristic (HH) lần đầu tiên được sử dụng trong bối cảnh tối ưu hóa tổ hợp bởi tác giả Cowling [3] và được mô tả là “phương pháp Heuristic để lựa chọn phương pháp Heuristic”. Tác giả Burke và cộng sự [5] sau đó đã mở rộng định nghĩa của HH thành “một phương pháp tìm kiếm hoặc cơ chế học tập để lựa chọn hoặc tạo ra Heuristic để giải quyết các vấn đề tìm kiếm tính toán”.
Ý tưởng cơ bản của HH là một khái niệm để phát triển một thuật toán chung chung hơn so với các phương pháp MH thường yêu cầu điều chỉnh tham số dựa trên kinh nghiệm chuyên sâu để giải quyết các miền vấn đề khác nhau. Trong MH, kiến thức về miền vấn đề (problem domain) là cần thiết để điều chỉnh tham số dựa trên thực nghiệm. Để đối phó với vấn đề này, HH đưa ra ý tưởng làm việc ở cấp độ cao hơn, tức là không gian tìm kiếm Heuristic cấp độ thấp thay vì trực tiếp đến không gian tìm kiếm giải pháp, nâng không 9 gian tìm kiếm nhằm mục đích làm cho HH trở nên chung chung hơn và hoạt động tốt trên các miền vấn đề chéo (cross problem domain). Tương tự như Heuristic và MH, HH là một phương pháp tiếp cận Heuristic không chắc chắn có thể tìm ra giải pháp tối ưu toàn cục.
Một quá trình lặp đi lặp lại việc hướng dẫn các Heuristic cấp thấp (Low-level Heuristic - LLH) bằng cách kết hợp các khái niệm khác nhau một cách thông minh, để khám phá và khai thác không gian tìm kiếm bằng cách sử dụng các chiến lược học tập để cấu trúc thông tin nhằm tìm ra các giải pháp gần tối ưu (near-optimal). Hyper-Heuristic framework [3]. Khung HH (HH Framework) cơ bản được thể hiện trong Hình 2.1 được đề xuất trong [3]. Phần chính của khung HH là một rào cản miền (Domain barrier).
Nó làm cho HH không có thông tin về miền mà nó đang hoạt động.