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<br /> CHO BÀI TOÁN XẾP THỜI KHOÁ BIỂU ĐẠI HỌC<br /> <br /> NGUYỄN TẤN TRẦN MINH KHANG (*)<br /> ĐẶNG THỊ THANH NGUYÊN (*)<br /> TRIỆU TRÁNG KHÔN (*)<br /> TRẦN THỊ HUỆ NƯƠNG (**)<br /> <br /> TÓM TẮT<br /> <br /> 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<br /> 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<br /> 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<br /> nay là hướng tiếp cận sử dụng các metaheuristic. Trong đó, metaheuristic Tabu Search đã<br /> 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<br /> 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.<br /> <br /> ABSTRACT<br /> <br /> The prolem of university ranked schedule is the problem comes from the very urgent<br /> needs of the practice. Because of belonging to the hard NP that have attracted several<br /> researchers in the world. Metaheuristics are the most popular approaches nowadays for<br /> solving these problems. Tabu Search is one of metaheuristics that have given remarkable<br /> results. This paper investigates the most effective variant of Tabu Search for the university<br /> timetabling problem.<br /> <br /> 1. GIỚI THIỆU BÀI TOÁN<br /> <br /> 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á<br /> 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<br /> 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<br /> 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.<br /> 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,<br /> 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<br /> 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<br /> 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.).<br /> 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<br /> 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<br /> [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<br /> 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<br /> khoá biểu cho giáo dục thành ba nhóm chính:<br /> <br /> <br /> <br /> <br /> (*)<br /> Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên TP.HCM<br /> (**)<br /> Khoa Toán – Tin, Trường Đại học Khoa học Tự nhiên TP.HCM<br />  - Bài toán xếp thời khoá biểu cho trường phổ thông (high school timetabling): xếp lịch<br /> 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<br /> 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<br /> một thời điểm.<br /> <br /> - 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<br /> bài toán con:<br /> <br /> + 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<br /> - based course timetabling): sinh viên đăng kí học sau khi thời khoá biểu đã được sắp, sự<br /> 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<br /> 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<br /> phụ thuộc vào kết quả đăng kí học của sinh viên.<br /> <br /> + 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<br /> (post enrolment – based course timetabling): sinh viên đăng kí môn mà mình muốn học, sau<br /> đó, 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ể<br /> học được tất cả các môn mà mình đã đăng kí mà không bị đụng độ giờ học.<br /> <br /> - Bài toán xếp lịch thi (examination timetabling): tương tự như bài toán xếp thời khoá<br /> 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<br /> 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á<br /> 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<br /> 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ể<br /> 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<br /> trường đại học thường không cho phép điều này).<br /> <br /> 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<br /> 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<br /> được phương pháp nào giải quyết được trong thời gian đa thức [1]).<br /> <br /> 2. GIỚI THIỆU THUẬT GIẢI TABU SEARCH<br /> <br /> Tabu Search là một trong những metaheuristic được áp dụng nhiều nhất cho các bài<br /> 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ơ<br /> 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<br /> 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<br /> 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,<br /> độ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<br /> là cha đẻ của thuật giải này [5].<br /> <br /> 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<br /> 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.<br /> 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ì<br /> càng tốt.<br /> <br /> Ý 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<br /> (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,<br /> 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.),<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> Search, chỉ thu được một lời giải duy nhất.<br /> <br /> 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<br /> 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 để<br /> 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<br /> 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<br /> 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à<br /> một bước chuyển.<br /> <br /> Để 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> đó, 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<br /> (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ó<br /> 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<br /> chuyển.<br /> <br /> 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<br /> 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<br /> 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<br /> (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<br /> 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,<br /> 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<br /> đượ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<br /> 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<br /> ngay lập tức.<br /> <br /> 3. CÁC THUẬT GIẢI TABU SEARCH CHO BÀI TOÁN XẾP THỜI KHOÁ BIỂU<br /> ĐẠI HỌC<br /> <br /> 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<br /> 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<br /> 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<br /> 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à<br /> 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<br /> đá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<br /> 1963 [6] và cho đến nay, đã có rất nhiều hướng tiếp cận được đưa ra [1]:<br /> <br /> 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<br /> 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<br /> (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<br /> 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<br /> 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)<br />  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<br /> như: lập trình ràng buộc (constraint programming), lập trình tuyến tính (linear<br /> programming), mạng phân luồng (network flow), v.v.<br /> <br /> 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<br /> 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<br /> Metaheuristics bao gồm: các thuật giải tiến hoá (Evolutionary Algorithm), thuật giải tôi luyện<br /> thép (Simulated Annealing), Tabu Search, thuật giải Đại Hồng Thủy (Great Deluge), v.v.<br /> 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<br /> 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<br /> 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<br /> 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ả<br /> quan, chẳng hạn như:<br /> <br /> - Năm 2001: Marcone Jamilson Freitas Souza, Nelson Maculan, Luiz Satoru Ochi<br /> (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<br /> cho trường trung học Escola Dom Silvério ở Mariana thuộc Brazil. Đầu tiên, nhóm các tác giả<br /> sử dụng thuật giải tham lam GRASP để tạo ra lời giải ban đầu (initial solution), sau đó Tabu<br /> Search được sử dụng để tìm lời giải tốt cho bài toán.<br /> <br /> - Năm 2003: Jean-François Cordeau, Brigitte Jaumard, Rodrigo Morales (xem tham<br /> khảo [11]) tham gia cuộc thi International Timetabling Competition 2002-2003 (gọi tắt là<br /> 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<br /> kết hợp với một số thủ tục Exchange Moves, Pertubation và Ejection Chain để giải quyết<br /> bài toán của cuộc thi. Kết quả nhóm được xếp hạng 2.<br /> <br /> - Năm 2003: Luca Di Gaspero và Andrea Schaerf (xem tham khảo [12]) tham gia cuộc<br /> thi International Timetabling Competition 2002-2003. Nhóm các tác giả chọn kĩ thuật Tabu<br /> 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<br /> 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.<br /> <br /> - Năm 2003: Halvard Arntzen và Arne Lokketangen (xem tham khảo [8]) tham gia<br /> cuộc thi International Timetabling Competition 2002-2003. Lời giải ban đầu được khởi tạo<br /> bằng thuật giải tham lam, sau đó Tabu Search được thực hiện. Cuối cùng thủ tục Ejection<br /> 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<br /> quả nhóm được xếp hạng 5.<br /> <br /> - Năm 2003: Alexandre Dubourg, Benoît Laurent, Emmanuel Long, Benoît Salotti<br /> (xem tham khảo [13]) tham gia cuộc thi International Timetabling Competition 2002-2003.<br /> 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<br /> Search để cải tiến chất lượng lời giải. Kết quả nhóm được xếp hạng 6.<br /> <br /> - Năm 2003: Gustavo Toro, Victor Parada (xem tham khảo[14]) tham gia cuộc thi<br /> International Timetabling Competition 2002-2003. Nhóm các tác giả tạo lời giải ban đầu<br /> bằng thuật giải tham lam, sau đó Tabu Search với bộ nhớ ngắn hạn (Short-term memory) và<br /> 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á<br /> (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à<br /> 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<br /> 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.<br />  - Năm 2007: Cagdas Hakan Aladag, Gulsum Hocaoglu (xem tham khảo [16]). Nhóm<br /> 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<br /> Department of Hacettepe University (Thổ Nhĩ Kì) và thu được kết quả tốt: không vi phạm<br /> ràng buộc đụng độ nào.<br /> <br /> 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<br /> đ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ể.<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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,<br /> 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 để<br /> giải quyết bài toán xếp thời khoá biểu cho trường đại học.<br /> <br /> 3.1. Khởi tạo lời giải ban đầu<br /> <br /> 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<br /> 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<br /> 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 đó,<br /> 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<br /> 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<br /> 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à<br /> 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<br /> 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<br /> 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<br /> 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ả<br /> H. Arntzen [8], C. H. Aladag [16], G. Toro [14] và A. Dubourg [13].<br /> <br /> 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<br /> đượ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<br /> 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à<br /> A.Schaerf [12], C. H. Aladag [16].<br /> <br /> Vào năm 2001, nhóm tác giả Souza và các đồng sự [15] đã ứng dụng một phương<br /> 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<br /> 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<br /> 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ó<br /> chất lượng khá tốt. Phương pháp này có tên là GRASP (Greedy Randomized Adaptive Search<br /> Procedure).<br /> <br /> 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]. Ý<br /> 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<br /> 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<br /> 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<br /> đầy đủ (tất cả các bài giảng đều phải được gán tiết, gán phòng).<br /> 3.2. Chọn tập láng giềng<br /> <br /> 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<br /> 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<br /> láng giềng, vào chiến lược chọn phép chuyển của thuật giải.<br /> <br /> 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<br /> 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<br /> đô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<br /> 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ử<br /> 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<br /> 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<br /> 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,<br /> 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ử<br /> 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<br /> 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.<br /> <br /> 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] đề<br /> 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<br /> 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,<br /> 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<br /> 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<br /> chọn được một phép chuyển để thực hiện cho bước lặp kế sau.<br /> <br /> 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<br /> 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<br /> 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<br /> 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à<br /> 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<br /> 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<br /> phép chuyển có liên quan đến các bài giảng này.<br /> <br /> 3.3. Phép chuyển<br /> <br /> 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ự<br /> nhau. Trong đó có hai loại phép chuyển thông dụng nhất:<br /> - 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<br /> [7] [8] [9] [10] [11] [12] [13] [15].<br /> - 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]<br /> [12] [13] [16].<br /> 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ị<br /> đụ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<br /> giả áp dụng là dạng phép chuyển đơn.<br /> <br /> 3.4. Danh sách Tabu<br /> <br /> 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<br /> 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<br /> 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ó<br /> 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,<br /> 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ị<br /> loại khỏi T2.<br /> <br /> 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ề<br /> lại tiết học cũ mà nó từng được gán cho đến khi bước chuyển được loại khỏi danh sách Tabu.<br /> Giá trị Tabu tenure được chọn cố định và được tính bằng tổng số bài giảng chia cho một hằng<br /> số k = 100.<br /> <br /> H. Arntzen [8] xét danh sách Tabu sau đối với phép chuyển đơn: lưu lại ngày mà bài<br /> giảng đã từng được xếp vào, nghĩa là khi phép chuyển đơn chuyển bài giảng A từ tiết học p1<br /> sang tiết học p2, cặp (bài giảng A, ngày d) sẽ được lưu vào danh sách Tabu (ngày d là ngày<br /> mà tiết học p1 thuộc về). Khi đó, bài giảng A sẽ bị cấm gán trở lại vào bất kì tiết nào của ngày<br /> d cho đến khi cặp (A,d) bị loại ra khỏi danh sách Tabu. Danh sách Tabu này khác so với danh<br /> sách Tabu cho phép chuyển đơn thường dùng ở trên, thay vì cấm quay trở lại tiết cũ thì nó<br /> cấm quay trở lại luôn cả ngày cũ. Giá trị Tabu tenure TE trong [8] được tính như sau:<br /> <br /> - Đặt v0, vc, vb là giá trị hàm mục tiêu của lời giải khởi tạo, lời giải hiện tại và lời giải<br /> tốt nhất hiện tại.<br /> - Các giá trị trung gian Tp, Td được tính như sau:<br /> <br />  30(vc  vb ) <br /> Tp   <br />  v 0  vb  1 <br /> Td  min( 2Tb , Tb  T p ) với Tb là một số nguyên được chọn trong đoạn [5,9].<br /> - Giá trị Tabu tenure TE khi đó sẽ là: TE = Td + r, với r là một số nguyên trong đoạn<br /> [0,3].<br /> Tác giả R. A.Valdes [9] lại tính giá trị Tabu tenure theo phương pháp sau:<br /> Gọi Tb là giá trị tabu tenure cơ bản, Tmin , Tmax là giá trị ngưỡng min, max mà của giá trị Tabu<br /> tenure động Td mà ta cần tính, ta có:<br /> Tb  Toå ng soá cuï m cuû a taá t caû caù c phaâ n coâ ng<br /> Tmin  0.25Tb và Tmax  2Tb .<br /> Khi đó, giá trị Tabu tenure cuối cùng Td là một số được chọn ngẫu nhiên trong đoạn [Tmin,<br /> Tmax]<br /> <br /> 3.5. Tiêu chuẩn mong đợi<br /> <br /> Hầu hết tất cả các tác giả đều sử dụng tiêu chuẩn mong đợi sau: nếu một phép chuyển<br /> Tabu có thể tạo ra một lời giải tốt hơn lời giải tốt nhất hiện tại thì phép chuyển này sẽ được<br /> loại ra khỏi danh sách Tabu ngay lập tức.<br /> <br /> Tuy nhiên, D.Costa [7] đưa ra một cách tiếp cận khác: tiêu chuẩn mong đợi sẽ gồm<br /> hai tiêu chuẩn khác nhau, tiêu chuẩn thứ nhất chỉ đánh giá dựa trên ba ràng buộc đầu tiên (3<br /> ràng buộc có trọng số cao nhất), tiêu chuẩn thứ hai đánh giá dựa trên tất cả các ràng buộc.<br /> Tiêu chuẩn thứ nhất có độ ưu tiên cao hơn, nếu tiêu chuẩn này không thoả thì mới sử dụng<br /> đến tiêu chuẩn thứ hai.<br /> <br /> 3.6. Các chiến lược bổ sung<br /> <br /> Ngoài các thành phần tìm kiếm cơ bản, các tác giả còn đưa ra thêm các chiến lược bổ<br /> sung khác nhằm nâng cao chất lượng tìm kiếm. Chẳng hạn như chiến lược đa dạng hoá (để<br /> giúp việc tìm kiếm tìm đến được những miền không gian tìm kiếm mới) và tăng cường hoá<br /> (tập trung tìm kiếm sâu hơn ở những vùng không gian tìm kiếm có triển vọng chứa lời giải tối<br /> ưu).<br /> <br /> Tác giả D.Costa [7] đưa chiến lược đa dạng hoá bằng cách thay đổi trọng số của ba<br /> ràng buộc đầu tiên (ba ràng buộc có trọng số cao nhất) trong suốt quá trình tìm kiếm, từ đó<br /> giúp việc tìm kiếm không bị tập trung vào một miền không gian cố định. Quy tắc thay đổi<br /> trọng số như sau: cứ sau k bước lặp liên tiếp mà các lời giải thu được không được cải thiện<br /> mặc dù ba ràng buộc đầu tiên không hề bị vi phạm thì trọng số của các ràng buộc này sẽ được<br /> giảm đi.<br /> <br /> Tác giả H. Arntzen [8] lại áp dụng một chiến lược đa dạng hoá khác: Ghi lại thông tin<br /> về tần số di chuyển của mỗi bài giảng. Tần số này là một tần số có trọng số, nghĩa là các bài<br /> giảng được di chuyển trong thời gian càng gần với hiện tại thì giá trị tần số đi kèm với nó<br /> càng tăng cao. Cụ thể như sau: tại bước khởi tạo, đặt p = 0.01, cứ sau mỗi bước lặp, p được<br /> cập nhật: p = 101%p. Khi đó, gọi F là giá trị tần số đi kèm với bài giảng l, mỗi khi bài giảng l<br /> được di chuyển, F được cập nhật như sau: F = F + p. Tần số này giúp làm tăng độ đa dạng hoá<br /> của quá trình tìm kiếm bằng cách: bài giảng có tần số di chuyển thấp hơn thì sẽ được ưu tiên<br /> chọn hơn. Ngoài ra, tác giả còn sử dụng một loại phép chuyển mới gọi là phép chuyển theo<br /> chuỗi (ejection chain): các bài giảng được đẩy dần ra cho đến khi thu được một lời giải tốt<br /> hơn lời giải hiện tại. Ví dụ như: chọn một bài giảng A để bắt đầu, ta sẽ đẩy bài giảng A vào<br /> tiết học của bài giảng B, rồi đẩy bài giảng B vào tiết học của bài giảng C, việc đẩy này sẽ<br /> dừng sau một bước lặp cố định, nếu lời giải mới thu được tốt hơn lời giải hiện tại thì chọn lời<br /> giải mới, nếu không, quay trở lại từ đầu và thực hiện lại quy trình đẩy như trên (với các bài<br /> giảng khác). Cách làm này trong một số trường hợp có thể tạo ra những lời giải rất tốt mà các<br /> bước chuyển thông thường của Tabu Search không thể tạo ra được.<br /> <br /> J. F. Cordeau [11] và các đồng sự cũng áp dụng chiến lược đa dạng hoá tương tự như<br /> của tác giả D.Costa [7] : trọng số của các ràng buộc cứng thay đổi trong suốt quá trình tìm<br /> kiếm và được điều khiển bởi 1 tham số  :<br /> <br /> - Nếu lời giải đang xét thoả tất cả các ràng buộc cứng: gán   min(1, /  ) với  được<br /> chọn ngẫu nhiên trong khoảng [1.05, 1.19].<br /> - Nếu lời giải đang xét không thoả tất cả các ràng buộc cứng: gán   max(1000, *  )<br /> với  được chọn ngẫu nhiên trong khoảng [1.05, 1.19]<br /> <br /> Bên cạnh đó, tác giả [11] còn thực hiện phép hoán chuyển (đã đề cập ở phần phép<br /> chuyển) nhiều lần để làm ‘‘xáo trộn’’ lời giải hiện tại, từ đó làm tăng tính đa dạng cho quá<br /> trình tìm kiếm.<br /> <br /> Về chiến lược tăng cường hoá, nhóm tác giả C.H. Aladag [16] áp dụng cách làm sau:<br /> nếu như sau một số bước lặp nhất định mà chất lượng lời giải tốt nhất vẫn không được cải<br /> thiện, quá trình tìm kiếm sẽ được khởi động lại, với lời giải khởi tạo chính là lời giải tốt nhất<br /> hiện tại. Mục đích của cách làm này là tập trung mạnh hơn vào vùng không gian của lời giải<br /> tốt nhất hiện tại với hi vọng tìm ra những lời giải tốt mà bị bỏ sót trong quá trình tìm kiếm<br /> trước đây.<br /> <br /> Ngoài ra, nhóm tác giả L. D. Gaspero và A. Schaerf [12] còn áp dụng thêm thuật giải<br /> leo đồi xen kẽ với phần tìm kiếm cơ bản của thuật giải Tabu Search, cũng với mục đích tăng<br /> cường hoá chất lượng tìm kiếm.<br /> 4. KẾT LUẬN<br /> <br /> Trong bài báo này, chúng tôi đã khảo sát một số biến thể của thuật giải Tabu Search<br /> cho bài toán xếp thời khoá biểu cho trường đại học, một trong những bài toán tối ưu tổ hợp rất<br /> khó và cũng rất thực tế hiện nay. Hướng tiếp cận Tabu Search đã giúp giải quyết được khá<br /> hiệu quả rất nhiều bài toán xếp thời khoá biểu đại học cụ thể. Việc khảo sát thuật giải này<br /> chính là tiền đề cho việc nghiên cứu và phát triển thuật giải Tabu Search để giải quyết bài<br /> toán xếp thời khoá biểu cho các trường đại học ở Việt Nam, với những yêu cầu rất đặc trưng<br /> của nền giáo dục nước ta. Sau một thời gian tìm hiểu và thử nghiệm, nhóm tác giả đã phát<br /> triển hai hệ thống xếp thời khoá biểu cho trường đại học và trường trung học với hướng tiếp<br /> cận dựa trên Tabu Search. Hai hệ thống này được thể hiện dưới cả hai dạng: online (các trang<br /> web) và offline (các phần mềm chạy trên máy tính), nhằm tăng tính mở và tính tiện dụng cho<br /> người dùng. Để biết chi tiết của các hệ thống này, độc giả có thể xem tại trang web của nhóm<br /> tác giả:<br /> <br /> <br /> <br /> <br /> TÀI LIỆU THAM KHẢO<br /> <br /> 1. Andrea Schaerf (1999). “A Survey of Automated Timetabling”. Kluwer Academic<br /> Publishers.<br /> 2. Luca Di Gaspero, Barry McCollum, Andrea Schaerf (2007), "The Second<br /> International Timetabling Competition (ITC-2007): Curriculum-based Course<br /> Timetabling (Track 3)", International Timetabling Competition 2007-2008.<br /> 3. Rhidian Lewis, Ben Paechter, Barry McCollum (2007), "Post Enrolment based<br /> Course Timetabling: A Description of the Problem Model used for Track Two of the<br /> Second International Timetabling Competition", International Timetabling<br /> Competition 2007-2008.<br /> 4. Fred Glover, Manuel Laguna (1998), “Tabu Search”, Kluwer Academic Publishers,<br /> Boston, London.<br /> 5. Fred Glover (1989), “Tabu Search - part I”, ORSA Journal on Computing, Vol.1, No.<br /> 3.<br /> 6. C. C. Gotlieb (1963). “The construction of class-teacher timetables”. In C. M.<br /> Popplewell, IFIP congress, 62:73--77. North-Holland.<br /> 7. D. Costa (1994). “A tabu search algorithm for computing an operational timetable”.<br /> European Journal of Operational Research, 79:98-110.<br /> 8. Halvard Arntzen , Arne Lokketangen (2003). “A tabu search heuristic for a university<br /> timetabling problem”, MIC2003, Japan.<br /> 9. Ramon Alvarez-Valdes, Enric Crespo, Jose M. Tamarit (2002). "Design and<br /> implementation of a course scheduling system using Tabu Search", European Journal<br /> of Operational Research 137, pp 517-518.<br /> 10. www.fit.hcmus.edu.vn/~nmkhang/uts<br /> www.fit.hcmus.edu.vn/~nmkhang/hts<br />