1
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ứng 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ử dụ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 chỉnh 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 bố
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ụ, nhng 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
3
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 đỉnh 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ạng 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.
x1
...
xn
j
wj0
wj1
j
aj
wjn
n
aj = wjixi +j
g(aj)
zj
zj = g ( a j )
i =1
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à xi với trọng số tơng ứng là
6
Vì 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( x )
if( x < )
1
g ( x) =
0
4) Hàm sigmoid (Sigmoid function (logsig))
g ( x) =
1
1 + ex
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 khoảng [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 họ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
h0
x1
bias
y1
h1
x2
y2
h2
xl
w
Lớp vào
(1 )
ji
hm
y1
yn
hm
Lớp ẩn
Lớp ra
Hình 1.3: Mạng hồi quy (Recurrent Neural Network)
8
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ố tìn hiệu vào và số tín hiệu ra
toán sử dụng để hiệu chỉnh các trọng số trong 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 i,yi)} đợc sử dụng
để luyện mạng nơ ron. Đối với mỗi véc tơ tín hiệu vào xi, 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 yi để 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 chỉnh 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].
Dữ liệu huấn luyện
Đầu vào
Đầu ra mong muốn
Đích
Mạng
Vào
Sai số
+
Ra
Thay đổi
Trọng số
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 bao 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 vi ứ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.
Phân 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ình 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
Giải thuật di truyề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 giải 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 dung giải thuật di 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 nghĩ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ù hợp của chuỗi. Độ phù hợp của mỗi chuỗi gen đánh giá độ
13
thích nghi 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.
Bớc 6 : Nếu cha tìm đợc lời giải tối u hay cha 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 : Tìm đợ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. Giải thuật di truyền đơn 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 đó đợ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ừng 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ử :
Chọn lọc (selecttion)
15
Lai tạo (crossover)
Đột biến (mutation)
Chọ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
(b1b2bposbpos+1bL) và (ccc2cposcpos+1cL)
đợc thay thế bởi cặp con cháu :
(b1b2bposcpos+1cL) và (ccc2cposbpos+1bL)
Đột biến
Các toán tử đột biến nhằm tạo ra các thông tin mới trong quần thể thu đợc
sau khi lai ghép tại các vị trí bít nào đó (quần thể có pop_size cá thể, mỗi cá thể có
độ dài L bít). Đột biến đợc áp dụng với xác suất rất nhỏ p m, vì nếu xác suất p m lớn,
giải thuật GA trở thành giải thuật tìm kiếm ngẫu nhiên. Số lợng bít đột biến là
pm*L*pop_size bít. Mỗi bít có cơ hội đột biến nh nhau và đợc thay đổi từ 0 thành 1
và ngợc lại. Có thể xử lý theo cách sau:
Với mỗi cá thể trong quần thể và mỗi bít trong cá thể:
Phát sinh một số ngẫu nhiên r trong miền [0,1].
Nếu r < pm, tiến hành đột biến tại bít đó.
Các thao tác này đợc áp dụng lặp lại cho tới khi các cá thể con cháu tăng trởng tới kích cỡ mong muốn của quần thể.
Tóm lại, ba toán tử nêu trên đợc tiến hành trong một vòng lặp cho đến khi các
chuỗi con chiếm toàn bộ quần thể mới. Quần thể mới gồm các cá thể của ba loại: bị
đột biến sau khi lai ghép; lai ghép nhng không bị đột biến; không lai ghép và cũng
không bị đột biến mà chỉ đơn giản là sao chép lại.
Hàm thích nghi (fitness)
17
Vì hàm thích nghi phải nhận giá trị không âm nên cần phải xây dựng ánh xạ
từ hàm mục tiêu đang xét của 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 giá g(x), việc chuyển từ hàm giá sang
hàm thích nghi để sử dụng trong GA nh sau:
f(x) = Cmax - g(x)
18
Một trong những thủ tục tỷ lệ hóa đơn giản và hiệu quả là tỷ lệ hóa tuyến
tính. Nếu gọi giá trị thích nghi ban đầu (cha tỷ lệ hóa) là f và giá trị thích nghi sau
khi tỷ lệ hóa là f thì phơng trình tỷ lệ hóa tuyến tính là :
f =
a.f + b
Các hệ số a, b có thể đợc chọn theo một số cách.Tuy nhiên, trong mọi trờng
hợp, mong muốn rằng giá trị thích nghi trung bình sau khi tỷ lệ hóa của toàn quần
thể fave bằng giá trị thích nghi trung bình của toàn quần thể trớc khi tỷ lệ hóa. Điểu
này đảm bảo rằng, các cá thể trung bình sẽ đóng góp một con cho thế hệ tiếp theo.
Để kiểm soát số con cho thành viên siêu khỏe, một phơng trình khác đợc chọn là
fmax = Cmult*fave , ở đây Cmult là số con của cá thể có giá trị thích nghi tốt nhất trong
quần thể. Đối với các quần thể nhỏ (50
} while (k
m
L 1
(2.1)
Giả thuyết về khối xây dựng
Từ biều thức 2.1, dễ thấy các giản đồ bậc nhỏ với độ dài ngắn và có giá trị độ
phù hợp trung bình lớn hơn giá trị độ phù hợp trung bình của toàn quần thể sẽ có số
thể hiện tăng và có vai trò quan trọng trong giải thuật GA. Các giản đồ nh vậy đợc
gọi là các khối xây dựng. Nh đã đề cập ở trên, mỗi chuỗi cá thể độ dài L đồng thời
chứa 2L thể hiện của các giản đồ khác nhau. Giải thuật SGA không xử lý các giản đồ
này một cách rõ ràng mà thay vào đó giải thuật SGA xử lý chúng một cách ngầm
định thông qua các toán tử chọn lọc, lai ghép và đột biến. Quá trình này đợc đặt tên
là sự song song ngầm định. J.H.Holland đã đa ra giả thuyết về khối xây dựng nh
sau : Giải thuật GA tối u hoá (tối thiểu hoá) hàm mục tiêu bằng việc kết hợp các
khối xây dựng tạo ra các cá thể dần tốt hơn từ các phần tử tốt nhất của các điểm đã
thăm dò trớc đấy [14].
2.4. Những cải tiến của giải thuật di truyền
Giải thuật SGA gặp phải một số hạn chế trong việc giải quyết các bài toán
thực tiễn nh sau:
1) SGA biểu diễn cấu trúc nhiễm sắc thể dới dạng chuỗi nhị phân nên trong
các bài toán phức tạp và có nhiều ràng buộc thì độ dài nhiễm sắc thể sẽ lớn, ảnh h ởng rất nhiều tới tốc độ thực hiện giải thuật.
2) Vấn đề hội tụ tới điểm tối u không đảm bảo là tối u toàn cục. Trong trờng
hợp giá trị tối u của lời giải biến đổi theo thời gian thì SGA thờng bị mắc kẹt ở tối u
địa phơng.
Trong những năm gần đây, nhiều nghiên cứu nhằm cải tiến SGA đã đợc công
bố. Dới đây là một số các nghiên cứu cải tiến SGA.
23
của mỗi chuỗi cũng đợc tính nh trên. Điều khác là, phần d còn lại của ei đợc dùng
nh xác suất lựa chọn trong kỹ thuật bánh xe xổ số để lấp đầy quần thể tiếp theo.
4) Lấy mẫu xác suất phần d và không thay thế (remainder stochastic
sampling with replacement) : Sơ đồ này cũng xuất phát từ sơ đồ lấy mẫu tiền định.
Các chuỗi có số con ít nhất bằng phần nguyên của số e i. Sau đó, quần thể đợc lấp
đầy bằng việc chọn các con khác cho mỗi chuỗi với xác suất bằng phần d của ei. Ví
dụ chuỗi ai có ei = 1.5 sẽ đóng góp 1 con vào thế hệ tiếp theo và một con khác với
xác suất là 0.5. Trong thực tế, sơ đồ này đợc sử dụng rộng rãi trong rất nhiều ứng
dụng.
5) Thủ tục phân hạng (ranking procedure): Là thủ tục không tham số cho
việc lựa chọn. Trong phơng pháp này, các cá thể trong quần thể đợc xếp hàng theo
độ phù hợp của chúng, cá thể tốt nhất đợc xếp thứ 1 và cá thể tồi nhất xếp thứ n. Sau
đó, các cá thể đợc gán cho số con là hàm của thứ tự của chúng trong dãy. Một trong
những hàm nh vậy đợc Baker đề xuất [4], số con có thể của chuỗi a i là ei đợc tính
theo công thức:
ei =
2( max 1)
n +1
* rank ( i ) + 1 + ( max 1)
n 1
n 1
Trong đó : max là giá trị do ngời dùng địng nghĩa, 1 max 2 và n là kích thớc của quần thể, khi đó giá trị của e i sẽ nằm trong khoảng [2- max, max], hàm
rank(i) trả lại giá trị là vị trí của i trong hàng xếp.
Mở rộng toán tử lai ghép
Các bít của Con 1 lấy theo mẫu với bít 0 của mẫu lấy từ mẹ, bít 1 lấy từ bố.
Các bít của Con 2 lấy theo mẫu với bít 0 của mẫu lấy từ bố, bít 1 lấy từ mẹ.
Cần phải thận trọng khi dùng toán tử lai ghép nhiều điểm vì theo các nghiên
cứu thực nghiệm, khi tăng số điểm cắt thì tính hiệu quả của giải thuật giảm đi.
Nguyên nhân là khi tăng số điểm cắt, toán tử gây ra sự xáo trộn không mang tính
cấu trúc. Do đó, giải thuật mang tính tìm kiếm ngẫu nhiên và các giản đồ có ích dễ
bị phá vỡ.
2) Toán tử xếp lại : Các toán tử xếp lại thích hợp cho những bài toán mà ở
đó, độ thích nghi phụ thuộc vào sự sắp xếp của các gien trong chuỗi. Một chuỗi kết
hợp các giá trị của gien và thông tin về trật tự có thể đợc biểu diễn nh sau :
1 2 3 4 5 6 7 8
1 0 0 1 0 0 0 1
ở đây, 1, 28 là các vị trí của gen và đ ợc gọi là tên của các gen. Một trong
những toán tử xếp lại hay dùng là toán tử đảo ngợc. Chọn hai điểm ngẫu nhiên theo
chiều dài của chuỗi và cắt chuỗi tại hai điểm đó. Hai chuỗi gen con ở hai đầu vị trí
cắt đổi chỗ cho nhau tạo nên chuỗi mới. Ví dụ:
Chuỗi ban đầu
Chuỗi mới
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 0 0 1 0 0 0 1
0 1 0 1 0 0 1 0
Cải tiến chiến lợc thay thế
Chiến lợc thay thế sản sinh ra quần thể trong thế hệ tiếp theo từ quần thể hiện
giải thuật tìm kiếm cục bộ sẽ tiến đần đến cực trị đó. Với phơng pháp này, giải thuật
GA đợc thực hiện trớc để đạt tới một độ hội tụ nào đó, sau đó các giải thuật tìm
kiếm cục bộ sẽ lấy khoảng 5 đến 10% số điểm tốt nhất có trong quần thể cuối cùng
làm điểm xuất phát. Xuất phát từ ý tởng đó, luận văn xây dựng một giải pháp lai
ghép giữa giải thuật GA và giải thuật BP tạo thành một giải thuật lai để huấn luyện
mạng nơ ron truyền thẳng. Giải pháp này sẽ đợc trình bày ở chơng 3.
Copyright: Tài liệu đại học ©