ðẠ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
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 http://www.lrc-tnu.edu.vnNgườ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. 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
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ề
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 http://www.lrc-tnu.edu.vn
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
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
Đồ 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
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 http://www.lrc-tnu.edu.vn
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 đề
tài.
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 http://www.lrc-tnu.edu.vn4
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.
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.
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn6Hì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
i ij j
j
net W s
=
=
∑
(1.1)
(ii)Dạng toàn phương:
2
1
N
i ij j
j
net W s
=
=
∑
(2.2)
(iii)Dạng mặt cầu:
( )
2
2
ij
1
w
N
i j
j
net s
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
function). Đầu ra của hàm này giới hạn một trong hai giá trị:
1,
( )
0,
neáu x
g x
neáu x
θ
θ
≥
=
<
(1.4)
λ
−
=
+
(1.5)
ở đó
λ
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 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]. Đồ thị hàm sigmoid
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ú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
=f
i
(U
i
)
U
i
= ∑
V
i
V
i
W
i1
1
θ
(1.7) (
)
iii
UfV
=
(1.8)
Trong đó:
i
U
: là tín hiệu vào tại nơ-ron i
i
V
: là tín hiệu ra tại nơ ron i
ij
W
: là trọng số liền kề từ nơ-ron j đến nơ-ron i
θ
i
: là ngưỡng (đầu vào ngoài) kích hoạt nơ-ron i.
i
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,
0,
i
i
i
neáu net
out
neáu net
θ
θ
≥
=
<
Với mỗi giá trị đầu vào. . 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à
được xác định như sau :
Trong đó :
m : Số tín hiệu vào
n : Số tín hiệu ra
y
1
y
n
y
2
X
m
x
1
x
2
[
]
T
n
yyyy ,
,
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.vn14
[
]
T
inii
T
i
wwwW , ,,
21
=
: là véc tơ trọng số của nơ-ron thứ i.
i
f
: 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
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 :
Tổng thông tin đầu vào
w
ij j
x
m
x
x
Lớp vào
Lớp ra
Lớp ẩ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.vn15
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
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.
Hình 1.6. Mạng nhiều lớp có nối
2
Y
. . . . . .
X
1
X
2
X
. . . . . .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn16
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
: 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
MjNirxW
jij
,1,,1, ===∆
η
(1.11)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn18
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.
MjNixyW
jiij
,1,,1, ===∆
η
(1.12)
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
Copyright: Tài liệu đại học ©