Giải thuật di truyền với bài toán người du lịch

Bài tập lớn môn học Trí tuệ nhân tạo 4

• GA có thể tìm kiếm trên các không gian giả thuyết có các phần tương
tác phức tạp, ở đó ảnh hưởng của mỗi phần lên toàn thể độ thích nghi
giả thuyết khó có thể mô hình.
• Thuật giải GA có thể được thực hiện song song và có thể tận dụng
thành tựu của phần cứng máy tính mạnh.

2. Thuật giải di truyền
Bài toán dành cho GAs là tìm kiếm trên không gian các giả thuyết ứng cử
để xác định giả thuyết tốt nhất. Trong GAs “giả thuyết tốt nhất” được định nghĩa
như là một giả thuyết tối ưu hóa một đại lượng số được định nghĩa trước cho bài
toán sắp tới, được gọi là độ thích nghi của giả thuyết. Ví dụ, nếu tác vụ học hỏi
là bài toán xấp xỉ một hàm chưa biết cho tập mẫu huấn luyện gồm dữ liệu đầu
vào và dữ liệu đầu ra, thì độ thích nghi có thể được định nghĩa như là độ chính
xác của giả thuyết trên dữ liệu huấn luyện này. Nếu tác vụ là học chiến lược chơi
cờ, độ thích nghi có thể là số ván thắng của chiến lược này khi đấu với các chiến
lược khác trong quần thể hiện tại.
Mặc dù các thuật giải di truyền được thực hiện thay đổi theo bài toán cụ thể,
nhưng chúng chia sẻ chung cấu trúc tiêu biểu sau: Thuật giải hoạt động bằng
cách cập nhật liên tục tập giả thuyết – được gọi là quần thể. Ở mỗi lần lặp, tất cả
các cá thể trong quần thể được ước lượng tương ứng với hàm thích nghi. Rồi
quần thể mới được tạo ra bằng cách lựa chọn có xác suất các cá thể thích nghi tốt
nhất từ quần thể hiện tại. Một số trong những cá thể được chọn được đưa nguyên
vẹn vào quần thể kế tiếp. Những cá thể khác được dùng làm cơ sở để tạo ra các
cá thể con bằng cách áp dụng các tác động di truyền: lai ghép và đột biến.

GA( Fitness, Fitness_threshold, p, r, m)

Bài tập lớn môn học Trí tuệ nhân tạo 5

{
// Fitness: hàm gán thang điểm ước lượng cho một giả thuyết
// Fitness_threshold: Ngưỡng xác định tiêu chuẩn dừng giài thuật tìm kiếm
// p: Số cá thể trong quần thể giả thuyết
// r: Phân số cá thể trong quần thể được áp dụng toán tử lai ghép ở mỗi
bước
// m: Tỉ lệ cá thể bị đột biến

• Khởi tạo quần thể: P  Tạo ngẫu nhiên p cá thể giả thuyết
• Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)
• while [max Fitness(h)] < Fitness_threshold do
Tạo thế hệ mới, P
S

1. Chọn cá thể: chọn theo xác suất (1 – r)p cá thể trong quần thể P
thêm vào P
S
. Xác suất Pr(h
i
) của giả thuyết h
i
thuộc P được tính
bởi công thức:
1
( )
Pr( )
( )
i
i
p
j
j
Fitness h
h
Fitness h
=
=
∑

2. Lai ghép: chọn lọc theo xác suất
2
r p×
cặp giả thuyết từ quần thể
P, theo Pr(h
i
) đã tính ở bước trên. Ứng với mỗi cặp <h
1
, h
2
>, tạo
ra hai con bằng cách áp dụng toán tử lai ghép. Thêm tất các các
con vào P
S
.
3. Đột biến: Chọn m% cá thể của P
S
với xác suất cho mỗi cá thể là
như nhau. Ứng với mỗi cá thể biến đổi một bit được chọn ngẫu
nhiên trong cách thể hiện của nó.
4. Cãp nhật: P  P
S.

5. Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)

Bài tập lớn môn học Trí tuệ nhân tạo 6

• Trả về giả thuyết trong P có độ thích nghi cao nhất.
}
Figure 1 : Các bước cơ bản của giải thuật



Bài tập lớn môn học Trí tuệ nhân tạo 7




Khởi tạo quần thể
Lựa chọn cha mẹ
Lai ghép
Đột biến
Điều kiện dừng
Đấu tranh sinh tồn
Các cá thể tốt nhất
TRUE
FALSE
Figure 2 : Lưu đồ giải thuật cơ bản


Bài tập lớn môn học Trí tuệ nhân tạo 8

3. Các toán tử di truyền
3.1 Lai ghép :
Phép lai là quá trình hình thành NST mới trên cơ sở NST cha mẹ, bằng cách
ghép một hay nhiều đoạn gen của hai (hay nhiều) NST cha mẹ khác nhau.
Các cặp cha mẹ được lựa chọn ngẫu nhiên và xác suất xảy ra lai ghép với
mỗi cặp được quy định từ trước.
Có nhiều cách lai ghép khác nhau:
• Lai ghép một điểm cắt, nhiều điểm cắt.

• Lai ghép nhiều đoạn.

3.2 Đột biến :
Đột biến là tình trạng NST con không có một (hoặc một số) tính trạng có
trong mã di truyền của cha mẹ.
Các cặp cha mẹ được lựa chọn ngẫu nhiên và xác suất xảy ra đột biến với
mỗi cặp được quy định từ trước, thường là rất nhỏ.
Các phép đột biến thường được sử dụng:
• Đảo bit.
• Hoán vị: Đổi vị trí của các gen với nhau.
• Đổi giá trị: Thay đổi giá trị tại một điểm gen.
• Đảo đoạn: Đảo thứ tự của một đoạn NST bất kì.

Bài tập lớn môn học Trí tuệ nhân tạo 9

4. Đấu tranh sinh tồn
Chọn những NST từ quần thể kết quả theo một quy tắc nào đó thay thế cho
cha mẹ để sinh ra thế hệ mới. Một số phương thức đấu tranh sinh tồn cơ bản:
• Tráo đổi hoàn toàn cha mẹ bằng con.
• Tráo đổi ngẫu nhiên: Chọn ngẫu nhiên k cha mẹ và thay thế bằng k
con mới.
• Chọn những cá thể ưu tú nhất trong quần thể.



Bài tập lớn môn học Trí tuệ nhân tạo 10

CHƯƠNG II : BÀI TOÁN NGƯỜI DU LỊCH (Travelling Salesman
Problem - TSP)

1. Lịch sử bài toán :
Bài toán người bán hàng (tiếng Anh: travelling salesman problem - TSP) là
một bài toán NP-Hard thuộc thể loại tối ưu tổ hợp được nghiên cứu trong lý
thuyết khoa học máy tính. Nội dung bài toán có thể hiểu khái quát như sau : Cho
trước một danh sách các thành phố và khoảng cách giữa chúng, tìm chu trình
ngắn nhất đi qua tất cả các thành phố đúng 1 lần.

Figure 3 22,775 Cities in Vietnam, derived from data from the National Imagery and Mapping Agency database of
geographic feature names.

Bài toán được nêu ra lần đầu tiên năm 1930 và là một trong những bài toán
được nghiên cứu sâu nhất trong tối ưu hóa. Nó thường được dùng làm thước đo
cho nhiều phương pháp tối ưu hóa. Mặc dù bài toán rất khó giải trong trường hợp
tổng quát, có nhiều phương pháp giải chính xác cũng như heuristic đã được tìm
ra để giải quyết một số trường hợp có tới hàng chục nghìn thành phố.
Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều
ứng dụng trong lập kế hoạch, hậu cần, cũng như thiết kế vi mạch, …
Nguồn gốc của bài toán người bán hàng vẫn chưa được biết rõ. Một cuốn sổ
tay dành cho người bán hàng xuất bản năm 1832 có đề cập đến bài toán này và

Bài tập lớn môn học Trí tuệ nhân tạo 11

có ví dụ cho chu trình trong nước Đức và Thụy Sĩ, nhưng không chứa bất kì nội
dung toán học nào.
Bài toán người bán hàng được định nghĩa trong thế kỉ 19 bởi nhà toán học
Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman.
Trường hợp tổng quát của TSP có thể được nghiên cứu lần đầu tiên bởi các nhà
toán học ở Vienna và Harvard trong những năm 1930.
Hassler Whitney ở đại học Princeton đưa ra tên bài toán người bán hàng
ngay sau đó.
Trong những năm 1950 và 1960, bài toán trở nên phổ biến trong giới
nghiên cứu khoa học ở Châu Âu và Mỹ. George Dantzig, Delbert Ray Fulkerson
và Selmer M. Johnson ở công ty RAND tại Santa Monica đã có đóng góp quan
trọng cho bài toán này, biểu diễn bài toán dưới dạng quy hoạch nguyên và đưa ra
phương pháp mặt phẳng cắt để tìm ra lời giải. Với phương pháp mới này, họ đã
giải được tối ưu một trường hợp có 49 thành phố bằng cách xây dựng một chu
trình và chứng minh rằng không có chu trình nào ngắn hơn. Trong những thập
niên tiếp theo, bài toán được nghiên cứu bởi nhiều nhà nghiên cứu trong các lĩnh
vực toán học, khoa học máy tính, hóa học, vật lý, và các ngành khác.
Năm 1972, Richard M. Karp chứng minh rằng bài toán chu trình Hamilton
là NP-đầy đủ, kéo theo bài toán TSP cũng là NP-đầy đủ. Đây là một lý giải toán
học cho sự khó khăn trong việc tìm kiếm chu trình ngắn nhất.
Một bước tiến lớn được thực hiện cuối thập niên 1970 và 1980 khi
Grötschel, Padberg, Rinaldi và cộng sự đã giải được những trường hợp lên tới
2392 thành phố, sử dụng phương pháp mặt phẳng cắt và nhánh cận.
Trong thập niên 1990, Applegate, Bixby, Chvátal, và Cook phát triển một
chương trình mang tên Concorde giải được nhiều trường hợp có độ lớn kỉ lục
hiện nay. Gerhard Reinelt xuất bản một bộ dữ liệu các trường hợp có độ khó
khác nhau mang tên TSPLIB năm 1991, và nó đã được sử dụng bởi nhiều nhóm

Bài tập lớn môn học Trí tuệ nhân tạo 12

nghiên cứu để so sánh kết quả. Năm 2005, Cook và cộng sự đã giải được một
trường hợp có 33810 thành phố, xuất phát từ một bài toán thiết kế vi mạch. Đây
là trường hợp lớn nhất đã được giải trong TSPLIB.
Đến nay bài toán TSP vẫn được tiếp tục nghiên cứu tìm ra lời giải cho các
bộ dữ liệu lớn hơn. Chẳng hạn bộ dữ liệu của nước Mĩ với 115,475 thành phố
người giải ra chu trình tối ưu được trao thưởng 500$ (thông tin chi tiết tại
http://www.tsp.gatech.edu/).

2. Phát biểu bài toán :
(*) Các khái niệm cơ bản về đồ thị sẽ không được trình bày trong báo cáo.
Phát biểu bài toán : Cho đồ thị đầy đủ n đỉnh vô hướng, có trọng số G = (V,
E). Tìm chu trình ݒ
ଵ
→ݒ
ଶ
→...ݒ
௡
→ݒ
ଵ
với ݒ
௜
∈ܸ,݅ = 1,݊
തതതതത
sao cho tổng trọng
số hành trình trên các cạnh (ݒ
௜
,ݒ
௜ାଵ
) và (ݒ
௡
,ݒ
ଵ
) là nhỏ nhất.
Một chu trình như vậy còn gọi là chu trình Hamilton, nó đi qua tất cả các
đỉnh của đồ thị đúng 1 lần. Đồ thị đầy đủ, luôn tồn tại chu trình Hamilton.

3. Phân tích độ phức tạp :
Bài toán TSP thuộc lớp bài toán NP-Khó (lớp các bài toán không có giải
thuật trong thời gian đa thức).
Việc thực hiện liệt kê hết tất cả các chu trình là điều gần như không thể với
số đỉnh lớn (đồ thị n đỉnh phải duyệt n! chu trình). Số chu trình phải duyệt tăng
rất nhanh khi số đỉnh n càng lớn. Ngay với 1 đồ thị 100 đỉnh, việc duyệt toàn bộ
cũng là điều rất khó thực hiện.


Bài tập lớn môn học Trí tuệ nhân tạo 13

CHƯƠNG III : ĐỀ XUẤT GIẢI THUẬT DI TRUYÊN GIẢI BÀI TOÁN
NGƯỜI DU LỊCH

1. Giải thuật đề xuất :
Nhóm đề xuất giải thuật di truyền đơn giản giải bài toán người du lịch. Giải
thuật được cài đặt bằng ngôn ngữ java.
Các bộ dữ liệu kiểm thử được lấy tại http://www.tsp.gatech.edu/ (cung cấp
các bộ dữ liệu chuẩn trên thực tế)

1.1 Mã hóa bài toán :
1.1.1 Mã hóa đồ thị :
Đồ thị được mã hóa bằng danh sách mảng các điểm và tọa độ tương ứng
của chúng. Dưới đây là ví dụ về bộ dữ liệu đồ thị chuẩn.
NAME : xit1083
COMMENT : Bonn VLSI data set with 1083 points
COMMENT : Uni Bonn, Research Institute for Discrete Math
COMMENT : Contributed by Andre Rohe
TYPE : TSP
DIMENSION : 1083
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 0 105
2 0 111
3 0 15
… … …

Xem chi tiết: Giải thuật di truyền với bài toán người du lịch

THỊ TRƯỜNG HIỆU QUẢ

Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
Giả thuyết thị trường hiệu quả (hay lý thuyết thị trường hiệu quả) (efficient market hypothesis)
là một giả thuyết của lý thuyết tài chính khẳng định rằng các thị trường tài chính là hiệu quả
(efficient), rằng giá của chứng khoán (securities) trên thị trường tài chính, đặc biệt là thị trường
chứng khoán, phản ánh đầy đủ mọi thông tin đã biết. Do đó không thể kiếm được lợi nhuận
bằng cách căn cứ vào các thông tin đã biết hay những hình thái biến động của giá cả trong quá
khứ. Có thể nói một cách ngắn gọn là các nhà đầu tư không thể khôn hơn thị trường.
Các nhà kinh tế thường định nghĩa ba mức độ của thị trường hiệu quả, được phân biệt bởi mức
độ thông tin đã phản ánh trong giá chứng khoán.
 Mức độ hiệu quả yếu: giá cả phản ánh đầy đủ thông tin đã công bố trong quá khứ, giá cả theo
bước ngẫu nhiên. (Nghĩa là dựa vào thông tin trong quá khứ thì nhà đầu cơ không thắng được
thị trường.)
 Mức độ hiệu quả vừa phải: giá cả phản ảnh không chỉ giá quá khứ mà còn phản ảnh tất cả các
thông tin đã công bố khác. Giá cả sẽ điều chỉnh ngay lập tức trước các thông tin đó như là việc
công bố tỷ suất sinh lợi quý vừa qua, một phát hành cổ phần mới, một đề nghị sát nhập 2 công
ty… (Nhà đầu cơ không thể dựa vào thông tin trong quá khứ cũng như thông tin vừa được
công bố , vì ngay khi thông tin được công bố, giá cả đã thay đổi phản ánh đầy đủ thông tin vừa
công bố.)
 Mức độ hiệu quả mạnh: giá cả phản ảnh tất cả các thông tin có thể có được bằng cách phân
tích tỉ mỉ về công ty và nền kinh tế, sẽ có các nhà đầu tư may mắn và không may mắn. Nhưng
sẽ không có bất kỳ siêu giám đốc nào liên tục đánh bại thị trường.
Các chuyên gia phân tích đầu tư có thể giúp làm cho thị trường hiệu quả
Có hai loại chuyên gia phân tích đầu tư:
 Các nhà phân tích cơ bản: là những người nghiên cứu phân tích việc kinh doanh của công ty
và cố gắng phát hiện thông tin về khả năng sinh lời tác động đến giá cổ phần. Các nỗ lực cạnh
tranh giữa các nghiên cứu cơ bản sẽ có khuynh hướng bảo đảm rằng giá cả phản ảnh tất cả các
thông tin liên quan và sự thay đổi giá cả là không thể dự đoán được.
 Các nhà phân tích kỹ thuật: là những người nghiên cứu phân tích hồ sơ giá cả và tìm kiếm các
khuynh hướng hay các chu kỳ. Các nỗ lực trong nghiên cứu kỹ thuật thường sẽ đảm bảo rằng
giá cả hiện tại phản ảnh tất cả thông tin trong chuỗi giá cả quá khứ và các thay đổi giá tương lai
không thể dự báo được từ giá quá khứ.
I.3 Các thị trường hiệu quả: chứng cứ
Hình 4 Mỗi điểm trong các biểu đồ rải rác dưới đây cho thấy tỷ suất sinh lợi trong các tuần lễ kế tiếp của bốn chỉ
số thị trường chứng khoán giữa tháng 8/1987 và tháng 4/1998. Các điểm rải rác rộng cho thấy hầu như không có
tương quan giữa tỷ suất sinh lợi trong một tuần và tỷ suất sinh lợi trong tuần kế tiếp. Bốn chỉ số này là FTSE 100
(Anh), chỉ số trung bình công nghiệp Dow Jones (Mỹ), DAX (Đức), CAC 40 (Pháp).
Nhóm 08 – Đêm 1 TCDN K20 Trang 5
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
Trong các năm tiếp theo khám phá của Maurice Kendall, các tạp chí tài chính đăng đầy thông
tin về các cuộc thử nghiệm về giả thuyết thị trường hiệu quả. Để thử nghiệm hình thức yếu của
giả thuyết, các nhà nghiên cứu đã đo lường khả năng sinh lợi của một vài quy luật giao dịch
được sử dụng bởi các nhà phân tích kỹ thuật – là những người công bố rằng đã tìm thấy các
mẫu mực trong giá cả cổ phần. Họ cũng áp dụng các thử nghiệm thống kê như là thử nghiệm
mà chúng ta đã mô tả khi tìm kiếm các mẫu mực trong tỷ suất sinh lợi của cổ phần Microsoft.
Ví dụ, trong hình 4, chúng ta đã dung cùng thử nghiệm đó để tìm kiếm mối liên hệ giữa tỷ suất
sinh lợi thị trường chứng khoán trong các tuần lễ kế tiếp. Có vẻ như trên thế giới chỉ có một vài
mẫu mực tỷ suất sinh lợi từ tuần này sang tuần khác.
Nhóm 08 – Đêm 1 TCDN K20 Trang 6
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
Hình 5 Thành quả của các cổ phần của các công ty mục tiêu so với thành quả của thị trường. Giá của cổ phần
mục tiêu tăng vọt vào ngày công bố, nhưng từ đó trở đi, không có chuyển động giá bất thường nào. Công bố về
việc sáp nhập có vẻ như đã được phản ánh đầy đủ vào giá cổ phần trong ngày công bố.
Để phân tích hình thức hiệu quả vừa phải của giả thuyết thị trường hiệu quả, các nhà nghiên
cứu đã đo lường xem giá cả chứng khoán đáp ứng nhanh đến mức độ nào đối với các mục tin
tức khác nhau, như là công bố tỷ suất sinh lợi hay cổ tức, tin về một vụ sáp nhập, hay tin tức
kinh tế vĩ mô. Hình 5 minh họa việc công bố các tin tức như vậy được phản ánh ngay lập tức
vào giá cả chứng khoán như thế nào. Đồ thị cho thấy chuyển động tăng giá của một mẫu gồm
194 doanh nghiệp là mục tiêu của nỗ lực sáp nhập. Trong hầu hết các cuộc sáp nhập, doanh
nghiệp mua lại sẵn sàng chi trả một chênh lệch giá lớn so giá với thị trường hiện hành của
doanh nghiệp bị mua lại; vì vậy khi một doanh nghiệp trở thành mục tiêu của một nỗ lực sáp
nhập, giá cổ phần của nó tăng trước dự báo về chênh lệch giá sáp nhập. Hình 5 cho thấy rằng
vào ngày công chúng được biết về nỗ lực sáp nhập (ngày 0 trong biểu đồ), giá cổ phần của mục
tiêu tiêu biểu tăng vọt rất cao. Giá chứng khoán điều chỉnh ngay tức khắc. Sau chuyển động giá
lớn vào ngày công bố, việc tăng giá ngưng lại và không có chuyển biến thêm nào khác trong
giá cổ phần, dù tăng hay giảm. Như vậy, trong vòng ngày hôm đó thì giá cổ phần mới phản ánh
rõ rệt độ lớn (ít nhất là trung bình) của chênh lệch giá sáp nhập.
Một nghiên cứu của Patell và Wolfson cho thấy giá cả biến động nhanh như thế nào khi thông
tin mới trở nên có sẵn. Họ tìm thấy rằng, khi một doanh nghiệp thông báo thu nhập mới nhất
Nhóm 08 – Đêm 1 TCDN K20 Trang 7
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
của mình hay công bố một thay đổi cổ tức, phần chính của điều chỉnh giá cả xảy ra trong vòng
5 đến 10 phút sau khi thông báo.
Các thử nghiệm về hình thức hiệu quả mạnh của giả thuyết đã xem xét các khuyến nghị của
các nhà phân tích chứng khoán chuyên nghiệp và đã tìm kiếm các quỹ hỗ tương hay quỹ hưu
bổng có thể có thành quả vượt trội so với thị trường một cách mà chúng ta có thể dự đoán
được. Một vài nhà nghiên cứu đã tìm thấy một thành quả khá cao liên tục, nhưng nhiều nhà
nghiên cứu khác đã kết luận rằng các quỹ được quản lý một cách chuyên nghiệp đã không
thành công trong việc thu hồi lại các chi phí quản lý. Ta hãy xem ở hình 6 chẳng hạn, được rút
ra từ một nghiên cứu của Mark Carhart về thu nhập trung bình của gần 1,500 quỹ hỗ tương
Mỹ. Bạn có thể thấy rằng trong một vài năm các quỹ hỗ tương đã đánh bại thị trường, nhưng
thường thì kết quả ngược lại. Hình 6 cung cấp một so sánh tương đối thô sơ, vì các quỹ hỗ
tương thường chuyên về các khu vực riêng biệt của thị trường, như là các cổ phần có beta thấp
hay cổ phần của các doanh nghiệp lớn, có thể có tỷ suất sinh lợi dưới trung bình. Để kiểm soát
các chênh lệch như vậy, mỗi quỹ cần được so sánh với một doanh mục chuẩn của các chứng
khoán tương tự. Nghiên cứu của Mark Carhart đã làm điều này, nhưng thông điệp vẫn không
thay đổi: tỷ suất sinh lợi các quỹ thu được thấp hơn danh mục chuẩn sau chi phí và chỉ vừa
bằng các mức chuẩn trước chi phí.
Hình 6 Tỷ suất sinh lợi hàng năm bình quân của 1,493 quỹ hỗ tương Mỹ và chỉ số thị trường 1962 – 1992. Lưu ý
rằng các quỹ hỗ tương có thành quả thấp hơn thị trường trong khoảng phân nữa số năm.
Nguồn: M.M. Carhart, “Về tính bền trong thành quả của quỹ hỗ tương”,
Tạp chí tài chính 52 (3/1997), tr. 57 – 82.
Nhóm 08 – Đêm 1 TCDN K20 Trang 8
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
Chứng cứ này về hình thức hiệu quả mạnh đã chứng tỏ một cách đủ thuyết phục rằng nhiều
quỹ được quản lý một cách chuyên nghiệp đã từ bỏ việc theo đuổi thành quả cao. Họ chỉ “mua
chỉ số”, tức tối đa hoá việc đa dạng hoá và thối thiểu hoá chi phí quản lý danh mục. Các
chương trình hưu bổng doanh nghiệp hiện đầu tư trên một phần tư của vốn cổ phần Mỹ họ
đang nắm giữ vào các quỹ chỉ số.
II. CÁC BÀI TOÁN ĐỐ VÀ CÁC BẤT THƯỜNG CÓ Ý NGHĨA GÌ ĐỐI VỚI GIÁM
ĐỐC TÀI CHÍNH
Các nhà nghiên cứu trước đây đã kết luận rằng giả thuyết thị trường hiệu quả là một mô hình
phản ánh rất tốt thực tế. Họ tin tưởng vào giả thuyết này đến nỗi nếu có một nghiên cứu nào
chống lại cũng bị xem xét và nghi ngờ. Tuy nhiên, dần dần, khi mà các độc giả của các tạp chí
tài chính bắt đầu nghi ngờ vào giả thuyết này thì càng ngày người ta càng đưa ra được nhiều
chứng cứ cho những nghi ngờ của mình mà các nhà đầu tư đã không khai thác được.
Bài toán đố đầu tiên – hiệu ứng doanh nghiệp nhỏ
Chẳng hạn như một bài toán đố mà các nhà đầu tư đã chứng kiến được – đó là bài toán đố tỷ
suất sinh lợi của chứng khoán các doanh nghiệp nhỏ cao một cách trên bình thường. Quan sát
trên thị trường chứng khoán Mỹ, người ta nhận thấy rằng, nếu bỏ 1 USD đầu tư vào các cổ
phần các doanh nghiệp nhỏ vào năm 1926, thì hơn 70 năm sau, tức là đến năm 1997, 1 USD đó
đã tăng giá lên hơn 5 lần (tương đương 5,526 USD). Trong khi đó, nếu bỏ 1 USD đó vào đầu
tư cổ phần các doanh nghiệp lớn thì chỉ thu được 1,828 USD. Mặc dù các doanh nghiệp nhỏ có
hệ số beta
1
cao hơn nhưng chênh lệch trong hệ số này không đủ lớn để giải thích chênh lệch
trong tỷ suất sinh lợi.
Hiện tại thì điều này có thể được giải thích với một trong ba lý do sau đây:
Thứ nhất, có thể là các nhà đầu tư đã yêu cầu một tỷ suất sinh lợi mong đợi cao hơn từ các
doanh nghiệp nhỏ để đền bù cho thêm một yếu tố rủi ro nào đó mà đã không được ghi lại trong
mô hình định giá tài sản vốn
2
đơn giản. Đó là lý do tại sao chúng ta cần phải nêu lại câu hỏi là
liệu hiệu ứng doanh nghiệp nhỏ có là chứng cứ chống lại mô hình CAPM không.
Thứ hai, lý thuyết trùng hợp – thành quả cao hơn của các doanh nghiệp nhỏ có thể chỉ là một
trùng hợp ngẫu nhiên. Mặc dù vậy, cũng có những nghiên cứu đưa ra chứng cứ chống lại lý
thuyết này. Những người không ủng hộ lý thuyết này đã chỉ ra rằng không phải chỉ ở Mỹ mà ở
1 Beta là hệ số đo lường độ nhạy cảm của một chứng khoán với các biến động thị trường (Sách Tài chính doanh
nghiệp hiện đại - Chương 4 – Rủi ro). Giả dụ khi Beta của một cổ phần bằng 1,1, nếu tương lai là những gì lặp
lại trong quá khứ thì hệ số này có ý nghĩa là, khi thị trường tăng thêm 1%, thì giá cổ phần này sẽ tăng thêm
1,1%. Khi thị trường giảm 2%, giá cổ phần giảm 2x1,1=2,2%.
2 Mô hình định giá tài sản vốn là một mô hình mô tả mối quan hệ giữa rủi ro và lợi nhuận kỳ vọng. Nó được
xây dựng dựa trên một trong những giả thuyết là thị trường vốn hiệu quả. Và mô hình này có hàm ý rằng tỷ suất
sinh lợi của một chứng khoán có mối tương quan xác định với beta của nó (Sách Tài chính doanh nghiệp hiện
đại – Chương 5 – Rủi ro và tỷ suất sinh lợi)
Nhóm 08 – Đêm 1 TCDN K20 Trang 9
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
những nước khác, tỷ suất sinh lợi của cổ phần các doanh nghiệp nhỏ cũng cao hơn, hiệu ứng
doanh nghiệp nhỏ là một hiện tượng lan tỏa. Tuy nhiên, những người ủng hộ thì cho rằng, nếu
quan sát, ta sẽ thấy tỷ suất sinh lợi của cổ phần doanh nghiệp nhỏ ở Mỹ chỉ giới hạn trong một
thời kỳ tương đối ngắn. Đến đầu thập niên 1960, cổ phần doanh nghiệp nhỏ và doanh nghiệp
lớn là ngang nhau. Tiếp đến trong hai thập kỷ kế, khoảng cách giữa tỷ suất sinh lợi của 2 loại
doanh nghiệp này lại rộng ra và rồi lại thu hẹp lại trong thập niên 1980. Và nếu chỉ nhìn vào
các năm gần đây, thì có thể chúng ta có thêm một lý thuyết mới – hiệu ứng doanh nghiệp lớn.
Thứ ba, có thể có những ngoại lệ của lý thuyết thị trường hiệu quả. Ngoại lệ này đã cho các
nhà đầu tư một cơ hội để tạo tỷ suất sinh lợi cao một cách có thể tiên đoán được trước qua một
thời kỳ dài hai thập kỷ. Các nhà đầu tư có thể tận dụng cái bất thường này để thu được các món
tỷ suất sinh lợi một cách dễ dàng. Tuy nhiên, thực tế là rất khó để làm giàu bằng cách này.
Giáo sư Richard Roll, một nhà nghiên cứu về những bất thường của thị trường hiệu quả, đã tận
dụng những “bất hiệu quả” phát hiện được và sử dụng số tiền lớn của mình vào các giao dịch
thật sự theo một quy luật giao dịch do các “bất hiệu quả” đề xướng. Tuy nhiên, ông thừa nhận
rằng ông chưa bao giờ tìm được một quy luật nào có hiệu lực trên thực tế, theo ý nghĩa là mang
lại tỷ suất sinh lợi sau chi phí nhiều hơn tỷ suất sinh lợi của một sách lược mua – và – giữ.
Các nhà đầu tư có đáp ứng chậm với thông tin mới không?
Chúng ta đề cập đến nhiều hiệu ứng doanh nghiệp nhỏ, nhưng không thiếu các bài toán đố và
các bất thường khác. Một số liên quan đến hành vi ngắn hạn của giá cổ phần. Ví dụ, tỷ suất
sinh lợi trong tháng giêng có vẻ cao hơn trong các tháng khác, trong ngày thứ hai có vẻ thấp
hơn các ngày khác trong tuần, và hầu hết tỷ suất sinh lợi trong ngày đến vào lúc đầu ngày và
cuối ngày.
Để có cơ may làm ra tiền từ các mẫu mực ngắn hạn như vậy, bạn cần phải là một người mua
bán cổ phần chuyên nghiệp, với một con mắt dán trên màn hình máy tính và con mắt kia trên
số tiền thưởng hàng năm của bạn. Nếu bạn là một giám đốc tài chính của doanh nghiệp, các mô
hình ngắn hạn trong giá cổ phần có thể gợi lên các câu đố, nhưng chúng ít khi làm thay đổi các
quyết định tài chính chủ yếu về dự án nào cần đầu tư và được tài trợ như thế nào. Mối quan
tâm tạo rắc rối hơn cho một giám đốc tài chính doanh nghiệp là khả năng có thể phải mất nhiều
năm trước khi các nhà đầu tư nắm bắt được ý nghĩa của thông tin mới. Các nghiên cứu về
chuyển biến giá cả hàng ngày và hàng giờ mà chúng ta đề cập ở trên có thể không ghi nhận
việc định giá sai dài hạn này, nhưng sau đây là hai thí dụ về việc chậm trễ rõ rệt trong phản
ứng với các tin tức.
Bài toán phát hành mới: khi các doanh nghiệp lần đầu tiên phát hành cổ phần ra công chúng,
các nhà đầu tư thường đổ xô đến mua. Tính trung bình, những người đủ may mắn mua được cổ
phần thực hiện được một lãi vốn ngay lập tức. Tuy nhiên, Loughran và Ritter, là người đã
nghiên cứu các phát hành mới giữa 1970 và 1990, tìm thấy rằng các món lãi sớm này đã biến
thành lỗ. Tổng cộng trong 5 năm theo sau việc phát hành ra công chúng ban đầu các cổ phần đã
Nhóm 08 – Đêm 1 TCDN K20 Trang 10
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
thực hiện có thành quả tệ hơn khoảng 30% so với một danh mục cổ phần của các doanh nghiệp
có quy mô tương tự. Loughran và Ritter tiếp tục theo dõi các phát hành cổ phần của các doanh
nghiệp đã giao dịch ngoài công chúng trước đây và tìm thấy các thành quả dưới tiêu chuẩn
tương tự trong vòng 5 năm sau phát hành.
Hình 7 Tỷ suất sinh lợi từ 4.753 cung ứng ra công chúng từ 1970 đến 1990 trong mỗi kỳ 5 năm theo sau phát
hành, đối chiếu với tỷ suất sinh lợi từ một mẫu các doanh nghiệp tương ứng không phát hành.
Bài toán công bố tỷ suất sinh lợi: Hình 8 tiếp theo dưới đây (thể hiện thành quả cổ phần theo
sau công bố tỷ suất sinh lợi tốt hay xấu ngoài mong đợi trong vòng các năm từ 1974 đến 1986)
cho chúng ta kết quả sau: trong vòng 2 tháng sau công bố, có khoảng 10% cổ phần của các
doanh nghiệp được công bố tỷ suất sinh lợi tốt nhất có thu nhập cao vượt trội (hơn 4%) so với
thu nhập các cổ phần của các doanh nghiệp được công bố tỷ suất sinh lợi thấp nhất. Từ đó cho
thấy hình như các nhà đầu tư đã không nhận biết ý nghĩa đầy đủ của việc công bố tỷ suất sinh
lợi và chỉ nhận ra khi có thêm thông tin.
Tuy nhiên, các nghiên cứu này chưa đề cập đến các bất thường dài hạn. Và các nhà nghiên cứu
thì vẫn đang tiếp tục tìm kiếm lời giải đáp từ các nghiên cứu này. Có ý kiến cho rằng câu trả lời
nằm ở tâm lý học hành vi. Các nhà tâm lý học đã quan sát rằng các cá nhân thường phản ứng
thái quá trước thông tin trong quá khứ. Nếu đúng như vậy thì lời giải đáp có vẻ là do sự phấn
khởi mà các nhà đầu tư dành để chào mừng lần phát hành cổ phần đầu tiên của một công ty có
vẻ được nối tiếp bằng một quay lại dần với thực tế.
Hình 8 Các thu nhập cao trên bình thường tích lũy của cổ phần của các doanh nghiệp trong thời gian 60 ngày
tiếp theo một công bố tỷ suất sinh lợi quý. 10% cổ phần với tin tức tỷ suất sinh lợi tốt nhất (nhóm 10) vượt quá cổ
phần của các doanh nghiệp có tin tức xấu nhất (nhóm 1) hơn 10%.
Nhóm 08 – Đêm 1 TCDN K20 Trang 11
Nguồn: “Bài toán phát hành mới” của R.Loughran và J.R. Ritter, Tạp chí tài chính 50 (1995). Tr. 23-561
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
Nguồn: “Chuyển biến sau công bố tỷ suất sinh lợi: đáp ứng giá cả chậm trễ hay phần bù rủi ro?”
của V.L Bernard và J.K. Thomas, tạp chí nghiên cứu kế toán 27 (phụ trang 1989), tr. 1 – 36.
Hiện nay, khuynh hướng phản ứng thái quá này có thể đúng, nhưng nó vẫn chưa giải thích
được bài toán dài hạn khác, các phản ứng dưới mức của các nhà đầu tư trước các công bố tỷ
suất sinh lợi. Trừ khi chúng ta có một lý thuyết về tính cách con người có thể cho chúng ta biết
khi nào các nhà đầu tư sẽ phản ứng thấp và khi nào phản ứng thái quá, chúng ta chỉ có thể tạm
thời chấp nhận lý thuyết thị trường hiệu quả, mà trong đó các phản ứng dưới mức và các phản
ứng thái quá đều có khả năng bằng nhau.
Cuộc khủng hoảng 1987
Vào ngày thứ hai (19/10/1987), chỉ số công nghiệp trung bình Dow Jones (Dow) giảm 508.32
điểm, sụt 23% trong một ngày. Ngay sau sụp đổ này, mọi người đều giật mình và đưa ra câu
hỏi: “Ai là người có tội?” và “Giá cả có phản ánh các giá trị cơ bản không?”
Nhóm nghi ngờ đầu tiên là các nhà mua bán song hành chỉ số. Các nhà đầu tư tìm thấy rằng dễ
rút khỏi thị trường tài chính bằng các hợp đồng giao sau hơn là bằng cách bán cổ phần cá nhân,
và đã dẫn đến các giao dịch giao sau xuống thấp hơn chỉ số thị trường chứng khoán.
Nhóm nghi ngờ thứ hai là các nhà đầu tư định chế lớn đang cố gắng thực hiện các kế hoạch
bảo hiểm danh mục. Bảo hiểm danh mục nhằm mục đích đặt một sàn trên giá trị của một danh
mục vốn cổ phần bằng cách tăng dần bán cổ phần và mua các chứng khoán nợ ngắn hạn an
toàn khi giá cổ phần sụt. Như vậy áp lực bán làm sụt giá cổ phần và mua các chứng khoán nợ
ngắn hạn an toàn khi giá cổ phần sụt. Vào ngày 19/10 này, một nhà đầu tư định chế đã bán cổ
Nhóm 08 – Đêm 1 TCDN K20 Trang 12
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
phần và hợp đồng giao sau tổng cộng đến 1.7 tỷ USD. Nguyên nhân trực tiếp của việc cổ phần
sụt giá ngày thứ hai đen tối đó có thể là cả đàn voi đang cố thoát ra qua cùng một lối hep.
Nhà kinh tế học Richard Roll tin rằng sự suy giảm tự nhiên của thị trường chứng khoán toàn
cầu phủ nhận lập luận rằng kinh doanh chênh lệch là lý do dẫn tới khủng hoảng. Ông Roll cho
rằng chiến lược kinh doanh này được sử dụng đầu tiên ở Mỹ. Nếu kinh doanh chênh lệch gây
ra dự suy giảm của thị trường thì tại sao các thị trường như Úc và Hồng Kông nơi mà kinh
doanh chênh lệch không phổ biến, vẫn suy giảm? Dù cho những thị trường này có thể đạt đến
mức độ kinh doanh chuyên nghiệp như Mỹ, Roll cũng đưa ra những nhận xét không khác mấy.
Cuộc khủng hoảng bắt đầu vào ngày 19 tháng 10 tại Hồng Kông, lan sang phía Tây đến Châu
Âu, và tấn công vào thị trường Mỹ chỉ sau khi Hồng Kông và các thị trường khác đã suy giảm
ở mức đáng kể.
Một lý thuyết khác cho rằng cuộc khủng hoảng là kết quả của sự tranh chấp về chính sách tiền
tệ giữa các nước công nghiệp G7, theo đó Mỹ muốn tăng giá đồng đôla và kiềm chế lạm phát
nhằm thắt chặt chính sách nhanh hơn các nước Châu Âu. Theo quan điểm này, cuộc khủng
hoảng nổ ra khi thị trường chứng khoán Hồng Kông – trợ lực của đồng đôla – gãy vụn và điều
này gây ra cuộc khủng hoảng nói riêng.
Không có thông tin cơ bản mới rõ ràng nào để biện minh cho một sụt giảm nghiêm trọng và lan
rộng như vậy trong giá trị cổ phần.Vì lý do này, ý tưởng giá thị trường là ước tính tốt nhất giá
trị nội tại có vẻ ít thuyết phục trước khi xảy ra cuộc khủng hoảng. Có thể lý thuyết thị trường
hiệu quả lại là một hình thức khác của tổn thất các cuộc khủng hoảng ?
Biến cố tháng 10 năm 1987 nhắc nhở chúng ta việc định giá cổ phần thường từ đầu đặc biệt
khó đến thế nào.
Ví dụ : Trong tháng 1 năm 2003, cổ tức mong đợi hàng năm của Standard & Poor’s vào
khoảng 16.7. Giả dụ cổ tức này được mong đợi tăng với một tốc độ đều đặn 10%/năm và các
nhà đầu tư đòi hỏi một tỷ suất sinh lợi hàng năm 11.4% từ các cổ phần thường.
DIV 16.7
PV = = 1,193 =
r – g 0.114 - 0.10
Tăng trưởng có thể chỉ là 9.6%/năm, điều này sẽ đưa đến một điều chỉnh giảm 22% trong ước
tính của bạn về mức đúng của chỉ số, từ 1,193 xuống 928.
DIV 16.7
PV = = 928 =
r – g 0.114 - 0.96
Nhóm 08 – Đêm 1 TCDN K20 Trang 13
Đề tài số 4 Giảng viên: PGS.TS Trần Ngọc Thơ
Nói cách khác, một sụt giá giống như ngày trong ngày thứ hai đen tối hẵn có thể đã xảy ra vào
tháng 01/2003 nếu các nhà đầu tư đột nhiên trở nên yếu kém lạc quan khoảng 0.04% về tăng
trưởng cổ tức tương lai.
Khó khăn của việc định giá cổ phần thường từ đầu có hai hậu quả quan trọng:
Thứ nhất, các nhà đầu tư luôn định giá cổ phần thường tương ứng với giá của ngày hôm qua
hay giá của ngày hôm nay với chứng khoán có thể so sánh. Nếu thông tin này đúng thì các nhà
đầu tư càng tin mức thị trường hôm nay là đúng và ngược lại có thể gây ra một cuộc rối loạn và
giá cả biến động trước khi thiết lập một chuẩn mực mới.
Thứ hai, giả thuyết giá cổ phần luôn luôn đúng với giá trị nội tại hầu như không thể kiểm
chứng. Cuộc khủng hoảng đã không bác bỏ giả thuyết này một cách khẳng định, nhưng hiện
nay nhiều người cho rằng giả thuyết trở nên kém thuyết phục.
Tuy nhiên cuộc khủng hoảng đã không phá hủy chứng cứ thị trường hiệu quả về giá tương đối.
Ví dụ: Quaker Oast được bán với giá 53$/cổ phần vào tháng 6/1998. Chúng ta không thể chứng
minh giá trị nội tại đúng là 53$ nhưng chúng ta có thể tin tưởng giá của Quaket Oast bằng với
giá của Heinz (52$) vì hai công ty có cùng tỷ suất sinh lợi mỗi cổ phần, trả cổ tức tương tự và
có triển vọng tương tự. Hơn nữa, nếu một trong hai công ty công bố tỷ suất sinh lợi cao hơn
ngoài mong đợi chúng ta có thể tin rằng giá cổ phần sẽ đáp ứng ngay tức khắc và không thiên
vị.
Các bất thường thị trường và giám đốc tài chính
Khi doanh nghiệp phát hành chứng khoán mới, Giám đốc tài chính cần tin rằng: doanh nghiệp
có thể xác định được một mức giá hợp lý. Nhưng một trong hai lý do sau sẽ lý giải cho việc
này có thể không thể như vậy:
Thứ nhất, hình thức mạnh của giả thuyết thị trường hiệu quả có thể không đúng 100%, vì vậy
giám đốc tài chính có thể có thông tin mà các nhà đầu tư khác không có.
Thứ hai, các nhà đầu tư có thể có cùng thông tin như ban giám đốc doanh nghiệp nhưng lại
phản ứng chậm. Phần trên của bài này đã cho một vài chứng cứ của việc các phát hành chứng
khoán mới có khuynh hướng tiếp theo là tỷ suất sinh lợi chứng khoán thấp trong thời gian kéo
dài.
Như vậy, khi phát hành chứng khoán mới, nếu cổ phần của doanh nghiệp thực sự được định
giá cao, doanh nghiệp có thể bán thêm cổ phần và sử dụng số tiền này để đầu tư vào các chứng
khoán thị trường vốn khác. Nhưng đừng bao giờ phát hành cổ phần để đầu tư vào một dự án
cung ứng một tỷ suất sinh lợi thấp hơn mức mà doanh nghiệp có thể kiếm được bằng cách khác
trong thị trường vốn. Một dự án như vậy sẽ có một NPV âm. Tuy nhiên, nếu chọn cách mua cổ
phần thường ở thị trường, trong một thị trường hiệu quả, các vụ mua như vậy luôn luôn có
NPV bằng 0 (tức là cao hơn nếu chọn phương án đầu tư vào dự án có NPV âm)
Nhóm 08 – Đêm 1 TCDN K20 Trang 14

Xem chi tiết: THỊ TRƯỜNG HIỆU QUẢ