Phương pháp lai mạng nơ ron - giải thuật di truyền giải bài toán NP-C và ứng 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

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

KHOA CÔNG NGHỆ THÔNG TIN

LÊ THANH BÌNH

PHƯƠNG PHÁP LAI MẠNG NƠ RON

GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NP-C

VÀ ỨNG DỤNG

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

THÁI NGUYÊN 2010

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 HỌC THÁI NGUYÊN

KHOA CÔNG NGHỆ THÔNG TIN

LÊ THANH BÌNH

PHƯƠNG PHÁP LAI MẠNG NƠ RON

GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NP-C

VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính

Mã số: 60.48.01

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

NGƯỜI HƯỚNG DẪN KHOA HỌC:

PGS- TS. ĐẶNG QUANG Á

THÁI NGUYÊN 2010

- 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

MỤC LỤC

TRANG PHỤ BÌA

LỜI CAM ĐOAN

MỤC LỤC ...............................................................................................................i

DANH MỤC CÁC BẢNG…………………………………………….…...………iii

DANH MỤC CÁC HÌNH ......................................................................................iv

LỜI NÓI ĐẦU………………………………………………………………………1

CHƢƠNG I: GIỚI THIỆU SƠ LƢỢC VỀ CÁC BÀI TOÁN NP-C.........................3

1.1. Giới thiệu chung về bài toán NP-C ................................................................3

1.2. Cách tiếp cận giải bài toán NP-C...................................................................4

1.2.1. Một số khái niệm...................................................................................4

1.2.2. Giới thiệu một số thuật toán xấp xỉ giải bài toán NP-C..........................5

1.2.3. Các thuật toán gần đúng ........................................................................6

1.2.4. Tô mầu đồ thị với bài toán 4 mầu ........................................................13

1.2.5. Bài toán phẳng hóa đồ thị ....................................................................15

1.3. Kết luận.........................................................................................................17

CHƢƠNG II : MẠNG NƠ RON VÀ THUẬT GIẢI DI TRUYỀN GIẢI BÀI TOÁN

TỐI ƢU.................................................................................................................18

2.1. Giới thiệu về mạng nơ-ron ...........................................................................18

2.1.1. Lịch sử phát triển.................................................................................18

2.1.2. Mô hình mạng nơ-ron nhân tạo............................................................19

2.2. Phạm vi ứng dụng của mạng nơ-ron ...........................................................23

2.2.1. Những bài toán thích hợp ....................................................................23

2.2.2. Các lĩnh vực ứng dụng mạng nơ-ron....................................................23

2.2.3. Ƣu và nhƣợc điểm của mạng nơ-ron....................................................24

2.3. Mạng Hopfield ..............................................................................................24

2.3.1. Mạng Hopfield rời rạc .........................................................................26

2.3.2 Mạng Hopfield liên tục.........................................................................27

2.4. Giới thiệu thuật giải di truyền......................................................................28

- ii -

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.4.1. Các tính chất đặc thù của thuật giải di truyền.......................................29

2.4.2. Các bƣớc quan trọng trong việc áp dụng thuật giải di truyền ...............29

2.4.3. Ví dụ minh họa....................................................................................31

2.4.4. Các phƣơng thức biến hóa của giải thuật di truyền ..............................34

2.4.5. Các giải thuật di truyền lai...................................................................38

2.5. Giải thuật di truyền với bài toán tối ƣu.......................................................39

2.5.1. Ánh xạ hàm mục tiêu sang hàm phù hợp .............................................39

2.5.2. Tỷ lệ hoá giá trị phù hợp......................................................................40

2.5.3. Mã hoá tham biến nhờ véctơ nhị phân .................................................41

2.5.4. Bài toán tối ƣu ràng buộc.....................................................................41

2.6. Mạng nơ ron Hopfield - giải thuật di truyền giải bài toán tối ƣu...............42

2.7. Kết luận.........................................................................................................44

CHƢƠNG 3: ỨNG DỤNG THUẬT GIẢI DI TRUYỀN GIẢI BÀI TOÁN PHÂN

CÔNG NHIỆM VỤ...............................................................................................45

3.1. Giới thiệu ......................................................................................................45

3.2. Định nghĩa bài toán ......................................................................................47

3.3. Ứng dụng Thuật giải di truyền vào bài toán ...............................................48

3.3.1. Mã hóa: ...............................................................................................49

3.3.2. Toán tử chọn cá thể .............................................................................50

3.3.3. Toán tử lai ghép và toán tử đột biến.....................................................51

3.3.4. Sƣ̉ a chƣ̃a giải pháp ..............................................................................52

3.3.5. Tìm kiếm cục bộ..................................................................................54

3.4. Thí nghiệm và nhận xét ................................................................................55

3.4.1. Thí nghiệm..........................................................................................55

3.4.2. Nhận xét..............................................................................................56

3.5. Kết luận.........................................................................................................57

KẾT LUẬN……………………..………………………………………………….58

TÀI LIỆU THAM KHẢO………….….…………………………………………...59

- iii -

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

DANH MỤC BẢNG

Bảng 3.1: Các ứng dụng toán tử lai ghép thực hiện trong GGA. 52

Bảng 3.2: Các ứng dụng toán tử đột biến thực hiện trong GGA. 52

Bảng 3.3: Ví dụ về các sở thích của sinh viên 53

Bảng 3.4: Ví dụ về các sở thích của sinh viên 54

Bảng 3.5: Số sinh viên trong nhóm thứ i trong những giải pháp đƣợc

tìm thấy bởi GGA. 56

Bảng 3.6: So sánh các kết quả thu đƣợc bằng GGA và thuật toán

tham lam GRAH.

57

- iv -

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

DANH MỤC CÁC HÌNH

Hình 1.1: Bản dồ 9 nƣớc chƣa tô màu. 14

Hình 1.2: Bản dồ 9 nƣớc tô bởi 4 mầu. 14

Hình 1.3: Đồ thị 6 cạnh. 16

Hình 1.4: Hình (a) và (b) là đồ thị phẳng. 16

Hình 1.5: Đồ thị trên một hàng đơn. 17

Hình 2.1: Mô hình nơ ron sinh học. 19

Hình 2.2 : Mô hình một Nơ-ron . 21

Hình 2.3: Mô hình mạng Hopfield. 25

Hình 2.4: Lƣu đồ mô tả cấu trúc của giải thuật di truyền. 31

Hình 2.5: Lƣu đồ thuật toán của quá trình chọn lọc. 35

Hình 2.6: Lƣu đồ thuật toán quá trình lai ghép. 36

Hình 2.7: Lƣu đồ thuật toán của quá trình đột biến . 37

Hình 2.8: Lƣu đồ thuật toán của giải thuật lai. 42

Hình 2.9: Ví dụ về biểu diễn nơ ron của bài toán với N = 4. 44

Hình 3.1: Ví dụ về sở thích của các sinh viên trong 5 nhóm. 55