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
………… *………… TRẦN KIÊN MỘT SỐ CẢI BIÊN CỦA MẠNG HOPFIELD
VÀ ỨNG DỤNG
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
Trang phụ bìa
Lời cam đoan
MỤC LỤC i -
DANH MỤC CÁC HÌNH iii -
MỞ ĐẦU - 1 -
CHƢƠNG 1 GIỚI THIỆU VỀ MẠNG NƠ RON HOPFIELD VÀ CÁC BÀI
TOÁN VỀ ĐỒ THỊ LOẠI NP - C - 3 -
1.1. Giới thiệu sơ lƣợc về mạng nơ-ron - 3 -
1.1.1. Lịch sử phát triển - 3 -
1.1.2. Nơ-ron nhân tạo - 4 -
1.1.3. Mạng nơ ron - 6 -
1.1.4. Luật học - 9 -

PHỤ LỤC 2 - 63 -
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 CÁC HÌNH

Hình 1.1 Mô hình một nơ ron
6
Hình 1.2 Mạng truyền thẳng một lớp
7
Hình 1.3 Mạng truyền thẳng nhiều lớp
8
Hình 1.4 Mạng một lớp có nối ngƣợc
9
Hình 1.5 Mạng nhiều lớp có nối ngƣợc
9
Hình 1.6 Mô hình mạng Hopfield
13
Hình 1.7 Đồ thị chƣa phẳng
19
Hình 1.8 Đồ thị phẳng
20
Hình 1.9 Đồ thị phẳng
20
Hình 1.10 Biểu diễn đồ thị trên một hàng
20
Hình 2.1 (a) Biểu diễn đồ thị 10 đỉnh
27
Hình 2.1 (b) Biểu diễn đồ thị phần bù


Hình 3.4 (a) Một đồ thị vô hƣớng đơn giản bao gồm 5 đỉnh
48
Hình 3.4 (b) Một trong các đồ thị cắt giảm tối đa
48
Hình 3.5( a) Biểu diễn đồ thị 10 đỉnh 21 cạnh
49
Hình 3.5 (b) Một trong các đồ thị cắt giảm tối đa
50
Hình 3.6 (a) Biểu diễn đồ thị 25 đỉnh
51
Hình 3.6 (b) Một trong các đồ thị cắt giảm tối đa
54
- 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

MỞ ĐẦU

Trong thực tế có nhiều bài toán phức tạp thuộc lớp bài toán tối ƣu tổ
hợp và bài toán tối ƣu có rằng buộc, cũng có nhiều công trình nghiên cứu để
giải quyết các bài toán đó. Ví dụ: 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 cắt giảm tối đa, bài toán phe nhóm tối
đa Xong các giải thuật đƣa ra thƣờng phức tạp mà chƣa có thuật toán đơn
giản và hợp lý. Những năm gần đây trên thế giới đƣa ra mô hình mạng nơron
nhân tạo là mô hình tính toán đƣợc áp dụng rộng rãi trong lĩnh vực công nghệ
thông tin. Đặc biệt mạng Hopfield và các cải biên của nó 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 "Một số cải biên mạng của

- 3 -

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 1
GIỚI THIỆU VỀ MẠNG NƠ RON HOPFIELD VÀ CÁC BÀI
TOÁN VỀ ĐỒ THỊ LOẠI NP – C

1.1. Giới thiệu sơ lƣợc về mạng nơ-ron
1.1.1. Lịch sử phát triển
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: Có thể tính 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 1940, MeCulloch và Pitts đã
cho biết: nơ-ron có thể đƣợc mô hình hoá nhƣ thiết bị ngƣỡng (giới hạn) để

1.1.2. Nơ-ron nhân tạo
 Trọng số và tổng tín hiệu đầu vào:
Mô phỏng nơ-ron sinh học, ta có nơ-ron nhân tạ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 tín hiệu vào s
j
đƣợc gán
một trọng số w
ij
tƣơng ứng. Ta có thể ƣớc lƣợng tổng tín hiệu đi vào nơ ron
net
i
theo một số dạng sau:
(i) Dạng tuyến tính:


= 




=1
(1.1)
(ii) Dạng toàn phƣơng:


= 




) lần lƣợt là bán kính và tâm cầu.
 Hàm kích hoạt
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 kích hoạt. Hàm này có đặc điểm không âm và bị chặn. 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:
(i) Hàm McCuloch-Pitts:
= 



= 
1 ế 
0 ế  < 

(1.4)
ở đây  là ngƣỡng.
(ii) Hàm McCuloch-Pitts trễ:
= 



= 
1 ế  
0 ế < 





=  




=1,
+ 

(1.7)


= 





(1.8)
trong đó:


là tín hiệu vào tại nơ ron i.



)







1













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

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

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 :
 Là mô hình toán học dựa trên bản chất của nơ ron.

x
1
x
2
Hình 1.2 Mạng truyền thẳng một lớp
- 8 -

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ới mỗi giá trị đầu vào =


1
, 
2
, , 



. 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à
=


1
, 
2
, , 



1
, 
2
, , 



là véc tơ trọng số của nơ ron thứ i.


:Là hàm kích hoạt nơ ron thứ i


: Là ngƣỡng của nơ ron thứ i.
Mạng truyền thẳng nhiều lớp
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. Hình (1.3) mô tả cấu trúc của mạng nơ ron truyền thẳng nhiều lớp. Hình 1.3 Mạng truyền thẳng nhiều lớp


1.1.4. Luật học
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 ).
. . .
. . .
. . .
X
1
X
2
X
N
Y
1
Y
2
Y
M


= 

, = 1, 





, = 1, 






(1.10)
trong đó


là sự thay đổi trọng số liên kết từ nơ ron j đến nơ ron i.


là tín hiệu vào nơ ron j.
 là tốc độ học, nằm trong khoảng (0,1).
 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

= 



, = 1, 





, = 1, 






(1.11)
trong đó:
ij
W
là sự thay đổi trọng số liên kết từ nơ-ron j đến nơ-ron i.
:j
x
là tín hiệu vào nơ-ron j.
i
y
là tín hiệu ra của nơ-ron i.

là tốc độ học, nằm trong khoảng (0,1).

- Thiết kế hệ thống thích nghi.
- Không đòi hỏi các đặc trƣng mở rộng của bài toán (chủ yếu dựa trên
tập học).
 Nhược điểm:
- 13 -

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ông có các quy tắc và các hƣớng dẫn thiết kế một cách rõ ràng đối
với một ứng dụng nhất định.
- Không có cách tổng quát để đánh giá hoạt động bên trong mạng.
- Việc học đối với mạng có thể khó (hoặc không thể) thực hiện.
- Khó có thể dự đoán trƣớc đƣợc hiệu quả của mạng trong tƣơng lai
(khả năng tổng quát hoá).
1.2. 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ố
tƣơng ứng.

jiij
ww 
), V
i
là đầu ra
của nơ ron i. Ta coi véc tơ (V
1
, V
2
, V
n
) 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 tin hiệu V
j
từ các nơ ron khác và tin hiệu từ
bên ngoài (bias)


= 



+ 



Tuỳ theo hàm kích hoạt f
i
mà nơ ron i cho đầu ra là.
V



=1

=1,

=1
(1.12)
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.2.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ộ.
Trƣờng hợp mạng nhận các giá trị nhị phân {0, 1}:
Hàm kích hoạt đƣợc xác định nhƣ sau:
f
i
 f




= 
1 ế 0
0 ế á

(1.13)

Việc cho hàm kích hoạt (1.13) tƣơng đƣơng với quy tắc chuyển trạng
thái của mạng V

0 à 




= 0

1 ế 






+ 

0 à 




= 1

0  á ườ ợ á

(1.14)
Định lý: (Xem [9]) Giả sử W
ii
=0 (
nii ,

Một mở rộng của mạng nhị phân là mạng lƣợng tử hoá (xem [15]). Đâ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.2.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
phƣơng trình động học



= 



+ 


(1.15)
- 16 -

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 đó f
i



0.
Chứng minh: Ta có vì theo giả thiết các hàm f
i
(U
i
) là không giảm nếu do đó

Với tƣ cách là hàm kích hoạt ngƣời ta thƣờng chọn hàm Sigmoid:


= 




=
1
1 + 


=
1
2
1 + tanh 







i i
i
i
i
i
i
i
i
dU
dV
V
E
dt
dU
dU
dV
V
E
dt
dE
.
2

-5 -4 -3 -2 -1 0 1 2 3 4 5
0

Nhƣ trong [4] đã nhận xét rằng 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 V
i
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 đƣợc định nghĩa bởi (1.16) 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 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(x).
1.3. Khả năng ứng dụng của mạng Hopfield.
Khó có thể thống kê đầy đủ các ứng dụng của mạng nơ-ron nói chung
và mạng Hopfield nói riêng. Tuy nhiên, có thể nêu một số ứng dụng nhƣ sau:
- Xử lý ảnh.
- Nhận dạng mẫu.
- Y học.
- Các hệ thống quân sự.
- Vấn đề lập kế hoạch, điều khiển và tìm kiếm.
- Các hệ thống năng lƣợng.
- Dự đoán.
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.
-5 -4 -3 -2 -1 0 1 2 3 4 5
-1

2
)).
Một số thuật toán song song đã đƣợc công bố bởi E, D. Dahl(1987),
Moopenn(1987), và Thakoor (1987) giới thiệu lần đầu tiên cho bài toán k
màu.
Bài toán bốn màu là bài toán thuộc lớp NP - đầy đủ.
1.4.2 Bài toán phẳng hóa đồ thị
Phẳng hoá đồ thị là một trong những bài toán quan trọng trong việc
thiết kế mạch điện tử và định tuyến tối ƣu mạch tổ hợp.
Một đồ thị đƣợc gọi là phẳng nếu nhƣ nó không có hai cạnh nào cắt
nhau khi biểu diễn chúng trên cùng một mặt phẳng.
Một cách tổng quát bài toán phẳng hóa đồ thị đƣợc phát biểu nhƣ sau:
Từ một đồ thị cho trƣớc (là đồ thị phẳng hoặc không phẳng), hãy tìm ra một
đồ thị con lớn nhất để có thể phẳng hoá đƣợc, sau đó phẳng hóa đồ thị con đó
- 19 -

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

sao cho không có cạnh nào cắt nhau khi biểu diễn chúng trên cùng một mặt
phẳng.
Với đồ thị không phẳng cho trƣớc, để thực hiện phẳng hoá nó, trƣớc hết
ta phải chọn từ nó một đồ thị con lớn nhất có thể phẳng hóa đƣợc. Đồ thị con
này đƣợc chọn sao cho số cạnh của nó là lớn nhất, tƣơng đƣơng với số cạnh bị
loại bỏ khỏi đồ thị cho trƣớc là nhỏ nhất. Nhƣ vậy, bài toán tìm một đồ thị
con lớn nhất từ một đồ thị không phẳng cho trƣớc sau đó phẳng hoá nó là một
bài toán thuộc lớp bài toán NP- đầy đủ.
Nhƣ vậy để phẳng hoá một đồ thị ta phải thực hiện các bƣớc sau:
- Với một đồ thị cho trƣớc kiểm tra xem nó có phẳng hay không,
nếu không phẳng, ta tìm một đồ thị con lớn nhất có thể phẳng hoá đƣợc.
- Biểu diễn đồ thị tìm đƣợc lên mặt phẳng sau đó thực hiện phẳng