Kết hợp mạng nơ ron và giải thuật di truyền ứng dụng cho lớp bài toán nhận mẫu
ISSN 2354-0575
KẾT HỢP MẠNG NƠ RON VÀ GIẢI THUẬT DI TRUYỀN
ỨNG DỤNG CHO LỚP BÀI TOÁN NHẬN MẪU
Nguyễn Quang Hoan1, Nguyễn Thị Trang2, Nguyễn Thị Huyền1,
Trương Quốc Khánh3, Nguyễn Thị Hoa4
1 Trường Đại học Sư phạm Kỹ thuật Hưng Yên
2 Trường Đại học Công nghệ Đông Á
3 Trường Trung Cấp nghề số 1 Hà Nội
4 Trường Cao đẳng Nghề Công nghệ Cao, Hà Nội
Ngày nhận: 15/06/2016
Ngày sửa chữa: 10/08/2016
Ngày xét duyệt: 19/09/2016
Tóm tắt:
Bài báo trình bày phương pháp tích hợp giải thuật di truyền (Genetic Algorithm: GA) và mạng
nơron (Neural Network: NN) lan truyền ngược (Back Propagation: BP) để tránh cực tiểu cục bộ trong kỹ
thuật học theo phương pháp hạ Graddient cho lớp bài toán nhận mẫu hoặc dự báo. Thực hiện vấn đề đó,
quá trình học NN được chia thành hai pha: pha đầu sử dụng GA để xác định tập trọng số (weights) khởi đầu
của mạng nơron nằm được vùng tối ưu; pha hai: dùng thuật toán lan truyền ngược để thu được tập trọng
số tối ưu toàn cục cuối cùng. Các thử nghiệm phương pháp cho nhận mẫu vân tay được thực hiện. Kết quả
học bằng cách tích hợp GA và mạng nơ ron được so sánh với việc học của mạng nơ ron không tích hợp và
định hướng nghiên cứu tiếp được đề xuất
Từ khóa: Mạng nơron, thuật toán lan truyền ngược, giải thuật di truyền, nhận mẫu, dự báo.
1. Giới thiệu
Có nhiều phương pháp và công cụ khác nhau
thuật toán lai và đột biến.
4. Loại NST có độ thích nghi kém,thay NST
mới vào quần thể.
để giải bài toán dự báo và nhận mẫu [4, 5, 13, 14,
15]. Để giải quyết những trường hợp phi tuyến tốt,
hoặc tránh rơi vào tối ưu cục bộ, chúng ta có thể
dùng NN lai với GA [6, 7, 8, 9, 10, 11, 15].
NN có nhiều cấu trúc khác nhau, nhưng
thường dùng nhất là mạng BP [2, 4, 5] do hội tụ
nhanh. Hạn chế của nó là kết quả học chỉ tìm được
tập trọng tối ưu cục bộ [8]; do đó, một biện pháp là
dùng GA để xác định giá trị các trọng số khởi đầu
thuộc vùng tối ưu toàn cục, đảm bảo mạng có bộ
trọng số tối ưu toàn cục.
Nội dung bài báo này là thử nghiệm kết hợp
NN và GA để giải lớp bài toán nhận mẫu hoặc lớp
bài toán dự báo.
2. Giải thuật di truyền
GA được đề xuất như là quá trình tìm kiếm
dựa trên luật chọn lọc tự nhiên và di truyền học. Thuật
toán được sử dụng để tìm các giá trị trọng số ban
đầu quanh vùng tối ưu của mạng nơ ron. Hình 1 mô
Hình 1. Chu trình hoạt động của GA
5. Tính các giá trị thích nghi cho NST mới
’t
tả quá trình hoạt động của của GA [6] với các bước: f(wij ) và chèn vào quần thể.
1. Khởi tạo ngẫu nhiên tạo một quần thể ban
6. Tăng số lượng thế hệ t nếu chưa đạt điều
đầu (thế hệ 0): P0 = (w11 , w12 ,…, w1j ) trong đó wij : kiện dừng và lặp lại từ bước 3. Khi đạt điều kiện
tập các NST (trọng số) thế hệ 0.
kết thúc thì dừng và cho NST tốt nhất (là bộ trọng
0
0
0
0
t
2. Tính giá trị từ hàm thích nghi f(wij ) của số cần tìm).
mỗi NST wij trong quần thể Pt hiện tại.
t
3. Dựa vào giá trị thích nghi, tạo ra các NST 3. Kết hợp mạng nơron với GA
mới bằng cách chọn lọc các NST cha mẹ, áp dụng
Cho cấu trúc NN. Dùng GA tìm tập các trọng
Khoa học & Công nghệ - Số 11/Tháng 9 - 2016
Journal of Science and Technology
57
ISSN 2354-0575
số nằm trong miền dẫn chúng tới tối ưu toàn cục
Bước 6. Thay thế hệ cũ bằng thế hệ mới nếu
cho NN. Một quần thể gồm N chuỗi trọng số của chưa thỏa mãn điều kiện dừng.
mạng được khởi tạo ngẫu nhiên. Sau G thế hệ tiến
hoá, cá thể tốt nhất trong G thế hệ được giữ lại. Các Giai đoạn 2: Pha học dùng thuật toán lan truyền
cá thể này, sau đó, được giải mã và đưa vào NN để ngược
học tiếp. Trong hệ tích hợp này, quá trình học có
thể phân thành hai giai đoạn huấn luyện. Giai đoạn
Bước 0 (Khởi tạo)
Chọn ngưỡng lỗi Ethreshold=0. Khởi tạo giá trị
đầu sử dụng GA với hàm thích nghi (hàm mục tiêu) các trọng số: lấy kết quả thu được từ pha 1.
được xác định theo:
Bước 1 (Bắt đầu một chu kỳ học)
Áp dụng véc tơ vào đối với lớp vào k của
NN (k=1): kyi = kOuti = 1Outi = xi , 6i;
Bước 2 (Lan truyền tiến)
n
n
m
1
1
2
2
/
/
/
E =
_
di - yi
i
=
(di - f( (wij xj - w0 )))
2 i = 1
2 i = 1
j = 1
(1)
Lan truyền tiến các tín hiệu vào qua mạng,
cho đến khi nhận được các giá trị ra của mạng (ở
lớp đầu ra) KOuti
Bước 3 (Tính toán lỗi đầu ra)
Tính sai số ra của mạng và tín hiệu lỗi kδi của
mỗi nơ ron ở lớp ra i.
trong đó: di và yi tương ứng là đầu ra mong muốn
và thực tế của nơron thứ i; xj là đầu vào thứ j; wij là
trọng số liên kết giữa đầu vào thứ j đến đầu ra thứ i.
Giai đoạn hai sử dụng thuật toán lan truyền ngược
để tìm các trọng số tối ưu toàn cục từ kết quả của
giai đoạn 1.
n
2
1
(k)
k
Giai đoạn 1: Pha học dùng GA
Thuật toán:
/
`
j
E =
di - Outi
2 i = 1
k
`
'
j
k
(k)
k
Neti
Bước 0. Khởi tạo các NST ngẫu nhiên (trọng
số khởi đầu) cho thế hệ hiện tại và các tham số làm
việc. Đặt NST đầu tiên là tốt nhất best_chromosome ở đây,
Bước 1. Lặp từ i=1 đến kích thước quần thể
n. Khởi tạo sub_total_fitness bằng 0 và sub_best_
chromosome là rỗng.
di = di - Outi f
2f
f, /
; kui kNeti
=
(4)
2wij
Bước 4 (Lan truyền ngược lỗi)
Lan truyền ngược sai số để cập nhật trọng số
và tính tín hiệu sai số k-1δi cho các lớp trước.
Bước 2. Lặp từ j=1 đến độ dài của NST m
- Thực hiện thủ tục truyền thẳng cho mạng 3
lớp sử dụng hàm tương tác dạng sigmoid:
k
k
k-1
3 W = h. di .
Outj ;
(5)
ij
k
k
k
_
i
_ i
_ i
t
W t + 1 = W t +3 W
m
ij
ij
ij
1
k-1
k
kWji dij
/
u =
wij xj - w0
;
/
(ui) =
j
k-1di = f'`
;
Neti
(2)
i
1 + e-m.u
j
i
j = 1
Bước 5. Kiểm tra tập học đã được sử dụng.
Nếu tập dữ liệu học đã được dùng, chuyển đến Bước
6; ngược lại, chuyển đến Bước 1.
- Tính hàm mục tiêu (1)
- Tính tổng sai số total_fitness bằng cách tích
lũy sub_total_fitness
Bước 3. Lưu best_chromosome vào sub_
best_chromosome
Bước 4. So sánh các sub_best_chromosome
Đặt sub_best_chromosome lớn nhất là best_chro-
mosome.
Bước 6 (Kiểm tra lỗi tổng thể)
Nếu lỗi tổng thể E đạt ngưỡng lỗi chấp nhận
(Ethreshold), quá trình học kết thúc và trả về các trọng
số tối ưu. Ngược lại, gán lại lỗi bằng 0, bắt đầu chu
kỳ học mới (quay về Bước 1).
Bước 5. Lặp từ i=0 đến kích thước quần thể n
- Khởi tạo sub_total_fitness bằng 0 và sub_
best_chromosome là rỗng;
4. Ứng dụng
Trong bài báo, chúng tôi thử nghiệm phương
pháp tích hơp đã nêu cho nhận mẫu vân tay theo
các đặc trưng mức hai. Bài toán dự báo cũng có thể
dùng GA tương tự để tính trọng ban đầu.
4.1. Các đặc trưng vân tay
Dấu vân tay là một thể hiện bằng những
đường vân đầu ngón tay của một người. Có thể chia
đặc trưng vân tay (hình 2 a, b, c) thành ba mức độ
(level): level 1: mẫu – Pattern); level 2:các điểm
đầu, kết thúc, chạc ba – Minutaie; level 3: các lỗ
chân lông và kiểu vân – Pores and Ridge Shape.
Hầu hết các hệ thống nhận mẫu vân tay sử dụng các
đặc trưng mức 1 và mức 2 [5, 6, 11, 12].
- Lặp từ j=1 tới độ dài NST m
* Chọn các NSTcha mẹ sử dụng phương
pháp chọn theo bánh xe Roulette
* Áp dụng các phép lai và đột biến
- Lặp từ k=1 đến độ dài nhiễm sắc thể:
* Thực hiện thủ tục truyền thẳng cho mạng
* Tính các giá trị hàm mục tiêu cho các NST
cha mẹ.
- Tính sub_total_fitness bằng cách tích lũy
giá trị hàm mục tiêu của mỗi nhiễm sắc thể.
- Lưu best_chromosome vào sub_best_
chromosome
Journal of Science and Technology
58
Khoa học & Công nghệ - Số 11/Tháng 9 - 2016
ISSN 2354-0575
Chọn 1000 nơron cho lớp ẩn qua thực ng-
hiệm từ những kết quả tối ưu và giá trị lỗi trong quá
trình huấn luyện.
c. Lớp ra: chọn hàm tương tác đầu ra của lớp
ra giống các lớp khác (2), khi đó:
l
l
m
/
q = 1
/
q = 1
/
j = 1
e
o
neti =
wiq zq =
wiq f
vqj xj
(9)
l
l
m
/
/
/
e
o
f
e
o
p
y = f net = f
wiq zq = f
wiq f
vqj xj
_
i
i
i
q = 1
q = 1
j = 1
Trong đó: i là nơ ron thứ i trong n nơ ron đầu
Hình 2. Các mức độ đặc trưng của vân tay
ra được chọn tuỳ thuộc vào cách mã hoá đặc trưng
đầu ra. Trong bài toán, chọn số nơ ron lớp ra n = 10,
vì 2n = 210 lớn hơn số mẫu thử.
Bài báo sử dụng mức hai. Mức hai có nhiều
kỹ thuật trích chọn đặc trưng khác nhau. Trong
phạm vi thử nghiệm trên máy tính xách tay, chúng
tôi chọn Core hoặc Delta (Hình 2.d) làm gốc tọa
độ, chia vân trên một ngón tay thành 4 góc phần
tư, mỗi góc phần tư trong mặt phẳng hai chiều; tìm
điểm trung bình của các giá trị kết thúc, bắt đầu
hoặc chạc ba của vân tay. Điểm trung bình có 2 giá
trị theo tọa độ trục (xi, yi), 4 góc phần tư sẽ có 8 giá
trị đặc trưng trở thành 8 đặc trưng đầu vào x = [x1 ,
x2 , …, x8 ] cho NN.
4.2.2. Nhận mẫu vân tay kết hợp NN và GA
Nhận mẫu được thực hiện trong 4 thao tác:
a) Tải hình ảnh vân tay cần nhận dạng từ tập
cơ sở dữ liệu ảnh thu thập được đã chuẩn hóa
4.2. Nhận dạng vân tay
4.2.1. Thiết kế mạng nơron nhân tạo
Chọn BP NN ba lớp-đủ khả năng nhận biết
các mẫu đầu vào với hàm tương tác đầu ra liên tục,
khả vi, bị chặn [4, 14, 15] như (2).
Hình 4. Cửa sổ tải hình ảnh vân tay
b) Học theo GA: (Hình 4. Chọn Nút: “Thuật
toán GA”): gọi chương trình học theo GA:
- Cho trọng số khởi đầu (xem Hình 5, cột
bên phải “Kết quả khởi tạo”
- “Kết quả huấn luyện” ở Hình 5 cột trái.
Hình 3. Cấu trúc NN ba lớp lan truyền ngược
a. Lớp vào (Input Layer)
Với tập mẫu đầu vào x, nơron thứ q của lớp
ẩn được xác định:
m
/
netq =
vjq xj
j = 1, 2,…, m ; q = 1, 2,…, l (6)
j = 1
trong đó m là số nơ ron của lớp vào, q là số nơ ron
thứ q trong l nơ ron của lớp ẩn.
b. Lớp ẩn. Đầu ra của lớp ẩn
m
/
zq = f(netq) =
(7)
(8)
e
o
f
vqj xj
j = 1
trong đó, f(.) là hàm tương tác đầu ra (2).
1
f(netq) =
1 + e-mnetq
Hình 5. Thực hiện thuật toán GA: pha học 1
Khoa học & Công nghệ - Số 11/Tháng 9 - 2016
Journal of Science and Technology
59
ISSN 2354-0575
4.2.3. Thực nghiệm nhận mẫu
Kết quả học dùng thuật toán GA1 (Hình 6).
Để áp dụng thực nghiệm nhận mẫu vân tay
sử dụng phương pháp trên (Hình 8), chúng tôi áp
dụng hệ thống cho Trường Đại học Công nghệ
Đông Á, cơ sở dữ liệu vân tay là của các nhân viên
Nhà trường trên 40 nhân viên và gần 400 mẫu vân
tay. Các thông tin của các nhân viên và mẫu vân tay
được lưu trữ trong cơ sở dữ liệu của hệ thống. Trong
400 mẫu, 300 mẫu (75%) vân tay dùng cho việc học
và 100 (chiếm 25%) mẫu dùng để thử (Test). Mẫu
thử chứa cả mẫu được học và mẫu chưa được học
để xem xét khả năng suy diễn của NN. Các mẫu đã
tiến hành tiến xử lý bằng các kỹ thuật xử lý ảnh, và
chuẩn hóa độ tương phản, khuôn dạng [1, 3].
Hình 6. Kết quả khởi tạo trọng số thực hiện bởi GA
4.3. Kết quả đạt được
Kết quả này dùng làm khởi tạo cho pha 2:
học dùng thuật toán lan truyền ngược của NN. Trên
Hình 6, số lần học tiến hành được hiển thị trên màn
hình tương tác. Tỷ lệ lai được thử với 25% và đột
biến 1% của NST [11].
c) Huấn luyện NN: pha học 2. Nhấn nút
“Huấn luyện với ANN”, ta có kết quả thử nghiêm
của một lần học như Hình 7.
Thử nghiệm tiến hành trên máy tính có cấu
hình: Intel® Core™i5–6500U CPU 2.3 GHz.
a) Thời gian thực hiện:
Phương pháp tích hợp mạng nơron và giải
thuật di truyền GA–NN có thời gian thực hiện
nhanh hơn phương pháp nhận mẫu bằng NN (Bảng
1). Điều này dễ giải thích vì GA–NN đã được đưa
về vùng tối ưu trước. Trong một số trường hợp GA–
NN đã cho đúng tập trọng tối ưu, nên thời gian học
pha hai nhanh. Tuy nhiên, thời gian học ở giai đoạn
một với GA dài. Có thể đề xuất chiến lược học: cho
pha hoc của GA học lần đầu (có thể kéo dài), các
mẫu vân tay cập nhật có thể bỏ qua giai đoạn này,
tránh thời gian kéo dài.
Bảng 1. Thời gian nhận mẫu của ANN, GA-NN
Mẫu
Thời gian thực hiện nhận dạng (s)
ANN
17
GA - NN
Mẫu 1
Mẫu 2
Mẫu 3
Mẫu 4
Mẫu 5
10
15
12
16
17
33
Hình 7. Học bằng thuật toán lan truyền ngược
23
36
d) Nhận dạng. Mẫu nhận dạng được đưa vào
trên NN đã học. Mẫu được gán tên người, giới tính
(Nam/nữ), ngày sinh, số chứng minh thư, địa chỉ…
42
Hình 9. So sánh thời gian thực hiện nhận mẫu của
Hình 8. Nhận mẫu vân tay bằng mạng nơ ron với GA
ANN và GA-NN
Journal of Science and Technology
60
Khoa học & Công nghệ - Số 11/Tháng 9 - 2016
ISSN 2354-0575
5. Kết luận
b) Tốc độ nhận mẫu (%):
NN tích hợp với GA có khả năng tối ưu quá
trình học toàn cục, giúp ta xác định tốt bộ trọng số
ứng với lỗi ra nhỏ nhất. NN tích hợp có những kết
quả tốt hơn so với không tích hợp, tuy nhiên, thời
gian học giai đoạn một (với GA khá lớn). Mỗi lần
dùng GA, có thể cho kết quả khác nhau phụ thuộc
vào điểm lai, quần thể lai và đột biến. Mỗi lần học
pha1 của GA cho kết quả, thời gian học, số vòng lặp
là khác nhau. Trong thực nghiệm lai GA-NN, chúng
tôi giải quyết bài toán nhận mẫu và hoàn toàn có thể
sử dụng nó cho lớp bài toán dự báo và các bài toán
khác kiểu tương tự.
Tốc độ nhận mẫu của phương pháp GA-NN
cao hơn so với phương pháp ANN.
Bảng 2. Tốc độ nhận mẫu của ANN và GA-NN
Mẫu
Tốc độ nhận dạng (%)
ANN
86
GA - NN
98
Mẫu 1
Mẫu 2
Mẫu 3
Mẫu 4
Mẫu 5
82
98.22
99.21
99.33
98.85
90
92
89
Hướng tiếp theo, chúng tôi sẽ nghiên cứu cải
tiến để chạy trên máy tình cấu hình lớn với nhiều
tham số và cấp độ vân tay mức ba. Các thử nghiệm
sẽ cố gắng phong phú số mẫu, chi tiết hơn. Các kết
quả sẽ được thông báo trong những công bố tiếp
theo.
Hình 10. Tốc độ nhận mẫu của ANN và GA-NN
Tài liệu tham khảo
[1]. Nguyễn Quang Hoan, Xử lý ảnh, Học viện Công nghệ Bưu chính Viễn thông, 2013.
[2]. Nguyễn Quang Hoan, Vũ Thị Giang. Mạng nơron Kohonen và khả năng ứng dụng. Tạp chí
Khoa học Công nghệ Quân sự, 2013.
[3]. Lương Mạnh Bá, Nguyễn Thanh Thuỷ, Nhập môn xử lý ảnh số, NXB Khoa học và Kỹ thuật, 2003.
[4]. Nguyễn Quang Hoan, Nguyễn Thị Thảo, Vũ Thành Vinh, Nhận mẫu ký tự sử dụng mạng nơron
lan truyền ngược, Tạp chí Khoa học và Công nghệ, Trường Đại học Sư phạm Kỹ thuật Hưng Yên,
số 7/9/2015.
[5]. Đỗ Thanh Long, Nguyễn Quang Hoan, Nguyễn Thị Hoa, Hệ thống nhận mẫu vân tay sử dụng
mạng nơron nhân tạo, Tạp chí Khoa học và Công nghệ, Trường Đại học Sư phạm Kỹ thuật Hưng
Yên, số 7/9/2015.
[6]. Le Hoai Bac, Le Hoang Thai, Neural Network & Genetic Algorithm Application Handwritten
Character Recognition, Tạp chí Tin học và Điều khiển học, T. 17, S. 4, 2001.
[7]. Sowmya Ravi, Neeraja Ganesan, Vandita Raju, Search Engines Using Evolutionary Algorithms,
International Journal of Communication Network Security ISSN: 2231 – 1882, Volume-1, Issue-4,
2012.
[8]. David J. Montana, Neural Network Weight Selection Using Genetic Algorithms, Bolt Beranek
and Newman Inc. 70 Fawcett Street, Cambridge, MA 02138, 2013.
[9]. Liu Han-li, Li Lin, Zhu Hai-hong, Genetic Neural Network Based Data Mining and Application
in Case Analysis of Police Office, School of Resource and Environment Science, Wuhan University,
129 Luoyu Road, Wuhan, P.R.China, 430079, 2011.
[10]. David J. Montana and Lawrence Davis, Training Feedforward Neural Networks Using Genetic
Algorithms, BBN Systems and Technologies Corp.10 Mouiton St.Cambridge, MA 02138, 2012.
[11]. Dhia A. Alzubaydi, Thikra M. Abed, Genetic Algorithm and Probabilistic Neural Networks for
Fingerprint Identification, International Journal of Computer Applications (0975 – 8887), Volume
101– No.11, September 2014.
Khoa học & Công nghệ - Số 11/Tháng 9 - 2016
Journal of Science and Technology
61
ISSN 2354-0575
[12]. Roli, Priti Shgal and Punam Bedi, Minutiae Extraction from Fingerprint Images - a Review,
IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 5, No 3, 2011.
[13]. Tu Le Anh, Hoan Nguyen Quang, Thai Le Son, Hierarchy Supervised SOM Neural Network
Applied for Classification Problem, Journal of Computer Science and Cybernetics, V.24, N.3 (2014),
pp. 278-290.
[14]. Hoan Nguyen Quang, Tu Le Anh, Clustering Hierarchical Data Using SOM Neural Network,
ICCASA 2012, LNICST 109, pp. 282–289, 2013.
[15]. Rajendra Arvind Akerkar and Priti Srinivas Sajja, Knowledge-Based Systems, Jones and
Bartlett Publisher, 2010.
NEURAL NETWORKS AND GENETIC ALGORITHM
FOR FINGERPRINT PATTERN RECOGNITION
Abstract:
In this paper, we integrate Genetic Algorithm (GA) with Backpopagation Neural Network (BP
NN to remove local minimums when using Gradient Recent technique for some problems such as pattern
recognitions or forecasting. With this method, learning process can be divided in two phases: first phase using
GA to define initial NN weighs; second phase using traditional BP Algorithm to receive global optimization
weights. We to make some experiments using the intergrated technique on Fingerprint Recognition and to
compare the results of the technique with the non-ingterated NN.
Keywords: Backpropagation, Genetic Algorithm, Pattern Fingerprint Recognition, Forecasting.
Journal of Science and Technology
62
Khoa học & Công nghệ - Số 11/Tháng 9 - 2016
6 trang
26080
Free
Bạn đang xem tài liệu "Kết hợp mạng nơ ron và giải thuật di truyền ứng dụng cho lớp bài toán nhận mẫu", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- ket_hop_mang_no_ron_va_giai_thuat_di_truyen_ung_dung_cho_lop.pdf
