Luận văn thạc sĩ: Thuật giải di truyền và ứng dụng lập thời khóa biểu theo học chế 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

145
lượt xem 30
download

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

Thuật giải di truyền và ứng dụng lập thời khóa biểu theo học chế tín chỉ cho trường đại học tìm hiểu và tiếp cận thuật giải di truyền cho lớp bài toán lập lịch và cụ thể là bài toán lập thời khóa biểu học theo hệ tín chỉ cho trường đại học.

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 thạc sĩ: Thuật giải di truyền và ứng dụng lập thời khóa biểu theo học chế 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 LÊ TI N M U Ngư i hư ng d n khoa h c: PGS.TSKH TR N QU C CHI N Ph n bi n 1: THU T GI I DI TRUY N VÀ NG D NG L P TH I KHÓA BI U THEO H C CH TÍN CH Ph n bi n 2: CHO TRƯ NG Đ I H C Lu n văn s ñư c b o v t i H i ñ ng ch m Lu n văn t t Chuyên ngành: Khoa h c máy tính nghi p th c sĩ khoa h c h p t i Đ i h c Đà n ng vào ngày Mã s : 60.48.01 ……..tháng………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: - Trung tâm Thông tin - H c li u, Đ i H c Đà N ng - Thư vi n Trư ng Đ i h c Bách khoa, Đ i h c Đà N ng Đà N ng – Năm 2012
3 4 M Đ U Nghiên c u ng d ng nh ng k t qu nghiên c u vào th c t . 1. Lý do ch n ñ tài 5. Ý nghĩa khoa h c và th c ti n c a ñ tài Bài toán l p l ch có th ñư c ñ nh nghĩa là m t bài toán tìm 5.1. Ý nghĩa khoa h c ki m chu i t i ưu ñ th c hi n m t t p các ho t ñ ng ch u tác ñ ng Thông qua ñ tài s hi u rõ hơn v bài toán l p l ch các các c a m t t p các ràng bu c c n ph i ñư c th a mãn. Ngư i l p l ch phương pháp ti p c n gi i bài toán l p l ch, qua ñó có s so sánh và thư ng c g ng th ñ n m c t i ña s s d ng các cá th , máy móc ñánh giá các thu t toán. và t i thi u th i gian ñòi h i ñ hoàn thành toàn b quá trình nh m Tìm hi u sâu v thu t gi i di truy n và ng d ng vào bài toán s p x p l ch t i ưu nh t. Vì th bài toán l p l ch là m t v n ñ r t khó th i khóa bi u nh m có nh ng c i ti n trong các bư c c a thu t gi i ñ gi i quy t. di truy n v i bài toán c th như vi c bi u di n bài toán, cách ch n Trong ñ tài, s tìm hi u và ti p c n thu t gi i di truy n cho cá th t t, cách xây d ng hàm ñánh giá, … l p bài toán l p l ch và c th là bài toán l p th i khóa bi u h c theo 5.2. Ý nghĩa th c ti n h tín ch cho trư ng ñ i h c. Bài toán l p th i khóa bi u là m t bài toán có nhi u ng d ng 2. M c ñích nghiên c u trong th c t , ñ c bi t là các trư ng ñ i h c, cao ñ ng ñào t o theo Nghiên c u, tìm hi u thu t gi i di truy n và trên cơ s ñó ti p h c ch tín ch . ng d ng thu t gi i di truy n ñ gi i bài toán th i c n ñ gi i bài toán th i khóa bi u theo h tín ch . khóa bi u là m t hư ng hy v ng gi i quy t ñư c bài toán th i khóa 3. Đ i tư ng và ph m vi nghiên c u bi u. Tìm hi u bài toán l p l ch và các hư ng gi i quy t truy n Qua ñ tài có th xây d ng ng d ng th c t góp ph n gi m th ng. thi u th i gian và ngu n l c cho vi c l p th i khóa bi u cho m t cơ Tìm hi u thu t gi i di truy n. s . ng d ng thu t gi i di truy n vào bài toán l p th i khóa bi u 6. C u trúc lu n văn Xây d ng ng d ng l p th i khóa bi u theo h c ch tín ch cho Lu n văn g m các chương có n i dung như sau trư ng ñ i h c, cao ñ ng. Chương 1 - T NG QUAN BÀI TOÁN L P L CH 4. Phương pháp nghiên c u Chương 2 - THU T GI I DI TRUY N D a trên các tài li u thu th p t nhi u ngu n (sách, báo, Chương 3 - NG D NG THU T GI I DI TRUY N VÀO BÀI Internet,… ) t ng h p, phân tích và trình bày l i theo s hi u bi t c a TOÁN L P TH I KHÓA BI U b n thân. M r ng cách ti p c n trư c ñây trên cơ s phân tích ñ c thù bài toán c n gi i quy t ñ có nh ng c i ti n h p lý.
5 6 ñi m, và các phòng h c ph i ñ m b o ch ng i cho sinh viên ñ sinh viên có ch ng i h c t p. Đ i v i yêu c u v giáo viên là m t giáo CHƯƠNG 1 - T NG QUAN BÀI TOÁN L P L CH viên không th d y ñư c hai l p trong cùng m t th i gian. V 1.1. Gi i thi u bài toán l p l ch chương trình, các môn h c trong cùng m t chương trình ph i ñư c 1.1.1. Tìm hi u chung s p x p khác th i ñi m ñ sinh viên ñư c l a ch n h c. Và v i m i môn h c có s ti t ñư c quy ñ nh trư c và th i khoá bi u ph i ñ m 1.1.2. Các thu c tính c a bài toán l p l ch b o s ti t h c c a môn h c ñó. 1.1.3. M t s lo i bài toán l p l ch 1.3. M t s hư ng ti p c n gi i bài toán th i khóa bi u 1.2. Bài toán th i khóa bi u 1.3.1. Mô ph ng luy n kim 1.2.1. Gi i thi u bài toán 1.3.2. Tìm ki m Tabu 1.2.2. D li u bài toán Ph n này tìm hi u, kh o sát các thành ph n, ñ i tư ng thông CHƯƠNG 2 - THU T GI I DI TRUY N tin có tác ñ ng tr c ti p ho c gián ti p ñ n bài toán th i khoá bi u: 2.1. T ng quan v thu t gi i di truy n Giáo viên, h c ph n (môn h c),Tín ch , L p h c ph n, Phòng h c, Ti t h c(gi h c). 2.1.1. Gi i thi u M t s cơ s ñào t o Cao ñ ng, Đ i h c c a nư c ta hi n nay Trong thu t gi i di truy n ngư i ta dùng thu t ng vay mư n m t s tài nguyên ñi u b h n ch do m t s nguyên nhân ch quan c a di truy n h c như: cá th , nhi m s c th (nhi m s c th ), gen, và khách quan. Vì v y, ñ s p x p th i khoá bi u t t tho mãn t t c qu n th , ñ thích nghi, ch n l c, lai ghép, ñ t bi n, v.v… Trong ñó các yêu c u là h t s c khó khăn. Tuy nhiên không ch khó khăn v s cá th (individual, genotypes, structure) bi u di n m t l i gi i, gi i thi u th n các tài nguyên trên mà còn có s nh hư ng c a m t s pháp c a bài toán, không gi ng như trong t nhiên m t cá th có th ràng bu c, yêu c u ph i tho mãn c a bài toán. có nhi u nhi m s c th , ñây chúng ta quy ư c m i cá th ch có m t nhi m s c th (chromosome). Các nhi m s c th là m t có th là m t 1.2.3. Ràng bu c c a bài toán chu i tuy n tính, trong nhi m s c th có th có các ñơn v nh hơn ñó Các ràng bu c là các yêu c u c n ph i ñư c tho mãn, n u là gen. M i gen ñ i di n m t thu c tính, tính ch t và có v trí nh t m t trong nh ng yêu c u này không tho mãn thì th i khoá bi u s ñ nh trong nhi m s c th . Qu n th (population) là m t t p h p h u không th ñưa vào s d ng. M t s yêu c u v phòng h c như: hai h n xác ñ nh các cá th , trong thu t gi i di truy n qu n th là m t t p l p h c khác nhau không th h c cùng m t phòng h c t i m t th i
7 8 các cá th bi u di n m t t p các l i gi i. Các phép toán ch n l c • Phương pháp gi i tích (selection), lai ghép (crossover), ñ t bi n (mutation) ñư c th c hi n • Phương pháp tìm ki m ng u nhiên trên qu n th ñ t o ra m t qu n th m i. Đ c trưng c a thu t gi i di truy n so v i các phương pháp truy n M t bài toán ñư c gi i b ng thu t gi i di truy n thông th ng: thư ng ph i qua các bư c sau: Thu t gi i di truy n làm vi c v i s mã hoá c a t p thông s Bi u di n l i gi i c a bài toán (hay nhi m s c th ) ch không làm vi c v i các giá tr c a các thông s . b ng chu i nh phân, chu i ký t , s th p phân, … Kh i t o qu n th ban ñ u g m N cá th m t cách Thu t gi i di truy n tìm ki m t m t qu n th các ñi m ch ng u nhiên. không ph i t m t ñi m. Xây d ng hàm thích nghi làm tiêu chu n ñánh giá Thu t gi i ch s d ng thông tin v các tiêu chu n t i ưu c a các cá th theo ñ thích nghi c a chúng. hàm m c tiêu ch không dùng các thông tin h tr nào khác. Xác ñ nh xác su t lai t o, xác su t ñ t bi n, … Thu t gi i s d ng các lu t chuy n ñ i mang tính xác su t ch Xây d ng các phép toán lai t o, ch n l c, ñ t bi n. không ph i là các lu t chuy n ñ i mang tính xác ñ nh. Lưu ñ thu t gi i di truy n: Thu t gi i thư ng khó cài ñ t, áp d ng. Tuy nhiên không ph i lúc nào cũng cho l i gi i chính xác. M t s thu t gi i di truy n có th cung c p l i gi i ti m năng cho m t bài toán xác ñ nh ñ ngư i s d ng l a ch n.[6] 2.1.3. Tính ch t c a thu t gi i di truy n 2.2. Các thành ph n trong thu t gi i di truy n 2.2.1. Bi u di n nhi m s c th Hình 2.1. Sơ ñ kh i mô t thu t gi i di truy n t ng quát 2.2.1.1. Bi u di n nh phân 2.1.2. S khác bi t c a thu t gi i di truy n và thu t gi i khác 2.2.1.2. Bi u di n s d ng hoán v Khi dùng phương pháp truy n th ng có m t s cách gi i sau: 2.2.1.3. Bi u di n b ng giá tr • Phương pháp li t kê 2.2.2. Kh i t o qu n th ban ñ u
9 10 2.2.3. Đánh giá cá th Tính theo th i gian, ph thu c vào th i gian ch y chương trình ñư c quy ñ nh trư c và thu t toán d ng. 2.2.4. Phương pháp ch n l c K t h p nhi u phương pháp khác nhau, thu t gi i cũng có th 2.2.4.1. Ch n l c t l s d ng k t h p nhi u phương pháp khác nhau ñ gi i quy t v n ñ . 2.2.4.2. Ch n l c x p h ng 2.2.6. Các tham s c a thu t gi i di truy n 2.2.4.3. Ch n l c c nh tranh 2.2.6.1. Kích thư c qu n th 2.2.5. Phương pháp lai ghép 2.2.6.2. Xác su t lai ghép 2.2.5.1. Lai ghép m t ñi m 2.2.6.3. Xác su t ñ t bi n 2.2.5.2. Lai ghép ña ñi m 2.3. Ví d minh h a 2.2.5.3. Lai ghép ánh x t ng ph n 2.3.1. Bi u di n nhi m s c th 2.2.5.4. Lai ghép có tr t t 2.3.2. Hàm thích nghi 2.2.5.5. Lai ghép d a trên v trí 2.3.3. Kh i t o qu n th 2.2.5.6. Lai ghép th t tuy n tính 2.3.4. Ch n l c cá th 2.2.5.7. Lai ghép có chu trình 2.3.5. Phương pháp lai ghép 2.2.6. Toán t ñ t bi n 2.3.6. Phương pháp ñ t bi n 2.2.7. Đi u ki n d ng c a thu t gi i 2.3.7. Các tham s s d ng trong bài toán và ñi u ki n d ng M t s ñi u ki n d ng c a thu t gi i: K t thúc theo k t qu , t c khi giá tr thích nghi c a cá th trong qu n th có giá tr sai s nh hơn m t giá tr ε cho trư c, thì d ng thu t toán. K t thúc d a trên s th h , m t s v n ñ d a vào s th h trong qu n th . Khi s lư ng ti n hoá c a qu n th ñ n m t gi i h n cho phép thì thu t toán s d ng, mà trong khi không quan tâm ñ n ch t lư ng c a cá th trong qu n th như th nào.
11 12 M t t p các phòng h c:P={P1, P2, …, Pm}. M i phòng h c có s ch ng i. CHƯƠNG 3 - NG D NG THU T GI I DI TRUY N VÀO BÀI TOÁN X P TH I KHÓA BI U M t t p các gi ng viên: G={G1, G2, …, Gk}. 3.1. Bài toán th i khóa bi u theo h c ch tín ch M t t p các ti t h c trong tu n: T={T1, T2, …, Th} Bài toán th i khoá bi u có vai trò r t quan tr ng trong b t c T p phân công giáo viên d y: E={ (SVi, Mi, Gi )| m t nhà trư ng nào, th i khóa bi u h c t p c a sinh viên và l ch SVi ∈ SV, Mi∈ M, Gi ∈ G } gi ng d y c a giáo viên luôn là b xương s ng cơ b n nh t, k t n i 3.1.2. Các ràng bu c c a bài toán h u như toàn b các ho t ñ ng c a nhà trư ng. Chính vì l ñó bài X p l ch h c cho các l p vào các phòng h c t i các th i ñi m toán x p Th i khóa bi u tr thành m t trong nh ng v n ñ chính và sao cho th a mãn các ñi u ki n sau: quan tr ng vào b c nh t c a m i trư ng. • (C1): Không có hai l p h c cùng m t phòng t i m t th i Đ i v i các bài toán không gian l i gi i nh thì có th s ñi m. d ng phương pháp c ñi n như vét c n là ñ ñ tìm ñư c gi i pháp t i ưu. Nhưng v i bài toán có không gian l i gi i l n và k t h p • (C2): M t giáo viên không d y hai l p t i cùng m t th i nhi u ràng bu c thì ñòi h i ph i có nh ng phương pháp trí tu nhân ñi m. t o ñ c bi t, thu t gi i di truy n là m t trong nh ng phương pháp ñó. • (C3): X p các l p h c vào các phòng h c ñ m b o ñ ch 3.1.1. Đ nh nghĩa bài toán ng i cho sinh viên. M t t p các chương trình ñào t o: CT={CT1, CT2, …, • (C4): X p các ti t h c ñ m b o ñ s ti t cho m i môn CTl}. M i chương trình g m nh ng môn h c theo k h c. ho ch c a m t ngành h c, cho m t khóa h c. • (C5): Không x p các môn h c c a cùng m t chương trình M t t p các môn h c: M={M1, M2, …, Mt}. M i môn h c ñào t o vào cùng m t ti t h c. g m s tín ch , danh sách các chương trình h c môn h c Yêu c u c a bài toán tìm l i gi i c a bài toán sao cho tho ñó. mãn t t c các ràng bu c {C}. M t t p các nhóm sinh viên (L p h c ph n): SV={SV1, SV2, …, SVn}. M i l p h c ph n g m môn h c, gi ng viên d y, s sinh viên h c (d ki n ho c chính th c).
13 14 3.2. Phát bi u bài toán theo hư ng ti p c n thu t gi i di truy n Như v y th i khóa bi u X c a m t cơ s s có c u trúc ñư c trình bày hình 3.2: Vi c áp d ng thu t gi i di truy n vào bài toán có th ñư c bi u di n b ng hình 3.1: Hình 3.2. Bi u di n nhi m s c th (cá th ) c a bài toán Trong ñó: ei ={ (SVi, Mi, Gi )|SVi ∈ SV Mi ∈ M, Gi ∈ G}, (Nhóm sinh viên h c ph n SVi h c môn Mi do gi ng viên Gi d y) hay ñư c g i là t p phân công gi ng d y. D a vào s ti t c a môn h c Hình 3.1. Bi u di n m t vòng l p c a thu t gi i di truy n trên tu n chúng ta chia nh thành s các s ki n trong tu n, v i m i trong bài toán th i khoá bi u s ki n s ñư c gán m t s nguyên ñ thu n l i cho vi c bi u di n 3.3. Áp d ng thu t gi i di truy n vào bài toán th i khóa bi u sau này. 3.3.1. Bi u di n nhi m s c th M t ph n c a th i khoá bi u tư ng minh như sau: M t th i khóa bi u ñư c bi u di n là ma tr n Xmxh, trong ñó T1 T12 T19 T 30 T45 h, m là s các ti t h c trong tu n và s phòng h c trong m t cơ s . P 1 G 1, M 1 , L 1 G 3,M 2,L 2 G 3, M 2 , L 2 G 1,M 1,L 1 V i m i giá tr c a ma tr n là m t ñ i tư ng s ki n, m i s ki n P 2 G 3, M 2 , L 2 G 2,M 3,L 3 G 4, M 4 , L 4 G 3,M 4,L 4 P 3 G 2, M 3 , L 3 G 4,M 4,L 4 G 2 ,M 3 ,L 3 g m có gi ng viên, l p h c ph n và môn h c và ñây cũng là m t giá P 4 G 3 ,M 4 ,L 4 tr trong t p phân công gi ng d y ñã ñư c ñ nh nghĩa như trên. V i m i cách s p x p các gen vào nhi m s c th cho ta m t nhi m s c th 3.3.2. Kh i t o qu n th (cá th ) m i. Kh i t o qu n th là bư c ñ u trong thu t gi i di truy n, thu t toán có h i t nhanh hay ch m ñ n giá tr t i ưu cũng ph thu c
15 16 vào qu n th kh i t o ban ñ u. Khi kh i t o qu n th ph i kh i t o Output: TKB //Th i khoá bi u (cá th ) t p d li u d li u ban ñ u, bao g m t p các yêu c u bài toán, kh i Begin t o t p phân công gi ng d y. Thu t toán kh i t o qu n th For each Tj∈ {T} do Procedure Population() For each Pi∈ {P} do Input: N //S lư ng cá th yêu c u trong qu n th e ← {E} //l y ng u nhiên m t s ki n e Output: Po //Qu n th các cá th TKB[Tj][Pi]=e //Đ t vào th i khoá bi u Begin E ← {E} − e //Lo i b s ki n e ra kh i While (i ≤ N) do t p s ki n P=Individual() //t o m t cá th m i Endfor Po=Po ∪ P//ñ t cá th m i vào qu n th Endfor i=i++ Return TKB Endwhile End. End 3.3.3. Lai ghép Trong ñó, Individual() là hàm t o ra cá th m i, nó ñư c Ý tư ng c a phương pháp lai ghép, v i m i giá tr c a m t th c hi n trên ý tư ng, v i m i Tj trong t p T và v i m i Pi trong t p n , n u m t n có giá tr là 1 thì cá th con s nh n gen c a cha (m ), P. Ch n ng u nhiên m t s ki n e thu c t p s ki n (t p phân công ngư c l i là gen c a m (cha). Các bư c th c hi n như sau: gi ng d y) ñ t vào v trí tr ng (Tj,Pi) và lo i b s ki n e ra kh i t p s ki n. Th c hi n cho ñ n khi h t s s ki n trong t p phân công Bư c 1: Xét tu n t m i giá tr g[i,j] ∈ M (M là ma tr n nh ho c các v trí (Tj,Pi) ñã xét h t. phân làm m t n , i=1..h,j=1..m). V i m i giá tr g[i,j] ki m tra: Thu t toán sinh cá th cho qu n th N u: g[i,j]=1 Function Individual() • Tìm gen x thu c cá th cha chưa ñư c xét và Input: t p các phân công gi ng d y E={e1, e2, e3, … en}, không có trong cá th con. Đ t x vào cá th {T}, {P}//n: s s ki n con.
17 18 • Đánh d u ñã xét gen x trong cá th cha. - Giá tr th nh t, m[1,1]=0. Cá th con s nh n gen c a m , Ngư c l i: N u g[i,j]=0 - Giá tr th hai, m[1,2]=1. Cá th con s nh n gen c a cha • Tìm gen x thu c cá th m chưa ñư c xét và Tương t các giá tr k ti p, k t qu cá th con (NSTCon) sau khi lai không có trong cá th con. Đ t x vào cá th t o gi a cha NSTCha, m NSTMe, d a vào m t n M: con. NSTCha NSTMe NSTCon • Đánh d u ñã xét gen x trong cá th m . T1 T2 T3 T4 T1 T2 T3 T4 T1 T2 T3 T4 P1 12 13 1 9 P1 13 4 14 7 P1 13 12 Bư c 2. L p l i bư c 1, cho ñ n khi các ph n t c a m t n P2 4 2 5 16 P2 5 3 15 8 P2 M ñã ñư c xét. P3 5 10 11 14 P3 6 10 9 2 P3 P4 8 1 7 6 P4 12 11 16 1 P4 Bư c 3: K t thúc thu t toán và tr v k t qu . Ví d : Gi s có hai nhi m s c th cha, m NSTCha, NSTMe (các Hình 3.3. K t qu ví d sau khi th c hi n lai ghép s ki n ñư c gán b ng các s nguyên ñ thu n l i trong vi c bi u di n) và ma tr n m t n M: T1 T2 T3 T4 P1 13 12 1 4 NSTCha T1 T2 T3 T4 T 1NSTMeT 3 T 4 T2 M1 t n 2 (M) 3 4 P2 14 7 9 5 P 1 12 13 1 9 P 1 13 4 14 7 1 0 1 1 0 P3 2 3 15 8 P 4 2 5 16 P 2 5 3 15 8 2 0 0 1 0 P4 2 6 16 10 11 P 3 5 10 11 14 P 3 6 10 9 2 3 1 0 0 0 P 4 8 1 7 6 P 4 12 11 16 1 4 0 1 1 0 3.3.4. Đ t bi n Trong bài toán, nhi m s c th ñ i di n cho l i gi i c a bài Cách lai ghép d a vào giá tr c a m t n , n u giá tr ñang xét c a toán và m i gen trong nhi m s c th có m t xác su t ñ t bi n là p, ví m t n b ng 1 gen ñư c nh n là c a cha NSTCha, ngư c l i nh n c a d : p = 0.03 t c v i 100 cá th trong qu n th thì có 0.03*100 = 3 cá m NSTMe. T ví d trên ta có: th s b ñ t bi n trong m i th h , và quá trình ñ t bi n ñư c th c NSTCha NSTMe NSTCon hi n b ng phương pháp ñ t bi n tương h b ng cách hoán v 2 gen T1 T2 T3 T4 T1 T2 T3 T4 T1 T2 T3 T4 b t ký trong m t nhi m s c th . P1 12 13 1 9 P1 13 4 14 7 P1 13 P2 4 2 5 16 P2 5 3 15 8 P2 Các bư c th c hi n ñ t bi n: P3 5 10 11 14 P3 6 10 9 2 P3 P4 8 1 7 6 P4 12 11 16 1 P4 {G i N s cá th trong qu n th , p xác su t ñ t bi n}
19 20 Bư c 1: Tính s cá th s b ñ t bi n. Ràng bu c {C2}.V i ràng bu c chúng ta trình bày thu t gi i ki m tra s tho mãn ràng bu c như sau: S cá th ñ t bi n, K= N * p  Bư c 2: V i m i giá tr k, (k ∈ [1..K]) th c hi n: Bư c 1: V i m i ti t h c Ti ∈ {T } , (i=1..h) • Đánh d u t t c các giáo viên là chưa xét Xác ñ nh v trí cá th b ñ t bi n: sinh ng u nhiên s nguyên, x ∈ [1..N] ( x: v trí cá th • V i m i phòng h c Pj ∈ { P } , (j=1..m) trong qu n th ). o L y thông tin giáo viên t i phòng Pj (gv ∈ V i cá th x, xác ñ nh v trí gen ñ t bi n b ng TKB[i,j]) cách sinh ng u nhiên hai c p s nguyên vt1, o N u gv ñã ñư c xét thì tăng giá tr ph t vt2, vt3, vt4 (vt1, vt2 ∈ [1..m], vt3, vt4∈ [1..h], h:s ti t h c/tu n, m: s phòng h c) Ngư c l i, ñánh d u gv là ñã xét Hoán v hai c p gen c a cá th x t i hai v o L p l i cho ñ n khi xét h t các phòng. trí(vt1, vt2) và( vt3, vt4) Bư c 2: L p l i bư c 1, cho ñ n khi các ti t h c ñ u xét Bư c 3: L p l i bư c 2, cho ñ n khi h t s cá th b ñ t bi n. Bư c 3: Tr v k t qu , và k t thúc thu t toán. 3.3.5. Hàm ñánh giá Ràng bu c (C3), m i phòng h c có s c ch a và ñ c ñi m riêng Trong lu n văn, hàm thích nghi s ñư c th c hi n ñánh giá c a phòng, vì v y s p x p l p h c vào các phòng sao cho ñ m b o ch thông qua ràng bu c ph i tho mãn {C}. ng i cho sinh viên. Đ i v i yêu c u, thì m i th i khoá bi u ph i tho mãn v s c ch a, vì v y ph i ki m tra s tho mãn c a ràng bu c. M t th i khoá bi u ch p nh n ñư c thì ph i tho mãn t t c các ràng bu c, trong bài toán chúng ta ñ nh nghĩa t p các ràng bu c C Các bư c th c hi n ki m tra như sau: = {C1, C2, C3, C4, C5}. Tương ng, xây d ng thu t toán ñánh giá m c Bư c 1: V i m i giá tr TKB[i,j], {i=1..m, j=1..h} ñ tho mãn v i các ràng bu c: • Xác ñ nh nhóm sinh viên, lop ∈ TKB[i,j], trong ñó Đ i v i ràng bu c {C1}, tương ng v i m i giá tr c a ma TKB[i,j]={gv,nhómsv,mon} tr n ch có m t và ch m t s ki n. Như v y giá tr ñánh giá cho ràng • L y kh năng ch a c a phòng h c th i. bu c lo i này ñư c xác ñ nh b ng: C1(x) = 0. • So sánh sĩ s c a nhóm sinh viên và kh năng ch a phòng h c th i
21 22 N u sĩ s l p h c ph n (nhóm sinh viên) > s c ch a Các bư c th c hi n ki m tra vi ph m c a ràng bu c C5 ñư c th c c a phòng h c th i thì tăng giá tr ph t hi n qua các bư c sau: G i m ng CT[] có giá tr boolean, có kích thư c b ng s lư ng Bư c 2: L p bư c 1, cho ñ n khi t t c các giá tr ñ u ñư c xét chương trình, m i giá tr c a m ng ñ i di n cho m t chương trình, ví Bư c 3: Tr v k t qu , d ng thu t toán.. d CT[1] ñ i di n cho CT1, CT[2] ñ i di n CT2, (CT1,CT2 ∈ {CT} ) Ràng bu c (C4), các bư c th c hi n ki m tra s lư ng các ti t Bư c 1: V i m i ti t h c Ti ∈ {T } , (i=1..h) h c trong tu n c a môn ñư c th c hi n như sau: • Đánh d u t t c các chương trình là chưa xét (CT[k]=false, k=1..l) G i m ng s nguyên dem_tiet[] ch a s ti t h c ñã ñư c x p • V i m i phòng h c Pj ∈ { P } , (j=1..m) l ch tương ng v i t ng môn, m i giá tr c a m ng ñ i di n cho m t o L y thông tin môn h c (mon) t i phòng Pj môn h c, ví d dem_tiet[1] ñ i di n cho môn h c m1, dem_tiet[2] (mon ∈ TKB[i,j]) cho môn m2, … m1 ,m2 ∈ {M} o Xác ñ nh chương trình c a môn (mon), (g i Bư c 1: V i m i giá tr TKB[i,j], {i=1..m, j=1..h} chương trình th k) • Xác ñ nh môn h c, mk∈ TKB[i,j] o N u CT[k] ñã ñư c xét thì tăng giá tr ph t Ngư c l i, ñánh d u CT[k] là ñã • Đ m s lư ng ti t h c tương ng c a môn(mk), và xét(CT[k]=true) lưu trong m ng dem_tiet[mk]= dem_tiet[mk]+1. o L p l i cho ñ n khi xét h t các phòng. • L p l i bư c 1, cho ñ n khi các giá tr ñi u ñư c xét. Bư c 2: L p l i bư c 1, cho ñ n khi các ti t h c ñ u xét Bư c 2: V i m i môn mi ∈ {M} ,i=1..t. Bư c 3: Tr v k t qu , và d ng thu t toán. • So sánh, n u s ti t quy ñ nh h c c a môn mi Giai ño n quy t ñ nh thu t gi i, ñánh giá m t l ch h c c a >dem_tiet[mi] s ti t ñư c x p l ch thì tăng giá tr m t cơ s có tho mãn các yêu c u c a bài toán. C m i ràng bu c b ph t. vi ph m thì chúng ta cho giá tr ph t là 1 ñi m, như v y t ng h p giá tr thích nghi c a các ràng bu c ñư c trình bày như trên chúng ta khái • L p bư c 2, cho ñ n khi các môn ñi u ñư c xét. quát thành công th c như sau: Bư c 3: Tr v k t qu , d ng thu t toán. 5 F (x) = ∑ w i * Ci Ràng bu c (C5). Th i khoá bi u ñư c phân yêu c u các môn i =1 Trong ñó: wi: tr ng s ñánh giá m c ñ quan tr ng trong m t chương trình ñào t o ph i có th i gian h c khác nhau (C5). c a ràng bu c th i.(wi ∈ [0,1], ∑i =1 wi = 1 ). 5
23 24 Ci(x): tương ng v i giá tr ph t c a ràng bu c th i. x: th i khoá bi u c n ñánh giá. Như v y m c tiêu c a hàm ñánh giá c a F1(x) là ñ t ñư c giá tr nh nh t, yêu c u c a bài toán là ph i tho mãn ñư c t t c các ràng bu c t c là: F(x) = 0. M c tiêu c n ñ t ñư c là xây d ng hàm F(x) ñ t giá tr nh nh t. 3.4. Đánh giá và k t qu th c hi n Hình 3.7. K t qu sau 200 cá th Qua quá trình cài ñ t chương trình và mô ph ng thu t gi i trong ñi u ki n lý tư ng, như tho các s c ch a các phòng, s lư ng Hình 3.8 k t qu l n th c hi n th 2, t n t i cá th tho mãn các ràng phòng ñi u tho mãn, giáo viên không yêu c u thì chương trình ñ t bu c sau 100 cá th . m t s k t qu t t. B ng 3.1 là ví d tương ng v i ñ u vào d li u kích c ñ u vào nh c a bài toán. Và các tham s : S phòng h c: 10, ti t h c: 9 ti t/ngày, s lư ng cá th : 20, xác su t lai: 0.5, Xác su t ñ t bi n: 0.05, Tr ng s các ràng bu c: w1=0, w2=0.4, w3=0.1, w4=0.3, w5=0.2 B ng 3.1. D li u th i khoá bi u ñ u vào nh Hình 3.8. K t qu sau 100 cá th Hình 3.9 cho th y trong quá trình lai ghép, ñ t bi n v n x y ra các cá th con không t t hơn b m c a chúng. Nhưng v n có các cá th t t. Giá tr t t nh t 0.1 Hình 3.7 k t qu qua lư c ch y th nh t, sau khi th c hi n 200 cá th giá tr t t nh t ñ t ñư c là 0.05
25 26 K T LU N VÀ KI N NGH 1. K T LU N Tóm l i lu n văn ñã gi i quy t ñư c nh ng v n ñ sau: Lu n văn bư c ñ u ñ xu t phương pháp thu t gi i di truy n vào bài toán x p th i khoá bi u. Phát bi u bài toán theo hư ng ti p c n thu t gi i di truy n Tìm hi u và cài ñ t ñư c thu t toán, xây d ng ñư c hàm Hình 3.9. K t qu sau 150 cá th ñánh giá cho các yêu c u bu c ph i tho mãn. Xây d ng chương trình demo và k t qu th nghi m ñã Như v y, do h n ch c a thu t gi i là do thu t gi i di truy n ch ng minh hư ng ti p c n thu t gi i di truy n vào bài toán l p l ch s d ng các lu t chuy n ñ i gi a các cá th trong qu n th mang tính c th là bài toán th i khoá bi u là hư ng ti p c n ñúng ñ n và có xác su t cho nên không lúc nào cũng cho l i gi i chính xác. Tuy hi u qu . Đ c bi t chương trình v i d li u th ñã ñưa ra ñư c m t nhiên bài toán v n d ng thu t gi i di truy n có th cung c p nhi u l i th i khoá bi u c th . gi i ti m năng ñ ngư i s d ng l a ch n. 2. HƯ NG PHÁT TRI N Đ TÀI Hi n nay chúng tôi ñang phát tri n chương trình ng d ng hoàn ch nh d a vào k t qu nghiên c u này. Do th i gian h n ch nên chương trình chưa ñư c hoàn thi n Sau khi phát tri n thành công chương trình ng d ng, hư ng nghiên c u ti p theo c a chúng tôi là tìm hi u ng d ng thu t gi i di truy n cho nhi u d ng bài toán l p l ch. So sánh v i các phương pháp khác ñã có và m r ng nhi u ràng bu c cho các bài toán l p l ch khác.