báo
TRƯỜNG ………………….
KHOA……………………….

[\[\
Báo cáo khoa học

Đề tài: Tối ưu hoá cấu trúc của mạng
nơron mờ bằng giải thuật di truyền
MỤC LỤC

I: MẠNG NƠRON 2
I.1 Giới Thiệu Mạng Nơron 2
I.1.1 Lịch sử phát triển 2
I.1.2 Căn nguyên sinh học 3
I.1.3 Đơn vị xử lý 5
I.1.4 Hàm xử lý 6
I.1.5 Ứng dụng 11
I.2 Mạng Norn Một Lớp 11
I.3 Mạng Noron Nhiều Lớp (Multi-layer Neural Network) 12
II: MẠNG NƠRON MỜ: 12
III: GIẢI THUẬT DI TRUYỀN 15
1: Các toán tử của giải thật di truyền 16
1.1 Chọn lọc 16
1.2 Lai ghép 17


MỞ ĐẦU

Lý do chọn đề tài: Gần đây suy diễn mờ được ứng dụng trong rất nhiều các
vấn đề khác nhau như: điều khiển máy móc hay trong các hệ thống sản xuất.
Một trong những suy diễn mờ đó là mạng nơron mờ. Có lẽ mạng noron
không chỉ hấp dẫn đối với những người yêu thích công nghệ thông tin bởi
khả năng do con người huấn luyện, mà còn bởi những ứng dụng thực tiễn
trong cuộc sống của nó. Chúng ta hoàn toàn có thể nhận dạng dấu vết vân
tay của tội phạm trong hình sự, có thể dự đoán thị trường chứng khoán, dự
đoán thời tiết, dự toán chi phí cho một dự án đường cao tốc, khôi phục
những tấm ảnh, hay một chiếc xe lăn dành cho người khuyết tật có thể nhận
được mệnh lệnh điều khiển bằng cử chỉ, hành động, thậm chí là suy nghĩ của
người ngồi trên xe v.v… nhờ có mạng noron nhân tạo. Mạng nơron ban đầu
có cấu trúc thô, vấn đề quan trọng là chúng ta phải làm sao cho cấu trúc thô
đó trở thành cấu trúc tương đối thích hợp. Do đó vấn đề tối ưu hoá cấu trúc
của mạng nơron là rất cần thiết. Một trong những giải thuật dùng để tối ưu
hoá cấu trúc của mạng nơron là giải thuật di truyền và giải thuật di truyền
được xem là thích hợp nhất.

Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
2

I: MẠNG NƠRON
I.1 Giới Thiệu Mạng Nơron
I.1.1 Lịch sử phát triển
Sự phát triển của mạng nơron trải qua cả quá trình đưa ra các khái niệm
mới lẫn thực thi các khái niệm này. Dưới đây là các mốc đáng chú ý trong
lịch sử phát triển của mạng nơron.

thức chỉ có khả năng giải quyết các bài toán khả phân tuyến tính. Họ cố gắng
cải tiến luật học và mạng để có thể vượt qua được hạn chế này nhưng họ đã
không thành công trong việc cải tiến luật học để có thể huấn luyện được các
mạng có cấu trúc phức tạp hơn.
* Do những kết quả của Minsky-Papert nên việc nghiên cứu về mạng
nơron gần như bị đình lại trong suốt một thập kỷ do nguyên nhân là không
có được các máy tính đủ mạnh để có thể thực nghiệm.
* Mặc dù vậy, cũng có vài phát kiến quan trọng vào những năm 70. Năm
1972 Teuvo Kohonen và James Anderson độc lập nhau phát triển một loại
mạng mới có thể hoạt động như một bộ nhớ. Stephen Grossberg cũng rất
tích cực trong việc khảo sát các mạng tự tổ chức (Self organizing network).
* Vào những năm 80, việc nghiên cứu mạng nơron phát triển rất mạnh
mẽ cùng với sự ra đời của PC. Có hai khái niệm mới liên quan tới sự hồi
sinh này, đó là:
+ Việc sử dụng các phương pháp thống kê để giải thích hoạt
động của một lớp các mạng hồi quy (recurrent network) có thể
được dùng như bộ nhớ liên hợp (associative memory) trong
công trình của nhà vật lý học Johh Hopfield.
+ Sự ra đời của thuật toán lan truyền ngược (back-
propagation) để luyện các mạng nhiều lớp được một vài nhà
nghiên cứu độc lập tìm ra như: David Rumelhart, James
McCelland,…Đó cũng là câu trả lời cho Minsky-Papert.

I.1.2 Căn nguyên sinh học
Bộ não con người chứa khoảng 10
11
các phần tử liên kết chặt chẽ với
nhau (khoảng 10
4
liên kết đối với mỗi phần tử) gọi là các nơron. Dưới con

-3
so với 10
-9
giây) nhưng bộ não có khả năng thực hiện
nhiều công việc nhanh hơn nhiều so với các máy tính thông thường. Đó một
phần là do cấu trúc song song của mạng nơron sinh học: toàn bộ các nơron
hoạt động một cách đồng thời tại một thời điểm. Mạng nơron nhân tạo cũng
chia sẻ đặc điểm này. Mặc dù hiện nay, các mạng nơron chủ yếu được thực
nghiệm trên các máy tính số, nhưng cấu trúc song song của chúng khiến
chúng ta có thể thấy cấu trúc phù hợp nhất là thực nghiệm chúng trên các vi
Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
5

mạch tích hợp lớn (VLSI: very large scale integrated circuit), các thiết bị
quang và các bộ xử lý song song.

Mạng nơron đôi khi được xem như là các mô hình liên kết (connectionist
models), là các mô hình phân bố song song (parallel-distributed models) có
các đặc trưng phân biệt sau:

* Tập các đơn vị xử lý;
* Trạng thái kích hoạt hay là đầu ra của đơn vị xử lý;
* Liên kết giữa các đơn vị. Xét tổng quát, mỗi liên kết được
định nghĩa bởi một trọng số w
jk
cho ta biết hiệu ứng mà tín
hiệu của đơn vị j có trên đơn vị k;
* Một luật lan truyền quyết định cách tính tín hiệu ra của
từng đơn vị đầu vào của nó;

j
: đầu vào mạng (net-input)
z
j
: đầu ra của nơron
g(x) : hàm chuyển (hàm kích hoạt).
Trong một mạng nơron có ba kiểu đơn vị:
* Các đơn vị đầu vào (input units), nhận tín hiệu từ bên ngoài;
* Cá đơn vị đầu ra (output units), gửi dữ liệu ra bên ngoài;
* Các đơn vị ẩn (hidden units), tín hiệu vào (input) và ra
(output) của nó nằm trong mạng.

Mỗi đơn vị j có thể có một hoặc nhiều đầu vào: x
0,
x
1
, x
2
,…x
n
, nhưng chỉ có
một đầu ra z
j
. Một đầu vào tới một đơn vị có thể là dữ liệu từ bên ngoài
mạng, hoặc đầu ra của một đơn vị khác, hoặc là đầu ra của chính nó.

I.1.4 Hàm xử lý
 Hàm kết hợp
Mỗi một đơn vị trong một mạng kết hợp các giá trị đưa vào nó thông
qua các liên kết với các đơn vị khác, sinh ra một giá trị gọi là net-input.

thích. Tương tự, nếu như w
ji
< 0, nơron ở trạng thái kiềm chế. Chúng ta
gọi các đơn vị với luật lan truyền như trên là các sigma units. Trong
một vài trường hợp người ta cũng có thể sử dụng các luật lan truyền
phức tạp hơn. Một trong số đó là luật sigma-pi, có dạng như sau:
a
j
=
ji
1
w
n
i
i
x


1
m
ik j
k
x



Rất nhiều hàm kết hợp sử dụng một “độ lệch” hay “ngưỡng” để

g(x) =
0 nếu (x ≤ 0)

Dạng hàm này được sử dụng trong các mạng chỉ có một lớp. Trong
hình vẽ sau, θ được chọn bằng 1. Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
9

+ Hàm sigmoid (Sigmoid function (logsig)) 1
( )
1
x
g x
e


Hàm này đặc biệt thuận lợi khi sử dụng cho các mạng được huấn luyện
(trained) bởi thuật toán lan truyền ngược (back-propagation) bởi vì nó
dễ lấy đạo hàm, do đó có thể giảm đáng kể tính toán trong quá trình
huấn luyện. Hàm này được ứng dụng trong các chương trình ứng dụng
mà các đầu ra mong muốn rơi vào khoảng [0,1].

đồng nhất là một hàm đồng nhất. Mặc dù vậy nhưng nó mang tính chất
phi tuyến (nghĩa là khả năng biểu diễn các hàm phi tuyến) làm cho các
mạng nhiều tầng có khả năng rất tốt trong biểu diễn các ánh xạ phi
tuyến. Tuy nhiên đối với luật học lan truyền ngược, hàm phải khả vi và
sẽ có ích nếu như hàm được gắn trong một khoảng nào đó. Do vậy hàm
sigmoid là lựa chọn thông dụng nhất.

Đối với các đơn vị đầu ra (output units), các hàm chuyển cần được chọn
sao cho phù hợp với sự phân phối của các giá trị đích mong muốn.
Chúng ta đã thấy rằng đối với các giá trị ra trong khoảng [0,1], hàm
sigmoid là có ích; đối với các giá trị đích mong muốn là liên tục trong
khoảng đó thì hàm này cũng vẫn có ích, nó có thể cho ta các giá trị ra
hay giá trị đích được căn trong một khoảng của hàm kích hoạt đầu ra.
Nhưng nếu các giá trị đích không được biết trước khoảng xác định thì
hàm hay được sử dụng nhất là hàm đồng nhất. Nếu giá trị mong muốn
là dương nhưng không biết cận trên thì nên sử dụng một hàm kích hoạt
dạng mũ (exponential output activation function).
Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
11

I.1.5 Ứng dụng
Trong quá trình phát triển, mạng nơron đã được ứng dụng
thành công trong rất nhiều lĩnh vực. Dưới đây là một số lĩnh vực ứng
dụng chính của mạng nơron:
 Aerospace: Phi công tự động, giả lập đường bay, các hệ thống
điều khiển lái máy bay, bộ phát hiện lỗi.
 Automotive: Các hệ thống dẫn đường tự động cho ô tô, các bộ
phân tích hoạt động của xe.
 Banking: Bộ đọc séc và các tài liệu, tính tiền của thẻ tín dụng.

 Mạng noron nhiều lớp lan truyền ngược sai số(Back- propagation
Neural Network)
 Mạng noron nhiều lớp ngược hướng (Counter – propagation Neural
Network)
 … II: MẠNG NƠRON MỜ:
Việc tích hợp kỹ thuật mạng nơron và logic mờ cho phép kết hợp ưu
điểm của cả hai. Một mặt, mạng nơron cung cấp cấu trúc tính toán dựa trên
liên kết (dung thứ lỗi và các tính chất biểu diễn phân tán) và khả năng học
cho các hệ logic mờ. Mặt khác, các hệ logic mờ sẽ đưa vào mạng nơron cơ
chế suy diễn dựa trên các luật “if…then”, chính sự kết hợp phong phú này
cho phép xây dựng các hệ thống tích hợp: Hệ mờ nơron, mạng nơron mờ và
các hệ lai.
Trong mạng nơron mờ có thể là tín hiệu vào, tín hiệu ra hay trọng số là
những số mờ Cũng có trường hợp mạng nơron mờ với tất cả các yếu tố.
* Mạng nơron như một công cụ suy diễn
Nói mạng nơron như một công cụ suy diễn vì: mạng nơron có khả năng
suy diễn. Với mỗi tín hiệu vào thì mạng nơron sẽ cho một đầu ra tương ứng
* Suy diễn mờ dựa trên mạng nơron:
 Biểu diễn luật mờ:
Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
13

Keller (1992) đề xuất mô hình mạng nơron truyền thẳng nhiều lớp
biểu diễn các luật suy diễn cơ sở:
If X
1

i
là {a
i1
,…, a
imi
}, I = 1… n. Có hai cách
xác định trọng số:
a
11
'
a
1m1
'
a
n1
'
a
nmn
'

w
11
w
1m1
w
n1
w
nm

d

Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
14 Cách 1:
ij
w
= 1 -
ij
a
. Khi đó lớp ẩn đầu tiên đo sự bất cập giữa
thông tin vào với A
i
.
Ta xác định d
i
như là d
i
= max{(1-
ij
a
)
ij
'
a
}
Hoặc d
i
= max{min(1-
ij

|}
Các hệ số a
i
xác định trọng số của mệnh đề X = A
i
trong luật (a
i

có thể được người thiết kế cung cấp hoặc đọc từ dữ liệu)
Ta thấy t = max {a
i
d
i
}.
Giả sử B tương ứng với tập mờ có độ thuộc {b
1
,…, b
k
}. Khi đó
trọng số u
i
được xác định bởi u
i
= 1- b
i
.
Cuối cùng với bộ đầu vào (A
1
’,…, A
n

Takagi-Sugeno-Kang bao gồm các bước như sau:
+ Lựa chọn biến vào ra trong tệp mẫu học.
+ Chia tập mẫu học thành hai phần: phần huấn luyện và
phần kiểm tra.
Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
15

+ Xây dựng mạng NN
memb
để biểu thị hàm phụ thuộc
cho phần IF của các luật. Huấn luyện mạng NN
memb
tương ứng
với phần IF của luật mờ.
+ Đơn giản phần THEN của các luật theo phương pháp
loại bỏ ngược.
+ Xác định kết quả ra và diễn giải mờ.

III: GIẢI THUẬT DI TRUYỀN
Giải thuật di truyền (Genetic Algorithsm- GA) là kĩ thuật giúp giải quyết
bài toán bằng cách mô phỏng theo sự tiến hoá của con người hay của sinh
vật nói chung (Dựa trên thuyết tiến hoá con người của Darwin) trong điều
kiện môi trường sống luôn thay đổi. Thuật giải di truyền là một hướng tiếp
cận tính toán gần đúng, nghĩa là mục tiêu của thuật giải di truyền không
nhằm đưa ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
Lý thuyết này do Johm Henry Holland (Giáo sư của trường đại học
Michigan- Mỹ) đề xướng vào giữa thập niên 70, thế kỉ XX.
Thuật giải di truyền về bản chất là thuật toán tìm kiếm dựa theo quy luật
của quá trình tiến hoá tự nhiên. Giải thuật kết hợp sự sống sót của cấu trúc

* Tính độ thích nghi của từng cá thể trong quần thể hiện hành, lập
bảng cộng dồn các giá trị thích nghi (theo số thứ tự gán cho từng cá
thể). Giả sử quần thể có n cá thể, gọi độ thích nghi của cá thể thứ I là F
i
,
tổng dồn thứ i là F
ti
, tổng độ thích nghi của toàn quần thể là F
m
.
* Tạo một số ngẫu nhiên F trong đoạn từ 0 đến F
m

* Chọn cá thể k đầu tiên thoả mãn F
tk-1
≤ F ≤ F
tk
đưa vào quần thể của
thế hệ mới.
Ví dụ: Giả sử quần thể ban đầu là 6 chuỗi nhiễm sắc thể. Tổng giá trị
của hàm mục tiêu là 50 như bảng sau:

STT

Chuỗi nhiễm sắc
thể
Hàm mục
tiêu
% của total total
1 01110 8 16 8

Chúng được áp dụng lên cặp cha mẹ được chọn lựa với xác suất lai
ghép p
cross
. Xác suất này cho ta số lượng p
cross
* popsize (popsize kích
thước của quần thể được lai tạo) nhiễm sắc thể được lai ghép.
Với mỗi nhiễm sắc thể trong quần thể:
 Phát sinh một số ngẫu nhiên r trong miền [0;1]
 Nếu r < p
cross
, chọn nhiễm sắc thể đó để lai ghép
Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
18

Sau đó, ta kết hợp các nhiễm sắc thể được chọn một cách ngẫu nhiên
lại. Mỗi cặp nhiễm sắc thể, chúng ta có thể phát sinh một số ngẫu
nhiên pos từ miền [1;L] (L là tổng số bít trong nhiễm sắc thể). Số
pos này sẽ cho ta vị trí của điểm lai ghép.

Ví dụ ta có 2 nhiễm sắc thể:
(a
1
a
2
…a
pos
a
pos+1

…b
pos
a
pos+1
…a
L
)

Như vậy toán tử này sau khi được thực hiện sẽ cho ra hai chuỗi
mới, mỗi chuỗi đều được thừa hưởng những đặc tính lấy ra từ cha và
mẹ của chúng. Chọn lọc cá thể và lai ghép cho phép giải thuật di truyền
sử dụng những thông tin đã có để tìm kiếm trực tiếp trên những vùng
tốt hơn.
Các ví dụ dưới đây thể hiện các hình thức của lai ghép:

Ví dụ 1 Trước khi lai ghép
1001101
0000110
Sau khi lai ghép tại vị trí giữa số thứ tự 4 và 5, chúng ta sẽ có:

(A) 100| 1101 000| 1101 (B’)
(B) 000| 0110 100| 0110 (A’)

Ví dụ 2
Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
19

 Phát sinh một số ngẫu nhiên r trong miền [0;1].
 Nếu r < p
mu
, tiến hành đột biến tại bít đó.
Các thao tác xử lý này được áp dụng lặp lại cho tới khi các cá thể
con, cháu của chúng tăng trưởng tới kích cỡ mong muốn của quần thể.
Ví dụ 1:
Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
Sinh viên: Trần Thị Thu Hoài_K54C_CNTT
20

100111 sẽ được đột biến thành 100110, trong đó số 1 ở hàng
cuối (tính từ trái) đã được đổi thành 0.

Ví dụ 2:
110110 sẽ được biến đổi thành 111110, trong đó số 0 ở vị
trí thứ 3 (tính từ trái) đã được đổi thành 1.

1.4 Hàm thích nghi
I.4.1 Ánh xạ giá trị hàm mục tiêu sang giá trị thích nghi
Vì hàm thích nghi phải nhận giá trị không âm, do đó cần
phải xây dựng ánh xạ hàm mục tiêu đang xét trong bài toán sang
hàm thích nghi thông qua một hoặc nhiều lần ánh xạ.
Nếu bài toán tối ưu là cực tiểu một hàm đánh giá g(x), việc
chuyển từ hàm đánh giá sang hàm thích nghi để sử dụng với giải
thuật di truyền như sau:

C
max
– g(x) khi g(x) < C

0 trong các trường hợp khác

Ở đây, C
min
là tham số đầu vào, có thể là trị tuyệt đối của
u(x) bé nhất trong quần thể hiện tại hoặc trong k vòng lặp cuối
cùng hoặc là một hàm của biến quần thể.
I.4.2 Điều chỉnh độ thích nghi
Một vấn quan trọng là điều chỉnh số con cháu. Điều này
đặc biệt quan trọng cho một vài vòng lặp đầu tiên, khi một vài cá
thể “siêu” có tiềm năng chiếm lĩnh phần lớn quần thể và làm cho
hội tụ sớm. Điều chỉnh độ thích nghi có thể giúp giải quyết vấn đề
này.
Có nhiều kiểu điều chỉnh khác nhau, tuy nhiên điều chỉnh
tuyến tính là hay gặp nhất. Gọi f là độ thích nghi gốc, f’ là độ thích
nghi đã được biến đổi. Độ thích nghi theo điều chỉnh tuyến tính
được xác định theo quy tắc:

f’ = a*f + b
Trong đó, hệ số a, b được xác định sao cho:
f’
avg
= f
avg

Và f’
max
= C
mult
*f


hàm thành viên. Cấu trúc được thay đổi giữa mỗi chuỗi dựa trên điểm lai,
các kết quả, chúng phải trải qua toán tử lai tạo ra 4 kiểu.
(1) các giá trị ở bên phải của chuỗi được kế thừa từ một chuỗi (A) và các
giá trị bên cạnh được kế thừa từ một chuỗi khác (B), trong đó mỗi giá
trị là bản sao bởi tổng các giá trị của một chuỗi.
(2) Các giá trị ở bên phải của chuỗi được kế thừa từ chuỗi (B) và các giá
trị bên cạnh được kế thừa từ chuỗi (A), trong đó mỗi giá trị là bản sao
của tổng các giá trị của chuỗi.
(3) Cũng giống như cách thức trên, các giá trị bên trái của chuỗi được kế
thừa từ chuỗi (A).
(4) các giá trị bên trái của chuỗi được kế thừa từ chuỗi (B).
Như đã thể hiện ở hình 4, đỉnh của hàm thành viên được thay đổi đối với
mỗi kết quả. Kết quả có thể kế thừa thông tin di truyền ở mức cao hơn từ hai
cha mẹ bởi toán tử lai ghép. Các giá trị thứ hai và thứ ba trong thao tác mã
hoá được thừa kế mà không thay đổi.

2.2 Mutation (Đột biến)
Toán tử đột biến xuất hiện đối với các chuỗi, chúng trải qua toán tử đột biến,
với xác suất P
m
. Toán tử đột biến trong này có nghĩa là hàm thành viên lựa
chọn được cắt bớt, được thể hiện trong hình 5. Chúng ta có thể mong rằng để
làm giảm bớt số luật mờ và thu được cấu trúc nhỏ nhất của mô hình mờ bởi
thao tác này.
Theo cách này, một chuỗi mới được sinh ra bằng các thao tác lai ghép và đột
biến. Các thao tác này nhằn đưa ra một cấu trúc thích hợp của mô hình mờ,
tương ứng với quá trình điều chỉnh thô.

2.3 Fitness function (Hàm thích nghi)