BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC KINH TẾ TP.HCM

CÔNG TRÌNH DỰ THI
GIẢI THƯỞNG NGHIÊN CỨU KHOA HỌC SINH VIÊN
“NHÀ KINH TẾ TRẺ – NĂM 2012”
TÊN CÔNG TRÌNH:
ỨNG DỤNG THUẬT TOÁN DI TRUYỀN
XÁC ĐỊNH QUY TẮC GIAO DỊCH TỐI ƯU TRÊN
TRỊ TRƯỜNG CHỨNG KHOÁN VIỆT NAM

THUỘC NHÓM NGÀNH: KHOA HỌC KINH TẾ


3.3 Các thử nghiệm và dữ liệu nghiên cứu 30
CHƯƠNG 4: KẾT QUẢ NGHIÊN CỨU & NHẬN ĐỊNH 35
4.1 Kết quả nghiên cứu 35
4.1.1 Kết quả với chỉ số VN-index 35
4.1.2 Kết quả nghiên cứu với các cổ phiếu 41
4.2 Một số nhận định về kết quả nghiên cứu 49
KẾT LUẬN 56
PHỤ LỤC 1: CODE VBA 57
PHỤ LỤC 2: ƯỚC LƯỢNG MÔ HÌNH GARCH 61
PHỤ LỤC 3: RANDOM WALK 68
TÀI LIỆU THAM KHẢO 74

DANH MỤC BẢNG

Bảng 2.1: Các thuật ngữ của thuật toán di truyền 9
Bảng 3.1 Phương pháp tính toán một số chỉ số PTKT 26
Bảng 3.2 Cấu trúc tổng quát của quy tắc giao dịch 29
Bảng 3.3 Thời gian thử nghiệm GAs với VN-index 30
Bảng 3.4 Quy tắc giao dịch với GARCH 32
Bảng 3.5 Các giai đoạn thử nghiệm với các cổ phiếu cụ thể 33
Bảng 3.6 Danh sách các cổ phiếu thử nghiệm 33

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

TSSL Tỷ suất sinh lợi
PTKT Phân tích kỹ thuật
TTCK Thị trường chứng khoán
GAs Genetic Algrithms – Thuật toán di truyền
NNs Neural Networks – Mô hình mạng thần kinh
FL Fuzzy Logic – Hệ suy luận mờ
SC Soft Computing
AI Artificial intelligence 1

MỞ ĐẦU
Cùng với sự phát triển của thị trường chứng khoán (TTCK), các phương pháp phân tích
đầu tư chứng khoán cũng được hình thành và phát triển như một nhu cầu không thể thiếu.
Phân tích kỹ thuật (PTKT) là phương pháp phổ biến được áp dụng ở hầu hết các thị
trường chứng khoán. Những nghiên cứu của Brock, Lakonishok và LeBaron (1992),
nghiên cứu của Bessembinder và Chan (1995) [1] đã chỉ ra rằng phân tích kỹ thuật có
những hạn chế nhất định và không phải lúc nào cũng tỏ ra hiệu quả.

Thuật toán di truyền cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên
quan điểm cho rằng, quá trình tiến hóa tự nhiên là quá trình hoà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. Quá 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 vì
tính kế thừa và đấu tranh sinh tồn.
Thuật giải di truyền cung cấp một cách tiếp cận cho việc tối ưu hóa dựa vào mô phỏng sự
tiến hóa. Các giả thuyết thường được mô tả bằng các chuỗi bit, việc hiểu các chuỗi bit
này tùy thuộc vào ứng dụng, ý tưởng các giả thuyết cũng có thể được mô tả bằng các biểu
thức kí hiệu hoặc các chương trình máy tính. Tìm kiếm giả thuyết thích hợp bắt đầu với
một quần thể, hay một tập hợp có chọn lọc ban đầu của các giả thuyết. Các cá thể của
quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép và
đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa sinh học. Ở mỗi bước, các
giả thuyết trong quần thể hiện tại được ước lượng liên hệ với đại lượng thích nghi được
cho, với các giả thuyết phù hợp nhất được chọn theo xác suất là các hạt giống cho việc
sản sinh thế hệ kế tiếp. Thuật giải di truyền đã được ứng dụng một cách thành công cho
nhiều tác vụ thuộc nhiều lĩnh vực khác nhau.
3

Ứng dụng của thuật toán di truyền
Ưu điểm vượt trội của thuật toán di truyền là nó dễ dàng thích nghi và xử lí với bất kì
rằng buộc nào của hàm mục tiêu. Đặc biệt với các bài toán tối ưu trong không gian tìm
kiếm lớn và không có những phân tích toán học có sẵn, ngay cả trường hợp mà phương
pháp truyền thống không thể tiếp cận được, GAs vẫn có thể giải quyết và đưa ra phương
án tối ưu. GAs được ứng dụng trong nhiều lĩnh vực khác nhau, bao gồm cả khoa học, kỹ
thuật, kinh tế, xã hội.
 Lĩnh vực tối ưu hóa: GAs được sử dụng trong hàng loạt các vấn đề tối ưu, bao gồm
cả tối ưu hóa số học và tối ưu hóa tổ hợp, ví dụ bài toán hành trình của người bán hàng
(TSP), thiết kế mạch Louis 1993, lập kế hoạch công việc của cửa hàng Goldstein 1991 và
tối ưu hóa chất lượng âm thanh & hình ảnh.

được đưa từ neural đầu vào, qua lớp neural ẩn đến neural đầu ra để trả ra kết quả dự báo
ban đầu được gọi bằng thuật ngữ Feedforward – tức dữ liệu được đẩy lần lượt từ đầu vào
đến đầu ra) với dữ liệu đã được training bằng thuật toán di truyền (GAs) để dự báo lãi
suất kì hạn 3 tháng của trái phiếu kho bạc Mỹ (U.S Treasury Bill). Họ kết luận NN kết
hợp với GAs có thể dự báo một cách chính xác lãi suất này.
Tansel và cộng sự (1999) đã so sánh mô hình hồi quy truyền thống với NN, GAs và các
mô hình dự báo chuỗi thời gian trên các tiêu chí: mức độ chính xác của mô hình, sự tiện
dụng và thời gian tính toán. Kết quả nghiên cứu cho thấy, các mô hình hồi quy tuyến tính
truyền thống là mô hình ước lượng tốt nhất. GAs cũng có thể cho kết quả ước lượng
chính xác nếu dữ liệu được giới hạn trong một miền nhất định và được ước lượng một
cách gần đúng. Nhưng NN lại cho kết quả ước lượng kém chính xác nhất. Mặc dù vậy, họ
nhấn mạnh rằng, mô hình phi tuyến được xây dựng kết hợp giữa GAs và NN có thể là
một công cụ dự báo mạnh, phù hợp với tiêu chuẩn ước lượng tổng quát.
Kim và Han (2000) sử dụng phương pháp mạng thần kinh NN với sự hỗ trợ của thuật
toán di truyền để dự báo chỉ số giá chứng khoán. Trong trường hợp này, GAs được sử
dụng để hạn chế sự phức tạp của những khoảng thời gian đặc biệt bằng cách tối ưu hóa sự
5

liên kết giữa các lớp. Họ kết luận rằng phương pháp sử dụng NN kết hợp với GAs cho
kết quả chính xác hơn các phương pháp thông thường.
Tiếp theo, nghiên cứu của Kuo và cộng sự (1996) và nghiên cứu của Kuo và cộng sự
(2001) phát triển FNN (GFNN) trên nền tảng GAs, để phát triển một cách có hệ thống
các kiến thức về hệ suy luận mờ, một hệ thống có thể định lượng ảnh hưởng của các nhân
tố định tính (ví dụ nhân tố chính trị) lên thị trường chứng khoán. Những tác động này
hoàn toàn đồng nhất với mô hình với các chỉ số phân tích kỹ thuật bằng phương pháp
NN. Sử dụng tín hiêu mua - bán thông qua cách tiếp cận trí tuệ nhân tạo trên TTCK Đài
Loan, họ kết luận rằng NNs sử dụng cả các nhân tố định lượng (phân tích kỹ thuật) và
nhân tố định tính hiệu quả hơn chỉ sử dụng các nhân tố định lượng.
Xác định các quy tắc giao dịch
Sự tính toán thời gian phù hợp để đưa ra quyết định (timing) là một trong những yếu tố

Intelligent Decision Support System (DSS) để phân tích chỉ số giá chứng khoán Tokyo
(Tokyo Stock Exchange Prices Indexes – TOPIX). Bản chất của nghiên cứu này là sử
dụng DSS để dự báo mức giá cao và thấp khác nhau, đưa ra các tín hiệu mua, bán của
TOPIX trong bốn tuần liên tục. Mặt khác, họ xây dựng mô hình (8,15,2)FFNN với dữ
liệu đã được training bởi GAs kết hợp phương pháp BackpropaGAstion – BP, là hệ
thống ANN đa lớp (lớp đầu vào, lớp ẩn và lớp đầu ra). Họ kết luận rằng GAs và NN là
một công cụ mạnh để nghiên cứu chỉ số TOPIX.
Định giá quyền chọn
Chen và Lee (1997) đã minh họa bằng cách nào mà GAs – được sử dụng như một công
cụ thay thế NNs có thể dùng để định giá quyền chọn. Nghiên cứu này kiểm định khả
năng của GAs trong việc định giá quyền chọn mua kiểu châu Âu, giả định rằng, giá của
7

quyền chọn có thể được xác định một cách chính xác bằng lý thuyết Black – Scholes. Kết
quả nghiên cứu cho thấy, đây là một phương pháp đầy hứa hẹn.
Xây dựng danh mục đầu tư
Wendt (1995) đã sử dụng GAs để xây dựng đường biên danh mục hiệu quả. Mẫu dữ liệu
bao gồm 250 quan sát về lợi nhuận hàng năm của tám loại tài sản khác nhau. Để đánh giá
hiệu quả của GAs, output cuối cùng của GAs được so sánh với phương pháp xây dựng
đường biên hiệu quả bằng mô hình phi tuyến phức tạp. Sau khoảng 50 vòng lặp, đường
biên hiệu quả được xây dựng bằng hai phương pháp này là rất trùng khớp nhau.
Jackson (1997) đã áp dụng GAs giải quyết bài toán phân bổ tài sản. Với benchmark được
chọn là phương pháp tối ưu hóa Newton. Trong khi phương pháp Newton cho nhiều kết
quả khác nhau, không phụ thuộc vào giá trị ban đầu thì ngược lại, kết quả của GAs
thường bị gián đoạn trong không gian tìm kiếm và phụ thuộc nhiều vào giá trị ban đầu.
1.3 Phương pháp luận của đề tài
Năm 1859, Charles Darwin đã đưa ra một học thuyết toàn diện về nguồn gốc của loài do
chọn lọc tự nhiên. Theo học thuyết này tất cả các sinh vật đa dạng ngày nay là kết quả
của một lịch sử tiến hóa lâu dài. Tất cả các sinh vật thường xuyên thay đổi và những thay
đổi này của mỗi loài giúp cho chúng thích nghi với môi trường sống. Một trong các đặc

thể, tồn tại những quy luật – một quy tắc giao dịch có thể mang lại một TSSL cao hơn so
với các quy tắc giao dịch khác. Do đó, các quy tắc giao dịch tối ưu trong quá khứ có thể
mang lại một TSSL cao trong tương lai nếu trong những khoảng thời gian khác nhau này,
giá cả vận động theo cùng một quy luật, quy luật chung của sự tiến hóa. Dựa trên quan
điểm đó, bài nghiên cứu sẽ sử dụng thuật toán di truyền GAs để xác định và kiếm chứng
các quy tắc giao dịch tối ưu ở những thời điểm cụ thể, với những cổ phiếu cụ thể trên
TTCK Việt Nam.

9

CHƯƠNG 2: THUẬT TOÁN DI TRUYỀN
Bài nghiên cứu sẽ dành toàn bộ chương 2 để trình bày một cách khái quát những nguyên
lý hoạt động và cơ sở toán học cơ bản về thuật toán di truyền. Các thuật ngữ, phương
pháp tổ chức và mã hóa cơ sở dữ liệu, xây dựng hàm thích nghi, các phép toán cơ bản
(tái sinh, lai ghép, đột biến) và các định lý cơ bản về thuật toán di truyền sẽ lần lượt
được giới thiệu. Trong phạm vi nghiên cứu, đề tài chỉ trình bày những kiến thức cơ bản
nhất, phương pháp chứng minh, hạn chế, những lời phê bình về các định lý sẽ không
được đề cập đến. Toàn bộ kiến thức trong chương 2 sẽ là nền tảng để thiết kế dữ liệu và
thuật toán phù hợp với vấn đề cụ thể của đề tài nghiên cứu.

2.1 Nguyên lý cơ bản về thuật toán di truyền
2.1.1 Tổng quan về nguyên lý của thuật toán di truyền
Bảng 2.1: Các thuật ngữ của thuật toán di truyền
Thuật ngữ Giải thích
Nhiễm sắc thể một cấu trúc có tổ chức của ADN và protein nằm trong các
tế bào.
Gen một đoạn ADN mang một chức năng nhất định trong quá
trình truyền thông tin di truyền
Locus Gen vị trí cụ thể của 1 gen hay AND trên nhiễm sắc thể
Allele hay alen những dạng biến dị khác nhau của một gene có 1 vị trí locus

Nói ngắn gọn, một lời giải sẽ được biểu diễn bằng một chuỗi bit, cũng giống như mỗi cá
thể đều được quy định bằng gen của cá thể đó. Như vậy, đối với thuật giải di truyền, một
cá thể chỉ có một gen duy nhất và một gen cũng chỉ phục vụ cho một cá thể duy nhất.
11

Ban đầu, ta sẽ phát sinh một số lượng lớn, giới hạn các cá thể có gen ngẫu nhiên - nghĩa
là phát sinh một tập hợp các chuỗi bit ngẫu nhiên. Tập hợp các cá thể này được gọi là
quần thể ban đầu (initial population). Sau đó, dựa trên một hàm thích nghi, ta sẽ xác định
được một giá trị gọi là độ thích nghi - Fitness. Giá trị này, để đơn giản, có thể tạm hiểu
chính là độ "tốt" của lời giải. Vì phát sinh ngẫu nhiên nên độ "tốt" của lời giải hay tính
thích nghi của các cá thể trong quần thể ban đầu là không xác định.
Để cải thiện tính thích nghi của quần thể, người ta tìm cách tạo ra quần thể mới. Có hai
thao tác thực hiện trên thế hệ hiện tại để tạo ra một thế hệ khác với độ thích nghi tốt hơn.
Thao tác đầu tiên là sao chép nguyên mẫu một nhóm các cá thể tốt từ thế hệ trước rồi đưa
sang thế hệ sau (selection). Thao tác này đảm bảo độ thích nghi của thế hệ sau luôn được
giữ ở một mức độ hợp lý. Các cá thể được chọn thông thường là các cá thể có độ thích
nghi cao nhất.
Thao tác thứ hai là tạo các cá thể mới bằng cách thực hiện các thao tác sinh sản trên một
số cá thể được chọn từ thế hệ trước – thông thường cũng là những cá thể có độ thích nghi
cao. Có hai loại thao tác sinh sản : một là lai tạo tác lai tạo (crossover), hai là đột biến
(mutation). Trong thao tác lai tạo, từ gen của hai cá thể được chọn trong thế hệ trước sẽ
được phối hợp với nhau (theo một số quy tắc nào đó) để tạo thành hai gen mới.
Thao tác chọn lọc và lai tạo giúp tạo ra thế hệ sau. Tuy nhiên, nhiều khi do thế hệ khởi
tạo ban đầu có đặc tính chưa phong phú và chưa phù hợp nên các cá thể không rải đều
được hết không gian của bài toán). Từ đó, khó có thể tìm ra lời giải tối ưu cho bài toán.
Thao tác đột biến sẽ giúp giải quyết được vấn đề này. Đó là sự biến đổi ngẫu nhiên một
hoặc nhiều thành phần gen của một cá thể ở thế hệ trước tạo ra một cá thể hoàn toàn mới
ở thế thệ sau. Nhưng thao tác này chỉ được phép xảy ra với tần suất rất thấp (thường dưới
0.01), vì thao tác này có thể gây xáo trộn và làm mất đi những cá thể đã chọn lọc và lai
tạo có tính thích nghi cao, dẫn đến thuật toán không còn hiệu quả.

[min, max] bằng một chuỗi nhị phân A dài L bit. Lúc đó, ta sẽ chia miền [min, max]
(lượng hóa) thành 2
L
-1 vùng. Trong đó, kích thước một vùng là :
1
max min
2
L
g




Người ta gọi g là độ chính xác của số thực được biểu diễn bằng cách này (vì g quy định
giá trị thập phân nhỏ nhất của số thực mà chuỗi nhị phân dài L bit có thể biểu diễn được).
Giá trị của số thực x được biểu diễn qua chuỗi nhị phân sẽ được tính như sau :
x = min + Decimal(<A>)*g
trong đó Decimal(<A>) là hàm để tính giá trị thập phân nguyên dương của chuỗi nhị
phân A theo quy tắc đếm. Hàm này được tính theo công thức sau:
1 2 1 0
1 2 1 0
( ) .2 .2 .2 .2 .
L
L
Decimal A a a a a


      
Với a
i

15

Một hàm đánh giá không chính xác có thể làm mất đi các cá thể tốt trong quần thể. Hàm
thích nghi có thể không tuyến tính, không có đạo hàm, không liên tục bởi vì thuật toán di
truyền chỉ cần liên kết hàm thích nghi với các chuỗi số.
Chúng ta xây dựng hàm thích nghi f(x) không âm, có hai trường hợp sau:
 Đối với bài toán tìm cực tiểu hàm g(x):
khi
max
( )
g x C


khi
max
( )
g x C


Có thể lấy C
max
là giá trị lớn nhất của g (x) trong quần thể hiện tại.
 Đối với bài toán tìm cực đại hàm u(x):
khi
min
( ) 0
u x C
 

khi

( )
( )
0
u x C
f x





16

 Tính độ thích nghi f
i
, i = 1, 2,…,n của mỗi nhiễm sắc thể trong quần thể hiện hành,
với n là kích thước quần thể (số nhiễm sắc thể trong quần thể).
 Tìm tổng giá trị thích nghi toàn quần thể:
1
n
i
i
F f




 Tính xác suất chọn p
i
cho mỗi nhiễm sắc thể:
i

bằng cách ghép một hay nhiều đoạn gen của hai (hay nhiều) nhiễm sắc thể cha – mẹ với
nhau. Phép lai xảy ra với xác suất p
c
được thực hiện như sau:
 Đối với nhiễm sắc thể trong quần thể mới, phát sinh ngẫu nhiên một số r trong khoảng
[0;1], nếu r < p
c
thì nhiễm sắc thể được chọn để lai ghép.
 Ghép đôi các nhiễm sắc thể đã chọn được một cách ngẫu nhiên, đối với mỗi cặp
nhiễm sắc thể được ghép đôi, ta phát sinh ngẫu nhiên một số nguyên pos nằm trong
khoảng [0; m-1] (m là tổng chiều dài của một nhiễm sắc thể - tổng số gen). Số pos cho
biết vị trí của điểm lai. Điều này được minh họa bởi hình dưới đây.
Như vậy phép lai tạo ra hai chuỗi mới, mỗi chuỗi đều được thừa hưởng những đặc tính
lấy từ cha và mẹ chúng. Mặc dù phép lai ghép sử dụng lựa chọn ngẫu nhiên, nhưng nó
không được xem như là một lối đi ngẫu nhiên qua không gian tìm kiếm. Sự kết hợp giữa
17

tái sinh và lai ghép giúp cho thuật toán di truyền hướng việc tìm kiếm đến những vùng tốt
hơn. Dưới đây là hình minh họa cho phép lai cơ bản, các nhiễm sắc thể bắt chéo tại một
điểm.
Hình 2.2: Lai ghép hai nhiễm sắc thể 1 điểm bắt chéo
Vị trí lai
b
1
b
2
. . .

b
pos

m

c
1
c
2
. . .

c
pos
b
pos+1
. . . b
m

2.1.3.3 Đột biến (Mutation)
Đột biến là hiện tượng cá thể con mang một (một số) tính trạng không có trong mã di
truyền của cha mẹ. Phép đột biến xảy ra với xác suất p
m
, nhỏ hơn rất nhiều so với xác
suất lai p
c
.
Theo nghiên cứu của Kenneth De Jong thì:
 Tỷ lệ lai ghép trung bình: 0.6
 Tỷ lệ đột biến: 0.001
 Tỷ lệ tạo sinh: 0.399
18

Mỗi gen trong nhiễm sắc thể có thể có cơ hội bị đột biến như nhau, nghĩa là đối với mỗi
Nguồn: Giáo trình công nghệ tính toán phần mềm – Đại học sư phạm kỹ thuật tp. HCM
Bắt đầu
Khởi động
Đánh giá
Hội tụ?
Mã hóa
Chọn lọc
Sinh sản
Đột biến
Giải mã
Kết thúc