zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Đề xuất giải thuật di truyền giải bài toán xếp thời khóa biểu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Báo xấu

173
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đề xuất sử dụng giải thuật di truyền để giải bài toán xếp thời khóa biểu trường phổ thông, một loại bài toán xếp thời khóa biểu phổ biến. Nghiên cứu đã cài đặt và thí nghiệm giải thuật đề xuất trên một số bộ dữ liệu thực tế.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề xuất giải thuật di truyền giải bài toán xếp thời khóa biểu

TRƯỜNG ĐẠI HỌC SÀI GÒN SAIGON UNIVERSITY TẠP CHÍ KHOA HỌC SCIENTIFIC JOURNAL ĐẠI HỌC SÀI GÒN OF SAIGON UNIVERSITY Số 71 (05/2020) No. 71 (05/2020) Email: tcdhsg@sgu.edu.vn ; Website: http://sj.sgu.edu.vn/ ĐỀ XUẤT GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN XẾP THỜI KHÓA BIỂU Proposing a genetic algorithm to solve timetabling problem Nguyễn Hồ Thiên Đăng(1), Nguyễn Thị Hồng Bích(2), Thái Minh Tân(3), TS. Phan Tấn Quốc(4) (1)Học viên cao học Trường Đại học Sài Gòn (2) Trường THPT Ngô Quyền, Q.7, TP.HCM (3)Công ty TMA Solutions, TP.HCM (4) Trường Đại học Sài Gòn TÓM TẮT Việc xếp thời khóa biểu hợp lý là bài toán tối ưu có nhiều ứng dụng trong thực tế. Được phân loại thuộc lớp NP-complete và đã được nghiên cứu rộng rãi trong hàng chục năm qua với các hướng tiếp cận như quy hoạch toán học, tối ưu dựa trên ràng buộc, tối ưu đa mục tiêu, giải thuật tham lam, giải thuật metaheuristic.v.v. Nghiên cứu này đề xuất sử dụng giải thuật di truyền để giải bài toán xếp thời khóa biểu trường phổ thông, một loại bài toán xếp thời khóa biểu phổ biến. Nghiên cứu đã cài đặt và thí nghiệm giải thuật đề xuất trên một số bộ dữ liệu thực tế. Kết quả thực nghiệm cho thấy giải thuật đề xuất cho kết quả tốt hơn một số phần mềm hỗ trợ xếp thời khóa biểu cho các trường phổ thông hiện nay trên dựa trên trọng số một số ràng buộc của bài toán. Từ khóa: thời khóa biểu, thời khóa biểu trường phổ thông, giải thuật di truyền ABSTRACT Timetabling problem is optimization problems that have many practical applications; this is the problem of class NP-complete. Timetabling problem has been widely studied over the past decades with approaches such as mathematical programming, constraint-based approaches, multiobjective optimization, greedy algorithms, metaheuristic algorithms, etc. In this study, we propose a genetic algorithm to solve a form of Timetabling problem that is the School Timetabling problem. The proposed algorithm was conducted on some real data sets. Experimental results claim that our algorithm results in better results than some of the current school Timetabling software based on some constraints of the problem. Keywords: genetic algorithm, timetabling problem, school timetabling 1. Giới thiệu định (thường là theo tuần) sao cho thỏa Bài toán xếp thời khóa biểu trường học mãn được nhiều ràng buộc nhất có thể của (timetabling problem) là tạo ra một lịch bài toán. Bài toán xếp thời khóa biểu thuộc phân công giảng dạy giữa người dạy và lớp bài toán tối ưu NP-complete [1]. người học trong một chu kỳ thời gian cố Bài toán xếp thời khóa biểu được biết Email: quocpt@sgu.edu.vn 87
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 71 (05/2020) đến rộng rãi với 3 dạng sau: bài toán xếp của lớp đó; các giáo viên có thể dạy môn thời khóa biểu trường phổ thông (school học ngoài chuyên môn chính, gọi là công timetabling-STTP); bài toán xếp thời khóa tác kiêm nhiệm. biểu trường đại học (course timetabling- Lớp học: lớp học gồm tập các học CTTP); bài toán xếp lịch thi (examination sinh học chung với nhau ở tất cả các môn timetabling-ETTP) [1]. học. Đã có nhiều công trình nghiên cứu về Phạm vi bài toán xếp thời khóa biểu đề bài toán xếp thời khóa biểu dựa trên các cập trong nghiên cứu này là các khối lớp hướng tiếp cận như giải thuật tô màu đồ thị, 10, 11 và 12. tiếp cận dựa trên ràng buộc, quy hoạch toán Phòng học: với bài toán xếp thời khóa học, tối ưu đa mục tiêu, giải thuật tham lam biểu ở trường phổ thông, mỗi lớp được cấp [2], giải thuật metaheuristic [3], [4], [5], cố định một phòng học lý thuyết trong suốt [6], [7]. năm học; mỗi phòng học có thêm thông tin Trong nghiên cứu này, chúng tôi đề là phòng học lý thuyết hay phòng thực xuất một giải thuật metaheuristic dạng hành, thực nghiệm. quần thể là giải thuật di truyền để giải bài Môn học: có thể gọi là môn, mỗi khối toán xếp thời khóa biểu trường phổ thông lớp trong một học kỳ có từ 13 đến 17 môn; với hy vọng có thể khắc phục được bẩy tối Môn ngữ văn, thể dục, quốc phòng phải ưu cục bộ so với các metaheuristic dạng cá xếp tiết cặp và không xếp tiết 2-3 vì sau thể khác. tiết 2 là giờ giải lao; Môn toán, tiếng Anh, 2. Bài toán xếp thời khóa biểu phổ Tin học cũng khuyến khích xếp tiết cặp. thông Các môn đã xếp tiết cặp thì một buổi 2.1. Một số khái niệm không xếp quá một cặp. Chu kỳ thời khóa biểu: chu kỳ thời Bảng phân công: bảng phân công khóa biểu là số ngày mà thời khóa biểu cần giảng dạy gồm một tập các phân công; mỗi xếp lịch, tính từ thứ Hai đến thứ Bảy. phân công bao gồm các thông tin về giáo Nhóm thời gian: nhóm thời gian là viên, lớp học, môn học, tổng số tiết môn tập hợp nhóm các tiết trong một chu kỳ học trong tuần. thời khóa biểu; buổi sáng từ tiết 1 đến tiết 2.2. Ràng buộc của bài toán xếp thời 5, buổi chiều từ tiết 6 đến tiết 8, sau 2 tiết khóa biểu đầu của mỗi buổi học sẽ có giờ giải lao. Ràng buộc của bài toán xếp thời khóa Định dạng khuôn mẫu các buổi học thông biểu được phân làm hai loại: ràng buộc thường ở trường phổ thông hiện như sau: cứng (hard constraints) và ràng buộc mềm từ thứ Hai đến thứ Sáu, mỗi buổi các lớp (soft constraints). học đủ 5 tiết; riêng thứ Bảy có thể học ít Ràng buộc cứng là các ràng buộc đã hơn tuỳ theo tổng số tiết các môn cả tuần, được quy định trong các văn bản của ngành. tổng số tiết này thay đổi tuỳ học kỳ và tuỳ Ví dụ môn học cần xếp có tiếp cặp, buổi khối lớp. học của các lớp không có tiết lủng.v.v. Ràng Giáo viên: các giáo viên có thể được buộc cứng là loại ràng buộc, không thể vi phân công làm công tác chủ nhiệm lớp, phạm, trừ trường hợp bất khả kháng. giáo viên chủ nhiệm lớp nào thì phải được Ràng buộc mềm là các ràng buộc phân công giảng dạy ít nhất một môn học thường do giáo viên hoặc lớp học yêu cầu 88
NGUYỄN HỒ THIÊN ĐĂNG và cộng sự TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN để làm tăng chất lượng thời khóa biểu. Các Ràng buộc về các môn học có tiết cặp ràng buộc mềm cần được xếp thỏa mãn (8): một số môn học theo quy định bắt càng nhiều càng tốt. Khi có nhiều ràng buộc phải có ít nhất một tiết cặp để đáp buộc mềm thì độ ưu tiên giữa chúng cũng ứng yêu cầu về chuyên môn. là yếu tố cần xem xét. Ràng buộc về mỗi môn học chỉ học Ràng buộc cứng của bài toán xếp một lần trong một buổi tại mỗi lớp (9): thời khóa biểu phổ thông trong một buổi học, một môn học chỉ có Ràng buộc đụng độ giáo viên (1): các thể xuất hiện nhiều nhất một lần (một tiết phân công đối với cùng giáo viên thì không lẻ hoặc tiết cặp). xếp vào cùng vị trí tiết học. Ràng buộc tiết trống của lớp theo buổi Ràng buộc đụng độ lớp học (2): các (10): tiết trống là tiết không bố trí dạy học phân công đối với cùng lớp học thì không xen giữa các tiết học khác; thực tế thì thời xếp vào cùng vị trí tiết học. khóa biểu các lớp ở trường phổ thông cần Ràng buộc đụng độ phòng học (3): được xếp sao cho không có hiện tượng mỗi phòng học chỉ được xếp vào nhiều trống tiết. nhất một phân công tại một vị trí tiết học. Ràng buộc về tiết không xếp của giáo Việc đụng độ phòng học chỉ có thể xảy ra ở viên (11): tiết không xếp là tiết theo quy các phòng thí nghiệm, thực hành, sân tập định của ngành, của cơ sở giáo dục; thời thể dục. khóa biểu của giáo viên cần xếp tránh các Ràng buộc về số tiết học liên tiếp tối tiết không xếp này, ví dụ ngày sinh hoạt thiểu và số tiết học liên tiếp tối đa (4): chuyên môn của giáo viên được xem là các thông số này là (1,2) đối với bài toán STTP tiết không xếp. và đây cũng là điểm khác biệt so với bài Ràng buộc mềm của bài toán xếp toán CTTP. Ở bài toán CTTP, số tiết học thời khóa biểu phổ thông liên tiếp tối thiểu, tối đa có thể là (2,k) với Ràng buộc về lịch bận của giáo viên 2 ≤ k ≤ 6. (1): mỗi giáo viên có lịch bận riêng. Ràng buộc thời gian rảnh của giáo Ràng buộc về học cách ngày (2): nên viên, lớp học, phòng học (5): các phân xếp các môn học học cách ngày trong tuần. công không được vi phạm thời gian rảnh Ràng buộc về độ nén lịch dạy của giáo của giáo viên, của lớp học, của phòng học. viên (3): nên xếp lịch dạy của giáo viên sao Ràng buộc về tính đầy đủ của phân cho số buổi mà giáo viên đi dạy là ít nhất công (6): tất cả các phân công đều phải có thể; gọi n là số buổi dạy của giáo viên được xếp thời khóa biểu. Nếu giải thuật thì: n ≤ số tiết trong tuần của giáo viên/5 không xếp được tất cả phân công thì cần gỡ +1. dần các ràng buộc mềm và tiến hành lại việc Ràng buộc về tiết trống của giáo viên xếp thời khóa biểu. Một giải thuật xếp được (4): mỗi buổi giáo viên có thể trống tiết tối tất cả các phân công không đồng nghĩa giải đa 1 lần (trống 1 tiết hoặc 2 tiết liên tục); thuật đó sẽ tạo ra thời khóa biểu tốt. trong một tuần số tiết trống của mỗi giáo Ràng buộc về phân công xếp sẵn (7): viên không vượt quá 3. tiết xếp sẵn là tiết được ưu tiên xếp trước Ràng buộc về số tiết dạy tối thiểu và mọi tiết khác xếp sau sẽ tránh các tiết trong một buổi của giáo viên (5): mỗi giáo xếp sẵn này. viên dạy ít nhất 2 tiết trong một buổi. 89
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 71 (05/2020) Ràng buộc về số tiết học tối thiểu nếu môn học mi có thể xếp vào phòng rj và trong một buổi học của một lớp (6): số tiết ngược lại. tối thiểu trong mỗi buổi học của một lớp là Tập A ={A1, A2,..., Aq} gồm q phân 2 tiết. công, tập Ai cho biết chi tiết của phân công Ràng buộc về số môn học tối đa giáo viên tj giảng dạy môn mf cho lớp Cv: trong mỗi buổi (7): số môn học tối đa Ai={tj, Cv, mf}. trong mỗi buổi là 4; trường hợp bất khả Tập lời giải S của bài toán gồm x phân kháng có 5 môn trong một buổi học thì 5 công được gán tiết học và phòng học môn học đó không cùng thuộc nhóm môn S={S1, S2,...,Sx}, trong đó tập Si gồm phân học xã hội (Văn, Sử, Địa, Giáo dục công công Ai được xếp vào tiết học Pj với số tiết dân, Tiếng Anh). liên tiếp là kv (với k=1,2) và tại phòng học Ràng buộc về số tiết tối đa của một rm: Si={Ai, pj, kv, rm}. giáo viên trong một lớp trong mỗi buổi (8): Để đánh giá được chất lượng của một tránh xếp một giáo viên dạy một lớp nhiều lời giải thì ta sử dụng một hàm mục tiêu hơn 2 tiết/buổi học (không tính tiết sinh biểu diễn tổng trọng số các vi phạm của hoạt chủ nhiệm). Trường hợp này có thể các ràng buộc của bài toán; trong đó các xảy ra đối với các môn học có nhiều hơn 2 ràng buộc cứng đã được chuyển thành các tiết hoặc các giáo viên dạy lớp đó 2 môn ràng buộc mềm có trọng số cao. học. 2.3. Mô hình hóa bài toán xếp thời khóa biểu Bài toán xếp thời khóa biểu gồm các Trong đó: S là lời giải - là thời khóa yếu tố sau: biểu toàn trường, n là tổng số các ràng Tập P ={p1, p2,…,pm} gồm m tiết học, buộc của bài toán, wi là trọng số vi phạm tập T ={t1, t2,…,tn} gồm n giáo viên, ma của ràng buộc thứ i (wi ≥ 0, với i=1..n), di trận PT cho biết tiết rảnh của mỗi giáo là số lần vi phạm ràng buộc thứ i (di ≥ 0, viên, trong đó PTij=1 nếu giáo viên ti rảnh với i=1..n) [4]. tiết pj và PTij=0 nếu ngược lại. Ký hiệu f(S) là giá trị hàm mục tiêu của Tập C ={c1, c2,…,ch} gồm h lớp học, lời giải S, giá trị hàm mục tiêu càng cao thì ma trận PC cho biết tiết rảnh của lớp học, độ thích nghi càng thấp và ngược lại. trong đó PCij=1 nếu lớp học ci rảnh tiết pj 2.4. Tiêu chí đánh giá chất lượng thời và PCij=0 nếu ngược lại. khóa biểu Tập R ={r1, r2,...,rk} gồm k phòng học, Chất lượng của một thời khóa biểu thể ma trận PR cho biết tiết rảnh của phòng hiện qua thời khóa biểu của các lớp học và học, trong đó PRij=1 nếu phòng học ri rảnh thời khóa biểu của mỗi giáo viên. Việc đánh tiết pj và PRij=0 nếu ngược lại. giá chất lượng một thời khóa biểu là công Tập M ={m1, m2,…, my} gồm y môn việc khó khăn và thông thường giáo viên sẽ học, tập PM gồm y tổng số tiết học trong đánh giá dựa vào thông tin thời khóa biểu có tuần của các môn học tương ứng trong tập vi phạm các ràng buộc của bài toán. M tức PM={pm1, pm2,…, pmy}. 3. Giải thuật di truyền giải bài toán Tập MR gồm các môn học được phân xếp thời khóa biểu công vào các phòng học, trong đó MRij=1 Trong phần này, chúng tôi sẽ đề xuất 90
NGUYỄN HỒ THIÊN ĐĂNG và cộng sự TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN một giải thuật metaheuristic, cụ thể là giải biểu T1’ và T2’. T1’ và và T2’ ban đầu được thuật di truyền [5], [7], [8] để giải bài toán gán bằng T1 và T2. xếp thời khóa biểu ở trường phổ thông. Lấy ngẫu nhiên một đoạn các gen 3.1. Tạo quần thể ban đầu trong mỗi cặp cá thể cha-mẹ thỏa mãn ràng Quần thể ban đầu được tạo gồm N cá buộc về tính chất gen của bài toán – ở đây thể T1, T2,...,TN, trong đó mỗi cá thể là một là cùng một lớp nào đó, giả sử đó là đoạn lời giải của bài toán, tức là một thời khóa (p1,p2). Duyệt các đoạn gen từ (p1,p2) trong biểu toàn trường. Mỗi cá thể gồm nhiều cá thể cha-mẹ T1, nếu có gen nào làm cho gen, mỗi gen được khởi tạo ngẫu nhiên từ cá thể T2’ tốt hơn thì cập nhật T2’. Công tập các phân công đã cho sao cho trước hết đoạn này kết thúc ta được cá thể con T2’. phải thỏa mãn được các ràng buộc cứng Tương tự, duyệt các đoạn gen từ của bài toán. (p1,p2) trong cá thể cha-mẹ T2, nếu có gen Chất lượng các cá thể của quần thể ban nào làm cho cá thể T1’ tốt hơn thì cập nhật đầu được khởi tạo ngẫu nhiên thường có T1’. Công đoạn này kết thúc ta được cá thể chất lượng kém hơn so với chất lượng của con T1’. các cá thể được khởi tạo bằng các heuristic Các cá thể gốc T1 và T2 không thay đổi của bài toán. Tuy nhiên do sự đa dạng của trong quá trình này; các cá thể T1’ và T2’ các cá thể khi khởi tạo ngẫu nhiên, nên lúc sinh ra từ phép lai phải thỏa mãn các ràng kết thúc quá trình tiến hóa, giải thuật di buộc của bài toán. truyền ứng với quần thể ban đầu (được Phép lai hai cá thể T1 và T2 để được hai khởi tạo ngẫu nhiên) thường cho chất cá thể con T1’ và T2’. Ta đưa 2 cá thể con lượng lời giải tốt hơn. này vào quần thể mới - nghĩa là sau khi 3.2. Độ thích nghi của cá thể thực hiện phép lai, số cá thể của quần thể sẽ Độ thích nghi của mỗi cá thể thời khóa lớn hơn N, giả sử đó là N’. Phép chọn ở biểu được xác định là giá trị của hàm mục cuối mỗi thế hệ có nhiệm vụ loại bớt một số tiêu. Giá trị hàm mục tiêu càng nhỏ thì cá cá thể có độ thích nghi kém hơn để đảm thể thời khóa biểu có chất lượng càng cao. bảo kích thước quần thể không đổi trong 3.3. Phép lai mỗi lần bắt đầu thế hệ tiến hóa tiếp theo. Mục này trình bày cách chọn các cá 3.4. Phép đột biến thể và cách thực hiện phép lai, cách xử lý Mục này trình bày cách chọn các phân các cá thể con sinh ra từ phép lai. công trong các cá thể để thực hiện phép đột Chọn các cá thể thời khóa biểu tham biến, cách thực hiện phép đột biến và cách gia phép lai xử lý các cá thể con sinh ra từ phép đột Cho xác xuất lai là pc, đối với mỗi cá biến. thể trong quần thể P, ta phát sinh ngẫu Phép đột biến được tiến hành sau khi nhiên một số thực r  [0..1]. Nếu r ≤ pc, thì thực hiện phép lai (trước khi thực hiện chọn cá thể đó để tham gia phép lai. Ta sẽ phép chọn). Kích thước của quần thể lúc tiến hành thực hiện phép lai từng cặp các thực hiện phép đột biến là N’. cá thể thời khóa biểu theo thứ tự mà chúng Chọn ngẫu nhiên một phân công, giả được chọn. sử đó là phân công X (tức 1 cụm tiết gồm Phép lai hai cá thể thời khóa biểu cha- các thông tin: giáo viên, môn học, lớp, số mẹ T1,T2 để sinh ra hai cá thể thời khóa tiết, vị trí tiết đầu đã bố trí cụm tiết.v.v.). 91
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 71 (05/2020) Thực hiện di chuyển cụm tiết đó từ vị trí u giải thuật chạy hết một lượng thời gian đến vị trí v trong cùng lớp hoặc qua một định trước. Trong bài toán xếp thời khóa lớp khác mà vẫn đảm bảo lớp khác ở đây biểu trường phổ thông đang xét, chúng tôi cũng có giáo viên, môn học phù hợp với chọn điều kiện dừng đầu tiên. phân công X. Nếu không tìm được vị trí v 3.7. Giải thuật di truyền giải bài toán phù hợp thì phép đột biến đó không được xếp thời khóa biểu thực hiện. Chúng tôi gọi giải thuật này là STTGA Theo nguyên tắc đột biến, cá thể sau (School Timetabling Problem Genetic đột biến không nhất thiết phải tốt hơn trước algorithm). đột biến. Vì xét về cả quá trình tiến hóa, Dữ liệu đầu vào: danh sách các phân một cá thể chưa tốt ở thế hệ này vẫn sẽ có công, danh sách các ràng buộc, bộ trọng số khả năng giúp quá trình tiến hóa sinh ra các vi phạm ứng với mỗi ràng buộc cá thể tốt ở những thế hệ tiếp theo. Dữ liệu đầu ra: thời khóa biểu của Xử lý các cá thể con sinh ra mỗi lớp, thời khóa biểu của mỗi giáo viên Giả sử cá thể T sau đột biến sinh ra cá Giải thuật di truyền giải bài toán xếp thể T’, khi đó ta có hai cách xử lý sau đây: thời khóa biểu - STTGA Cách thứ nhất là nếu T’ tốt hơn T thì thay T bằng T’, nếu T’ kém hơn T thì xem 1: Khởi tạo quần thể ban đầu với N cá thể như phép đột biến không thực hiện gì cả. ngẫu nhiên, trong đó mỗi lời giải là một Cách thứ hai là thay T bằng T’ mà thời khóa biểu toàn trường, mỗi gen của không quan tâm đến chất lượng lời giải của cá thể ứng với một phân công; T’. Trong bài báo này, chúng tôi chọn thực 2: Xác suất lai là pc, xác suất đột biến là pm; hiện phép đột biến thứ hai. 3: Đánh giá độ thích nghi mỗi cá thể trong 3.5. Phép chọn lọc quần thể, cá thể T có giá trị hàm mục là Chúng tôi sử dụng phép chọn lọc các C(T), cá thể T càng tốt nếu C(T) có giá cá thể dựa trên độ thích nghi xếp hạng trị càng bé và ngược lại; bằng cách bố trí chung theo độ thích nghi 4: while (điều kiện dừng chưa thỏa) giảm dần (tức theo chiều tăng dần của giá { trị hàm mục tiêu), sau đó chọn N cá thể có a) Chọn ngẫu nhiên một cặp cá thể độ thích nghi cao nhất. cha-mẹ từ quần thể; Để không làm mất đi cá thể tốt nhất b) Phép lai (crossover): nếu xảy ra xác được khai phá trong suốt quá trình tiến suất lai ghép pc thì lai ghép hai cá hóa, giải thuật của chúng tôi luôn cập nhật thể cha-mẹ để tạo thành các cá thể cá thể tốt nhất cho đến thời điểm hiện tại con, ngược lại, các cá thể con giống (cá thể ưu tú). cá thể cha-mẹ; 3.6. Điều kiện dừng c) Đột biến (Mutation): nếu xảy ra xác Thường các giải thuật di truyền chọn suất đột biến pm thì đột biến bằng các điều kiện dừng sau đây: thứ nhất là lời cách cho thay đổi nhỏ trong cá thể; giải tốt nhất tìm được của bài toán không d) Đánh giá lại độ thích nghi của các được cải thiện sau một số lần lặp định cá thể, tức tính lại giá trị của hàm trước ; thứ hai là số lần lặp của giải thuật mục tiêu; đạt đến một giá trị định trước ; thứ ba là e) Chọn lọc (Selection): thay thế các 92
NGUYỄN HỒ THIÊN ĐĂNG và cộng sự TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN cá thể có độ thích nghi ít hơn; Chúng tôi thực nghiệm giải thuật di } truyền STTGA trên 2 bộ dữ liệu thực tế tại 5: Cá thể tốt nhất của thế hệ sau cùng là Trường Trung học phổ thông Giồng Ông lời giải của bài toán. Tố, Quận 2, Thành phố Hồ Chí Minh. Bộ 4. Thực nghiệm và đánh giá thứ nhất có tên gọi là HK11920, bộ thứ hai 4.1. Dữ liệu thực nghiệm có tên gọi là HK21920. Bảng 1. Thông số các bộ dữ liệu thực nghiệm HK11920 HK21920 STT Loại dữ liệu (Số lượng) (Số lượng) 1 Số giáo viên có phân công 76 73 2 Số phòng học 36 36 3 Số môn học 45 44 4 Số phân công 485 475 5 Số ràng buộc cứng 11 11 6 Số ràng buộc mềm 8 8 7 Số buổi học trong tuần 6 6 8 Số tiết tối đa trên mỗi buổi học 5 5 Các ràng buộc cứng 1, 2, 3, 9, 10, 11 ở 6, 7, 8 còn lại luôn được thỏa mãn khi cài trên được mềm hóa với trọng số cao (các đặt. Do đó, bài toán có 6 ràng buộc cứng và giá trị này được đề xuất qua quá trình thực 8 ràng buộc mềm cần được xử lý theo liệt nghiệm thực tế), các ràng buộc cứng 4, 5, kê ở Bảng 2 và Bảng 3. Bảng 2. Trọng số vi phạm của ràng buộc cứng Ràng Đối tượng Tên ràng buộc Trọng số buộc ràng buộc H1 Ràng buộc đụng độ giáo viên 999 Giáo viên H2 Ràng buộc đụng độ lớp học 999 Lớp H3 Ràng buộc đụng độ phòng học 999 Phòng học Ràng buộc về mỗi môn học chỉ học một lần trong H4 600 Lớp một buổi tại mỗi lớp H5 Ràng buộc tiết lủng của lớp theo buổi 600 Lớp H6 Ràng buộc về tiết không xếp của giáo viên 600 Giáo viên 93
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 71 (05/2020) Bảng 3. Trọng số vi phạm của ràng buộc mềm Ràng Đối tượng Tên ràng buộc Trọng số buộc ràng buộc S1 Ràng buộc về lịch bận của giáo viên 15 Giáo viên S2 Ràng buộc về học cách ngày môn học 10 Lớp S3 Ràng buộc về độ nén lịch dạy của giáo viên 20 Giáo viên S4 Ràng buộc về tiết lủng của giáo viên 25 Giáo viên Ràng buộc về số tiết dạy tối thiểu trong một buổi của S5 10 Giáo viên giáo viên Ràng buộc về số tiết học tối thiểu trong một buổi học S6 20 Lớp của một lớp S7 Ràng buộc về số môn học tối đa trong mỗi buổi 15 Lớp Ràng buộc về số tiết tối đa của một giáo viên trong S8 20 Lớp một lớp trong mỗi buổi 4.2. Môi trường thực nghiệm các ràng buộc thời khóa biểu các lớp và thời Giải thuật STTGA được chúng tôi cài khóa biểu các giáo viên để làm cơ sở so sánh đặt bằng ngôn ngữ C++ sử dụng môi trường chất lượng lời giải giữa các giải thuật. CodeBlocks 17.12, và thực nghiệm trên 4.5. Đánh giá về chất lượng của giải máy tính hệ điều hành Windows 10 64bit, thuật đề xuất Processor Intel(R) Core (TM) i3-814U Chúng tôi so sánh chất lượng thời CPU @ 2.10GHz 2.30GHz, RAM 4GB. khóa biểu kết quả của giải thuật di truyền 4.3. Tham số thực nghiệm STTGA với thời khóa biểu thực tế đã triển Trong quá trình thực nghiệm, chúng khai tại Trường Trung học phổ thông tôi đề xuất xác suất lai ghép pc= 0.85 và Giồng Ông Tố, Quận 2, Thành phố Hồ Chí xác suất phép đột biến pm = 0.05, với số Minh – chúng tôi gọi giải thuật này là lượng cá thể trong quần thể là 75. GOT. Trong đó, giải thuật GOT tạo nên 4.4. Kết quả thực nghiệm thời khóa biểu qua hai giai đoạn: thực hiện Kết quả thực nghiệm của giải thuật di tự động bằng các phần mềm hỗ trợ xếp thời truyền STTGA bao gồm thời khóa hiểu của khóa biểu và tinh chỉnh thủ công với sự mỗi lớp học và lịch dạy của mỗi giáo viên. kiểm tra tự động của các phần mềm hỗ trợ Từ đó, chúng tôi ghi nhận tình trạng vi phạm xếp thời khóa biểu. 94
NGUYỄN HỒ THIÊN ĐĂNG và cộng sự TẠP CHÍ KHOA HỌC ĐẠI HỌC SÀI GÒN Bảng 4. Thống kê số lần vi phạm các ràng buộc của các lớp theo giải thuật GOT và giải thuật di truyền STTGA trên các bộ dữ liệu HK11920 và HK21920 Bộ dữ Lớp H1 H2 H3 H4 H5 H6 S1 S2 S3 S4 S5 S6 S7 S8 liệu STTGA 0 0 0 0 0 0 0 0 0 0 0 0 28 0 HK11920 GOT 0 0 0 15 0 0 0 54 0 0 0 0 26 0 STTGA 0 0 0 0 0 0 0 9 0 0 0 0 28 0 HK21920 GOT 0 0 0 4 0 0 0 36 0 0 0 0 20 0 Xét bộ dữ liệu HK11920, giải thuật liệu HK21920, giải thuật STTGA và giải STTGA và giải thuật GOT cho tổng số lần thuật GOT cho tổng số lần vi phạm trên vi phạm trên các ràng buộc H4, S2, S7 lần các ràng buộc H4, S2, S7 lần lượt là (0, 4), lượt là (0, 15), (0, 54), (28, 26). Xét bộ dữ (9, 36), (28, 20). Bảng 5. Thống kê số lần vi phạm ràng buộc của các giáo viên theo toán thuật GOT và giải thuật di truyền STTGA trên các bộ dữ liệu HK11920 và HK21920 Bộ dữ Giáo viên H1 H2 H3 H4 H5 H6 S1 S2 S3 S4 S5 S6 S7 S8 liệu STTGA 0 0 0 0 0 0 0 0 53 7 19 0 0 0 HK11920 GOT 0 0 0 0 0 0 6 0 12 93 1 0 0 0 STTGA 0 0 0 0 0 0 0 0 47 3 16 0 0 0 HK21920 GOT 0 0 0 0 0 0 27 0 12 91 0 0 0 0 Xét bộ dữ liệu HK11920, giải thuật trường phổ thông và đã đề xuất giải thuật STTGA và giải thuật GOT cho tổng số lần di truyền STTGA nhằm giải bài toán xếp vi phạm trên các ràng buộc S1, S3, S4, S5 thời khóa biểu trường phổ thông. Nghiên lần lượt là (0, 6), (53, 12), (7, 93), (19, 1). cứu đã cài đặt và thực nghiệm giải thuật di Xét bộ dữ liệu HK21920, giải thuật truyền STTGA trên 2 bộ dữ liệu thực tế STTGA và giải thuật GOT cho tổng số lần với tổng cộng 960 phân công. Kết quả vi phạm trên các ràng buộc S1, S3, S4, S5 thực nghiệm tổng hợp trên hai bộ dữ liệu lần lượt là (0, 27), (47, 12), (3, 91), (16, 0). cho thấy: với thời khóa biểu các lớp, tổng Thời gian chạy thực nghiệm giải thuật số lần vi phạm các ràng buộc cứng và các STTGA trên 2 bộ dữ liệu trên là hơn 202 ràng buộc mềm ứng với giải thuật di giờ và chúng tôi ghi nhận kết quả tốt nhất truyền STTGA và giải thuật GOT lần lượt làm kết quả của giải thuật. là (0, 65), (19, 136); với thời khóa biểu 5. Kết luận các giáo viên, số lần vi phạm các ràng Nghiên cứu đã chỉ ra được một số đặc buộc cứng và các ràng buộc mềm ứng với trưng của bài toán xếp thời khóa biểu giải thuật di truyền STTGA và giải thuật 95
SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 71 (05/2020) GOT lần lượt là (0, 145), (0, 242). Nghiên với các chiến lược tìm kiếm lân cận để cứu này có thể cho phép phát triển các nâng cao hơn nữa chất lượng lời giải của chiến lược đột biến, lai ghép và kết hợp bài toán. Lời cảm ơn Nhóm tác giả trân trọng cảm ơn lãnh đạo Trường THPT Giồng Ông Tố đã cho phép sử dụng thời khóa biểu của trường làm dữ liệu thực nghiệm; cảm ơn các Thầy, Cô Khoa Công nghệ Thông tin Trường Đại học Sài Gòn đã có những ý kiến đóng góp cho luận văn thạc sỹ “Đề xuất giải thuật di truyền giải bài toán xếp thời khóa biểu”; cảm ơn các nhà khoa học đã phản biện và cho những ý kiến đóng góp quý báu giúp nhóm tác giả hoàn chỉnh bài báo. TÀI LIỆU THAM KHẢO [1] Dominique de Werra, “An Introduction to Timetabling”, European Journal of Operational Research, 19(2), 151-162, 1985. [2] Trương Quốc Định và Nguyễn Thanh Hải, “Giải thuật xếp thời khóa biểu ứng dụng vào bài toán quản lý xếp lịch thi kết thúc các lớp học phần tại trường Đại học Cần Thơ”, Tạp chí khoa học trường Đại học Cần Thơ, 43(a), 116-125, 2016. [3] Nguyễn Bá Phúc, “Thuật giải bees cho bài toán xếp thời khoá biểu”, thạc sĩ khoa học, chuyên ngành Khoa học máy tính, Trường ĐH Khoa học tự nhiên, ĐH Quốc gia TP Hồ Chí Minh, 2011. [4] Nguyễn Tấn Trần Minh Khang, “Nghiên cứu ứng dụng các giải thuật Metaheuristic cho bài toán xếp thời khóa biểu môn học trường đại học”, tiến sĩ Khoa học, chuyên ngành Khoa học máy tính, Trường ĐH Khoa học Tự nhiên, ĐH Quốc gia TP Hồ Chí Minh, 2014. [5] Nguyễn Đình Thúc, Trí tuệ nhân tạo - Lập trình tiến hóa, Nhà xuất bản Giáo dục, 2008. [6] Nguyen Khang, Nguyen Dang, Trieu Khon, Tran Nuong, “Automating a Real-World University Timetabling Problem with Tabu Search Algorithm”, IEEE RIVF International Conference on Computing & Communication Technologies, Research, Innovation, and Vision for the Future, 1-6, 2010. [7] Nguyen Quoc Viet Hung, Ta Quang Binh, Duong Tuan Anh, “A Memetic Algorithm for Timetabling”, RIVF’05 Research Informatics Vietnam-Francophony, Can Tho, 2005. [8] Xin She Yang, Engineering optimization: an introduction with metaheuristic applications, John Wiley & Sons, 2010. [9] Carlos Lara, Juan José Flores, Félix Calderón, “Solving a School Timetabling Problem Using a Bee Algorithm”, Proceedings of the 7th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence, 664 – 674, 2008. [10] S.N. Sivanandam, S.N. Deepa, "Introduction to genetic algorithms", Springer, 2008. Ngày nhận bài: 11/4/2020 Biên tập xong: 15/5/2020 Duyệt đăng: 20/5/2020 96

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.