ðẠ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
TOÁN LẬP THỜI KHÓA BIỂU
Chuyên ngành: Khoa học máy tính
TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Mã số: 60.48.01
THÁI NGUYÊN - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Công trình ñược hoà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 luận văn họp tại: Vào hồi...... giờ...... ngày....... tháng........ năm 2011.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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: …………………………….
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 http://www.lrc-tnu.edu.vn
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 toá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ề
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
luận văn của mình.
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 toá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 toán tối ưu................................................ 28
1.3.4. Mạng Hopfield với bài toá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 TOÁN LẬP THỜI
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
KHÓA BIỂU CHO TRƯỜNG ĐẠI HỌC...................................................... 33
iv
2.1 Bài toá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 toá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 toán thời khóa biểu.......... 38
2.3.1. Mạng nơ ron Hopfield................................................................... 38
2.3.2. Ánh xạ bài toán thời khóa biểu lên mạng nơ-ron Hopfield .......... 40
2.4. Thuật toán mạng nơ-ron Hopfield trong bài toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
PHỤ LỤC ........................................................................................................ 55
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 toán 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 http://www.lrc-tnu.edu.vn
Hình 3.5: Minh họa kết quả sau khi xếp thời khóa biểu ................................. 50
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 toán nơ-ron cho phép giải quyết tốt những
bài toá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
toán học giữa các biến. Ngoài ra phương pháp này còn cho phép tìm ra
nghiệm của nhưng bài toá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 toán lập thời khóa biểu đại học là một bài toá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 toá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 toá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 toá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 toá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 toán nơ-ron cho phép giải quyết tốt các bài toá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 toá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
toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
khá mới mẻ và chưa được ứng dụng rộng rãi ở nước ta. Trong nước cũng
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 toá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 toá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 toán xếp thời khóa biểu.
Chương 2: Trình bày phương pháp giải bài toá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 toán, đưa ra những nhận xét về hiệu quả của các mô hình bài toá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 toán lập thời khóa biểu, đánh giá về kết quả
đạt được.
Ngoà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 đề
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
tài.
CHƯƠNG I
3
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 toá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 hoá như thiết bị ngưỡng (giới hạn)
để thực hiện tính toá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
hoà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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Papert của MIT (Massachurehs Insritute of Technology) đã phát hiện ra và
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 toá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 toá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 toá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ị toà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, hoá 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 1010 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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
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 ngoà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 mm2) để 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 toà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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình vẽ (1.1) là một hình ảnh đơn giản hoá của một loại nơ-ron như vậy.
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 toá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 toán hay đơn vị xử lý thông tin
cơ sở cho hoạt động của một mạng nơ-ron.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Các thành phần cơ bản của một mô hình nơ-ron
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
jS được gán một trọng số
ijW tương ứng. Ta ước lượng tổng tín
tín hiệu vào
inet theo một số dạng sau:
hiệu đi vào nơ-ron
N
net
(i)Dạng tuyến tính:
= ∑
i
W s ij
j
= 1
j
(1.1)
N
net
(ii)Dạng toàn phương:
= ∑
i
W s ij
2 j
= 1
j
(2.2)
N
2
= -
r
)2
net
w
(iii)Dạng mặt cầu:
( -∑ s
ij
i
j
= 1
j
(
)
j
N= 1,
(3.3)
ijw
Trong đó: r và 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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
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 toà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
q
function). Đầu ra của hàm này giới hạn một trong hai giá trị:
neáu x
g x ( )
‡
<
q
neáu x
0,
1, =
(1.4)
ở đây q là ngưỡng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Đồ thị hàm bước nhị phân (Binary step function)
9
Dạng hàm này thường sử dụng trong mạng một lớp. Trong hình vẽ q đượ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
=
g x ( )
logistics, xác định như sau:
x
+
1 e l-
1
(1.5)
ở đó l là tham số độ dốc của hàm sigma. Bằng việc biến đổi tham số l ,
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à 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 toá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 toá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].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Đồ thị hàm sigmoid
10
4) Hàm sigmoid lưỡng cực (Bipolar sigmoid function (tan(sig))
x
=
g x ( )
x
+
e e
1 1
- - (1.6) -
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):
Vi
Wi1
Vj Wij Vi Ui= ∑ Vi=fi(Ui)
WiN
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
VN
11
N
=
+
U
i
VW j ij
i
∑
θ
Hình 1.2. Mô hình một nơ-ron
= 1 # i
j j
)
V =
(1.7)
i
( Uf i
i
(1.8)
iU : là tín hiệu vào tại nơ-ron i
iV : là tín hiệu ra tại nơ ron i
ijW : là trọng số liền kề từ nơ-ron j đến nơ-ron i
q
i : là ngưỡng (đầu vào ngoài) kích hoạt nơ-ron i.
if : là hàm kích hoạt của nơ-ron i
Trong đó:
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 toán học hay
mô hình tính toá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 toá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 ngoà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 toán, mạng nơ-
ron có thể giải quyết được các lớp bài toán nhất định, như: Bài toán người du
lịch, bài toán tô màu bản đồ, bài toán xếp loại, bài toán lập thời khóa biểu, bài
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
toán tìm kiếm, bài toán nhận dạng mẫu... Các bài toán phức tạp cao, không
12
xác định. Tuy nhiên, sự liên kết giữa một bài toá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 :
(cid:1) Là mô hình toán học dựa trên bản chất của nơ-ron. (cid:1) Bao gồm một số lượng rất lớn các nơ-ron liên kết với nhau. (cid:1) 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.
(cid:1) Tổ chức theo kiểu tập hợp mang lại cho mạng nơ-ron khả năng
tính toá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
q
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.
out i
‡
<
q
0 ,
1, =
neáu net i neáu net i
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(1.9)
13
jx∑
là tổng thông tin đầu vào của nơ-ron i. Với neti = wij
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
y2 x2
yn Xm
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
. Qua quá trình xử lý của
[ xx ,2,1
nx
]T
=
y
...,
ny
,2
[ yy ,1
mạng ta sẽ thu được một bộ tương ứng các giá trị đầu ra là
m
q
=
được xác định như sau :
y
i
,1
n
i
i
xw ij
j
i
j
= 1
= ∑ f
,
- (1.10)
Trong đó :
m : Số tín hiệu vào
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
n : Số tín hiệu ra
T
]T
W
,...,
w
14
i
in
i
[ = , ww i 1
2
if : Là hàm kích hoạt nơ-ron thứ i
q : Là ngưỡng của nơ-ron thứ i.
i
: là véc tơ trọng số 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
q > i
toán phân lớp. Một đối tượng sẽ được nơ-ron i phân vào lớp A nếu :
jx∑
Tổng thông tin đầu vào wij
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
toá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 toá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 Lớp ẩn Lớp ra x y
y x
y xm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình 1.4. Mạng truyền thẳng nhiều lớp
15
1.1.2.3.2. Mạng hồi quy (Recurrent Neutral Network)
X1
Y1
X2
Y2
Mạng hồi quy một lớp có nối ngược
. . .
. . .
. . .
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.
Y1
Y2
. . . . . . . . .
X1 X2 . . . 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
nơ-ron ghi nhớ giá trị đó.
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 toán thuộc lớp bài toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
làm hai loại: Học tham số và học cấu trúc.
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
=
h
=
=
tham số có thể được mô tả như sau:
rx
,
i
,1
, jN
,1
M
W ij
j
D (1.11)
trong đó:
ijW : là sự thay đổi trọng số liên kết từ nơ ron j đến nơ ron i.
jx : là tín hiệu vào nơ ron j.
D
r : là hằng số học.
h : là tốc độ học, nằm trong khoảng (0,1).
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
luật Delta cho mạng nhiều lớp. Đối với mạng truyền thẳng thường sử dụng
18
luật truyền ngược để chỉnh trọng với tín hiệu chỉ đạo từ bên ngoà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
=
h
=
=
quan trước và sau, nghĩa là:
W
,1
, jN
,1
M
ij
, ixy i j
D (1.12)
trong đó:
ijWD
:jx là tín hiệu vào nơ-ron j.
iy là tín hiệu ra của nơ-ron i.
h là tốc độ học, nằm trong khoảng (0,1).
là sự thay đổi trọng số liên kết từ nơ-ron j đến nơ-ron i.
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 ngoà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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
mạng nơ-ron có thể tăng lên rất nhiều lầ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 ngoà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 ngoà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. Ngoà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 toá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 toá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).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2. Mô hình hoá (modeling).
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 toá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 hoá
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
hoá 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 hoá, 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
những biến đổi nhỏ của tín hiệu ra.
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 hoá 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 hoá 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 hoá 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 hoá bằng cách cân xứng hoá 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 toàn không gian, khi đó số liệu có
thể được dùng ngay cho việc mô hình hoá. 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 toàn không gian, sau đó mới dùng làm
số liệu cho việc mô hình hoá.
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Trong phân loại, chúng ta muốn định danh các nhóm hoặc lớp mà đối tượng
22
thuộc vào, còn trong biến đổi, chúng ta quan tâm đến toà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 hoá 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 hoàn toà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 hoá 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 soá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 hoà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ả
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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
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 soá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 đoá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 khoá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 toàn.
- Trí tuệ nhân tạo: Gồm các hệ chuyên gia, ..
- Các hệ thống năng lượng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- Dự đoán: Dự đoán các trạng thái của hệ thống,..
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 toán thỏa mãn ràng buộc, bài toán lập thời khóa biểu cho trường
đại học, bài toán người đi du lịch, ..
- Giải các bài toán tối ưu: Vấn đề chính là tìm những thuật toán huấn
luyện mạng để góp phần tìm nghiệm cho nhiều lớp bài toán tối ưu toà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 toá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 toá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ố
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
tương ứng.
25
X1 Y1
Đầu vào Đầu ra Y2 X2
. . .
XN YM
ww =
Hình 1.7. Mô hình mạng Hopfield
ij
ji
Ký hiệu Wij là liên kết giữa hai nơ-ron i và j ( ), Vi là đầu ra
của nơ-ron i. Ta coi véc tơ (V1, V2, ... Vn) 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 Vj từ các nơ-ron khác và tín hiệu từ
=
+
U
I
i
VW ij
j
i
∑
bên ngoài (bias)
Tuỳ theo hàm kích hoạt fi mà nơ-ron i cho đầu ra là:
Vi(t+1) = fi(Vi(t)).
i Mạng đạt trạng thái cân bằng nếu Vi(t+1) = Vi(t) , "
n
n
n
=
)
-=
,
,...,
( VVEE 2
1
V n
VVW ij
i
j
VE i j
∑∑
∑-
Ta định nghĩa hàm năng lượng của mạng là:
1 2
(1.13)
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ộ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Trường hợp mạng nhận các giá trị nhị phân {0, 1}:
26
f Hàm kích hoạt được xác định như sau: fi ”
net
)
f net (
‡
1, neáu 0 = 0, neáu khaù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
0
= ( ) 0
+ ‡ I i
I
1,neáu
0
D = - V i
i
vaø V t i = vaø V t ( ) 1 i
thái của mạng Vi(t+1) = Vi(t) +D Vi trong đó D Vi được cho bởi công thức (quy tắc)
∑ W V t ( ) ij j ∑ + £ W V t ( ) ij j trong caùctröôøng hôïp khaùc
0,
1, neáu
,=
ni
i
(1.15)
). Khi đó với quy tắc chuyển trạng thái như Định lý: Giả sử Wii =0 (
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à
= ( tEE
)1
)( tE
-= (
I
)
V
)( tVW kj
j
k
k
∑
j
D - - D (1.16)
Vì thế theo công thức (1.14) ta luôn có D 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hopfield rời rạc được sử dụng cho các bài toán tối ưu {0, 1}
27
Một mở rộng của mạng nhị phân là mạng lượng tử hoá. Đâ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 toá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
i
+
I
= ∑
VW ij
j
i
phương trình động học
dU dt
j
V =
)
i
Uf ( i
i
(1.17)
trong đó fi là hàm kích hoạt.
Ở đây ta cũng giả thiết Wij= Wji và Wii =0. Dễ thấy rằng nếu hàm năng lượng
được cho bởi (1.12) thì :
i
-=
¶
dU dt
i
E V Sự hội tụ của mạng Hopfield liên tục cho bởi định lý sau:
¶
i
n= 1,
0
dE dt
£ ) là các hàm khả vi và không giảm thì Định lý: nếu fi(Ui) (
Chứng minh: Ta có vì theo giả thiết các hàm fi(Ui) là không giảm nếu
0
0
dV i dU
dE dt
i
2
‡ £ , do đó ,
i
=
-=
.
∑
¶ ¶
dE dt
dV i dU
dU dt
dV i dU
E V i
i
E ∑ V i
i
i
i
¶ ¶
l
=
=
=
+
)
V
Sigmoid
( U
1(
tanh(
U
))
i
i
i
l
Với tư cách là hàm kích hoạt người ta thường chọn hàm Sigmoid:
U
i
+
1 2
2
1
1 e
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- l trong đó >0 là
28
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 -5
-4
-3
-2
-1
0
1
2
3
4
5
0 -5
-4
-3
-2
-1
0
1
2
3
4
5
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 l xem hình vẽ
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 Vi bằng 0 hoặc 1. Chính vì vậy mạng Hopfield được
sử dụng cho các bài toá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 toán tối ưu {0, 1}. Nếu cần giải
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
bài toá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 (l x).
Đồ thị hàm Hàm y=tanh(x)
1.3.3. Mạng Hopfield với bài toán tối ưu
Sau công trình của Hopfield và Tank mạng Hopfield đã được sử dụng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
nhiều vào việc giải bài toán tối ưu tổ hợp. Ta đã biết mạng Hopfield sẽ đạt tới
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 toá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 toán tối ưu tổ hợp, đặc biệt là đối với một số bài toán thuộc lớp bài toán
NP-đầy đủ như: bài toán thời khóa biểu, bài toá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 toá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 toá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ụ toà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ụ toà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 toán tối ưu như sau (ánh xạ bài toá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 toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
nhất của bài toán cần ánh xạ.
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 toá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 toán lập thời khóa biểu
Bài toá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 hoà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 toán thời khóa biểu đơn giản nhất là mô hình lớp –
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
giáo viên được trình bày bởi De Werra (1985) như sau (xem [9]):
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
ijR ).
một ma trận kích thước C · T thỏa R = (
ijR là số đơn vị thời gian mà giáo viên j phải dạy lớp i trong suốt
Trong đó,
thời gian biểu quy định.
j
i
k
x
Chúng ta định nghĩa một biến logic ijkx như sau:
k
ij
1, neáu lôùp vaø giaùo vieân daïy trong thôøi gian = 0,tröôøng hôïp khaùc
(1)
ijkx =1 thể hiện một giáo viên j có mặt để dạy lớp i tại
Theo công thức (1) thì
ijkx = 0 trong trường hợp còn lại, ví dụ như không có giáo viên j,
phòng k ; và
dạy lớp i, vào thời gian k.
P
Mô hình Lớp – giáo viên (TT1)
(
TjCi ,
)
=∑ x
ijk
R ij
= 1
k
T
˛ ˛ " (2)
(1
kCi
,
)
ijk
£∑ x
= 1
j
C
(cid:213) ˛ ˛ " (3)
(1
kTj
,
)
ijk
£∑ x
= 1
i
(cid:213) ˛ ˛ " (4)
i C j T k
;
;
)
ijkx = 0 hoặc 1 ( "
˛ ˛ ˛ (5) (cid:213)
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 toàn vẹn cho lời giải.
=
ˆ G C T R (
,
,
)
Trong mô hình TT1, quy về bài toán liên quan đến đồ thị hai phía
và sử dụng kỹ thuật tô màu các cạnh để tìm xung đột trong phân
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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
32
tj liên kết bởi các cạnh song song Rij. Bài toá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
toá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 toá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 hoàn toàn không phù hợp cho lời giải khi mở rộng bài toá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 toá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 ngoà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 toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
phép mô phỏng các hệ thống tương đối phức tạp trong thực tế
CHƯƠNG II: ỨNG DỤNG MẠNG NƠ-RON HOPFIELD
33
TRONG BÀI TOÁN LẬP THỜI KHÓA BIỂU CHO TRƯỜNG
ĐẠI HỌC
2.1 Bài toá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 toá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à
ijkR ˛ C · T ·
ijkR là số
các giáo viên. Ta xây dựng một ma trận V, trong đó,
đơ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.
ijklx như sau:
klx
ij
Chúng ta định nghĩa một biến logic
0,
1, =
(6) nếu lớp i và giáo viên j dạy tại phòng k trong thời gian l 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
ijklx =1 thể hiện một giáo viên j có mặt để dạy lớp i tại
Theo công thức (6) thì
ijklx = 0 trong các trường hợp còn lại.
phòng k trong thời gian l; và
Bài toán lập thời khóa biểu đáp ứng các ràng buộc theo mô hình TT2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(Timetable 2) được phát biểu như sau:
34
Mô hình Lớp – giáo viên – phòng học (TT2)
ijklx thỏa mãn các ràng buộc sau (xem [9]):
P
Cần tìm các biến logic
R
(
VkTjCi
,
,
)
ijkl
ijk
=∑ x
= 1
l
T
V
˛ ˛ ˛ " (7)
1 (
i C l ,
)
∑∑
x ijkl
£ " ˛ " ˛ (cid:213)
= 1
= 1
j
k
C
V
(8)
1 (
j T l ,
)
∑∑
x ijkl
= 1
= 1
i
k
C
T
£ " ˛ ˛ (cid:213) (9)
1 (
k V l ,
)
∑∑
x ijkl
i
j
= 1
= 1
(10) £ " ˛ ˛ (cid:213)
i C j T k V l ;
;
;
)
" ˛ ˛ ˛ ˛ (cid:213) (11) xijkl = 0 hoặc 1 (
ijkR thể hiện mối quan hệ giữa lớp i – giáo
Trong đó, công thức (7) ở vế phải
ijklx để nói tổng
viên j – phòng học k, vế trái của công thức ta sử dụng biến
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
điểm.
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.
ijklx chỉ được phép nhận một
• Công thức (11) thể hiện giá trị biến logic
trong hai giá trị 0 hoặc 1.
Với mục đích xây dựng mô hình bài toá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 toá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 toàn bộ
V
C
T
t
=
ijkR
T, tổng số bộ ba được xác định bởi:
∑∑∑
= 1
i
= 1
j
= 1
k
(12)
Sử dụng biến Boolean xtp như sau:
=
tpx
(13)
,1 ,0
ˆ
,
ˆ ,C T V :
nếu bộ ba t = (i, j, k) được gán đợt P nếu khác
=
ˆ itC
Định nghĩa các ma trận ˆ
,1 ,0
nếu lớp i thuộc bộ ba t=(i,j,k) nếu khác
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(14)
(15)
=
ˆ jtT
nếu giáo viên j thuộc bộ ba t=(i,j,k) nếu khác
,1 ,0
(16)
=
ˆ ktV
nếu phòng học k thuộc bộ ba t=(i,j,k) nếu khác
,1 ,0
Ma trận x định rõ một lời giải đúng cho bài toán thời khóa biểu nếu
thỏa mãn các ràng buộc (TT3):
P
t
36
(1
t
)
tp
=∑ x
(17)
p
= 1 t
˛ "
1 (
i C p
,
)
(18)
£ " ˛ ˛ (cid:213)
∑
ˆ x C tp it
= 1
t
t
(19)
(1
pTj
,
)
˛ ˛ " £ (cid:213)
∑
ˆ Tx tp
jt
= 1
t
t
(20)
)
(1
pVk
,
˛ ˛ " £ (cid:213)
∑
ˆ Vx tp kt
= 1
t
=
t
(21)
{ } (,1,0
t
,
p
)
xtp
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
P ˛ ˛ "
so với TT2, nhằm giảm chiều bài toá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
Pt ·
.
kích thước
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
đảm tính toà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
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 toá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 toán, .. sẽ là những khó khăn thực sự khi tìm lời giải bài toán lập thời
khóa biểu.
Việc bài toá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 toán của chương trình.
2.2. Tình hình giải quyết bài toán lập thời khóa biểu
Thời khóa biểu là một dạng bài toán kinh điển trong hoạt động nghiên
cứu về lập lịch nói chung, do bài toá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 toán phân công công việc phức tạp, thời khóa biểu là bài toá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 toá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
toá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 toá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 toán siêu tìm kiếm
(metaheuristics) khác như mô phỏng luyện kim (Annealing) và tìm kiếm tabu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
về lời giải chất lượng và thời gian tính toán qua kiểm tra.
38
2.3. Xây dựng mô hình mạng Hopfield cho bài toá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ụ toán học có
thể được sử dụng để giải các bài toá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 toá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 toá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(ui). Hàm kích hoạt này độc lập trên mạng Hopfield rời rạc
i
=
=
+
hoặc liên tục. Có dạng:
g u (
)
(1 tanh(
))
v i
i
u l
1 2
(22)
Công thức trên sử dụng cho mạng Hopfield liên tục, trong đó l là biến xác
định độ dốc của hàm kích hoạt g(ui).
Đố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
>
0
rời rạc:
=
v i
0, neáu
0
1 , neáu =
u i u i
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(23) g u ) ( i £
39
N
+ D
t
I
+ = 1)
∑
u t ( i
u t ( ) i
+ w v j ij
i
Các nơ-ron tự học (tuần tự hoặc song song) theo đúng luật sau:
j
= 1
(24)
+ = 1)
)
v t ( i
g u ( i
(25)
( trong ∆t là thời gian trễ cố định), và khi thực hiện mạng nơ-ron sẽ hội tụ về
N
N
N
= -
cực tiểu địa phương với hàm năng lượng theo thời gian:
E
∑∑
∑
W v v ij
i
j
I v i i
1 2
i
j
i
= 1
= 1
= 1
- (26)
Được cung cấp bởi trọng số đối xứng Wij = Wji. 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 toá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 toá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 toá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 toá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
toá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 toá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,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
có thể dịch đến lời giải cực tiểu địa phương của bài toán tối ưu, cung cấp tham
40
số mạng (trọng số và đầu vào bias) đã được lựa chọn thích hợp cho bài toá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 toán tối ưu đã được giảm đến mức tối thiểu. Trong khi
các ràng buộc bài toá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, Ii mỗi nơ-ron i, hệ số vi của hàm năng lượng.
Mạng được cài đặt ban đầu mức kích hoạt vi 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
N
+
-=
minh liên quan thể hiện:
I
v
0
E
i
j
i
vW ij
∑
= 1
j
N
£ D D
0
0
+
I
∑
W v ij
i
j
D £
vaø
0
0
0
j
= 1
< D < u 0 = i u i
vaø v i v i
‡ D ‡ D ‡
Bởi nếu 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 toán thời khóa biểu lên mạng nơ-ron Hopfield
Để ánh xạ bài toán tối ưu lên mạng nơ-ron Hopfield, chúng ta cần đưa
C
T
V
P
C
T
V
P
T
V
a
b
=
ra các trọng số và ràng buộc của bài toán. Hàm năng lượng biểu diễn theo TT2:
E
x
∑∑∑ ∑
∑∑∑∑∑∑
ijkl
R ij
x x ijkl
+ ' ' ij k l
'
'
2
2
i
j
k
l
i
j
k
l
= 1
= 1
= 1
= 1
= 1
= 1
= 1
= 1
2 +
'
-
j j
= = k 1 1 ' j k k
C
C
T
V
P C
V
T
V
P C
T
c
g +
∑∑∑∑∑∑
∑∑∑∑∑
∑
x x ijkl
x x ijkl
' ' i jk l
' ' i j kl
'
'
'
'
2
2
i
j
k
l
j
k
l
i= 1
= 1
= 1
= 1
= 1
= 1
= 1
= 1
'
'
'
„ „ (27)
i i
= = k 1 1 ' i k k
i i
= 1 i
j j
= 1 j
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
„ „ „ „
41
Trong đó a,b, c, g 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 i ' ' i j k l
xây dựng ma kết nối tất cả các nơ-ron vijkl tới tất cả các nơ-ron khác
trận bốn chiều đầu ra bias.
C
T
V
P
T
V
P
P
C
T
V
Hàm năng lượng rút ra từ mạng Hopfield là:
-=
'
'
E
W
vv ijkl
vI ijkl
ijkl
∑∑∑∑∑∑∑
∑∑∑∑
ijkl
' ' ' lkji
' ' ' lkji ,
'
'
'
1 2
i
j
k
l
i
j
k
l
= 1
= 1
= 1
= 1
= 1
= 1
= 1
= 1
j
k
l
= 1
= 1
= 1
(28) -
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
'
'
= -
bd
d
d
d
d
d
(28) cho hai hàm tương đương sau.
(1
c )(1
)
(1
)
(1
)
'
'
'
'
'
'
'
'
'
kk
jj
ii
d ' jj
d kk
ll
ii
jj
kk
ll
(1
d )(1
'
'
'
ad d d ' ii d d ) ' jj
ii
kk
ll
a=
I
- - - - - - (29) Thiết lập ma trận trọng của TT2: W i ' ijkl i j k l , d g - - -
ijkl
R ijk
'
s
y
(30)
s =1 nếu
y= và bằng không trong
'yy
'yy
là hàm Kronecker – Delta , ở đây
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
trường hợp khác.
'
=
i
d
'
42
ii
'
0, ngöôïc laïi i
i
= 1, neáu i
C
T
V
a
R
2 ijk
Ta có: „
∑∑∑
2
i
j
k
= 1
= 1
= 1
Một thành phần hằng số được thêm vào là
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à toà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
t
t
t
t
t
P
C
P
T
P
a
b
ˆ
=
2 +
xây dựng như sau:
E
1
'
'
∑∑∑∑
∑∑∑∑
x tp
c ˆ + x C x C tp it it
' t p
ˆ ˆ x T x T jt tp jt
' t p
'
'
2
2
2
= 1
= 1
p
t
= 1
i
= 1
p
= 1
t
= 1
j
= 1
p
= 1
t
∑ ∑
'
'
-
t t
= 1 t
t t
= 1 t
t
t
V
P
g
+
'
∑∑∑∑
ˆ ˆ x V x V tp kt ' t p kt
'
2
= 1
= 1
= 1
k
p
t
'
„ „ (31)
t t
= 1 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 toán tối ưu lên mạng nơ-ron Hopfield, lời giải ma trận x
W
'
'
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
tp t p , và tpI .
,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
mạng Hopfield sẽ là một hàm của tpv ,
43
C
T
= -
ad
b
Thiết lập ma trận trọng số theo TT3:
W
d d (1
)
(1
)
'
'
'
'
'
'
'
'
∑
∑
' tp t p ,
tt
tt
pp
ˆ ˆ c C C it it
tt
pp
ˆ ˆ T T jt jt
d d
= 1
= 1
i
j
(32)
V
g
- - - -
(1
)
'
'
'
∑
d d tt
pp
ˆ ˆ V V kt kt
= 1
k
a=
(33)
tpI
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 toán thời khóa biểu mở rộng.
- -
2.4. Thuật toán mạng nơ-ron Hopfield trong bài toán lập thời khóa biểu
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)
cho trường Đại học
For i= 1 to descent
For j=1 to lặp
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 =
D∑ v k
k
= 1
Nếu tiêu chuẩn ổn định đã phù hợp, thoá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 http://www.lrc-tnu.edu.vn
For k=1 to N
44
Chọn một nơ-ron ngẫu nhiên, và xoay tới ngưỡng
1
0;
0
0
u k
> neáu u k
u k
< neáu u k
fi fi Chuẩn hóa u ( )
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 toá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
a b cg ,
,
,
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 a quá lớn so với ba số hạng còn lại, lời giải bài toá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 a 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ị toà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 toá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 toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
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à
45
một lần cập nhật hoàn toà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 soá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
N
phương pháp được gọi là ổn định, đếm số thay đổi trạng thái của nơ-ron trong
D∑ hoặc vD
v k
k
= 1
. Nếu trạng thái ổn định đo lường này dưới giá trị một lần lặp
đượ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
a b cg ,
,
,
xuống, dùng để điều khiển vùng ổn định và xáo trộn ngẫu nhiên để thoá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2. Số dốc xuống
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
D =1. t
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
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 toán.
- Giới thiệu tình hình giải quyết bài toá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 toán bằng cách sử dụng hai ánh xạ bài toá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 toá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 toá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 toá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 soá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
toán thời khóa biểu mở rộng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- Giới thiệu thuật giải mạng nơ-ron Hopfield cải tiến bằng mã giả.
CHƯƠNG 3:
47
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 toán nơ-ron Hopfield sẽ được cài đặt.
Input:
ijklu (ngẫu nhiên)
Khởi tạo một mảng 4 chiều
ijklv
>
neáu u
0
ijkl
=
g u (
)
v ijkl
ijkl
sử dụng phương trình (23) - Tính
neáu u
0,
0
ijkl
1 , =
£
)kl
g u ij(
Trong đó là hàm kích hoạt.
ijklu tại thời điểm (t+1) sử dụng phương trình (24)
I+
w
- cập nhập
'
∑
v * kl ij
ijkl
ijklu (t+1) = ijklu (t) + ∆t(
' ' ' kl i j k l
,
ij
'
' ' ' i j k l
=
+
I
w
*
'
∑
kl
kl
u ij
v ij
ijkl
' ' ' kl i j k l
,
ij
'
' ' ' i j k l
a=
I
)
R cho trước.
ijkl
ijk
Trong đó
=
+ D
kl
kl
kl
v ij
v ij
v ij
tại thời điểm (t+1) sử dụng phương trình (25) - Cập nhập ijklv
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Trong đó
+
48
W
V
I
t ( )
= ( ) 0
0
'
'
'
ijkl
‡
V
' ' ijkl i j k l , V
I
1,neáu
' ' ' i j k l + t ( )
0
( ) 1
'
'
'
∑ ∑ W
= - ijkl
ijkl
vaø V t ijkl = vaø V t ijkl
' ' ' i j k l
0,
' ' ijkl i j k l , trong caùctröôøng hôïp khaùc
1, neáu
D £
Output: ijklv
là một ma trận cho lời giải bài toán lập thời khóa biểu. Tín hiệu ra ijklv
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- 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ẽ:
49
Hình 3.2: Danh sách các form dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình 3.3: Minh họa tìm kiếm dữ liệu theo lớp
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 toán này, tôi cho dữ liệu đầu
a =3, b
c= = =1. g
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.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 toán thời khóa biểu
- 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 http://www.lrc-tnu.edu.vn
Hình 3.5: Minh họa kết quả sau khi xếp thời khóa biểu
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 toá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 toá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 toán sửa đổi của bài
toá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 hoàn thiện
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
hơn, và sớm ứng dụng vào thực tế.
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 toán lập thời
khóa biểu“ tôi đã hoà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 toán tối ưu,
và giới thiệu mạng nơ-ron Hopfield đối với bài toán lập thời khóa biểu.
2. Đã trình bày phát biểu bài toá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 toá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 toá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 toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
tham số sao cho bài toán lập thời khóa biểu tìm được là tối ưu.
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
toá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 toán, Sách “Hệ mờ,
mạng nơ ron và ứng dụng”, Chủ biên: Bùi Công Cường, Nguyễn Doã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 toá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 toá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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Timetabling Problem, CIO − Working Paper 4/2001,
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. http://www.grupet.at/en/downloads/demoversion/demoversion.php
11. http://www.mimosasoftware.com/company2.html
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Computation, Addison-Wesley, 1991.
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
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 http://www.lrc-tnu.edu.vn
Hopfield giải bài toán thời khóa biểu”
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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 56 }
}
}
}
}
private void ChuanHoaU()
{
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++)
{
if (arrU[i, j, k, l] >=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 http://www.lrc-tnu.edu.vn 57 {
for (int j = 0; j < CountJ; j++)
{
for (int k = 0; k < CountK; k++)
{
for (int l = 0; l < CountL; l++)
{
arrI[i, j, k, l] = arrR[i, j,
k]*fAlpha;
}
}
}
}
}
private int TinhG(int i, int j, int k, int l)
{
if (arrU[i,j,k,l]>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 http://www.lrc-tnu.edu.vn 58 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 < CountI; i1++)
{
for (int j1 = 0; j1 < CountJ; j1++)
{
for (int k1 = 0; k1 < CountK; k1++)
{
for (int l1 = 0; l1 < CountL; l1++)
{
fTemp += arrW[i, j, k, l, i1, j1,
k1, l1]*V[i1, j1, k1, l1] ;
}
}
}
}
if (fTemp + I[i, j, k, l] >= 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 http://www.lrc-tnu.edu.vn 59 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 http://www.lrc-tnu.edu.vn 60
