..

ĐẠ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

THÁI NGUN - 2010

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




ĐẠ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
Chuyên nghà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

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




i

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 1.1.5. Ƣu và nhƣợc điểm của mạng nơ-ron......................................... - 12 1.2. Mạng Hopfield ............................................................................... - 13 1.2.1. Mạng Hopfield rời rạc .............................................................. - 14 1.2.2 Mạng Hopfield liên tục:............................................................. - 15 1.3. Khả năng ứng dụng của mạng Hopfield.......................................... - 17 1.4 Một số bài loại NP - C ..................................................................... - 18 1.4.1 Bài toán bốn màu....................................................................... - 18 1.4.2 Bài tốn phẳng hóa đồ thị .......................................................... - 18 1.4.3 Bài toán ngƣời du lịch ............................................................... - 20 1.4.4 Bài tốn phe nhóm tối đa. .......................................................... - 23 1.4.5 Bài toán cắt giảm tối đa ............................................................. - 23 CHƢƠNG 2: ỨNG DỤNG MẠNG MAXIMUM NEURAL NETWORK
VỚI TỰ PHẢN HỒI PHI TUYẾN ĐỂ GIẢI BÀI TỐN PHE NHĨM TỐI
ĐA...............................................................................................................- 24 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




ii

2.1 Giới thiệu bài tốn phe nhóm tối đa ................................................. - 24 2.2 Mơ tả của thuật tốn đề xuất cho vấn đề phe nhóm tối đa. ............... - 25 2.3 Thử nghiệm và đánh giá kết quả. ..................................................... - 31 CHƢƠNG 3: ỨNG DỤNG MẠNG MAXIMUM NEURAL NETWORK
VỚI TỰ PHẢN HỒI PHI TUYẾN ĐỂ GIẢI BÀI TOÁN CẮT GIẢM TỐI

ĐA ........................................................................................................... - 38 3.1 Giới thiệu bài toán ........................................................................... - 38 3.2 Mơ tả thuật tốn đề xuất .................................................................. - 41 3.3 Thử nghiệm và đánh giá kết quả. ..................................................... - 45 KẾT LUẬN .............................................................................................. - 55 TÀI LIỆU THAM KHẢO ........................................................................ - 56 PHỤ LỤC 1 ............................................................................................. - 58 PHỤ LỤC 2 ............................................................................................. - 63 -

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




iii

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ù

27

Hình 2.1 (c) Biểu diễn một phe nhóm tối đa


28

Hình 2.2. Cơ cấu của mạng MNN với phi tuyến tự phản hồi

30

Hình 2.3 Biểu diễn lƣu đồ thuật tốn

33

Hình 2.4 (a) Biểu diễn đồ thị 6 đỉnh

34

Hình 2.4 (b) Biểu diễn một phe nhóm tối đa

34

Hình 2.5 (a) Biểu diễn đồ thị 10 đỉnh

35

Hình 2.5 (b) Biểu diễn một phe nhóm tối đa

36

Hình 2.6 (a) Biểu diễn đồ thị 20 đỉnh

36


Hình 2.6 (b) Biểu diễn một phe nhóm tối đa

37

Hình 3.1 (a ) Một đồ thị vô hƣớng đơn giản bao gồm 5 đỉnh

41

Hình 3.1 (b ) Một trong các đồ thị cắt giảm tối đa

41

Hình 3.2. Cơ cấu của mạng MNN với phi tuyến tự phản hồi

45

Hình 3.3 Biểu diễn lƣu đồ thuật tốn

47

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




iv

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

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-1-

MỞ ĐẦU
Trong thực tế có nhiều bài tố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 tốn đó. Ví dụ: Bài tốn tìm đƣờng đi ngắn nhất, bài tố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 tố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 tố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 tố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
Hopfield và ứng dụng". 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, mạng nơ
ron Hopfiel và các bài toán về đồ thị loại NP - C bao gồm: Giới thiệu sơ lƣợc
về mạng nơ-ron, mạng nơ ron Hopfield, phạm vi ứng dụng của mạng nơron
Hopfield, một số bài toán đồ thị loại NP - C.
Chƣơng hai trình bày về ứng dụng cải biên của mạng nơron Hopfield
trong việc giải quyết bài tốn phe nhóm tối đa. Khi ứng dụng cải biên mạng
nơron Hopfield để giải quyết bài tốn này thì thu đƣợc kết qủa khả quan cụ
thể: Về mặt chƣơng trình gọn đơn giản, thời gian thực hiện nhỏ.
Chƣơng ba trình bày về ứng dụng cải biên của mạng nơron Hopfield
trong việc giải quyết bài toán cắt giảm tối đa, đây là bài toán thuộc lớp bài
toán tối ƣu tổ hợp. Khi ứng dụng cải biên mạng nơron Hopfield để giải quyết

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-2-


bài tốn này thì thu đƣợc kết qủa khả quan cụ thể: Về mặt chƣơng trình gọn
đơn giản, thời gian thực hiện nhỏ.
Qua luận văn này em xin chân thành cảm ơn: PGS .TS Đặng Quang Á Viện Công nghệ thơng tin đã tận tình giúp đỡ, động viên, định hƣớng, hƣớng
dẫn em nghiên cứu và hoàn thành luận văn này. Em xin cảm ơn các thầy cô
giáo trong viện Công nghệ thông tin, các thầy cô giáo khoa Công nghệ thông
tin ĐH Thái nguyên, đã giảng dạy và giúp đỡ em trong hai năm học qua, cảm
ơn sự giúp đỡ nhiệt tình của các bạn đồng nghiệp .

THÁI NGUYÊN 10/2010
Ngƣời viết luận văn
Trần Kiên

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-3-

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 hố nhƣ thiết bị ngƣỡng (giới hạn) để

thực hiện các phép tính logic và mơ hình mạng nơ-ron của Mc Culloch-Pitts
cùng với giải thuật huấn luyện mạng của Hebb ra đời năm 1943.
+ Giai đoạn hai: Vào khoảng gần những năm 1960, một số mơ hình nơron hồn thiện hơn đã đƣợc đƣa ra nhƣ: mơ hình Perceptron của Rosenblatt
(1958), Adaline của 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)
đã 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: Có thể tính vào khoảng đầu thập niên 80. Những đóng
góp lớn cho mạng nơ-ron trong giai đoạn này phải kể đến Grossberg,
Kohonen, Rumelhart và Hopfield. Trong đó đóng góp lớn của 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 tố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à

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-4-

Williams đề xuất thuật toán sai số truyền ngƣợc nổi tiếng để huấn luyện mạng
nơ-ron nhiều lớp nhằm giải bài tố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ính 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, ví dụ nhƣ: Kỹ thuật tính, tối ƣu, sinh học, y
học, thống kê, giao thơng, hố 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.
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 sj đƣợc gán
một trọng số wij tƣơng ứng. Ta có thể ƣớc lƣợng tổng tín hiệu đi vào nơ ron
neti theo một số dạng sau:
(i)

Dạng tuyến tính:
𝑁

𝑛𝑒𝑡𝑖 =

𝑤𝑖𝑗 𝑆𝑗

(1.1)

𝑗 =1

(ii)

Dạng toàn phƣơng:
𝑁


𝑤𝑖𝑗 𝑆𝑗2

𝑛𝑒𝑡𝑖 =

(1.2)

𝑗 =1

(iii)

Dạng mặt cầu:
𝑁

𝑛𝑒𝑡𝑖 = 𝜌 −2

𝑠𝑗 − 𝑤𝑖𝑗

2

(1.3)

𝑗 =1

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-5-


Trong đó 𝜌 và 𝑤𝑖𝑗 ( 𝑗 = 1, 𝑁 ) 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 tồ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.5)

ở đây UTP>LTP. Trong đó :
UTP là ngƣỡng trên (Upper Trip Point ).
LTP là ngƣỡng dƣới (Lower Trip Point ).

(iii) Hàm Sigmoid:
𝑜𝑢𝑡 = 𝑓 𝑛𝑒𝑡 =

1
1 + 𝑒 −𝜆(𝑛𝑒𝑡 +𝜃)

(1.6)

Trong đó 𝜆 >0 là hằng số xác định độ nghiêng của hàm.


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 q trình học. Trong các mạng nơ ron có sử dụng bias, mỗi nơ ron có
thể có trọng số tƣơng ứng với bias. Trọng số này ln ln có giá trị là 1.


Mơ hình của một nút xử lý (nút thứ i ):

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-6-

𝑉𝑖
𝑉𝑗


𝑤𝑖1
𝑤𝑖𝑗

Ui =

𝑤𝑖𝑁

𝑉𝑁

𝑉𝑖

Vi=fi(Ui)

Hình 1.1 Mơ hình một nơ ron
𝑁

𝑈𝑖 =

𝑊𝑖𝑗 𝑉𝑗 + 𝜃𝑖

(1.7)

𝑗 =1,𝑗 ≠𝑖

𝑉𝑖 = 𝑓𝑖 𝑈𝑖

(1.8)

trong đó:
𝑈𝑖 là tín hiệu vào tại nơ ron i.

𝑉𝑖 là tín hiệu ra tại nơ ron i.
𝑊𝑖𝑗 là trọng số liên kết tại nơ ron j đến nơ ron i.
𝜃𝑖 là ngƣỡng (đầu vào ngồi) kích hoạt nơ ron i.
𝑓𝑖 là hàm kích hoạt của nơ ron i.
1.1.3. Mạng nơ ron
Mạng nơ ron nhân tạo (Artificial Neural Network ) là một cấu trúc
mạng đƣợc hình thành nên bởi một số lƣợng các nơ ron nhân tạo liên kết với
nhau. Mỗi nơ ron có đặc tính đầu vào, đầu ra và thực hiện một chức năng tính
tốn cục bộ.
Với việc giả lập các hệ thống sinh học, các cấu trúc tính tốn, mạng nơ
ron có thể giải quyết đƣợc các lớp bài tốn nhất định, nhƣ : Bài toán xếp loại,
bài toán lập lịch, bài tốn tìm kiếm, bài tốn nhận dạng mẫu... Các bài tốn
phức tạp cao, khơng xác định. Tuy nhiên, sự liên kết giữa một bài toán bất kỳ
trong thực tế với một giải pháp mạng nơ ron lại là một việc khơng dễ dàng.

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-7-

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 tốn học dựa trên bản chất của nơ ron.




Bao gồm một số lƣợng rất lớn các nơ ron liên kết với nhau.



Mạng nơ ron có khả năng học, khái quát hóa tập dữ liệu học

thông qua việc gán và hiệu chỉnh các trọng số liên kết.


Tổ chức theo kiểu tập hợp mang lại cho mạng nơ ron khă năng

tính tốn rất lớn, trong đó khơng có nơ ron nào mang thơng tin 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.
(i) Mạng truyền thẳng :
Mạng truyền thẳng một lớp
Mơ hình mạng nơ ron truyền thẳng một lớp là mơ hình liên kết cơ bản
và đơn giản nhất. Các nơ ron tổ chức lại với nhau tạo thành một lớp, đƣờng
truyền tín hiệu đƣợc truyền theo một hƣớng nhất định nào đó. Các đầu vào
đƣợc nối với các nơ ron theo các trọng số khác nhau, sau quá trình xử lý cho
ra một chuỗi các tín hiệu ra. Nếu mạng nơ ron là mơ hình LTU thì nó đƣợc
gọi là mạng Perception, cịn mạng nơ ron là mơ hình LGU thì nó đƣợc gọi là
mạng Adaline.
x1

y1

x2

y2


Xm

yn

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

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-8-

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 , … , 𝑦𝑛

𝑇

đƣợc xác định nhƣ sau :
𝑚

𝑦𝑖 = 𝑓𝑖

𝑤𝑖𝑗 𝑥𝑗 − 𝜃𝑖 , 𝑖 = 1, 𝑛

(1.9)

𝑗 =1


Trong đó :
m : Số tín hiệu vào
n : Số tín hiệu ra
𝑊𝑖𝑇 = 𝑤𝑖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
tố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.
x1

Lớp vào

Lớp ẩn

Lớp ra

x2

y1
y2

yn

xm
Hình 1.3 Mạng truyền thẳng nhiều lớp

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




-9-

(ii) Mạng hồi quy
Mạng hồi quy một lớp có nối ngược
X1

Y1

X2

...

Y2

...

XN

...
YM


Hình1.4 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
X1

Y1

X2

Y2

...

...

...

...

XN

YM
Hình1.5 Mạng nhiều lớp có nối ngƣợc

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 tốn thuộc lớp bài tốn NP- đầy
đủ (NP-Complete ).

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 10 -

Các luật học đóng vai trị quan trọng trong việc xác định một mạng nơ
ron nhân tạo. Một cách đơn giản về khái niệm học của mạng nơ ron là cập
nhật trọng số trên cơ sở các mẫu. Theo nghĩa rộng thì học có thể đƣợc chia ra
làm hai loại: Học tham số và học cấu trúc.


Học tham số: Các thủ tục học này nhằm tìm kiếm ma trận trọng

số sao cho mạng có khả năng đƣa ra dự báo sát với thực tế. Dạng chung của
luật học tham số có thể đƣợc mơ tả nhƣ sau:
∆𝑊𝑖𝑗 = 𝜂𝑟𝑥𝑗 , 𝑖 = 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
từng kiểu học.
+ Học có tín hiệu chỉ đạo: Là q 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.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 11 -

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
luật truyền ngƣợc để chỉnh trọng với tín hiệu chỉ đạo từ bên ngồi và ngƣời ta
gọi mạng này là mạng lan truyền ngƣợc.
+ Học khơng có tín hiệu chỉ đạo: Luật học này sử dụng đầu ra của
mạng làm cơ sở để hiệu chỉnh các trọng số liên kết. Hay trong luật này chính
là tín hiệu ra của mạng. Điển hình là luật Hebb (1949) thƣờng dùng cho các
mạng tự liên kết, luật LVQ (Learning Vector Quantization) dùng cho mạng tự
tổ chức một lớp thuộc lớp mạng ánh xạ đặc trƣng của Kohonen.

Luật học Hebb là luật sinh học xuất phát từ tiên đề của Hebb cho rằng:
Giữa hai nơ-ron có quan hệ và có thay đổi thế năng màng thì giữa chúng có
sự thay đổi trọng số liên kết. Nói cách khác, trọng số đƣợc điều chỉnh theo
mối tƣơng quan trƣớc và sau, nghĩa là:
∆𝑊𝑖𝑗 = 𝜂𝑦𝑖 𝑥𝑗 , 𝑖 = 1, 𝑁, 𝑗 = 1, 𝑀

(1.11)

trong đó:
Wij là sự thay đổi trọng số liên kết từ nơ-ron j đến nơ-ron i.
x j: là tín hiệu vào nơ-ron j.

y i là tín hiệu ra của nơ-ron i.

 là tốc độ học, nằm trong khoảng (0,1).

Luật Hebb giải thích việc chỉnh trọng trong phạm vi cục bộ của mạng
mà khơng cần tín hiệu chỉ đạo từ bên ngoài. Hopfield cũng cải tiến luật Hebb
cho các mạng tự liên kết thành 16 dạng khác nhau theo kiểu luật Hebb, luật
đối Hebb, luật Hopfield...

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 12 -

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.
Đối với mạng phản hồi thƣờng sử dụng luật Hebb và các luật cải tiến
của nó để chỉnh trọng mà khơng cần tín hiệu chỉ đạo từ bên ngồi.
+ Học tăng cường: Trong một số trƣờng hợp, thông tin phản hồi chỉ là
tín hiệu bao gồm hai trạng thái cho biết tín hiệu đầu ra của mạng là đúng hay
sai. Quá trình học dựa trên các thông tin hƣớng dẫn nhƣ vậy đƣợc gọi là học
có củng cố (học tăng cƣờng) và tín hiệu mang thơng tin phản hồi đƣợc gọi là
tín hiệu củng cố cho q trình học. Ta có thể thấy rằng quá trình học này là
một dạng của quá trình học có tín hiệu chỉ đạo bởi vì mạng nhận đƣợc một số
thơng tin phản hồi từ bên ngồi.


Học cấu trúc: Tìm kiếm các tham số của cấu trúc mạng để tìm ra

một cấu trúc mạng hoạt động tốt nhất. Trong thực tế, việc học cấu trúc là tìm
ra số lớp ẩn và tìm ra số nơ-ron trên mỗi lớp đó. Giải thuật di truyền thƣờng
đƣợc sử dụng trong các cấu trúc nhƣng thƣờng chạy rất lâu, thậm chí ngay cả
đối với mạng có kích thƣớc trung bình. Ngồi ra kỹ thuật gọt tỉa mạng hay
mạng tăng dần cũng đƣợc áp dụng trong việc học cấu trúc của mạng có kích
thƣớc tƣơng đối nhỏ.
1.1.5. Ƣu và nhƣợc điểm của mạng nơ-ron


Ưu điểm:

- Xử lý song song.
- 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:

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 13 -

- 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 qt để đá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ự đố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à q 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.
Đầu vào

X1
X2

Y1

.

Y2

Đầu ra

.
XN

.

YM

Hình1.6 Mơ hình mạng Hopfield
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 14 -

Ký hiệu Wij là liên kết gữa hai nơ ron i và j ( w ij  w ji ), Vi là đầu ra

của nơ ron i. Ta coi véc tơ (V1, V2, ... Vn) 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 Vj 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 fi mà nơ ron i cho đầu ra là.
Vi(t+1) = fi(Vi(t)).
Mạng đạt trạng thái cân bằng nếu Vi(t+1) = Vi(t) ,  i
Ta định nghĩa hàm năng lƣợng của mạng là:
1
𝐸 = 𝐸(𝑉1 , 𝑉2 , … , 𝑉𝑛 ) = −
2

𝑛

𝑛

𝑛

𝑊𝑖𝑗 𝑉𝑖 𝑉𝑗 −
𝑖=1 𝑗 =1,𝑖≠𝑗

𝐼𝑗 𝑉𝑖

(1.12)

𝑖=1


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:
fi  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

Vi(t+1) = Vi(t) +Vi

trong đó Vi đƣợc cho bởi cơng thức (quy tắc)

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên





- 15 -

1 𝑛ế𝑢

𝑊𝑖𝑗 𝑉𝑗 𝑡 + 𝐼𝑖 ≥ 0 𝑣à 𝑉𝑖 𝑡 = 0
𝑗

Δ𝑉𝑖 =

−1 𝑛ế𝑢

𝑊𝑖𝑗 𝑉𝑗 𝑡 + 𝐼𝑖 ≤ 0 𝑣à 𝑉𝑖 𝑡 = 1

(1.14)

𝑗

0 𝑡𝑟𝑜𝑛𝑔 𝑐á𝑐 𝑡𝑟ườ𝑛𝑔 𝑕ợ𝑝 𝑘𝑕á𝑐
Định lý: (Xem [9]) Giả sử Wii =0 ( i  i, n ) . Khi đó với quy tắc
chuyển trạng thái nhƣ trên và cập nhật không đồng bộ thì năng lƣợng của
mạng khơng tăng (tức là giảm hoặc giữ nguyên).
Chứng minh: Giả sử nơ ron k thay đổi trạng thái từ thời điểm t đến
t+1. Khi đó mạng sẽ thay đổi năng lƣợng và

∆𝐸 = 𝐸 𝑡 + 1 − 𝐸 𝑡 = −

𝑊𝑘𝑗 𝑉𝑗 (𝑡) − 𝐼𝑘 ∆𝑉𝑘
𝑗

Vì thế theo cơng thức (1.14) ta ln có E 0, tức là năng lƣợng của

mạng khơng tăng. Vì thế hàm năng lƣợng sẽ đạt tới giá trị cực tiểu. Do hàm
giới nội.
Do tính chất hội tụ và giá trị nhị phân của các nơ ron nên mạng
Hopfield rời rạc đƣợc sử dụng cho các bài toán tối ƣu {0, 1}
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
𝑑𝑈𝑖
=
𝑑𝑡
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

𝑊𝑖𝑗 𝑉𝑗 + 𝐼𝑖

(1.15)

𝑗




- 16 -

𝑉𝑖 = 𝑓𝑖 (𝑈𝑖 )
trong đó fi là hàm kích hoạt.
Ở đây ta cũng giả thiết Wij= Wji và Wii =0. Dễ thấy rằng nếu hàm năng
lƣợng đƣợc cho bởi (1.12) thì :

𝑑𝑈𝑖
𝜕𝐸
= −
𝑑𝑡
𝜕𝑉𝑖
Sự hội tụ của mạng Hopfield liên tục cho bởi định lý sau:
Định lý: (xem Takefuji [8]) nếu fi(Ui) (𝑖 = 1, 𝑛 ) là các hàm khả vi và
khơng giảm thì

𝑑𝐸
𝑑𝑡

≤ 0.

Chứng minh: Ta có
dE

dt


i

E dVi dU i

Vi dU i dt


i

 E


 V
 i

2

 dVi
 .
 dU
i

dV

i
vì theo giả thiết các hàm fi(Ui) là khơng giảm nếu dU  0, do đó
i

dE
 0.
dt

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
+

tanh
𝑈
1 + 𝑒 −𝜆𝑈𝑖 2
2 𝑖

(1.16)

trong đó  >0 là tham số xác định độ dốc của hàm. Đồ thị của hàm
Sigmoid với một số giá trị của  xem hình vẽ
1

1

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5


0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

0.1

0
-5

-4

-3

-2

-1


0

1

2

3

4

5

0
-5

lamda =1

-4

-3

-2

-1

0

1

2


3

4

5

lamda =2
Đồ thị hàm Sigmoid

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 17 -

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 Vi 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 tố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
0.8
0.6
0.4
0.2

0
-0.2
-0.4
-0.6
-0.8
-1
-5

-4

-3

-2

-1

0

1

2

3

4

5

Đồ thị hàm Hàm y=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ự đốn.


Giải các bài tốn tối ƣu: Vấn đề chính là tìm những thuật tốn huấn
luyện mạng để góp phần tìm nghiệm cho nhiều lớp bài tốn tối ƣu tồn cục.

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 18 -

1.4 Một số bài loại NP - C
1.4.1 Bài toán bốn màu
Phát biểu bài toán bốn màu:
Cho một bản đồ trong đó có N nƣớc. Cần tơ màu cho các nƣớc sao cho
hai nƣớc kề nhau (tức là có chung biên giới) đƣợc tơ bởi hai màu khác nhau,
nhờ đó có thể phân biệt các vùng một cách dễ dàng.
Bài tốn sẽ khơng cịn tồn tại nếu nhƣ có số lƣợng màu lớn. Tuy nhiên,
sẽ thực sự khó khăn với ràng buộc rằng phải sử dụng số màu là nhỏ nhất.
Đầu những năm 1850, Francis Guthrie quan tâm tới bài tốn này và đã
trình bày bài tốn với Augustus DeMorgan. Khi đó nhiều nhà tốn học khác
đã cố gắng chứng minh rằng bất kỳ một đồ thị phẳng nào cũng có thể tơ đƣợc
bởi bốn màu. Vào tháng 8 năm 1976, Kenneth Appel và Wolfgang Haken đã
trình bày công việc của họ với những thành viên của hội tốn học Mỹ. Tuy
nhiên, cách tơ màu của họ dựa trên phƣơng pháp tuần tự nên mất nhiều thời
gian để giải bài toán lớn (cỡ O(n2)).
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 tốn phẳng hóa đồ thị

Phẳng hố đồ 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 qt bài tố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 hố đƣợc, sau đó phẳng hóa đồ thị con đó

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên




- 19 -

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 hố 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 hố 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 hố đƣợc.
-


Biểu diễn đồ thị tìm đƣợc lên mặt phẳng sau đó thực hiện phẳng

hố.
Ví dụ:
Giả sử ta có một đồ thị gồm sáu cạnh và bốn đỉnh đƣợc biểu diễn bởi
các hình sau:
1

2

4

3

Hình 1.7 Đồ thị chƣa phẳng
hóa
Hình (1.7) là đồ thị phẳng nếu nhƣ hai cạnh(1,3) và (2,4) không cắt
nhau.

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên