Ứng dụng mạng nơ-ron giải một số bài toán về đồ thị

i

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

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

HÀ DUYÊN HÙNG

ỨNG DỤNG MẠNG NƠ-RON

GIẢI MỘT SỐ BÀI TOÁN VỀ ĐỒ THỊ

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN, NĂM 2011

ii

LỜI CẢM ƠN

Xin chân thành cảm ơn Thầy PGS, TS. Đặng Quang Á đã tận tình chỉ

bảo, hướng dẫn tôi trong suốt thời gian học tập và làm luận văn.

Em chân thành biết ơn đế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 Trường Đại Học CNTT&TT- ĐH Thái Nguyên đã

tạo điều kiện tốt cho tôi trong hai năm học vừa qua.

Xin cám ơn đế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 qủa như ngày

ngày hôm nay.

THÁI NGUYÊN 11/2011

Người viết luận văn

Hà Duyên Hùng

iii

LỜI CAM ĐOAN

Tôi xin cam đoan đề tài khoa học “Ứng dụng mạng nơ-ron giải một số

bài toán về đồ thị” là công trình nghiên cứu của bản thân tôi. Các kết quả

nghiên cứu nêu trong luận văn này là trung thực. Tôi xin chịu trách nhiệm về

luận văn của mình.

iv

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 hình vẽ, ký hiệu, chữ viết tắt.....................................................v

MỞ ĐẦU........................................................................................................-1-

Chương 1. GIỚI THIỆU SƠ LƯỢC 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................................................................-14-

1.2.1. Các lĩnh vực ứng dụng của mạng nơ-ron....................................-14-

1.2.2. Ưu và nhược điểm của mạng nơ-ron..........................................-14-

1.3. Mạng Hopfield.................................................................................-15-

1.3.1. Mạng Hopfield rời rạc................................................................-16-

1.3.2. Mạng Hopfield liên tục:..............................................................-18-

1.3.3. Ánh xạ các bài toán tối ưu tổ hợp lên mạng nơ-ron...................-19-

1.3.4. Mạng Hopfield với bài toán NP-C..............................................-22-

Chương 2. ỨNG DỤNG MẠNG NƠ-RON HOPIELD TRONG BÀI TOÁN

SỐ CẠNH CẮT NHAU CỦA ĐỒ THỊ TRÒN..............................-29-

2.1. Bài toán số cạnh cắt nhau của đồ thị tròn.............................................................-29-

v

2.2. Mạng nơ-ron Hopfield với bài toán số cạnh cắt nhau của đồ thị tròn….….....-31-

Chương 3. CÀI ĐẶT THUẬT TOÁN VÀ THỬ NGHIỆM....................................-43-

3.1 Thiết kế chương trình ứng dụng mạng nơ-ron trong việc giải quyết bài toán số

cạnh cắt nhau của đồ thị tròn..........................................................................................-43-

3.2. Chương trình và kết quả thử nghiệm.................................................-44-

3.3. Đánh giá kết quả...............................................................................-53-

KẾT LUẬN VÀ ĐỀ NGHỊ……………………………………………...……..-54-

TÀI LIỆU THAM KHẢO............................................................................................-55-

PHỤ LỤC . …………………………...………………………………………..-57-

v

DANH MỤC CÁC HÌNH

Hình 1.1. Mô hình nơ-ron sinh học 5

Hình 1.2. Mô hình một nơ-ron 7

Hình 1.3. Mạng truyền thẳng một lớp 9

Hình 1.4. Mạng truyền thẳng nhiều lớp 10

Hình 1.5. Mạng một lớp có nối ngược 10

Hình 1.6. Mạng nhiều lớp có nối ngược 11

Hình 1.7. Mô hình mạng Hopfield 16

Hình 1.8. Ánh xạ bài toán lên mạng nơ-ron 21

Hình 1.9. Đồ thị chưa phẳng 24

Hình 1.10. Đồ thị phẳng 24

Hình 1.11. Đồ thị phẳng 24

Hình 1.12. Biểu diễn đồ thị trên một hàng 25

Hình 1.13. Mô hình đồ thị của bài toán 27

Hình 2.1. Biểu diễn đồ thị trong Thí dụ 2.1.. 30

Hình 2.2. Biểu diễn đồ thị có một điểm cắt nhau. 30

Hình 2.3. Mạng nơ-ron Hopfield. 31

Hình 2.4. Mạng nơ-ron giải bài toán đồ thị tròn. 33

Hình 2.5. Đồ thị nối bởi các đường thẳng. 34

Hình 3.3. Biểu diễn lưu đồ thuật toán. 45

Hình 3.4 (a). Biểu diễn đồ thị trong thí dụ hình 3.4 (a). 46

Hình 3.4 (b). Biểu diễn đồ thị có một điểm cắt nhau. 47

Hình 3.5 (a). Biểu diễn đồ thị trong thí dụ hình 3.5 (a). 49

Hình 3.5 (b). Biểu diễn đồ thị có mười điểm cắt nhau. 50

Hình 3.6 (a). Biểu diễn đồ thị trong thí dụ hình 3.6 (a). 51

Hình 3.6 (b). Biểu diễn đồ thị có tám điểm cắt nhau. 52

- 1 -

MỞ ĐẦU

Trong thực tế có nhiều bài toán phức tạp thuộc lớp các bài toán thoả

mãn ràng buộc và bài toán tối ưu tổ hợp có ràng buộc. Đây là các bài toán

thuộc loại NP-C. Đã có nhiều phương pháp để giải quyết các bài toán đó.

Trong số các bài toán điển hình phải kể đến bài toán tìm đường đi ngắn nhất,

bài toán tô màu bản đồ, bài toán xếp hậu, bài toán số cạnh cắt nhau của đồ thị

tròn, bài toán người bán hàng rong,... Các giải thuật heuristic được đề xuất

nói chung thường phức tạp và có những hạn chế nhất định về độ chính xác.

Trong khoảng hơn hai chục năm trở lại đây một hướng nghiên cứu mới là

mạng nơ-ron nhân tạo đã được phát triển và có nhiều ứng dụng trong các lĩnh

vực của công nghệ thông tin. Đặc biệt mạng Hopfield rất thích hợp cho các

bài toán trên.

Nhận thức được vấn đề đó và có sự gợi ý và định hướng của PGS, TS.

Đặng Quang Á em đã mạnh dạn nghiên cứu đề tài " Ứng dụng mạng nơ-ron

giải một số bài toán về đồ thị ". Nội dung cơ bản của luận văn tốt nghiệp gồm

có ba chương:

Chương một trình bày tổng quan về cơ sở của mạng nơ-ron nhân tạo và

các phương pháp giải bài toán NP-C, bao gồm: Giới thiệu mạng nơ-ron sinh

học, mô hình mạng nơ-ron nhân tạo, phạm vi ứng dụng của mạng nơ-ron

Hopfield, ưu và nhược điểm của mạng nơ-ron, phương pháp ánh xạ một bài

toán lên mạng nơ-ron, mạng nơ-ron với một số bài toán NP-C, khái niệm về

các bài toán lớp NP-C và NP-hard, khái quát về các phương pháp giải.

Chương hai trình bày về ứng dụng mạng nơ-ron Hopfield trong bài toán

số cạnh cắt nhau của đồ thị tròn. Đây là bài toán có nhiều ý nghĩa trong thực

tiễn như thiết kế mạch điện tử, định tuyến và tối ưu mạch điện tử đây. Bài

toán thuộc lớp bài toán tối ưu có ràng buộc.