Khảo sát các thuật giải Tabu Search cho bài toán xếp thời khoá biểu đại học

KHẢO SÁT CÁC THUẬT GIẢI TABU SEARCH CHO BÀI TOÁN XẾP THỜI KHOÁ BIỂU ĐẠI HỌC NGUYỄN TẤN TRẦN MINH KHANG (*) ĐẶNG THỊ THANH NGUYÊN (*) TRIỆU TRÁNG KHÔN (*) TRẦN THỊ HUỆ NƯƠNG (**) TÓM TẮT Bài toán xếp thời khoá biểu đại học là bài toán xuất phát từ nhu cầu rất cấp thiết của thực tế. Do thuộc lớp bài toán khó NP, bài toán hiện được quan tâm nghiên cứu và phát triển bởi rất nhiều nhà khoa học trên thế giới. Một trong những hướng tiếp cận hiệu quả nhất hiện nay là hướng tiếp cận sử dụng các metaheuristic. Trong đó, metaheuristic Tabu Search đã cho nhiều kết quả rất khả quan. Bài báo này sẽ khảo sát một số thuật giải Tabu Search tiêu biểu và cho hiệu quả cao đối với bài toán xếp thời khoá biểu đại học. ABSTRACT The prolem of university ranked schedule is the problem comes from the very urgent needs of the practice. Because of belonging to the hard NP that have attracted several researchers in the world. Metaheuristics are the most popular approaches nowadays for solving these problems. Tabu Search is one of metaheuristics that have given remarkable results. This paper investigates the most effective variant of Tabu Search for the university timetabling problem. 1. GIỚI THIỆU BÀI TOÁN Bài toán xếp thời khoá biểu cho trường đại học thuộc lớp các bài toán xếp thời khoá biểu cho giáo dục. Đây là lớp các bài toán rất thực tế, xuất hiện ở tất cả các trường phổ thông và đại học. Mục tiêu của bài toán là tìm cách xếp lịch học, lịch dạy cho các sinh viên (học sinh) và giáo viên vào các tiết học, các phòng học sao cho thoả một số ràng buộc nhất định. Yêu cầu chính của lớp bài toán này là xếp các tài nguyên (giáo viên, học sinh, phòng học, thiết bị, v.v.) vào các tiết học thích hợp sao cho thời khoá biểu thu được phải thoả một số ràng buộc nhất định [1] (chẳng hạn: một giáo viên không dạy hai nhóm lớp khác nhau tại cùng một thời điểm, một sinh viên không học hai nhóm lớp khác nhau tại cùng một thời điểm, v.v.). Trên thực tế, do sự đa dạng về nhu cầu và qui định của các trường, đã xuất hiện rất nhiều biến thể khác nhau của bài toán xếp thời khoá biểu. Dựa theo bài khảo sát của tác giả A. Schaerf [1] và bài báo cáo kĩ thuật của cuộc thi Xếp thời khoá biểu quốc tế 2007 (International Timetabling Competition 2007 – gọi tắt là ITC07) [2][3], có thể phân các bài toán xếp thời khoá biểu cho giáo dục thành ba nhóm chính: (*) Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên TP.HCM (**) Khoa Toán – Tin, Trường Đại học Khoa học Tự nhiên TP.HCM - Bài toán xếp thời khoá biểu cho trường phổ thông (high school timetabling): xếp lịch học hàng tuần cho các lớp và lịch dạy hàng tuần cho các giáo viên sao cho không có giáo viên nào phải dạy hai lớp tại cùng một thời điểm, và không có lớp nào học hai giáo viên tại cùng một thời điểm. - Bài toán xếp thời khoá biểu cho trường đại học (course timetabling), gồm có hai lớp bài toán con: + Bài toán xếp thời khoá biểu cho trường đại học dựa trên nhóm học phần (curriculum - based course timetabling): sinh viên đăng kí học sau khi thời khoá biểu đã được sắp, sự tránh đụng độ giữa các môn học được quy định bởi nhóm học phần (nhóm các môn học không được sắp trùng giờ nhau), các nhóm học phần này được trường quy định sẵn và không phụ thuộc vào kết quả đăng kí học của sinh viên. + Bài toán xếp thời khoá biểu cho trường đại học dựa trên lịch đăng kí của sinh viên (post enrolment – based course timetabling): sinh viên đăng kí môn mà mình muốn học, sau đó, trường sẽ dựa trên kết quả đăng kí này để xếp thời khoá biểu sao cho sinh viên đều có thể học được tất cả các môn mà mình đã đăng kí mà không bị đụng độ giờ học. - Bài toán xếp lịch thi (examination timetabling): tương tự như bài toán xếp thời khoá biểu cho trường đại học, nhưng bài toán này có một số điểm khác biệt, chẳng hạn như: xếp lịch thi sao cho thời gian kéo dài của lịch thi là ít nhất (trong khi độ dài của một thời khoá biểu cho bài toán xếp thời khoá biểu cho trường đại học là cố định, thường là một tuần), hai môn thi có thể dùng chung một phòng học tại cùng một thời điểm, hoặc một môn thi có thể tách ra thi ở hai phòng khác nhau tại cùng một thời điểm (bài toán xếp thời khoá biểu cho trường đại học thường không cho phép điều này). Bài toán xếp thời khoá biểu đại học nói riêng và bài toán xếp thời khoá biểu cho giáo dục nói chung đều thuộc lớp bài toán NP đầy đủ (là lớp bài toán mà cho đến nay, chưa tìm ra được phương pháp nào giải quyết được trong thời gian đa thức [1]). 2. GIỚI THIỆU THUẬT GIẢI TABU SEARCH Tabu Search là một trong những metaheuristic được áp dụng nhiều nhất cho các bài toán tối ưu tổ hợp khó. Trong phần này, chúng tôi sẽ giới thiệu sơ lược về các thành phần cơ bản nhất của thuật giải Tabu Search và cách hoạt động của nó. Ngoài các thành phần cơ bản này, thuật giải Tabu Search được áp dụng trong thực tế có rất nhiều biến thể, với rất nhiều chiến lược hiệu quả khác được bổ sung vào nhằm nâng cao khả năng tìm kiếm của thuật giải, độc giả quan tâm có thể xem chi tiết tại tài liệu của tác giả Fred Glover [4], người được xem là cha đẻ của thuật giải này [5]. Bài toán mà thuật giải Tabu Search giải quyết là bài toán tối ưu, mục tiêu của bài toán là tìm ra lời giải tốt nhất - lời giải mà tại đó, hàm mục tiêu của bài toán đạt giá trị cực tiểu. Hàm mục tiêu là hàm dùng để đo chi phí của một lời giải, lời giải có chi phí càng thấp thì càng tốt. Ý tưởng chính của thuật giải Tabu Search như sau: bắt nguồn từ một lời giải ban đầu (lời giải này gọi là lời giải khởi tạo, có thể được tạo thành từ nhiều phương pháp khác nhau, chẳng hạn như: phương pháp thuật giải tham lam, phương pháp khởi tạo ngẫu nhiên, v.v.), thuật giải Tabu Search sẽ thực hiện lặp đi lặp lại việc tìm kiếm trong miền không gian tìm kiếm của bài toán nhằm mục đích tìm ra lời giải tối ưu. Tại mỗi bước lặp của mình, thuật giải Tabu Search sẽ tìm kiếm và chỉ lựa ra một lời giải duy nhất để làm cơ sở cho bước lặp tiếp theo - đây chính là điểm khác biệt cơ bản nhất giữa thuật giải Tabu Search so với nhóm các thuật giải tiến hoá (như thuật giải di truyền, lập trình tiến hoá, v.v.). Ở nhóm các thuật giải tiến hoá, sau mỗi bước lặp, kết quả thu được là cả một tập các lời giải, trong khi ở Tabu Search, chỉ thu được một lời giải duy nhất. Tại mỗi bước lặp, Tabu Search sẽ lấy lời giải duy nhất thu được từ bước lặp trước làm lời giải hiện tại, thuật giải sẽ duyệt trong miền không gian láng giềng của lời giải hiện tại để chọn ra lời giải tốt nhất, lời giải này sẽ thay thế cho lời giải hiện tại ở bước lặp kế sau. Mỗi lời giải trong không gian láng giềng của lời giải hiện tại được gọi là một láng giềng của lời giải hiện tại. Sự tác động lên lời giải hiện tại để biến nó thành một lời giải láng giềng của nó gọi là một bước chuyển. Để tránh việc duyệt trở lại những lời giải đã từng được duyệt, thuật giải Tabu Search sử dụng một danh sách để lưu trữ một số bước chuyển đã từng được sử dụng, gọi là danh sách Tabu. Danh sách này sẽ chứa những bước chuyển đã được thực hiện trong một số bước lặp gần đây, các bước chuyển nằm trong danh sách Tabu được gọi là các bước chuyển Tabu. Các bước chuyển này sẽ bị cấm sử dụng lại chừng nào nó còn nằm trong danh sách Tabu. Một bước chuyển Tabu sẽ tồn tại trong danh sách Tabu trong một khoảng thời gian n bước lặp, sau đó, bước chuyển này sẽ được loại ra khỏi danh sách Tabu và trở về trạng thái bình thường (không bị cấm nữa), số n này được gọi là giá trị Tabu tenure của bước chuyển, giá trị n này có thể cố định cho tất cả các bước chuyển hoặc là một số được chọn ngẫu nhiên cho từng bước chuyển. Tuy nhiên, đôi khi một số bước chuyển dù bị cấm (bước chuyển Tabu) nhưng nó lại có khả năng cải tiến chất lượng của lời giải tốt nhất hiện nay, do đó, để tránh bỏ sót các bước chuyển tốt này, Tabu Search đưa ra một khái niệm nữa, đó là khái niệm tiêu chuẩn mong đợi (aspiration criteria). Cách áp dụng của tiêu chuẩn này như sau: nếu một bước chuyển Tabu bầt kì thoả được tiêu chuẩn mong đợi thì nó sẽ được loại ra khỏi danh sách Tabu ngay lập tức, cho dù giá trị Tabu tenure đi kèm có là bao nhiêu đi chăng nữa. Tiêu chuẩn mong đợi thường được dùng nhất là: nếu bước chuyển Tabu nào có thể làm cho lời giải hiện tại trở nên tốt hơn cả lời giải tốt nhất hiện nay thì bước chuyển Tabu đó sẽ được loại ra khỏi danh sách Tabu ngay lập tức. 3. CÁC THUẬT GIẢI TABU SEARCH CHO BÀI TOÁN XẾP THỜI KHOÁ BIỂU ĐẠI HỌC Với yêu cầu phức tạp của bài toán xếp thời khoá biểu cho đại học, việc thực hiện xếp thời khoá biểu bằng tay đòi hỏi tốn rất nhiều công sức và thời gian mà kết quả tìm được đôi khi lại không phù hợp với thực tế. Do thuộc lớp bài toán NP đầy đủ nên việc giải quyết bài toán bằng phương pháp vét cạn là hầu như không thể. Chính vì độ phức tạp của bài toán và nhu cầu cao xuất phát từ thực tế nên bài toán xếp thời khoá biểu đã nhận được mối quan tâm đáng kể của các nhà khoa học. Bài toán này lần đầu tiên được Gotlieb khởi xướng vào năm 1963 [6] và cho đến nay, đã có rất nhiều hướng tiếp cận được đưa ra [1]: Các kĩ thuật đầu tiên mà con người sử dụng để xếp thời khoá biểu dựa trên mô phỏng suy nghĩ của con người để giải quyết vấn đề. Những kĩ thuật đó gọi là heuristic trực tiếp (direct heuristic). Một ví dụ của dạng này là kĩ thuật ưu tiên xếp những bài giảng khó xếp nhất trước. Thời khoá biểu sẽ dần dần được hình thành sau mỗi bước xếp. Ngoài ra, người ta còn đưa bài toán xếp thời khoá biểu về bài toán tô màu đồ thị (graph coloring) Tiếp theo đó, những kĩ thuật khác cũng được áp dụng vào bài toán xếp thời khoá biểu như: lập trình ràng buộc (constraint programming), lập trình tuyến tính (linear programming), mạng phân luồng (network flow), v.v. Gần đây, hướng tiếp cận metaheuristic trở thành hướng tiếp cận khá phổ biến và được quan tâm nghiên cứu khá rộng rãi trong suốt các thập niên vừa qua. Nhóm các thuật giải Metaheuristics bao gồm: các thuật giải tiến hoá (Evolutionary Algorithm), thuật giải tôi luyện thép (Simulated Annealing), Tabu Search, thuật giải Đại Hồng Thủy (Great Deluge), v.v. Metaheuristics tỏ ra khá hiệu quả trong việc tìm ra lời giải cho các bài toán tối ưu, giúp giải quyết khá tốt nhiều bài toán khó với kích thước miền tìm kiếm rất lớn như bài toán xếp thời khoá biểu, trong đó Tabu Search được đánh giá khá cao và được sử dụng rất nhiều bởi các tác giả nghiên cứu bài toán xếp thời khoá biểu trên thế giới và đã thu được nhiều kết quả khả quan, chẳng hạn như: - Năm 2001: Marcone Jamilson Freitas Souza, Nelson Maculan, Luiz Satoru Ochi (xem tham khảo [15]) sử dụng kĩ thuật Tabu Search để giải quyết bài toán xếp thời khoá biểu cho trường trung học Escola Dom Silvério ở Mariana thuộc Brazil. Đầu tiên, nhóm các tác giả sử dụng thuật giải tham lam GRASP để tạo ra lời giải ban đầu (initial solution), sau đó Tabu Search được sử dụng để tìm lời giải tốt cho bài toán. - Năm 2003: Jean-François Cordeau, Brigitte Jaumard, Rodrigo Morales (xem tham khảo [11]) tham gia cuộc thi International Timetabling Competition 2002-2003 (gọi tắt là ITC2002, chi tiết cuộc thi được mô tả ở phần 3.2). Nhóm các tác giả đã sử dụng Tabu Search kết hợp với một số thủ tục Exchange Moves, Pertubation và Ejection Chain để giải quyết bài toán của cuộc thi. Kết quả nhóm được xếp hạng 2. - Năm 2003: Luca Di Gaspero và Andrea Schaerf (xem tham khảo [12]) tham gia cuộc thi International Timetabling Competition 2002-2003. Nhóm các tác giả chọn kĩ thuật Tabu Search làm trọng tâm, kết hợp với thuật giải leo đồi (Hill Climbing) và thủ tục Multi-Swap Shake để nâng cao chất lượng lời giải tìm được. Kết quả nhóm được xếp hạng 4. - Năm 2003: Halvard Arntzen và Arne Lokketangen (xem tham khảo [8]) tham gia cuộc thi International Timetabling Competition 2002-2003. Lời giải ban đầu được khởi tạo bằng thuật giải tham lam, sau đó Tabu Search được thực hiện. Cuối cùng thủ tục Ejection Chain được kích hoạt để hướng việc tìm kiếm đến một vùng không gian tìm kiếm mới. Kết quả nhóm được xếp hạng 5. - Năm 2003: Alexandre Dubourg, Benoît Laurent, Emmanuel Long, Benoît Salotti (xem tham khảo [13]) tham gia cuộc thi International Timetabling Competition 2002-2003. Nhóm tác giả sử dụng thuật giải tham lam để tạo ra lời giải ban đầu, sau đó sử dụng Tabu Search để cải tiến chất lượng lời giải. Kết quả nhóm được xếp hạng 6. - Năm 2003: Gustavo Toro, Victor Parada (xem tham khảo[14]) tham gia cuộc thi International Timetabling Competition 2002-2003. Nhóm các tác giả tạo lời giải ban đầu bằng thuật giải tham lam, sau đó Tabu Search với bộ nhớ ngắn hạn (Short-term memory) và bộ nhớ dài hạn (Long-term memory) được thực hiện. Cuối cùng chiến lượng tăng cường hoá (intensifying - hướng việc tìm kiếm đến vùng không gian chứa lời giải tối ưu cục bộ) và chiến lược đa dạng hoá (diversifying - hướng việc tìm kiếm tránh rơi vào vùng không gian chứa lời giải tối ưu cục bộ) được thực hiện. Kết quả nhóm được xếp hạng 7. - Năm 2007: Cagdas Hakan Aladag, Gulsum Hocaoglu (xem tham khảo [16]). Nhóm tác giả sử dụng Tabu Search để giải bài toán xếp thời khoá biểu của trường đại học Statistics Department of Hacettepe University (Thổ Nhĩ Kì) và thu được kết quả tốt: không vi phạm ràng buộc đụng độ nào. Tuy nhiên, hiệu quả của nhóm các thuật giải Metaheuristic còn phụ thuộc vào việc điều chỉnh các tham số của thuật giải, cách áp dụng thuật giải vào mô hình bài toán cụ thể. Thuật giải Tabu Search cũng không ngoại lệ, tính hiệu quả của thuật giải phụ thuộc vào yêu cầu cụ thể của bài toán, cách lựa chọn tập láng giềng, cách thiết kế phép chuyển, việc lựa chọn giá trị kích thước của Tabu list, v.v. Một thuật toán cụ thể có thể chạy tốt trên một số bài toán cụ thể và số bộ dữ liệu, nhưng lại không hiệu quả trên các bài toán biến thể khác. Hiện nay, nhìn chung vẫn chưa có một phương pháp nào có thể giải quyết trọn vẹn tất cả các biến thể của bài toán xếp thời khoá biểu cho giáo dục trên thế giới. Trong khuôn khổ bài báo này, chúng tôi tập trung khảo sát một số hướng tiếp cận nổi bật dựa trên thuật giải Tabu Search để giải quyết bài toán xếp thời khoá biểu cho trường đại học. 3.1. Khởi tạo lời giải ban đầu Một trong những cách thông dụng nhất để khởi tạo lời giải ban đầu là phương pháp dựa trên thuật giải tham lam, cụ thể là trong bài báo của mình, tác giả D.Costa [7] đã sử dụng cách sau: các bài giảng có ít cách gán tiết, gán phòng nhất sẽ được chọn để gán trước, khi đó, các tiết học, phòng học không gây ra bất kì đụng độ nào sẽ được ưu tiên gán cho bài giảng này, nếu không tồn tại tiết học, phòng học nào thoả yêu cầu trên thì mục tiêu sẽ được giảm đi một bậc: các tiết học, phòng học không gây ra bất kì đụng độ nào liên quan đến giáo viên và lớp học sẽ được ưu tiên gán cho các bài giảng này, nếu vẫn không tồn tại tiết học, phòng học nào thoả yêu cầu trên, mục tiêu sẽ lại được giảm đi một bậc nữa (tổng cộng có 6 bậc, chi tiết của từng bậc xin xem ở bài báo của tác giả D.Costa). Sau đó đã có nhiều tác giả khác cũng áp dụng phương pháp tương tự cho bước khởi tạo lời giải của mình, chẳng hạn như nhóm tác giả H. Arntzen [8], C. H. Aladag [16], G. Toro [14] và A. Dubourg [13]. Một phương pháp thông dụng khác nữa là phương pháp khởi tạo ngẫu nhiên: lời giải được khởi tạo một cách ngẫu nhiên bằng cách gán ngẫu nhiên các bài giảng cho các tiết học và các phòng học bất kì. Phương pháp này được sử dụng bởi các tác giả L. D. Gaspero và A.Schaerf [12], C. H. Aladag [16]. Vào năm 2001, nhóm tác giả Souza và các đồng sự [15] đã ứng dụng một phương pháp mới để khởi tạo lời giải ban đầu, ý tưởng của phương pháp này là kết hợp giữa thuật giải tham lam và phương pháp ngẫu nhiên, người sử dụng có thể điều chỉnh sự tương quan giữa mức độ ngẫu nhiên và “mức độ tham lam” trong thuật giải để tạo nên một lời giải khởi tạo có chất lượng khá tốt. Phương pháp này có tên là GRASP (Greedy Randomized Adaptive Search Procedure). Một cách làm khác là khởi tạo lời giải bằng phương pháp mạng phân luồng[11]. Ý tưởng của phương pháp này là: ứng với mỗi tiết học, ta có hai tập điểm, tập thứ nhất biểu diễn các bài giảng có thể gán cho tiết học đang xét, tập thứ hai biểu diễn các phòng học rảnh vào tiết đang xét, mục tiêu là sử dụng các thuật giải cho mạng phân luồng để tạo nên một lời giải đầy đủ (tất cả các bài giảng đều phải được gán tiết, gán phòng). 3.2. Chọn tập láng giềng Có nhiều cách khác nhau để chọn tập láng giềng trong quá trình xét duyệt, tùy thuộc vào tính chất và mục tiêu của bài toán, chẳng hạn như: tùy thuộc vào kích thước của miền láng giềng, vào chiến lược chọn phép chuyển của thuật giải. Trong hướng tiếp cận của mình, tác giả D. Costa [7] xét toàn bộ các phần tử thoả tất cả ràng buộc cứng trong tập láng giềng và chọn phần tử tốt nhất. Tuy nhiên, cách chọn trên đôi khi không hiệu quả khi kích thước miền láng giềng quá lớn. Chẳng hạn như trong bài báo của O.R. Doria và các đồng sự ở trường đại học Napier, Scotland [10], tác giả thực hiện thử nghiệm Tabu Search trên các bộ dữ liệu thật của cuộc thi Xếp lịch Quốc tế ITC2007 với hai loại phép chuyển khác nhau (được đề cập ở phần sau). Nhóm tác giải chọn cả hai tập láng giềng thu được từ hai loại phép chuyển: phép chuyển đơn và phép hoán chuyển cùng một lúc, do đó, không gian láng giềng khá lớn. Khi đó, tại mỗi bước lặp, không phải tất cả các phần tử láng giềng đều được chọn, mà mỗi phần tử sẽ được chọn với xác suất cố định là 0.1, từ đó lấy ra phần tử tốt nhất trong số các phần tử được chọn để thực hiện cho bước lặp kế sau. Thay vì duyệt miền láng giềng và chọn ngay phép chuyển tốt nhất. H. Arntzen [8] đề ra một cách làm khác như sau: nếu phép chuyển tốt nhất trong miền láng giềng có thể cải thiện được chất lượng lời giải tốt nhất hiện tại thì phép chuyển này sẽ được chọn, nếu không, phép chuyển này sẽ được chọn với xác suất 0.5, nếu sau phép thử xác suất mà phép chuyển này không được chọn thì sẽ chọn phép thử tốt thứ hai với xác suất 0.5, cứ thế cho đến khi chọn được một phép chuyển để thực hiện cho bước lặp kế sau. G. Toro [14] lại đề ra một chiến lược khác: chỉ xét một phần của tập láng giềng do kích thước quá lớn của nó. Nếu lời giải khởi tạo không thoả tất các ràng buộc cứng, tại mỗi bước lặp, sẽ có một danh sách L gồm các bài giảng bị vi phạm ràng buộc cứng, xác suất phép chuyển được chọn liên quan đến các bài giảng thuộc danh sách L này là 80%, 20% còn lại là chọn ngẫu nhiên. Khi lời giải đang xét không còn vi phạm các ràng buộc cứng nữa, danh sách L sẽ bị hủy, thay vào đó, tại mỗi bước lặp, ta chọn ngẫu nhiên 10 bài giảng, sau đó xét các phép chuyển có liên quan đến các bài giảng này. 3.3. Phép chuyển Hầu hết các tác giả áp dụng Tabu Search đều sử dụng các loại phép chuyển tương tự nhau. Trong đó có hai loại phép chuyển thông dụng nhất: - Phép chuyển đơn: chuyển một bài giảng đến một tiết học mới, một phòng học mới [7] [8] [9] [10] [11] [12] [13] [15]. - Phép hoán chuyển: hoán đổi tiết học, phòng học của hai bài giảng cho nhau [11] [12] [13] [16]. Trong đó, D. Costa [7] chỉ sử dụng các phép chuyển có tác động lên các bài giảng bị đụng độ. Bài giảng bị đụng độ là bài giảng vi phạm ít nhất một ràng buộc. Phép chuyển tác giả áp dụng là dạng phép chuyển đơn. 3.4. Danh sách Tabu D.Costa [7] xét hai danh sách Tabu T1 và T2, khi một phép chuyển thực hiện di chuyển bài giảng A từ tiết học p1 sang tiết học p2 được chọn, phép chuyển này sẽ được đưa vào danh sách Tabu T1 và T2 như sau: T1 lưu bài giảng A, T2 lưu cặp bài giảng A và tiết học p1, có nghĩa là bài giảng A sẽ không được di chuyển cho đến khi phép chuyển này bị loại ra khỏi T1, và bài giảng A cũng sẽ không được gán trở lại cho tiết học p1 cho đến khi phép chuyển này bị loại khỏi T2. Danh sách Tabu được sử dụng bởi O.R. Dorial [10] cấm bài giảng A di chuyển trở về l