Tài liệu Kết hợp thuật giải di truyền phân nhóm và tìm kiếm cục bộ cho bài toán xếp thời khóa biểu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- TRƯƠNG VĂN HIẾU KẾT HỢP THUẬT GIẢI DI TRUYỀN PHÂN NHÓM VÀ TÌM KIẾM CỤC BỘ CHO BÀI TOÁN XẾP THỜI KHÓA BIỂU NGÀNH: TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH MÃ SỐ: 60.48.15 8 Người hướng dẫn khoa học: PGS. TS TRẦN ĐÌNH QUẾ TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT HÀ NỘI – 2010 -1- MỞ ĐẦU 1. Cơ sở khoa học và thực tiễn của đề tài: Bài toán lập thời khóa biểu luôn là một bài toán cổ điển thuộc lớp bài toán tối ưu ràng buộc, khó. Từ lâu đã thu hút được sự quan tâm, nghiên cứu và phát triển của nhiều tổ chức giáo dục, các nhà khoa học bởi tính ứng dụng cao và độ phức tạp của nó. Các bài toán lập thời khóa biểu thường rất phong phú, đa dạng bởi các ràng buộc và yêu cẩu của từng tổ chức. Trong nhiều thập niên qua đã có rất nhiều các phương pháp giải được đưa ra. Tuy nhiên, tính hiệu quả của lời giải cho lớp bài toán vẫn còn nhiều bàn cãi. Trong khi các thuật toán truyền thống tỏ ra kém hiệu quả thì các thuật toán mô phỏng tự nhiên lại tỏ ra là phương pháp hữu hiệu nhất để giải các bài toán này. Những năm gần đây, đã có nhiều các phát triển phong phú của Thuật giải di truyền cổ điển về kiểu gen, kỹ thuật kết hợp tìm kiếm cục bộ và thuật toán di truyền. Chúng đem lại những Thuật giải mới khá mạnh và linh hoạt để giải quyết các vấn đề mang tính tổ hợp. Với đề tài ”Kết hợp Thuật giải di truyền phân nhóm và tìm kiếm cục bộ cho bài toán xếp thời khóa biểu”, khóa luận mạnh dạn nghiên cứu và giới thiệu một phương pháp mới cho việc giải các bài toán xếp thời khóa biểu trong trường đại học. 2. Mục tiêu của luận văn Bài toán xếp Thời khóa biểu đã từ lâu trở thành một bài toán nổi tiếng và thu hút được sự quan tâm của rất nhiều nhà nghiên cứu, nhiều chuyên gia trong các lĩnh vực liên quan. Sự "nổi tiếng" của bài toán này không chỉ được đo bởi độ phức tạp của vấn đề, mà còn ở tính thực tiễn, khả năng áp dụng rất cao trên thực tế. Do đó mục tiêu của luận văn là: Nghiên cứu kỹ thuật kết hợp thuật toán di truyền phân nhóm và tìm kiếm cục bộ cho bài toán sắp xếp thời khoá biểu. Luận văn sẽ xem xét áp dụng kỹ thuật này vào việc xây dựng chương trình xếp thời khóa biểu cho trường đại học. -2- CHƯƠNG 1 TỔNG QUAN VỀ BÀI TOÁN XẾP THỜI KHÓA BIỂU VÀ CÁC CÁCH TIẾP CẬN HIỆN NAY Bài toán xếp Thời khóa biểu luôn là một bài toán khó, mang tính khoa học đồng thời tính thực tiễn cũng rất cao. Riêng đối với môi trường Việt Nam, từ lâu việc xếp thời khóa biểu đã trở thành một vấn đề có tính thời sự, một bài toán gây được sự chú ý, quan tâm của nhiều người. Bài toán lập thời khóa biểu là một trường hợp riêng của bài toán lập lịch trong đó đưa ra một chuỗi các sự kiện (thông thường là các môn học, bài giảng hoặc các môn thi) và bao gồm các giáo viên và học viên trong một khoảng thời gian định trước và thỏa mãn một tập hợp các ràng buộc của từng loại thời khóa biểu khác nhau. Nói chung bài toán lập thời khóa biểu được chia làm 3 dạng chung được mô tả khác nhau: Bài toán lập thời khóa biểu cho trường phổ thông, bài toán lập thời khóa biểu cho trường đại học, bài toán xếp lịch thi. 1.1 Bài toán lập thời khóa biểu cho trường phổ thông Bài toán lập thời khóa biểu cho trường phổ thông hay bài toán phân chia giáo viên, lớp học trong một tuần đối với tất cả các môn học của một trường học. Với ba tập hợp cho trước là tập giáo viên, tập lớp học và tập tiết học và một ma trận ràng buộc số bài giảng một giáo viên được phân công dạy một lớp. Bài toán yêu cầu phân chia các bài giảng vào các tiết sao cho không giáo viên hay lớp học nào có cùng một bài giảng trong cùng một thời gian và mỗi giáo viên đều có một số lượng nhất định các bài giảng với mỗi lớp học. 1.2 Bài toán lập thời khóa biểu cho trường đại học ( University timetabling ) Bài toán lập thời khóa biểu cho trường đại học là bài toán lập lịch cho các bài giảng (lectures) vào từng khóa học với một số lượng phòng học và tiết học cho trước. Điểm khác biệt chính với bài toán lập thời khóa biểu trường phổ thông là đặc trưng của các khóa học ở trường đại học, các sinh viên tham dự khóa học, trong khi các lớp học ở trường phổ thông được tạo bởi tập hợp các học sinh và có thể coi như là một thực thể đơn. Ở các trường đại học, hai khóa học khác nhau có thể có trùng sinh viên tham dự và điều đó có thể tạo ra xung đột và sẽ không thể lập lịch được trong cùng một tiết học. Thêm vào đó, các giáo viên ở trường phổ thông luôn dạy nhiều hơn một lớp trong khi ở trường đại học -3- một giáo sư thường chỉ dạy một khóa học hay một môn học trong một kỳ. Cuối cùng, với bài toán trường đại học kích cỡ các phòng học chiếm một vai trò quan trọng trong khi với bài toán trường phổ thông vấn đề này là không quan trọng bởi vì trong hầu hết các trường phổ thông mỗi lớp có một phòng học riêng. 1.3 Bài toán xếp lịch thi (Examination timetabling) Bài toán lập lịch thi tương tự như bài toán lập thời khóa biểu cho trường đại học nhưng ta cần phân biệt sự khác nhau giữa hai bài toán này. Bài toán lập lịch thi có những đặc điểm khác sau đây :  Chỉ có một kỳ thi cho mỗi một môn thi.  Các điều kiện xung đột nói chung là hạn chế. Thực tế, chúng ta có thể chấp nhận một sinh viên có thể bỏ qua một bài giảng do sự chồng chéo các môn học nhưng không có sinh viên nào được phép bỏ qua một kỳ thi.  Và một số ràng buộc khác nhau ví dụ hầu hết một sinh viên sẽ chỉ có một kỳ thi trong một ngày và không có nhiều quá các kỳ thi liên tiếp nhau với một sinh viên.  Số tiết của kỳ thi có thể khác nhau, ngược lại với bài toán lập thời khóa biểu cho trường đại học cái đó là cố định.  Có thể có nhiều hơn một kỳ thi trong một phòng nhưng lại không thể có nhiều bài giảng được diễn ra trong một phòng tại một thời điểm. 1.4 Các cách tiếp cận hiện nay Bài toán thời khóa biểu nói riêng và các bài toán tối ưu tổ hợp nói chung là rất khó giải. Sự khó khăn của chúng được thể hiện ở độ phức tạp tính toán và với những bài toán thuộc lớp NP-khó như vậy thời gian để giải thường tăng theo hàm mũ của kích thước bài toán. Như chúng ta đã biết, trong thuật toán “vét cạn” (tìm kiếm theo bề rộng hoặc theo độ sâu), về mặt nguyên tắc các phương pháp tìm được nghiệm của bài toán nếu bài toán có nghiệm, song trên thực tế những bài toán NP-khó không thể áp dụng được phương pháp này, vì ta phải phát triển một không gian trạng thái rất lớn, trước khi đi tới trạng thái đích, do những hạn chế về thời gian tính toán và dung lượng bộ nhớ, không cho phép chúng ta làm được điều đó. Trong những năm gần đây việc kết hợp tìm kiếm cục bộ và thuật giải di truyền phân nhóm là một trong số các cách tiếp cận mới nhất. Trong chương 3 chúng ta sẽ tìm hiểu chi tiết thuật toán di truyền phân nhóm cho bài toán UCTP. -4- CHƯƠNG 2 TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP TÌM KIẾM CỤC BỘ, THUẬT GIẢI DI TRUYỀN 2.1 Tìm kiếm cục bộ Tìm kiếm cục bộ dựa vào một ý tưởng tổng quát và đơn giản. Gọi P là một bài toán tối ưu tổ hợp cần giải, và s là lời giải hiện hành giả sử là một lời giải khả thi của P, và có hàm chi phí f(s). Miền lân cận N(s) được định nghĩa cho s, là tập những lời giải láng giềng khả thi s’ của s sao cho từ s ta có thể đạt tới s’ nhờ vào một bước chuyển m. Bước chuyển có tác dụng biến đổi s thành ra một lời giải láng giềng. Thao tác biến đổi này được lặp cho đến khi hội tụ về một lời giải tốt. Lời giải này là lời giải cận tối ưu, mà trong một số bài toán thực tế, không sai biệt gì nhiều với lời giải tối ưu. 2.1.1 Xung đột tối thiểu (Min-conflict) Thuật giải xung đột tối thiểu, viết tắt là MC đã được dùng khá phổ biến để giải hệ ràng buộc quá mức. Thuật giải MC chọn ngẫu nhiên một biến nào đó dính líu đến một ràng buộc bị vi phạm và rồi chọn một trị từ miền trị của biến này sao cho tối thiểu hoá số lượng những vị phạm ràng buộc có thể xảy ra. Vì Thuật giải MC thuần túy có thể không thoát ra được điểm tối ưu cục bộ, Thuật giải thường kết hợp với một chiến lược bước ra ngẫu nhiên (random walk). Với một biến nào đó được chọn, chiến lược bước ra ngẫu nhiên lấy ngẫu nhiên một trị từ miền trị của biến này với xác xuất p, và áp dụng theo Thuật giải MC với xác xuất 1- p. Giá trị của thông số p có ảnh hưởng lên hiệu quả của Thuật giải. Thuật giải này được gọi là MCRW 2.1.2 Thuật giải mô phỏng luyện kim (simulated annealing) Mô phỏng luyện kim(SA) là một kỹ thuật tìm kiếm ngẫu nhiên (stochastic search) mà tỏ ra rất hữu hiệu cho những bài toán tối ưu hóa qui mô lớn. Trong kỹ thuật này, nhiệt độ là biến được khởi tạo ở một giá trị cao và dần dần giảm dần xuống trong quá trình tìm kiếm. Tại những trị nhiệt độ cao, các bước chuyển được chấp nhận một cách ngẫu nhiên bất luận chúng là bước chuyển có cải thiện hàm chi phí của lời giải hay không. Khi nhiệt độ được giảm xuống, xác xuất để chấp nhận một lời giải có cải thiện sẽ tăng lên và xác xuất để chấp nhận một lời giải không cải thiện sẽ giảm xuống. Có một số cách thức giảm -5- nhiệt độ dần xuống được dùng trong một Thuật giải SA, được gọi là lịch biểu làm nguội (cooling schedule). 2.1.3 Thuật giải leo đồi (Hill-climbing) Thuật giải leo đồi chính là nền tảng cơ sở của các kỹ thuật tìm kiếm cục bộ. Mặc dù đây là Thuật giải đơn giản nhưng lại nó lại rất mạnh và hiệu quả trong việc giải quyết các bài toán CSP lớn. Thuật ngữ “leo đồi” (hill-climbing) xuất phát từ cơ chế “tu chỉnh lập”: ở mỗi bước của việc tìm kiếm, chúng ta sẽ chọn một bước chuyển mà nó cải thiện giá trị hàm mục tiêu để thực hiện. Trong Thuật giải leo đồi, chỉ những bước chuyển cải thiện được hàm chi phí hoặc không làm cho hàm chi phí thay đổi mới được chọn vì vậy việc tìm kiếm sẽ liên tục bước lên vị trí cao hơn cho đến khi nó gặp điều kiện dừng. 2.1.4 Tìm kiếm Tabu (Tabu search) Tìm kiếm Tabu được đề xuất bởi Glover năm 1986 ([10]). Phương pháp dò tìm trong không gian lời giải bằng cách di chuyển từ một lời giải s tại lượt lặp t về một lời giải tốt nhất s’ trong tập con N* của miền lân cận N(s). Vì s’ không nhất thiết cải thiện chi phí của s, một cơ chế được đặt ra để ngăn chặn quá trình khỏi lặp vòng trên một chuỗi các lời giải. Một cách để tránh sự lặp vòng là cấm quá trình tìm kiếm quay về những lời giải đã gặp rồi, nhưng làm như vậy đòi hỏi phải lưu trữ khá nhiều thông tin. Thay vì làm thế, chỉ một vài thuộc tính của những lời giải đã gặp sẽ được lưu trong danh sách tabu (tabu list) và bất kỳ lời giải nào sở hữu những thuộc tính này sẽ không được xét đến trong θ? lần lặp. Cơ chế này thường được gọi là bộ nhớ ngắn hạn và θ? được gọi là kỳ hạn tabu. Tìm kiếm tabu được phát triển thành nhiều dạng cải tiến như tìm kiếm tabu thích nghi (reactive tabu search) ([1]) và tìm kiếm tabu với hai danh sách tabu: bộ nhớ ngắn hạn và bộ nhớ dài hạn ([32]). 2.1.5 Thuật giải di truyền (genetic algorithm) Thuật giải di truyền (GA) (Goldberg, 1989 [6]) đã tỏ ra khá thành công trong một số những áp dụng. GA mượn ý tưởng trong quá trình tiến hóa của sinh vật. Ý tưởng chính của Thuật giải là duy trì một quần thể các lời giải ứng viên. Các lời giải ứng viên này sẽ được cho cơ hội riêng lẻ để sản sinh ra con cái tùy thuộc vào độ thích nghi (fitness) của chúng. Độ thích nghi được đo bằng một -6- hàm mục tiêu. Thuật giải GA đã được áp dụng vào việc giải hệ ràng buộc ([3]). Việc dùng Thuật giải GA vào các bài toán tối ưu hóa có ràng buộc làm phát sinh nhiều vấn đề mà các nhà nghiên cứu phải quan tâm giải quyết. Một trong những vấn đề quan trọng là làm thế nào để đưa các ràng buộc vào các hàm thích nghi (fitness function) để điều khiển quá trình tìm kiếm một cách đóng đắn. 2.1.6 Kết luận Sự thành công của bất kỳ Thuật giải tìmkiếm cục bộ nào nêu trên cũng tùy thuộc vào các đặc điểm thi công, tức là tùy thuộc vào các tham số kỹ thuật đặc thù mà người sử dụng phải xác định khi áp dụng Thuật giải tìm kiếm cục bộ đó vào bài toán cụ thể. Quá trình thực nghiệm để xác định các thông số kỹ thuật của một Thuật giải tìm kiếm cục bộ nào đó khi áp dụng vào một bài toán cụ thể được gọi là quá trình điều chỉnh thông số (parametertuning). -7- 2.2 Thuật giải di truyền 2.2.1 Các đặc điểm đặc trưng Giải thuật di truyền đã mô phỏng sự chọn lọc tự nhiên và di truyền. Trong tự nhiên, các cá thể khỏe, có khả năng thích nghi với môi trường tốt sẽ được tồn tại và phát triển ở các thế hệ sau. Mỗi cá thể có cấu trúc gen đặc trưng cho tính chất của cá thể đó. Trong quá trình sinh sản, các cá thể con có thể thừa hưởng các phẩm chất của cha mẹ, cấu trúc gen của nó mang một phần cấu trúc gen của cha mẹ. Ngoài ra, trong quá trình tiến hóa, có thể xảy ra hiện tượng đột biến, cấu trúc gen của cá thể con có thể chứa các gen mà cả cha mẹ đều không có. Trong giải thuật di truyền, mỗi cá thể được mã hóa bởi một cấu trúc dữ liệu mô tả cấu trúc gen của cá thể đó, ta gọi nó là nhiễm sắc thể. Mỗi nhiễm sắc thể được tạo thành từ các đơn vị được gọi là gen. Giải thuật di truyền sẽ làm việc trên các quần thể gồm nhiều cá thể. Một quần thể ứng với một giai đoạn phát triển gọi là một thế hệ. Từ một thế hệ được tạo ra, giải thuật di truyền bắt chước sự chọn lọc tự nhiên và di truyền để biến đổi các thế hệ. 2.2.2 Các thành phần của giải thuật di truyền 2.2.2.1 Khởi tạo quần thể ban đầu Tạo quần thể đầu tiên trong giải thuật, là nơi xuất phát quá trình tiến hóa, bao gồm tất cả các giá trị thô ban đầu. Tùy theo vấn đề của bài toán mà có cách khởi tạo khác nhau. 2.2.2.2 Đánh giá cá thể Có nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất, ví dụ: chọn lọc roulette wheel, chọn lọc xếp hàng, chọn lọc cạnh tranh, v.v… - Chọc lọc Roulette wheel Các cá thể cha mẹ được chọn theo độ thích nghi của chúng. Nhiễm sắc thể tốt hơn có cơ hội cao hơn để tham dự vào thế hệ tiếp theo. - Chọn lọc xếp hạng (Rank Selection) Phương pháp này sẽ sắp hạng cá thể dựa trên độ thích nghi của chúng. Cá thể xấu nhất sẽ có giá trị 1, kế tiếp là 2, v.v…và cá thể tốt nhất sẽ có độ thích nghi N (N là số nhiễm sắc thể trong quần thể). - Chọn lọc cạnh tranh (Tournament Selection)  Chọn lọc cạnh tranh 2 (2-tournament selection) -8- Hai nhiễm sắc thể khác nhau được chọn ngẫu nhiên và được so sánh với nhiễm sắc thể tồn tại. Nếu nhiễm sắc thể I1 không tốt hơn nhiễm sắc thể I2 nghĩa là: f(I1) ≤ f(I2), thì nhiễm sắc thể I1 chết đi và bị loại ra khỏi quần thể. Quá trình này lặp lại đến hết N nhiễm sắc thể còn lại.  Chọn lọc cạnh tranh 3 (3-tournament selection) Giống như trên, ba nhiễm sắc thể khác nhau được chọn ngẫu nhiên và được so sánh. Nếu chúng ta có f(I1) ≤ f(I2) và f(I1) ≤ f(I3), thì nhiễm sắc thể I1 chết đi và bị loại ra khỏi quần thể. Quá trình này lặp lại đến hết N nhiễm sắc thể còn lại. 2.2.2.3 Toán tử lai ghép: Toán tử lai ghép có trật tự bao gồm các bước sau: - Chọn ngẫu nhiên một chuỗi con từ một cá thể cha mẹ (parent). - Đưa ra một proto-child bằng cách sao chép chuỗi con vào những vị trí tương ứng như trong cá thể cha mẹ. - Xoá tất cả các ký hiệu từ cá thể cha mẹ thứ hai, lúc này đã có trong chuỗi con. Chuỗi còn lại chứa các ký hiệu mà proto-child cần. - Đặt các ký hiệu vào những vị trí không cố định của proto-child từ trái sang phải theo trật tự của chuỗi để tạo ra cá thể con. 2.2.2.4 Toán tử đột biến: - Đột biến đảo ngược(Inversion Mutation) Chọn hai vị trí ngẫu nhiên trong một nhiễm sắc thể và sau đó, nghịch đảo chuỗi giữa hai vị trí này. - Đột biến thay thế (Displacement Mutation) Chọn ngẫu nhiên một chuỗi con và chèn nó vào một vị trí ngẫu nhiên. Đột biến chèn có thể được xem như trường hợp đặc biệt của đột biến thay, trong đó, chuỗi con chỉ chứa một gen. - Đột biến tương hỗ (Reciprocal Exchange Mutation) Chọn ngẫu nhiên hai vị trí và sau đó hoán vị gen trên những vị trí này. 2.2.2.5 Đột biến chuyển dịch (Shift Mutation) Trước tiên, chọn ngẫu nhiên một gen, sau đó, dịch chuyển nó đến một vị trí ngẫu nhiên bên phải hoặc bên trái vị trí của gen. -9- CHƯƠNG 3 KẾT HỢP THUẬT GIẢI DI TRUYỀN PHÂN NHÓM VÀ TÌM KIẾM CỤC BỘ CHO BÀI TOÁN UCTP 3.1 Thuật giải di truyền phân nhóm Thuật toán GGA, có thể được coi là một dạng đặc biệt của thuật toán di truyền chuyên dùng cho các vấn đề phân nhóm. Falkenauer[2] định nghĩa bài toán phân nhóm là bài toán có nhiệm vụ phân chia một tập hợp các đối tượng U thành một tập hợp các tập hợp con (nhóm) ui của U thỏa mãn: 3.1.1 Mã hóa Cấu tạo của đoạn mã GGA gồm 2 phần : phần 1 là đối tượng, phần 2 là nhóm. Mỗi đối tượng có một đoạn gen. Đối tượng Phân cách Nhóm AABC:BAC Đối tượng 3 ở Nhóm C Đối tượng 2 ở Nhóm B Đối tượng 1 ở Nhóm A Đối tượng 0 ở Nhóm A Hình 1: Mã hóa gen trong Thuật giải di truyền phân nhóm Ví dụ [1,2,3,4,1,1,1,1,1] : [1,2,3,4] ta có thể mã hóa theo cách khác như sau: {{1, 5, 6, 7, 8, 9},{2},{3},{4}} - 10 - 3.1.2 Lai ghép Mục đích của toán tử lai ghép là chuyển một cách hợp lý các liên kết nhóm từ bố mẹ tới con. Toán tử lai ghép làm việc trực tiếp với nhóm và giám tiếp với đối tượng. Toán tử lai ghép được thực hiện theo 5 bước sau: 1> Chọn ngẫu nhiên 2 điểm cắt trên nhóm của 2 bố mẹ, phân định ranh giới của đoạn cắt 2> Sao chép nội dung của đoạn cắt trên bố mẹ thứ 2 tới vị trí cắt đầu tiên trên bố mẹ thứ 1. Điều này có nghĩa là ta đã sao chép một vài nhóm từ bố mẹ thứ 2 tới bố mẹ thứ 1 3> Loại bỏ tất cả các đối tượng xuất hiện từ 2 lần trở lên từ bố mẹ thứ 1 4> Các đối tượng trong các nhóm đã bị tác động ( nhóm mà các phần tử trùng đã bị loại bỏ) được gán lại tuân theo một luật heuristic 5> Lặp lại các bước từ 2 tới 4 cho con mới được sinh ra với vai trò của bố mẹ và các điểm lai ghép được đảo ngược Điểm cắt Bước 2 Chọn nhóm Bước 1 Nhóm bị xóa Nhóm sửa Đối tượng 2 bị xóa và chèn lại Bước 4 Bước 3 Hình 2: Lai ghép 3.1.3 Đột biến Vai trò của toán tử đột biến ở thuật toán di truyền đảm bảo rằng một vài nhiễm sắc thể con được tạo ra gần đây sẽ được tìm kiếm trên vùng mới của không gian tìm kiếm. - 11 - Cũng giống như lai ghép, toán tử đột biến làm việc trực tiếp với nhóm theo các bước sau: 1> Tạo nhóm ra mới cho các đối tượng được trích ra từ một hoặc nhiều nhóm đã tồn tại 2> Loại bỏ nhóm đã tồn tại bằng cách di chuyển nội dung của nó tới các nhóm khác 3> Di chuyển một hoặc nhiều đối tượng tới các nhóm khác 4> Sắp xếp lại một hoặc nhiều đối tượng giữa các nhóm 3.2 Kết hợp GGA và tìm kiếm cục bộ cho bài toán UCTP 3.2.1 Dữ liệu của bài toán Trong bài luận này tôi không mong muốn làm để có thể đáp ứng cho tất cả các loại hình đào tạo, vì vậy mà tôi sẽ cố gắng giải quyết dạng đơn giản nhất đó là đào tạo theo niên chế và học đồng đều theo kỳ. Điều đó có nghĩa rằng tôi sẽ chỉ đơn giản đó là lập thời khoá biểu cho 1 tuần sau đó sẽ nhân chúng lên Trong khuôn khổ thời gian của một bài luận tôi chỉ cố gắng quan tâm đến vấn đề mô phỏng thuật toán mà chưa đến giai đoạn làm thật. 3.2.2 Các yêu cầu của bài toán (các ràng buộc) Khi lập thời khoá biểu chúng ta phải đảm bảo các yêu cầu sau (ràng buộc cứng):  Không lớp học nào phải học cùng một thời điểm 2 môn  Các phòng là đủ rộng để có thể chứa hết số SV  Không giáo viên nào phải dạy 2 môn trong cùng thời gian Tiếp đến chúng ta sẽ xem xét đến các ràng buộc mềm:  Thời khoá biểu phải có khả năng chấp nhận các ngày nghỉ định trước của các giáo viên. 3.2.3 Các sự kiện Các sự kiện được định nghĩa như sau:  Có 1 nhóm các lớp tham gia học (1 nhóm có thể chỉ bao gồm 1 lớp). Tham số này đồng thời cũng chứa các thống số phụ đó là tổng số Sinh Viên Tham gia sự kiện  Có 1 môn học  Có 1 giáo viên dạy  Sự kiện sảy ra trong 1 thời điểm trong tuần (xác định bởi ngày, tiết)  Phòng học - 12 - 3.2.4 Trình bày giải pháp Trong bài toán này chúng tôi đề xuất sử dụng giải pháp 2 giai đoạn:  Giai đoạn 1 : Tìm ra phương án khả thi bằng cách sử dụng thuật giải di truyền phân nhóm để thỏa mãn các ràng buộc cứng  Giai đoạn 2 : Giảm thiểu các vi phạm ràng buộc mềm xuống mức thấp nhất có thể bằng cách sử dụng phương pháp tìm kiếm cục bộ 3.2.5 Giai đoạn 1 sử dụng Thuật giải di truyền phân phóm Ở đây tập hợp các sự kiện đóng vai trò là tập hợp các đối tượng để phân chia và các nhóm được xác định bởi tiết học. Do đó một giải pháp khả thi là giải pháp mà tất cả các sự kiện cần được nhóm tới nhiều nhất các tiết học t (trong trường hợp này t=60 (5 ngày và 12 tiết một ngày) Mỗi thời khoá biểu tương đương với một ma trận M với các hàng đại diện cho các phòng học và các cột đại diện cho các tiết học; do đó nếu M(a,b)=c thì sự kiện c chắc chắn xảy ra trong phòng học a và tiết học b và có nhiếu nhất một sự kiện. Mặt khác nếu M(a,b) bỏ trống thì không có sự kiện nào được sắp xếp trong phòng học a và tiết học b. CONSTRUCT (tt, U). 1. if (len(tt) < t) 2. Open (t – len(tt)) new timeslots; 3. Build (tt, U, 1, len(tt)); BUILD (tt, U, l, r). 1. while ( tồn tại sự kiện ở trong U với vị trí ở tt nằm trong khoảng l và r) 2. Chọn sự kiện e ở trong U mà khả thi gán ở tt; 3. Chọn một vị trí và chèn e vào; 4. if (U =Φ) end; 5. else 6. Open mới [|U|/m] timeslots; 7. Build (tt, U, r, len(tt)); Hình 1 Lưu ý rằng các ràng buộc mềm không được xem xét trong định nghĩa này. Ở đây chúng ta sử dụng 2 thủ tục Construct và Buid với các tham số: tt là thời khóa biểu chưa hoàn chỉnh, U chứa danh sách các sự kiện chưa được sắp xếp trên thời khóa biểu. Sử dụng chương trình con Buid, từng sự kiện một được lấy từ U ( tuân theo các heristics được định nghĩa ở bảng 1) và chèn vào các vị trí khả thi nằm trong khoảng l và r ở trên thời khóa biểu. Các sự kiện mà không có vị trí khả thi để chèn thì được bỏ qua. Cuối cùng là U sẽ bằng rỗng hoặc là - 13 - nó chỉ chứa các sự kiện mà không thể chèn vào bất cứ đâu trên thời khóa biểu hiện thời. Số tiết học mới được mở thêm sẽ được tính ở dòng 6 của thủ tục Buid trong hình 1. Thứ tự khởi tạo quẩn thể ban đầu được thực hiện như sau: Thủ tục Construct được gọi cho mỗi nhiễm sắc thể. Ở mỗi bước thực hiện, sự kiện được chọn sẽ tuân theo heuristic H1 với ưu tiên sau đó bởi H3. Tiếp theo một vị trí được chọn cho mỗi sự kiện sẽ tuân theo heuristic H4 với ưu tiên sau đó là H6. Việc sử dụng luật H1, H2 cho phép chúng ta ưu tiên sắp xếp các sự kiện mà khó khả thi nhất, luật H4, H5 cho phép chúng ta ưu tiên chọn những vị trí kém khả thi nhất. Điều đó có nghĩa là thời khóa biểu sẽ được điền với nhiều nhất các sự kiện và tiết học khả thi trên đó. Luật H3, H6 ( chọn ngẫu nhiên) đảm bảo cho chúng ta đủ sự ngẫu nhiên khi khởi tạo quần thể. Heuristic H1 H2 H3 H4 H5 H6 Bảng 1 Mô tả Chọn sự kiện có khả năng sắp xếp vào thời khóa biểu hiện tại là Chọn sự kiện mà khả năng xung đột với các sự kiện khác là nhiều Chọn một sự kiện ngẫu nhiên Chọn vị trí mà tồi nhất trong các sự kiện chưa đc sắp xếp Chọn vị trí trên thời khóa biểu có nhiều nhất các sự kiện Chọn vị trí ngẫu nhiên Toán tử di truyền Hình 6 cho thấy chúng tôi thực hiện việc tái kết hợp như thế nào để xây dựng thời khoá biểu con đầu tiên sử dụng bố mẹ P1 và P2, chọn ngẫu nhiên các điểm lai ghép a, b, c và d. - 14 a c b P1 d P2 (1) Điểm lựa chọn: Chọn 2 thời khóa biểu p1 và p2, chọn ngẫu nhiên 4 điểm cắt a, b, c và d + (2) Lai ghép: Copy các tiết học nằm trong khoảng c và d tới điểm a U (3) Xóa các sự kiện trùng: Xóa các tiết học mà nội dung chứa các sự kiện trùng ở p1. Các sự kiện không trùng lặp nằm trong các tiết học bị xóa được đưa vào tập U (4) Xây dựng lại: Chèn lại các sự kiện trong U sử dụng chương trình con Buid Hình 6: Quá trình tái kết hợp Để thực hiện TKB con thứ hai chúng ta chuyển đổi vai trò của bố mẹ và các điểm lai ghép. Điểm quan trọng ở đây là toán tử lai ghép cho phép TKB con tạo ra thừa kế những tiết học đã được sắp xếp hoàn chỉnh trên TKB của cả bố và mẹ. Trong quá trình tiến hành tái kết hợp, chúng ta lưu ý rằng ở bước2 (lai ghép), sẽ có các sự kiện trùng ở TKB con, vì vậy mà nó tạo ra sự không hợp lệ. Để hiểu chỉnh lỗi này chúng tôi sẽ tiến hành xóa các sự kiện trùng từ tiết học ở p1. Cuối cùng, ở bước 4 của quá trình tái kết hợp các sự kiện chưa được sắp xếp (sự kiện trong U) sẽ lần lượt được chèn lại sử dụng thủ tục BUID (hình 1) với heuristic H1 để định nghĩa thứ tự các sự kiện được chèn ( với ưu tiên sau đó sử dụng H2, H3). Các vị trí để chèn các sự kiện sử dụng heuristic như ở phần khởi tạo quần thể. Toán tử đột biến mà chúng tôi sử dụng tuân theo một biểu đồ đột biến GGA điển hình (mr là tỷ lệ đột biến) : chuyển một số tiết học khó sắp xếp trong số các tiết học được lựa chọn ngẫu nhiên từ một TKB và nhập lại các sự kiện vào trong các tiết học có sử dụng biểu đồ Rebuild. Cụ thể là biểu đồ Rebuild lấy một TKB tt rỗng hoặc từng phần và một tập hợp U các sự kiện chưa được sắp xếp. Sau đó nó gán cho tất cả u∈U một phòng học và tiết học để tạo ra một TKB hoàn chỉnh, mở ra các tiết học mới cần thiết. Lưu ý rằng TKB ban đầu với U=E. Để S ứng với tập hợp các tiết học trong tt và P ứng với tập hợp các nơi trong tt , ví dụ P=RxS - 15 - Cuối cùng, ở trong GGA chúng tôi cũng sử dụng toán tử đảo ngược, toán tử này lựa chọn ngẫu nhiên hai tiết học trong TKB và đổi thứ tự tất cả các nội dung giữa chúng. Nâng cao chất lượng lời giải ở giai đoạn 1 Sau khi sử dụng thuật toán GGA chúng tôi tiếp tục sử dụng thủ tục HeuristicSearch để giảm thiểu các sự kiện chưa được sắp xếp xuống mức nhỏ nhất có thể. - 16 HeuristicSearch(tt,U,itLimit) 1. V là danh sách các vị trí ở tt mà chưa có sự kiện đc gán 2. i:=0; 3. while (U and V and i - Xem thêm -