Ứng dụng mạng nơron hopfield giải bài toán thời khóa biểu

ðẠI HỌC THÁI NGUYÊN

TRƯỜNG ðẠI HỌC CNTT&TT

HÀ TUẤN VIỆT

ỨNG DỤNG MẠNG NƠ RON HOPFIELD GIẢI BÀI

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.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.

Có thể tìm hiểu luận văn tại trung tâm học liệu ðại học Thái Nguyên

Và thư viện Trường/Khoa: …………………………….

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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ề

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

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

KHÓA BIỂU CHO TRƯỜNG ĐẠI HỌC...................................................... 33

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

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

PHỤ LỤC........................................................................................................ 55

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