Luận văn: Ứng dụng giải thuật di truyền để xếp thời khóa biểu hệ tín chỉ cho trường đại học

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

234
lượt xem 40
download

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

Ứng dụng giải thuật di truyền để xếp thời khóa biểu hệ tín chỉ cho trường đại học nhằm đưa ra phương án xếp thời khóa biểu thõa mãn tất cả các ràng buộc đặt ra đồng thời khai thác hiệu quả các nguồn lực đào tạo của nhà trường với thời gian ngắn

Chủ đề:

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

Lưu

Nội dung Text: Luận văn: Ứng dụng giải thuật di truyền để xếp thời khóa biểu hệ tín chỉ cho trường đại học

-1- -2- B GIÁO D C VÀ ĐÀO T O Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Đ I H C ĐÀ N NG PH M ANH TU N Ngư i hư ng d n khoa h c: TS.Nguy n T n Khôi Ph n bi n 1: TS.Nguy n Thanh Bình NG D NG GI I THU T DI TRUY N Đ X P TH I KHÓA BI U H TÍN CH CHO TRƯ NG Đ I H C Ph n bi n 2: TS.Trương Công Tu n Chuyên ngành: KHOA H C MÁY TÍNH Mã s : 60.48.01 Lu n văn ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 21 tháng 7 năm 2012. TÓM T T LU N VĂN TH C SĨ K THU T Có th tìm hi u lu n văn t i: Đà N ng - Năm 2012 - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng.
-3- -4- M Đ U Vi t Nam hi n nay, các trư ng Đ i h c ñang d n chuy n 1. Lý do ch n ñ tài sang hình th c ñào t o tín ch . M c d u hình th c ñào t o này có nhi u ưu ñi m hơn so v i ñào t o niên ch tuy nhiên vi c x p th i Trong cu c s ng ta thư ng g p các bài toán liên quan ñ n x p khóa bi u v n là m t gánh n ng th c s cho các trư ng, ñ c bi t là l ch như x p l ch v n hành máy móc, x p l ch bi u cho vi c th c hi n các trư ng có quy mô ñào t o l n. V l i trên th trư ng cũng chưa m t d án, x p l ch làm vi c, x p l ch thi ñ u th thao,… Đ i v i lo i có s n ph m ph n m m nào gi i quy t hi u qu bài toán trên. bài toán này c n ph i tìm ra m t phương án x p l ch th a mãn t t c các ràng bu c cũng như khai thác hi u qu các ngu n tài nguyên hi n Trong nh ng năm g n ñây, phương pháp ti p c n di truy n ñã có, gi m th i gian và chi phí th c hi n. thu hút r t nhi u s chú ý trong các lĩnh v c nghiên c u khác nhau trong ñó có khoa h c máy tính. Phương pháp này có nhi u ñ c ñi m Bài toán x p th i khóa bi u trong trư ng h c nói chung và n i tr i như không ñòi h i tri th c, tránh t i ưu c c b , th c hi n t t trong trư ng Đ i h c nói riêng là m t trong nh ng bài toán như v y. v i các bài toán có không gian l i gi i l n và có th áp d ng cho Có r t nhi u các ràng bu c ñư c ñ t ra trong bài toán này như ràng nhi u lo i bài toán t i ưu khác nhau. Trên th gi i hi n nay, gi i thu t bu c v ñ i tư ng tham gia (gi ng viên, l p h c, sinh viên), ràng di truy n k t h p v i tin h c ñư c ng d ng ñ gi i quy t nh ng bài bu c v tài nguyên ph c v gi ng d y (phòng h c lý thuy t, phòng toán t i ưu m t cách r t hi u qu . th c hành,…), ràng bu c v th i gian (s ti t h c, s l n h c, s ti t m i l n), ràng bu c v chuyên môn và r t nhi u các ràng bu c khác Vì v y, vi c nghiên c u và ng d ng gi i thu t di truy n tùy thu c vào t ng trư ng. V n ñ ñ t ra là c n xây d ng m t th i (Genetic Algorithm - GA) ñ gi i quy t hi u qu bài toán x p th i khóa bi u th a mãn t t c các ràng bu c trên ñ ng th i khai thác hi u khóa bi u nói trên là vi c làm c n thi t. qu các ngu n tài nguyên ph c v gi ng d y. 2. M c tiêu và nhi m v nghiên c u Bài toán x p th i khóa bi u thu c l p các bài toán NP-ñ y ñ Đ tài t p trung nghiên c u và ng d ng gi i thu t di truy n vì v y có th không tìm ra ñư c l i gi i t i ưu. Đây là m t bài toán vào bài toán x p th i khóa bi u cho h tín ch t i m t trư ng ñ i h c không m i và ñã có nhi u gi i thu t ñư c ñưa ra ñ gi i quy t như ña ngành nh m ñưa ra phương án x p th i khóa bi u th a mãn t t c gi i thu t nhánh c n, gi i thu t leo ñ i, gi i thu t luy n thép, gi i các ràng bu c ñ t ra ñ ng th i khai thác hi u qu các ngu n l c ñào thu t tô màu ñ th , gi i thu t x p x ,… Tuy nhiên các gi i thu t này t o c a nhà trư ng v i th i gian ng n. thư ng không có tính t ng quát và ch áp d ng hi u qu ñ i v i các Đ ñ t ñư c các m c tiêu trên, ñ tài t p trung vào các nhi m trư ng h c có quy mô nh , ít ràng bu c v m t d li u. v c th sau:
-5- -6- - Phân tích ñ c ñi m c a bài toán x p th i khóa bi u h tín ch Phương pháp nghiên c u th c nghi m trong trư ng ñ i h c ñ t ñó ñ ra các gi i pháp h p lý trong vi c - Phân tích và thi t k h th ng x p th i khóa bi u h tín ch xây d ng và tri n khai h th ng. theo quy trình xây d ng ng d ng ph n m m. - Tìm hi u gi i thu t di truy n và ng d ng c a nó trong vi c - Xây d ng h th ng x p th i khóa bi u h tín ch s d ng gi i gi i quy t hi u qu các bài toán t i ưu. thu t di truy n. - ng d ng gi i thu t di truy n vào bài toán x p th i khóa bi u - Th nghi m h th ng và ñánh giá k t qu ñ t ñư c d a trên h tín ch trong trư ng Đ i h c. b d li u th và d li u th c t t i m t trư ng ñ i h c. 5. K t qu d ki n - Phân tích và ñánh giá k t qu ñ t ñư c khi th c hi n h th ng ñ i v i các b d li u th ñơn gi n. - Nh n th c ñ y ñ v th m nh c a gi i thu t di truy n trong vi c gi i các bài toán t i ưu. - Tri n khai th c nghi m v i b d li u x p th i khóa bi u c a - Đ ra ñư c gi i pháp và ng d ng các v n ñ c a gi i thu t m t s ngành t i Trư ng Đ i h c Bách khoa – Đ i h c Đà N ng. di truy n vào vi c gi i quy t bài toán x p th i khóa bi u h tín ch . 3. Đ i tư ng và ph m vi nghiên c u - Xây d ng h th ng ph n m m uniScheGA nh m ph c v - Nghiên c u các ñ c ñi m, ñ c trưng c a gi i thu t di truy n, cho vi c x p th i khóa bi u h tín ch t i m t s trư ng Đ i h c. các thành ph n cơ b n c a gi i thu t di truy n như kh i ñ ng qu n 6. Ý nghĩa khoa h c và th c ti n c a lu n văn th ban ñ u, ñánh giá ñ thích nghi c a cá th , các toán t di truy n (ch n l c, lai ghép, ñ t bi n), ñi u ki n d ng. V m t lý thuy t - ng d ng gi i thu t di truy n vào bài toán x p th i khóa - Áp d ng gi i thu t di truy n vào máy tính là phương pháp áp bi u t i m t trư ng ñ i h c ña ngành ñào t o theo h c ch tín ch v i d ng các quy lu t c a quá trình ti n hóa t nhiên vào vi c gi i quy t các ràng bu c và nh ng yêu c u cơ b n. các bài toán ph c t p mà các gi i thu t trư c ñó không ñáp ng ñư c. 4. Phương pháp nghiên c u - Vi c x p th i khoá bi u h tín ch s d ng gi i thu t di truy n là m t v n ñ tuy không m i nhưng l i chưa ñư c áp d ng Phương pháp nghiên c u lý thuy t hi u qu trong th c t . - Nghiên c u tài li u, ngôn ng và công ngh liên quan. - Ngoài bài toán x p th i khoá bi u, gi i thu t di truy n còn có - T ng h p các tài li u lý thuy t v gi i thu t di truy n. th ñư c ng d ng trong nhi u bài toán t i ưu khác. Vì v y k t qu - Bi u di n bài toán x p th i khóa bi u h tín ch trong trư ng nghiên c u c a ñ tài s t o n n t ng và cơ s ñ ti p t c nghiên c u ñ i h c s d ng mô hình gi i thu t di truy n. v sau.
-7- -8- CHƯƠNG 1: BÀI TOÁN X P TH I KHÓA BI U H TÍN V m t th c ti n CH VÀ CÁC PHƯƠNG PHÁP GI I QUY T - K t qu c a ñ tài là h th ng ph n m m uniScheGA dùng Chương này trình bày t ng quan v bài toán x p th i khóa bi u ñ x p th i khóa bi u h tín ch d s d ng, có tính tùy bi n cao, ñáp h tín ch trong trư ng ñ i h c và các phương pháp gi i quy t. ng t t nhu c u c a ngư i dùng. 1.1. BÀI TOÁN X P TH I KHÓA BI U H TÍN CH - H th ng có th ch y t t v i b d li u th c t t i các trư ng 1.1.1. Các quy trình x p th i khóa bi u h tín ch ñ i h c giúp gi m ñáng k th i gian và công s c trong vi c x p th i Trình bày các quy trình x p th i khóa bi u h tín ch , ñánh giá khóa bi u. ưu như c ñi m c a m i quy trình. 7. B c c lu n văn 1.1.2. Bài toán x p th i khóa bi u h tín ch N i dung chính c a lu n văn ñư c chia thành 4 chương sau: Trình bày chi ti t bài toán x p th i khóa bi u h tín ch , các Chương 1: Bài toán x p th i khóa bi u h tín ch và các thông tin, các ràng bu c và các yêu c u c a bài toán. phương pháp gi i quy t 1.1.2.1. Các thông tin c a bài toán Chương 2: Gi i thu t di truy n 1.1.2.2. Các ràng bu c c a bài toán Chương 3: ng d ng gi i thu t di truy n ñ x p th i khóa 1.1.3. Các mô hình x p th i khóa bi u h tín ch bi u h tín ch Trình bày các mô hình x p th i khóa bi u thông d ng hi n Chương 4: Tri n khai h th ng x p th i khóa bi u h tín ch ñang ñư c s d ng trong th c t . 1.1.3.1. Th i khóa bi u tu n 1.1.3.2. Th i khóa bi u h c kỳ 1.1.3.3. Th i khóa bi u (k) tu n/h c kỳ 1.1.3.4. Th i khóa bi u cho m i tu n 1.1.4. M c tiêu c a bài toán x p th i khóa bi u h tín ch 1.2. CÁC PH N M M X P TH I KHÓA BI U HI N NAY 1.2.1. Ph n m m th i khóa bi u t i Vi t Nam 1.2.2. Ph n m m th i khóa bi u trên th gi i
-9- - 10 - 1.3. CÁC PHƯƠNG PHÁP GI I QUY T BÀI TOÁN CHƯƠNG 2: GI I THU T DI TRUY N Trình bày các phương pháp gi i quy t bài toán x p th i khóa Chương này trình bày các khái ni m v gi i thu t di truy n và bi u h tín ch , ñánh giá ưu như c ñi m c a các phương pháp, lý do cách ng d ng nó vào gi i quy t m t s bài toán trong th c t . ch n gi i thu t di truy n ñ gi i quy t bài toán. 2.1. T NG QUAN V GI I THU T DI TRUY N 1.3.1. Các phương pháp truy n th ng 2.1.1. L ch s gi i thu t di truy n 1.3.1.1. Gi i thu t vét c n 2.1.2. T ng quan 1.3.1.2. Gi i thu t leo ñ i 1.3.2. Các phương pháp hi n nay 1.3.2.1. Gi i thu t luy n kim 1.3.2.2. Gi i thu t di truy n 1.3.2.3. Gi i thu t t i ưu ñàn ki n 1.3.3. Đánh giá phương pháp Các gi i thu t leo ñ i và luy n kim có r t nhi u như c ñi m và thư ng không tr v ñư c k t qu như mong ñ i. Các gi i thu t di truy n và t i ưu ñàn ki n có nhi u ưu ñi m hơn vì th hi n nay hai phương pháp này ñư c s d ng nhi u nh t ñ gi i quy t các bài toán t i ưu trong ñó có bài toán x 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 t p hơn so v i gi i thu t di truy n. Trên th c t công vi c l p th i khóa bi u t i các trư ng ñ i h c ch di n ra kho ng hai ñ n Hình 2.2. Sơ ñ t ng quan c a gi i thu t di truy n ba l n trong m t năm nên th i gian và chi phí cũng không nh hư ng nhi u. Vì v y trong lu n văn này ñ ñơn gi n tôi s d ng gi i thu t di 2.1.3. Các thao tác cơ b n truy n ñ gi i quy t bài toán x p th i khóa bi u h ñào t o tín ch cho 2.1.3.1. Bi u di n mô hình cá th trư ng ñ i h c. 2.1.3.2. Kh i t o qu n th ban ñ u 2.1.3.3. Xây d ng hàm thích nghi 2.1.3.4. Xây d ng các toán t di truy n
- 11 - - 12 - 2.1.3.5. Xác ñ nh các tham s cho gi i thu t 2.2.3.1. Đ t bi n ñ o ngư c 2.1.3.6. Xác ñ nh ñi u ki n d ng 2.2.3.2. Đ t bi n chèn 2.1.4. S khác bi t gi a gi i thu t di truy n so v i các gi i 2.2.3.3. Đ t bi n thay th thu t khác 2.2.3.4. Đ t bi n chuy n d ch Trình bày s khác bi t gi a gi i thu t di truy n so v i các gi i 2.3. CÁC THAM S C A GI I THU T DI TRUY N thu t tìm ki m và t i ưu bình thư ng. Gi i thu t di truy n có các tham s quan tr ng như kích thư c 2.2. CÁC TOÁN T DI TRUY N qu n th (popsize), xác su t lai ghép (pc), xác su t ñ t bi n (pm). Vi c 2.2.1. Toán t ch n l c l a ch n các tham s phù h p s tăng tính hi u qu c a gi i thu t. Ch n l c là quá trình ch n ra các NST có ñ thích nghi cao Trong các tham s trên thì popsize là quan tr ng nh t, n u trong qu n th hi n t i ñ ñưa vào qu n th th h ti p theo. ch n kích thư c qu n th quá nh thì tính ña d ng c a qu n th b 2.2.1.1. Toán t ch n l c t l h n ch và nh hư ng ñ n k t qu còn n u quá l n s làm hao phí tài 2.2.1.2. Toán t ch n l c c nh tranh nguyên c a máy tính và làm ch m quá trình ti n hóa. 2.2.1.3. Toán t ch n l c x p h ng 2.4. NG D NG GI I THU T DI TRUY N 2.2.2. Toán t lai ghép Đ ng d ng gi i thu t di truy n vào vi c gi i quy t m t bài Toán t lai ghép nh m t o ra NST con m i trên cơ s c p NST toán nào ñó c n ph i th c hi n m t s công vi c quan tr ng sau: cha - m b ng cách ghép các ño n gen trong NST cha - m l i v i 1. L a ch n cách bi u di n mô hình NST sao cho m i NST có nhau. Toán t lai ghép ñư c th c hi n v i m t xác su t pc nào ñó. th ch a ñ ng ñư c m t l i gi i c a bài toán. 2.2.2.1. Lai ghép m t ñi m 2. Xây d ng hàm ñánh giá ñ thích nghi cho t ng NST. Đây là 2.2.2.2. Lai ghép ña ñi m bư c khó khăn và nh hư ng l n ñ n tính hi u qu c a gi i thu t. 2.2.2.3. Lai ghép ñ ng nh t 3. L a ch n các toán t di truy n phù h p, trong ñó t p trung 2.2.3. Toán t ñ t bi n cho ba toán t chính là ch n l c, lai ghép và ñ t bi n. Đ t bi n là hi n tư ng NST con mang m t s ñ c tính không 4. Xác ñ nh các tham s c a gi i thu t di truy n như kích thư c có trong NST c a cha và m . Toán t ñ t bi n ñư c th c hi n v i qu n th , xác su t lai ghép, xác su t ñ t bi n. m t xác su t pm nh hơn nhi u so v i xác su t lai ghép pc b i vì trong t nhiên ñ t bi n gen thư ng ít x y ra. 5. Xác ñ nh ñi u ki n d ng cho quá trình ti n hóa.
- 13 - - 14 - CHƯƠNG 3: NG D NG GI I THU T DI TRUY N Đ X P M i NST có th xem là m t m ng 3 chi u: Chi u th nh t bi u TH I KHÓA BI U H TÍN CH di n các ti t h c trong ngày, chi u th hai bi u di n các ngày trong Chương này v n d ng các ki n th c v gi i thu t di truy n ñ tu n, chi u th ba bi u di n các phòng h c. áp d ng vào bài toán x p th i khóa bi u h tín ch . 3.1. QUY TRÌNH X P TH I KHÓA BI U Hình 3.5. C u trúc c a m t nhi m s c th 3.3. BI U DI N MÔ HÌNH QU N TH Hình 3.1. Quy trình x p th i khóa bi u ñ xu t Qu n th là t p h p các NST. Ngoài vi c lưu tr danh sách các 3.2. BI U DI N MÔ HÌNH CÁ TH NST, qu n th còn ch a thêm các thông tin khác như kích thư c 3.2.1. Bi u di n th i gian bi u qu n th , ñ thích nghi c a qu n th , … 3.2.2. Bi u di n mô hình cá th 3.4. KH I T O QU N TH M i NST dùng ñ ch a m t phương án x p th i khóa bi u. Trư c khi th c hi n quá trình ti n hóa c n ph i kh i t o qu n th b ng cách gán cho các gen trong NST b i các giá tr ng u nhiên. 3.5. BI U DI N RÀNG BU C TH I GIAN Mã l p 3.6. CÁC TOÁN T DI TRUY N 3.6.1. Toán t ch n l c Ta s d ng toán t ch n l c x p h ng ñ gi i quy t bài toán. V i cách làm này các NST trong qu n th ñư c s p x p gi m d n theo ñ thích nghi c a chúng. Hình 3.4. Bi u di n m t nhi m s c th
- 15 - - 16 - 3.6.2. Toán t lai ghép Trong ñào t o theo tín ch thì sinh viên ñư c xem là trung tâm Do bài toán có c u trúc NST khá ph c t p, vì v y ta ch n toán c a quá trình ñào t o. V i hình th c ñào t o này ngoài các ràng bu c t lai ghép ña ñi m ñ áp d ng v i các ñi m ñư c t o ng u nhiên. cơ b n v gi ng viên, phòng h c, chuyên môn,… thì sinh viên cũng Ch n hai NST ng u nhiên c n lai ghép: N1 (cha), N2 (m ) có th ch ñ ng l a ch n chương trình h c phù h p v i ñi u ki n và G i hai NST con ñư c sinh ra: C1, C2 năng l c c a mình. T o m t n lai ghép M (m ng 1 chi u) v i các ñi m lai ghép ng u nhiên For each gen in NST: Tuy nhiên, s lư ng sinh viên thư ng r t l n, m i sinh viên l i Begin có m t yêu c u v th i khóa bi u khác nhau. Vì v y ch c ch n không If (M[i] = 1) Then th th a mãn ñ ng th i cho t t c các sinh viên ñư c mà ch th a mãn C1 nh n gen t NST cha N1 C2 nh n gen t NST m N2 t i ña trong ñi u ki n cho phép. If (M[i] = 0) Then C1 nh n gen t NST m N2 3.8.2. Phương pháp gi i quy t C2 nh n gen t NST cha N1 Đ u m i h c kỳ, nhà trư ng l p danh sách các l p h c ph n d End ki n m , phân công GV gi ng d y r i cho sinh viên ñăng ký h c. 3.6.3. Toán t ñ t bi n D a vào s li u ñăng ký h c ta s phân thành các nhóm. M i Toán t ñ t bi n ñư c th c hi n ñ i v i các NST con sinh ra nhóm là t p h p các sinh viên ñăng ký các l p h c ph n gi ng nhau. b i toán t lai ghép, ta áp d ng toán t ñ t bi n thay th . K t h p các nhóm l i v i nhau sao cho các l p h c ph n không G i pm là xác su t ñ t bi n b trùng l p và t ng s l p h c ph n b ng v i t ng s l p c n x p For each gen in NST: th i khóa bi u. Begin x = S nguyên ng u nhiên trong kho ng t 1 ñ n 1000 Ch n phương án k t h p các nhóm sao cho t ng s sinh viên If (x < pm*1000) Then ñăng ký h c ñư c th a mãn yêu c u là l n nh t. Begin rangen = Là m t gen ng u nhiên trong NST Áp d ng gi i thu t di truy n ñ x p th i khóa bi u cho các gen = rangen End nhóm l p ñư c ch n trên. End 3.9. TÍNH Đ THÍCH NGHI C A CÁ TH 3.7. PHÂN NHÓM L P H C PH N 3.9.1. Tính ñ thích nghi c a cá th 3.8. X P TKB H TÍN CH THEO YÊU C U C A SV Vi c ñánh giá ñ thích nghi c a cá th ñư c căn c vào s l n 3.8.1. Yêu c u c a sinh viên trong bài toán x p TKB h tín ch vi ph m các ràng bu c. Đ th c hi n, ñ u tiên ta tính ñ thích nghi
- 17 - - 18 - c a cá th d a trên t ng ràng bu c, sau ñó c ng t t c ñ thích nghi 3.9.3. Tính ñ thích nghi d a vào ràng bu c trùng gi GV d a trên t ng ràng bu c ñó l i ta s thu ñư c ñ thích nghi c a cá th . Vi ph m ràng bu c trùng gi gi ng viên x y ra khi m t gi ng Đ tăng tính hi u qu c a gi i thu t, tùy thu c vào t ng lo i viên ñư c phân công gi ng d y nhi u hơn m t l p t i m t th i ñi m. ràng bu c mà ta nhân s l n vi ph m v i m t tr ng s thích h p. Function Đ _thích_nghi_LDB (Cathe) Begin Function Đ _thích_nghi_RB (Cathe) Count = 0 {Bi n ñ m s l n vi ph m ràng bu c} Begin For each gv: Count = 0 {Bi n ñ m s l n vi ph m} Begin For each gen in Cathe For each ngày, ti t h c: Begin Begin If (gen vi ph m ràng bu c RB) Then Count = Count + 1 C = 0 {Kh i t o bi n ñ m s l n ñ t l ch c a gi ng viên} End For each phòng: Return 1/(Count * Tr ng s ) Begin End l p = Cathe [phòng, ngày, ti t] 3.9.2. Tính ñ thích nghi d a vào ràng bu c v nhóm l p If (Gi ng_d y (l p) = gv) Then C = C + 1 End Đ thu n l i cho sinh viên ñăng ký h c ngư i ta thư ng t o ra If (C > 1) Then Count = Count + (C-1) End các nhóm l p. Các l p trong cùng nhóm không ñư c trùng l ch h c. End Function Đ _thích_nghi_RCC (Cathe) Return 1/ (Count * Tr ng s ) Begin End For each nhóm: Begin 3.9.4. Tính ñ thích nghi d a vào ràng bu c gi b n c a GV For each ngày, ti t h c: Begin Khi x p th i khóa bi u m i gi ng viên có th có nh ng ti t C = 0 {Kh i t o bi n ñ m s l n ñ t l ch c a nhóm} không th lên l p vì lý do riêng ho c b n sinh ho t chuyên môn. For each phòng: Function Đ _thích_nghi_LUA (Cathe) Begin Begin lop = Cathe [phòng, ngày, ti t] Count = 0 {Bi n ñ m s l n vi ph m ràng bu c} If (lop ∈ nhóm) Then C = C + 1 For each phòng: End Begin If (C > 1) Then Count = Count + (C-1) For each ngày, ti t h c: End Begin End l p = Cathe [phòng, ngày, ti t] Return 1/ (Count * Tr ng s ) gv = Gi ng_d y (l p) End If (Gv_b n_gi (gv, ngày, ti t)) Then Count = Count + 1 End
- 19 - - 20 - End Begin Return 1/ (Count * Tr ng s ) For each ngày, ti t h c: End Begin If (l p = Cathe [phòng, ngày, ti t]) Then C = C + 1 3.9.5. Tính ñ thích nghi d a vào ràng bu c s c ch a phòng End End Vi ph m s c ch a c a phòng x y ra khi m t l p ñư c x p l ch Count = Count + Abs (S ti t tu n quy ñ nh - C) h c t i phòng có s c ch a nh hơn s lư ng sinh viên c a l p ñó. End Return 1/ (Count * Tr ng s ) Function Đ _thích_nghi_RTS (Cathe) End Begin Count = 0 {Bi n ñ m s l n vi ph m ràng bu c} 3.9.8. Tính ñ thích nghi d a vào ràng bu c s l n h c For each phòng: Begin D a vào s ti t h c trong tu n c a m i l p cũng như ñ c thù For each ngày, ti t h c: c a t ng h c ph n mà ngư i ta quy ñ nh s l n h c t i thi u, t i ña. Begin l p = Cathe [phòng, ngày, ti t] Function Đ _thích_nghi_NSW (Cathe) If (S _SV (l p) > S _ch _ng i (phòng)) Then Count = Count+1 Begin End For each phòng: End Begin Return 1/ (Count * Tr ng s ) For each ngày, bu i h c: End Begin PreClass = -1 {Bi n ch a tên l p ñ t l ch ti t trư c ñó } 3.9.6. Tính ñ thích nghi d a vào ràng bu c gi b n c a phòng For each ti t h c: Begin Tương t như gi ng viên, m i phòng h c cũng có nh ng ti t Class = Cathe [phòng, ngày, ti t] b n không th s d ng ñư c. If (Class PreClass) Then arrCount[Class] = arrCount[Class] +1 3.9.7. Tính ñ thích nghi d a vào ràng bu c s ti t trong tu n PreClass = Class Đ ñ m b o ti n ñ , ñ i v i các l p h c ph n thì t ng s ti t End End trong tu n ph i ñúng v i quy ñ nh. End Function Đ _thích_nghi_NHW (Cathe) For each l p: Begin Begin Count = 0 {Bi n ñ m s l n vi ph m ràng bu c} If ((arrCount[i] < S l n min) or (arrCount[i] > S l n max)) Then For each l p: Count=Count+Min(Abs(arrCount[i]-min), Abs(arrCount[i]-max)) Begin End C = 0 {Bi n ñ m s ti t trong tu n} Return 1/ (Count * Tr ng s ) For each phòng End
- 21 - - 22 - 3.9.9. Tính ñ thích nghi d a vào ràng bu c s ti t h c m i l n ph m nào c n x lý sau, ñi u này d n ñ n vi c có th không tìm ra Thông thư ng m i l n x p l ch ph i ñ m b o s ti t t 2 tr ñư c phương án x p th i khóa bi u th a mãn yêu c u. lên, ngo i tr m t s l p h c ph n ñ c thù ñòi h i th i gian nhi u Nguyên t c 1: Ràng bu c nào c n ñ t ñư c trư c thì ñ t tr ng như th c hành, thí nghi m thì s ti t h c m i l n có th nhi u hơn. s th p, ràng bu c nào c n ñ t ñư c sau thì ñ t tr ng s cao. 3.9.10. Tính ñ thích nghi d a vào ràng bu c lo i phòng Nguyên t c 2: Ràng bu c nào khó ñ t ñư c hơn thì ñ t tr ng Tùy theo tính ch t c a h c ph n mà m i l p s yêu c u m t s th p, d ñ t ñư c hơn thì ñ t tr ng s cao. lo i phòng khác nhau như lý thuy t, th c hành, thí nghi m,… Nguyên t c 3: Ràng bu c m m nên ñ t tr ng s cao hơn so 3.9.11. Tính ñ thích nghi d a vào s bu i lên l p c a GV v i ràng bu c c ng. Vì các ràng bu c m m là nh ng ràng bu c thêm, n u ñ t ñư c thì càng t t còn không thì cũng có th ch p nh n ñư c. H u h t các gi ng viên ñ u mong mu n gi m thi u s bu i lên l p c a h trên cơ s v n ñ m b o s lư ng ti t gi ng d y. Đây là 3.10. THAM S C A GI I THU T DI TRUY N m t yêu c u r t chính ñáng, vì v y c n ph i ñưa tiêu chí này vào ñ Trong lu n văn này tôi l a ch n các tham s c a gi i thu t di ñánh giá ñ thích nghi c a cá th . truy n như sau: pc = 0.5, pm = 0.015, popsize = s lư ng l p × 50. Sau 3.9.12. Tính ñ thích nghi d a vào kho ng cách di chuy n c a m i th h popsize tăng lên kho ng 0.02%. gi ng viên Trong m t bu i gi ng viên ph i di chuy n ñ n nhi u phòng ñ CHƯƠNG 4: TRI N KHAI H TH NG X P TH I KHÓA gi ng d y các l p khác nhau. Đ i v i các trư ng có khuôn viên r ng BI U H TÍN CH l n, các phòng h c có th n m cách xa nhau thì kho ng th i gian D a trên k t qu nghiên c u c a các chương trư c tôi ñã cài ngh gi a các ti t h c không ñ ñ gi ng viên di chuy n và ít nhi u ñ t thành công h th ng uniScheGA dùng ñ x p th i khóa bi u h nh hư ng ñ n s c kh e. Vì v y c n thi t ph i gi m thi u kho ng tín ch cho trư ng ñ i h c. cách di chuy n c a gi ng viên trong quá trình gi ng d y. 4.1. CÁC CH C NĂNG C A H TH NG 3.9.13. Tr ng s c a các lo i vi ph m ràng bu c 4.1.1. Nh p các danh m c d li u h th ng Trong các lo i ràng bu c, m i lo i ràng bu c có m t tính ch t riêng. Có lo i vi ph m ràng bu c thư ng xuyên x y ra và có lo i ít 4.1.2. Nh p danh sách l p h c ph n x y ra hơn. Có lo i d ñ t ñư c và có lo i khó ñ t ñư c hơn. Vì v y, 4.1.3. Nh p ràng bu c th i gian b n n u xem xét các ràng bu c này m t cách bình ñ ng thì ch c ch n h 4.1.4. X p th i khóa bi u th ng s không xác ñ nh ñư c vi ph m nào c n x lý trư c và vi
- 23 - - 24 - 4.2.1.5. K t qu th nghi m Qua quá trình th nghi m ta th y các ràng bu c NHW, NHS, NSW khó ñ t ñư c hơn so v i các ràng bu c còn l i. Th i gian th c hi n chương trình kho ng t 2 ñ n 4 phút. 1 T ng vi ph m 1 2 Vi ph m NHW 3 Vi ph m NHS 4 Vi ph m NSW 2 5 Vi ph m LUA ... 3 4 5 Hình 4.4. Giao di n x p th i khóa bi u 4.1.5. Tra c u th i khóa bi u Hình 4.7. Bi u ñ minh h a k t qu th nghi m l n 1 H th ng cho phép xem th i khóa bi u c a t ng l p h c ph n, 4.2.2. K ch b n th nghi m 2 nhóm l p, gi ng viên, sinh viên và l ch s d ng t ng phòng. Ph n này trình bày quá trình th nghi m h th ng uniScheGA 4.2. K T QU TH NGHI M H TH NG X P TKB v i b d li u th c t t i Trư ng Đ i h c Bách khoa - ĐHĐN. 4.2.1. K ch b n th nghi m 1 4.2.2.1. Mô t d li u 4.2.1.1. D li u ñ u vào 4.2.2.2. K t qu th nghi m D li u th nghi m g m có 8 l p h c ph n, t ng s ti t c n 4.2.3. Nh n xét x p là 48, s gi ng viên là 3 và s phòng h c là 4 (trong ñó có 1 Quá trình th nghi m h th ng th c t cho th y n u s l p c n phòng th c hành). x p tăng lên thì th i gian th c hi n s tăng nhanh theo hàm mũ. 4.2.1.2. Các ràng bu c Trong quá trình th nghi m tác gi nh n th y n u chia nh d li u ñ 4.2.1.3. Các tham s x p th i khóa bi u nhi u l n thì t ng th i gian c a các l n s nh hơn 4.2.1.4. C u hình th nghi m r t nhi u so v i th i gian ñ x p khi không chia nh .
- 25 - - 26 - K T LU N VÀ HƯ NG PHÁT TRI N - Th c thi h th ng trên các b d li u l n (kho ng 100 l p 1. K T QU Đ T ĐƯ C h c ph n, kho ng t 300 ñ n 500 ti t / tu n) thư ng khá ch m. Khi ñó ph i chia nh d li u ñ th c hi n nhi u l n. Qua quá trình th c hi n lu n văn, tôi ñã có ki n th c ñ y ñ v 2. PH M VI NG D NG gi i thu t di truy n, bi t cách v n d ng gi i thu t di truy n vào vi c gi i quy t m t s bài toán t i ưu, ñ c bi t là các bài toán t i ưu có H th ng có th ng d ng t t ñ i v i các trư ng ñ i h c, cao không gian tìm ki m l n. ñ ng ñào t o theo tín ch . V n d ng ñư c gi i thu t di truy n ñ xây d ng h th ng ph n Đ i v i các trư ng x p th i khóa bi u theo quy trình ngư c l i m m uniScheGA x p th i khóa bi u h tín ch cho trư ng ñ i h c: t c là cho sinh viên ñăng ký h c r i m i x p th i khóa bi u thì trong - H th ng ñáp ng t t t t c các ràng bu c ñư c nêu ra trong nhi u trư ng h p h th ng chưa cho ra ñư c k t qu mong mu n. lu n văn bao g m các ràng bu c c ng và m m. H th ng có th ng d ng ñ x p th i khóa bi u cho nh ng - H th ng ch y n ñ nh, có giao di n ñ p, có bi u ñ minh trư ng có quy mô ñào t o l n, khi ñó ñ th c hi n hi u qu ta nên h a tr c quan trong quá trình x p th i khóa bi u. chia nh d li u r i ti n hành x p th i khóa bi u nhi u l n. - Cho phép x p th i khóa bi u t m t tu n b t kỳ trong h c kỳ 3. HƯ NG PHÁT TRI N trên cơ s có tính ñ n các ñi u ki n ràng bu c v gi ng viên, v Đ h th ng ngày càng hoàn thi n hơn và ch y nhanh hơn c n phòng h c tu n hi n t i. ph i ti p t c nghiên c u và phát tri n h th ng theo các hư ng sau: - K t qu x p th i khóa bi u ñư c trình bày ña d ng bao g m - Tích h p thêm các ràng bu c x p th i khóa bi u ngoài các th i khóa bi u c a t ng l p, t ng gi ng viên, t ng sinh viên, t ng ràng bu c cơ b n ñư c ñ c p trong lu n văn. Khi th c hi n ngư i s nhóm và l ch s d ng t ng phòng h c. d ng có th tùy ý l a ch n các ràng bu c mà mình c n ñáp ng. - D li u th i khóa bi u có th d dàng xu t sang Acrobat - Song song hóa gi i thu t GA ñ x lý ñ ng th i trên nhi u Reader, Microsoft Excel và có th tra c u t website. máy tính nh m tăng t c ñ th c hi n chương trình. Tuy nhiên, h th ng cũng còn có m t s t n t i sau: - Ti p t c hoàn thi n hàm ñánh giá ñ thích nghi ñ tùy theo - Yêu c u c a bài toán x p th i khóa bi u trong th c t khá ña ng c nh có th t ñi u ch nh các tr ng s sao cho phù h p nh t. d ng trong khi h th ng hi n t i ch ñáp ng ñư c các yêu c u cơ b n - Nghiên c u k t h p gi i thu t di truy n v i các k thu t khác ñư c nêu ra. như m ng Nơron, lôgic m ,… ñ nâng cao hi u qu cho h th ng.