Tóm tắt Luận văn Ứng dụng mạng nơ ron Hopfield giải bài toán thời khóa biểu
Bạn đang xem 20 trang mẫu của tài liệu "Tóm tắt Luận văn Ứng dụng mạng nơ ron Hopfield giải bài toán thời khóa biểu", để 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:
- tom_tat_luan_van_ung_dung_mang_no_ron_hopfield_giai_bai_toan.pdf
Nội dung text: Tóm tắt Luận văn Ứng dụng mạng nơ ron Hopfield giải bài toán thời khóa biểu
- ðI H C THÁI NGUYÊN TR ƯNG ð I H C CNTT&TT HÀ TU N VI T NG D NG M NG N Ơ RON HOPFIELD GI I BÀI TỐN L P TH I KHĨA BI U Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 TĨM T T LU N V ĂN TH C S Ĩ KHOA H C MÁY TÍNH THÁI NGUYÊN - 2011 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- Cơng trình đưc hồn thành t i: Tr ưng ð i h c CNTT & TT- ði H c Thái Nguyên Ng ưi h ưng d n khoa h c: PGS TS. ðNG QUANG Á Ph n bi n 1: Ph n bi n 2: Lu n v ăn s đưc b o v tr ưc H i đng ch m lun v ăn h p t i: Vào h i gi ngày tháng n ăm 2011. Cĩ th tìm hi u lu n v ăn t i trung tâm h c li u ði h c Thái Nguyên Và th ư vi n Tr ưng/Khoa: . Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- i LỜI C ẢM ƠN Xin chân thành c ảm ơn Th ầy PGS TS . Đặng Quang Á đã t ận tình ch ỉ dạy, h ướng d ẫn tơi trong su ốt th ời gian h ọc t ập và làm lu ận v ăn. Tơi c ũng xin bi ết ơn chân thành đến các Th ầy giáo Vi ện Cơng ngh ệ Thơng tin đã gi ảng d ạy, giúp đỡ trong su ốt th ời gian h ọc t ập. Xin c ảm ơn t ất c ả các anh ch ị h ọc viên Cao h ọc khĩa 8, cám ơn các cán bộ cơng ch ức, gi ảng viên Khoa Cơng ngh ệ thơng tin- ĐH Thái Nguyên đã t ạo điều ki ện tốt cho tơi trong su ốt trong hai n ăm h ọc qua. Xin cám ơn các b ạn bè, đồng nghi ệp đã ch ỉ b ảo tơi r ất nhi ều trong th ời gian th ực hi ện lu ận v ăn này. Cu ối cùng, xin chân thành cảm ơn các thành viên trong gia đình đã động viên và tạo m ọi điều ki ện thu ận l ợi để tơi cĩ được k ết qu ả nh ư ngày hơm nay. THÁI NGUYÊN 10/2011 Ng ười vi ết lu ận v ăn Hà Tu ấn Vi ệt Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- ii LỜI CAM ĐOAN Tơi xin cam đoan đề tài lu ận v ăn “ Ứng d ụng m ạng n ơ-ron Hopfield gi ải bài tốn th ời khĩa bi ểu” là cơng trình nghiên c ứu c ủa b ản thân tơi. Các số li ệu, kết qu ả nghiên c ứu nêu trong lu ận v ăn này là trung th ực và ch ưa t ừng được ai cơng b ố trong m ột cơng trình nào khác. Tơi xin ch ịu trách nhi ệm v ề lu ận v ăn c ủa mình. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- iii MỤC L ỤC TRANG PH Ụ BÌA Trang LỜI C ẢM ƠN i LỜI CAM ĐOAN ii MỤC L ỤC iii DANH M ỤC CÁC BI ỂU ĐỒ , HÌNH V Ẽ v MỞ ĐẦ U 1 CH ƯƠ NG I 3 TỔNG QUAN V Ề M ẠNG N Ơ RON NHÂN T ẠO 3 1.1. GI ỚI THI ỆU V Ề M ẠNG N Ơ-RON NHÂN T ẠO 3 1.1.1 L ịch s ử phát tri ển 3 1.1.2. Mơ hình m ạng n ơ-ron nhân t ạo 4 1.2. PH ẠM VI ỨNG D ỤNG C ỦA M ẠNG N Ơ RON NHÂN T ẠO 19 1.2.1. Nh ững bài tốn thích h ợp 19 1.2.2. Các l ĩnh v ực ứng d ụng m ạng n ơ ron 23 1.3. M ẠNG HOPFIELD 24 1.3.1. M ạng Hopfield r ời r ạc 25 1.3.2. M ạng Hopfield liên t ục. 27 1.3.3. M ạng Hopfield v ới bài tốn t ối ưu 28 1.3.4. M ạng Hopfield v ới bài tốn l ập th ời khĩa bi ểu 30 1.4. NH ẬN XÉT 32 CH ƯƠ NG II 33 ỨNG D ỤNG M ẠNG N Ơ-RON HOPFIELD TRONG BÀI TỐN L ẬP TH ỜI KHĨA BI ỂU CHO TR ƯỜNG ĐẠ I H ỌC 33 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- iv 2.1 Bài tốn l ập th ời khĩa bi ểu và nh ững khĩ kh ăn trong vi ệc l ập th ời khĩa bi ểu cho tr ường đạ i h ọc 33 2.2. Tình hình gi ải quy ết bài tốn l ập th ời khĩa bi ểu 37 2.3. Xây d ựng mơ hình m ạng Hopfield cho bài tốn th ời khĩa bi ểu 38 2.3.1. M ạng n ơ ron Hopfield 38 2.3.2. Ánh x ạ bài tốn th ời khĩa bi ểu lên m ạng n ơ-ron Hopfield 40 2.4. Thu ật tốn m ạng n ơ-ron Hopfield trong bài tốn l ập th ời khĩa bi ểu cho tr ường Đạ i h ọc 43 2.5. K ết lu ận ch ươ ng 2 46 CH ƯƠ NG 3: CÀI ĐẶT TH Ử NGHI ỆM 47 3.1 Thi ết k ế ch ươ ng trình ứng d ụng m ạng n ơ ron Hopfield trong vi ệc l ập th ời khĩa bi ểu cho tr ường đạ i h ọc. 47 3.2 Chu ẩn b ị d ữ li ệu 50 3.3. K ết qu ả th ử nghi ệm 50 3.4. Đánh giá k ết qu ả 51 KẾT LU ẬN VÀ ĐỀ NGH Ị 52 Kết qu ả đạ t được c ủa lu ận v ăn 52 Các định h ướng nghiên c ứu ti ếp theo 52 TÀI LI ỆU THAM KH ẢO 53 PH Ụ L ỤC 55 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- v DANH M ỤC CÁC BI ỂU ĐỒ , HÌNH V Ẽ Hình 1.1. Mơ hình n ơ-ron sinh h ọc 6 Đồ th ị hàm đồng nh ất (Identity function) 8 Đồ th ị hàm b ước nh ị phân (Binary step function) 8 Đồ th ị hàm sigmoid 9 Đồ th ị hàm sigmoid l ưỡng c ực 10 Hình 1.2. Mơ hình m ột n ơ-ron 11 Hình 1.3. M ạng truy ền th ẳng m ột l ớp 13 Hình 1.4. M ạng truy ền th ẳng nhi ều l ớp 14 Hình 1.5. M ạng m ột l ớp cĩ n ối ng ược 15 Hình 1.6. M ạng nhi ều l ớp cĩ n ối 15 Hình 1.7. Mơ hình m ạng Hopfield 25 Đồ th ị hàm Sigmoid 28 Đồ th ị hàm Hàm y=tanh(x) 28 Hình 3.1: Giao di ện ch ươ ng trình th ời khĩa bi ểu 48 Hình 3.2: Danh sách các form d ữ li ệu 49 Hình 3.3: Minh h ọa tìm ki ếm d ữ li ệu theo l ớp 49 Hình 3.4: Nh ập tham s ố cơng th ức cho bài tốn th ời khĩa bi ểu 50 Hình 3.5: Minh h ọa k ết qu ả sau khi x ếp th ời khĩa bi ểu 50 Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 1 MỞ ĐẦU Nh ờ các kh ả n ăng: h ọc, nh ớ l ại và khái quát hĩa t ừ các m ẫu hu ấn luy ện ho ặc d ữ li ệu, m ạng n ơ-ron nhân t ạo tr ở thành m ột phát minh đầ y h ứa h ẹn c ủa hệ th ống x ử lý thơng tin. Các tính tốn n ơ-ron cho phép gi ải quy ết t ốt nh ững bài tốn đặc tr ưng b ởi m ột s ố ho ặc t ất c ả các tính ch ất sau: s ử d ụng khơng gian nhi ều chi ều, các t ươ ng tác ph ức t ạp, ch ưa bi ết ho ặc khơng th ể bi ết v ề m ặt tốn h ọc gi ữa các bi ến. Ngồi ra ph ươ ng pháp này cịn cho phép tìm ra nghi ệm c ủa nh ưng bài tốn địi h ỏi đầ u vào là các c ảm nh ận c ủa con ng ười nh ư: ti ếng nĩi, nhìn và nh ận d ạng Bài tốn l ập th ời khĩa bi ểu đạ i h ọc là m ột bài tốn t ối ưu d ạng NP-hard và tìm được m ột th ời khĩa bi ểu cĩ ch ất l ượng t ốt là m ột th ử thách th ực s ự. Bài tốn v ới m ột s ố l ượng l ớn các s ự ki ện và bao g ồm nhi ều ràng bu ộc c ứng khác nhau để th ực hi ện vi ệc tìm ki ếm th ời khĩa bi ểu t ối ưu là ph ức t ạp và t ốn nhi ều th ời gian. Để x ử lý độ ph ức t ạp c ủa bài tốn và để cung c ấp vi ệc t ự động h ỗ tr ợ con ng ười trong x ếp th ời khĩa bi ểu, đã cĩ nhi ều cách ti ếp c ận trong các tài li ệu t ập trung vào bài tốn này. Nh ững cơng việc nghiên c ứu th ể hi ện trong lu ận v ăn nh ằm xây d ựng theo tình tr ạng phát bi ểu tìm ki ếm ph ươ ng pháp lu ận cho bài tốn th ời khĩa bi ểu. Nghiên c ứu t ập trung vào ph ần x ếp l ịch dạy c ủa th ời khĩa bi ểu nh ằm đả m b ảo l ớp - giáo viên - phịng h ọc tránh b ị xung đột. Các tính tốn n ơ-ron cho phép gi ải quy ết t ốt các bài tốn cĩ nhi ều tươ ng tác ph ức t ạp. Vì v ậy, ứng d ụng m ạng n ơ-ron Hopfield trong bài tốn th ời khĩa bi ểu s ẽ h ứa h ẹn là m ột gi ải pháp hi ệu qu ả gĩp ph ần nâng cao kh ả năng x ếp th ời khĩa bi ểu nh ờ tính h ội t ụ nhanh đến m ột tr ạng thái ổn đị nh c ủa mạng n ơ-ron Hopfield. Trên th ế gi ới, đã cĩ m ột s ố nghiên c ứu ứng d ụng m ạng n ơ-ron trong bài tốn x ếp l ịch th ời khĩa bi ểu cho tr ường đạ i h ọc. Tuy nhiên, l ĩnh v ực này cịn khá m ới m ẻ và ch ưa được ứng d ụng r ộng rãi ở n ước ta. Trong n ước c ũng Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 2 ch ưa cĩ m ột tài li ệu chính th ống nào v ề l ĩnh v ực này. V ới nh ững ứng d ụng ngày càng r ộng rãi c ủa m ạng n ơ-ron, vi ệc nghiên c ứu và áp d ụng vào bài tốn th ời khĩa bi ểu tr ở nên c ấp thi ết, và đang r ất được quan tâm. Chính vì nh ững lý do trên em đã quy ết đị nh ch ọn đề tài: “Ứng d ụng m ạng n ơ-ron Hopfield trong vi ệc l ập th ời khĩa bi ểu cho tr ường đạ i h ọc“ làm h ướng nghiên c ứu. Với m ục tiêu đư a nh ững ý t ưởng khác nhau nh ằm t ăng hi ệu qu ả t ổng quan v ới thu ật tốn x ếp th ời khĩa bi ểu và tìm cách ứng d ụng vào th ực t ế. Lu ận v ăn g ồm 3 ch ươ ng v ới các n ội dung c ơ b ản sau: Ch ươ ng 1 : Trình bày t ổng quan v ề c ơ s ở m ạng n ơ-ron nhân t ạo, và nêu khái quát ứng d ụng m ạng n ơ-ron trong bài tốn x ếp th ời khĩa bi ểu. Ch ươ ng 2 : Trình bày ph ươ ng pháp gi ải bài tốn l ập th ời khĩa bi ểu, dùng m ạng Hopfield s ửa đổ i nh ằm gi ảm độ ph ức t ạp và t ăng t ốc gi ải bài tốn, đư a ra nh ững nh ận xét v ề hi ệu qu ả c ủa các mơ hình bài tốn. Ch ươ ng 3 : Thi ết k ế cài đặt th ử nghi ệm ch ươ ng trình ứng d ụng m ạng nơ-ron Hopfield cho bài tốn l ập th ời khĩa bi ểu, đánh giá v ề k ết qu ả đạt được. Ngồi ra, lu ận v ăn cịn ph ần ph ụ l ục và tài li ệu tham kh ảo kèm theo ở cu ối đề tài. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 3 CH ƯƠ NG I TỔNG QUAN V Ề MẠNG N Ơ RON NHÂN T ẠO 1.1. GI ỚI THI ỆU V Ề M ẠNG N Ơ-RON NHÂN T ẠO 1.1.1 L ịch s ử phát tri ển Khái ni ệm m ạng nơ-ron được b ắt đầ u vào cu ối th ế k ỷ 19, đầu th ế k ỷ 20 do cĩ s ự tham gia c ủa ba ngành V ật lý h ọc, Tâm lý h ọc và Th ần kinh h ọc. Các nhà khoa h ọc nh ư Hermann Von Hemholtz, Earnst Mach, Ivan Pavlov với các cơng trình nghiên c ứu đi sâu vào lý thuy ết t ổng quát mơ t ả ho ạt độ ng c ủa trí tu ệ con ng ười nh ư: H ọc, nhìn, và l ập lu ận, nh ưng khơng đư a ra được mơ hình tốn h ọc c ụ th ể mơ t ả ho ạt độ ng c ủa n ơ-ron. Về l ịch s ử, quá trình nghiên c ứu và phát tri ển m ạng n ơ-ron nhân t ạo cĩ th ể chia thành b ốn giai đoạn nh ư sau: + Giai đoạn m ột: Từ nghiên c ứu c ủa William (1890) v ề tâm lý h ọc v ới sự liên k ết các n ơ-ron th ần kinh. N ăm 1943, nhà th ần kinh h ọc Warren MeCulloch và nhà logic h ọc Walter Pitts đã ch ỉ ra r ằng:về nguyên t ắc mạng các nơ-ron nhân t ạo cĩ th ể được mơ hình hố như thi ết b ị ng ưỡng (gi ới h ạn) để th ực hi ện tính tốn b ất k ỳ m ột hàm s ố h ọc hay các phép tính logic nào. Ti ếp theo hai ơng là Donald Hebb với gi ải thu ật hu ấn luy ện m ạng ra đờ i n ăm 1949. + Giai đoạn hai: Vào kho ảng nh ững n ăm 1960, m ột s ố mơ hình n ơ-ron hồn thi ện h ơn cĩ tính ứng d ụng th ực ti ễn đã được đưa ra nh ư: mơ hình Perceptron c ủa Frank Rosenblatt (1958), mơ hình Adaline c ủa Bernard Widrow (1962). Trong đĩ mơ hình Perceptron r ất được quan tâm vì nguyên lý đơ n gi ản, nh ưng nĩ c ũng cĩ h ạn ch ế vì nh ư Marvin Minsky và Seymour Papert c ủa MIT (Massachurehs Insritute of Technology) đã phát hi ện ra và Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 4 ch ứng minh nĩ khơng dùng được cho các hàm logic ph ức (1969). Cịn Adaline là mơ hình tuy ến tính, t ự ch ỉnh, được dùng r ộng rãi trong điều khi ển thích nghi, tách nhi ễu và v ẫn phát tri ển cho đế n nay. + Giai đoạn ba: Vào kho ảng đầ u th ập niên 80, vi ệc nghiên c ứu m ạng nơ-ron di ễn ra r ất m ạnh m ẽ cùng v ới s ự ra đờ i c ủa máy tính cá nhân PC. Nh ững đĩng gĩp l ớn cho m ạng n ơ-ron trong giai đoạn này ph ải k ể đế n Stephen Grossberg, Teuvo Kohonen, Rumelhart và John Hopfield. Trong đĩ đĩng gĩp l ớn c ủa nhà v ật lý h ọc ng ười M ỹ John Hopfield g ồm hai m ạng ph ản hồi: M ạng r ời r ạc n ăm 1982 và m ạng liên t ục n ăm 1984. Đặ c bi ệt, ơng đã d ự ki ến nhi ều kh ả n ăng tính tốn l ớn c ủa m ạng mà m ột n ơ-ron khơng cĩ kh ả năng đĩ. C ảm nh ận c ủa Hopfield đã được Rumelhart, Hinton và Williams đề xu ất thu ật tốn sai s ố truy ền ng ược (back –propagation) n ổi ti ếng để hu ấn luy ện m ạng n ơ-ron nhi ều l ớp nh ằm gi ải bài tốn mà m ạng khác khơng th ực hi ện được. Nhi ều ứng d ụng m ạnh m ẽ c ủa m ạng n ơ-ron ra đời cùng v ới các mạng theo ki ểu máy Boltzmann và m ạng Neocognition c ủa Fukushima. + Giai đoạn b ốn: t ừ n ăm 1987 - đến nay, hàng n ăm th ế gi ới đề u m ở h ội ngh ị tồn c ầu chuyên ngành n ơ-ron IJCNN (International Joint Conference on Neural Networks). R ất nhi ều cơng trình được nghiên c ứu để ứng d ụng m ạng nơ-ron vào các l ĩnh v ực cu ộc s ống, ví d ụ nh ư: K ỹ thu ật tính, t ối ưu, sinh h ọc, y học, th ống kê, giao thơng, hố h ọc Cho đế n nay, m ạng n ơ-ron đã tìm được và kh ẳng đị nh được v ị trí c ủa mình trong r ất nhi ều ứng d ụng khác nhau. 1.1.2. Mơ hình m ạng n ơ-ron nhân t ạo 1.1.2.1. N ơ-ron sinh h ọc Bộ não con ng ười cĩ kho ảng 10 10 t ế bào th ần kinh liên k ết ch ặt ch ẽ v ới nhau được g ọi là các n ơ-ron. M ỗi n ơ-ron g ồm cĩ ba ph ần: Thân n ơ-ron v ới nhân ở bên trong (soma), m ột đầ u s ợi tr ục th ần kinh ra (axon) và m ột h ệ th ống t ế bào hình cây (dendrite). Tế bào hình cây cĩ nhi ệm v ụ mang các tín hi ệu điện t ới các Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 5 tế bào thân, t ế bào thân s ẽ th ực hi ện g ộp (Sum) và phân ng ưỡng ( Thresholds) các tín hi ệu đế n. S ợi tr ục thần kinh làm nhi ệm v ụ đưa các tín hi ệu thân ra ngồi Trong th ực t ế cĩ r ất nhi ều dây th ần kinh vào và chúng bao ph ủ m ột di ện tích r ất l ớn (0.25 mm 2) để nh ận các tín hi ệu t ừ các n ơ-ron khác. Đầu th ần kinh ra được r ẽ nhánh nh ằm chuy ển giao tín hi ệu t ừ thân n ơ-ron t ới n ơ-ron khác. Các nhánh c ủa đầ u th ần kinh được n ối v ới các kh ớp th ần kinh (synapse). Các kh ớp th ần kinh này được n ối v ới th ần kinh vào c ủa các n ơ-ron khác. S ự s ắp x ếp c ủa các n ơ-ron và m ức độ m ạnh y ếu c ủa các kh ớp th ần kinh được quy ết đị nh b ởi quá trình hĩa h ọc ph ức t ạp, s ẽ thi ết l ập ch ức n ăng c ủa m ạng n ơ-ron, các n ơ-ron cĩ th ể s ửa đổ i tín hi ệu t ại các kh ớp, trong các n ơ-ron nhân t ạo được g ọi là tr ọng s ố. Cĩ th ể nĩi, m ạng n ơ-ron sinh h ọc ho ạt độ ng ch ậm h ơn r ất nhi ều so v ới các linh ki ện điện t ử (10 -3 giây so v ới 10 -9 giây), nh ưng b ộ não cĩ th ể th ực hi ện nhi ều cơng vi ệc nhanh h ơn r ất nhi ều so v ới máy tính thơng th ường. Do c ấu trúc song song c ủa m ạng n ơ-ron sinh h ọc th ể hi ện tồn b ộ các n ơ-ron th ực hi ện đồ ng th ời t ại m ột th ời điểm. M ạng n ơ-ron nhân tạo c ũng cĩ được đặ c điểm này. Các mạng n ơ-ron nhân t ạo ch ủ y ếu th ực nghi ệm trên các máy tính m ạnh cĩ vi m ạch tích h ợp r ất l ớn, các thi ết b ị quang, b ộ x ử lý song song. Điều này c ũng gi ải thích tại sao nh ững nghiên c ứu khoa h ọc v ề m ạng n ơ-ron nhân t ạo cĩ điều ki ện phát tri ển cùng v ới s ự phát tri ển v ề k ỹ thu ật cơng ngh ệ ph ần c ứng máy tính. Cĩ nhi ều lo ại n ơ-ron khác nhau v ề kích th ước và kh ả n ăng thu phát tín hi ệu. Tuy nhiên, chúng cĩ c ấu trúc và nguyên lý ho ạt độ ng chung. Hình v ẽ (1.1) là m ột hình ảnh đơn gi ản hố c ủa m ột lo ại n ơ-ron nh ư v ậy. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 6 Hình 1.1. Mơ hình n ơ-ron sinh h ọc - Ho ạt độ ng c ủa n ơ-ron sinh h ọc cĩ th ể mơ t ả tĩm t ắt nh ư sau: Mỗi n ơ-ron nh ận tín hi ệu vào t ừ các t ế bào th ần kinh khác. Chúng tích hợp các tín hi ệu vào, khi t ổng tín hi ệu v ượt quá m ột ng ưỡng nào đĩ chúng t ạo tín hi ệu ra và g ửi tín hi ệu này t ới các n ơ-ron khác thơng qua dây th ần kinh. Các n ơ-ron liên k ết v ới nhau thành m ạng. M ức độ b ền v ững c ủa các liên k ết này xác định m ột h ệ s ố g ọi là tr ọng s ố liên k ết. 1.1.2.2. N ơ-ron nhân t ạo Để mơ ph ỏng các t ế bào th ần kinh và các kh ớp n ối th ần kinh c ủa b ộ não con ng ười, m ạng n ơ-ron nhân t ạo cĩ các thành ph ần cĩ vai trị t ươ ng t ự là các n ơ-ron nhân t ạo và k ết n ối gi ữa chúng (kết n ối này g ọi là weights). Nơ- ron là m ột đơn v ị tính tốn cĩ nhi ều đầ u vào và m ột đầ u ra, m ỗi đầ u vào đến từ m ột kh ớp n ối th ần kinh (synapse). Đặc tr ưng c ủa n ơ-ron là m ột hàm kích ho ạt phi tuy ến chuy ển đổ i m ột t ổ h ợp tuy ến tính c ủa t ất c ả các tín hi ệu đầ u vào thành tín hi ệu đầ u ra. Một n ơ-ron nhân t ạo là m ột đơn v ị tính tốn hay đơ n v ị x ử lý thơng tin cơ s ở cho ho ạt độ ng c ủa m ột m ạng n ơ-ron. Các thành ph ần c ơ b ản c ủa m ột mơ hình n ơ-ron Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 7 • Tr ọng s ố và t ổng tín hi ệu đầ u vào: Mỗi n ơ-ron cĩ r ất nhi ều dây th ần kinh vào, ngh ĩa là m ỗi n ơ-ron cĩ th ể ti ếp nh ận đồ ng th ời nhi ều tín hi ệu. Gi ả s ử t ại n ơ-ron i cĩ N tín hi ệu vào, m ỗi tín hi ệu vào S j được gán m ột tr ọng s ố Wij t ươ ng ứng. Ta ước l ượng t ổng tín hi ệu đi vào n ơ-ron net i theo m ột s ố d ạng sau: (i)Dạng tuy ến tính: N = neti∑ W ijj s (1.1) j=1 (ii)Dạng tồn ph ươ ng: N = 2 neti∑ W ijj s (2.2) j=1 (iii)Dạng m ặt c ầu: N 2 = −ρ 2 − neti∑() s j wij (3.3) j=1 ρ = Trong đĩ: và wij ( j 1, N ) l ần l ượt là tâm và bán kính m ặt c ầu • Hàm kích ho ạt (hàm chuy ển): Hầu h ết các đơn v ị trong m ạng n ơ-ron chuy ển net input b ằng cách s ử d ụng một hàm vơ h ướng (scalar – to – scalar function) g ọi là hàm kích ho ạt, k ết qu ả của hàm này là m ột giá tr ị g ọi là m ức độ kích ho ạt c ủa đơn v ị. Tr ừ kh ả n ăng đơ n v ị đĩ thu ộc l ớp ra, giá tr ị kích ho ạt được đưa vào m ột hay nhi ều đơn v ị khác. Các hàm kích ho ạt th ường b ị ép vào m ột kho ảng giá tr ị xác đị nh, do đĩ th ường được g ọi là các hàm nén (squashing). Hàm bi ến đổ i tín hi ệu đầ u vào net cho tín hi ệu đầ u ra out được g ọi là hàm kích ho ạt. Hàm này cĩ đặc điểm là khơng âm và b ị ch ặn, dùng để gi ới h ạn biên Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 8 độ đầ u ra c ủa n ơ-ron. Cĩ nhi ều d ạng hàm kích ho ạt, ng ười ta th ường s ử d ụng một hàm kích ho ạt chung cho tồn m ạng. Một s ố hàm kích ho ạt th ường được s ử d ụng 1) Hàm đồng nh ất (Linear function, Identity function) g(x) = x (1.3) Nếu coi các đầ u vào là m ột đơn v ị thì chúng s ẽ s ử d ụng hàm này. Cĩ khi m ột hằng s ố được nhân v ới net-input t ạo thành m ột hàm đồng nh ất. Đồ th ị hàm đồng nh ất (Identity function) 2) Hàm b ước nh ị phân (Binary step function, Hard limit function) Hàm này cịn g ọi là hàm ng ưỡng (Threshold function hay Heaviside function). Đầu ra c ủa hàm này gi ới h ạn m ột trong hai giá tr ị: 1, nếu x ≥ θ g( x ) = (1.4) 0, nếu x < θ ở đây θ là ng ưỡng. Đồ th ị hàm b ước nh ị phân (Binary step function) Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 9 Dạng hàm này th ường s ử d ụng trong m ạng m ột l ớp. Trong hình v ẽ θ được ch ọn b ằng 1. 3) Hàm sigmoid (Sigmoid function (logsig)) Hàm sigma là d ạng chung nh ất c ủa hàm kích ho ạt được s ử d ụng trong cấu trúc m ạng n ơ-ron nhân t ạo. Nĩ là m ột hàm t ăng và nĩ th ể hi ện m ột s ự trung gian gi ữa tuy ến tính và phi tuy ến. M ột ví d ụ c ủa hàm này là hàm logistics , xác định nh ư sau: = 1 g( x ) −λ (1.5) 1+ e x ở đĩ λ là tham s ố độ d ốc c ủa hàm sigma. B ằng vi ệc bi ến đổ i tham s ố λ , chúng ta thu được các hàm sigma v ới các độ d ốc khác nhau. Th ực t ế, h ệ s ố gĩc t ại x= 0 là λ /4. Khi tham s ố h ệ s ố gĩc ti ến t ới khơng xác đị nh, hàm sigma tr ở thành m ột hàm ng ưỡng đơn gi ản. Trong khi m ột hàm ng ưỡng ch ỉ cĩ giá tr ị là 0 ho ặc 1, thì m ột hàm sigma nh ận các giá tr ị t ừ 0 t ới 1. C ũng ph ải ghi nh ận r ằng hàm sigma là hàm phân bi ệt, trong khi hàm ng ưỡng thì khơng (Tính phân bi ệt c ủa hàm là m ột đặ c tính quan tr ọng trong lý thuy ết m ạng neuron). Hàm này th ường được dùng cho các m ạng được hu ấn luy ện (trained) bởi thu ật tốn lan truy ền ng ược (back –propagation), b ởi nĩ d ễ l ấy đạ o hàm, làm gi ảm đáng k ể tính tốn trong quá trình hu ấn luy ện. Hàm được dùng cho các ch ươ ng trình ứng d ụng mà đầu ra mong mu ốn r ơi vào kho ảng [0,1]. Đồ th ị hàm sigmoid Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 10 4) Hàm sigmoid l ưỡng c ực (Bipolar sigmoid function (tan(sig)) 1− e−x g( x ) = (1.6) 1+ e− x Hàm này cĩ đặc tính t ươ ng t ự hàm sigmoid. Hàm làm vi ệc t ốt đố i v ới các ứng dụng cĩ đầ u ra yêu c ầu trong kho ảng [-1,1]. Đồ th ị hàm sigmoid l ưỡng c ực Các hàm chuy ển c ủa các đơn v ị ẩn (hidden units) là c ần thi ết để bi ểu di ễn s ự phi tuy ến vào trong m ạng. • Nút bias: Là m ột nút thêm vào nh ằm t ăng kh ả n ăng thích nghi c ủa m ạng n ơ-ron trong quá trình h ọc. Trong các m ạng n ơ-ron cĩ s ử d ụng bias, mỗi n ơ-ron cĩ th ể cĩ m ột tr ọng s ố t ươ ng ứng v ới bias. Tr ọng s ố này luơn cĩ giá tr ị là 1. Mơ hình c ủa m ột nút x ử lý (nút th ứ i): V i Wi1 Vj Wij ∑ Vi Ui= Vi=f i(U i) WiN VN Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 11 Hình 1.2. Mơ hình m ột n ơ-ron N = + Ui ∑Wij Vj θ i (1.7) j=1 j #i = ( ) Vi fi U i (1.8) Trong đĩ: Ui : là tín hi ệu vào t ại n ơ-ron i Vi : là tín hi ệu ra t ại n ơ ron i Wij : là tr ọng s ố li ền k ề t ừ n ơ-ron j đến n ơ-ron i θ i : là ng ưỡng (đầu vào ngồi) kích ho ạt n ơ-ron i. fi : là hàm kích ho ạt c ủa n ơ-ron i 1.1.2.3. M ạng n ơ-ron nhân t ạo Mạng n ơ-ron nhân t ạo (gọi t ắt là m ạng n ơ-ron) là mơ hình tốn h ọc hay mơ hình tính tốn được xây d ựng d ựa trên các m ạng n ơ-ron sinh h ọc. Nĩ g ồm cĩ m ột nhĩm các n ơ-ron nhân t ạo(nút) n ối v ới nhau, và x ử lý thơng tin b ằng cách truy ền theo các k ết n ối và tính giá tr ị m ới t ại các nút (cách ti ếp c ận connectionism đối v ới tính tốn). Ph ần l ớn m ạng n ơ-ron nhân t ạo là một h ệ th ống thích ứng (adaptive system ) t ự thay đổ i c ấu trúc c ủa mình d ựa trên các thơng tin bên ngồi hay bên trong ch ảy qua m ạng trong quá trình h ọc. Với vi ệc gi ả l ập các h ệ th ống sinh h ọc, các c ấu trúc tính tốn, m ạng n ơ- ron cĩ th ể gi ải quy ết được các l ớp bài tốn nh ất đị nh, nh ư: Bài tốn ng ười du lịch, bài tốn tơ màu b ản đồ , bài tốn x ếp lo ại, bài tốn l ập th ời khĩa bi ểu, bài tốn tìm ki ếm, bài tốn nh ận d ạng m ẫu Các bài tốn ph ức t ạp cao, khơng Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 12 xác định. Tuy nhiên, s ự liên k ết gi ữa m ột bài tốn b ất k ỳ trong th ực t ế v ới m ột gi ải pháp m ạng n ơ-ron l ại là m ột vi ệc khơng d ễ dàng. Xét m ột cách t ổng quát, m ạng n ơ-ron là m ột c ấu trúc x ử lý song song thơng tin phân tán mang các đặc tính n ổi b ật sau : Là mơ hình tốn h ọc d ựa trên b ản ch ất c ủa n ơ-ron. Bao g ồm m ột s ố l ượng r ất l ớn các n ơ-ron liên k ết v ới nhau. Mạng n ơ-ron cĩ kh ả n ăng h ọc, khái quát hĩa t ập d ữ li ệu h ọc thơng qua vi ệc gán và hi ệu ch ỉnh các tr ọng s ố liên k ết. Tổ ch ức theo ki ểu t ập h ợp mang l ại cho m ạng n ơ-ron kh ả n ăng tính tốn r ất l ớn, trong đĩ khơng cĩ n ơ-ron nào mang thơng tin riêng bi ệt. Ví d ụ : Hình 1.2, 1.3,1.4, 1.5 là m ột s ố mơ hình m ạng thơng d ụng. • Các hình tr ạng c ủa m ạng Hình tr ạng m ạng được đị nh ngh ĩa b ởi: s ố l ớp (layers), s ố đơn v ị trên mỗi l ớp, và s ự liên k ết gi ữa các l ớp đĩ. Các m ạng th ường được chia làm hai lo ại d ựa trên cách th ức liên k ết các đơn v ị: 1.1.2.3.1. Mạng truy ền th ẳng - Mạng truy ền th ẳng m ột l ớp Mạng perceptron m ột l ớp do F.Rosenblatt đề xu ất n ăm 1960 là m ạng truy ền th ẳng ch ỉ m ột l ớp vào và m ột l ớp ra khơng cĩ l ớp ẩn. Trên m ỗi l ớp này cĩ th ể cĩ m ột ho ặc nhi ều n ơ-ron. Mơ hình m ạng n ơ-ron c ủa F.Rosenblatt s ử dụng hàm ng ưỡng đĩng vai trị là hàm chuy ển. Do đĩ, t ổng c ủa tín hi ệu vào lớn h ơn giá tr ị ng ưỡng thì giá tr ị đầ u ra c ủa n ơ-ron s ẽ là 1, cịn trái l ại s ẽ là 0. 1, nếu net ≥ θ out = i i < θ (1.9) 0, nếu net i Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 13 Với net i = ∑ wijx j là t ổng thơng tin đầ u vào c ủa n ơ-ron i. Mơ hình m ạng n ơ-ron truy ền th ẳng m ột l ớp là mơ hình liên k ết c ơ b ản và đơ n gi ản nh ất. Các n ơ-ron t ổ chức l ại v ới nhau t ạo thành m ột l ớp, đường truy ền tín hi ệu được truy ền theo m ột h ướng nh ất đị nh nào đĩ. Các đầu vào được n ối v ới các n ơ-ron theo các tr ọng s ố khác nhau, sau quá trình x ử lý cho ra m ột chuỗi các tín hi ệu ra. x1 y1 x2 y2 Xm yn Hình 1.3. M ạng truy ền th ẳng m ột l ớp = [ ]T Với m ỗi giá tr ị đầ u vào. x x 1 , x 2 , , xn . Qua quá trình x ử lý c ủa mạng ta s ẽ thu được m ột b ộ t ươ ng ứng các giá tr ị đầ u ra là = [ ]T y y ,1 y ,2 , yn được xác đị nh nh ư sau : m = −θ = yi fi ∑ wij x j i ,i ,1 n (1.10) j=1 Trong đĩ : m : S ố tín hi ệu vào n : S ố tín hi ệu ra Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 14 T =[ ]T Wi wi1 , wi2 , , win : là véc t ơ tr ọng s ố c ủa n ơ-ron th ứ i. fi : Là hàm kích ho ạt n ơ-ron th ứ i θ i : Là ng ưỡng c ủa n ơ-ron th ứ i. Ngay t ừ khi m ạng Perceptron được đề xu ất nĩ được s ử d ụng để gi ải quy ết bài tốn phân l ớp. M ột đối t ượng s ẽ được n ơ-ron i phân vào l ớp A n ếu : θ Tổng thơng tin đầ u vào ∑ wijx j > i Trong tr ường h ợp trái l ại n ơ-ron s ẽ được phân vào l ớp B. - Mạng truy ền th ẳng nhi ều l ớp (Multilayer Perceptron –MLP) Với m ạng n ơ-ron truy ền th ẳng m ột l ớp ở trên, khi phân tích m ột bài tốn ph ức t ạp s ẽ g ặp r ất nhi ều khĩ kh ăn, để kh ắc ph ục v ấn đề này ng ười ta đư a ra mơ hình m ạng n ơ-ron truy ền th ẳng nhi ều l ớp b ằng vi ệc k ết h ợp m ột s ố lớp n ơ-ron l ại v ới nhau. L ớp nh ận tín hi ệu vào g ọi là l ớp vào, l ớp đưa tín hi ệu ra c ủa m ạng được g ọi là l ớp ra. Các l ớp ở gi ữa l ớp vào và l ớp ra được g ọi là lớp ẩn và các n ơ-ron trong các l ớp ẩn cĩ hàm chuy ển (hàm kích ho ạt) d ạng phi tuy ến. Mạng n ơ-ron nhi ều l ớp cĩ th ể gi ải quy ết các bài tốn phi tuy ến nh ờ vào các l ớp ẩn. Càng nhi ều l ớp ẩn thì kh ả n ăng m ở r ộng thơng tin càng cao và xử lý t ốt m ạng cĩ nhi ều l ớp vào và l ớp ra. Hình (1.4) mơ t ả c ấu trúc c ủa m ạng n ơ-ron truy ền th ẳng nhi ều l ớp. Lớp vào x Lớp ẩn Lớp ra y x y y x m Hình 1.4. M ạng truy ền th ẳng nhi ều l ớp Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 15 1.1.2.3.2. Mạng h ồi quy (Recurrent Neutral Network) Mạng h ồi quy m ột l ớp cĩ n ối ng ược X1 Y1 X2 Y2 . . . . . . . . . XN YM Hình 1.5. M ạng m ột l ớp cĩ n ối ng ược Mạng h ồi quy nhi ều l ớp cĩ n ối ng ược. X1 Y1 X 2 Y 2 . . . . . . . . . . . . X Y Hình 1.6. M ạng nhi ều l ớp cĩ n ối 1.1.2.4. Lu ật h ọc Ti ến trình h ọc là ti ến trình quan tr ọng c ủa con ng ười, nh ờ h ọc mà b ộ não ngày càng tích l ũy các kinh nghi ệm để thích nghi v ới mơi tr ường và x ử lý tình hu ống t ốt h ơn. M ạng n ơ-ron xây d ựng l ại c ấu trúc b ộ não thì ph ải c ần cĩ kh ả n ăng nh ận bi ết d ữ li ệu thơng qua ti ến trình h ọc, v ới các thơng s ố t ự do của m ạng cĩ th ể thay đổ i liên t ục b ởi nh ững thay đổ i c ủa mơi tr ường và m ạng nơ-ron ghi nh ớ giá tr ị đĩ. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 16 Trong quá trình h ọc, giá tr ị đầ u vào được đưa vào m ạng và theo dịng ch ảy trong m ạng t ạo thành giá tr ị đầ u ra. Ti ếp đế n là quá trình so sánh giá tr ị t ạo ra b ởi mạng n ơ-ron v ới giá tr ị mong mu ốn. N ếu hai giá tr ị này gi ống nhau thì khơng thay đổi gì c ả. Tuy nhiên, n ếu cĩ m ột sai l ệch gi ữa hai giá tr ị này v ượt quá giá tr ị sai s ố mong mu ốn thì đi ng ược m ạng t ừ đầ u ra v ề đầ u vào để thay đổ i m ột s ố k ết n ối. Đây là quá trình l ặp l ại liên t ục và cĩ th ể khơng d ừng khi khơng tìm được giá tr ị W sao cho đầ u ra t ạo b ởi m ạng n ơ-ron b ằng đúng đầ u ra mong mu ốn. Do đĩ trong th ực t ế ng ười ta ph ải thi ết l ập m ột s ố tiêu chu ẩn d ựa trên một giá tr ị sai s ố nào đĩ c ủa hai giá tr ị này, hay d ựa trên m ột s ố l ần l ặp nh ất định. Để ti ện cho vi ệc trình bày, ta kí hi ệu y là giá tr ị k ết xu ất c ủa m ạng n ơ- ron, t là giá tr ị ra mong mu ốn, e là sai l ệch gi ữa hai giá tr ị này.: e = t - y Mạng n ơ-ron cĩ m ột s ố ưu điểm so v ới máy tính truy ền th ống. C ấu trúc song song c ủa m ạng n ơ-ron r ất thích h ợp cho nh ững ứng d ụng địi h ỏi t ốc độ nhanh theo th ời gian th ực. Kh ả n ăng hu ấn luy ện c ủa m ạng n ơ-ron cĩ th ể khai thác để phát tri ển h ệ th ống thích nghi. M ặt khác, v ới kh ả n ăng t ổng quát hĩa của m ạng n ơ-ron, nĩ cĩ th ể áp d ụng để điều khi ển nhi ều tham s ố ph ức t ạp đồng th ời t ừ đĩ gi ải quy ết d ễ dàng m ột s ố bài tốn thu ộc l ớp bài tốn NP- đầy đủ (NP-Complete ). Các lu ật h ọc đĩng vai trị quan tr ọng trong vi ệc xác đị nh m ột m ạng nơ-ron nhân t ạo. M ột cách đơn gi ản v ề khái ni ệm h ọc c ủa m ạng n ơ-ron là c ập nh ật tr ọng s ố trên c ơ s ở các m ẫu. Theo ngh ĩa r ộng thì h ọc cĩ th ể được chia ra làm hai lo ại: H ọc tham s ố và h ọc c ấu trúc. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 17 - H ọc tham s ố: Các th ủ t ục h ọc này nh ằm tìm ki ếm ma tr ận tr ọng s ố sao cho m ạng cĩ kh ả n ăng đư a ra d ự báo sát v ới th ực t ế. D ạng chung c ủa lu ật h ọc tham s ố cĩ th ể được mơ t ả nh ư sau: ∆W =ηrx ,i = ,1 N, j = ,1 M (1.11) ij j trong đĩ: ∆ Wij : là s ự thay đổ i tr ọng s ố liên k ết t ừ n ơ ron j đến n ơ ron i. x j : là tín hi ệu vào n ơ ron j. η : là t ốc độ h ọc, n ằm trong kho ảng (0,1). r : là h ằng s ố h ọc. Vấn đề đặ t ra ở đây là tín hi ệu h ọc r được sinh ra nh ư th ế nào để hi ệu ch ỉnh tr ọng s ố c ủa m ạng. Cĩ th ể chia th ủ t ục h ọc tham s ố ra thành ba l ớp h ọc nh ỏ h ơn: H ọc cĩ ch ỉ đạ o, h ọc t ăng c ường và h ọc khơng ch ỉ đạ o. Vi ệc xác đị nh r tùy thu ộc vào từng ki ểu h ọc. + Học cĩ tín hi ệu ch ỉ đạ o: Là quá trình m ạng h ọc d ựa vào sai s ố gi ữa đầu ra th ực và đầu ra mong mu ốn để làm c ơ s ở cho vi ệc hi ệu ch ỉnh tr ọng s ố. Sai s ố này chính là h ằng s ố h ọc r. Lu ật h ọc điển hình c ủa nhĩm này là lu ật học Delta c ủa Widrow (1962) nêu ra đầu tiên dùng để x ấp x ỉ tr ọng c ủa Adaline d ựa trên nguyên t ắc gi ảm gradient. Trong nhĩm lu ật h ọc này c ũng c ần ph ải k ể đế n lu ật h ọc Perceptron c ủa Rosenblatt (1958). V ề c ơ b ản lu ật h ọc này thay đổi các giá tr ị tr ọng trong th ời gian h ọc, cịn lu ật Perceptron thì thêm ho ặc b ỏ tr ọng tùy theo giá tr ị sai s ố dươ ng hay âm. Một lo ạt các lu ật h ọc khác c ũng được d ựa trên t ư t ưởng này. Lu ật Oja là c ải ti ến và nâng c ấp c ủa lu ật Delta. Lu ật truy ền ng ược là lu ật m ở r ộng c ủa lu ật Delta cho m ạng nhi ều l ớp. Đố i v ới m ạng truy ền th ẳng th ường s ử d ụng Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 18 lu ật truy ền ng ược để ch ỉnh tr ọng v ới tín hi ệu ch ỉ đạ o t ừ bên ngồi và ng ười ta gọi m ạng này là m ạng lan truy ền ng ược. + H ọc khơng cĩ tín hi ệu ch ỉ đạ o: Lu ật h ọc này s ử d ụng đầ u ra c ủa mạng làm c ơ s ở để hi ệu ch ỉnh các tr ọng s ố liên k ết. Hay trong lu ật này chính là tín hi ệu ra c ủa m ạng. Điển hình là lu ật Hebb (1949) th ường dùng cho các mạng t ự liên k ết, lu ật LVQ (Learning Vector Quantization) dùng cho m ạng t ự tổ ch ức m ột l ớp thu ộc l ớp m ạng ánh x ạ đặ c tr ưng c ủa Kohonen. Lu ật h ọc Hebb là lu ật sinh h ọc xu ất phát t ừ tiên đề c ủa Hebb cho r ằng: Gi ữa hai n ơ-ron cĩ quan h ệ và cĩ thay đổi th ế n ăng thì gi ữa chúng cĩ s ự thay đổi tr ọng số liên k ết. Nĩi cách khác, tr ọng s ố được điều ch ỉnh theo m ối t ươ ng quan tr ước và sau, ngh ĩa là: ∆ = η = = Wij yi x j ,i ,1 N, j ,1 M (1.12) trong đĩ: ∆ Wij là s ự thay đổ i tr ọng s ố liên k ết t ừ n ơ-ron j đến n ơ-ron i. x j: là tín hi ệu vào n ơ-ron j. yi là tín hi ệu ra c ủa n ơ-ron i. η là t ốc độ h ọc, n ằm trong kho ảng (0,1). Lu ật Hebb gi ải thích vi ệc ch ỉnh tr ọng trong ph ạm vi c ục b ộ c ủa m ạng mà khơng c ần tín hi ệu ch ỉ đạ o t ừ bên ngồi. Hopfield c ũng c ải ti ến lu ật Hebb cho các m ạng t ự liên k ết thành 16 d ạng khác nhau theo ki ểu lu ật Hebb, lu ật đối Hebb, lu ật Hopfield Nh ư v ậy, ứng v ới m ỗi nhĩm m ạng th ường áp d ụng m ột lu ật h ọc nh ất định. N ếu t ồn t ại hàng ch ục lo ại m ạng khác nhau thì các lu ật h ọc dùng trong mạng n ơ-ron cĩ th ể t ăng lên r ất nhi ều l ần. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 19 Đối v ới m ạng ph ản h ồi th ường s ử d ụng lu ật Hebb và các lu ật c ải ti ến của nĩ để ch ỉnh tr ọng mà khơng c ần tín hi ệu ch ỉ đạ o t ừ bên ngồi. + H ọc t ăng c ường: Trong m ột s ố tr ường h ợp, thơng tin ph ản h ồi ch ỉ là tín hi ệu bao g ồm hai tr ạng thái cho bi ết tín hi ệu đầ u ra c ủa m ạng là đúng hay sai. Quá trình h ọc d ựa trên các thơng tin h ướng d ẫn nh ư v ậy được g ọi là h ọc cĩ c ủng c ố (h ọc t ăng c ường) và tín hi ệu mang thơng tin ph ản h ồi được g ọi là tín hi ệu c ủng c ố cho quá trình h ọc. Ta cĩ th ể th ấy r ằng quá trình h ọc này là một d ạng c ủa quá trình h ọc cĩ tín hi ệu ch ỉ đạ o b ởi vì m ạng nh ận được m ột s ố thơng tin ph ản h ồi t ừ bên ngồi. - H ọc c ấu trúc : Tìm ki ếm các tham s ố c ủa c ấu trúc m ạng để tìm ra m ột cấu trúc m ạng ho ạt động t ốt nh ất. Trong th ực t ế, vi ệc h ọc c ấu trúc là tìm ra s ố lớp ẩn và tìm ra s ố n ơ-ron trên m ỗi l ớp đĩ. Gi ải thu ật di truy ền th ường được sử d ụng trong các c ấu trúc nh ưng th ường ch ạy r ất lâu, th ậm chí ngay c ả đối với m ạng cĩ kích th ước trung bình. Ngồi ra k ỹ thu ật g ọt t ỉa m ạng hay m ạng tăng d ần c ũng được áp d ụng trong vi ệc h ọc c ấu trúc c ủa m ạng cĩ kích th ước tươ ng đối nh ỏ. 1.2. PH ẠM VI ỨNG D ỤNG C ỦA M ẠNG N Ơ RON NHÂN T ẠO 1.2.1. Nh ững bài tốn thích h ợp Mạng n ơ-ron được coi nh ư là h ộp đen bi ến đổ i véc-tơ đầu vào m bi ến thành véc-tơ đầu ra n bi ến. Tín hi ệu ra cĩ th ể là các tham s ố th ực, (t ốt nh ất nằm trong kho ảng [0, 1], ho ặc [-1, 1]), s ố nh ị phân 0, 1, hay s ố l ưỡng c ực - 1;+1. S ố bi ến c ủa véc-tơ vào ra khơng b ị h ạn ch ế xong s ẽ ảnh h ưởng t ới th ời gian tính và t ải d ữ li ệu c ủa máy tính. Nĩi chung, các l ớp bài tốn áp d ụng cho nơ-ron cĩ th ể được phân chia thành b ốn lo ại: 1. Phân l ớp (classification). 2. Mơ hình hố (modeling). Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 20 3. Bi ến đổ i, th ực hi ện ánh x ạ t ừ m ột khơng gian đa bi ến vào khơng gian đa bi ến khác t ươ ng ứng (transformation and mapping). 4. Liên k ết và k ỹ thu ật d ịch chuy ển c ửa s ổ (association and moving window). 1.2.1.1. Phân lo ại Một trong các cơng vi ệc đơn gi ản và th ường được s ử d ụng nhi ều trong vi ệc qu ản lý các đố i t ượng đa bi ến là phân lo ại (phân l ớp m ột đố i t ượng vào các nhĩm, nhĩm con, hay ch ủng lo ại). Ví d ụ: Bài tốn phân l ớp ảnh, nh ận dạng m ẫu, . . . Khi ph ải phân lo ại m ột quy ết đị nh ph ức t ạp, chúng ta ph ải b ắt đầ u v ới vi ệc nghiên c ứu th ống kê các m ối liên quan gi ữa nhi ều đố i t ượng và thu ộc tính c ủa l ớp các đố i t ượng. Cĩ th ể nĩi vi ệc xây d ựng m ột cây phân l ớp các quy ết đị nh ph ải được th ực hi ện tr ước khi th ủ t ục h ọc được ti ến hành. N ếu k ết qu ả cu ối cùng khơng tho ả mãn, chúng ta c ần ph ải xem xét l ại cách bi ểu di ễn các đối t ượng ho ặc cây phân l ớp ho ặc thay đổ i c ả hai. 1.2.1.2. Mơ hình hố Các h ệ th ống phân lo ại đưa ra các câu tr ả l ời r ời r ạc nh ư cĩ, khơng ho ặc m ột s ố nguyên định danh các đố i t ượng đầ u vào thu ộc l ớp nào. Mơ hình hố yêu c ầu h ệ th ống ph ải s ản sinh ra các câu tr ả l ời mang tính liên t ục. Trong quá trình mơ hình hố, c ần m ột s ố l ượng nh ỏ các s ố li ệu để xây d ựng mơ hình. Mơ hình này cĩ th ể đưa ra các d ự báo cho t ất c ả các đố i t ượng đầ u vào. Vi ệc tìm ra đường cong phù h ợp v ới các s ố li ệu th ực nghi ệm là m ột trong nh ững ứng d ụng thu ộc d ạng này. Trong b ất k ỳ lo ại mơ hình nào c ũng ph ải tuân theo m ột gi ả đị nh là: các thay đổi nh ỏ c ủa tín hi ệu vào ch ỉ gây ra nh ững bi ến đổ i nh ỏ c ủa tín hi ệu ra. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 21 Trong các v ấn đề đa bi ến, m ạng n ơ-ron cĩ nhi ều l ợi th ế h ơn so v ới các ph ươ ng pháp mơ hình hố c ổ điển s ử d ụng các hàm gi ải tích. B ởi vì trong ph ươ ng pháp mơ hình hố c ổ điển đố i v ới m ỗi đầ u ra, ta ph ải đị nh ngh ĩa m ột hàm c ụ th ể cùng m ột b ộ các tham s ố, trong khi đĩ đố i v ới m ạng n ơ-ron thì khơng ph ải quan tâm t ới các hàm đĩ. Tuy nhiên, trong các ph ươ ng pháp mơ hình hố c ổ điển, các h ệ s ố cĩ th ể cĩ m ột s ố ý ngh ĩa nào đĩ đối v ới v ấn đề c ần gi ải quy ết, trái l ại các tr ọng s ố c ủa m ạng khơng mang m ột ý ngh ĩa nào c ả. Trong nhi ều ứng d ụng khá đặ c bi ệt, khi sai s ố th ực hi ện khá l ớn chúng ta cĩ th ể mơ hình hố b ằng cách cân x ứng hố gi ữa tín hi ệu vào tín hi ệu ra. Trong các tr ường h ợp này, s ử d ụng m ạng nh ư m ột b ảng tra là đủ, m ặc dù các b ảng này s ẽ cho l ời gi ải gi ống nhau trong m ột kho ảng nào đĩ c ủa tín hi ệu vào. Đối v ới vi ệc ch ọn chi ến l ược h ọc, chúng ta c ần quan tâm đế n s ự phân bố c ủa các đố i t ượng dùng để h ọc. N ếu số l ượng đố i t ượng dùng cho vi ệc h ọc là ít và được phân b ố t ươ ng đối đề u trong tồn khơng gian, khi đĩ s ố li ệu cĩ th ể được dùng ngay cho vi ệc mơ hình hố. Trái l ại, n ếu các đố i t ượng là nhi ều, s ẵn cĩ nh ưng phân b ố ng ẫu nhiên trong khơng gian bi ến, đầ u tiên ph ải gi ảm thi ểu chúng sao cho v ẫn bao trùm tồn khơng gian, sau đĩ m ới dùng làm số li ệu cho vi ệc mơ hình hố. 1.2.1.3. Bi ến đổ i Vi ệc bi ến đổ i nh ằm m ục đích nén các đố i t ượng t ừ khơng gian m chi ều vào khơng gian cĩ s ố chi ều nh ỏ h ơn r ất nhi ều. Qua vi ệc nén, các đối t ượng này sẽ b ộc l ộ các đặ c điểm mà chúng ta khơng th ể nh ận th ấy khi chúng thu ộc khơng gian nhi ều chi ều. Theo m ột ch ừng m ực nào đĩ, bi ến đổ i t ươ ng t ự nh ư vi ệc nhĩm các đố i t ượng hay phân lo ại th ể hi ện ở ch ỗ bi ểu di ễn các k ết qu ả ra. Trong phân lo ại, chúng ta mu ốn đị nh danh các nhĩm ho ặc l ớp mà đối t ượng Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 22 thu ộc vào, cịn trong bi ến đổ i, chúng ta quan tâm đế n tồn b ộ các đố i t ượng và từ đĩ chúng ta thu nh ận được các nhĩm t ừ các đố i t ượng h ọc. Điểm quan tr ọng trong bi ến đổ i là các đối t ượng được bi ểu diễn b ởi to ạ độ c ủa n ơ-ron trung tâm ch ứ khơng ph ải là giá tr ị c ủa tín hi ệu ra. Một trong nh ững ứng d ụng c ủa vi ệc bi ến đổ i là ti ền x ử lý (th ường được gọi là k ế ho ạch hố th ực nghi ệm). Thơng qua quá trình ti ền x ử lý, chúng ta cĩ th ể ch ọn ra các đố i t ượng điển hình t ừ t ập vơ s ố các đố i t ượng ng ẫu nhiên, lo ại tr ừ các đố i t ượng d ư th ừa hay trùng l ặp. Điều này là c ực k ỳ quan tr ọng khi l ựa ch ọn các đố i t ượng làm m ẫu h ọc cho m ạng lan truy ền ng ược sai s ố. 1.2.1.4. Liên k ết Liên k ết là tìm ra đối t ượng đích cĩ m ối quan h ệ v ới m ột đố i t ượng vào, th ậm chí c ả khi đố i t ượng vào b ị h ỏng ho ặc hồn tồn khơng bi ết. Theo một ngh ĩa nào đĩ, liên k ết cĩ th ể được coi là phân lo ại. Th ủ t ục h ọc cho v ấn đề này là h ọc cĩ tín hi ệu ch ỉ đạ o. Lĩnh v ực nghiên c ứu các quá trình ph ụ thu ộc th ời gian là m ột trong nh ững l ĩnh v ực chính trong nghiên c ứu quá trình điều khi ển. Ở đây ng ười s ử dụng d ự báo được các hành vi c ủa h ệ th ống đa bi ến d ựa trên m ột chu ỗi s ố li ệu được ghi nh ận theo th ời gian. Trong mơ hình hố ph ụ thu ộc th ời gian, các bi ến c ủa tín hi ệu vào bao g ồm các giá tr ị hi ện t ại và quá kh ứ c ủa các bi ến quá trình, trong đĩ tín hi ệu ra d ự báo giá tr ị trong t ươ ng lai c ủa nh ững bi ến quá trình đĩ. V ề nguyên t ắc các hi ểu bi ết này cĩ th ể cĩ các độ dài tu ỳ ý, nh ưng trong quá trình ki ểm sốt hi ểu bi ết t ươ ng lai ch ỉ bao g ồm m ột b ước th ời gian. Vi ệc h ọc d ịch chuy ển t ới b ước ti ếp theo t ạo ra các c ửa s ổ bao g ồm s ố b ước th ời gian c ủa véc-tơ ra. Để t ạo ra mơ hình hồn ch ỉnh c ủa m ột quá trình, t ất c ả các bi ến quá trình ph ải được hu ấn luy ện t ại đầ u ra c ủa m ạng, nh ưng khơng ph ải t ất c ả các bi ến trong quá trình đều ảnh h ưởng nh ư nhau đối v ới k ết qu ả cu ối cùng, ch ỉ cĩ m ột s ố bi ến là đáng quan tâm. Do đĩ chúng ta ch ỉ ph ải ch ọn Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 23 các bi ến đĩ cho quá trình h ọc. K ỹ thu ật d ịch chuy ển c ửa s ổ cĩ th ể được s ử dụng để gi ải quy ết các v ấn đề chu ỗi các s ự ki ện và đối t ượng nh ư trong các lĩnh v ực v ề mơi tr ường theo th ời gian, ki ểm sốt h ỏng hĩc. 1.2.2. Các l ĩnh v ực ứng d ụng m ạng n ơ ron Trong quá trình phát tri ển, m ạng n ơ ron đã được ứng d ụng thành cơng trong r ất nhi ều lĩnh v ực. M ột s ố ứng d ụng chính c ủa m ạng n ơ-ron cĩ th ể li ệt kê là: - Xử lý ảnh: G ồm trùng kh ớp ảnh, ti ền x ử lý ảnh, phân đoạn và phân tích ảnh, nén ảnh, - Xử lý tín hi ệu: phân tích tín hi ệu đị a ch ấn và hình thái h ọc. - Nh ận d ạng m ẫu: G ồm vi ệc tách các nét đặ c bi ệt c ủa m ẫu, phân lo ại và phân tích tín hi ệu c ủa ra đa, nh ận d ạng và hi ểu ti ếng nĩi, nh ận d ạng vân tay, ký t ự, ch ữ vi ết, - Y h ọc: phân tích và hi ểu tín hi ệu điện tâm đồ , chu ẩn đốn b ệnh, x ử lý ảnh y h ọc. - Các h ệ th ống quân s ự: phát hi ện th ủy lơi, phân loại lu ồng ra đa, nh ận dạng ng ười nĩi. - Gi ải trí: Ho ạt hình, các hi ệu ứng đặ c bi ệt, d ự báo th ị tr ường. - Các h ệ tài chính: G ồm phân tích th ị tr ường ch ứng khốn, đị nh giá b ất động s ản, cho vay, ki ểm tra tài s ản c ầm c ố, đánh giá m ức độ h ợp tác, phân tích đường tín d ụng, c ấp phát th ẻ tín d ụng, d ự báo t ỷ giá ti ền t ệ và th ươ ng m ại an tồn. - Trí tu ệ nhân t ạo: G ồm các h ệ chuyên gia, - Các h ệ th ống n ăng l ượng. - Dự đốn: D ự đốn các tr ạng thái c ủa h ệ th ống, Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 24 - Vấn đề l ập k ế ho ạch, điều khi ển và tìm ki ếm: G ồm cài đặt song song các bài tốn th ỏa mãn ràng bu ộc, bài tốn l ập th ời khĩa bi ểu cho tr ường đại h ọc, bài tốn ng ười đi du l ịch, - Gi ải các bài tốn t ối ưu: V ấn đề chính là tìm nh ững thu ật tốn hu ấn luy ện m ạng để gĩp ph ần tìm nghi ệm cho nhi ều l ớp bài tốn t ối ưu tồn cục. Tĩm l ại, m ạng n ơ-ron nhân t ạo được xem là m ột cách ti ếp c ận đầ y ti ềm n ăng để gi ải quy ết các bài tốn cĩ tính phi tuy ến, ph ức t ạp và đặc bi ệt trong tình hình các d ữ li ệu đầ u vào khơng t ường minh. 1.3. M ẠNG HOPFIELD Trong m ạng h ồi quy tín hi ệu ra c ủa m ột n ơ-ron cĩ th ể được truy ền ng ược l ại làm tín hi ệu vào cho các n ơ-ron ở các l ớp tr ước, ho ặc các n ơ-ron trong cùng m ột l ớp. Ph ần này s ẽ trình bày mơ hình m ạng tiêu bi ểu thu ộc l ớp mạng h ồi quy, đĩ là m ạng Hopfield. Mạng Hopfield được b ắt đầ u nghiên c ứu t ừ n ăm 1982. Đây là m ạng một l ớp v ới thơng tin và quá trình x ử lý cĩ n ối ng ược. Chính cơng trình c ủa Hopfield được tìm th ấy r ất nhi ều ứng d ụng, đặ c bi ệt trong b ộ nh ớ liên k ết và trong các bài tốn t ối ưu. Gi ả s ử m ạng được xây d ựng d ưới d ạng m ạng m ột l ớp, m ỗi n ơ-ron được truy ền ng ược l ại làm tín hi ệu vào cho các n ơ-ron khác nh ưng b ản thân các nơ-ron khơng t ự liên k ết v ới chính nĩ. Khi đĩ mơ hình m ạng Hopfield được bi ểu di ễn nh ư Hình 1.6. Tín hi ệu ra c ủa n ơ-ron th ứ j nào đĩ được truy ền ng ược l ại làm tín hi ệu vào cho các n ơ-ron khác trong m ạng m ột cách đầ y đủ thơng qua các tr ọng s ố tươ ng ứng. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 25 X1 Y1 Đầu vào X2 Y2 Đầu ra . . . XN YM Hình 1.7. Mơ hình m ạng Hopfield w = w Ký hi ệu W ij là liên k ết giữa hai n ơ-ron i và j ( ij ji ), V i là đầu ra của n ơ-ron i. Ta coi véc t ơ (V 1, V 2, V n) là tr ạng thái c ủa m ạng. T ại m ỗi th ời điểm t m ỗi n ơ-ron i t ổng h ợp các tín hi ệu V j t ừ các n ơ-ron khác và tín hi ệu t ừ bên ngồi (bias) = + U i ∑Wij V j I i Tu ỳ theo hàm kích ho ạt f i mà n ơ-ron i cho đầu ra là: Vi(t+1) = f i(V i(t)). Mạng đạ t tr ạng thái cân b ằng n ếu V i(t+1) = V i(t) , ∀ i Ta định ngh ĩa hàm n ăng l ượng c ủa m ạng là: n n n = () = − 1 − E E V1,V2 , , Vn ∑∑Wij ViV j ∑ E jVi (1.13) 2 Tu ỳ theo ph ươ ng th ức ho ạt độ ng c ủa m ạng mà ng ười ta phân m ạng Hopfield ra thành m ạng Hopfield r ời r ạc và m ạng Hopfield liên t ục. 1.3.1. M ạng Hopfield r ời r ạc. Mạng Hopfield r ời r ạc là m ạng được tính r ời r ạc ( đầ u ra r ời r ạc) và làm vi ệc ở ch ế độ khơng đồ ng b ộ. Tr ường h ợp m ạng nh ận các giá tr ị nh ị phân {0, 1}: Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 26 Hàm kích ho ạt được xác đị nh nh ư sau: f i ≡ f 1,nếunet ≥ 0 f( net ) = 0, nếu khác (1.14) Vi ệc cho hàm kích ho ạt (1.13) t ươ ng đươ ng v ới quy t ắc chuy ển tr ạng thái c ủa m ạng V i(t+1) = V i(t) + ∆Vi trong đĩ ∆Vi được cho b ởi cơng th ức (quy t ắc) 1, nếu∑WVt ( )+ I ≥ 0 vàVt ( ) = 0 ij j i i ∆=−V1,nếu WVtI () +≤ 0 vàVt ()1 = i ∑ ij j i i (1.15) 0, trongcáctrườnghợpkhác = Định lý: Gi ả s ử W ii =0 ( i i, n ). Khi đĩ v ới quy t ắc chuy ển tr ạng thái nh ư trên và c ập nh ật khơng đồ ng b ộ thì n ăng l ượng c ủa m ạng khơng t ăng (t ức là gi ảm ho ặc gi ữ nguyên). Ch ứng minh: Gi ả s ử n ơ-ron khơng thay đổi tr ạng thái t ừ th ời điểm t đến t+1. Khi đĩ m ạng s ẽ thay đổ i n ăng l ượng và ∆ = + − = − − ∆ E E(t )1 E(t) ( ∑Wkj V j (t) I k ) Vk (1.16) j Vì th ế theo cơng th ức (1.14) ta luơn cĩ ∆E≤ 0, t ức là n ăng l ượng c ủa m ạng khơng t ăng. Vì th ế hàm n ăng l ượng s ẽ đạ t t ới giá tr ị c ực ti ểu. Do hàm gi ới nội. Do tính ch ất h ội t ụ và giá tr ị nh ị phân c ủa các n ơ-ron nên m ạng Hopfield r ời r ạc được s ử d ụng cho các bài tốn t ối ưu {0, 1} Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 27 Một m ở r ộng c ủa m ạng nh ị phân là m ạng l ượng t ử hố. Đây là m ột lo ại mạng m ới được đề xu ất và thích h ợp cho vi ệc gi ải các bài tốn quy ho ạch nguyên. 1.3.2. M ạng Hopfield liên t ục. Mạng Hopfield liên t ục là m ạng mà tr ạng thái c ủa nĩ được mơ t ả b ởi ph ươ ng trình động h ọc dU i = + ∑Wij V j Ii (1.17) dt j = Vi f i (U i ) trong đĩ fi là hàm kích ho ạt. Ở đây ta c ũng gi ả thi ết W ij = W ji và W ii =0. D ễ th ấy r ằng n ếu hàm n ăng l ượng được cho b ởi (1.12) thì : dU ∂ i = − E ∂ dt Vi Sự h ội t ụ c ủa m ạng Hopfield liên t ục cho b ởi đị nh lý sau: dE Định lý: nếu f i(U i) ( i= 1, n ) là các hàm kh ả vi và khơng gi ảm thì ≤ 0 dt Ch ứng minh : Ta cĩ vì theo gi ả thi ết các hàm f i(U i) là khơng gi ảm n ếu dV dE i ≥ 0 , do đĩ ≤ 0 , dU i dt ∂ ∂ 2 dE = E dVi dU i = − E dVi ∑ ∑ . dt ∂V dU dt ∂V dU ii i i i i Với t ư cách là hàm kích ho ạt ng ười ta th ường ch ọn hàm Sigmoid: 1 1 λ V = Sigmoid (U ) = = 1( + tanh( U )) i i −λU i λ trong đĩ 1 + e i 2 2 >0 là Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 28 tham s ố xác đị nh độ d ốc c ủa hàm. Đồ th ị c ủa hàm Sigmoid v ới m ột s ố giá tr ị của λ xem hình v ẽ 1 1 0.9 0.9 0.8 0.8 0.7 0.7 0.6 0.6 0.5 0.5 0.4 0.4 0.3 0.3 0.2 0.2 0.1 0.1 0 0 -5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5 lamda =1 lamda =2 Đồ th ị hàm Sigmoid Với hàm kích ho ạt Sigmoid thì c ực ti ểu đị a ph ươ ng c ủa hàm n ăng l ượng bu ộc x ảy ra v ới các giá tr ị c ủa V i b ằng 0 ho ặc 1. Chính vì v ậy m ạng Hopfield được sử d ụng cho các bài tốn t ối ưu t ổ h ợp {0, 1}. Nh ận xét rằng hàm kích ho ạt Sigmoid là m ột hàm nén (squashing function) trong d ải [0, 1] và vì th ế thích h ợp cho các bài tốn t ối ưu {0, 1}. N ếu c ần gi ải bài tốn t ố ưu {-1, 1} c ần s ử d ụng hàm nén trong d ải [-1, 1], ch ẳng h ạn hàm tanh (λx). 1 0.8 0.6 0.4 0.2 0 -0.2 -0.4 -0.6 -0.8 -1 -5 -4 -3 -2 -1 0 1 2 3 4 5 Đồ th ị hàm Hàm y=tanh(x) 1.3.3. M ạng Hopfield v ới bài tốn t ối ưu Sau cơng trình c ủa Hopfield và Tank m ạng Hopfield đã được s ử d ụng nhi ều vào vi ệc gi ải bài tốn t ối ưu t ổ h ợp. Ta đã bi ết m ạng Hopfield s ẽ đạ t t ới Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 29 tr ạng thái cân b ằng khi hàm n ăng l ượng c ủa nĩ đạ t t ới giá tr ị c ực ti ểu. Vì v ậy, từ bài tốn cho tr ước, ta xây d ựng m ột hàm m ục tiêu F nào đĩ ( đã được x ử lý các ràng bu ộc) và đặt F = E (E là hàm n ăng l ượng), sau đĩ tìm m ối liên h ệ gi ữa các bi ến c ủa chúng. Chính vì v ậy mà m ạng Hopfield r ất phù h ợp v ới các bài tốn t ối ưu t ổ h ợp, đặ c bi ệt là đối v ới m ột s ố bài tốn thu ộc l ớp bài tốn NP-đầy đủ nh ư: bài tốn th ời khĩa bi ểu, bài tốn ng ười bán hàng, tìm đường đi t ối ưu cho tuy ến đường xe bus tr ường h ọc, bài tốn ng ười đưa th ư, Tuy nhiên, khi s ử d ụng m ạng Hopfield vào vi ệc gi ải các bài tốn t ối ưu trong th ực t ế cịn g ặp m ột s ố h ạn ch ế sau: - Mạng Hopfield khơng đả m b ảo cho h ội t ụ tồn c ục. Để kh ắc ph ục, ng ười ta đã k ết h ợp m ạng Hopfield v ới m ột s ố gi ải thu ật khác, ví d ụ nh ư gi ải thu ật di truy ền v. v. . . , ho ặc đưa vào ph ươ ng trình động h ọc m ột s ố h ạng đặ c bi ệt g ọi là s ố h ạng leo đồ i. T ừ đĩ hàm n ăng l ượng c ủa m ạng cĩ th ể thay đổ i đế n m ột tr ạng thái cao h ơn, tránh được h ội t ụ đị a ph ươ ng và ti ến t ới h ội t ụ tồn c ục. - Vi ệc ch ọn h ệ s ố c ủa hàm m ục tiêu và h ệ s ố c ủa hàm ràng bu ộc để nh ận được một l ời gi ải t ốt là h ết s ức khĩ kh ăn. Cho đế n nay, vi ệc ch ọn nĩ v ẫn ch ủ y ếu dựa vào kinh nghi ệm. Hi ện nay, đã cĩ m ột s ố ph ươ ng pháp điều khi ển các h ệ số này b ằng cách dùng điều khi ển m ờ . - Một cách t ổng quát, cĩ th ể xây d ựng m ột s ố b ước c ần ph ải th ực hi ện khi s ử dụng m ạng Hopfield vào vi ệc gi ải bài tốn t ối ưu nh ư sau (ánh x ạ bài tốn t ối ưu lên m ạng n ơ ron): 1. Lập s ơ đồ bi ểu di ễn các đầ u ra c ủa m ạng sao cho nĩ cĩ th ể gi ải mã thành nghi ệm c ủa bài tốn t ối ưu. 2. Tạo hàm n ăng l ượng sao cho giá tr ị c ực ti ểu c ủa nĩ ứng v ới nghi ệm t ốt nh ất c ủa bài tốn c ần ánh x ạ. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 30 3. Gán giá tr ị cho các tham s ố c ủa hàm n ăng l ượng, điều này xác định các tr ọng s ố t ươ ng đối gán cho các thành ph ần khác nhau c ủa hàm n ăng lượng. 4. Đư a ra ph ươ ng trình động h ọc cho các n ơ ron. 5. Kh ởi t ạo các giá tr ị đầ u vào. * Chú ý: Khơng cĩ ph ươ ng pháp ánh x ạ tr ực ti ếp các bài tốn t ối ưu cĩ ràng bu ộc lên m ạng n ơ ron. Cho nên ph ải thêm vào hàm m ục tiêu các thành ph ần ph ạt khi các ràng bu ộc b ị phá v ỡ. Khi đĩ hàm n ăng l ượng được bi ểu di ễn nh ư tổng c ủa hàm m ục tiêu và các thành ph ần ph ạt. 1.3.4. M ạng Hopfield v ới bài tốn l ập th ời khĩa bi ểu Bài tốn th ời khĩa bi ểu bao hàm s ự phân cơng Giáo viên, l ớp và phịng học c ụ th ể t ới khung th ời gian và h ọc k ỳ, theo cách đĩ khơng m ột ai đĩ được giao nhi ều h ơn m ột phịng t ại m ột th ời điểm và phịng khơng cĩ nhi ều h ơn một l ớp h ọc và giáo viên t ại cùng th ời điểm. Nh ư v ậy, th ời khĩa bi ểu mang tính kh ả thi tránh được xung đột, nh ưng khơng h ẳn nh ất thi ết nh ư v ậy. Để th ời khĩa bi ểu ho ạt độ ng chúng ta c ần xem xét đế n m ột s ố ràng bu ộc c ụ th ể. Ví d ụ về các ràng bu ộc này s ẽ được gi ới thi ệu ở ph ần sau đề tài này. Th ường t ổ ch ức hồn thi ện nh ất l ập th ời khĩa bi ểu nh ư các khĩa h ọc và l ập k ế ho ạch ki ểm tra trong tr ường đạ i h ọc. Các cơ s ở gi ả đị nh trong mơ hình đơ n gi ản này là chúng ta đang l ập th ời khĩa bi ểu lớp h ọc ch ứ khơng ph ải là sinh viên cá nhân. M ột l ớp đị nh ngh ĩa nh ư m ột nhĩm sinh viên h ọc cùng khĩa h ọc gi ống nhau về cùng mơn h ọc và khơng phân tách, b ởi v ậy cĩ th ể thay đổ i nh ư m ột nhĩm và cĩ th ể tham chi ếu đế n nh ư m ột th ực th ể đơn. Một trong nh ững bài tốn th ời khĩa bi ểu đơn gi ản nh ất là mơ hình l ớp – giáo viên được trình bày b ởi De Werra (1985) nh ư sau (xem [9]): Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 31 Gọi C là t ập h ợp các l ớp h ọc và T là tập hợp các giáo viên. Ta xây d ựng × một ma tr ận kích th ước C T th ỏa R = ( Rij ). Trong đĩ, Rij là s ố đơ n v ị th ời gian mà giáo viên j ph ải d ạy l ớp i trong su ốt th ời gian bi ểu quy đị nh. Chúng ta định ngh ĩa m ột bi ến logic xij k nh ư sau: = 1, nếulớpi vàgiáoviên j dạytrongthờigia n k x k (1) ij 0,trườnghợp khác Theo cơng th ức (1) thì xij k =1 th ể hi ện m ột giáo viên j cĩ m ặt để d ạy lớp i t ại phịng k ; và xij k = 0 trong tr ường h ợp cịn l ại, ví d ụ nh ư khơng cĩ giáo viên j, dạy l ớp i, vào th ời gian k. Mơ hình Lớp – giáo viên (TT1) P = ∀ ∈ ∈ ∑ xijk Rij ( i C, j T) (2) k=1 T ≤ ∀ ∈ ∈∏ ∑ xijk 1 ( i C,k ) (3) j=1 C ≤ ∀ ∈ ∈∏ ∑ xijk 1 ( j T,k ) (4) i=1 ∀∈ ∈ ∈ xij k = 0 ho ặc 1 ( i Cj; Tk ;∏ ) (5) Cơng th ức (2) đả m b ảo m ỗi b ộ (L ớp – giáo viên) ch ỉ xu ất hi ện chính xác m ột lần trong th ời khĩa bi ểu, trong khi cơng th ức (3) và (4) tránh xung đột l ớp, giáo viên, và cơng th ức (5) b ảo đả m tính tồn v ẹn cho l ời gi ải. Trong mơ hình TT1, quy v ề bài tốn liên quan đến đồ th ị hai phía G= ( CTR , ,ˆ ) và s ử d ụng k ỹ thuật tơ màu các c ạnh để tìm xung đột trong phân cơng L ớp –giáo viên. Đỉnh c ủa đồ th ị là l ớp và giáo viên, m ỗi đỉ nh ci và đỉnh Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 32 tj liên k ết b ởi các c ạnh song song Rij . Bài tốn yêu c ầu cách tơ m ầu cho m ỗi cạnh c ủa đồ th ị G (t ừ ch ọn l ựa P m ầu) sao cho khơng cĩ hai c ạnh li ền k ề cĩ mầu gi ống nhau. K ỹ thu ật phát tri ển m ạng được s ử d ụng để gi ải quy ết bài tốn L ớp – giáo viên đơ n gi ản chính xác cho kích c ỡ đồ th ị nh ỏ. Tuy nhiên, đây là bài tốn thu ộc l ớp NP đầ y đủ và k ỹ thu ật tơ m ầu c ủa c ạnh và phát tri ển mạng hồn tồn khơng phù h ợp cho l ời gi ải khi m ở r ộng bài tốn L ớp – giáo viên. 1.4. NH ẬN XÉT Mạng truy ền th ẳng và m ạng h ồi quy là hai mơ hình tiêu bi ểu c ủa m ạng n ơ- ron nhân t ạo, m ỗi lo ại m ạng s ẽ cĩ nh ững ưu nh ược điểm riêng. - Mạng truy ền th ẳng m ột l ớp d ễ phân tích nh ưng khơng mơ t ả được m ọi hàm. M ạng nhi ều l ớp kh ắc ph ục được nh ược điểm trên nh ưng l ại r ất khĩ phân tích và g ặp khĩ kh ăn trong quá trình xây d ựng m ạng. M ặt khác mạng truy ền th ẳng nhi ều l ớp cĩ th ể gây sai s ố tích l ũy qua các l ớp. - Mạng ph ản h ồi m ột l ớp (tiêu bi ểu là m ạng Hopfield) cĩ c ấu trúc đơn gi ản vì th ế d ễ phân tích, khơng ch ứa sai s ố tích l ũy. - Mạng n ơ-ron truy ền th ẳng ch ỉ đơn thu ần tính tốn các tín hi ệu ra d ựa trên các tín hi ệu vào và tr ọng s ố liên k ết gi ữa các n ơ-ron đã xác định s ẵn trong m ạng. Do đĩ chúng khơng cĩ tr ạng thái bên trong nào khác ngồi tr ọng s ố W. Đố i v ới m ạng h ồi quy, tr ạng thái bên trong c ủa m ạng được lưu tr ữ t ại các ng ưỡng c ủa n ơ-ron. Nĩi chung m ạng h ồi quy khơng ổn định, m ạng c ần ph ải tính tốn r ất lâu, th ậm chí l ặp vơ h ạn tr ước khi đư a ra k ết qu ả mong mu ốn. Quá trình h ọc c ủa m ạng h ồi quy c ũng ph ức t ạp hơn m ạng truy ền th ẳng r ất nhi ều. Tuy v ậy các m ạng h ồi quy cĩ th ể cho phép mơ ph ỏng các h ệ th ống t ươ ng đối ph ức t ạp trong th ực t ế Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 33 CH ƯƠ NG II: ỨNG D ỤNG M ẠNG N Ơ-RON HOPFIELD TRONG BÀI TỐN L ẬP TH ỜI KHĨA BI ỂU CHO TR ƯỜNG ĐẠI H ỌC 2.1 Bài tốn l ập th ời khĩa bi ểu và nh ững khĩ kh ăn trong vi ệc l ập th ời khĩa bi ểu cho tr ường đạ i h ọc. - Phát bi ểu bài tốn Gọi V là t ập h ợp các phịng h ọc và C, T lần l ượt là t ập các l ớp h ọc và ∈ × × các giáo viên. Ta xây d ựng m ột ma tr ận Rij k C T V, trong đĩ, Rij k là s ố đơ n v ị th ời gian mà giáo viên j ph ải dạy l ớp i t ại phịng h ọc k theo th ời gian bi ểu quy đị nh. Chúng ta định ngh ĩa m ột bi ến logic xij kl nh ư sau: 1, = nếu l ớp i và giáo viên j d ạy t ại phịng k trong th ời gian l xij kl (6) 0, ng ược l ại Ví d ụ: Giáo viên : Nguy ễn V ăn A -> j Phịng : 309 A -> k Lớp : ĐH Tin 11B ->i Th ời gian: 8h30 – 10h05 ->l Theo cơng th ức (6) thì xij kl =1 th ể hi ện m ột giáo viên j cĩ m ặt để d ạy lớp i t ại phịng k trong th ời gian l; và xij kl = 0 trong các tr ường h ợp cịn l ại. Bài tốn l ập th ời khĩa bi ểu đáp ứng các ràng bu ộc theo mơ hình TT2 (Timetable 2) được phát bi ểu nh ư sau: Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 34 Mơ hình Lớp – giáo viên – phịng h ọc (TT2 ) Cần tìm các bi ến logic xij kl th ỏa mãn các ràng bu ộc sau (xem [9]): P = ∀ ∈ ∈ ∈ ∑ xijkl Rijk ( i C, j T,k V ) (7) l=1 T V ≤ ∀∈ ∀∈∏ ∑∑ xijkl 1( iCl , ) j=1 k = 1 (8) C V ≤ ∀∈ ∈∏ ∑∑ xijkl 1( jTl , ) i=1 k = 1 (9) C T ≤ ∀∈ ∈∏ (10) ∑∑ xijkl 1( kVl , ) = = i1 j 1 ∀∈ ∈ ∈ ∈∏ xijkl = 0 ho ặc 1 (i Cj ;; Tk Vl ; ) (11) Trong đĩ, cơng th ức (7) ở v ế ph ải Rij k th ể hi ện m ối quan h ệ gi ữa l ớp i – giáo viên j – phịng h ọc k, v ế trái c ủa cơng th ức ta s ử d ụng bi ến xij kl để nĩi t ổng th ời gian (s ố ti ết) mà m ột giáo viên j dạy l ớp i t ại phịng k trong th ời điểm l được th ực hi ện su ốt trong th ời gian bi ểu. Các cơng th ức t ừ (8) –(10) đảm b ảo L ớp –giáo viên – phịng h ọc khơng b ị xung đột. C ụ th ể: • Cơng th ức (8) đả m b ảo ràng bu ộc v ề Giáo viên – phịng h ọc, ngh ĩa là trong m ột l ớp t ại m ột th ời điểm ch ỉ cĩ t ối đa m ột giáo viên j d ạy phịng k. hay m ột phịng h ọc ch ỉ được phép m ột giáo viên d ạy t ại m ột th ời điểm. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 35 • Cơng th ức (9) đả m b ảo c ặp ràng bu ộc L ớp - phịng h ọc, ngh ĩa là m ọi giáo viên j tại m ột th ời điểm l ch ỉ d ạy được m ột l ớp i t ại phịng k hay một phịng h ọc ch ỉ được phép m ột l ớp h ọc t ại m ột th ời điểm. • Cơng th ức (10) đả m b ảo ràng bu ộc theo c ặp L ớp –giáo viên, t ức trong một th ời điểm l một lớp ch ỉ cĩ t ối đa m ột giáo viên. • Cơng th ức (11) th ể hi ện giá tr ị bi ến logic xij kl ch ỉ được phép nh ận m ột trong hai giá tr ị 0 ho ặc 1. Với m ục đích xây d ựng mơ hình bài tốn th ời khĩa bi ểu để gi ải b ằng mạng nơ-ron Hopfield, ta di ễn gi ải mơ hình bài tốn th ời khĩa bi ểu ở trên (TT2) sang d ạng bi ễu di ễn m ới (TT3) nh ư sau: Gi ả s ử cĩ b ộ ba T ( Lớp- giáo viên - phịng h ọc) cho vi ệc l ập th ời gian bi ểu t ới h ọc k ỳ P. M ỗi b ộ ba theo m ẫu l ớp i gặp giáo viên j t ại phịng k. Cĩ duy nh ất m ột b ộ ba s ẽ x ảy ra Rijk trong tồn b ộ T, t ổng s ố b ộ ba được xác đị nh b ởi: C T V τ = R ∑∑∑ ijk (12) i=1j = 1k = 1 Sử d ụng bi ến Boolean xtp nh ư sau: ,1 nếu bộ ba t = (i, j, k) được gán đợ t P (13) = xtp ,0 nếu khác Định ngh ĩa các ma tr ậnCˆ, Tˆ , V ˆ : ,1 ˆ = nếu l ớp i thu ộc b ộ ba t=(i,j,k ) Cit (14) ,0 n ếu khác Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 36 ,1 ˆ = nếu giáo viên j thu ộc b ộ ba t= (i,j,k ) (15) T jt ,0 nếu khác ,1 nếu phịng h ọc k thu ộc b ộ ba t= (i,j,k ) (16) ˆ = Vkt ,0 nếu khác Ma tr ận x định rõ m ột l ời gi ải đúng cho bài tốn th ời khĩa bi ểu n ếu th ỏa mãn các ràng bu ộc (TT3): P = ∀ ∈τ ∑ xtp 1 ( t ) (17) p=1 τ ˆ ≤ ∀∈ ∈ ∑ xCtp it 1( iCp ,∏ ) (18) t=1 τ ˆ ≤ ∀ ∈ ∈ (19) ∑ xtp T jt 1 ( j T, p ∏) t=1 τ ˆ ≤ ∀ ∈ ∈ ∑ xtp Vkt 1 ( k V , p ∏) (20) t=1 = { } ∀ ∈τ ∈Π (21) xtp ,1,0 ( t , p ) Ph ươ ng trình (17) đảm b ảo m ỗi b ộ ba (L ớp – giáo viên – phịng h ọc) ch ỉ xu ất hi ện chính xác m ột l ần trong th ời khĩa bi ểu, trong khi ph ươ ng trình (18) – (20) tránh xung đột lớp, giáo viên, phịng h ọc, và ph ươ ng trình (21) b ảo đảm tính tồn v ẹn cho l ời gi ải. Rõ ràng, cơng th ức này trình bày ng ắn g ọn h ơn so v ới TT2, nh ằm gi ảm chi ều bài tốn. Trong khi trình bày TT2 bao hàm ma tr ận l ời gi ải v ới kích th ước C x T x V x P, qua trình bày TT3 gi ảm xu ống cịn kích th ước τ × P . Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 37 - Nh ững khĩ kh ăn trong vi ệc l ập th ời khĩa bi ểu Vi ệc ánh x ạ các ràng bu ộc bài tốn lên m ạng n ơ-ron Hopfield thơng qua hàm n ăng l ượng E, xác đị nh các thành ph ần trong hàm ph ạt, t ừ đĩ k ết h ợp hàm n ăng l ượng c ủa m ạng n ơ-ron Hopfield cho ra ma tr ận tr ọng s ố c ủa mơ hình bài tốn, s ẽ là nh ững khĩ kh ăn th ực s ự khi tìm l ời gi ải bài tốn l ập th ời khĩa bi ểu. Vi ệc bài tốn v ới t ập d ữ li ệu l ớn v ề s ố l ượng các l ớp h ọc, giáo viên, phịng, đơ n v ị th ời gian và nhi ều điều ki ện ràng bu ộc s ẽ ảnh h ưởng đế n kh ả năng tính tốn c ủa ch ươ ng trình. 2.2. Tình hình gi ải quy ết bài tốn l ập th ời khĩa bi ểu Th ời khĩa bi ểu là m ột dạng bài tốn kinh điển trong ho ạt độ ng nghiên cứu về l ập l ịch nĩi chung, do bài tốn địi h ỏi ph ải th ỏa mãn nhi ều điều ki ện ràng bu ộc. T ừ hình th ức đơ n gi ản nh ất nh ư mơ hình l ớp – giáo viên đến các bài tốn phân cơng cơng vi ệc ph ức t ạp, th ời khĩa bi ểu là bài tốn tối ưu t ổ hợp dạng NP-complete, và chúng ta s ẽ m ở r ộng m ối liên h ệ mơ hình l ớp – giáo viên này. Cĩ th ể sử d ụng m ạng n ơ-ron Hopfield để giải bài tốn th ời khĩa bi ểu cho tr ường đại h ọc. Các nghiên c ứu tr ước đây s ử d ụng m ạng n ơ-ron cho bài tốn th ời khĩa bi ểu khơng mang l ại kết qu ả nh ư mong đợi, nh ưng nh ững nghiên c ứu g ần đây đã ch ứng minh rằng m ạng n ơ-ron đã cĩ thể gi ải quy ết t ốt Bài tốn Ng ười bán hàng rong (Smith, 1999). Vi ệc áp d ụng mạng n ơ-ron Hopfield vào lập th ời khĩa bi ểu tr ường h ọc mang tính th ời s ự và hi ệu su ất của m ạng Hopfield ph ụ thu ộc vào vi ệc s ử d ụng cơng th ức phù h ợp. Thu ật gi ải mạng Hopfield cĩ th ể so sánh v ới các thu ật tốn siêu tìm ki ếm (metaheuristics) khác nh ư mơ ph ỏng luy ện kim (Annealing) và tìm ki ếm tabu về l ời gi ải ch ất l ượng và th ời gian tính tốn qua ki ểm tra. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 38 2.3. Xây d ựng mơ hình m ạng Hopfield cho bài tốn th ời khĩa bi ểu 2.3.1. M ạng n ơ ron Hopfield Mạng n ơ ron Hopfield ( Hopfield, 1982, 1984) là cơng c ụ tốn h ọc cĩ th ể được s ử d ụng để gi ải các bài tốn t ối ưu t ổ h ợp. Ưu th ế c ủa m ạng n ơ-ron đã v ượt qua nh ững k ỹ thu ật t ối ưu truy ền th ống ở d ạng ti ềm n ăng v ề s ức mạnh tính tốn r ất nhanh khi ph ươ ng ti ện ph ần c ứng máy tính ngày càng phát tri ển, và dùng trong m ạng tính tốn x ử lý song song. Cĩ hai lo ại m ạng Hopfield là m ạng Hopfield r ời r ạc và liên t ục, cho các giá tr ị khác nhau tùy vào tr ạng thái n ơ-ron. Mơ hình sinh h ọc c ủa b ộ não ng ười là luơn c ố g ắng s ử d ụng đầ y đủ các h ệ th ống k ết n ối bên trong c ủa N nơ-ron. N ơ-ron i cĩ tr ạng thái vào ui và đầu ra vi (cĩ th ể là giá tr ị nh ị phân trong m ạng r ời r ạc ho ặc giá tr ị th ực b ởi s ố 0 và 1 ở m ạng liên t ục). Tr ạng thái ui k ết h ợp đầ u vào bias Ii, và tổng tr ọng s ố đi ra t ừ t ất c ả các n ơ-ron. Tr ọng số, xác đị nh độ dài c ủa các k ết n ối t ừ n ơ-ron i t ới j, cho b ởi Wij . Quan h ệ gi ữa các tr ạng thái c ủa m ột n ơ-ron và tín hi ệu đi ra c ủa n ơ-ron được xác đị nh b ởi hàm kích ho ạt g(u i). Hàm kích ho ạt này độc l ập trên m ạng Hopfield r ời r ạc ho ặc liên t ục. Cĩ d ạng: 1 u v= g( u ) = (1 + tanh(i )) (22) i i 2 λ Cơng th ức trên s ử d ụng cho m ạng Hopfield liên t ục, trong đĩ λ là bi ến xác định độ d ốc c ủa hàm kích ho ạt g(u i). Đối v ới m ạng Hopfield r ời r ạc, hàm kích ho ạt th ường th ể hi ện hàm ng ưỡng rời r ạc: 1 , nếuu > 0 v = g ( u ) = i (23) i i 0, nếuu ≤ 0 i Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 39 Các n ơ-ron tự học (tu ần t ự ho ặc song song) theo đúng lu ật sau: N ut(+= 1) ut ( ) +∆ t wvI + i i∑ ij j i (24) j=1 + = (25) vti( 1) gu ( i ) ( trong ∆t là th ời gian tr ễ c ố đị nh), và khi th ực hi ện m ạng n ơ-ron s ẽ h ội t ụ v ề cực ti ểu đị a ph ươ ng với hàm n ăng l ượng theo th ời gian: 1 N N N E= − Wvv − Iv ∑∑ij i j ∑ i i (26) 2 i=1 j = 1 i = 1 Được cung c ấp b ởi tr ọng s ố đố i x ứng W ij = W ji . Nếu các n ơ-ron ti ếp nh ận thơng tin song song (ho ặc đồ ng b ộ) thì tr ạng thái h ội t ụ t ới t ồn t ại hai chu k ỳ. C ả hai tr ạng thái m ạng trong đĩ bao g ồm hai chu k ỳ s ẽ c ực ti ểu đị a ph ươ ng v ới hàm n ăng lượng. Mạng r ời r ạc cĩ ưu th ế h ơn m ạng liên t ục trong s ố l ần c ập nh ập để h ội t ụ c ực ti ểu đị a ph ươ ng và t ốc độ th ực hi ện nhanh h ơn trong m ỗi n ơ-ron, v ề ch ủ điểm này, liên k ết v ới ràng bu ộc ph ần c ứng khác, chúng tơi đã ch ọn m ạng Hopfield rời r ạc để gi ải bài tốn th ời khĩa bi ểu trình bày ở trên. Chúng tơi c ũng ch ọn cập nh ập cho các n ơ-ron b ằng phép tốn song song h ơn cách tu ần t ự tr ước đây, t ăng c ường khơng gi ới h ạn để gi ải các bài tốn l ớn v ới t ốc độ nhanh nh ất cĩ th ể. Liên quan đến vi ệc th ực hi ện t ất c ả các tính tốn song song c ủa tr ạng thái đầu vào u khi t ất c ả v được c ập nh ập, trái v ới c ập nh ập tu ần t ự mà tính tốn u và v c ập nh ập cho n ơ-ron t ại m ột th ời điểm. Hopfield và Tank (1985) cho th ấy r ằng n ếu bài tốn t ối ưu 0 – 1 cĩ th ể được th ể hi ện trong m ột hàm n ăng l ượng được cho b ởi cơng th ức (26), m ạng Hopfield cĩ th ể được dùng để tìm l ời gi ải t ối ưu c ục b ộ c ủa hàm n ăng l ượng, cĩ th ể d ịch đế n l ời gi ải c ực ti ểu đị a ph ươ ng c ủa bài tốn t ối ưu, cung c ấp tham Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 40 số m ạng (tr ọng s ố và đầu vào bias) đã được l ựa ch ọn thích h ợp cho bài tốn. Thơng th ường, hàm n ăng l ượng c ủa m ạng được th ực hi ện t ươ ng đươ ng v ới hàm m ục tiêu c ủa bài tốn t ối ưu đã được gi ảm đế n m ức t ối thi ểu. Trong khi các ràng bu ộc bài tốn bao g ồm hàm n ăng l ượng nh ư hàm ph ạt. Các tham s ố mạng cĩ th ể được suy ra b ởi so sánh v ới hàm n ăng l ượng chu ẩn cho b ởi cơng th ức (26). Tr ọng s ố c ủa m ạng, Wij , h ệ s ố c ủa hàm b ậc 2 vivj, và đầu vào bias hi ện t ại, I i m ỗi n ơ-ron i, h ệ s ố v i c ủa hàm n ăng l ượng. Mạng được cài đặt ban đầ u m ức kích ho ạt v i c ủa m ỗi n ơ-ron t ới tr ạng thái. Ng ẫu nhiên và khơng đồng b ộ c ập nh ập c ủa m ạng x ảy ra ở cơng th ức (24) và (25) s ẽ cho tr ạng thái n ăng l ượng t ối thi ểu đạ t được, tr ước m ức n ăng lượng khơng t ăng trong su ốt tr ạng thái d ịch chuy ển (Hopfield, 1982). Ch ứng minh liên quan th ể hi ện: N ∆ = − + ∆ ≤ E ∑Wij v j Ii vi 0 j=1 Bởi n ếu N <∆<0u 0 và ∆≤ v 0 + = i i ∑Wij v j I i j=1 ≥∆≥0u 0 và ∆≥ v 0 i i Các d ẫn xu ất c ủa tr ọng s ố và đầu vào bias ở hai trình bày th ời khĩa bi ểu (TT2 và TT3) được cho ở trên. 2.3.2. Ánh x ạ bài tốn th ời khĩa bi ểu lên m ạng n ơ-ron Hopfield Để ánh x ạ bài tốn t ối ưu lên m ạng n ơ-ron Hopfield, chúng ta c ần đưa ra các tr ọng s ố và ràng bu ộc c ủa bài tốn. Hàm n ăng l ượng bi ểu di ễn theo TT2: 2 αCTVP β CTVPTV E= xR −+ xx + ∑∑∑∑ijkl ij ∑∑∑∑∑∑ ijkl ij' k ' l 2=== 2 === ' ' ijkl1111 ijkl 1111 j=1 k = 1 '≠ ' ≠ j jk k (27) χCTVPCV γ C TVPCT xx+ xx ∑∑∑∑∑∑ijkl i'' jk l ∑ ∑∑∑∑∑ ijkl i' jkl ' 2ijkl===1111i''=1 k = 1 2 i=1 jkl === 111 i'=1 j ' = 1 i''≠ i k ≠ k i'≠ ij ' ≠ j Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 41 Trong đĩ α,β,χ, γ là các tham s ố ph ạt được ch ọn để cân b ằng các thành ph ần của hàm. Số h ạng đầ u tiên trong ph ươ ng trình (27) đạt giá tr ị c ực ti ểu khi yêu cầu ràng bu ộc (7) là th ỏa mãn, và lớn h ơn khơng trong tr ường h ợp cịn l ại. Ba thành ph ần cịn l ại trong ph ươ ng trình (27) đảm b ảo các ràng bu ộc tươ ng ứng với các b ất ph ươ ng trình (8)-(10). Mạng Hopfield cĩ th ể được thi ết k ế để t ối thi ểu hĩa hàm này, với điều ki ện tr ọng s ố c ủa m ạng và đầu ra bias xác đị nh c ụ th ể. M ột n ơ-ron vijkl th ực hi ện t ươ ng đươ ng v ới ma tr ận gi ải xijkl , và m ột ma tr ận tám chi ều cĩ tr ọng s ố v kết n ối t ất c ả các n ơ-ron vijkl t ới t ất c ả các n ơ-ron khác i' ji kl ' ' xây d ựng ma tr ận bốn chi ều đầu ra bias. Hàm n ăng l ượng rút ra t ừ mạng Hopfield là: C T V P T V P C T V P = − 1 − (28) E W ' ' '' v v ' ' '' I v ∑∑∑∑∑∑∑ ijkl , lkji ijkl lkji ∑∑∑∑ ijkl ijkl 2 i=1j = 1k = 1l = 1 '''= = = i=1j = 1k = 1l = 1 j 1k 1l 1 Hàm này t ổng quát hĩa ph ươ ng trình (26) cho các bi ến bốn chi ều c ủa m ỗi nơ-ron. Sau khi khai tri ển sắp x ếp l ại hàm (27), so sánh với hàm n ăng l ượng (28) cho hai hàm t ươ ng đươ ng sau. Thi ết l ập ma tr ận tr ọng c ủa TT2: W ijkl, i' j ' ki l ' =−αδδδ − βδ (1 −− δ )(1 δδχδδ ) −− (1 ) (1 − δδ ) iijjkk'''' ii jj ' kk '' ll ii '' jj kk '' ll (29) −γ(1 − δ )(1 − δδδ ) ii' jj ' kk '' ll = α Iijkl R ijk (30) ở đây σ là hàm Kronecker – Delta , σ =1 n ếu y= y ' và b ằng khơng trong yy ' yy ' trường h ợp khác. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 42 = ' δ = 1,nếu i i Ta cĩ: ' ii 0, ngượclại i≠ i ' α C T V 2 Một thành ph ần hằng s ố được thêm vào là ∑∑∑ Rijk 2 i=1 j = 1 k = 1 Tuy nhiên hằng s ố này cĩ th ể được b ỏ qua mà khơng ảnh h ưởng đế n các giá tr ị t ối ưu c ục b ộ và tồn c ục c ủa hàm g ốc (27), và hàm n ăng l ượng Hopfield (28). Đối v ới mơ hình l ớp – giáo viên – phịng h ọc (TT3), chúng ta cĩ th ể ánh x ạ lên m ạng n ơ-ron Hopfield theo cách t ươ ng t ự. S ử d ụng mơ hình này, số chi ều c ủa m ỗi n ơ-ron là nh ỏ h ơn, và số chi ều k ết n ối tr ọng số và đầu ra bias c ũng nh ư v ậy. T ừ mơ hình TT3 đã trình bày, m ột hàm tối ưu cĩ th ể được xây d ựng nh ư sau: 2 ατ P β CPτ τ χ TP τ τ E= x −+1 xCxCˆ ˆ + xTxTˆ ˆ ∑∑tp ∑∑∑∑ tp it tpit'' ∑∑∑∑ tp jt tpjt' ' 2tp==11 2 ipt === 111t' =1 2 jpt === 111 t ' = 1 t' ≠ t t' ≠ t γ V P τ τ (31) + x Vˆ x V ˆ ∑∑∑∑ tp kt t' p kt ' 2 k=1 p = 1 t = 1 t' =1 t' ≠ t Số h ạng đầ u tiên của ph ươ ng trình (31) s ẽ b ằng khơng n ếu m ỗi b ộ ba L ớp – giáo viên – phịng h ọc x ếp chính xác v ới th ời khĩa bi ểu. Điều ki ện th ứ hai đảm b ảo s ự xung độ t v ề l ớp là nh ỏ nh ất b ởi t ất c ả ba thành ph ần tránh l ớp đã xếp trong m ột th ời điểm. Điều ki ện ba và b ốn đảm b ảo h ạn ch ế đế n m ức t ối thi ểu các vi ph ạm về giáo viên và phịng h ọc. Để ánh x ạ bài tốn t ối ưu lên m ạng n ơ-ron Hopfield, l ời gi ải ma trận x là đặt l ại ban đầ u nh ư là m ột ma tr ận n ơ-ron nh ị phân v, và hàm n ăng l ượng v W I mạng Hopfield s ẽ là m ột hàm c ủa tp , tp, t' p ' , và tp . Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 43 Thi ết l ập ma tr ận tr ọng s ố theo TT3: C T W=−−−αδβδδ (1 )CCˆ ˆ −− χδδ (1 ) TTˆ ˆ tptp, '' tt ' ttpp ''∑it it ' ttpp '' ∑ jt jt ' i=1 j = 1 (32) V −γ(1 − δ ) δ Vˆ V ˆ tt' pp '∑ kt kt ' k =1 = α Itp (33) Nh ư v ậy, các cơng th ức (29) và (30) định ngh ĩa các tham s ố m ạng c ủa mơ hình TT2, và các cơng th ức (32) và (33) dành cho mơ hình TT3. Cĩ th ể nh ận th ấy r ằng, s ố chi ều c ủa n ơ-ron và ma tr ận tr ọng s ố và ma tr ận đầ u ra bias, nh ư TT3 cĩ tính hi ệu qu ả h ơn so v ới các mơ hình tr ước. S ố n ơ-ron địi hỏi c ũng gi ảm b ớt khi s ử d ụng TT3 đố i v ới bài tốn th ời khĩa bi ểu m ở r ộng. 2.4. Thu ật tốn m ạng n ơ-ron Hopfield trong bài tốn l ập th ời khĩa bi ểu cho tr ường Đạ i học Thu ật gi ải m ạng n ơ-ron Hopfield dùng mã gi ả nh ư sau: Kh ởi t ạo u ( ng ẫu nhiên) Tính v s ử d ụng ph ươ ng trình (23) For i= 1 to descent For j=1 to l ặp For k=1 to N Cập nh ập uk dùng ph ươ ng trình (24) Cập nh ập vk dùng ph ươ ng trình (25) Tăng k N ∆ Tính ổn đị nh = ∑ vk k=1 Nếu tiêu chu ẩn ổn đị nh đã phù h ợp, thốt vịng l ặp j Tăng j Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 44 Ch ọn m ột n ơ-ron ng ẫu nhiên, và xoay t ới ng ưỡng → >→ < Chu ẩn hĩa u ( uk1 nếuu kk 0; u 0 nếuu k 0 ) T ăng i. (xem [9], p293-294) Mạng n ơ-ron Hopfield dạng chu ẩn khi được c ập nh ật theo ph ươ ng trình (24) và (25) ở trên s ẽ cực ti ểu cả hai hàm n ăng l ượng Hopefield và hàm ph ạt t ối ưu tươ ng ứng. B ản ch ất c ủa vi ệc gi ảm thi ểu này là gi ảm độ d ốc xu ống, việc này s ẽ gây m ột vài khĩ kh ăn cho vi ệc h ội t ụ ở cực tr ị địa ph ươ ng c ủa hàm n ăng l ượng. Chúng ta s ẽ cịn g ặp nhi ều khĩ kh ăn h ơn khi xem xét b ản ch ất c ủa các c ực tr ị đị a ph ươ ng này. Vì bài tốn t ối ưu hĩa được th ể hi ện thơng qua m ột chu ỗi các điều ki ện ph ạt, r ất khĩ để cân b ằng các điều ki ện này b ằng cách l ựa ch ọn các tham s ố ph ạt, trong tr ường h ợp này là α, β , χγ , . Nếu s ố h ạng α quá l ớn so v ới ba s ố h ạng cịn l ại, l ời gi ải bài tốn nhi ều kh ả n ăng s ẽ cĩ xung đột gi ữa các l ớp h ọc, giáo viên, phịng h ọc hay gi ữa c ả ba ràng bu ộc v ới nhau. T ươ ng t ự, n ếu s ố h ạng α quá nh ỏ so v ới ba s ố hạng cịn l ại, lời gi ải s ẽ g ần nh ư khơng cĩ mâu thu ẫn do các điều ki ện ho ặc b ộ ba đã b ị lo ại b ỏ để gi ảm mâu thu ẫn. Các c ực tr ị đị a ph ươ ng này s ẽ d ẫn t ới vi ệc l ập nên m ột th ời khĩa bi ểu khơng hi ệu qu ả. Để đạ t được m ột th ời khĩa bi ểu t ốt, c ực tr ị tồn c ục ph ải được duy trì, t ươ ng ứng v ới chi phí b ỏ ra b ằng khơng theo ph ươ ng trình (27) ho ặc (31). Rõ ràng, n ếu các tham s ố phạt được ch ọn thích h ợp để cân b ằng các thành ph ần c ủa bài tốn t ối ưu, chúng ta v ẫn ph ải đố i m ặt v ới các v ấn đề gây ra b ởi thu ật tốn độ d ốc xu ống c ủa quy t ắc c ập nh ật. Trong ph ần này, chúng tơi s ẽ trình bày m ột s ố sửa đổ i để tránh kh ỏi cực tr ị đị a ph ươ ng. Các s ửa đổ i của chúng tơi d ựa trên vi ệc quan sát và nh ận th ấy m ạng n ơ-ron Hopfield ho ạt động t ốt nh ất ( đo l ường b ằng vi ệc gi ảm hàm n ăng l ượng m ột cách nhanh chĩng) trong su ốt vài l ần l ặp l ại đầ u tiên. M ột l ần l ặp l ại được đị nh ngh ĩa là Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 45 một l ần c ập nh ật hồn tồn c ủa t ất c ả các n ơ-ron N d ựa theo ph ươ ng trình (24) và (25). Trong vài l ần l ặp l ại đầ u tiên, hàm n ăng l ượng gi ảm nhanh chĩng và cải thi ện t ừ t ừ sau đĩ, cho t ới sau kho ảng 50 vịng l ặp thì g ặp ph ải m ột c ực tr ị địa ph ươ ng và m ạng dao độ ng gi ữa n ơ-ron tr ạng thái và t ất c ả giá tr ị n ăng lượng t ươ ng t ự nhau. Do đĩ, chúng tơi ch ấm d ứt vi ệc c ập nh ật sau m ột s ố ít lần l ặp l ại, đưa giá tr ị u v ề 0 ho ặc 1 d ựa trên giá tr ị v hi ện t ại, và kh ởi độ ng l ại quá trình. Quá trình này được l ặp đi l ặp l ại m ột vài l ần. Tính ng ẫu nhiên ở cu ối m ỗi vịng được t ạo ra b ằng cách ch ọn ng ẫu nhiên m ột n ơ-ron và cho nĩ một tr ạng thái v b ằng 0 ho ặc 1. M ột ng ưỡng được dùng để ki ểm sốt tính ng ẫu nhiên, n ếu ng ưỡng là 0.5 thì t ất c ả các n ơ-ron đều s ẽ cĩ c ơ h ội ngang nhau để tr ở thành 0 ho ặc 1, nh ưng n ếu nh ư ng ưỡng được t ăng lên 0.9 thì s ẽ ch ỉ cĩ 10% c ơ h ội cho 1 n ơ-ron tr ở thành 1. Để cho phép m ột m ức gi ảm b ất kỳ d ừng l ại khi xu ất hi ện c ực tr ị đị a ph ươ ng, chúng tơi c ũng gi ới thi ệu m ột ph ươ ng pháp được g ọi là ổn đị nh, đế m s ố thay đổ i tr ạng thái c ủa n ơ-ron trong N ∆ ∆ một l ần l ặp ∑ vk ho ặc v . N ếu tr ạng thái ổn đị nh đo l ường này d ưới giá tr ị k=1 được xác đị nh tr ước, m ạng Hopfield cĩ th ể d ừng độ d ốc hi ện t ại, xoay vịng của m ột n ơ-ron, và ti ếp t ục v ới g ốc khác. T ạo m ột s ố l ần l ặp linh ho ạt, và t ổng số l ần l ặp cho phép được gi ảm đi đáng k ể cĩ th ể. Vì v ậy, nh ững s ửa đổ i đế n m ạng n ơ-ron linh ho ạt ở trên k ết h ợp v ới thu ộc tính m ột kh ả n ăng tìm ki ếm vơ h ướng trong nh ững đoạn ng ắn độ d ốc xu ống, dùng để điều khi ển vùng ổn đị nh và xáo tr ộn ng ẫu nhiên để thốt kh ỏi cực tr ị đị a ph ươ ng. Các tham s ố được xác đị nh là các tham s ố ph ạt α, β , χγ , nh ư sau: 1. Số l ần l ặp l ại t ại m ỗi dốc 2. Số d ốc xu ống Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 46 3. Điều ki ện ổn đị nh để ch ấm d ứt s ớm t ại m ỗi l ần l ặp 4. Số n ơ-ron cho phép xoay đến khi k ết thúc m ỗi l ần l ặp 5. Ng ưỡng xác đị nh xác su ất m ột n ơ-ron m ột giá tr ị 1 khi đã xoay 6. Tổng s ố b ước ch ạy th ực hi ện t ừ kh ởi t ạo ng ẫu nhiên u và v Mạng n ơ-ron r ời r ạc cĩ th ời gian tr ễ c ố đị nh ở cơng th ức (24) t ại ∆t =1. 2.5. K ết lu ận ch ươ ng 2 - Ph ần đặ t v ấn đề đã th ể hi ện được phát bi ểu t ổng quát c ủa bài tốn. - Gi ới thi ệu tình hình gi ải quy ết bài tốn l ập th ời khĩa bi ểu và nh ững khĩ kh ăn trong vi ệc th ực hi ện. - Đã trình bày lời gi ải bài tốn b ằng cách s ử d ụng hai ánh xạ bài tốn th ời khĩa bi ểu theo mơ hình TT2 và TT3 lên m ạng Hopfield (xem [9]). Mơ hình đầu tiên là m ột m ở r ộng c ơ b ản c ủa cơng th ức Hopfield and Tank (1985), cĩ th ể ứng d ụng t ới t ất c ả các bài tốn t ối ưu t ổ h ợp. Mơ hình th ứ hai cĩ hi ệu qu ả h ơn mang ý t ưởng ánh x ạ b ộ ba (L ớp – giáo viên – phịng h ọc) trong su ốt h ọc k ỳ (Abramson, 1991) lên m ạng n ơ-ron Hopfield. Vi ệc dùng cơng th ức ánh x ạ b ộ ba (l ớp –giáo viên- phịng) TT3, đã ch ứng minh là cĩ hi ệu qu ả h ơn v ề s ố các n ơ-ron và tr ọng s ố c ần thi ết để mã hĩa cho bài tốn. Trong khi ch ất l ượng gi ải pháp t ươ ng t ự thu được cho c ả hai trình bày m ạng nơ-ron, s ự c ải thi ện v ề t ốc độ tính tốn cho TT3 làm cho nĩ các ưu tiên ti ếp cận m ạng n ơ-ron. Vi ệc cài đặt th ử nghi ệm nh ằm xác đị nh ảnh h ưởng c ủa s ửa đổi đã th ực hi ện trên m ạng nơ-ron, đĩ là s ự tác độ ng c ủa ng ẫu nhiên xoay vịng, ki ểm sốt thơng qua các ng ưỡng tham s ố. Do v ậy, thu ật gi ải m ạng nơ- ron Hopfield đã th ể hi ện được kh ả n ăng cho l ời gi ải ch ất l ượng t ốt với bài tốn th ời khĩa bi ểu m ở r ộng. - Gi ới thi ệu thu ật gi ải m ạng n ơ-ron Hopfield cải ti ến b ằng mã gi ả. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 47 CH ƯƠ NG 3: CÀI ĐẶT TH Ử NGHI ỆM 3.1 Thi ết k ế ch ươ ng trình ứng d ụng m ạng n ơ ron Hopfield trong vi ệc l ập th ời khĩa bi ểu cho tr ường đạ i h ọc. - Ch ươ ng trình Demo Với nh ững lý thuy ết đã nghiên c ứu, tác gi ả đã cài đặt mơ hình th ử nghi ệm b ằng ngơn ng ữ C#. Minh h ọa thu ật tốn n ơ-ron Hopfield s ẽ được cài đặt. Input: Kh ởi t ạo m ột m ảng 4 chi ều uij kl (ng ẫu nhiên) - Tính vij kl s ử d ụng ph ươ ng trình (23) > 1 ,nếu u ijkl 0 v= g( u ) = ijkl ijkl ≤ 0,nếu u ijkl 0 Trong đĩ g( u ij kl ) là hàm kích ho ạt. - c ập nh ập uij kl t ại th ời điểm (t+1) s ử d ụng ph ươ ng trình (24) u (t+1) = u (t) + ∆t( w * v+ I ) ij kl ij kl ∑ ijkl , i' jkl ' '' ijkl ijkl i' jkl ' '' u=w * v + I ijkl∑ ijkl , i' jkl ' '' ij kl ijkl i' jkl ' '' = α Trong đĩ Iijkl R ijk cho tr ước. - C ập nh ập vij kl t ại th ời điểm (t+1) s ử d ụng ph ươ ng trình (25) = + ∆ vijkl v ij kl v ij kl Trong đĩ Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 48 + ≥ = 1,nếu∑W'''' V '''' () t I 0 vàV ()0 t ijklijkl, ijkl ijkl ijkl ∆=− +≤ = V 1,nếu W'''' VtI '''' () 0 vàVt ()1 ijkl ∑ ijkl, i j k l i j k l ijkl ijkl 0, trongcáctrườnghợpkhác Output: vij kl Tín hi ệu ra vij kl là m ột ma tr ận cho l ời gi ải bài tốn l ập th ời khĩa bi ểu. Dưới đây là ch ươ ng trình cài đặt th ử nghi ệm theo thu ật gi ải m ạng n ơ-ron Hopfield. Giao di ện chính ch ươ ng trình Hình 3.1: Giao di ện ch ươ ng trình th ời khĩa bi ểu - Về giao di ện ( UI) bao g ồm nhi ều Form trong đĩ cĩ các form nh ập d ữ li ệu nh ư hình v ẽ: Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 49 Hình 3.2: Danh sách các form d ữ li ệu Hình 3.3: Minh h ọa tìm ki ếm d ữ li ệu theo l ớp Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 50 3.2 Chu ẩn b ị d ữ li ệu Để cài đặt ch ươ ng trình th ử nghi ệm ta c ần ph ải l ựa ch ọn d ữ li ệu đầ u vào đơ n gi ản và các tham s ố phù h ợp. Trong bài tốn này, tơi cho d ữ li ệu đầ u vào là 2 l ớp, 2 giáo viên, 4 phịng h ọc, 4 ti ết c ụ th ể và h ệ s ố cơng th ức là α =3, β= γ = χ =1. 3.3. K ết qu ả th ử nghi ệm - Nh ập tham s ố cơng th ức: Hình 3.4: Nh ập tham s ố cơng th ức cho bài tốn th ời khĩa bi ểu - X ếp th ời khĩa bi ểu Hình 3.5: Minh h ọa k ết qu ả sau khi x ếp th ời khĩa bi ểu Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 51 Ph ần m ềm Demo đã ch ạy ra k ết qu ả là l ịch th ời khĩa bi ểu, nh ưng đang cịn b ị xung độ t gi ữa l ớp - giáo viên - phịng h ọc. Qua đĩ, tơi th ấy r ằng cĩ th ể sử d ụng m ạng Hopfield để gi ải bài tốn l ập th ời khĩa bi ểu cho tr ường đạ i h ọc tuy v ậy cịn nhi ều các y ếu t ố ràng bu ộc và cần ph ải dành nhi ều th ời gian nghiên c ứu k ỹ để cho k ết qu ả t ối ưu. 3.4. Đánh giá k ết qu ả Vi ệc cài đặt ch ươ ng trình mơ ph ỏng h ệ th ống ứng d ụng m ạng n ơ-ron Hopfield x ếp l ịch th ời khĩa bi ểu ban đầ u cho k ết qu ả kh ả quan. Tuy nhiên, vi ệc s ử d ụng m ạng n ơ-ron Hopfield để gi ải bài tốn c ũng c ần được th ử nghi ệm nhi ều và so sánh v ới các thu ật gi ải siêu tìm ki ếm khác. Một h ạn ch ế trong lu ận v ăn này là khi ti ến hành cài đặt thu ật gi ải g ặp ph ải vơ cùng khĩ kh ăn do tính tr ừu t ượng trong thu ật tốn s ửa đổ i của bài tốn l ập th ời khĩa bi ểu. Và vi ệc so sánh gi ữa hai mơ hình TT2 và TT3 c ần ph ải cĩ nhi ều th ời gian và cơng s ức nghiên c ứu tìm tịi h ơn n ữa. Trong th ời gian làm lu ận v ăn, m ặc dù đã n ỗ l ực h ết s ức trong vi ệc nghiên c ứu tìm tịi trong đĩ cĩ các tài li ệu ti ếng anh liên quan và s ự giúp đỡ nhi ệt tình c ủa th ầy h ướng d ẫn và b ạn bè đồng nghi ệp. Song do th ời gian cĩ hạn và cịn nhi ều h ạn ch ế v ề m ặt kinh nghi ệm, ki ến th ức nên trong quá trình tìm hi ểu lu ận v ăn, khơng th ể tránh kh ỏi nh ững sai sĩt. Em mong r ằng s ẽ nh ận được nhi ều ý ki ến đĩng gĩp c ủa th ầy cơ và các b ạn để lu ận v ăn hồn thi ện hơn, và s ớm ứng d ụng vào th ực t ế. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 52 KẾT LU ẬN VÀ ĐỀ NGH Ị Kết qu ả đạ t được c ủa lu ận v ăn Trong lu ận v ăn “ Ứng d ụng m ạng n ơ-ron Hopfield gi ải bài tốn lập th ời khĩa bi ểu“ tơi đã hồn thành nh ững nhi ệm v ụ sau: 1. Đã hệ th ống cơ sở lý thuy ết c ủa m ạng n ơ-ron nhân t ạo, đặc bi ệt là mạng nơ-ron Hopfield. Nêu ph ươ ng pháp ánh x ạ m ạng n ơ-ron lên bài tốn t ối ưu, và gi ới thi ệu m ạng n ơ-ron Hopfield đối v ới bài tốn l ập th ời khĩa bi ểu. 2. Đã trình bày phát bi ểu bài tốn l ập th ời khĩa bi ểu và nh ững khĩ kh ăn trong vi ệc l ập th ời khĩa bi ểu cho tr ường đạ i h ọc. 3. Đã nghiên c ứu bài tốn l ập th ời khĩa bi ểu d ựa trên m ạng n ơ-ron Hopfield do tác gi ả De Verra (1985) đề xu ất và hi ểu rõ lý thuy ết bài tốn. 4. Đã cài đặt th ử nghi ệm thu ật gi ải m ạng n ơ-ron Hopfield, l ựa ch ọn m ột mơ hình cụ th ể TT2 trên máy tính, k ết qu ả đạ t được là ph ần m ềm x ếp th ời khĩa bi ểu. Các định h ướng nghiên c ứu ti ếp theo Để cho m ột th ời khĩa bi ểu t ốt nh ất th ỏa mãn nhi ều ràng bu ộc ph ụ thu ộc vào nhi ều y ếu t ố nh ư: v ề độ l ớn bài tốn đặt ra, vi ệc ch ọn l ựa các tham s ố cho ma tr ận tr ọng s ố là vơ cùng c ần thi ết. Vì v ậy hướng nghiên cứu ti ếp theo c ủa lu ận v ăn là tìm ra thu ật gi ải c ải ti ến và ph ươ ng pháp ch ọn l ựa tham s ố sao cho bài tốn l ập th ời khĩa bi ểu tìm được là t ối ưu. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 53 TÀI LI ỆU THAM KH ẢO Ti ếng Việt 1. Đặng Quang Á, M ột cách nhìn v ề vi ệc s ử d ụng m ạng Hopfield gi ải các bài tốn tho ả mãn ràng bu ộc và t ối ưu cĩ ràng bu ộc, Báo cáo t ại H ội th ảo qu ốc gia “M ột s ố v ấn đề ch ọn l ọc c ủa cơng ngh ệ thơng tin”, H ải phịng 6/2001. 2. Đặng Quang Á, Ứng d ụng c ủa mang n ơ ron trong tính tốn, Sách “H ệ m ờ, mạng n ơ ron và ứng d ụng”, Chủ biên: Bùi Cơng C ường, Nguy ễn Dỗn Ph ước, Nhà XBKH-KT, Hà n ội, 2001, 199-211. 3. Bùi V ăn Thanh, Bùi Vi ệt Hà, Ứng d ụng mơ hình bài tốn x ếp th ời khĩa bi ểu để phát tri ển ph ần m ềm x ếp th ời khĩa bi ểu cho tr ường đạ i h ọc, cao đẳ ng, Báo cáo nghiên c ứu, Vi ện CNTT, 2008. 4. Nguy ễn Th ị Thanh Huy ền, Nguy ễn H ồng H ạnh, V ũ Tuy ết Trinh, Tr ần Đình Khang. Gi ải thu ật di truy ền và bài tốn l ập th ời khĩa bi ểu. T ạp chí Khoa học và Cơng ngh ệ các tr ường Đạ i h ọc k ỹ thu ật, 6/2008. 5. KS. L ươ ng V ăn Khoa, TS. L ưu Tr ường V ăn, GS. Lê Ki ều M ạng, Mạng n ơ- ron nhân t ạo (ANNs) và gi ới thi ệu m ột s ố nghiên c ứu ứng d ụng trong qu ản lý dự án đầ u t ư xây d ựng, t ạp chí kinh t ế xây d ựng s ố 2/2006. Ti ếng Anh 6. Y. Takefuji, Neural Network Parallel Computing , Kluwer Acad. Publ., 1992. 7. Marco Paulo Carrasco and Margarida Vaz Pato, A Comparison of Discrete and Continuous Neural Network Approaches to Solve the Class/Teacher Timetabling Problem, CIO − Working Paper 4/2001, Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 54 8. Masri Ayob, Salwani Abdullah and Ariff Md Ab Malik, A Practical Examination Timetabling Problem at the Universiti Kebangsaan Malaysia, IJCSNS International Journal of Computer Science and Network Security , VOL.7 No.9, September 2007. 9. Kate A. Smitha, David Abramsonb, David Dukeb, Hopfield neural networks for timetabling: formulations, methods, and comparative results, Computers & Industrial Engineering 44 (2003) 283–305. 10. 11. 12. Salwani Abdullah, Heuristic approaches for university timetabling problems , The Scholl of Computer Science and Information Technology, June 2006 13. J. Hertz, A. Krogh, R. G. Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley, 1991. Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 55 PH Ụ L ỤC // Mã l ệnh chính chươ ng trình cài đặt th ử nghi ệm “ Ứng d ụng m ạng n ơ-ron Hopfield gi ải bài tốn th ời khĩa bi ểu” using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Hopfield.TT2 { public class Calculation { private int iCountI; private int iCountJ; private int iCountK; private int iCountL; private float fAlpha; private float fGamma; private float fBeta; private float fLama; private int iDescentNumber; private int iNeuralNumber; private float [,,,] arrU; private float [,,,] arrV; private float [,,,] arrI; private float [,,,] arrDelta; private float [,,,,,,,] arrW; private int [,] arrKroneckerDelta; private float [, , ] arrR; public Calculation( int i, int j, int k, int l, float alpha, float beta, float gamma, float lama, int neural, int descent) { CountI = i; CountJ = j; CountK = k; CountL = l; fAlpha = alpha; fBeta = beta; fGamma = gamma; fLama = lama; Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 56 iNeuralNumber = neural; iDescentNumber = descent; U = new float [CountI,CountJ,CountK,CountL]; V = new float [CountI, CountJ, CountK, CountL]; I = new float [CountI, CountJ, CountK, CountL]; W = new float [CountI, CountJ, CountK, CountL, CountI, CountJ, CountK, CountL]; arrDelta = new float [CountI, CountJ, CountK, CountL]; arrKroneckerDelta = new int [CountI + CountJ + CountK + CountL, CountI + CountJ + CountK + CountL]; R = new float [CountI, CountJ, CountK]; #region Private methods private void KhoiTaoKroneckerDelta() { for ( int i = 0; i < CountI + CountJ + CountK + CountL; i++) { for ( int j = 0; j < CountI + CountJ + CountK + CountL; j++) { if (i == j) { arrKroneckerDelta[i, j] = 1; } else { arrKroneckerDelta[i, j] = 0; } } } } private void KhoiTaoU() { Random r = new Random (); for ( int i=0;i<CountI;i++) { for ( int j=0;j<CountJ;j++) { for ( int k=0;k<CountK;k++) { for ( int l=0;l<CountL;l++) { arrU[i, j, k, l] = r.Next(2); Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 57 } } } } } private void ChuanHoaU() { for ( int i = 0; i =0) { arrU[i, j, k, l] = 1; } else { arrU[i, j, k, l] = 0; } } } } } } private void KhoiTaoV() { for ( int i = 0; i < CountI; i++) { for ( int j = 0; j < CountJ; j++) { for ( int k = 0; k < CountK; k++) { for ( int l = 0; l < CountL; l++) { arrV[i, j, k, l] = TinhG(i,j,k,l); } } } } } private void TinhI() { for ( int i = 0; i < CountI; i++) Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 58 { for ( int j = 0; j 0) { return 1; } return 0; } private float TinhW( int i, int j, int k, int l) { float fResult = 0; for ( int i1 = 0; i1 < CountI; i1++) { for ( int j1 = 0; j1 < CountJ; j1++) { for ( int k1 = 0; k1 < CountK; k1++) { for ( int l1 = 0; l1 < CountL; l1++) { arrW[i,j,k,l,i1,j1,k1,l1] = (- 1)*fAlpha*arrKroneckerDelta[i, i1]*arrKroneckerDelta[j, j1]*arrKroneckerDelta[k, k1] - fBeta*arrKroneckerDelta[i, i1]*(1 - arrKroneckerDelta[j, j1])*(1 - arrKroneckerDelta[k, k1])*arrKroneckerDelta[l, l1] - fLama*(1 - arrKroneckerDelta[i, i1])*arrKroneckerDelta[j, j1]*(1 - arrKroneckerDelta[k, k1])*arrKroneckerDelta[l, l1] - fGamma*(1 - arrKroneckerDelta[i, i1])*(1 - Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 59 arrKroneckerDelta[j, j1])*arrKroneckerDelta[k, k1]*arrKroneckerDelta[l, l1]; fResult += arrW[i, j, k, l, i1, j1, k1, l1]; } } } } return fResult; } private float TinhDeltaV( int i, int j, int k, int l) { float fTemp = 0; for ( int i1 = 0; i1 = 0 && arrV[i, j, k, l] == 0) { return 1; } if (fTemp + I[i, j, k, l] <= 0 && arrV[i, j, k, l] == 1) { return -1; } return 0; } #endregion public void TT2() { float fCondition = -1; KhoiTaoU(); KhoiTaoV(); TinhI(); Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 60 KhoiTaoKroneckerDelta(); for ( int m = 0; m < iDescentNumber; m++) { for ( int n = 0; n < iNeuralNumber;n++ ) { fCondition = 0; for ( int i = 0; i < CountI; i++) { for ( int j = 0; j < CountJ; j++) { for ( int k = 0; k < CountK; k++) { for ( int l = 0; l < CountL; l++) { arrU[i, j, k, l] = TinhW(i, j, k, l) * arrV[i, j, k, l] + arrI[i, j, k, l]; arrV[i, j, k, l] = TinhG(i, j, k, l); arrDelta[i, j, k, l] = TinhDeltaV(i, j, k, l); arrV[i, j, k, l] += arrDelta[i, j, k, l]; fCondition += arrDelta[i, j, k, l]; } } } } ChuanHoaU(); } } } } } Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên