›

Đồ án Xây dựng chương trình hỗ trợ xếp lịch thời khóa biểu cho đào tạo và học tập tín chỉ - Nguyễn Hoàng Anh

pdf 74 trang huongle 2810
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Xây dựng chương trình hỗ trợ xếp lịch thời khóa biểu cho đào tạo và học tập tín chỉ - Nguyễn Hoàng Anh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_xay_dung_chuong_trinh_ho_tro_xep_lich_thoi_khoa_bieu_c.pdf

Nội dung text: Đồ án Xây dựng chương trình hỗ trợ xếp lịch thời khóa biểu cho đào tạo và học tập tín chỉ - Nguyễn Hoàng Anh

  1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o Xây dựng chƣơng trình hỗ trợ xếp lịch thời khóa biểu cho đào tạo và học tập tín chỉ ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY NGÀNH CÔNG NGHỆ THÔNG TIN Sinh viên thực hiên: Nguyễn Hoàng Anh Giáo viên hướng dẫn: Ths. Nguyễn Thị Xuân Hƣơng Mã số sinh viên: 111185 HẢI PHÒNG – 2011 1
  2. LỜI CẢM ƠN Trước tiên em xin được bày tỏ sự trân trọng và lòng biết ơn đối với cô giáo Th.S Nguyễn Thị Xuân Hương giảng viên Khoa Công nghệ thông tin – Trường Đại học Dân lập Hải Phòng. Trong suốt thời gian học và làm đồ án tốt nghiệp, cô đã dành rất nhiều thời gian quí báu để tận tình chỉ bảo, hướng dẫn, định hướng cho em trong việc nghiên cứu, thực hiện đồ án. Em xin được cảm ơn các thầy, cô giáo Khoa Công nghệ thông tin của trường đã giảng dạy em trong quá trình học tập, thực hành, làm bài tập, cung cấp những kiến thức quý báu để em có thể tiếp cận và nghiên cứu những công nghệ, kỹ thuật mới. Xin cảm ơn các bạn bè và nhất là các thành viên trong gia đình đã tạo mọi điều kiện tốt nhất, động viên, cổ vũ tôi trong suốt quá trình học và làm đồ án tốt nghiệp. Mặc dù em đã tích cực cố gắng hoàn thành đồ án song với khuôn khổ đồ án tốt nghiệp không tránh khỏi thiếu sót. Vì vậy, em rất mong được sự thông cảm góp ý của các thầy cô và các bạn. Em xin chân thành cảm ơn! Hải Phòng, tháng 07 năm 2010 Sinh viên Nguyễn Hoàng Anh 2
  3. MỤC LỤC LỜI CẢM ƠN 1 MỤC LỤC 3 DANH MỤC HÌNH VẼ 5 DANH MỤC BẢNG BIỂU 6 DANH MỤC CHỮ VIẾT TẮT 7 MỞ ĐẦU 8 CHƢƠNG 1: TỔNG QUAN VỀ BÀI TOÁN XẾP THỜI KHÓA BIỂU VÀ CÁC PHƢƠNG PHÁP TIẾP CẬN 9 1.1 Tổng quan 9 1.2 ng Cao đẳng – Đại học 10 1.3 Các phương pháp tiếp cận hiện nay 12 CHƢƠNG 2: GIẢI THUẬT DI TRUYỀN VÀ TÍNH TOÁN TIẾN HÓA 15 2.1 Giải thuật di truyền 15 2.1.1 Ý tưởng 15 2.1.2 Đặc trưng 15 2.1.3 Cấu trúc 16 2.1.4 Biểu diễn bằng vector số thực 23 2.1.5 Một số cải tiến đơn giản của giải thuật di truyền 24 2.2 Tính toán tiến hóa (Evolutionary Computation) 25 2.2.1 Các chiến lược tiến hóa (Evolution Strategies – ES) 25 2.2.2 Lập trình tiến hóa (Evoluationary Programming – EP) 28 2.2.3 Lập trình di truyền (Genetic Programming – GP) 29 2.2.4 Chương trình tiến hóa (Evoluation Programmes – Eps) 31 CHƢƠNG 3: BÀI TOÁN THỜI KHÓA BIỂU – PHÂN TÍCH THIẾT KẾ HỆ THỐNG VÀ ÁP DỤNG GIẢI THUẬT TIẾN HÓA 35 3.1 Phân tích thiết kế hệ thống 35 3.1.1 Mô hình đào tạo theo tín chỉ 35 3.1.2 Quy trình xếp thời khóa biểu theo đào tạo tín chỉ 36 3.1.3 Sơ đồ tiến trình nghiệp vụ xếp thời khóa biểu 39 3.1.4 Mô hình nghiệp vụ 40 3.1.5 Biểu đồ ngữ cảnh 41 3
  4. 3.1.6 Biểu đồ phân rã chức năng 42 3.1.7 Danh sách hồ sơ dữ liệu sử dụng 43 3.1.8 Ma trận thực thể chức năng 43 3.1.9 Biểu đồ luồng dữ liệu 44 3.1.10 Mô hình liên kết thực thể (ER) 47 3.1.11 Mô hình quan hệ 50 3.2 Áp dụng giải thuật tiến hóa 54 3.2.1 Các yêu cầu cơ bản của thời khóa biểu theo đào tạo tín chỉ 54 3.2.2 Biểu diễn nhiễm sắc thể 55 3.2.3 Khởi tạo quần thể ban đầu 57 3.2.4 Xác định hàm thích nghi 60 3.2.5 Các toán tử di truyền 61 3.2.6 Quá trình chọn lọc 63 3.2.7 Thủ tục tiến hóa 64 CHƢƠNG 4: XÂY DỰNG ỨNG DỤNG MINH HỌA 65 4.1 Tổng quan về ứng dụng 65 4.2 Một số chức năng vào giao diện của ứng dụng 66 4.2.1 Chức năng nhập dữ liệu 66 4.2.2 Chức năng hiển thị thời khóa biểu 69 4.3 Thử nghiệm ứng dụng 70 4.3.1 Kết quả đạt được của ứng dụng 71 4.3.2 Bảng kết quả thực nghiệm 71 TÀI LIỆU THAM KHẢO 74 4
  5. DANH MỤC HÌNH VẼ Hình 2.1 Sơ đồ cấu trúc giải thuật di truyền 17 Hình 2.2 Bánh xe xổ số 20 Hình 2.3 Sơ đồ hình cây của hai nhiễm sắc thể v1 và v2 30 Hình 2.4 Nội dung thủ tục Eps 32 Hình 2.5 Hướng tiếp cận của GA cổ điển 33 Hình 2.6 Hướng tiếp cận của Eps 33 Hình 3.1 Quy trình xếp thời khóa biểu theo đào tạo tín chỉ 36 Hình 3.2 Sơ đồ tiến trình nghiệp vụ 39 Hình 3.3 Biểu đồ ngữ cảnh 41 Hình 3.4 Biểu đồ phân rã chức năng 42 Hình 3.5 Biểu đồ luồng dữ liệu mức 0 44 Hình 3.6 Biểu đồ luồng dữ liệu mức 1 tiến trình nhập dữ liệu 45 Hình 3.7 Biểu đồ luồng dữ liệu mức 1 tiến trình xếp TKB 46 Hình 3.8 Biểu đồ luồng dữ liệu mức 1 tiến trình xem TKB 46 Hình 3.9 Mô hình ER 48 Hình 3.10 Cơ sở dữ liệu 50 Hình 3.11 Cấu trúc một nhiễm sắc 56 Hình 3.12 Thời khóa biểu ban đầu theo trục ca-ngày 58 Hình 3.13 Thời khóa biểu hoàn chỉnh của phòng học 59 Hình 3.14 Toán tử đổi chỗ giáo viên 62 Hình 3.15 Toán tử đổi chỗ lớp môn học 63 Hình 3.16 Thủ tục tiến hóa cho bài toán xếp thời khóa biểu tín chỉ 64 Hình 4.1 Menu ứng dụng 65 Hình 4.2 Trang nhập lớp môn học 66 Hình 4.3 Trang nhập giáo viên dự kiến 67 Hình 4.4 Trang nhập phòng học dự kiến 68 Hình 4.5 Thời khóa biểu của phòng học 69 Hình 4.6 Thời khóa biểu giáo viên 69 Hình 4.7 Thời khóa biểu các lớp môn học 70 5
  6. DANH MỤC BẢNG BIỂU Bảng 1.1: So sánh giữa mô hình niên chế và tín chỉ: 11 Bảng 2.1 Mô tả cách hoạt động của bánh xe xổ số 21 Bảng 3.1 Nội dung công việc xếp thời khóa biểu 38 Bảng 3.2 Bảng phân tích xác định các chức năng tác nhân và hồ sơ 40 Bảng 3.3 Ma trận thực thể chức năng 43 Bảng 3.4 Các kiểu thực thể, thuộc tính và khóa 47 Bảng 3.5 DUKIEN_DT 51 Bảng 3.6 MON_CHO_CTDT 51 Bảng 3.7 LOP_MONHOC 51 Bảng 3.8 MON 52 Bảng 3.9 GV 52 Bảng 3.10 GV_DAY_MON 52 Bảng 3.11 TKB 53 Bảng 3.12 PHONG 53 Bảng 3.13 NGUYEN_VONG 53 Bảng 3.14 Danh sách các môn học dự kiến cho ngành CT13 57 Bảng 4.1 Bảng kết quả đánh giá thực nghiệm ứng dụng 72 6
  7. DANH MỤC CHỮ VIẾT TẮT GA – Genetic Algorithm – Giải thuật di truyền cổ điển TKB – Thời khóa biểu GV – Giáo viên DS – Danh sách HSDL – Hồ sơ dữ liệu SV – Sinh viên MH – Môn học t/tin – Thông tin QL – Quản lý HT – Hệ thống 7
  8. MỞ ĐẦU Thời khóa biểu của trường học là kế hoạch giảng dạy của giáo viên và học tập của sinh viên. Một bảng thời khóa biểu hợp lý giúp giáo viên thuận lợi, thoải mái khi lên lớp và giúp sinh viên thoải mái khi đăng ký học tập. Đã từ lâu, việc lập thời khóa biểu cho các lớp tín chỉ là vấn đề quan trọng của phòng đào tạo và phải luôn luôn hoàn thành trước khi triển khai cho sinh viên đăng ký học. Lập thời khóa biểu bằng phương pháp thủ công là công việc rất nặng nề, tốn nhiều thời gian và dễ vi phạm các ràng buộc về nghiệp vụ. Do vậy, khi áp dụng phải trải qua điều chỉnh vài lần mới có thể đạt được yêu cầu cơ bản. Các bài toán thời khóa biểu rất phong phú và đa dạng bởi những ràng buộc và yêu cầu đặc trưng của từng hệ đào tạo, thậm chí từng trường học. Bài toán thời khóa biểu thuộc lớp các bài toán tối ưu nên các giải thuật truyền thống khó giải quyết được trọn vẹn các yêu cầu nghiệp vụ và yêu cầu về thời gian thực hiện. Trong ba thập niên qua, có nhiều giải thuật được xây dựng và cải tiến để giải các bài toán tối ưu. Giải thuật di truyền và tính tiến hóa mô phỏng sự tiến hóa của tự nhiên của sinh học và gần đây nhất là phương pháp tối ưu hóa đàn kiến do Dorigo đề xuất là hướng tiếp cận hiện đại nhất. Cả hai loại giải thuật trên đã tỏ ra rất hiệu quả trong việc áp dụng giải quyết các bài toán tối ưu trong thực tế, tiêu biểu là bài toán lập thời khóa biểu trường học, là một bài toán thú vị và có tính thực tiễn cao. Xuất phát từ những vấn đề trên, đề tài “Xây dựng chương trình hỗ trợ xếp lịch thời khóa biểu cho đào tạo và học tập tín chỉ” được hình thành, đồ án tập trung nghiên cứu bài toán lập thời khóa biểu cho đào tạo tín chỉ, sử dụng giải thuật di truyền và phương pháp tính toán tiến hóa để giải bài toán cả về mặt lý thuyết lẫn xây dựng ứng dụng. Cấu trúc của đồ án như sau: Chương 1: Tổng quan về bài toán xếp thời khóa biểu và các phương pháp tiếp cận, Chương 2: Giải thuật di truyền và tính toán tiến hóa, Chương 3: Bài toán thời khóa biểu – Phân tích thiết kế hệ thống và áp dụng giải thuật tiến hóa, Chương 4: Xây dựng ứng dụng minh họa, Và cuối cùng là phần kết luận. 8
  9. CHƢƠNG 1: TỔNG QUAN VỀ BÀI TOÁN XẾP THỜI KHÓA BIỂU VÀ CÁC PHƢƠNG PHÁP TIẾP CẬN 1.1 Tổng quan Bài toán lập thời khóa biểu trường học là một trong những bài toán thú vị nhất trong lớp các bài toán tối ưu vì tính chất đa dạng về mô hình thời khóa biểu, có nhiều ràng buộc phức tạp và tính chất thực tiễn của nó. Bài toán thời khóa biểu là 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 (các môn học, bài giảng hoặc môn thi) và bao gồm các giáo viên và học sinh trong một khoảng thời gian định trước, và một tập các ràng buộc phải thỏa mãn của từng loại thời khóa biểu khác nhau. Tập ràng buộc bao gồm khả năng tham dự của học sinh, khả năng làm việc của giáo viên, số lượng và sức chứa của phòng học và các yêu cầu của các sự kiện. Phát biểu bài toán Mỗi trường có một danh sách các lớp học. Mỗi lớp có một danh sách xác định các giờ học trong một tuần, bao gồm tên môn học, tên giáo viên và số tiết. Các lớp học được phân bố trong các phòng học đã biết. Tìm một phương án phân bố giờ học, môn học và giáo viên thỏa mãn một số ràng buộc bắt buộc (ràng buộc cứng) và một số có thể có hoặc không các ràng buộc không bắt buộc thỏa mãn triệt để (ràng buộc mềm). Có thể nêu ra một số ràng buộc phổ biến sau: Ràng buộc cứng: Một giáo viên trong một tiết dạy không quá một lớp. Một lớp trong một tiết học có không quá một giáo viên. Một lớp trong một tiết học có không quá một môn. Không được lập lịch vào các giờ bận của giáo viên. Chẳng hạn, các tiết họp định kỳ của trưởng khoa, hay trưởng bộ môn Một số môn không được dạy quá k tiết trong một ngày học. Trong mỗi buổi học của mỗi lớp các tiết học liên tục (không có tiết nghỉ ở giữa) Trong mỗi buổi học, các tiết học của cùng một môn học liên tục (không được tách rời). 9
  10. Một số môn phải phân vào các giờ xác định. Ví dụ: tiết sinh hoạt là tiết đầu của buổi đầu tuần. Ràng buộc mềm: Các môn học có nhiều tiết trong tuần phải phân bố tương đối tập trung cho mỗi lớp. Một số giáo viên muốn dạy hoặc không dạy vào một số tiết hoặc một số buổi nhất định. Số buổi dạy của mỗi giáo viên là không quá nhiều (gom ngày dạy). Trường hợp một giáo viên dạy cả hai buổi thì nếu buổi sáng có tiết dạy thì buổi chiều ngày đó không phân lịch dạy, hoặc buổi sáng không phân lịch tiết cuối và buổi chiều không phân lịch tiết đầu 1.2 Bài toán thời khóa biểu ao đẳng – Đại học Đây là loại thời khóa biểu phức tạp vì tính biến động và tính chất đa dạng của loại hình đào tạo (học theo niên chế, học theo tín chỉ ). 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 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. Khóa học là điểm khác biệt của thời khóa biểu trường Đại học với trường Trung Học Phổ Thông. Các sinh viên tham dự khóa học, còn các lớp học ở trường phổ thông được tạo bởi tập học sinh. Ở trường Đại học, , hai khóa học có thể có trùng một số sinh viên tham dự và điều này tạo ra xung đột không thể lập lịch được trong một tiết học. Hơn nữa, các giảng viên thường chỉ dạy một khóa học hay một môn học trong một học kỳ. Cuối cùng, sức chứa của các phòng học là một yếu tố quan trọng trong việc lập lịch. Hiện nay, các trường Đại học ở Việt Nam thường đào tạo theo 2 mô hình: Mô hình lớp học niên chế: Sinh viên vào nhập học và các năm học được phân cố định vào các lớp học. Mô hình lớp học tín chỉ: Sinh viên được tự do đăng ký vào các lớp môn học đã được chuẩn bị trước của thời khóa biểu. Các lớp môn học này thực chất là các môn học được thiết kế thời khóa biểu giảng dạy chi tiết. Thông thường, sau khi thời khóa biểu của các lớp học này đã được lên kế hoạch thì sinh viên mới căn cứ vào thời khóa biểu cụ thể để đăng ký học. 10
  11. Bảng 1.1: So sánh giữa mô hình niên chế và tín chỉ: Đặc thù Lớp niên chế Lớp tín chỉ Bắc buộc phải phân lớp Không cần phân lớp cụ Tạo lớp học cho mỗi khóa học đầu thể, sinh viên tự đăng ký năm học Phân bố môn học và các Việc phân bố, tạo lớp tín Phân bố môn học bài giảng cho các lớp chỉ hàng năm tương đối học dễ dàng phức tạp Lập thời khóa biểu rất phức tạp vì phải chú ý Lập thời khóa biểu tương đến việc trùng giờ, trùng đối dễ dàng vì chỉ phải Lập TKB tiết trên lớp, giáo viên và quan tâm đến giáo viên phòng học, chưa kể các và phòng học phát sinh do ghép lớp, tách lớp Quản lý lớp học và sinh Quản lý việc lên lớp rất Quản lý giảng dạy viên dễ dàng phức tạp Rất phức tạp khi tổ chức Không cần ghép hay tách Lớp ghép, lớp tách ghép và tách các lớp các lớp tín chỉ niên chế Yêu cầu chung về phòng Yêu cầu phòng học đơn Phòng học học là lớn và phức tạp giản Ta nhận thấy, đối với lớp tín chỉ, việc tổ chức thời khóa biểu đơn giản hơn, nhưng rất phức tạp cho việc quản lý chuyên môn, đào tạo, còn đối với lớp niên chế, đơn giản về mặt tổ chức, quản lý chuyên môn, nhưng rất phức tạp trong việc lập thời khóa biểu. Trong trường hợp phải ghép hoặc tách lớp thì công việc lập thời khóa biểu lại càng phức tạp hơn. Vì nội dung đồ án đề cập về mô hình tín chỉ, nên phần này chỉ để cập đến hệ đào tạo theo tín chỉ. Đối với các trường Đại học có hình thức đào tạo theo tín chỉ, bài toán thời khóa biểu được phát biểu như sau: Có N môn học được các sinh viên đăng ký tham dự cần lập lịch vào một tuần gồm K tiết học tương ứng. Các môn học được tổ chức tại các phòng học đáp ứng đủ các điều kiện học tập của môn học đó. 11
  12. Một lời giải hay một thời khóa biểu chấp nhận được là tất cả các môn học đều được chia vào các tiết học và các phòng học tương ứng, đồng thời thỏa mãn các ràng buộc sau: Ràng buộc cứng: Không có sinh viên nào tham dự hơn một môn học trong cùng một thời gian. Phòng học có sức chứa và điều kiện để tổ chức dạy môn học đó. Chỉ có một môn học được tổ chức tại một phòng học trong một khoảng thời gian cho trước. Các môn học thường được học từ 2 đến 4 tiết mỗi ngày. Ràng buộc mềm: Hạn chế số sinh viên phải tham dự nhiều môn học liên tiếp nhau trong cùng một ngày. Hạn chế số sinh viên chỉ học đúng một môn học trong một ngày 1.3 Các phƣơng pháp tiếp cận hiện nay Trước hết, chúng ta cùng điểm qua các giải thuật truyền thống: Giải thuật vét cạn (tìm kiếm theo chiều rộng hoặc chiều sâu) về mặt nguyên tắc luôn tìm được nghiệm nếu bài toán có nghiệm. Nhưng trên thực tế, các bài toán thời khóa biểu không nên áp dụng phương pháp này, vì ta phải phát triển một không gian trạng thái cực lớn trước khi đi đến trạng thái đích. Do các hạn chế về thời gian tính toán và dung lượng bộ nhớ, không cho phép ta thực hiện được. Chẳng hạn, với bài toán thời khóa biểu cho 40 lớp học, mỗi lớp có 8 môn học, mỗi lớp có 25 tiết mỗi tuần thì không gian tìm kiếm rất lớn là 825*40 trường hợp. Rõ ràng, nếu dùng phương pháp vét cạn thì thời gian chạy rất lâu, khó chấp nhận được. Giải thuật leo đồi (Hill Climbing) sử dụng kỹ thuật nâng cấp lặp, áp dụng cho một số điểm đơn (điểm hiện hành) trong không gian tìm kiếm. Mỗi lần nâng cấp, một điểm trong lân cận của điểm hiện hành được chọn làm điểm kế tiếp, nếu nó cho kết quả tốt hơn của hàm mục tiêu. Việc tìm kiếm kết thúc khi không thể nâng cấp được nữa. Rõ ràng, giải thuật leo đồi chỉ cho kết quả tối ưu cục bộ, kết quả này phụ thuộc vào sự chọn lựa điểm xuất phát, mặt khác ta không có được thông tin về sai số giữa tối ưu cục bộ tìm được và tối ưu toàn cục. Mặc dù đã cải tiến bằng cách tăng số lượng điểm xuất phát (chọn ngẫu nhiên hoặc chọn theo kết quả của lần chạy trước), nhưng khi có nhiều cực trị 12
  13. địa phương thì khả năng tìm được kết quả tối ưu toàn cục của giải thuật leo đồi còn rất thấp. Tiếp theo chúng ta sẽ xem các cách tiếp cận hiện nay: Đã có nhiều giải thuật được đề xuất để giải các bài toán thời khóa biểu. Các giải thuật này tìm được lời giải gần tối ưu và là một trong các xu thế phát triển hiện nay đối với các bài toán chưa thể tìm được lời giải tối ưu thực sự. Các giải thuật này đều mô phỏng theo tự nhiên như giải thuật luyện kim, giải thuật di truyền, phương pháp tính toán tiến hóa, giải thuật hệ kiến trong đó, tính toán tiến hóa và tối ưu hóa đàn kiến tỏ ra là phương pháp hữu hiệu nhất. Trong giải thuật luyện kim (Annealing Algorithm), người ta dùng kỹ thuật thay đổi entropy của hệ và điều khiển tốc độ hội tụ của quần thể bằng cách biến đổi nhiệt động học với một tham số nhiệt độ T toàn cục. Để hạn chế sự tối ưu cục bộ và tăng khả năng khám phá không gian tìm kiếm, người ta dùng thủ thuật giảm từng bước nhiệt độ T (đến một mức nào đó). Tuy nhiên, do T chỉ giảm đến một mức nhất định, nên kỹ thuật luyện kim không tránh khỏi hạn chế trong việc khám phá không gian tìm kiếm và sự hội tụ địa phương. Giải thuật di truyền và tính toán tiến hóa kết hợp ý tưởng của giải thuật leo đồi và luyện kim. Đặc trưng của giải thuật này là duy trì một tập các lời giải tiềm năng (gọi là tập các cá thể hay quẩn thể), khuyến khích việc hình thành và trao đổi thông tin giữa các cá thể trong quần thể thông qua phép lai và phép biến dị. Một quá trình tiến hóa được thực hiện trên một quần thể thực chất là sự tìm kiếm trong một không gian các lời giải tiềm năng. Sự tìm kiếm này đòi hỏi sự cân bằng giữa hai mục tiêu: tìm lời giải tốt nhất và khám phá không gian tìm kiếm mới. Giải thuật tối ưu đàn kiến (ACO – Ant Colony Optimization) do Dorigo đề xuất là phương pháp tiếp cận hiện đại nhất. Một thành phần ngẫu nhiên trong ACO cho phép các con kiến xây dựng được một lượng lớn các lời giải khác nhau hơn các phương pháp khác. Tại cùng một thời gian, việc sử dụng các thông tin kinh nghiệm sẽ hướng dẫn các con kiến tìm kiếm được các lời giải hứa hẹn. Quan trọng hơn, kinh nghiệm tìm kiếm của con kiến sẽ được sử dụng để học tăng cường trong quá trình lặp xây dựng giải thuật. Thêm vào đó, việc tham gia của đàn kiến kiến làm cho giải thuật ACO có được một tập hợp các tác nhân lặp hiệu quả đề giải quyết bài toán. Tuy nhiên, giải thuật tối ưu đàn kiến phức tạp hơn phương pháp tính toán tiến hóa nhiều. Hiện nay giải thuật di truyền và giải thuật tối ưu đàn kiến là hai phương pháp được sử dụng nhiều nhất để giải quyết bài toán lập thời khóa biểu. Xét về thời gian thực hiện, chi phí thực hiện thì giải thuật tối ưu đàn kiến tốt hơn nhưng cũng phức 13
  14. tạp hơn giải thuật di truyền. Trên thực tế việc lập thời khóa biểu chỉ diễn ra khoảng hai đến ba lần trong một năm phụ thuộc vào chương trình đào tạo của từng trường cụ thể, nên thời gian và chi phí cũng không ảnh hưởng nhiều tới việc lập thời khóa biểu, vì vậy trong đồ án này để đơn giản em sử dụng giải thuật di truyền để giải quyết bài toán lập thời khóa biểu cho đào tạo tín chỉ. 14
  15. CHƢƠNG 2: GIẢI THUẬT DI TRUYỀN VÀ TÍNH TOÁN TIẾN HÓA 2.1 Giải thuật di truyền 2.1.1 Ý tƣởng Giải thuật di truyền (GA - Genetic Algorithm) là mô phỏng theo quá trình tiến hóa tự nhiên của sinh vật theo thuyết Darwin. Trong quá trình tiến hóa, mỗi cá thể đều phải tự tìm cách thích nghi tốt nhất với môi trường sống rất phức tạp và luôn luôn thay đổi. Cá thể nào có khả năng thích nghi với môi trường cao hơn thì sẽ có khả năng tồn tại, phát triển và sinh sản cao hơn, ngược lại cá thể nào có khả năng thích nghi thấp sẽ có nhiều nguy cơ bị tiêu vong hoặc phát triển chậm. Sự thích nghi đó được đúc kết và ghi lại trong cấu trúc của nhiễm sắc thể của chúng. Việc giải bài toán thực tế có thể xem là việc tìm kiếm trong một không gian các lời giải tiềm năng nhằm tìm ra lời giải tốt nhất hoặc chấp nhận được mà ta có thể gọi là quá trình tối ưu hóa. Đối với không gian tìm kiếm nhỏ, đơn giản nhất là dùng kỹ thuật “vét cạn”, nghĩa là liệt kê toàn bộ lời giải tiềm năng, sau đó kiểm tra điều kiện để chọn ra lời giải. Đối với không gian tìm kiếm khá lớn thì kỹ thuật vét cạn có độ phức tạp rất lớn, khó chấp nhận được. Khi đó, giải thuật di truyền được xem là rất thích hợp cho việc giải quyết bài toán tìm kiếm lời giải tối ưu. GA không chú trọng đến giải pháp duy nhất và chính xác như các phương thức cổ điển, trái lại GA xét đến toàn bộ các giải pháp và chọn lấy giải pháp tương đối tốt nhất. GA dựa trên tính ngẫu nhiên như trong thế giới tự nhiên của sinh vật, nhưng được hướng dẫn bởi hàm thích nghi. 2.1.2 Đặc trƣng GA làm việc với một mã hóa của tập hợp tham số mà không phải một tham số. GA tìm kiếm từ một quần thể các điểm chứ không phải một điểm hoặc một vài điểm như phương pháp tìm kiếm leo đồi. GA đánh giá thông tin với hàm mục tiêu mà không đưa vào đạo hàm hay thông tin bổ sung khác. GA sử dụng các luật biến đổi theo xác suất mà không sử dụng luật quyết định. 15
  16. 2.1.3 Cấu trúc GA sử dụng ý tưởng và các thuật ngữ trong di truyền học như được trình bày sau đây. Trong tự nhiên, mỗi cá thể có các tính chất và đặc điểm riêng được thể hiện ra ngoài gọi là kiểu hình. Kiểu hình này được quyết định bởi các cấu trúc gene trong cơ thể, gọi là kiểu gene (genotype). Các gene tạo thành các nhiễm sắc thể, mỗi tế bào có tập hợp các nhiễm sắc thể như nhau. Các nhiễm sắc thể là các chuỗi DNA hoạt động như một mô hình cho toàn bộ cơ thể. Sự đa dạng về kiểu gene của các cá thể dẫn đến sự đa dạng về kiểu hình của một quần thể sinh học. Quá trình phát triển của mỗi quần thể tuân theo quy luật chọn lọc của tự nhiên mà tiến hóa qua các thế hệ nối tiếp nhau. Trong đó, các hậu duệ được sinh ra từ thế hệ trước thông qua quá trình sinh sản ( di truyền và biến dị) cạch tranh tự nhiên với nhau, cá thể nào có kiểu hình (và do đó là kiểu gene) thích nghi cao hơn trong môi trường phát triển thì sẽ có khả năng cao hơn trong tồn tại và sinh sản con cháu. Do đó, kiểu gene này sẽ tiến hóa và hoàn thiện. Quá trình tiến hóa này được lặp đi lặp lại, các cá thể có kiểu gene phù hợp sẽ sống sót và phát triển, các cá thể yếu sẽ bị loại bỏ dần. GA là kỹ thuật tối ưu dựa trên khái niệm chọn lọc tự nhiên và di truyền. Do vậy, lời giải của bài toán được trình bày như các gene trong nhiễm sắc thể. GA mô tả một nhóm các lời giải tiềm năng được đề cử. Qua tiến hóa và chọn lọc tự nhiên các nhiễm sắc thể với độ thích nghi tốt hơn sẽ xuất hiện. Chọn lọc tự nhiên đảm bảo cho cá thể có độ thích nghi tốt nhất sẽ được truyền lại cho các thế hệ con cháu (các quần thể tương lai). Phép lai ghép kết hợp các gene từ hai cá thể bố mẹ để tạo thành hai cá thể con mới với độ thích nghi có chiều hướng cao hơn bố mẹ. Phép biến dị cho phép tạo ra chất liệu di truyền mới, tạo ra những đột phá trong tìm kiếm thông tin mới. GA cung cấp sự cải tiến thế hệ về độ thích nghi của các cá thể và sau nhiều thế hệ sẽ tạo ra các cá thể chứa những thiết lập biến đổi đã được tối ưu. Mỗi cá thể trong GA thường chỉ gồm một nhiễm sắc thể. Do vậy thuật ngữ cá thể và nhiễm sắc thể được dùng không phân biệt ngữ nghĩa. 16
  17. t=0 Khởi tạo P(t) Đánh giá độ thích nghi của P(t) t=t+1 Chọn Q(t) từ P(t-1) // bởi bánh xe xổ số Tái tạo P(t) từ Q(t) // bởi các toán tử di truyền Đánh giá độ thích nghi của P(t) và chọn cá thể tốt nhất N Kiểm tra điều kiện kết thúc thuật toán thỏa mãn chưa? Y Kết thúc Hình 2.1 Sơ đồ cấu trúc giải thuật di truyền Trong đó: P(t) là quần thể tại thế hệ thứ t. Q(t) là quần thể trung gian. 2.1.3.1 Nhiễm sắc thể và quần thể Trong GA, mỗi cá thể (hay nhiễm sắc thể) được mã hóa bởi các chuỗi nhị phân. Ví dụ: một nhiễm sắc thể gồm 8 gene như sau 17
  18. 1 0 0 1 0 1 1 0 Mỗi cá thể (một nhiễm sắc thể cụ thể) biểu thị một lời giải tiềm năng của bài toán. Một quá trình tiến hóa được thực hiện trên một quần thể (một tập hợp các cá thể) tương đương với sự tìm kiếm trong một không gian các lời giải tiềm năng. Sự tìm kiếm này đòi hỏi sự cân bằng giữa hai mục tiêu: tìm lời giải tốt nhất và khám phá không gian tìm kiếm. GA thực hiện việc tìm kiếm theo nhiều hướng bằng cách duy trì một tập lời giải tiềm năng, khuyến khích sự hình thành và trao đổi thông tin giữa các hướng. Tập lời giải trải qua quá trình tiến hóa và cuối cùng cho ta một lời giải đủ tốt theo yêu cầu. Tại mỗi thế hệ, các lời giải tương đối tốt được tái sinh, và các lời giải tương đối xấu bị loại bỏ dần. Để đánh giá mức đ tốt xấu của từng lời giải, người ta xây dựng hàm thích nghi, hàm này đóng vai trò như môi trường sống trong thuyết tiến hóa của darwin. Mã hóa nhiễm sắc thể: Biểu diễn mã nhị phân của mỗi lời giải tiềm năng (b a )*10 p 2mi 1 Ta có công thức: i i [2.1] Trong đó : -p 10 sai số đến p chữ số thập phân bi là điểm cuối trên miền giới hạn ai là điểm đầu trên miền giới hạn mi là độ dài chuỗi nhị phân Ví dụ: Tìm giá trị cực đại của hàm số hai biến: f(x1,x2)= 10 + x1 * sin x1 + x2 * sin x2 trên miền -1 ≤ x1 ≤ 3 ; 3 ≤ x2 ≤ 5 với sai số các biến là 10-2 2 8 9 Vì: b1 – a1 = 3 – (-1) = 4; 4*10 = 400 và 2 < 400 <2 nên cần 9 gene để biểu diễn x1 7 8 Tương tự ta có 2 < 200 < 2 nên cần 8 gene để biểu diễn x2 Do vậy, m = 17 là độ dài chuỗi của một nhiễm sắc thể. Giải mã nhiễm sắc thể: Chuyển đổi các chuỗi nhị phân về dạng số thập phân. (b , , b ) j Với mỗi đoạn gene mi 1 0 ta xác định ki theo cơ số 10: (bj*2 )10 mi 1 j ki (bj *2 )10 j 0 18
  19. và có: (bi ai ) xi ai ki * mi 2 1 [2.2] Ví dụ trên ta có: x1 biểu diễn bởi 9 gene x2 biểu diễn bởi 8 gene 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 2 4 5 8 k1 = 1*2 + 1*2 + 1*2 + 1*2 = 308 9 x1 = -1 + 308*(3 – (-1)) / (2 – 1) = 1.41 k2 = 1*20 + 1*21 + 1*22 =7 x2 =3 + 7 *(5 – 3) / (28 – 1) = 3.05 2.1.3.2 Hàm đánh giá Hàm đánh giá (eval) trên tập nhiễm sắc thể để đánh giá độ thích nghi của mỗi cá thể : eval(z) = f(x), trong đó x là vector tương ứng với z Ví dụ hàm f(x1,x2)= 10 + x1 * sin x1 + x2 * sin x2 ở ví dụ trên chính là hàm đánh giá độ thích nghi. 2.1.3.3 Thủ tục chọn lọc (Selection) Các cá thể được chọn lọc theo độ thích nghi của chúng để tham gia vào pha tiếp theo của quá trình tiến hóa. Cá thể có độ thích nghi cao hơn có cơ hội được chọn nhiều hơn, nghĩa là có nhiều con cháu trong các thế hệ tiếp theo. Phép chọn lọc các cá thể trong mỗi quần thể được thực hiện nhờ bánh xe xổ số (Roulette Wheel). Với mỗi quần thể P(t – 1) gồm N nhiễm sắc thể: P(t – 1) = {v1,v2, vn} ta xây dựng bánh xe xổ số như sau: Đánh giá độ phù hợp toàn phần, còn gọi là tổng độ thích nghi của quần thể. N F eval(vi ) i 1 [2.3] Tính xác suất chọn lọc pi của mỗi cá thể vi: eval(vi ) pi F [2.4] 19
  20. Tính xác suất tích lũy qi cho mỗi cá thể vi: i qi p j ,i 1,2, N j 1 [2.5] Quá trình chọn lọc quần thể Q(t) từ P(t – 1) dựa vào bánh xe xổ số được thực hiện như sau: Đối với mỗi số tự nhiên k = 1, 2, N phát sinh một số thực ngẫu nhiên r [0,1] k Nếu rk ≤ q1 thì chọn cá thể v1, ngược lại, chọn cá thể vi sao cho qi – 1 < rk ≤ qi ; 2 ≤ i ≤ N Với cách thực hiện như thế, có thể có một số cá thể được chọn nhiều lần và Q(t) vẫn được xem là có N phần tử. Các cá thể tốt được chọn nhiều lần, các cá thể trung bình thì bình ổn và các cá thể xấu bị giảm dần. Minh họa bánh xe xổ số với quần thể có 5 cá thể: Cá thể 1, 20% Cá thể 5, 30% Cá thể 2, 25% Cá thể 4, 15% Cá thể 3, 10% Hình 2.2 Bánh xe xổ số Cá thể 1 có xác suất chọn lọc là 20%, nghĩa là mỗi lần quay bánh xe xổ số, nó có khả năng được chọn là 0.2. Tương tự như vậy cho các cá thể thứ 2, 3, 4, 5. Với ví dụ trên ta có f(x1,x2)= 10 + x1 * sin x1 + x2 * sin x2 trên miền -1 ≤ x1 ≤ 3 ; 3 ≤ x2 ≤ 5 với sai số các biến là 10-2 m = 17 là độ dài chuỗi của một nhiễm sắc thể, x1 biểu diễn bởi 9 gene x2 biểu diễn bởi 8 gene. 20
  21. Khởi tạo ngẫu nhiên 3 cá thể: v1 = (10011010000000111) tương ứng với x1 = 1.41; x2 = 3.05; eval (v1) =12.68; v2 = (11100010010011011) tương ứng với x1 = 2.54; x2 = 4.22; eval (v2) =14.78; v3 = (00001000001100100) tương ứng với x1 = 0.87; x2 = 3.78; eval (v3) =10.94; Cá thể v2 là tốt nhất với eval (v2) =14.78 và độ thích nghi toàn phần của quần thể là F = 38.4 Giả sử các ri ngẫu nhiên như sau: r1 = 0.52; r2 = 0.17; r3 = 0.7 Bảng 2.1 Mô tả cách hoạt động của bánh xe xổ số Xác suất Xác suất Số ngẫu Cá thể Đánh số STT chọn lọc pi tích lũy qi nhiên ri đƣợc chọn lại 1 0.33 0.33 0.52 v2 u1 2 0.38 0.71 0.17 v1 u2 3 0.28 1 0.7 v2 u3 2.1.3.4 Quá trình tái tạo Quá trình tái tạo dựa trên các toán tử di truyền là Phép lai và biến dị. Cho trước xác suất lai pc và xác suất biến dị pm Với mỗi cá thể vi thuộc Q(t), i=1, 2, N, phát sinh một số ngẫu nhiên r [0,1]. Nếu r < pc thì vi được đưa vào tập lai. Tập này chia thành cặp, nếu lẻ thì thêm hoặc bớt ngẫu nhiên một cá thể khác và áp dụng phép lai để tạo hậu duệ thay thế cho chúng. Sau khi lai ghép, đối với mỗi gene của cá thể, phát sinh một số ngẫu nhiên r [0,1]. Nếu r < pm thì gene đó được biến dị Quá trình trên cho ta quần thể P(t) của thế hệ t và được đánh giá để chọn cá thể có giá trị thích nghi tốt nhất. Phép lai hay trao đổi chéo: Kết hợp các đặc tính trên nhiễm sắc thể của bố và mẹ để tạo thành hai cá thể con mới, bằng cách hoán đổi các đoạn gene tương ứng trên các nhiễm sắc thể của bố và mẹ. Phép lai nhằm nâng cao chất lượng cá thể, do vậy sẽ ảnh hưởng đến tốc độ hội tự của quá trình tiến hóa. 21
  22. Với hai nhiễm sắc thể tùy ý: x = (x1, x2, , xm) y = (y1, y2, , ym) Chọn điểm lai k [1, m-1] (k chọn trước hoặc ngẫu nhiên), ta sẽ sinh được hai cá thể mới: x’ = (x1, , xk, yk+1, , ym) y’ =(y1, , yk, xk+1, , xm) Ví dụ: Parent1 0 1 0 1 1 0 0 1 0 1 Parent2 1 1 0 0 0 1 0 1 1 0 Nếu thực hiện lai ghép sau gene thứ 5, sẽ tạo ra hai con như sau: Child1 0 1 0 1 1 1 0 1 1 0 Child2 1 1 0 0 0 0 0 1 0 1 Phép biến dị: Là sự sửa đổi một hoặc một vài gene của một nhiễm sắc thể. Toán tử biến dị làm tăng nhanh quá trình hội tụ, nhưng có thể làm tăng đột ngột và không gây tác dụng gì hoặc làm hội tụ sớm đến một lời giải dưới tối ưu. Trong GA, mỗi cá thể biểu diễn bởi một chuỗi nhị phân, nên biến dị tại một vị trí nào đó là sự đảo bit tại vị trí đó. Ví dụ: Parent 0 1 0 1 1 0 0 1 0 1 Sau khi biến dị tại vị trí 6: Child 0 1 0 1 1 1 0 1 0 1 2.1.3.5 Điều kiện kết thúc: Là điều kiện để kết thúc quá trình tiến hóa của quần thể. Tùy theo bài toán mà chọn cách kết thúc khác nhau. Người ta thường dùng một trong các cách sau: Kết thúc theo kết quả: Khi đạt đến mức giá trị yêu cầu thì dừng. Kết thúc dựa vào số thế hệ: xác định trước số thế hệ cần tiến hóa, khi trải qua đủ số thế hệ thì dừng, không cần biết kết quả như thế nào. Tính theo thời gian: quá trình kết thúc sau một khoảng thời gian quy định trước, không cần biết số thế hệ đã trải qua cũng như kết quả. 22
  23. Tổ hợp nhiều cách: dùng nhiều phương án khác nhau cho vấn đề. Chẳng hạn: chạy theo số thế hệ, đánh giá và cho chạy tiếp theo kết quả 2.1.4 Biểu diễn bằng vector số thực Đối với các bài toán khó có miền chấp nhận lớn và đòi hỏi sai số nhỏ thì độ dài của mỗi nhiễm sắc thể theo phương pháp GA cổ điển trình bầy ở trên là rất lớn, nên việc áp dụng GA rất khó khăn. Do vậy, người ta cải tiến cách biểu diễn nhiễm sắc thể bằng vector thực để giải bài toán. Trong cách biểu diễn này, người ta dùng các vector thực trong miền chấp nhận được (thuộc tập M) làm nhiễm sắc thể và thiết kế các nhóm toán tử di truyền cho thích hợp với cách biểu diễn này mà vẫn giữ nguyên thủ tục GA đã đặc tả ở trên. Dưới đây giới thiệu một số toán tử dễ dùng. Các toán tử lai: Lai đơn giản: toán tử này thực hiện tráo đổi hai nhóm gene tương tự như GA cổ điển. x = (x1, x2, , xm) và y = (y1, y2, , ym) Chọn điểm lai k [1, m – 1] (chọn trước hoặc ngẫu nhiên), ta sẽ sinh được hai cá thể mới: x’ = (x1, , xk, yk+1, , ym) và y’ = (y1, , yk, xk+1, , xm) Lai số học đơn: Nếu lai hai vector: x = (x1, , xm) và y = (y1, , ym) với điểm chọn ở vị trí k, thì ta được: x’ = (x1, xk’, , xm) và y’ = (y1, , yk’, , ym) trong đó, xk’ = a*xk + (1 – a)*yk và yk’ = a*yk + (1 – a)*xk với a (0,1) là một số cho trước hoặc chọn ngẫu nhiên. Lai số học toàn cục: Nếu lai hai vector x = (x1, , xm) và y = (y1, , ym) thì được: X’ = a*x + (1 – a)*y và y’ = a*y + (1 – a)*x với a (0,1) là một số cho trước hoặc chọn ngẫu nhiên. Các toán tử biến dị: Biến dị đều: giả sử gene xk biến dị thành xk’ thì xk’ là số ngẫu nhiên phân bố đều trên miền chấp nhận được [ak, bk] của nó. Biến dị không đều: giả sử gene xk biến dị thành xk’ thì xk’ = xk + (t, xk), trong đó (t, xk) là số ngẫu nhiên phân bố không đều trên đoạn [ak – xk, bk – xk] và hội tụ theo xác suất về 0 khi t tăng ra vô cùng, tham số t chỉ vòng lặp. 23
  24. 2.1.5 Một số cải tiến đơn giản của giải thuật di truyền Cùng với sự phát triển của thuật toán di truyền các nhà nghiên cứu đã đề xuất một số phương pháp chọn lọc, lai ghép và đột biến khác. 2.1.5.1 Chọn lọc cá thể Theo thuyết tiến hóa của Darwin, nhiễm sắc thể tốt nhất sẽ tồn tại và tạo ra các cá thể con mới. Có nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất. Chọn lọc Roulette (Roulette Wheel Selection) Chọn lọc xếp hạng (Rank Selection) Chọn lọc cạnh tranh (Tournament Selection) 2.1.5.2 Toán tử lai ghép Lai ghép nhằm nâng cao kết quả cá thể, do đó, toán tử lai ghép sẽ tạo điều kiện cho tiến trình hội tụ nhanh hay chậm. Còn tùy thuộc vào cách tổ chức và phân bố các nhiễm sắc thể mà chúng ta có xác suất lai ghép nhanh hay chậm. Sau đây là vài phương pháp lai ghép thông dụng trong giải thuật di truyền: Lai ghép ánh xạ từng phần (PMX Partial Mapped Crossover) Lai ghép có trật tự (OX Order Crossover) Lai ghép dựa trên vị trí (Position Based Crossover) Lai ghép dựa trên thứ tự (Order Base Crossover) Lai ghép có chu trình (CX Cycle Crossover) Lai ghép thứ tự tuyến tính (LOX Linear Order Crossover) 2.1.5.3 Toán tử đột biến Cũng giống như lai ghép, toán tử đột biến làm tăng nhanh quá trình hội tụ, nhưng tăng một cách đột ngột, cũng có khi sẽ không gây tác dụng gì một khi không thành công. Không ai có thể đánh giá được phương pháp đột biến nào tốt hơn, do đó có một vài phương pháp đơn giản, cũng có vài trường hợp khá phức tạp. Người ta thường chọn một trong những phương pháp sau : Đột biến đảo ngược (Inversion Mutation) Đột biến chèn (Insertion Mutation) Đột biến thay thế (Displacement Mutation) Đột biến tương hỗ (Reciprocal Exchange Mutation) Đột biến chuyển dịch (Shift Mutation) 24
  25. 2.2 Tính toán tiến hóa (Evolutionary Computation) Giải thuật di truyền cổ điển dùng phương pháp mã hóa nhị phân cho các nhiễm sắc thể, vì vậy khi áp dụng cho các bài toán có miền chấp nhận được lớn trong không gian nhiều chiều và yêu cầu độ chính xác cao, thì các nhiễm sắc thể sẽ có kích thước rất lớn nên gặp nhiều khó khăn khi thực hiện. Ví dụ : xét hàm số hai biến: F(x1, x2) = 10 + x1*sin x1 + x2*sin x2 trên miền -5 ≤ x1 ≤ 5; -10 ≤ x2 ≤ 10 với sai số các biến là 10-4 Biểu diễn nhiễm sắc thể theo GA cổ điển 4 5 16 5 17 Vì b1 – a1 =5 – (-5) = 10; 10*10 =10 và 2 < 10 <2 nên cần 17 gene để biểu diễn x1 Tương tự, b2 – a2 = 10 – (-10) =20; 2*105 và 217 < 2*105 <218 nên cần 18 gene để biểu diễn x2 Nên độ dài của chuỗi là 35 là khá lớn. Đặc biệt, khi bài toán có nhiều ràng buộc phức tạp, thì các toán tử di truyền truyền thống tỏ ra kém hiệu quả. Trong những năm vừa qua, rất nhiều hướng tiếp cận dựa trên nguyên lý tiến hóa và chọn lọc tự nhiên được nghiên cứu và phát triển. Các hướng tiếp cận tập trung vào một số vấn đề chính sau đây; các nhiễm sắc thể có độ dài không cố định và có cấu trúc đa dạng, phức tạp hơn chuỗi nhị phân, chẳng hạn nhiễm sắc thể có cấu trúc mảng đa chiều, các toán tử di truyền được thay đổi để phù hợp với điều kiện của bài toán cụ thể. Phần lớn các nhà nghiên cứu đã cải tiến giải thuật di truyền bằng cách dùng biểu diễn không thuộc dạng chuỗi, hoặc thiết kế các toán tử di truyền đặc biệt để phù hợp với bài toán cụ thể cần giải. Sự cần thiết của việc kết hợp các thông tin đặc thù của bài toán và giải thuật di truyền đã được thừa nhận trong nhiều công trình nghiên cứu và nhiều bài báo khoa học trong thập kỷ qua. Các phát triển của GA cổ điển được đề xuất và ứng dụng để giải các bài toán khó, đặc thù trong thực tiễn mang các tên gọi khác nhau như: Các chiến lược tiến hóa, lập trình tiến hóa, lập trình di truyền, các chương trình tiến hóa và tất cả chúng đều có một tên gọi chung là tính toán tiến hóa. 2.2.1 Các chiến lƣợc tiến hóa (Evolution Strategies – ES) ES mô phỏng các nguyên tắc tiến hóa trong tự nhiên để tạo ra một phương pháp giải các bài toán tối ưu với các tham số thay đổi liên tục, và gần đây mở rộng 25
  26. cho các bài toán rời rạc. Trong đó, cách biểu diễn gene trên các vector thực được sử dụng để xử lý các ràng buộc và giảm khối lượng xử lý dữ liệu. Nội dung của chiến lược tiến hóa: 2.2.1.1 Chiến lƣợc tiến hóa hai thành viên Chiến lược này được dùng trên quẩn thể chỉ gồm một cá thể và chỉ áp dụng một toán tử di truyền là biến dị. Sau khi biến dị ta có một cá thể con. Cá thể con này đấu tranh sinh tồn với cá thể mẹ sinh ra nó trong pha chọn lọc. Một trong hai cá thể mẹ và con này sẽ được chọn cho thế hệ tiếp theo tùy thuộc độ thích nghi của chúng. ES được ký hiệu là (1+1) – ES Biểu diễn nhiễm sắc thể: mỗi cá thể biểu diễn ở dạng v = (x, ), trong đó x và là các vector thực, x là đại diện cho một điểm tìm kiếm, là vector các độ lệch tiêu chuẩn. Tập lời giải: (1+1) – ES có quẩn thể chỉ gồm một cá thể. Xác định hàm thích nghi: Hàm thích nghi và tổng độ thích nghi được xác định tương tự như GA cổ điển, nó được đo dựa vào giá trị của hàm phù hợp. Các toán tử di truyền: Chỉ gồm phép biến dị, và được thực hiện như sau: Thay x bởi x’= x + N(0, ) là vector các số Gausse ngẫu nhiên độc lập, có trung bình là 0 và có độ lệch tiêu chuẩn là . Phép chọn lọc: Nếu cá thể con có độ thích nghi cao hơn cá thể mẹ và thỏa mãn mọi ràng buộc thì nó thay thế cá thể mẹ, nếu không nó sẽ bị loại bỏ và quẩn thể không thay đổi. Ví dụ: Cho hàm số f(x1, x2) = 21.5 + x1*sin(4π*x1)*x2*sin(20π*x2) miền xác định như sau: -3 ≤ x1 ≤ 12.1; 4.1 ≤ x2 ≤ 5.8 Nhiễm sắc thể có dạng (x, ) trong đó x = (x1, x2) là một điểm trong không gian tìm kiếm ( -3 ≤ x1 ≤ 12.1; 4.1 ≤ x2 ≤ 5.8) = ( 1, 2) biểu diễn hai độ lệch tiêu chuẩn được dùng cho phép biến dị. Giả sử tại thế hệ thứ t, ta có tập lời giải với một cá thể duy nhất là: (xt, ) = ((5.3, 4.9), (1.0, 1.0)) Giả sử phép biến dị cho ta kết quả sau: t+1 t x1 = x1 + N (0, 1.0) = 5.3 + 0.4 = 5.7 t+1 t x2 = x2 + N (0, 1.0) = 4.9 – 0.3 = 4.6 26
  27. Hàm thích nghi chính là hàm f đã cho, ta có: f(xt) = f(5.3, 4.9) = 18.3837 f(xt+1) = f(5.7, 4.6) = 24.8495 t t+1 t+1 t+1 Phép chọn lọc vì f(x ) < f(x ) và x1 và x2 đều nằm trong miền xác định, nên cá thể con sẽ được chọn thay thế cá thể mẹ ở thế hệ thứ t + 1. 2.2.1.2 Chiến lƣợc tiến hóa đa thành viên: ký hiệu (µ + 1) – ES Cấu trúc nhiễm sắc thể: cấu trúc nhiễm sắc thể và hoạt động giống như (1 + 1) – ES Tập lời giải: có nhiều cá thể. Các toán tử di truyền Phép lai: Mọi cá thể trong quần thể có cùng xác suất ghép cặp để tham gia lai ghép. Hai cá thể cha mẹ được chọn ngẫu nhiên, sau phép lại cho ra một cá thể con Toán tử biến dị và quy tắc điều chỉnh vẫn giống như chiến lược tiến hóa hai thành viên (1 + 1) – ES Phép chọn lọc : giống như (1 + 1) – ES ở chỗ trong mỗi thế hệ chỉ sinh đúng một cá thể con, và cá thể yếu nhất trong (pop_size + 1) cá thể sẽ bị loại bỏ. 2.2.1.3 Chiến lƣợc tiến hóa đa thành viên cải tiến Gồm hai dạng sau: ( + µ) – ES : trong mỗi thế hệ, µ cá thể cha mẹ sinh ra cá thể con, sau đó quẩn thể + µ sẽ loại bỏ cá thể trong quá trình chọn lọc. (µ, ) – ES : trong mỗi thế hệ, µ cá thể cha mẹ sinh ra cá thể con (µ < ), sau đó sẽ chọn lọc µ cá thể từ cá thể con trong quá trình chọn lọc. So sánh chiến lược tiến hóa và giải thuật di truyền cổ điển ES và GA cổ điển giống nhau ở điểm đều duy trì một tập lời giải tiềm năng, sau đó trải qua các quá trình tiến hóa để tìm ra lời giải tốt nhất. Điểm khác biệt giữa ES và GA là: Cách biểu diễn cá thể : ES biểu diễn các cá thể bằng các vector thực, còn GA cổ điển dùng các vector nhị phân. Quá trình chọn lọc: trong ES, thủ tục chọn lọc có tính chất tất định – chọn µ cá thể từ + µ cá thể trong - ( + µ) – ES, hoặc từ cá thể trong (µ, ) – ES và không có sự lặp lại. Còn trong GA cổ điển thì cá thể tốt vẫn có thể được chọn nhiều lần. 27
  28. Trật tự các toán tử: trong ES, thủ tục chọn lọc được thực hiện sau các phép biến đổi gene, còn trong GA cổ điển thì ngược lại. Trong những năm gần đây, khoảng cách giữa hai hướng tiếp cận ES và GA cổ điển càng gần nhau hơn. 2.2.2 Lập trình tiến hóa (Evoluationary Programming – EP) 2.2.2.1 Ý tƣởng Lập trình tiến hóa hướng tới sự tiến hóa của trí tuệ nhân tạo trong việc phát triển khả năng dự đoán các thay đổi của môi trường. Môi trường được mô tả bằng một chuỗi ký hiệu (từ một bảng chữ cái hữu hạn), giải thuật tiến hóa cần đưa ra một ký hiệu mới, ký hiệu mới này làm cực đại hàm do độ chính xác của dự đoán. 2.2.2.2 Biểu diễn nhiễm sắc thể Các cá thể của quần thể trong EP được biểu diễn bởi các automat hữu hạn, ký hiệu là FSM (Finite State Machine) Tập lời giải: EP duy trì một quần thể các FSM, mỗi FSM đại diện cho một lời giải của bài toán. Hàm thích nghi: Mỗi FSM được đo độ thích nghi bằng cách thử chúng trong môi trường, nghĩa là cho các FSM khảo sát các ký hiệu đã gặp. Các toán tử di truyền: EP chỉ sử dụng một phép biến dị gene, EP tạo các cá thể con trước, sau đó mới thực hiện phép chọn lọc. Mỗi cá thể cha mẹ sinh ra đúng một cá thể con, vì vậy quần thể trung gian có kích thước gấp đôi tập lời giải. Các cá thể con (FSM) được sinh ra bằng cách thực hiện phép biến dị ngẫu nhiên trên quẩn thể cha mẹ. Có năm hình thức biến dị: Sửa một ký hiệu ra. Sửa một cung chuyển trạng thái. Thêm một cung trạng thái. Xóa một trạng thái. Thay đổi trạng thái ban đầu. Phép chọn lọc: Pop_size cá thể tốt nhất được chọn từ 2* pop_size cá thể trung gian cho thế hệ mới theo độ thích nghi của các cá thể, như vậy, mỗi FSM được chọn phải nằm trong nhóm 50% FSM có độ thích nghi cao hơn các FSM còn lại. So sánh lập trình tiến hóa với giải thuật di truyền cổ điển 28
  29. EP và GA cổ điển có một số khác biệt sau đây: Cách biểu diễn nhiễm sắc thể: EP biểu diễn các cá thể bằng các otomat hữu hạn, còn GA biểu diễn bằng các vector nhị phân. Quá trình chọn lọc: trong EP, thủ tục chọn lọc có tính chất tất định: chọn pop_size cá thể tốt nhất từ 2* pop_size cá thể trung gian và không có sự lặp lại trong việc chọn lọc, còn trong GA thì các cá thể tốt có thể được chọn nhiều lần. Trật tự các toán tử: trong EP, thủ tục chọn lọc được thực hiện sau các phép biến dị gene, còn trong GA cổ điển thì ngược lại. Các tham số: trong GA cổ điển, xác suất lai và biến dị giữ nguyên trong suốt quá trình tiến hóa, còn trong EP, xác suất biến dị có thể thay đổi trong quá trình tiến hóa. 2.2.3 Lập trình di truyền (Genetic Programming – GP) 2.2.3.1 Ý tƣởng của GP Lập trình di truyền dựa trên nguyên lý tiến hóa tự nhiên, trong đó các cá thể của quần thể là các chương trình máy tính. Để tìm lời giải cho một bài toán, người ta xây dựng một quần thể các chương trình máy tính, trải qua quá trình tiến hóa, các chương trình cạch tranh nhau, các chương trình yếu bị dần loại bỏ và cuối cùng cho ta chương trình tốt nhất. 2.2.3.2 Biểu diễn nhiễm sắc thể Mỗi chương trình máy tính có cấu trúc cây. x+y Ví dụ: hai nhiễm sắc thể v1 biểu diễn biểu thức sin(x) + 2 và v2 biểu diễn biểu thức sin(x) + (x2 y) có dạng sau: 29
  30. + sin ^ + x 2 x y + sin √ x + ^ y x 2 Hình 2.3 Sơ đồ hình cây của hai nhiễm sắc thể v1 và v2 Tập lời giải: Quần thể ban đầu gồm có một tập các cây được sinh ngẫu nhiên. Hàm thích nghi: Hàm đánh giá gán một giá trị thích nghi đánh giá hiệu quả của cây. Các đánh giá dựa trên bộ test đã được chọn trước. Các toán tử di truyền Phép lai: là toán tử chủ đạo trong GP. Phép lai tạo ra cá thể con bằng cách hoán đổi các cây con của các cá thể cha mẹ. Phép biến dị: thường sử dụng là chọn một nút trên cây và sinh ngẫu nhiên một cây con mới có gốc tại nút được chọn. Phép chọn lọc 30
  31. Chọn lọc theo nguyên tắc mỗi cây có một xác suất được chọn cho thế hệ sau tỷ lệ thuận với độ thích nghi của cây đó. So sánh lập trình di truyền với giải thuật di truyền cổ điển Khác biệt cơ bản giữa GP và GA cổ điển ở cách biểu diễn cá thể, GP biểu diễn các cá thể bằng các chương trình máy tính có cấu trúc dạng cây, GA cổ điển sử dụng vector nhị phân. 2.2.4 Chƣơng trình tiến hóa (Evoluation Programmes – Eps) 2.2.4.1 Ý tƣởng Như đã trình bày, GA cổ điển gặp khó khăn với những bài toán có nhiều ràng buộc không tầm thường và những bài toán có không gian tìm kiếm phức tạp. Chính vì vậy, người ta đã cải tiến GA cổ điển bằng cách sử dụng những cấu trúc dữ liệu hợp lý và tốt hơn mà không buộc phải dùng các chuỗi nhị phân, cũng như sử dụng các toán tử di truyền thích hợp hơn cho từng lớp bài toán cụ. Phương pháp tính toán tiến hóa theo phương thức trên gọi là các chương trình tiến hóa. Theo Michalewicz thì: Cấu trúc dữ liệu + Giải thuật di truyền = Chƣơng trình tiến hóa 2.2.4.2 So sánh GA cổ điển và các chƣơng trình tiến hóa GA và Eps tương đồng ở điểm cùng duy trì một tập các lời giải tiềm năng, và thực hiện chọn lọc dựa trên độ thích nghi của từng cá thể, rồi áp dụng các phép biến đổi gene trong quá trình tiến hóa. 31
  32. Nội dung thủ tục Eps đều có dạng sau: Procedure Eps Begin t  0 Khởi tạo P(t) Đánh giá P(t) While (not điều kiện dừng) do Begin t  t + 1 chọn P(t) từ P(t-1) thay đổi P(t) đánh giá P(t) End End End Hình 2.4 Nội dung thủ tục Eps Một số khác biệt giữa GA cổ điển và Eps như sau: Eps kết hợp được đặc điểm của mỗi bài toán bằng cách dùng các cấu trúc dữ liệu tự nhiên, có dạng gần giống với lời giải thực tế của bài toán, và xây dựng các toán tử di truyền phù hợp với bài toán cụ thể. GA cổ điển không phụ thuộc đặc điểm bài toán vì sử dụng cấu trúc nhiễm sắc thể nhị phân. Trong GA cổ điển, bước chọn lọc P(t) được thực hiện trước, bước thay đổi P(t) được thực hiện sau. Trong Eps thì hai bước này có thể được hoán đổi cho nhau. Sự khác nhau về cách tiếp cận: Trong GA cổ điển, bài toán ban đầu được biến đổi sang dạng đặc biệt bằng cách xây dựng các chuỗi nhị phân cho các lời giải tiềm năng (mã hóa), các bộ giải 32
  33. mã, các giải thuật sửa chữa Trong thực tế, những việc này không phải lúc nào cũng dễ dàng thực hiện. Hướng tiếp cận GA cổ điển có thể biểu diễn bằng sở đồ sau: Bài toán GA cổ điển thực tế Bài toán đã biến đổi Hình 2.5 Hướng tiếp cận của GA cổ điển Trong các chương trình tiến hóa thì ngược lại. Người ta không biến đổi bài toán mà biến đổi chính GA, tức là biến đổi cách biểu diễn nhiễm sắc thể và các toán tử di truyền sao cho phù hợp với bài toán. Hướng tiếp cận của Eps có thể biểu diễn bằng sơ đồ sau: GA cổ điển Bài toán thực tế Chương trình tiến hóa Hình 2.6 Hướng tiếp cận của Eps Có thể nói, chương trình tiến hóa là sự cải tiến toàn diện GA cổ điển về cách biểu diễn nhiễm sắc thể và nội dung các toán tử di truyền. 33
  34. Nhược điểm của chương trình tiến hóa: Nhìn chung, chúng có nhược điểm là không có cơ sở lý thuyết chắc chắn như GA cổ điển, mà chỉ được đánh giá qua kết quả thực nghiệm. 2.2.4.3 Các bƣớc xây dựng một chƣơng trình tiến hóa Bước 1: Chọn cách biểu diễn gene cho lời giải của bài toán. Cần chọn cách biểu diễn gene sao cho tự nhiên, gần với dạng lời giải thực tế. Đây là bước quan trọng nhất có ảnh hưởng đến chương trình tiến hóa. Cách biểu diễn gene cần chứa đủ các thông tin quan trọng về kết quả. Sự khác nhau cơ bản của các phương pháp tính toán tiến hóa là cách biểu diễn gene. Bước 2: Khởi tạo quần thể (tập lời giải) ban đầu. Việc khởi tạo có thể là ngẫu nhiên hay có áp dụng một vài giả thuật heuristic, nhưng phải bảo đảm được các ràng buộc của bài toán. Bước 3: xây dựng hàm đánh giá để đánh giá độ thích nghi của các cá thể trong quần thể theo độ thích nghi của chúng. Bước 4: xây dựng các toán tử di truyền dựa trên bài toán và các ràng buộc của nó. Bước 5: Các tham số cho bài toán. Các tham số này có thẻ không thay đổi hoặc được tự điều chỉnh trong quá trình tiến hóa như các hướng tiếp cận mới. 34
  35. CHƢƠNG 3: BÀI TOÁN THỜI KHÓA BIỂU – PHÂN TÍCH THIẾT KẾ HỆ THỐNG VÀ ÁP DỤNG GIẢI THUẬT TIẾN HÓA 3.1 Phân tích thiết kế hệ thống 3.1.1 Mô hình đào tạo theo tín chỉ Học chế tín chỉ là phương thức đào tạo, trong đó sinh viên chủ động lựa chọn học từng môn học (tuân theo một số ràng buộc được quy định trước) nhằm tích lũy từng phần và tiến tới hoàn tất toàn bộ chương trình đào tạo, được cấp văn bằng tốt nghiệp. Trên cơ sở lượng hóa quy trình đào tạo thông qua khái niệm "tín chỉ", học chế tín chỉ tạo điều kiện tối đa để cá nhân hóa quy trình đào tạo, trao quyền cho sinh viên trong việc đăng ký sắp xếp lịch học, việc tích lũy các học phần, kể cả sắp xếp thời gian học ở khoa, thời gian tốt nghiệp, ra trường. Về phía mình, người sinh viên cần phát huy tính tích cực, chủ động để thích ứng với quy trình đào tạo này và để đạt những kết quả tốt nhất trong học tập, rèn luyện. Tín chỉ được sử dụng để tính khối lượng học tập của sinh viên. Một tín chỉ được quy định bằng 22.5 tiết học lý thuyết; 30 - 45 tiết thực hành, thí nghiệm hoặc thảo luận; 45 - 90 giờ thực tập tại cơ sở; 45 - 60 giờ làm tiểu luận, bài tập lớn hoặc đồ án, khoá luận tốt nghiệp (Đối với những chương trình, khối lượng của từng học phần đã được tính theo đơn vị học trình, thì 1,5 đơn vị học trình được quy đổi thành 1 tín chỉ). 35
  36. 3.1.2 Quy trình xếp thời khóa biểu theo đào tạo tín chỉ Giai đoạn xếp Dự kiến kế Các hoạch mở lớp Xếp tự động lớp (thuật toán) môn TKB dự Danh sách sinh học kiến viên (các khoa, ngành) Xếp thủ công Danh sách GV Lịch (can thiệp có bận chủ ý) rỗi Danh sách phòng Các ràng buộc xếp TKB Hình 3.1 Quy trình xếp thời khóa biểu theo đào tạo tín chỉ Diễn giải quy trình Đầu mỗi kỳ học, để xếp được thời khóa biểu hợp lý, nhân viên phòng đào tạo phải nắm được các thông tin về danh sách lớp môn học, danh sách giáo viên bận rỗi, danh sách phòng bận rỗi, Đầu mỗi kỳ học, để tạo được danh sách lớp môn học hợp lý, phòng đào tạo phải nắm được các thông tin về danh sách môn học dự kiến, danh sách lượng sinh viên. Từ đó đưa ra giải pháp để trợ giúp quyết định số lớp môn học cần mở, đó chính là “Dự kiến mở lớp”. Việc lập danh sách môn học dự kiến cho từng kỳ từng năm học được các khoa thực hiện dựa vào danh sách môn học đưa ra dự kiến về các môn học cần mở lớp cho từng ngành từng khóa. Việc thống kê và lập danh sách lượng sinh viên được bộ phận quản lý điểm sinh viên thực hiện dựa trên danh sách sinh viên của từng ngành từng khóa, số lượng sinh viên sẽ được tính như sau: số sinh viên sẽ là tổng số sinh viên của các ngành có môn học tương ứng cộng thêm số lượng sinh viên đã học môn học đó mà chưa qua. 36
  37. Sau khi lập xong hai loại danh sách trên khoa và bộ phận quản lý điểm sinh viên sẽ gửi lại cho phòng đào tạo, phòng đào tạo sẽ lập danh sách dự kiến mở lớp và đệ trình lên lãnh đạo ký duyệt, tiếp theo dựa trên danh sách dự kiến mở lớp đã được duyệt phòng đào tạo sẽ lập danh sách lớp môn học. Một lớp môn học có thể được chia thành các nhóm lý thuyết, thực hành. Ví dụ như môn Vật lý đại cương 1: được chia thành nhóm lý thuyết và nhóm thực hành. Cần kiểm tra khi xếp tkb sao cho lý thuyết và thực hành không trùng vào cùng thời gian. Các lớp môn học được tổ chức giảng dậy theo ca mỗi ca là 3 tiết, một ngày tại 1 phòng có 4 ca. Với các lớp môn học có khối lượng học từ 4 tín chỉ trở lên: ví dụ như môn quản trị tài chính doanh nghiệp được tổ chức giảng dạy 2 ca 1 tuần. Các môn dưới 4 tín chỉ thì 1 ca 1 tuần. Để tiến hành xếp thời khóa biểu ngoài danh sách lớp môn học còn cần thêm danh sách giáo viên dự kiến và danh sách phòng dự kiến: Việc lập danh sách giáo viên dự kiến do khoa thực hiện dựa trên danh sách giáo viên của các bộ môn. Việc thống kê và lập danh sách phòng học dự kiến do phòng tổ chức hành chính thực hiện dựa trên danh sách phòng học. Sau khi có được đủ ba danh sách bao gồm: danh sách lớp môn học, danh sách giáo viên dự kiến, danh sách phòng học dự kiến, phòng đào tạo tiến hành xếp thời khóa biểu. Thời khóa biểu sẽ được xếp cho 1 tuần và sau đó trải ra 15 tuần. Sau khi trải xong có thể sửa thời khóa biểu của từng tuần. 37
  38. Bảng 3.1 Nội dung công việc xếp thời khóa biểu STT Tên công việc Đối tƣợng thực hiện Hồ sơ dữ liệu Lập danh sách lớp Danh sách lớp môn 1. Phòng đào tạo môn học học Thống kê và lập Phòng tổ chức hành Danh sách phòng học 2. danh sách phòng học chính dự kiến dự kiến Lập danh sách giáo Danh sách giáo viên 3. Khoa viên dự kiến dự kiến Lập danh sách môn Danh sách môn học 4. Khoa học dự kiến dự kiến Thống kê và lập Bộ phận quản lý điểm Danh sách lượng sinh 5. danh sách lượng sinh sinh viên viên viên Lập danh sách dự Danh sách dự kiến 6. Phòng đào tạo kiến mở lớp mở lớp Danh sách dự kiến 7. Ký duyệt Lãnh đạo mở lớp 8. Xếp thời khóa biểu Phòng đào tạo Thời khóa biểu 38
  39. 3.1.3 Sơ đồ tiến trình nghiệp vụ xếp thời khóa biểu Phòng tổ Lãnh Phòng đào Bộ phận QL chức hành Khoa Hồ sơ dữ liệu đạo tạo điểm sinh viên chính DS SinhViên Yêu cầu Thống kê và Lập DS DS môn học thông tin dự lập DS lượng môn học kiến mở lớp sinh viên dự kiến DS MH dự kiến Gửi DS môn học Gửi DS dự kiến lượng sinh DS lượng SV viên Lập DS dự kiến mở lớp DS dự kiến mở lớp Gửi DS dự kiến mở lớp Duyệt DS dự kiến mở Lập DS lớp lớp môn học DS lớp môn học DS phòng Yêu cầu t/tin Thống kê học xếp TKB và lập DS Lập DS GV phòng học dự kiến dự kiến DS Giáo viên DS GV dự Gửi DS GV kiến Xếp TKB dự kiến Gửi DS DS phòng phòng học học dự kiến dự kiến TKB Hình 3.2 Sơ đồ tiến trình nghiệp vụ 39
  40. 3.1.4 Mô hình nghiệp vụ Bảng 3.2 Bảng phân tích xác định các chức năng tác nhân và hồ sơ Động từ + Bổ ngữ Danh từ Nhận xét Thống kê và lập danh sách lượng Bộ phận quản lý điểm sinh viên Tác nhân sinh viên Lập danh sách môn học dự kiến Khoa Tác nhân Danh sách môn học dự kiến + Lập danh sách dự kiến mở lớp HSDL Danh sách lượng sinh viên Lập danh sách lớp môn học Danh sách dự kiến mở lớp HSDL Lập danh sách giáo viên dự kiến Khoa Tác nhân Thống kê và lập danh sách phòng Phòng tổ chức hành chính Tác nhân học dự kiến Duyệt danh sách dự kiến mở lớp Lãnh đạo Tác nhân Danh sách lớp môn học + Danh Xếp thời khóa biểu sách phòng học dự kiến+ Danh HSDL sách giáo viên dự kiến 40
  41. 3.1.5 Biểu đồ ngữ cảnh PHÒNG TỔ CHỨC HÀNH CHÍNH Yêu cầu t/tin học dự kiến phòngDS xếp TKB 0 Yêu cầu t/tin xếp TBK Duyệt DS dự HỆ DS giáo LÃNH kiến mở lớp THỐNG viên dự kiến KHOA ĐẠO XẾP THỜI DS dự kiến KHÓA DS môn học mở lớp BIỂU dự kiến Yêu cầu thông tin Yêu cầu thông tin DS sinh viên dự mở kiến lớp dự kiến mở lớp lượng BỘ PHẬN QUẢN LÝ ĐIỂM SINH VIÊN Hình 3.3 Biểu đồ ngữ cảnh Phân tích hoạt động: Khi có yêu cầu từ hệ thống về thông tin cần thiết để lập danh sách dự kiến mở lớp, khoa và bộ phận quản lý điểm sinh viên sẽ đưa dữ liệu đầu vào cho hệ thống: Danh sách lượng sinh viên Danh sách môn học dự kiến Khi nhận được các thông tin trên hệ thống sẽ tiến hành lập danh sách dự kiến mở lớp và gửi cho các lãnh đạo phê duyệt. Khi đã được phê duyệt dựa vào danh sách dự kiến mở lớp hệ thống tiến hành lên danh sách lớp môn học và gửi đi yêu 41
  42. cầu thông tin xếp thời khóa biểu cho khoa và phòng tổ chức hành chính, hai nơi này sẽ gửi về dữ liệu đầu vào cho hệ thống: Danh sách giáo viên dự kiến Danh sách phòng học dự kiến Kết hợp thông tin trên với danh sách lớp môn học hệ thống sẽ tiến hành xếp thời khóa biểu. 3.1.6 Biểu đồ phân rã chức năng Vì nội dung đồ án chỉ đề cập về vấn đề xếp lịch nên phần dự kiến đào tạo em sẽ bỏ qua trong các phần thiết kế tiếp theo của đồ án, em chỉ sử dụng nhưng dữ liệu cần thiết đó là danh sách lớp môn học, danh sách phòng học dự kiến, danh sách giáo viên dự kiến, danh sách dự kiến đào tạo. Hệ thống xếp thời khóa biểu 1.0 Nhập dữ 2.0 Lập thời 3.0 Xem thời liệu khóa biểu khóa biểu 1.1 Nhập DS lớp 2.1 Lập TKB các 3.1 Xem TKB môn học lớp môn học phòng 1.2 Nhập DS 2.2 Chọn thời 3.2 Xem TKB giáo viên dự khóa biểu Giáo viên kiến 1.3 Nhập DS 3.3 Xem TKB lớp phòng học dự môn học kiến Hình 3.4 Biểu đồ phân rã chức năng 42
  43. 3.1.7 Danh sách hồ sơ dữ liệu sử dụng d1. Danh sách lớp môn học d2. Danh sách phòng học dự kiến d3. Danh sách giáo viên dự kiến d4. Thời khóa biểu d5. Danh sách dự kiến đào tạo 3.1.8 Ma trận thực thể chức năng Bảng 3.3 Ma trận thực thể chức năng Các thực thể dữ liệu d1. Danh sách lớp môn học d2. Danh sách phòng học dự kiến d3. Danh sách giáo viên dự kiến d4. Thời khóa biểu d5.Danh sách dự kiến đào tạo Các chức năng nghiệp vụ D1 D2 D3 D4 D5 1.0 Nhập dữ liệu C C C 2.0 Lập thời khóa biểu R R R C/U R 3.0 Xem thời khóa biểu R 43
  44. 3.1.9 Biểu đồ luồng dữ liệu 3.1.9.1 Biểu đồ luồng dữ liệu mức 0 Phòng tổ Khoa chức hành DS phòng học dự chính kiến 1.0 DS Nhập dữ liệu d3 DS giáo viên dự kiến d2 DS phòng học dự kiến d1 DS lớp môn học 2.0 d4 Thời khóa biểu Lập TKB 3.0 d5 DS dự kiến đào tạo Xem TKB Hình 3.5 Biểu đồ luồng dữ liệu mức 0 44
  45. 3.1.9.2 Biểu đồ luồng dữ liệu mức 1 Tiến trình nhập dữ liệu 1.1 liệu xếp TKB Chuẩn bị dữ d1 DS lớp môn học Nhập DS lớp môn liệu xếp TKB Chuẩn bị dữ học DS giáo viên dự kiến 1.2 Khoa Nhập DS d3 DS giáo viên dự kiến giáo viên Yêu cầu thông tin dự kiến xếp TKB 1.3 DS phòng học dự kiến Nhập DS phòng học Phòng tổ dự kiến chức hành chính d2 DS phòng học dự kiến Yêu cầu thông tin xếp TKB Hình 3.6 Biểu đồ luồng dữ liệu mức 1 tiến trình nhập dữ liệu 45
  46. Tiến trình xếp thời khóa biểu 2.1 d3 DS giáo viên dự kiến d4 Thời khóa biểu Lập TKB các lớp d2 DS phòng học dự kiến môn học d1 DS lớp môn học 2.2 d5 DS dự kiến đào tạo Chọn TKB Hình 3.7 Biểu đồ luồng dữ liệu mức 1 tiến trình xếp TKB Tiến trình xem thời khóa biểu 3.1 d4 Thời khóa biểu Xem TKB phòng 3.2 Xem TKB 3.3 giáo viên Xem TKB lớp môn học Hình 3.8 Biểu đồ luồng dữ liệu mức 1 tiến trình xem TKB 46
  47. 3.1.10 Mô hình liên kết thực thể (ER) Xác định các kiểu thực thể, các thuộc tính và thuộc tính khóa của thực thể Bảng 3.4 Các kiểu thực thể, thuộc tính và khóa Kiểu thực Thuộc tính STT Thuộc tính thể khoá Môn ID, Môn tên, Môn số tín chỉ, Môn học 1 Môn Môn ID phần, Môn vị trí, Môn tên tiếng anh. Giáo viên 2 Giáo viên Giáo viên ID, Giáo viên họ tên ID 3 Lớp môn học Lớp ID, Lớp số lượng sinh viên, Lớp tên Lớp ID 4 Phòng Phòng ID, Phòng loại, Phòng số chỗ Phòng ID Dự kiến đào Dự kiến đào tạo ID, Kỳ, Ngành, Dự kiến Dự kiến đào 5 tạo đào tạo tổng số tín chỉ tạo ID Nguyện 6 Nguyện vọng Nguyện vọng ID, Ca, Thứ vọng ID 47
  48. Mô hình ER DUKIEN_DT KY MON_TEN _ID MON_ID _TA MON_TINCHI n n DUKIEN_DT CHO MON MON_HOC 1 n PHAN DUKIEN_DT_ NGANH MON_VITRI SOTINCHI MON_TEN CO LOP_TEN DAY n GV_ID n LOP_MONHOC LOP_ID GV n 1 LOP_SLSV THU n GV_HOTEN CO TKB_ID XEP_TKB CA n PHONG_ID NGUYEN_VONG n CA PHONG THU NV_ID PHONG_LOAI PHONG_SOCHO Hình 3.9 Mô hình ER : Dự kiến đào tạo: DUKIEN_DT (DUKIEN_DT_ID, DUKIEN_DT_SOTINCHI, NGANH_ID, KY_ID) Môn học: 48
  49. MON (MON_ID, MON_SOTINCHI, MON_HOCPHAN, MON_VITRI, MON_TEN_TA, MON_TEN) Lớp môn học: LOP_MONHOC (LOP_ID, LOP_TEN, LOP_SLSV) Giáo viên: GV (GV_ID, GV_HO_TEN) Phòng: PHONG (PHONG_ID, PHONG_LOAI, PHONG_SOCHO) Nguyện vọng: NGUYEN_VONG (NV_ID, CA, THU) Biểu diễn các mối quan hệ Môn CHO dự kiến đào tạo thuộc dạng quan hệ nhiều với nhiều. MON_CHO_CTDT (DUKIEN_DT_ID, MON_ID) Tạo ra một bảng với hai khóa phụ lầy từ hai khóa của hai thực thể hình thành mối quan hệ. Giáo viên DAY môn học thuộc dạng quan hệ nhiều với nhiều. GV_DAY_MON (GV_ID, MON_ID) Tạo ra một bảng với hai khóa phụ lầy từ hai khóa của hai thực thể hình thành mối quan hệ. Môn CO các lớp môn học thuộc dạng quan hệ một nhiều với một ở phía môn và nhiều ở phía lớp môn học. LOP_MONHOC (LOP_ID, LOP_TEN, LOP_SLSV, MON_ID) Thực thể lớp môn học lấy khóa chính của thực thể môn về làm thuộc tính. Giáo viên CO nguyện vọng thuộc dạng quan hệ một nhiều với một ở phía giáo viên và nhiều ở phía nguyện vọng. NGUYEN_VONG (NV_ID, CA, THU, GV_ID) Thực thể nguyện vọng lấy khóa chính của thực thể giáo viên về làm thuộc tính. XEP_TKB cho lớp môn học, giáo viên, và phòng thuộc dạng quan hệ nhiều nhiều. TKB (TKB_ID, TKB_CA, TKB_THU, LOP_ID, PHONG_ID, GV_ID) 49
  50. Tạo ra một bảng có khóa chính và thuộc tính riêng, đồng thời lấy khóa của cả ba thực thể tham gia vào quan hệ làm thuộc tính. 3.1.11 Mô hình quan hệ Hình 3.10 Cơ sở dữ liệu 50
  51. Các bảng dữ liệu: Bảng 3.5 DUKIEN_DT Dùng để lưu thông tin về dự kiến kế hoạch mở lớp của các năm học. Kiểu dữ Kích STT Tên trƣờng Ghi chú liệu cỡ 1 DUKIEN_DT_ID nvarchar 50 Mã dự kiến đào tạo 2 KY_ID nvarchar 50 Mã kỳ 3 NGANH_ID nvarchar 50 Mã ngành 4 DUKIEN_DT_SOTINCHI nvarchar 50 Tổng số tín chỉ Bảng 3.6 MON_CHO_CTDT Dùng để lưu thông tin về các môn học ứng với từng kế hoạch mở lớp của các năm. STT Tên trƣờng Kiểu dữ liệu Kích cỡ Ghi chú 1 MON_ID nvarchar 50 Mã môn 2 DUKIEN_DT_ID nvarchar 50 Mã dự kiến đào tạo Bảng 3.7 LOP_MONHOC Dùng để lưu thông tin về các lớp môn học. STT Tên trƣờng Kiểu dữ liệu Kích cỡ Ghi chú 1 LOP_ID nvarchar 50 Mã lớp 2 MON_ID nvarchar 50 Mã môn 3 LOP_SLSV nvarchar 50 Số lượng sinh viên của lớp 4 LOP_TEN nvarchar 50 Tên lớp 51
  52. Bảng 3.8 MON Dùng để lưu thông tin về các môn học. Kiểu dữ Kích STT Tên trƣờng Ghi chú liệu cỡ 1 MON_ID nvarchar 50 Mã môn 2 MON_TEN nvarchar 50 Tên tiếng việt của môn 3 MON_TEN_TA nvarchar 50 Tên viết tắt tiếng anh của môn 4 BOMON_ID nvarchar 50 Mã bộ môn 5 MON_SOTINCHI nvarchar 50 Số tín chỉ 6 MON_HOCPHAN nvarchar 50 Số học phần của môn 7 MON_VITRI nvarchar 50 Vị trí của môn trong CTDT Bảng 3.9 GV Dùng để lưu thông tin về các giáo viên. STT Tên trƣờng Kiểu dữ liệu Kích cỡ Ghi chú 1 GV_ID nvarchar 50 Mã Giáo viên Họ Tên Giáo 2 GV_HO_TEN nvarchar 50 viên 3 BOMON_ID nvarchar 50 Mã bộ môn Bảng 3.10 GV_DAY_MON Dùng để lưu thông tin các về các giáo viên ứng với các môn học họ có thể dậy. STT Tên trƣờng Kiểu dữ liệu Kích cỡ Ghi chú 1 MON_ID nvarchar 50 Mã môn 2 GV_ID nvarchar 50 Mã Giáo viên 52
  53. Bảng 3.11 TKB Dùng để lưu thông tin về thời khóa biểu của toàn bộ các lớp môn học hiện có. STT Tên trƣờng Kiểu dữ liệu Kích cỡ Ghi chú 1 TKB_ID nvarchar 50 Mã sự kiện 2 TKB_THU nvarchar 50 Thứ 3 TKB_CA nvarchar 50 Ca 4 LOP_ID nvarchar 50 Mã lớp 5 PHONG_ID nvarchar 50 Mã phòng 6 GV_ID nvarchar 50 Mã Giáo viên Bảng 3.12 PHONG Dùng để lưu thông tin về các phòng. STT Tên trƣờng Kiểu dữ liệu Kích cỡ Ghi chú 1 PHONG_ID nvarchar 50 Mã phòng 2 PHONG_LOAI nvarchar 50 Loại phòng 3 PHONG_SOCHO nvarchar 50 Sức chứa của phòng Bảng 3.13 NGUYEN_VONG Dùng để lưu thông tin về các buổi học mà các giáo viên không thể dậy trong tuần. STT Tên trƣờng Kiểu dữ liệu Kích cỡ Ghi chú 1 NV_ID nvarchar 50 Mã nguyện vọng 2 GV_ID nvarchar 50 Mã giáo viên 3 CA nvarchar 50 Ca 4 THU nvarchar 50 Thứ 53
  54. 3.2 Áp dụng giải thuật tiến hóa 3.2.1 Các yêu cầu cơ bản của thời khóa biểu theo đào tạo tín chỉ Thời khóa biểu của giáo viên không trùng lặp: Thỏa mãn điều này có nghĩa là tại một thời điểm chỉ cho phép giáo viên dạy một lớp môn học tại một phòng học xác định nào đó. Thời khóa biểu phải thỏa mãn cơ bản nguyện vọng của giáo viên. Thời khóa biểu thỏa mãn nguyện vọng của giáo viên là điều rất cần thiết vì sẽ tạo nên tính mềm dẻo cho Thời khóa biểu. Thực tế có rất nhiều giáo viên vừa phải dạy, vừa phải kiêm nhiệm các chức vụ khác như trưởng, phó phòng, , trưởng bộ môn, .Các giáo viên này thường có những cuộc họp quan trọng, đòi hỏi trong Thời khóa biểu của họ phải tránh xếp vào các tiết mà giáo viên phải đi họp. Ngoài ra, việc cho phép Thời khóa biểu thỏa mãn nguyện vọng của giáo viên còn giúp những giáo viên có con nhỏ, các giáo viên ở xa về Khoa công tác, giảng dạy, có lịch biểu hợp lý hơn để tạo điều kiện tốt nhất cho họ khi công tác tại Khoa. Tuy nhiên, nguyện vọng của giáo viên phải đảm bảo số tiết phải dạy của giáo viên nhỏ hơn hoặc bằng số tiết con trống trong Thời khóa biểu hiện thời của giáo viên đó. Nếu số tiết dạy của giáo viên lớn hơn số tiết còn trống trong Thời khóa biểu của giáo viên thì nguyện vọng của giáo viên không thể được đáp ứng và bài toán là không thể xếp được. Thời khóa biểu của giáo viên nên được xếp sao cho giáo viên có thể dạy liên tiếp các tiết trong một buổi, phải hạn chế các tiết trống giữa buổi cho giáo viên. Một yêu cầu quan trọng trong thời khóa biểu theo tín chỉ là phải đảm bảo sao cho mọi sinh viên có thể đăng ký được hết các môn học trong học kỳ. Như vậy thời khóa biểu phải rõ ràng, dễ hiểu để sinh viên có thể dễ chọn ra được lịch học cho bản thân. Phòng học được sắp xếp để đảm bảo làm sao cho sức chứa của phòng học phải lớn hơn hoặc bằng tổng số sinh viên của lớp môn học tại phòng đó. Từ các yêu cầu cơ bản trên ta có các ràng buộc cho bài toán thời khóa biểu tín chỉ Các ràng buộc cứng: Phòng học có đủ điều kiện để dạy lớp môn học đó. Chỉ có một lớp môn học được tổ chức tại một phòng học trong một ca xác định. Các lớp môn học từ 4 chỉ trở lên phải được chia thành hai ca học khác nhau. 54
  55. Tại một khoảng thời gian cho trước chỉ được một giáo viên dậy một lớp môn học tại một phòng xác định nào đó. Các ràng buộc mềm: Các môn chuyên ngành của cùng một kỳ, cùng một khóa, thuộc cùng một ngành ít bị trùng lịch nhau để đảm bảo cho mọi sinh viên có thể đăng ký được hết các môn học. Các lớp môn học được chia thành hai ca học tại hai ngày có khoảng giãn cách trong tuần là phù hợp (thông thường khoảng cách giữa 2 ngày đó cách nhau từ 2-3 ngày là hợp lý). 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. Các ngày nghỉ định trước đó là những ngày mà giáo viên phải đi họp, hội thảo Hoặc là các yêu cầu từ phía các giảng viên đã cao tuổi, họ yêu cầu không dạy học vào các tiết đầu của buổi trưa vì như thế là quá sức với họ Ta có thể thấy nếu vi phạm các ràng buộc cứng sẽ làm cho thời khoá biểu không thể chấp nhận được, và đó sẽ không phải là một thời khoá biểu thực sự. Còn nếu vi phạm các ràng buộc mềm thì thời khoá biểu vẫn được coi là thời khoá biểu nhưng nó không được hợp lý lắm và sẽ có một số người không thích kiểu lập thời khoá biểu này. Tuy nhiên với chương trình này chúng ta sẽ cố gằng làm sao đảm bảo không vi phạm các ràng buộc cứng, còn các ràng buộc mềm nếu giải quyết được thì càng tốt còn nếu không thì cũng có thể coi là chấp nhận được. Các ràng buộc cho sinh viên không được tính đến ở đây vì thời khóa biểu này sẽ là chuẩn cho sinh viên đăng ký học. Trong quá trình đăng ký sẽ xử lý việc trùng thời gian giữa các lớp môn học mà sinh viên đăng ký bằng cách thông báo cho sinh viên đăng ký lớp khác hoặc hủy đăng ký môn đó. Lịch học của sinh viên nhiều hay ít phụ thuộc hoàn toàn vào quyết định và lựa chọn của sinh viên. 3.2.2 Biểu diễn nhiễm sắc thể Tùy vào từng bài toán mà người giải có các cách biểu diễn cấu trúc nhiễm sắc thể khác nhau, mỗi cách có ưu điểm riêng nhưng đều bảo đảm gần giống với dạng lời giải thực tế hoặc dễ dàng chuyển về dạng như lời giải thực tế sau khi đã tìm được lời giải đủ tốt. Phổ biến là dùng cấu trúc mảng 3 chiều. Vì thế ta sẽ dùng mảng 3 chiều để biểu diễn một nhiễm sắc thể (cá thể): Chiều thứ nhất biểu diễn các ca học trong ngày. Chiều thứ hai biểu diễn các ngày trong tuần. Chiều thứ ba biểu diễn các phòng học. 55
  56. Khi thiết kế ứng dụng ta sẽ sử dụng một mảng 2 chiều thay cho mảng 3 chiều để biểu diễn nhiễm sắc thể vì thực tế mảng 3 chiều cũng chỉ là nhiều mảng 2 chiều nối tiếp nhau. Phòng A205 A204 A203 A202 A201 Hai Ba Tư Năm Sáu Bảy Ngày 1 2 3 4 Ca A202-Thứ 7-Ca 3: (ALG31021-1: Nguyễn Thị Huệ) A201-Thứ 4-Ca 2: (GPH31021-1: Đinh Đức Linh) Hình 3.11 Cấu trúc một nhiễm sắc Mỗi một phần tử của mảng ứng với vị trí của một gene trên nhiễm sắc thể, mã hóa cho một ca học trong một ngày trong tuần tại một phòng xác định, nghĩa là xác định 3 tham số [Ca, Ngày, Phòng]. Mỗi gene lữu trữ hai thông tin (Lớp môn học, Giáo viên) tương ứng với ca học của một lớp môn học trong ngày. Một nhát cắt theo hai trục ca-ngày, ta có thời khóa biểu của một phòng. Một nhát cắt theo hai trục ngày-phòng ta có một ca học của tất cả các phòng trong cả tuần. Một nhát cắt theo hai trục ca-phòng ta có các ca học của một ngày trong tuần tại tất cả các phòng. Toàn bộ nhiễm sắc thể là thời khóa biểu một trường. 56
  57. 3.2.3 Khởi tạo quần thể ban đầu 3.2.3.1 Thủ tục tạo ngẫu nhiên một nhiễm sắc thể Ta lần lượt tạo ngẫu nhiên thời khóa biểu cho một phòng, tương ứng với một nhát cắt theo trục ca-ngày. Trước tiên, để đảm bảo các môn học dự kiến cho từng khóa ngành trong dự kiến kế hoạch mở lớp ít bị trùng nhau tạo điều kiện cho các sinh viên có thể đăng ký hết các môn học cần thiết của ngành mình ta sẽ lấy thông tin về các môn học của từng ngành từng khóa trong dự kiến mở lớp để xếp trước. Ta sẽ dùng hàm (random) để chọn ra một ngành trong danh sách các ngành và lấy các môn dự kiến của ngành đó tham chiếu tới các lớp môn học tương ứng và xếp vào một hoặc hai phòng sau đó loại bỏ ngành này khỏi danh sách, lặp lại bước này với tất cả các ngành còn lại tại các phòng còn lại ta giải quyết được tất cả các môn dự kiến cho từng ngành đảm bảo ít bị trùng nhau. Các lớp môn học còn lại thực hiện random tại một vị trí ngẫu nhiên trong mảng 3 chiều sao cho tại vị trí đó còn trống thì xếp vào vị trí đó. Thực hiện thủ tục này với tất cả các lớp môn học còn lại ta được quần thể ban đầu gồm N cá thể, và hiển nhiên còn vi phạm nhiều ràng buộc. Ví dụ: xét danh sách các môn học dự kiến của ngành CT13 với số lượng của các ca học của từng môn trong 1 tuần Bảng 3.14 Danh sách các môn học dự kiến cho ngành CT13 Số lƣợng ca học trong Môn Lớp môn học một tuần Đồ họa máy tính CGR33021-1 1 Vẽ kỹ thuật DRA31021-1 1 Cơ sở dữ liệu DSY33031-1 1 Tiếng Anh 5 ENG31035-1 1 Tiếng Anh 1 ENG31041-2 2 Tiếng Anh 2 ENG31042-2 2 Tiếng Anh 3 ENG31053-2 2 Tiếng Anh 4 ENG31054-2 2 Toán cao cấp 2 MAT31032-2 1 Toán cao cấp 1 MAT31031-2 1 Toán cao cấp 3 MAT31023-2 1 Vi xử lý và lập trình MAP32021-1 1 57
  58. Assembly Tư tưởng HCM HCM31021-1 1 Vật lý đại cương 2 GPH31022-1 1 Vật lý đại cương 1 GPH31021-1 1 Phương pháp tính MCA32021-1 1 Những nguyên lí cơ bản của chủ nghĩa MAC- MLP31021-2 1 LENIN 1 Những nguyên lí cơ bản của chủ nghĩa MAC- MLP31032-1 1 LENIN 2 Lập trình hướng đối tượng OOP33021-1 1 Hệ điều hành OSP23021-1 1 An toàn bảo mật thông tin SSI33021-1 1 25 gene trong một cá thể 21 môn học dự kiến Tương ứng với 25 vị trí khác nhau. Ta lấy ngẫu nhiên một môn và ánh xạ tới một lớp môn học tương ứng chưa được xếp chỗ và xếp vào một vị trí bất kỳ trong cùng một phòng. Ca\Thứ 2 3 4 5 6 7 CGR33021 DSY33031 MAP32021 HCM31021 GPH31022 1 SSI33021-1 -1 -1 -1 -1 -1 DRA31021 OSP23021- OOP33021 MCA32021 GPH31021 MLP31032 2 -1 1 -1 -1 -1 -1 MLP31021 ENG31041 MAT31031 ENG31054 ENG31053 ENG31054 3 -2 -2 -2 -2 -2 -2 ENG31041 MAT31032 ENG31042 ENG31053 ENG31042 MAT31023 4 -2 -2 -2 -2 -2 -2 Hình 3.12 Thời khóa biểu ban đầu theo trục ca-ngày Như vậy là ta còn lớp tiếng anh 5 không xếp được vào vì một phòng trong một tuần chỉ có 4*6=24 vị trí mà ta cần tới 25 vị trí, nhưng cũng không có ai có thể học được 5 lớp tiếng anh cùng một kỳ, cho nên nếu sau này ta xếp lớp tiếng anh này tại một phòng nào khác và chắc chắn sẽ trùng lịch với một môn nào đó ở trên thì cũng không ảnh hưởng nhiều lắm. Từ bảng trên ta thấy nếu xếp như vậy sẽ khiến cho các lớp môn học tập trung tại một phòng. Điều này khiến cho các phòng còn lại có nguy cơ không có lớp môn 58
  59. học nào cả vì các phòng khác đã lấy hết các lớp môn học của kỳ đó rồi. Vì vậy ta sẽ tách số lượng lớp môn học ở phòng trên làm hai các lớp tại ca sáng ta giữ nguyên và chuyển toàn bộ các lớp buổi chiều sang một phòng trống khác làm vậy để đảm bảo các lớp môn học được dàn đều ra các phòng. Với các lớp môn học còn lại ta sẽ xếp ngẫu nhiên vào một gene trống trên cá thể, sau khi xếp hết số lượng lớp môn học vào các phòng ta đã có một cá thể với N lớp môn học tương ứng với N gene. Việc tiếp theo là điền mã giáo viên vào các lớp đã được xếp chỗ dựa vào danh sách mời giảng, nếu đã chỉ định rõ giáo viên nào sẽ dậy lớp nào thì đơn giản là chỉ việc tìm lớp đó trên cá thể và điền mã giáo viên tương ứng vào cạnh mã lớp. Nếu như chưa chỉ định rõ giáo viên nào dậy lớp môn học nào thì ta sẽ tìm trong cơ sở dữ liệu các giáo viên có khả năng dậy lớp đó, rồi lựa chọn một giáo viên mà khi nhận lớp các ràng buộc bị vi phạm là ít nhất để xếp vào. Sau bước này ta được một cá thể hoàn chỉnh với nhiều phòng học được xếp lịch giống như hai bảng sau: C\T 2 3 4 5 6 7 CGR33021-1 DSY33031-1 \ SSI33021-1 \ GPH31022-1 1 \ GV-001 GV-007 GV-123 \ GV-221 DRA31021-1\ OOP33021-1 \ GPH31021-1 2 GV-321 GV-322 \ GV-422 MLP31032-2 \ MAP32021-2 3 GV-777 \ GV-213 HCM31021-2 OSP23021-2 \ MCA32021-2 4 \ GV-331 GV-751 \ GV-023 C\T 2 3 4 5 6 7 MLP31021-2 MAT31023-2 ENG31042-2 1 \ GV-512 \GV-733 \GV-742 ENG31053-2 ENG31042-2 2 \GV-245 \GV-572 ENG31041-2 MAT31031-2 ENG31054-2 ENG31054-2 3 \GV-623 \GV-432 \GV-145 \GV-235 ENG31041-2 MAT31032-2 ENG31053-2 4 \GV-867 \GV-735 \GV-522 Hình 3.13 Thời khóa biểu hoàn chỉnh của phòng học 59
  60. Nếu như không tìm được một giáo viên nào thích hợp ta sẽ để trống phần mã giáo viên tại lớp môn học đó. Với cách biểu diễn nhiễm sắc thể và thủ tục khởi tạo quần thể ban đầu như trên, giải thuật thỏa mãn được một số ràng buộc cứng sau: Chỉ có một lớp môn học được tổ chức tại một phòng trong một ca xác định. Các lớp học từ 4 chỉ trở lên được chia thành hai ca khác nhau. Và thỏa mãn một ràng buộc mềm: Các môn chuyên ngành của cùng một kỳ, cùng một khóa, thuộc cùng một ngành ít bị trùng lịch nhau để đảm bảo cho mọi sinh viên có thể đăng ký được hết các môn học. Các ràng buộc còn lại sẽ được xử lý bằng các phép biến dị, sẽ trình bày kỹ ở phần sau. Ưu điểm của cách biểu diễn này là: Cấu trúc nhiễm sắc thể giống với một thời khóa biểu thực tế. Mỗi nhiễm sắc thể mã hóa cho toàn bộ thời khóa biểu của một trường. 3.2.4 Xác định hàm thích nghi Do các ràng buộc đa dạng, ta nên xét từng ràng buộc và xây dựng các hàm đánh giá tương ứng, sau đó tổ hợp lại thành hàm đánh giá chung cho cá thể. Tùy theo tính chất cứng, mềm và tính cần thiết của các ràng buộc, ta sẽ gán cho chúng các tham số lớn nhỏ khác nhau trong hàm đánh giá tổng thể của cá thể. Ta xây dựng tổ hợp các hàm đánh giá thành phần của cá thể v gồm k ràng buộc như sau: k f (v) M fi (v) i 1 [3.1] Trong đó, fi(v) = - Ai*xi là hàm đánh giá theo ràng buộc thứ i, Ai > 0 là tham số, xi ≥ 0 là số lớp môn học vi phạm ràng buộc thứ i, với i = 1, 2, , k, M > 0 là gia số ban đầu. Gia số M phải được chọn đủ lớn để bảo đảm cho f(v) > 0 Ví dụ: f1(v) = - A1*x1 Đánh giá số tiết học bị trùng của giáo viên (A1 là tham số, x1 là số lớp môn học bị trùng). x1=10 có nghĩa là có 10 lớp môn học mà một số giáo viên bị trùng lịch tại một số ca học. 60
  61. A1 = 10 tương ứng với mỗi vi phạm tính 10 điểm tổng số điểm vi phạm là 100 Khi đó chọn M bằng 1000 vậy số điểm còn lại của cá thể đó là 1000 – 100 còn 900. Vậy cá thể nào có điểm càng cao càng gần với 1000 là cá thể tối ưu hơn. Tùy theo từng loại ràng buộc cứng hay mềm và sự vi phạm nhiều hay ít mà quyết định giá trị cho tham số A và gia số M. Việc xây dựng hàm thích nghi cho cá thể từ các hàm thích nghi toàn phần giúp ta dễ dàng thay đổi các tham số để có thể điều khiển hướng hội tụ của bài toán theo định hướng của người sử dụng. Tuy nhiên, những thay đổi này cần phải bảo đảm tiêu chuẩn cơ bản của hàm thích nghi trong mỗi pha tiến hóa, nghĩa là hàm thích nghi phải phân biệt được độ thích nghi của từng cá thể, để cá thể tương ứng với lời giải tốt hơn sẽ có giá trị hàm thích nghi lớn hơn. 3.2.5 Các toán tử di truyền Các toán tử di truyền được tách thành hai nhóm chính là toán tử lai và toán tử biến dị. Một số toán tử biến dị ngoài việc tạo ra các cá thể mới còn có nhiệm vụ xử lý các ràng buộc. Với bài toán thời khóa biểu này ta không sử dụng toán tử lai vì các đoạn gene trong mỗi nhiễm sắc thể mang tính duy nhất đại diện cho một lớp môn học cụ thể và chúng được xếp ngẫu nhiên vào các phòng. Vì thế ta khi đổi chỗ các đoạn gene giữa các cá thể với nhau sẽ tạo ra việc thừa các lớp môn học ở cá thể này nhưng lại thiếu lớp môn học ở cá thể kia, điều đó sẽ không đảm bảo sự toàn vẹn của các lớp môn học đầu vào. Hơn nữa đây là xếp ngẫu nhiên vì thế càng khó để tìm các đoạn gene giống nhau để đổi chỗ nên ta chỉ dùng được toán tử biến dị trong bài toán này. Một đặc điểm của giải thuật tiến hóa là thường chỉ tìm được các lời giải gần tối ưu, rất khó thỏa mãn hoàn toàn các ràng buộc, hoặc nếu cho thỏa mãn triệt để thì thời gian chạy rất lâu (có thể lên tới cả ngày ) do không gian tìm kiếm rộng và có sự lặp lại. Do đó, đối với mỗi ràng buộc, ta cần có các toán tử biến đổi có định hướng (giống như việc biến đổi gene theo ý con người trong công nghệ sinh học). Việc này vừa giúp tạo ra nhiễm sắc thể mới, vừa xử lý được các ràng buộc và đẩy nhanh quá trình hội tụ. Ngoài ra, việc đẩy nhanh sự hội tụ sẽ có thể dẫn đến mất một số thông tin tích cực (một số nhiễm sắc thể có tiềm năng cao bị bỏ qua), nên để bổ sung thông tin ta cần có các toán tử biến dị mạnh. 61
  62. 3.2.5.1 Toán tử đổi chỗ giáo viên trong một phòng (khử ca trùng) Sử dụng toán tử này để xóa ca trùng của một giáo viên tại nhiều phòng. Khi có một giáo viên A bị trùng ca dạy trên hai phòng, giả sử là phòng A201 và phòng C101 vào ca thứ T của ngày N. Ta sẽ tìm ca T’ vào ngày N’ trong tuần sao cho giáo viên A không có ca dạy. Ta tìm được giáo viên B dạy tại tiết T’ của ngày N’ của một trong hai phòng đó. Đổi chỗ ca dạy của hai giáo viên, ta khử được xung đột tại ca T của giáo viên A. Ví dụ: A201 Thứ 2 Thứ 3 Thứ 7 A201 Thứ 2 Thứ 3 Thứ 7 Ca 1 GV-A GV-D Ca 1 GV-B GV-D Ca 2 GV-G GV-B Ca 2 GV-G GV-A Ca 3 GV-G GV-E Ca 3 GV-G GV-E Ca 4 GV-C Ca 4 GV-C C101 Thứ 2 Thứ 3 Thứ 7 Ca 1 GV-A GV-C Ca 2 GV-M GV-G Ca 3 GV-L GV-N Ca 4 GV-O Hình 3.14 Toán tử đổi chỗ giáo viên 62
  63. 3.2.5.2 Toán tử đổi chỗ lớp môn học (khử các lớp cụm) Sử dụng toán tử này để đổi chỗ các lớp môn học có 4 chỉ trở lên được chia làm hai ca có vị trí liền kề nhau. Khoảng cách tối ưu giữa hai ca học này là hai đến ba ngày. C\T 2 3 4 5 6 7 1 MLP31021-2 MAT31023-2 ENG31042-2 2 ENG31053-2 ENG31042-2 3 ENG31041-2 MAT31031-2 ENG31054-2 ENG31054-2 4 MAT31032-2 ENG31041-2 ENG31053-2 C\T 2 3 4 5 6 7 1 MLP31021-2 MAT31023-2 ENG31042-2 2 ENG31053-2 ENG31042-2 3 ENG31041-2 MAT31031-2 ENG31054-2 ENG31054-2 4 MAT31032-2 ENG31053-2 ENG31041-2 Hình 3.15 Toán tử đổi chỗ lớp môn học 3.2.5.3 Toán tử thay đổi toàn bộ lớp Một đặc điểm của giải thuật tiến hóa là khi đã đạt đến giá trị gần tối ưu, quần thể sẽ mất dần tính biến dị và không còn thông tin mới nên khó phát triển. Để khắc phục điểm này, ta sẽ cho biến dị mạnh bằng cách thay thế một phần hoặc toàn bộ các cá thể bằng các cá thể hoàn toàn mới. Điều này sẽ cung cấp thông tin mới cho giải thuật, đem lại khả năng có những đột phá mới tromg tìm kiếm để dẫn đến giá trị gần tối ưu hơn. 3.2.6 Quá trình chọn lọc Quá trình này dựa vào phương pháp bánh xe xổ số của GA cổ điển (xem ở mục 2.1.3.3) với xác suất lựa chọn của mỗi cá thể vi được tính theo công thức: f (vi ) pi N f (v j ) j 1 [3.2] N Trong đó, f(vi) là hàm đánh giá cá thể vi trên tất cả các ràng buộc, f (v j ) j 1 là độ thích nghi toàn phần của quần thể, N là số cá thể. 63
  64. 3.2.7 Thủ tục tiến hóa Procedure len_lich_tkb; Begin Khởi tạo P; Đánh giá P; Repeat Số_lần  Random( ) For i  1 to Số_lần Do Begin Hệ_số  Random( ); If Hệ_số < Pmut1 then Khử ca trùng của giáo viên( P,T); Hệ_số  Random( ); If Hệ_số < Pmut2 then Khử các lớp cụm (P,T); Hệ_số  Random( ); If Hệ_số < Pmut3 then Biến dị mạnh (P); End; Đánh giá P; Until Điều_kiện_kết_thúc; Biểu_diễn_lời_giải; End; Hình 3.16 Thủ tục tiến hóa cho bài toán xếp thời khóa biểu tín chỉ Trước tiên, khởi tạo quần thể P như đã trình bày ở mục 3.2.3 Sau đó, các cá thể của quần thể P được đánh giá độ thích nghi thông qua thủ tục đánh giá như ở mục 3.2.4. Hệ_số  Random( ); Vòng lặp Repeat Until thực hiện quá trình tiến hóa cho đến khi thỏa mãn Điều_kiện_kết_thúc (đạt đến một giá trị đủ lớn của hàm thích nghi). Trong vòng lặp Hệ_số  Random( ); này, quần thể P liên tục được tái sinh và phát triển thông qua quần thể trung gian T. Các cá thể mới được sinh ra thông qua các toán tử di truyền được lưu trữ tạm thời trong T. Sau khi hoàn thành các toán tử di truyền, thủ tục Lựa_chọn (xem mục 3.2.6) mới thực hiện lựa chọn từ quần thể T các cá thể tốt hơn thông qua hàm thích nghi để đưa vào quần thể P. Cuối cùng P được đánh giá với các cá thể mới để kết thúc một bước lặp.Trong thủ tục trên, các biến Pmut1, Pmut2, Pmut3 là các tham số thể hiện xác suất được sử dụng các toán tử. Chúng có thể được cố định hoặc thay đổi giá trị trong quá trình thực hiện ứng dụng. 64
  65. CHƢƠNG 4: XÂY DỰNG ỨNG DỤNG MINH HỌA 4.1 Tổng quan về ứng dụng Ứng dụng sử dụng quần thể gồm 20 cá thể, mỗi cá thể được thể hiện bởi một nhiễm sắc thể có cấu trúc mảng hai chiều thể hiện thời khóa biểu của toàn bộ một trường học. Cấu trúc này dễ dàng chuyển về dạng cấu trúc mảng ba chiều như đã mô tả ở mục 3.2.2 sau khi tìm được lời giải đủ tốt. Việc sử dụng mảng hai chiều giúp ta có cái nhìn tổng thể về thời khóa biểu của toàn bộ trường, đồng thời dễ dàng xây dựng các toán tử di truyền và ít lãng phí bộ nhớ. Để giải quyết vấn đề về các buổi mà giáo viên phải họp tại bộ môn ứng dụng cho phép đánh dấu trước vào ngày đó để tránh phân lịch. Cuối cùng, ứng dụng cho phép quyết định lấy bao nhiêu lời giải đủ tốt để có thể chọn ra phương án vừa ý nhất. Menu chính: Hình 4.1 Menu ứng dụng 65
  66. 4.2 Một số chức năng vào giao diện của ứng dụng 4.2.1 Chức năng nhập dữ liệu 4.2.1.1 Chức năng nhập lớp môn học Nhập các lớp môn học cho quá trình xếp lịch thời khóa biểu tại đây. Sử dụng một lưới hiển thị kết nối tới cơ sở dữ liệu để hiệu chỉnh, xóa và thêm mới các lớp môn học. Menu tự động hiển thị khi di chuột tới trường dữ liệu tương ứng, có thể hiệu chỉnh trực tiếp trên lưới dữ liệu hoặc sử dụng các textbox và combobox bên dưới. Sử dụng các nút bên dưới để kết thúc hoặc áp dụng các thay đổi vào cơ sở dữ liệu thực tế. Hình 4.2 Trang nhập lớp môn học 66
  67. 4.2.1.2 Chức năng nhập giáo viên dự kiến Dùng lưới dữ liệu để hiện thị các bảng trong cơ sở dữ liệu, có thể tương tác với các dữ liệu trên lưới một cách trực quan và dễ sử dụng. Tại đây có thể nhập các môn mà giáo viên có khả năng dậy đồng thời cho phép đăng ký các ca bận của giáo viên trong tuần. Hình 4.3 Trang nhập giáo viên dự kiến 67
  68. 4.2.1.3 Chức năng nhập phòng học dự kiến Trang này chỉ để nhập mới hoặc sửa chứa các thông tin về phòng học. Hình 4.4 Trang nhập phòng học dự kiến 68
  69. 4.2.2 Chức năng hiển thị thời khóa biểu 4.2.2.1 Xem thời khóa biểu phòng học Sử dụng một dropdownlist để lựa chọn phòng học cần xem lịch. Hình 4.5 Thời khóa biểu của phòng học 4.2.2.2 Xem thời khóa biểu giáo viên Sử dụng tab ở phía trên để di chuyển qua lại giữa ba loại thời khóa biểu hoặc có thể sử dụng menu ở bên trái. Hình 4.6 Thời khóa biểu giáo viên 69
  70. 4.2.2.3 Xem thời khóa biểu các lớp môn học Tại đây hiển thị toàn bộ thời khóa biểu của các lớp môn học trong một kỳ. Hình 4.7 Thời khóa biểu các lớp môn học 4.3 Thử nghiệm ứng dụng Ứng dụng được chạy thử nhiều lần trên cùng một bộ dữ liệu thực tế, với các tham số biến dị cố định, kết qua thu được khá khả quan trong việc giải quyết các ràng buộc cứng và ràng buộc mềm. Qua thử nghiệm cho thấy, sau 50 tới 100 thế hệ tiến hóa với thời gian thực hiện từ 7 tới 15 phút có thể cho lời giải đủ tốt hoặc chấp nhận được. Hạn chế của ứng dụng này là tốc độ hội tụ còn kém, nếu cải tiến các tham số tĩnh bằng các tham số động thì chắc chắn sẽ hiệu quả hơn. 70
  71. 4.3.1 Kết quả đạt đƣợc của ứng dụng Các ràng buộc cứng: Giải quyết trọn vẹn các ràng buộc sau: Phòng học có đủ điều kiện để dạy lớp môn học đó. Chỉ có một lớp môn học được tổ chức tại một phòng học trong một ca xác định. Các lớp môn học từ 4 chỉ trở lên phải được chia thành hai ca học khác nhau. Tại một khoảng thời gian cho trước chỉ được một giáo viên dậy một lớp môn học tại một phòng xác định nào đó. Các ràng buộc mềm Các môn chuyên ngành của cùng một kỳ, cùng một khóa, thuộc cùng một ngành ít bị trùng lịch nhau để đảm bảo cho mọi sinh viên có thể đăng ký được hết các môn học. Các lớp môn học được chia thành hai ca học tại hai ngày có khoảng giãn cách trong tuần là phù hợp (thông thường khoảng cách giữa 2 ngày đó cách nhau từ 2-3 ngày là hợp lý). 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. 4.3.2 Bảng kết quả thực nghiệm Bộ dữ liệu thử nghiệm Gồm toàn bộ các lớp môn học được phòng đào tạo dự kiến mở cho khối ngành kỹ thuật CT, CTC, ĐC, ĐCC, XD, XDC, ĐT với tất cả các khóa cộng thêm các lớp thuộc bộ môn Giáo dục thể chất (GDTC) tổng cộng 405 lớp môn học. Tổng số giáo viên tham gia quy trình xếp thời khóa biểu tương ứng với 405 lớp môn học là 112 giáo viên. Một số lớp môn học như Giáo dục quốc phòng, kỹ năng thuyết trình và giao tiếp hiệu quả không xác định trước được giáo viên giảng dậy. Tổng số phòng học được sử dụng để xếp thời khóa biểu là toàn bộ dãy nhà A gồm 3 phòng máy và 24 phòng học cộng với tầng 1 và tầng 2 dãy nhà F gồm 3 phòng máy ở tầng 1 và 2 phòng thí nghiệm ở tầng 2 và cuối cùng là khu nhà tập đa năng và bể bơi sân bóng đá tổng cộng 37 phòng được sử dụng để xếp các lớp môn học vào. 71
  72. Tổng số trường tạo ra cho mối quan hệ giữa các giáo viên với các lớp môn học mình có thể dậy là 1132 trường. Bảng 4.1 Bảng kết quả đánh giá thực nghiệm ứng dụng Kết quả trung bình Kết quả tốt nhất Số ca cùng Số ca Số ca Số thế hệ Số ca trùng ngày của cùng ngày trùng lịch lịch GV các môn 4 của các GV chỉ môn 4 chỉ 30 20 15 0 0 50 0 0 0 0 72
  73. KẾT LUẬN Trong thời gian , đồ án đã đạt được một số kết quả sau: Tìm hiểu sơ bộ về bài toán xếp thời khóa biểu tín chỉ Tìm hiểu về giải thuật di truyền và phương pháp tính toán tiến hóa. . Áp dụng giải thuật di truyền vào bài toán xếp thời khóa biểu tín chỉ. Xây dựng thành công ứng dụng demo xếp thời khóa biểu tín chỉ. Tuy nhiên hạn chế thiếu sót nhất định. Do sử dụng các tham số tĩnh nên sự hội tụ của ứng dụng bằng nhau tại mọi thời điểm nên kết quả đạt được đôi khi không đủ tốt để tạo thành thời khóa biểu. Với một số lượng lớn các giá trị đầu vào tạo ra một không gian tìm kiếm cực lớn giải thuật di truyền phải tăng số lượng thế hệ lên khiến cho thời gian thực hiện ứng dụng tương đối lâu có thể lên tới cả vài tiếng điều này có thể gây khó khăn cho một số hệ thống. Các ràng buộc cho bài toán chỉ dừng lại ở mức cơ bản để tạo thành một thời khóa biểu thô chưa phản ánh được một thời khóa biểu hoàn chỉnh và đầy đủ trong thực tế. Trong tương lai em sẽ cố gắng bổ sung và phát triển thêm một số chức năng cho ứng dụng để người sử dụng có thể linh động hơn trong quá trình xếp lịch, đồng thời cũng nâng cấp thuật toán để có thể xử lý và giải quyết nhiều ràng buộc hơn trong thực tế. 73
  74. TÀI LIỆU THAM KHẢO [1]. Trần Quốc Hưng (2004), Luận văn thạc sĩ đề tài “Tính toán tiến hóa và ứng dụng lập thời khóa biểu trường trung học phổ thông”, Đại học Quốc Gia Hà Nội. [2]. Lưu Thị Liễu (2009), Đồ án Tốt Nghiệp đề tài “Xây dựng chương trình xếp thời khóa biểu phục vụ đào tạo tín chỉ cho khoa CNTT”, Trường Đại học Thái Nguyên. [3]. Hoàng Chính Nghĩa (2009), Đồ án Tốt Nghiệp đề tài “Tìm hiểu giải thuật di truyền ứng dụng giải bài toán lập lịch”, Trường ĐHDL Hải Phòng. [4]. Bùi Thị Oanh (2009), Đồ án Tốt Nghiệp đề tài “Nghiên cứu tính toán mềm và ứng dụng”, Trường ĐHDL Hải Phòng. [5]. Nguyễn Đức Khánh (2007), Đồ án Tốt Nghiệp đề tài “Lập thời khóa biểu tự động cho trường Đại học Bách Khoa”, Trường Đại học Bách Khoa Hà Nội 74