Đ Ạ I HỌC Q U Ố C G IA H À N Ộ I
KHOA CÔNG NGHỆ
N G U Y Ẽ N LONG G IANG
T ÍC H H Ợ• P G I Ả I T H Ư Ậ• T DI T R U Y È N V Ớ I G I Ả I T H U Ậ• T
H U Ấ N L U Y Ệ N M Ạ N G N O R O N T R U Y Ề N T H Ả N G N H ỈÈ U
LỚ P V À Ừ NG D Ụ N G T R O N G DỤ B Á O DỮ L IỆ• U
•
•
C H U Y Ê N N G À N H : C Ô N G N G H Ệ T H Ô N G T IN
M Ả SỐ : 1.01.10
LUẬN VẢN THẠC s ĩ
NGƯ Ờ I HƯỚNG D ẢN K H O A HỌC
PGS.TS. V Ũ Đ Ứ C THI
H À N Ộ I - 2003
í
ITRlifil
I
i____
I
M ỤC LỤC
M ục l ụ c .................................................................................................................................................. I
M ục lục từ viết t á t .........................................................................................................................III
Mở đ ầ u ................................................................................................................................................. I
Những đóng góp chính của luậnv ã n ............................................................................. 2
Câu trúc của luận văn.........................................................................................................2
C hương 1 :
C ác khái niệm CƯ bán về m ạng nơ r ơ n .......................................................4
1.1.
Nơ ron sinh học và mạng nơ ron sinh h ọ c .........................................................4
1.2.
Nơ ron nhân t ạ o .........................................................................................................4
1.3.
Mạng nơ ron nhân tạ o .............................................................................................. 6
1.4.
Thủ tục học của mạng nơ r o n ................................................................................8
1.5.
Phạm vi ứng dụng của mạng nơ r o n ..................................................................10
C hương 2 : Giải thuật di tr u y ề n ..............................................................................................12
2.1. Tổng quan về giải thuật di truyền.......................................................................... 12
2.2. Giải thuật di truyền đơn g iả n ............................................................................... 14
2.3.
Nền tảng toán học của giải thuật di truyền.....................................................20
2.4.
Những cải tiến của giải thuật di truyền.............................................................21
Chưưng 3 : Tích hựp giai thuật di truvền với giái thuật huân luyện mạng nư
ron truvền thảng nhiều lứp................................................................................ 26
3.1.
Mạng nơ ron truyền thẳng và thuật toán lan truyền ngược của sai số ....26
3.1.1.
Kiến trúc cơ b ả n ..................................................................................... 26
3.1.2.
Cơ chế học của mạng nơ ron truyền thảng nhiều lớp................. 28
3.1.3.
Giải thuật lan truyền ngược của sai s ố ............................................29
3. i .4. Một số cải tiến của giải thuật BP.............................................. 40
II
3.2.
Sử dụng giải thuật di truyền kết hợp với giải thuật lan truyền ngược
của sai số trong việc huấn luyện mạng nơ ron truyền thẳng nhiều
lớp........................................................................................................................... 42
3.2.1
Đặt vấn đề................................................................................................ 42
3.2.2. Giải thuật di truyền trong việc huấn luyện mạng nơ ron truyền
thẳng nhiều lớ p ......................................................................................43
3.2.3.
Ghép nối với giải thuật lan truyền ngược của sai s ố .....................45
C h ư ơ n g 4 : Cài đật ch ư ơ n g t r ì n h ..............................................................................................47
4.1.
Cấu trúc dữ liệu và các khai báo cần thiết.....................................................47
4.2.
Thiết kế giải thuật ............................................................................................... 48
C hư ư n g 5 : ứ n g d ụ n g m ạ n g nư ron tru vền th ả n g n h iều lớp tro n g d ự báo d ữ
liệ u .............................................................................................................................................................. 60
5.1.
Sư lược về ứng dụng mạng nơ ron trong dựbáo dữ liệ u ............................. 60
5.2.
Các bước chính trong việc thiết kế mô hình mạng nơ ron dự b á o .......... 61
5.3.
Úng dụng mạng
I1Ơ
ron truyền thẳng nhiều lớp trong dự báo đinh lũ
sông Trà Khúc trạm Sơn G ia n g .........................................................................65
5.4.
Chương trình dự báo dữ liệ u ............................................................................. 68
Kết l u ậ n ...................................................................................................................................................74
Tài liệu th am k h ả o ............................................................................................................................ 76
Phụ l ụ c ......................................................................................................................................................... i
Ill
M Ụ C L Ụ C T Ừ V IẾ T T Ắ T
T ừ v iết tắt
N g h ĩ a t iế n g V iệt
T iế n g A n h tư ư n g ứ n g
GA
Giải thuật di truyền
Genetic algorithm
SG A
Giải thuật di truyền đơn giản
Simple genetic algorithm
BP
Giải thuật lan truvềnngược
Back-Propagation o f Error
của sai sô
M Ở ĐẦU
Dự báo dữ liệu là bài toán quan trọng mang lại nhiều lợi ích thiết thực phục
vụ con người, nó giúp con người nắm bắt được các quy luật vận động trong tự nhiên
và trong đời sông kinh tế xã hội. Trong những năm gần đây, các mạng nơ ron truyền
thẳng nhiều lớp được thực tiễn chứns minh là khá mạnh và hiệu quả trong các bài
toán dự báo và phân tích số liệu, đặc biệt trong các bài toán dự báo sử dụng năng
lượng, dự báo kinh tế. dự báo trong tự nhiên...
Các mạng nơ ron truyền thằng phải được huấn luyện trước khi sử cỉụng đê
thực thi một bài toán dự báo trong thực tế. Với một cấu trúc mạng được chọn, quá
trình huấn luyện mạng là quá trình hiệu chinh các trọng số của mạng và thường
được phát biểu dưới dạng một bài toán tối thiểu hoá hàm sai số huấn luyện. Thú tục
huấn luyện cần một giải thuật tìm kiếm có khả năng tìm lời giải toàn cục, không phụ
thuộc vào quá trình khởi động các trong số ban đầu. Ngoài ra, các giải thuật này
phải có khả năng tìm kiếm hiệu quả trong không gian nhiều chiều do số lượng trọng
sô trong các mạng nơ ron là khá lớn.
Giải thuật GA là giải thuật tìm kiếm dựa trên quá trình chọn lọc tự nhiên, di
truyền và tiến hóa. Các nguyên lý cơ bản của giải thuật được tác giả J.H.Holland đề
xuất lần đầu vào năm 1962, nền tảng toán học của giải thuật GA được tác giả công
hố trong cuốn sách “Sự thích nghi trong các hệ thống tự nhiên và nhân tạo” xuất bản
năm 1975. Giải thuật GA được xem như một phương pháp tìm kiếm có bước chuyển
ngẫu nhiên mang tính tổng quát để giải các bài toán tối ưu hoá. Với những đặc thù
riêng của mình, giải thuật GA được sử dụng khá hiệu quả trong thú tục huấn luyện
mạng nơ ron. Tuy nhiên, giải thuật GA gặp khó khăn về sự hội tụ. Giải thuật GA
đơn giản do Holland đề xuất đã được chứng minh là không bảo đảm sự hội tụ hoặc
không hội tụ tới lời giải toàn cục. Ngoài ra, các giải pháp cải tiến chiến lược thay thế
hoặc toán tử đột biến tuy giúp cho giải thuật GA hội tụ, nhưng sự hội tụ này dễ dẫn
đến hiện tượng hội tụ sớm, nghĩa là giải thuật kết thúc tại một cực trị địa phương mà
không có khả năng tìm thấy cực trị toàn cục.
2
Giải thuật huấn luyện kinh điển lan truyền ngược của sai số (giải thuật BP)
được sử dụng rộng rãi nhất trong việc huân luyện mạng nơ ron truyền thảng. Giải
thuật này đám bảo sự hội tụ nhưng dễ hội tụ tại một cực trị địa phương mà không có
khả năng tìm kiếm cực trị toàn cục. Mặt khác, kết quá huấn luyện của giải thuật này
phụ thuộc vào nhiều yếu tố, đặc biệt là quá trình khởi động các trọng số ban đầu.
Do nhu cầu cấp thiết phải xây dựng một giải thuật vừa có khá năng tìm kiếm
lời giải toàn cục, vừa phải đảm báo sự hội tụ để huấn luyện cho mạng nơ ron truyền
thẳng thực thi một bài toán dự báo trong thực tế, luận văn tập trung nghiên cứu giải
pháp tích hợp giải thuật GA với giải thuật BP trong việc huấn luyện mạng nơ ron
truyền thẳng. Trên cơ sở đó, luận văn trình bày các bước chính để xây dụng mô hình
mạng nơ ron dự báo dữ liệu và ứng dựng mô hình đó trong bài toán dự báo đỉnh lũ
sông Trà Khúc tại trạm khí tượng Sơn Giang.
Những đóng góp chính cua luận văn
•
Luận văn trình bày các vấn để lý thuyết về mạng nơ ron, mạng nơ ron truyền
thẳng nhiểu lớp và thuật toán BP dạng tổng quát để huấn luyện mạng, một số
vấn đề về sử dụng giải thuật BP đế huấn luyện mạng thực thi một bài toán
trong thực tế.
•
Luận văn trình bày các vấn đề lý thuyết về giải thuật SGA và những cải tiến
của giải thuật SGA.
•
Luận văn xây dựng giải pháp tích hợp giải thuật GA với giải thuật BP thành
một giải thuật lai GA - BP dể huấn luyện mạng nơ ron truyền thẳng nhiêu
lớp.
•
Luận văn trình bày ứng dụng giải thuật lai GA - BP trong mô hình mạng nơ
ron dự báo. Giải thuật lai GA - BP đã được cài đặt và thử nghiệm để huân
luyện mạng nơ ron truyền thẳng trong bài toán dự báo khí tượng thuỷ văn.
Cấu trúc của luận vãn
Phấn mớ đầu của luận văn giới thiệu nội dung nghiên cứu, tính cấp thiết của
đề tài và những đóng góp chính của luận văn. Chương 1 giới thiệu các khái niệm cơ
bản và phạm vi ứng dụng cùa mạng nơ ron. Chương 2 giới thiệu về giải thuật SGA
3
và các cải tiến của giải thuật SGA. Chương 3 giới thiệu về mạng nơ ron truyền
thẳng nhiều lớp, giải thuật BP. các vấn đề về sử dụng giải thuật BP và xây dựng giải
pháp tích hợp giải thuật GA với giải thuật BP trong việc huấn luyện mạng nơ ron
truyền thảng nhiều lớp. Chương 4 trình bày mô hình thuật toán và cài đặt giải thuật
lai GA - BP. Chương 5 trình bày các bước xây dựng mô hình mạng nơ ron dự báo và
thứ nghiệm giải thuật GA - BP trong việc huấn luyện mạng nơ ron đê thực thi bài
toán dự báo đinh lũ sông Trà Khúc tại trạm Sơn Giang. Phđn kết luận nêu ra các kết
luận từ luận văn và các hướng nghiên cứu tiếp theo. Phần phụ lục đưa ra một số chức
năng của chương trình được viết bằng Visual Basic.
4
Chương 1
CÁC KHÁI NIỆM C ơ BẨN VỂ M Ạ N G N ơ RON
Chương này đề cập đến các vân đề sau:
1.1.
Nơ ron sinh học và mạng nơ ron sinh học
1.2.
Nơ ron nhân tạo
1.3.
Mạng nơ ron nhân tạo
1.4.
Thủ tục học của mạng nơ ron
1.5.
Phạm vi ứng dụng của mạng nơ ron
1.1. Nơ ron sinh học và mạng nơ ron sinh học
Hệ thần kinh ở người có khoảng 10'° tế bào thần kinh được gọi là các nơ ron
[24]. Mỗi nơ ron gồm có ba phần: thân nơ ron với nhân ở bên trong, một đầu thần
kinh ra và một hệ thống hình cây các đầu thần kinh vào. Độ lớn của các tín hiệu vào
có thể bị thay đổi khi được truyền qua các khớp thần kinh có trên các nhánh thần
kinh vào. Tỷ lệ biến đổi tín hiệu ở khớp thần kinh được gọi là độ khuyếch đụi khớp
và được gọi là các trọng s ố trong các nơ ron nhân tạo. Theo các nghiên cứu về sinh
học, chức năng của hệ thần kinh không phụ thuộc nhiều vào vai trò của từng nơ ron
đơn lé mà phụ thuộc vào cách mà toàn bộ các nơ ron được nối với nhau, gọi là mạng
nơ von sinli học [24],
1.2. Nư ron nhân tạo
Nơ ron nhân tạo là mò hình toán học mô phỏng nơ ron sinh học. Mỗi nơ ron
nhân tạo được gọi là một đơn vị xử lý với chức nâng: nhận tín hiệu vào từ các đơn vị
phía trước (hay một nguồn bên ngoài), tính tín hiệu ra từ các tín hiệu vào và lan
truyền tín hiệu ra sang các đơn vị khác.
5
a
Jl
^
g(at)
H’
a,= Ỹ , w>‘x‘+ e'
Zj = g(aj)
Hình 1. 1: Đơn vị xử lý thứ j
Mồi tín hiệu đầu vào nơ ron thứ j được ký hiệu là Xị với trọng số tương ứng là
Wjị. Đại lượng đo tín hiệu tổng cộng đi vào nơ ron thứ j, ký hiệu là ơj, được xác định
một cách đơn giản như sau :
•
dị là hàm của các tín hiệu X, và các trọng số Wjị, gọi là Hàm kết hợp
•
Hàm kết hợp là tổng các tích của tín hiệu Xị và trọng số tương ứng Wj:
n
a>= ^
W
jiXi 6j
+
Trong đó 0 là một tham số được gọi là ngưỡng của nơ ron. Nếu Wjị>0, nơ ron
được coi là ở trong trạng thái kích thích. Nếu Wjị < 0, nơ ron ở trạng thái kiềm chế.
Quá trình biến đổi giá trị dj thành tín hiệu đầu ra Zj được thực hiện bới hàm
kích hoạt (hàm chuyên) phi tuyến Zj= g(dj). Hàm kích hoạt phải thoả mãn các điều
kiện sau:
•
Tín hiệu đầu ra Zj là không âm với bất kể giá trị nào của dj
•
g là hàm liên tục và bị chặn trong khoảng [0,1 ]
Những hàm thỏa mãn điều kiện trên còn được gọi là các hàm nén theo nghĩa
chúng nén tín hiệu đầu ra vào một khoảns nhỏ. Có khá nhiều hàm thoả mãn các điều
kiện trên, song trong thực tế chi có một số hàm thường được sử dụng trong các
mạng nơ ron như sau
1) Hàm tuyến tính (Linear): g(.x) =
X
2) Hàm ranh giới cứng (Hard-Limiter) : Hàm này chỉ có hai giá trị là 0 và 1,
ngoài ra hàm còn có một giá trị ngưỡng 6. Tín hiệu đầu ra phụ thuộc tổng
tín hiệu đầu vào và giá trị ngưỡng.
ifị x >6 )
if(jc < e )
6
Vi hàm này rất thuận tiện khi đưa câu trả lời có hay không nên nó thường
xuyên được sử dụng cho các tín hiệu ra cuối cùng của mạng.
3)
Hàm ngưỡng logic:
if(.T >
9 )
if(jt <
0)
4) Hàm sigmoid (Sigmoid function (logsig))
gW = \ + e~x
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 bằng
giái thuật BP. 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. Mặt khác, hàm này được ứng dụng cho các bài toán mà đầu ra
mong muốn rơi vào khoang [0,1].
1.3. Mạng nư ron nhân tạo
Khái niệm
Mạng nơ ron nhân tạo là hệ thống bao gồm nhiều nơ ron nhân tạo kết hợp với
nhau. Hệ thống này có khả năng học số liệu và tổng quát hóa từ các số liệu được
Cáu trúc
Mạng nơ ron nhân tạo được biểu diễn bàng một đồ thị gồm một tập các nút
và các cung có hướng, mỗi nút tương ứng với một nơ ron, các cung biểu diễn các
liên kết giữa các nơ ron. Cấu trúc mans nơ ron gồm cơ cấu tổ chức và sơ đồ kết nối.
Cơ cấu tổ chức thường được xác định bởi số lớp mạng và số nơ ron trong mỗi
lớp:
•
Lớp vào : Các nơ ron trong lớp vào gọi là các nơ ron vào, chúng không xử
lý thông tin mà chí mã hóa mẫu đưa vào mạng để xử lý. Thông thường, số
thuộc tính của mẫu đưa vào mạng bằng số nơ ron vào, chính là số đầu vào
của mạng.
•
Lớp ẩn : Các nơ ron trong lớp này gọi là các nơ ron ẩn vì chúng không thể
7
quan sát trực tiếp được. Mạnơ có thê có một hay nhiều lớp ẩn. Chúng cung
cấp các mô hình toán học phi tuyến cho mạng.
•
Lớp ra : Các nơ ron ở lớp này gọi là các nơ ron ra, các nơ ron này mã hoá
giá trị hay khái niệm của các mẫu đưa vào mạng. Ví dụ, trong bài toán
phân lớp. mỗi đầu ra là đại diện cho một lớp các đối tượng.
Sơ đồ kết nối xác định bởi phương thức kết nối giữa các nơ ron trong mạng
[21]:
•
Mạng truyền thẳng : Luồng dữ liệu đi từ các nơ ron vào đến các nơ ron ra
chí được truyền thẳng. Khống có các liên kết từ các nơ ron ra tới các nơ
ron vào trong cùng một lớp hay của các lớp trước đó.
Lớp vào
w (1) "
11 Lớp ân
(2)
wl
Lớp ra
Hình ỉ . 2: Mạng nơron truyền thẳng nhiều lớp (Feed-Forward Neural Network)
•
Mạng hồi quy: Có chứa các liên kết ngược, nghĩa là các liên kết từ nơ ron
lớp ra tới nơ ron lớp vào trong cùng một lớp hoặc các lớp trước đó.
h0
^
Lớp vào
Lớp ẩn
o
Lớp ra
Hình 1.3: Mạng hồi quy (Recurrent Neural Network)
Các thông số cấu trúc của mạng
Dưới đây là các thông số cấu trúc của mạng nơ ron nhân tạo:
•
Sơ đồ kết nối (mạng truyền thảng hay hồi quy)
•
Sỏ tin hiệu vào và số tín hiệu ra
•
Số lớp mạng
•
Số nơ ron trên mỗi lớp
•
Số lượng các trọng số của mỗi lớp
1.4. Thủ tục học của mạng nư ron
Thành phần quan trọng nhất và không thể thiếu của các mạng nơ ron là các
thủ tục học (giải thuật huấn luyện mạng). Có thể chia các thủ tục này thành hai
nhóm chính là h ọ c th a m s ố và h ọ c c ấ u trú c . Cả hai thủ tục học này có thể được thực
hiện đồng thời hoặc tách biệt. Các thủ tục học tham số lại có thể được chia thành ba
lớp nhỏ hơn là h ọ c có th ầ y [24], h ọ c tă n g cư ờ ng [6] và h ọ c k h ô n g c ó th ầ y [16].
Học tham sò
Với một cấu trúc mạng cho trước, các trọng số của mạng (gọi là các tham số
của mạng) phải được xác định trước khi sử dụng mạng để thực thi một nhiệm vụ cụ
thể. Ngoại trừ trường hợp các mạng nơ ron một lớp Hopfield (các trọng số được tính
toán một cách giải tích), thông thường, các trọng số của mạng được khởi tạo ngẫu
nhiên trong một khoáng nhất định. Học tham số là quá trình điểu chỉnh các trọng số
đế mạng nhận biết được mối quan hệ giữa đầu vào và đầu ra mong muốn. Rất nhiều
các thuật toán học được đề xuất để tìm tập trọng số tối ưu đối với mỗi bài toán, các
thuật toán đó có thể chia thành hai nhóm chính : H ọ c c ó th ầ y (Supervised learning)
và H ọ c k h ô n g c ó th ầ y (Unsupervised Learning).
•
H ọ c c ó th ầ y
Mạng được học bằng cách cung cấp cho nó các cặp mẫu đầu vào và đầu ra
inonỉỉ muốn. Sai số giữa các đầu ra thực tế so với các đầu ra mong muốn được thuật
toán sử dụng để hiệu chính các trọng số tronạ mạng.
9
Tập mẫu là tập các cặp véc tơ vào - ra mong muốn M = {x¡,y¡)} được sử
dụng đê luyện mạng nơ ron. Đối với mỗi véc tơ tín hiệu vào Xị, mạng nơ ron tính
toán tín hiệu ra out và so sánh tín hiệu này với tín hiệu ra mong muốn y, để tạo ra tín
hiệu sai số. Tín hiệu sai số này xác định bể mặt sai số là hàm của các trọng số, có
thể dùng như hàm mục tiêu để hiệu chinh các trọng số. Các giải thuật tìm kiếm được
áp dụng trong thủ tục học đê hiệu chỉnh các trọng số sao cho mạng nơ ron có thê sản
sinh ra các tín hiệu ra out với một sai số chấp nhận được so với tín hiệu ra mong
muốn [13].
H ình 1.4. Sơ đồ học có thầy
•
H ọ c không có thầy
Với phương pháp học không có thầy, không có thông tin phản hồi từ môi
trường bên ngoài để chi ra rằng đầu ra out của mạng là đúng hay sai. Mạng nơ ron
phái tự khám phá các đặc trưng, các mối tương quan, tính cân xứng của các mẫu học
một cách tự động. Đối với phần lớn các biến thể của học không có thầy, các đích
trùng với đáu vào. Nói một cách khác, học không có thầy luôn thực hiện một công
việc tương tự như một mạng tự liên hợp, cô đọng thông tin từ dữ liệu vào.
H ọ c càu trú c
Trong phần học tham số, giả định là đã có một cấu trúc mạng. Thú tục học
tham số tinh chinh các giá trị trọng số sao cho mạng hoạt động như mong muốn.
Thu tục học cấu trúc tìm kiếm các tham sô cấu trúc của mạng để tạo ra một mạng
hoạt động tốt nhất. Thực chất, học cấu trúc là việc tìm ra số lớp ẩn và số nơ ron trên
10
mỗi lớp ẩn vì số đầu vào và số đầu ra của mạng là xác định đối với một bài toán cụ
Kết quả học cấu trúc phụ thuộc nhiều vào kết quả học tham số. Do đó, việc
xây dựng một giải thuật tìm kiếm cho thú tục học tham số là cần thiết. Giải thuật tìm
kiếm này phải có khả năng tìm kiếm lời giải toàn cục, tìm kiếm hiệu quả trong
không gian nhiều chiều và có thể sử dụng cho nhiều cấu trúc mạng khác nhau.
Trong những nãm gần đây, một số giải thuật tối ưu toàn cục mang tính tất định và
một số giải thuật mang tính xác suất đã được đề xuất. Các giải thuật mang tính xác
suất hao gồm các giải thuật tiến hóa{3] mà giải thuật GA là một ví dụ điển hình.
Giải thuật GA sẽ được trình bày trong chương 2 của luận văn.
1.5. Phạm vỉ ứng dụng của mạng nơ ron
Mạng nơ ron thường được ứng dụng trong các lĩnh vực như phân loại
(classification), mô hình hóa (modeling), biến đổi (transformation and mapping) và
dự báo các sự kiện phụ thuộc thời gian.
P h an lo ạ i
Phân loại là cách sắp xếp các đối tượng vào các tập hoặc vào các lớp con của
các lứp lớn hơn. Việc phân loại thường được tiến hành nhiều mức giống như phép
toán ra quyết định, phân lớp đối tượng vào nhóm, nhóm con; vào chủng loại, chủng
loại con hoặc vào lớp, lớp con. Một đối tượng có thể đồng thời thuộc vào nhiều lớp
khác nhau, do đó kết quả của việc phân loại là tích của hai hay nhiều quyết định.
M ò h ìn h hóa
Hệ thống phân loại thường đưa ra câu trả lời rời rạc như có, không hoặc một
số nguyên định danh đối tượng đầu vào thuộc lớp nào. Tuy nhiên, việc mô hình hóa
yêu cầu hệ thống phải sản sinh ra các câu trả lời mang tính liên tục. Một số lượng
nhỏ các số liệu thực nghiệm được sử dụng đê xây dựng mô hình, mô hình này có thể
đưa ra các dự báo cho tất cả các đối tượng đầu vào có thể. Việc tìm ra đường cong
phù hợp với các số liệu thực nghiệm là một ví dụ ứng dụng thuộc dạng này. Các ứng
dụng thuộc dạng này phần lớn là thủ tục của một biến vào và một biến ra như sau:
y = f (x, a, b......p)
11
Hàm f chứa một tập các tham số a, b..... p. Các tham số này phải được xác
định bàng việc tối thiểu hóa độ chênh lệch giữa số liệu thực nghiệm và giá trị tính
toán từ mô hình. Mô hình hóa cũng có thể mở rộng cho bài toán nhiều biến vào một biến ra hoặc nhiều biến vào - nhiều biến ra.
Việc mô hình hóa thường được sử dụng cho các đối tượng có ít biến, khoảng
từ 1 đến 10. Điều này có nghĩa là thường sử dụng các mạng nhỏ, thời gian tính cũng
như tài nguyên máy tính ít hơn so với các mạng dùng cho việc phân loại.
B iế n đổi
Việc biến đổi nhằm mục đích nén các đối tượng từ không gian m chiều vào
không gian có số chiều nhỏ, khoáng hai hoặc ba. Qua việc nén các đối tượng này,
chúng sẽ bộc lộ những đặc điểm mà chúng ta không nhận thấy khi chứng ở trong
khỏng gian nhiều chiều. Việc biến đổi tương tự như việc nhóm các đối tượng hay
phân loại. Sự khác biệt không lớn làm nằm ở phương pháp biểu diễn các kết quả.
Những câu hỏi mà việc biến đổi có thể trá lời là bàn đồ của toàn bộ đối tượng như
thế nào, có bao nhiêu vùng trên bản đồ có thể phân biệt được, hình dáng các vùng
đó như thế nào...
Một trong những ứng dụng của biến đổi là tiền xử lý số liệu. Thông qua tiền
xử lý, các đối tượng điển hình được chọn từ tập vô số các đối tượng ngẫu nhiên nhận
được, loại trừ được các đối tượng dư thừa hay trùne lặp. Điều này rất quan trọng khi
chọn các đối tượng làm mẫu học cho mạng truyền thầng huấn luyện bằng giải thuật
BP đề cập ở chương 3.
D ự báo các sự kiệ n p h ụ th u ộ c th ờ i g ian
Lĩnh vực nghiên cứu các quá trình phụ thuộc ihời gian là một trong những
lĩnh vực chính trong nghiên cứu điều khiển quá trình, ở đây, mô hình dự báo được
xây dựng dựa trên một chuỗi số liệu được ghi nhận theo thời gian. Trong mô hình
này, các biến của tín hiệu vào và tín hiệu ra về cơ bản là giống nhau. Chỉ một điều
khác biệt là, tín hiệu vào là các giá trị hiện tại và quá khứ của các biến quá trình, tín
hiệu ra là giá trị dự báo trong tương lai của các biến quá trình đó.
12
Chương 2
G I Ả I T H U Ậ T DI T R U Y Ể N
Chương này trình bày các vấn đề sau:
2.1. Tổng quan về giải thuật di truyền
2.2. Giải thuật di truyền đơn giản
2.3. Nền táng toán học của giải thuật di truyền
2.4. Những cải tiến tiếp theo của giải thuật di truyền
2.1. Tổng quan về giải thuật di truyền
Giải thuật GA thuộc lớp các giải thuật tìm kiếm tiến hóa. Khác với phần lớn
các giai thuật tìm kiếm theo điểm, giải thuật GA thực hiện tìm kiếm song song trên
một tập gọi là quần thể các lời giải có thể. Thống qua việc áp dụng các toán tử di
truyền, giải thuật GA trao đổi thông tin giữa các cực trị và do đó làm giám thiếu khá
năng kết thúc giải thuật tại một cực trị địa phương. Trong thực tế, giải thuật GA đã
được áp dụng thành công trong nhiều lĩnh vực bao gồm cả thú tục huấn luyện mạng
nơ ron [7, 11].
N ộ i d u n g g ia i th u ậ t d i truyền
Giải thuật GA lần đầu tiên được tác giả J. H. Holland giới thiệu vào năn 1962
[12, 14]. Giải thuật GA mô phỏng quá trình tồn tại của các cá thể có độ phù hợp tốt
thông qua quá trình tiến hóa trong tự nhiên, sao cho khi thực thi giải thuật, quần thể
các lời giải ban đầu tiến hoá dần tới lời giải mong muôn.
Giải thuật GA duy trì một quần thể các lời giải có thể của bài toán tối ưu hóa.
Mỗi lời giải gọi là một cá thế hay một nhiễm sắc thể, thường được mã hóa dưới dạng
một chuỗi các gen, giá trị của các gen có trong chuỗi được lấy từ một báng các ký tự
được định nehĩa trước. Mỗi chuỗi gen được liên kết với một giá trị gọi là giá trị thích
nghi, còn gọi là độ phù hcrp của chuỗi. Độ phù hợp của mỗi chuỗi gen đánh giá độ
13
thích nehi của nó với môi trường (độ tốt xấu của lời giải) và được dùng trong quá
trình chọn lọc.
Quần thể mới được tạo ra bàng cách sử dụng các quá trình chọn lọ c , la i ghép
và đột biến. Ọuá trình chọn lọc sao chép các cá thẻ có độ phù hợp tốt vào một quần
thế tạm thời được gọi là quần thể bố mẹ. Các cá thê trong quần thể bố mẹ được ghép
đôi một cách ngẫu nhiên và tiến hành lai ghép tạo ra các cá thể con. Sau khi tiến
hành quá trình lai ghép, giải thuật GA mô phỏng một quá trình khác trong tự nhiên
là quá trình đột biến, trong đó các gen của các cá thể con tự thay đổi giá trị với một
xác xuất nhỏ.
Như vậy, giải thuật GA xuất phát với tập lời giải ban đầu, thông qua nhiều
hước trons quá trình tiến hoá hình thành các tập lời giải mới tốt hơn, và cuối cùng
tìm ra lời giải đủ tốt chấp nhận được (lời giải gần với lời giải tối ưu).
Dưới đây là sơ đồ khối của giải thuật di truvền
Ỉ-ÌHT Sinh quàn
ti Ifc* bdl IdU
:
Hh'
♦
Co Cd thê" nào
đạt đẽn ÒI gứí
tối ưu
xar 1nh l o
th ú I IJII -ùđ
cac cá thế trorg
quan thế
ìr r h \ray
ớùa?
lơ
j
----
T
T
Xây dưhq quár
ttip’ mríi
ằỵ dư’nq thé hẻ t ẻ tiẽp
2.1. Sơ đổ khối của giải thuật di truyền
- ?i-
14
Các bước chính trong việc áp dụng giải thuật di truyền
Để áp dụng giải thuật GA giải một bài toán trong thực tế, các bước sau đày
cần được thực hiện:
Bước l : Chọn tập lời giải ban đầu cho bài toán.
Bước 2 : Mã hoá các lời giải dưới dạng các chuỗi, thông thường các lời giải
được mã hóa thành các chuỗi nhị phân.
Bước 3 : Tìm hàm số thích nahi (hàm phù hợp) cho bài toán và tính giá trị
thích nahi cho mỗi lời g iả i, còn sọi là giá trị độ phù hợp.
Bước 4 : Dựa trên giá trị thích nshi của mỗi lời giải đê’ thực hiện chọn lọc
(selecttion) và tiến hóa các lời giải. Các phương pháp tiến hóa gồm la i ghép
(crossover) và đột biến (mutation).
Bước 5 : Tính các giá trị thích nghi cho các lời giải mới và loại bỏ các lời giải
kém nhất, chỉ giữ lại một số nhất định các lời giải
Bước 6 : Nếu chưa tìm được lời giải tối ưu hay chưa hết hạn chu kỳ xác định
thì trở lại Bước 4 để tìm lời giải mới.
Bước 7 : Tim được lời giải tối ưu chấp nhận được hoặc nếu chu kỳ cho phép
đã chấm dứt thì báo cáo kết quả tính được.
Có nhiều lựa chọn khác nhau cho từng vấn đề trên. Phần tiếp theo sẽ đưa ra
cách lựa chọn theo J.H.Holland khi thiết kế phiên bản giải thuật GA đầu tiên. Giải
thuật này được gọi là giải thuật di truyền đơn giản (SGA) [12,14]
2.2. G iải thuật di truyền đon giản
J. H. Holland sử dụng mã hóa nhị phân để biểu diễn các cá thể, lý do là phần
lớn các bài toán tối ưu hóa, lời giải đều có thể được mã hóa thành chuỗi nhị phân
khá đơn giản [14], Mỗi lời giải được mã hóa thành một chuỗi bít, mỗi chuỗi bít sau
dó được giải mã để lấy lại giá trị thực và giá trị hàm mục tiêu được tính theo giá trị
thực này. Tuỳ từnR bài toán cực tiểu hay cực đại, giá trị hàm mục tiêu được biến đổi
thành giá trị thích nghi cho từng chuỗi. Quần thể chuỗi ban đầu được khới động
ngẫu nhiên và sau đó được tiến hóa từ thê hệ này sang thế hệ khác bàng cách sử
dụng ba toán tử :
15
Chọn lọc (selecttion)
L a i tạo (crossover)
Đ ột biến (m u ta tio n )
C họn lọc
Chọn lọc là việc lựa chọn các cá thê để tham gia vào các pha tiếp theo của
quá trình tiến hóa, việc lựa chọn này phụ thuộc vào giá trị thích nghi của cá thê’ đó,
nghĩa là những cá thể nào có giá trị thích nghi cao hơn sẽ có khả năng có nhiéu con
cháu hơn trong các thế hệ tiếp theo. Giá trị thích nghi quyết định sự tồn tại hay diệt
vong của một cá thể. Giá trị thích nghi được tính từ hàm thích nghi, việc ánh xạ từ
hàm mục tiêu sang hàm thích nghi được trình bày ở phẩn sau.
Mô hình chọn lọc thường được dùng là bánh xe xổ số (roulette wheel
selection). Giải thuật GA sử dụng một vòng tròn trong đó mỏi cá thể chiếm một
phần tương với
của cá thể
Vị
độ
rộng
là
xác suất chọn lọc của mỗi cá thể. Xác suất chọn lọc
Pi
được tính theo công thức p,= eval(v;)/F, trong đó eval(vị) là giá trị thích
nghi của cá thể
Vị,
F là tổng giá trị thích nghi của toàn quần thể F = ịe v a lịv j).
Mỗi khi thực hiện một lần quay vòn tròn, một ứng cử viên được chọn cho
việc lai ghép. Việc quay vòng tròn được thực hiện qua những bước sau:
Bước I : Đánh số các cá thể trong quần thể. Tính tổng giá trị thích nghi của
toàn quần thể và gọi nó là tổng thích nghi (Total fitness).
Bước 2 : Sinh một số ngẫu nhiên n trong khoảng từ 0 đến tổng thích nghi.
Bước 3 : Trả lại cá thể đầu tiên trong quần thể có giá trị thích nghi của nó
cộng với giá trị thích nghi của các cá thể trước đấy lớn hơn hoặc bằng n.
L a i ghép
Toán tử chọn lọc nhằm tìm ra những cá thể tốt nhất nhưng không tạo ra cá
thê mới. Tuy vậy, trong tự nhiên, các con sẽ thừa hưởng di truyền những đặc tính tốt
từ cả cha và mẹ. Toán tử tác động trên các cá thể cha và mẹ để tạo ra các con lai tốt
được gọi là lai ghép. Chúng chỉ được áp dụng lên cặp cha mẹ được chọn với xác suất
lai ghép ký hiệu là PLT0SS[14], Xác xuất này cho chúng ta số lượng Pcross*pop_size cá
16
thể được dùng cho hoạt động lai ghép với pop_size là kích thước quần thế. Ngoài
các cá thế đó ra. các cá thể con là bản sao trực tiếp từ cha mẹ.
Toán tử lai ghép trong giải thuật SGA là toán tử lai ghép một điểm cắt. Giả sử
chuỗi cá thể có độ dài L (chuỏi có L bít), toán từ lai ghép được tiến hành qua hai
giai đoạn là :
•
Phát sinh một số ngẫu nhiên r trong miền [0; 1]
•
Nếu r < Pcrosschọn cá thể đó đê lai ghép.
Sau đó. kết hợp các cá thể được chọn một cách ngẫu nhiên. Với mỗi cặp cá
thể, phát sinh một số ngẫu nhiên pos từ miền [1, L]. Số pos báo hiệu vị trí của điểm
lai ghép. Hai cá thể :
(b|b2...b p0SbpHS+|...b L) và (ccc2... Cpos^pos+1 • • -CL)
d ư ợ c th a y t h ế bởi c ặ p c o n c h á u :
( b , b 2. . . b p
- Xem thêm -
.PDF 
89 
101 
63 
