Mạng nơron Hopfield -Ứng dụng

Trang 1

ĐỒ ÁN TRÍ TUỆ NHÂN TẠO
TÊN ĐỀ TÀI:
MẠNG NƠRON HOPFIELD-ỨNG DỤNG

TÊN HỌC VIÊN: HỒ ĐẮC QUÁN
LỚP :CHKHMT – TPHCM23A11
NIÊN KHÓA:2011-2013
MÃ HỌC VIÊN:11870233
GVHD:TS. NGUYỄN HỮU PHÚC

Mạng nơron Hopfield -Ứng dụng

Trang 2

Lời cảm ơn
Nội dung của đồ án đi vào tìm hiểu và xây dựng các phần tử nơron cơ bản,
xem xét và nghiên cứu cấu trúc một mạng nơron, giới thiệu về mạng nơron nhiều
lớp. Trọng tâm của đồ án đi vào tìm hiểu về mạng nơron Hopfield . Ứng dụng

Hình 1.1 Một nơron sinh học
Một nơron sinh học chỉ có một số chức năng cơ bản như vậy, ta nhận
thấy khả năng xử lý thông tin của nó là rất yếu. Để có được khả năng xử lý thông tin
Mạng nơron Hopfield -Ứng dụng

Trang 4

hoàn hảo như bộ não con người, thì các nơron phải kết hợp và trao đổi thông tin với
nhau. Ta hình dung sơ đồ liên kết, và trao đổi thông tin giữa hai nơron như hình 1.2. Hình 1.2. Sự liên kết các nơron
1.1.2 Cấu trúc và mô hình của một nơron nhân tạo
Mô hình toán học của mạng nơron sinh học được đề xuất bởi McCulloch và
Pitts, thường được gọi là nơron M-P, ngoài ra nó còn được gọi là phần tử xử lý và
được ký hiệu là PE (Processing Element).
Mô hình nơron có m đầu vào x
1
, x
2
, , x
m
, và một đầu ra y
i
như sau:

Hình 1.3 Mô hình một nơron nhân tạo

Mạng nơron Hopfield -Ứng dụng




và
j
n
j
iji
xwnet



1

trong đó: x
1
, x
2
, …x
m
là các tín hiệu đầu vào, còn w
i1
, w
i2
,…,w
im
là các
trọng số kết nối của nơron thứ i, net
i
là hàm tổng, f là hàm truyền,
i




01
01
)sgn(
xkhi
xkhi
xy
(1.7)
- Hàm bậc thang









00
10
11
)sgn(
xkhi
xkhix
xkhi
xy (1.8)
- Hàm ngưỡng đơn cực
x

hình dung mạng nơron như là một hệ truyền đạt và xử lý tín hiệu. Đặc tính truyền
đạt của nơron phần lớn là đặc tính truyền đạt tĩnh.
Khi liên kết các đầu vào/ra của nhiều nơron với nhau, ta thu được một mạng
nơron, việc ghép nối các nơron trong mạng với nhau có thể là theo một nguyên tắc
bất kỳ. Vì mạng nơron là một hệ truyền đạt và xử lý tín hiệu, nên có thể phân biệt
các loại nơron khác nhau, các nơron có đầu vào nhận thông tin từ môi trường bên
ngoài khác với các nơron có đầu vào được nối với các nơron khác trong mạng,
chúng được phân biệt với nhau qua vector hàm trọng số ở đầu vào w.
Nguyên lý cấu tạo của mạng nơron bao gồm nhiều lớp, mỗi lớp bao gồm nhiều
nơron có cùng chức năng trong mạng. Hình 1.5 là mô hình hoạt động của một mạng
nơron 3 lớp với 8 phần tử nơron. Mạng có ba đầu vào là x
1
, x
2
, x
3
và hai đầu ra y
1
,
y
2
. Các tín hiệu đầu vào được đưa đến 3 nơron đầu vào, 3 nơron này làm thành lớp
đầu vào của mạng. Các nơron trong lớp này được gọi là nơron đầu vào. Đầu ra của
các nơron này được đưa đến đầu vào của 3 nơron tiếp theo, 3 nơron này không trực
Mạng nơron Hopfield -Ứng dụng

Trang 8

tiếp tiếp xúc với môi trường bên ngoài mà làm thành lớp ẩn, hay còn gọi là lớp
trung gian. Các nơron trong lớp này có tên là nơron nội hay nơron ẩn. Đầu ra của

ứng đầu ra tương ứng, để khi có một kích thích bất kỳ tác động vào mạng,
mạng có khả năng suy diễn và đưa ra một đáp ứng phù hợp. Đây chính là
chức năng nhận dạng theo mẫu của mạng nơron. Để thực hiện chức năng
này, mạng nơron đóng vai trò như một bộ phận tổ chức các nhóm thông tin
đầu vào, và tương ứng với mỗi nhóm là một đáp ứng đầu ra phù hợp. Như
vậy, một nhóm bao gồm một loại thông tin đầu vào và một đáp ứng đầu ra.
Các nhóm có thể được hình thành trong quá trình học, và cũng có thể không
hình thành trong quá trình học.
Hình 1.6 là một số liên kết đặc thù của mạng nơron. Nơron được vẽ là các
vòng tròn xem như một tế bào thần kinh, chúng có các mối liên hệ đến các nơron
khác nhờ các trọng số liên kết. Tập hợp các trọng số liên kết này sẽ lập thành các
ma trận trọng số tương ứng.
1.2.1 Mạng nơron một lớp
Mỗi một nơron có thể phối hợp với các nơron khác tạo thành một lớp các
trọng số. Mạng một lớp truyền thẳng như hình 1.6a. Một lớp nơron là một nhóm các
nơron mà chúng đều có cùng trọng số, nhận cùng một tín hiệu đầu vào đồng thời.
Trong ma trận trọng số, các hàng là thể hiện nơron, hàng thứ j có thể đặt
nhãn như một vector w
j
của nơron thứ j gồm m trọng số w
ji
. Các trọng số trong cùng
một cột thứ j (j=1,2, ,n) đồng thời cùng nhận một tín hiệu đầu vào x
j
.
Mạng nơron Hopfield -Ứng dụng

Trang 10

w

1.2.2 Mạng nơron truyền thẳng nhiều lớp
Mạng nơron nhiều lớp (Hình 1.6.c) có các lớp được phân chia thành 3 loại sau
đây:
 Lớp vào là lớp nơron đầu tiên nhận tín hiệu vào x
i
(i = 1, 2, , n). Mỗi tín
hiệu x
i
được đưa đến tất cả các nơron của lớp đầu vào. Thông thường, các
nơron đầu vào không làm biến đổi các tín hiệu vào x
i
, tức là chúng không có
các trọng số hoặc không có các loại hàm chuyển đổi nào, chúng chỉ đóng vai
trò phân phối các tín hiệu.
 Lớp ẩn là lớp nơron sau lớp vào, chúng không trực tiếp liên hệ với thế giới
bên ngoài như các lớp nơron vào/ra.
 Lớp ra là lớp nơron tạo ra các tín hiệu ra cuối cùng.
1.2.3 Mạng nơron phản hồi
Mạng nơron phản hồi là mạng mà đầu ra của mỗi nơron được quay trở lại
nối với đầu vào của các nơron cùng lớp được gọi là mạng Laeral như hình 1.6b
1.2.4 Mạng nơron hồi quy
Mạng nơron phản hồi có thể thực hiện đóng vòng được gọi là mạng nơron
hồi quy như hình 1.6d. Mạng nơron hồi quy có trọng số liên kết đối xứng như mạng
Hopfield, mạng luôn hội tụ về trạng thái ổn định (Hình 1.6.b). Mạng BAM thuộc
nhóm mạng nơron hồi quy, gồm 2 lớp liên kết 2 chiều, không được gắn với tín hiệu
vào/ra. Nghiên cứu mạng nơron hồi quy mà có trọng số liên kết không đối xứng, thì
sẽ gặp phải vấn đề phức tạp nhiều hơn so với mạng truyền thẳng và mạng hồi quy
có trọng số liên kết đối xứng.
Mạng nơron Hopfield -Ứng dụng


một mạng đơn lớp nhưng nhờ cơ cấu phản hồi mà nó hoạt động hiệu quả như một
mạng đa lớp. Trong mạng này độ trễ trong quá trình phản hồi được đưa ra nhằm
đóng vai trò ổn định mạng, điều này mang bản chất tự nhiên giống như độ trễ của
các neuron sinh học ghi nhận khoảng cách của các khớp nối và tỉ lệ giới hạn của
vòng thần kinh. Mạng trong hình 1.1 thỏa mãn:

j
z
=
w ( )
ij i
i j
y n


+
j
I
; n=0,1,1….(1.1)

j
y
(n+1)= 1 với

j
z

j
Th


j
z
=
j
Thj
y
(n+1)= 0 với

j
z
<
j
Th

Trọng W
ii
trong công thức (1.1) bằng 0 cho biết không có sự tự phản hồi.
Trạng thái 0 của đầu ra y là -1 trong trường hợp lưỡng cực

Mạng nơron Hopfield -Ứng dụng

Trang 14 Hình 2.1 Cấu trúc của một mạng Hopfield

i

hợp bộ nhớ 2 chiều như sau:
Giả sử
i
X

R
m
,
i
y

R
n
i=1,2….L (1.3)
Và giả sử: W=
T
i i
i
y X

(1.4)
Trong đó W là ma trận trọng của các kết nối giữa vector x và vector y. Kết
nối này được gọi là một mạng lưới liên kết. Đặc biệt khi
i
y
=
i
x
kết nối được gọi là tự
động liên kết, tức là W=

x
liên kết với các trọng W
được phục hồi. Có thể thấy W phục vụ như một bộ nhớ cho phép mạng ghi nhớ các
vector đầu vào giống nhau, giống như được hợp nhất trong W. Cấu trúc trên có thể
được sử dụng để tái tạo lại thông tin, đặc biệt là loại thông tin không đầy đủ hoặc
thông tin sai. Cụ thể nếu xem xét một mạng đơn lớp thì:
W=
1
L
T
i i
i
X X


(1.8)
Với
w
ij
=
w
ji


i,j (1.9)
Tuy nhiên để đáp ứng các yêu cầu về sự ổn định của mạng (sẽ được thảo
luận sau) ta đặt:
w
ii
=0 với

w
ij
=
w
ji


i,j (1.21)
và
w
ii
=0 với

i (1.22)
Yêu cầu trên được phát biểu thông qua định lý ổn định Lyapunov. Trạng thái
một mạng là ổn định nếu có thể định nghĩa được một hàm năng lượng của mạng
(hàm Lyapunov của nó) luôn luôn giảm theo thời gian [7] (Lyapunov 1907). Trạng
thái của mạng là ổn định nếu xây dựng được một hàm E của các trạng thái y thỏa
mãn định lý ổn định Lyapunov theo các điều kiện sau đây:
Điều kiện A: Bất kỳ sự thay đổi hữu hạn ở các trạng thái y của mạng sẽ dẫn
đến sự giảm hữu hạn trong E
Điều kiện B: E là hàm bị chặn dưới
Do đó ta định nghĩa hàm năng lượng E như sau:
E=
1
1
w
2
j j j j ij j i
j j i i

là tổng các đầu ra của mạng, khi đó đầu ra
i
y
của mạng thỏa mãn:

i
y
=
( )
i i
f z

=
1
[1+tanh( )]
2
i
z

(1.36)
Như trong hình 2.2

Hình 2.2 Hàm kích hoạt với biến


Trong đó

là biến xác định độ dốc của f. Ngoài ra một phương trình vi phân
có thể thay thế các mối quan hệ thời gian trễ giữa đầu vào và tổng trọng đầu ra của
mạng.

Mạng nơron Hopfield -Ứng dụng

Trang 19

10!=3.628.800 đường đi (bao gồm cả đường đi với cùng một tuyến đường nhưng
khác hướng). Con số này tăng lên hơn 6.2 triệu với 13 thành phố.
Đối với n thành phố được viếng thăm , đặt
ij
X
là biến có giá trị 1 nếu người
du lịch đi từ thành phố i đến thành phố j và 0 nếu ngược lại.
ij
D
là khoảng cách từ i
đến j. Khi đó bài toán người du lịch có thể được phát biểu lại như sau:
Cực tiểu hóa hàm mục tiêu tuyến tính:
1
n n
ij ij
i j j
X D
 


3.2.1. Thiết kế mạng
Mạng Hopfield là một mạng năng động với số lần lặp cho sự hội tụ từ một
trạng thái đầu vào tùy ý như trong hình 3.1

Hình 3.1: Kiến trúc mạng Hopfield cho bài toán TSP n thành phố
Sử dụng n


(2.1)
Trong đó: A,B,C,D là các số nguyên dương
ij
X
là biến để biểu thị đường đi thực tế được viếng thăm từ thành phố i đến thành
phố j. Vì vậy
ij
X
là đầu ra của neuron thứ j trong mảng của các neuron tương ứng
với thành phố thứ i. Ta có n
2
biến như vậy và giá trị cuối cùng của chúng là 0 hoặc
1 hay rất gần đến 0 hoặc 1.
Hàm năng lượng có thể được phân tích như sau:
- Ràng buộc hàng(
ik ij
i k
j k
A X X

  
): Trong hàm năng lượng bộ ba tổng
đầu tiên sẽ bằng 0 khi và chỉ khi có duy nhất số 1 trong mỗi cột theo thứ tự.
Điều này đảm bảo cho không có 2 thành phố được viếng thăm đồng thời.
- Ràng buộc cột(
ki ji
i k j k
B X X


): Giá
trị của điều kiện này là cực tiểu khi tổng khoảng cách đường đi là ngắn nhất.
Giá trị của D rất quan trọng quyết định giữa thời gian để hội tụ và tính tối ưu
của giải pháp. Nếu giá trị của D thấp phải mất nhiều thời gian để mạng hội tụ
nhưng nó mang lại giải pháp gần với giải pháp tối ưu, nếu giá trị của D cao
mạng hội tụ nhanh nhưng giải pháp thu được có thể sẽ không tối ưu.
3.2.3. Thiết lập ma trận trọng
Mạng ở đây hoàn toàn được kết nối với thông tin phản hồi và có n
2
neuron.
Do đó ma trận trọng sẽ là một ma trận vuông gồm n
2
xn
2
phần tử. Theo hàm năng
lượng ma trận trọng có thể được thiết lập như sau:
,
W
ik lj
=
, 1 , 1
(1 ) (1 ) ( )
il kj jl jl j k j k
A B C Dd
    
 
      
(2.2)
Trong đó: các hằng số A,B,C,D cũng giống như trong hàm năng lượng. Các
trọng cũng được cập nhật để thỏa mãn các ràng buộc khác nhau để cung cấp một

(2.3)
Biểu diễn neuron kích hoạt trong dòng thứ i và cột thứ j bởi
ij
a
và đầu ra kí
hiệu là
ij
X
.
Sử dụng một hằng thời gian

với giá trị 1.0
Một thông số khác cũng được sử dụng là m với giá trị 15
Điều kiện đầu tiên trong hàm kích hoạt là giảm sau mỗi lần lặp
Điều kiện 2,3,4,5 là giữ cho các ràng buộc để được đường đi hợp lệ
Chức năng kích hoạt được cập nhật như sau:
Mạng nơron Hopfield -Ứng dụng

Trang 23 ij
a
(moi)=
ij
a
(cu)+

ij
a

cụ thể nào. Ví dụ với 5 thành phố, mạng thường đạt được sự hội tụ với 120-
170 lần lặp. Trong vài trường hợp mạng chỉ cần 80 lần lặp để hội tụ, cũng có
vài trường hợp cần đến 250 lần. Điều này có thể lý giải được là do trạng thái
ban đầu được khởi tạo ngẫu nhiên của mạng.
- Nhiều trường hợp khi năng lượng của hệ thống đã được tính toán nó lại tăng
thay vì giảm. Vì vậy thuật toán không thành công trong một vài trường hợp.
- Trong quá trình test thử các mẫu có 93% là hội tụ, 7% thất bại và đôi khi
năng lượng của hệ thống tăng lên thay vì giảm trong khi mạng lặp theo
hướng hội tụ.
4. Kết luận
- Mạng được phát triển không phải luôn luôn đưa ra được các giải pháp tối ưu,
tuy nhiên trong phần lớn các trường hợp nó rất gần đến sự tối ưu. Cách tiếp
cận này là rất nhanh so với các phương pháp lập trình được sử dụng cho bài
toán người du lịch
- Vài sự thay đổi hoặc cải tiến có thể được thực hiện đối với hàm năng lượng
cùng với những hàm khác như hàm cập nhật trọng, hàm kích hoạt có thể cho
giải pháp tốt hơn.
- Trong nhiều trường hợp thuật toán hội tụ tới giá trị cực tiểu cục bộ thay vì
cực tiểu toàn cục. Vấn đề này có thể được giải quyết bằng cách thêm một
nhiễu ngẫu nhiên vào đầu vào ban đầu của hệ thống.
- Vấn đề khó giải quyết và chất lượng kém của các giải pháp có thể được loại
bỏ bằng hình thức thích hợp của hàm năng lượng và sửa đổi tính năng động
nội bộ của mạng. Bằng việc thể hiện tất cả các ràng buộc của bài toán trong
những điều kiện đơn tổng số các điều kiện và tham số trong hàm năng lượng
có thể giảm
Mạng nơron Hopfield -Ứng dụng

Trang 25

- Các thiết lập cho các tham số khác nhau như A,B,C,D,m…. vẫn có thể được