TRƯỜNG ĐẠI HỌC HÙNG VƯƠNG
KHOA KỸ THUẬT – CÔNG NGHỆ
-----------------------

TRẦN ĐẠO NGHĨA

ẢNH HƯỞNG CỦA PHƯƠNG PHÁP SHUFFLE
ĐỐI VỚI GIẢI THUẬT TIẾN HÓA VI PHÂN
ỨNG DỤNG TRONG DỰ BÁO CHUỖI THỜI GIAN

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC
Ngành Cơng Nghệ Thơng Tin

Phú Thọ, (2017)


TRƯỜNG ĐẠI HỌC HÙNG VƯƠNG
KHOA KỸ THUẬT – CÔNG NGHỆ

-----------------------

TRẦN ĐẠO NGHĨA

ẢNH HƯỞNG CỦA PHƯƠNG PHÁP SHUFFLE
ĐỐI VỚI GIẢI THUẬT TIẾN HÓA VI PHÂN
ỨNG DỤNG TRONG DỰ BÁO CHUỖI THỜI GIAN

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC
Ngành: Cơng Nghệ Thơng Tin

NGƯỜI HƯỚNG DẪN: ThS. VŨ THỊ THU MINH

Phú Thọ, (2017)


i

LỜI CẢM ƠN
Sau quá trình tìm hiểu đề tài “Ảnh hưởng của phương pháp Shuffle đối với
giải thuật tiến hóa vi phân ứng dụng trong dự báo chuỗi thời gian”, em đã hoàn
thành đúng tiến độ dự kiến ban đầu. Để đạt được kết quả này, em đã nỗ lực thực
hiện và đồng thời cũng nhận được rất nhiều sự giúp đỡ từ thầy cơ, gia đình, người
thân và bạn bè.
Em xin chân thành cảm ơn các thầy, các cô khoa Kỹ Thuật - Công Nghệ
Trường Đại học Hùng Vương đã tận tình dạy dỗ, truyền đạt cho chúng em nhiều
kiến thức, kinh nghiệm quý báu trong suốt quá trình học cũng như làm khóa luận
trong trường.
Đặc biệt, em xin tỏ lịng biết ơn sâu sắc đến cơ giáo ThS. Vũ Thị Thu Minh
đã trực tiếp dìu dắt, giúp đỡ em tận tình, chu đáo trong suốt thời gian em hồn
thiện khóa luận lần này.
Xin chân thành cảm ơn các bạn trong lớp K11 – Công nghệ thông tin, khoa
Kỹ Thuật - Công Nghệ, trường Đại Học Hùng Vương đã giúp đỡ, động viên tơi
rất nhiều trong q trình thực hiện đề tài.
Em xin chân thành cảm ơn!
Việt Trì, tháng 5, năm 2017
Sinh viên
Trần Đạo Nghĩa


ii


DANH MỤC HÌNH VẼ
Hình 1.1: Mơ hình hoạt động của giải thuật di truyền. ........................................ 6
Hình 1.2: Ví dụ hai chiều của một hàm mục tiêu.............................................. 111
Hình 1.3: Minh họa q trình chéo cho đề án DE1............................................ 13
Hình 1.4: Ví dụ hai chiều của một hàm mục tiêu 2............................................. 14
Hình 1.5: Sơ đồ khối mô tả luật học giám sát..................................................... 19
Hình 1.6: Cấu trúc chung của mạng neural. ...................................................... 22
Hình 1.7: Mơ hình mạng neural có 1 lớp S neural. ............................................ 22
Hình 1.8: Mơ hình neural 2 lớp. ......................................................................... 23
Hình 1.9: Biểu đồ thể hiện mạng lan truyền tiến 3 lớp của ANN. ...................... 33
Hình 1.10: Quá trình hoạt động của một nút đặc trưng của ANN. .................... 33
Hình 2.1: Q trình để có được tập huấn luyện và xác nhận các tập con. ........ 39
Hình 2.2: Quy trình mã hóa thơng số ban đầu. .................................................. 40
Hình 2.3: ANNs thiết kế theo lược đồ DE. .......................................................... 42
Hình 2.4: ANN thiết kế theo lược đồ DE của q trình để có được fisness. ...... 42
Hình 2.5: Quy trình lấy các mẫu huấn luyện và xác nhận với "Shuffle". ................ 44
Hình 2.6: Đào tạo và xác nhận tập mẫu thu được theo tuần tự. ............................. 45
Hình 3.1: Dữ liệu chuỗi thời gian. ...................................................................... 46
Hình 3.2: Dữ liệu thơ ban đầu được chọn từ dữ liệu Abraham12...................... 46
Hình 3.3: Kết quả được lưu vào hai file khi chương trình kết thúc.................... 48
Hình 3.4: File “File 1” chứa dữ liệu đã chuẩn hóa........................................... 48
Hình 3.5: File “best_sofar_File1” chứa giá trị Fitness đã được chọn lọc........ 49
Hình 3.6: Thư mục chứa kết quả đánh giá......................................................... 49


iii

DANH MỤC BẢNG BIỂU
Bảng 3.1: Bảng so sánh kết quả dự báo giữa GA và DE. ................................... 50
Bảng 3.2: Bảng so sánh kết quả dự báo giữa DE với các phương pháp khác. .. 50



iv

DANH MỤC CÁC TỪ VIẾT TẮT
STT

Từ viết tắt

Tiếng anh

Nghĩa tiếng việt

2

ANN

Atificial Neural Networks

Mạng neural nhân tạo

4

BP

Back Propagation

5

DE


Differential Evolution

6

EA

Evolutionary Algorithm

Giải thuật tiến hóa

7

GA

Genetic Algorithms

Giải thuật di truyền

8

MLP

Multilayer Perceptron

Mạng lan truyền thẳng
nhiều lớp

9


LR

Learning Factor

Hệ số học

Mạng lan truyền ngược
sai số
Giải thuật tiến hóa
vi phân


v

MỤC LỤC
LỜI CẢM ƠN ....................................................................................................... i
DANH MỤC HÌNH VẼ ...................................................................................... ii
DANH MỤC BẢNG BIỂU ................................................................................ iii
DANH MỤC CÁC TỪ VIẾT TẮT ................................................................... iv
MỤC LỤC ............................................................................................................ v
MỞ ĐẦU .............................................................................................................. 1
1. Tính cấp thiết của đề tài khóa luận ............................................................ 1
2. Ý nghĩa khoa học và thực tiễn ..................................................................... 2
3. Mục tiêu khóa luận ...................................................................................... 2
4. Nhiệm vụ nghiên cứu ................................................................................... 2
5. Phương pháp nghiên cứu ............................................................................ 3
6. Đối tượng và phạm vi nghiên cứu............................................................... 3
7. Bố cục khóa luận .......................................................................................... 3
NỘI DUNG........................................................................................................... 5
CHƯƠNG I: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU ............................. 5

1.1. Tổng quan về giải thuật tiến hóa ............................................................. 5
1.1.1. Giải thuật di truyền ............................................................................... 5
1.1.2. Giải thuật tiến hóa ................................................................................. 8
1.1.3. Giải thuật tiến hóa vi phân .................................................................. 10
1.2. Mạng neural nhân tạo............................................................................. 14
1.2.1. Định nghĩa ........................................................................................... 14
1.2.2. Một số chức năng của mạng neural nhân tạo ..................................... 15
1.2.3. Phân loại mạng neural nhân tạo .......................................................... 17
1.2.4. Hoạt động của mạng neural nhân tạo................................................. 18


vi

1.2.5. Luật học của mạng neural ................................................................... 18
1.2.6. Mạng neural nhiều lớp ........................................................................ 20
1.2.7. Mơ hình mạng neural nhân tạo ........................................................... 21
1.2.8. Thuật toán lan truyền ngược sai số của ANN ..................................... 29
1.2.9. Lan truyề n tiế n của ANN .................................................................... 32
1.3. Q trình chuẩn hóa chuỗi thời gian .................................................... 33
1.3.1. Khái niệm ............................................................................................ 33
1.3.2. Chuẩn hóa dữ liệu ............................................................................... 34
1.3.3. Chuỗi thời gian và quá trình ngẫu nhiên............................................. 34
1.3.4. Quá trình ngẫu nhiên dừng ................................................................. 35
1.3.5. Hàm tự tương quan ............................................................................. 36
CHƯƠNG II: THIẾT KẾ GIẢI THUẬT TIẾN HÓA VI PHÂN ĐÁNH GIÁ
ẢNH HƯỞNG PHƯƠNG PHÁP SHUFFLE CHO BÀI TỐN DỰ BÁO . 37
2.1. Thiết kế tiến hố của mạng neural nhân tạo ........................................ 37
2.1.1. Chuỗi thời gian và ANN ..................................................................... 37
2.1.2. Quá trình thiết kế ANN ....................................................................... 38
2.2. Quá trình tìm kiếm ANN ........................................................................ 39

2.3. Phương pháp shuffle ................................................................................. 43
CHƯƠNG III: KẾT QUẢ ĐÁNH GIÁ VÀ THỰC NGIỆM ........................ 46
3.1. Thực nghiệm ............................................................................................ 46
3.1.1. Chuẩn bị dữ liệu .................................................................................. 46
3.1.2. Chuẩn hóa dữ liệu ............................................................................... 47
3.1.3. Thơng số cài đặt cho bài toán. ............................................................ 47
3.2. Kết quả và đánh giá ................................................................................ 47
3.2.1. Kết quả ................................................................................................ 47


vii

3.2.2. Đánh giá .............................................................................................. 49
KẾT LUẬN CHUNG ........................................................................................ 52
TÀI LIỆU THAM KHẢO ................................................................................ 53


1

MỞ ĐẦU
1. Tính cấp thiết của đề tài khóa luận
Ngày nay, do sự phát triển nhanh chóng của khoa học cơng nghệ, đặc biệt là
CNTT, việc tiến hóa từ giải thuật di truyền được các nhà nghiên cứu quan tâm.
Giải thuật tiến hóa được ứng dụng rộng rãi trong các lĩnh vực phức tạp, các vấn
đề khó, sử dụng các kỹ thuật tìm kiếm lời giải, với khơng gian tìm kiếm rất lớn,
nhất là những bài tốn cần có sự lượng giá, đánh giá sự tối ưu của kết quả thu
được. Chính vì vậy, giải thuật tiến hóa vi phân đã trở thành đề tài nghiên cứu thú
vị và đem đến nhiều ứng dụng trong thực tiễn. Một hướng mới đang được quan
tâm nghiên cứu là dự báo chuỗi thời gian dựa vào kỹ thuật mạng neural. Kỹ thuật
này bước đầu đang được ứng dụng và đã cho những kết quả quan trọng. Điều này

nói lên tính cấp thiết của khoa học về mạng neural trong việc giải quyết nhiều bài
toán trong thực tiễn. Khả năng ứng dụng của mạng neural hiện nay khơng cịn
nằm trong các phịng thí nghiệm nữa mà đã xuất hiện ứng dụng vào trong các lĩnh
vực thương mại.
Nghiên cứu dự báo chuỗi thời gian luôn là một bài toán gây được sự chú ý của
các nhà toán học, kinh tế, xã hội học,... Các quan sát trong thực tế thường được
thu thập dưới dạng chuỗi số liệu. Từ những chuỗi số liệu này người ta có thể rút
ra được những quy luật của một quá trình được mơ tả thơng qua chuỗi số liệu.
Nhưng ứng dụng quan trọng nhất là dự báo khả năng xảy ra khi cho một chuỗi số
liệu. Những thí dụ dẫn ra trong các bài báo đều đưa ra khả năng dự báo trong kinh
tế như dự báo chỉ số chứng khoán, mức tăng dân số, dự báo nhu cầu sử dụng điện,
dự báo số lượng sinh viên nhập học của một trường đại học... Các thí dụ này đều
có thể dẫn ra trong mỗi ngành kinh tế kỹ thuật.
Tính tốn tiến hóa (Evolutionary computation): ứng dụng các khái niệm
sinh học như quần thể, biến dị và đấu tranh sinh tồn để sinh các lời giải ngày càng
tốt hơn cho bài tốn. Có một số phương pháp tiếp cận được tn thủ theo tính
tốn tiến hóa và thuật ngữ chung cho cách tiếp cận này là giải thuật tiến hóa. Hình


2

thức sử dụng rộng rãi nhất của giải thuật tiến hóa là giải thuật di truyền (Genetic
Algorithms). Và trong phần trình bày dưới đây sẽ mơ tả rộng hơn về giải thuật
tiến hóa và thuật tiến hóa vi phân (Differential Evolution).
Trong thực tế, chúng ta bắt gặp nhiều bài toán tương tự như dự đoán thị trường
chứng khoán, dự đoán lưu lượng nước, dự đoán lượng gas tiêu, dự đoán năng lực
sản xuất, dự báo khí tượng, dự báo hệ thống mạng giao thơng, bài tốn về thời
khóa biểu. Đó là các bài toán thuộc lớp bài toán dự đoán. Đã có nhiều phương
pháp được đưa ra để giải các lớp bài toán trên như phương pháp thống kê, phương
pháp hồi quy, cây quyết định, mạng neural nhân tạo,…. Trong đó, mạng neural

nhân tạo nhờ khả năng học, nhớ lại và khái quát hóa từ các mẫu dữ liệu huấn
luyện, đã tỏ ra là có ưu thế hơn cả.
Hiện nay vấn đề dự báo chuỗi thời gian sử dụng mạng neural dựa trên giải
thuật di truyền được các nhà nghiên cứu trong nước rất quan tâm. Đã có nhiều đề
tài thạc sỹ, tiến sỹ đề cập và nghiên cứu tới vấn đề này. Sự triển khai giải thuật
tiến hóa vi phân ở nước ngoài tương đối phổ biến nhưng chưa đi sâu tìm hiểu về
ứng dụng trong dự báo chuỗi thời gian. Vì vậy, việc nghiên cứu về sự ảnh hưởng
của giải thuật tiến hóa vi phân ứng dụng trong dự báo chuỗi thời gian là hoàn
toàn cần thiết ở thời điểm hiện tại.
Vì những lý do trên em chọn đề tài khóa luận “ Ảnh hưởng của phương pháp
Shuffle đối với giải thuật tiến hóa vi phân ứng dụng trong dự báo chuỗi thời
gian” . Khóa luận sẽ giúp đánh giá kết quả chính xác về dự báo chuỗi thời gian.
2. Ý nghĩa khoa học và thực tiễn
 Đánh giá ảnh hưởng của phương pháp Shuffle đối với giải thuật tiến hóa vi
phân ứng dụng trong dự báo chuỗi thời gian.
3. Mục tiêu khóa luận
 Đánh giá và đưa ra kết quả dự báo chuỗi thời gian.
4. Nhiệm vụ nghiên cứu
 Tìm hiểu về mạng neural nhân tạo.


3

 Nghiên cứu ánh hưởng của phương pháp Shuffle tới giải thuật tiến hóa vi
phân (DE) trong q trình dự báo chuỗi thời gian.
 Đánh giá và đưa ra kết quả thực nghiệm.
5. Phương pháp nghiên cứu
 Phương pháp nghiên cứu tự luận: Đọc và nghiên cứu tài liệu, giáo trình có
liên quan đến giải thuật tiến hóa vi phân ứng dụng trong dự báo chuỗi thời
gian, hệ thống hóa các kiến thức.

 Phương pháp lấy ý kiến chuyên gia: Lấy ý kiến của giảng viên trực tiếp
hướng dẫn, các giảng viên khác để hoàn thiện về mặt nội dung và hình thức
của thực tập.
 Phương pháp thực nghiệm: Đánh giá và đưa ra kết quả của bài toán.
6. Đối tượng và phạm vi nghiên cứu
 Đối tượng nghiên cứu
- Giải thuật tiến hóa vi phân (DE).
- Mạng neural nhân tạo: Mạng MLP, BP.
- Dự báo chuỗi thời gian.
 Phạm vi nghiên cứu
- Mạng neural nhân tạo sử dụng là mạng MLP (mạng lan truyền thẳng
nhiều lớp).
- Ảnh hưởng của giải thuật tiến hóa vi phân trong q trình huấn luyện
mạng neural.
- Kết quả thực nghiệm chuỗi thời gian.
7. Bố cục khóa luận
Ngồi phần mục lục, mở đầu, kết luận và phụ lục thì báo cáo được chia làm ba
chương như sau:
 Chương I: Tổng quan về vấn đề nghiên cứu.


4

 Chương 2: Thiết kế giải thuật tiến hóa vi phân đánh giá ảnh hưởng
phương pháp shuffle cho bài toán dự báo.
 Chương 3: Kết quả đánh giá và Thực nghiệm.


5


NỘI DUNG
CHƯƠNG I: TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU
1.1. Tổng quan về giải thuật tiến hóa
1.1.1. Giải thuật di truyền
1.1.1.1. Giới thiệu
Thuật toán di truyền là thuật toán tối ưu ngẫu nhiên dựa trên cơ chế chọn lọc
tự nhiên và tiến hóa di truyền. Nguyên lý cơ bản của thuật toán di truyền đã được
Holland giới thiệu vào năm 1962. Cơ sở toán học đã được phát triển từ cuối những
năm 1960 và được giới thiệu trong quyển sách đầu tiên của Holland, “Adaptive
in Natural and Artificial Systems”. Thuật toán di truyền được ứng dụng đầu tiên
trong hai lĩnh vực chính: tối ưu hóa và học tập của máy. Trong lĩnh vực tối ưu hóa
thuật tốn di truyền được phát triển nhanh chóng và ứng dụng trong nhiều lĩnh
vực khác nhau như tối ưu hàm, xử lý ảnh, bài tốn hành trình người bán hàng,
nhận dạng hệ thống và điều khiển. Thuật toán di truyền cũng như các thuật tốn
tiến hóa nói chung hình thành dựa trên quan niệm cho rằng, q trình tiến hóa tự
nhiên là q trình hồn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan
niệm này có thể xem như một tiên đề đúng, không chứng minh được, nhưng phù
hợp với thực tế khách quan. Q trình tiến hóa thể hiện tính tối ưu ở chỗ, thế hệ
sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trước bởi tính kế
thừa và đấu tranh sinh tồn.
Thuật giải di truyền là kỹ thuật giúp giải quết vấn đề bắt chước theo sự tiến
hóa của con người hay sinh vật nói chung, trong điều kiện quy định sẵn của môi
trường. Phương tiện để thực hiện cách giải quyết vấn đề là chương trình tin học
gồm các bước thi hành, từ việc chọn giải pháp tiêu biểu cho vấn đề, cho đến việc
chọn các hàm số thích nghi hơn. Như vậy, GA không chú trọng đến giả pháp duy
nhất và chính xác như phương pháp cổ điển, trái lại GA xét đến toàn bộ các giải
pháp chọn lọc lấy giải pháp tương đối tốt nhất nếu khơng nói là tối ưu.


6


1.1.1.2. Khái niệm
Các thuật giải di truyền (GAs: Genetic Algorithms) cũng như các thuật tốn
tiến hóa khác hình thành dựa trên quan niệm cho rằng q trình tiến hóa tự nhiên
là q trình hợp lý, hồn hảo và tự nó đã mang tính tối ưu. Quan điểm trên như
một tiên đề, không chứng minh, nhưng phù hợp với thực tế khách quan.
Mục tiêu nghiên cứu của GAs có thể được khái qt như sau:
- Trừu tượng hố và mơ phỏng q trình thích nghi trong hệ thống tự nhiên.
- Thiết kế phần mềm, chương trình mơ phỏng, nhằm duy trì các cơ chế quan
trọng của hệ thống tự nhiên.
Giải thuật di truyền sử dụng một số thuật ngữ của ngành di truyền học như:
nhiễm sắc thể, quần thể (Population), Gen.... Nhiễm sắc thể được tạo thành từ các
Gen (được biểu diễn của một chuỗi tuyến tính). Mỗi Gen mang một số đặc trưng
và có vị tri nhất định trong nhiễm sắc thể. Mỗi nhiễm sắc thể sẽ biểu diễn một lời
giải của bài tốn.
Population

Selection

New
Population

Mutation

Mating

Hình 1.1: Mơ hình hoạt động của giải thuật di truyền.
1.1.1.3. Cơ sở toán học của giải thuật di truyền
Ý tưởng của giải thuật di truyền là mơ phỏng theo cơ chế của q trình chọn
lọc và di truyền trong tự nhiên. Từ tập các lời giải có thể ban đầu, thơng qua nhiều

bước tiến hóa để hình thành các tấp mới với những lời giải tốt hơn, cuối cùng sẽ
tìm được lời giải gần tối ưu nhất.
GA sử dụng các thuật ngữ lấy từ di truyền học:


7

- Một tập hợp các lời giải được gọi là Lớp hay Quần thể (population)
- Mỗi lời giải được biểu diễn bởi một Nhiễm sắc thể hay Cá thể.
- Nhiễm sắc thể được tảo thành từ các gen.
GA thực hiện tìm kiếm theo nhiều hướng bằng cách duy trì tập hợp các lời
giải có thể và khuyến khích sự hình thành và trao đổi thơng tin giữa các hướng.

Hình 2.1: Sơ đồ cấu trúc giải thuật di truyền.


8

 Một giải thuật di truyền đơn giản bao gồm các bước sau:
Bước 1: Khởi tạo một quần thể ban đầu gồm các chuỗi nhiễm sắc thể.
Bước 2: Xác định giá trị mục tiêu cho từng nhiễm sắc thể tương ứng.
Bước 3: Tạo các nhiễm sắc thể mới dựa trên các toán tử di truyền.
Bước 4: Loại bớt các nhiễm sắc thể có độ thich nghi thấp.
Bước 5: Xác định hàm mục tiêu cho các nhiễm sắc thể mới và đưa vào
quần thể.
Bước 6: Kiểm tra thỏa mãn điều kiện dừng. Nếu điều kiện đúng, lấy ra
nhiễm sắc thể tốt nhất, giải thuật dừng lại; ngược lại, quay về bước 3.
Các thơng số bài tốn được mã hóa thành các chuỗi. Cách đơn giản nhất là
chúng ta dùng chuỗi bit để mã hóa các thơng số. Mỗi thơng số được mã hóa bằng
một chuỗi bit có độ dài nào đó, sau đó nối chúng lại với nhau, chúng ta sẽ có một

chuỗi cho tập các thơng số. Để tính tốn giá trị hàm mục tiêu tương ứng với mỗi
chuỗi thông số, ta phải giải mã bộ thông số này theo một quy tắc nào đó, Giải
thuật di truyền tìm kiếm song song trên một tập các chuỗi, do đó giảm thiểu được
khả năng bỏ qua các cực trị toàn cục và dừng lại ở vị trí địa phương. Điều này giải
thích vì sao giải thuật di truyền mang tính tồn cục.
1.1.2. Giải thuật tiến hóa
1.1.2.1. Giới thiệu
Nhiều ứng dụng trong hóa học tính tốn có một khơng gian tìm kiếm mà là
theo cấp số tỷ lệ thuận với kích thước và vấn đề nhưng đối với các đơn giản nhất
của trường hợp, những vấn đề không thể được giải quyết bằng các phương pháp
tìm kiếm đầy đủ. Do đó, có lợi ích đáng kể trong kỹ thuật tiến hóa cố gắng để
khám phá các giải pháp gần tối ưu trong một thời gian chấp nhận được. các thuật
toán di truyền (GA) và các thuật tốn tiến hóa khác có liên quan (EA) cung cấp
một khuôn khổ cho việc lấy mẫu một cách hiệu quả khơng gian tìm kiếm lớn, và
các kỹ thuật cơ bản là cả hai áp dụng rộng rãi và dễ dàng phù hợp với các vấn đề
cụ thể (Giải thuật di truyền). Tất cả những gì cần thiết để áp dụng một EA cho bất
kỳ vấn đề cụ thể là một chương trình mã hóa thích hợp và một hàm mục tiêu.


9

Tính tốn tiến hóa sử dụng các mơ hình tính tốn của q trình tiến hóa là yếu
tố quan trọng trong việc thiết kế và thực hiện hệ thống dựa trên máy tính và giải
quyết các vấn đề ứng dụng. Có một loạt các mơ hình tính tốn tiến hóa đã được
đề xuất và nghiên cứu mà chúng tôi sẽ đề cập đến các thuật tốn như tiến hóa. Họ
chia sẻ một cơ sở khái niệm phổ biến của mô phỏng sự tiến hóa của cấu trúc cá
nhân thơng qua quá trình lựa chọn và sinh sản. Họ phụ thuộc vào việc thực hiện
(giá trị fitness) của các cấu trúc riêng.
1.1.2.2. Cơ sở khoa học
Chính xác hơn, thuật tốn tiến hóa duy trì quần thể cấu trúc tiến hóa theo quy

tắc lựa chọn và khai thác khác, chẳng hạn như tái tổ hợp và đột biến. Mỗi cá thể
trong quần thể nhận được một giá trị “fitness” của mình trong môi trường. Lựa
chọn tập trung vào những giá trị “fitness” cao, từ đó khai thác các giá trị có sẵn.
Tái tổ hợp và đột biến làm xáo trộn những cá nhân, cung cấp cơng nghệ tự động
nói chung để thăm dò. Mặc dù đơn giản từ quan điểm của một nhà sinh vật học,
những thuật toán là đủ phức tạp để cung cấp các cơ chế tìm kiếm thích hợp.
Một số cấu trúc quần thể được khởi tạo và sau đó phát triển từ thế hệ này đến
thế hệ các ứng dụng lặp đi lặp lại của việc đánh giá, lựa chọn, tái tổ hợp, và đột
biến. Quy mô quần thể N nói chung là khơng đổi trong một thuật tốn tiến hóa.
procedure EA
{
t = 0;
initialize population P(t);
evaluate P(t);
until (done) {
t = t + 1;
parent_selection P(t);
recombine P(t);
mutate P(t);
evaluate P(t);


10

survive P(t);
}
}
Một thuật tốn tiến hóa thường được xắp xếp ngẫu nhiên các quần thể, mặc
dù kiến thức tên miền cụ thể cũng có thể được sử dụng để xác định các tìm kiếm.
Đánh giá các giá trị “fitness” của từng cá thể theo giá trị của nó trong một số mơi

trường. Đánh giá có thể được đơn giản như tính tốn một chức năng “fitness” hoặc
phức tạp như chạy một chương trình mơ phỏng. Lựa chọn thường được thực hiện
theo hai bước, lựa chọn cha mẹ và sống sót. Lựa chọn cha mẹ quyết định ai sẽ trở
thành cha mẹ và bao nhiêu trẻ em cha mẹ có. Trẻ em được tạo ra thông qua tái tổ
hợp, mà trao đổi thông tin giữa phụ huynh, và đột biến. Những đứa trẻ này sau đó
được đánh giá. Cuối cùng, bước sống cịn quyết định ai sống sót trong quần thể.
Nguồn gốc của các thuật tốn tiến hóa có thể được phát triển từ ít nhất là năm 1950.
Ba phương pháp mà đã nổi lên trong vài thập kỷ qua:
"Lập trình tiến hóa" (Fogel et al., 1966)
"Chiến lược tiến hóa" (Rechenberg, 1973)
"Thuật tốn di truyền" và "lập trình di truyền" (Holland, 1975).
Mặc dù tương tự ở cấp cao nhất, mỗi cá thể trong các quần thể thực hiện một
thuật toán tiến hóa một cách khác nhau. Sự khác biệt bao gồm gần như tất cả các
khía cạnh của các thuật tốn tiến hóa, bao gồm cả việc lựa chọn đại diện cho các
cấu trúc cá thể, các loại cơ chế lựa chọn sử dụng, hình thức của các nhà khai thác
di truyền, và các biện pháp thực hiện.
1.1.3. Giải thuật tiến hóa vi phân
1.1.3.1. Giới thiệu
Giải thuật tiến hóa vi phân (DE) là một phương pháp tìm kiếm trực tiếp song
song trong đó sử dụng các vector tham số NP như một cá thể cho từng thế hệ NP,
không thay đổi trong suốt quá trình giảm thiểu. Ban đầu cá thể được chọn ngẫu
nhiên, nếu khơng có gì được biết về hệ thống. Ban đầu, chúng ta sẽ cho một bộ
dữ liệu phân bố xác suất cho tất cả các quần thể ngẫu nhiên . Trong trường hợp


11

một giải pháp sơ bộ là có sẵn, các cá thể ban đầu thường được tạo ra bằng cách
thêm phân phối chuẩn độ lệch ngẫu nhiên. Ý tưởng quan trọng đằng sau DE là
một chương trình để tạo ra các vector tham số thử nghiệm. DE tạo ra vectơ tham

số mới bằng cách thêm một vector khác biệt trọng số giữa hai cá thể thành viên
để thành cá thể thứ ba. Nếu các vectơ kết quả ra một giá trị hàm mục tiêu thấp
hơn so với một thành viên có thể được xác định trước, các vector được tạo mới sẽ
thay thế các vector mà nó đã so sánh trong các thế hệ sau.
1.1.3.2. Thiết lập đề án khiểm thử
Đề án DE1
Biến thể đầu tiên của DE hoạt động như sau: đối với mỗi vector xi, G,
i = 0,1,2,...,NP-1, một vector thử nghiệm v được tạo ra theo:
v = x r1,G + F.(xr2,G –xr3,G)
Với r1,r2,r3 ∈ [0,NP – 1], số thập phân và hai số bằng nhau,và F>0.
Các số nguyên r1,r2 và r3 được chọn ngẫu nhiên từ khoảng [0, NP-1] và là
khác nhau từ các chỉ số hoạt động i. F là một yếu tố thực và kiểm soát sự
khuếch đại của các biến thể khác biệt (xr2,G –xr3,G).

Hình 1.2: Ví dụ hai chiều của một hàm mục tiêu.


12

Từ ví dụ cho thấy đường viền của nó và quá trình để tạo ra các câu trong đề
án DE1. Các vector khác biệt trọng của hai vector tùy chọn được thêm vào một
vector thứ ba để mang lại vector v.
Để tăng sự đa dạng của các vectơ tham số, vector

(1)
Được hình thành nơi dấu ngoặc cấp < >D biểu thị các chức năng của
modun D.
Từ (1) mang lại một trình tự nhất định của các yếu tố của vector u để được
giống hệt nhau trên những yếu tố v các yếu tố khác của u có được các giá trị ban
đầu của x i,G. Chọn một nhóm các tham số của đột biến là tương tự như một quá

trình được gọi là GAS hoặc ESS.
Ý tưởng này được minh họa trong hình 1.3 cho D = 7, n = 2 và L = 3. Các chỉ
số bắt đầu từ n trong (1) là một số nguyên được chọn ngẫu nhiên từ khoảng
[0, D-1]. Các số nguyên L, mà biểu thị số lượng các thơng số đó sẽ được trao
đổi, được rút ra từ khoảng [1, D]. Các thuật toán mà quyết định L làm việc theo
những dòng mã giả để tạo ra một số ngẫu nhiên ∈ [0,1):
L = 0;
do {
L = L + 1;
}while(rand()< CR) AND (L < D));
Do đó xác suất Pr (L> = ν) = (CR)v-1, ν> 0. CR ∈ [0,1] là xác suất chéo và tạo
thành một biến điều khiển cho các DE1 đề án. Các quyết định ngẫu nhiên cho cả
hai n và L được làm lại cho từng vector thử nghiệm v.


13

Hình 1.3: Minh họa quá trình chéo cho đề án DE1.
Vector tham số chứa các thông số : xj , j=0,1, ... , D-1. Cho D = 7, n = 2 và
L = 3.
Để quyết định liệu các vector mới u sẽ trở thành một thành viên của quần
thể thế hệ G + 1, nó sẽ được so sánh với x i,G. Nếu vector u ra một giá trị hàm mục
tiêu nhỏ hơn so với x i,G, x i,G+1 được thiết lập để u, nếu không giá trị x i,G cũ được
giữ lại.
Đề án DE2
Về cơ bản, đề án DE2 hoạt động theo cách tương tự như DE1 nhưng tạo
ra các v vector theo:
(2)
Giới thiệu thêm một biến kiểm soát λ. Ý tưởng đằng sau λ là để cung cấp
một phương tiện để tăng cường sự tích cực của các chương trình này bằng

cách kết hợp vector xbest,G tốt nhất hiện nay. Tính năng này có thể có ích cho
các chức năng quan nơi tối thiểu toàn cầu là tương đối dễ dàng để tìm thấy.
Minh họa quá trình tạo vector xác định bởi (2). Việc xây dựng các u từ v và
x i,G cũng như quá trình ra quyết định là giống hệt nhau để DE1.


14

Hình 1.4: Ví dụ hai chiều của một hàm mục tiêu 2.
Ví dụ cho thấy đường viền của nó và quá trình để tạo ra các v trong đề
án DE2.
1.2. Mạng neural nhân tạo
1.2.1. Định nghĩa
Mạng neural nhân tạo là sự kết hợp giữa các neural nhân tạo với nhau. Mỗi
liên kết kèm theo một trọng số nào đó đặc trưng cho đặc tính kích hoạt ức chế
giữa các neural. Các neural còn gọi là các nút (node) được sắp xếp trong mạng
theo các lớp, bao gồm lớp ra (output player) và các lớp ẩn (hiden layer). Các đặc
điểm của mang neural nhân tạo:
- Mạng được xây dựng bằng các neural liên kết lại với nhau.
- Chức năng của mạng được xác định bởi: cấu trúc mạng, quá trình xử lý bên
trong của từng neural, và mức độ liên kết giữa các neural.
- Mức độ liên kết giữa các neural được xác định thơng qua q trình học của
mạng (q trình huấn luyện mạng).
Có thể xem các trọng số là các phương tiện để lưu trữ thông tin dài hạn trong
mạng neural. Nhiệm vụ của quá trình huấn luyện mạng là cập nhật các trọng số
khi có thơng tin về các mẫu học.


15


* Một số định nghĩa về mạng neural:
+ Mạng neural là một hệ thống gồm nhiều phần tử xử lý hoạt động song
song. Chức năng của nó được xác định bởi cấu trúc mạng, độ lớn các liên
kết và quá trình xử lý tại mỗi nút hoặc đơn vị tính toán.
+ Một mạng neural là một bộ xử lý song song và đồ sộ, có xu hướng tự
nhiên là lưu trữ các tri thức dựa trên kinh nghiệm, và tạo ra tri thức mới dựa
vào cái đã có. Nó tương tự với bộ não ở hai khía cạnh:
- Tri thức có được thơng qua q trình học.
- Độ lớn liên kết giữa các neural được dùng như một phương tiện lưu
trữ thơng tin.
+ Hệ thống neural nhân tạo, hay cịn gọi là các mạng neural, là một tập hợp
các tế bào vật lý, được liên kết với nhau nhằm mục đích thu thập, lưu trữ
và sử dụng tri thức, kinh nghiệm một cách tốt nhất.
1.2.2. Một số chức năng của mạng neural nhân tạo
1.2.2.1. Chức năng phân loại mẫu
Phân loại mẫu là sự sắp xếp các mẫu thành các nhóm khác nhau. Mạng neural
có thể tạo ra một mẫu ra khi đưa cho nó một mẫu vào, đây là chức năng phân loại
mẫu của mạng neural. Mạng neural nhận mẫu vào và tạo một mẫu ở đầu ra đúng
với phân loại. Có thể nói mạng neural là một bộ phân loại mẫu. Điểm khác của
mạng neural với các bộ phân loại mẫu khác là khả năng học và tổng quát
hóa của mạng neural.
1.2.2.2. Học và tổng quát hóa
Đầu tiên là việc học, có thể hiểu việc này là cho mạng neural xem một ít mẫu
kèm với đầu ra tương ứng với mẫu đó và mạng neural phải học để phân loại đúng
được các mẫu này. Còn khả năng tổng quát hóa là: mạng neural khơng chỉ nhận
biết được các mẫu nó đã được học mà có thể nhận được các mẫu gần với mẫu nó
đã được học. Tức là mạng neural có thể suy ra các đặc tính chung của các lớp
khác nhau từ các mẫu đã cho. Chức năng này tạo ra một chiến lược tính tốn rất
phù hợp cho việc giải quyết các vấn đề mang tính "động", tức là thông tin về



16

chúng có rất ít hoặc bị thiếu, khơng đầy đủ. Điểu quan trọng là tìm được mơ hình
mạng và phương pháp học thích hợp đối với từng bài tốn. Ngồi ra mạng neural
cịn có khả năng được huấn luyện để trở thành bộ xấp xỉ hàm liên tục bất kỳ.
1.2.2.3. Lịch sử phát triển của mạng neural nhân tạo
- Cuối thế kỷ 19, đầu thế kỷ 20, một số nghiên cứu về vật lý, tâm lý và hệ
thần kinh của các nhà khoa học Herman, Ernst Mach và Ivan Ivalov đã đưa ra các
lý thuyết về quá trình học, sự tưởng tượng, sự quyết định... của hệ thần kinh nhưng
chưa có sự mơ tả tốn học cho hoạt động của mạng neural.
- Năm 1943, mơ hình đơn giản mạng neural bằng mạch điện tử lần đầu tiên
được đưa ra bởi Warren McCulloch và Walter Pits cùng với sự khẳng định mạng
neural nhân tạo về nguyên lý có thể thực hiện được trong phạm vi tính tốn các
hàm số học và logic. Đây là điểm khởi đầu của lĩnh vực mạng neural.
- Sau đó Donal Hebb đưa ra một cơ chế giải thích cho q trình học (learning)
diễn ra trong các neural sinh học (trong cuốn Organnization of Behaviaor - 1949).
- Cuối thập niên 50, ứng dụng thực tế đầu tiên của mạng neural nhân tạo do
Frank Rosenblatt đưa ra. Mạng của ơng đưa ra là mạng Perceptron có kết hợp luật
học (learning rule) dùng để nhận dạng mẫu (pattern recognition). Cùng thời gian
đó, Bernard Widrow và Ted Hoff giới thiệu một thuật tốn học (learning
algorithm) và sử dụng nó để huấn luyện (training) các mạng neural tiếp hợp tuyến
tính (tương tự mạng của Rosenblatt).
- Năm 1969, Minskey và Papert là hai nhà tốn học nổi tiếng thời đó đã chỉ
ra những hạn chế của mạng Perceptron của Rosenblatt và mạng Widrow- Hoff
làm nhiều người nghĩ rằng nghiên cứu về mạng neural sẽ vào ngõ cụt. Hơn nữa
vào thời gian này chưa có những máy tính số mạnh để thực nghiệm mạng neural
nên các nghiên cứu về mạng nơ-ron bị trì hoãn gần một thập kỷ.
- Năm 1972, Teuvo Kohonen và James Anderson độc lập phát triển các mạng
neural mới với năng lực nhớ (memory) và khả năng tự tổ chức (selforganizing).

Cũng trong giai đoạn này,Stephen Grossberg cũng nghiên cứu tích cực về các
mạng tự tổ chức. - Sang thập kỷ 80, khi ngành cơng nghiệp máy tính phát triển