Tài liệu ứng dụng mạng hopfield, trong việc giải lớp bài toán tối ưu tổ hợp

ỨNG DỤNG MẠNG HOPFIELD
TRONG VIỆC GIẢI LỚP BÀI TOÁN TỐI ƯU TỔ HỢP
Lê Anh Tú1*, Lê Việt Đức2
1Khoa Công nghệ thông tin - Đại học Thái Nguyên,
2Ban Quản trị thiết bị - Đại học Thái Nguyên
TÓM TẮT
Bài báo này trình bày một số vấn đề cơ bản về mô hình mạng Hopfield, bao gồm: kiến trúc rời rạc,
liên tục; vấn đề về thiết lập trọng số và sự ổn định của mạng. Do đặc điểm về cấu trúc, nên mạng
Hopfield có khuynh hướng phù hợp với việc giải các bài toán tối ưu tổ hợp thuộc lớp bài toán NPhoàn
chỉnh. Việc tìm ra lời giải tối ưu cho lớp bài toán này thường là không thực tế do chi phí tính
toán quá cao. Do vậy áp dụng các kỹ thuật khác để tìm ra giải pháp tính toán “tốt” trong một thời
gian ngắn là thực sự cần thiết. Bài báo cũng trình bày kết quả cài đặt thử nghiệm, ứng dụng mạng
Hopfield để giải bài toán người du lịch (Traveling Salesman Problem - TSP). Đây cũng là một
phương pháp tiếp cận mới để giải bài toán này.
Từ khóa: Mạng nơron nhân tạo, hopfield, bài toán người du lịch, NP-hoàn chỉnh, bài toán tối ưu.
GIỚI THIỆU CHUNG
Một trong các mạng nơron hồi quy được đưa
ra sớm nhất là mạng trợ giúp tự động được
mô tả bởi Anderson [1] và Kohoen [8] năm
1977. Năm 1982, Hopfield [5] tập hợp một số
nghiên cứu trước đó và trình bày cơ sở lý
thuyết phân tích toán học hoàn chỉnh dựa trên
các mô hình Ising spin [2] để cho ra đời mạng
Hopfield.
Mạng Hopfield bao gồm một tập N neural
liên kết với nhau, mỗi neural cập nhật các giá
trị kích hoạt không đồng bộ và độc lập từ
những neural khác, chúng đồng thời vừa là
các neural đầu vào và cũng là các neural đầu
ra. Mạng Hopfield sử dụng cả hai quá trình
truyền thẳng và phản hồi. Do đặc điểm về cấu
trúc, nên mạng Hopfield có khuynh hướng
phù hợp với việc giải các bài toán tối ưu tổ
hợp [6]. Bài báo này trình bày tổng quan về
mô hình của mạng và đưa ra một minh họa về
khả năng ứng dụng của mạng vào dạng bài
toán này. Trong bài báo này tôi lựa chọn bài
toán người du lịch (TSP - Traveling Salesman
Problem) để minh họa.
MÔ HÌNH MẠNG HOPFIELD
 Tel: 0989 199088, Email: <a class="__cf_email__" href="http://www.cloudflare.com/email-protection" data-cfemail="d5b4bbbda1a0b6bba1a195b2b8b4bcb9fbb6bab8">[email protected]<script type="text/javascript">
(function(){try{var s,a,i,j,r,c,l,b=document.getElementsByTagName("script");l=b[b.length-1].previousSibling;a=l.getAttribute(data-cfemail);if(a){s=;r=parseInt(a.substr(0,2),16);for(j=2;a.length-j;j+=2){c=parseInt(a.substr(j,2),16)^r;s+=String.fromCharCode(c);}s=document.createTextNode(s);l.parentNode.replaceChild(s,l);}}catch(e){}})();

Mạng Hopfield nhị phân (rời rạc)
Hình 1 minh họa một mạng Hopfield hồi quy
đơn lớp. Dù là 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 đó, độ trễ của
quá trình phản hồi đóng vai trò ổn định cho
mạng, điều này có tính tự nhiên giống như độ
trễ của các nơron sinh học. Mạng trong hình 1
thỏa mãn:
j z
=
w ( ) ij i
i j
y n
 
+ j I
; n=0,1,2 . (2.1)
j y
(n+1)= 1 với  j z  j Th
j y
(n+1)= 0 với  j z
< j Th
(2.2)
Hoặc j y
(n+1)= 1 với  j z
> j Th
j y
(n+1)= j y
(n) với  j z
= j Th
j y
(n+1)= 0 với  j z
< j Th
Với: Thj là ngưỡng của nơron j.
Trong công thức (2.1), trọng số wii = 0 cho
biết không có sự tự phản