i

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
*** ĐÀO NGỌC PHONG TÊN ĐỀ TÀI LUẬN ÁN

NGHIÊN CỨU NGỮ NGHĨA TRONG HỆ LẬP TRÌNH
GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM NỐI CÂY VÀ
ỨNG DỤNG TRONG XẤP XỈ HÀM Q

CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN
MÃ SỐ: 62480104
LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC
1. GS.TS NGUYỄN THANH THỦY
2. PGS.TS NGUYỄN XUÂN HOÀI

Hà Nội - 2014

iii

MỤC LỤC

LỜI CAM ĐOAN vi
LỜI CẢM ƠN vii
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT viii
DANH MỤC CÁC BẢNG ix
DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ x
GIỚI THIỆU CHUNG 1
MỤC ĐÍCH 1
MỤC TIÊU NGHIÊN CỨU 3
PHƯƠNG PHÁP NGHIÊN CỨU 3
CÁC ĐÓNG GÓP CHÍNH 4
TỔNG QUAN VỀ CẤU TRÚC CỦA LUẬN ÁN 5
CHƯƠNG 1. TỔNG QUAN 6
1.1 GIẢI THUẬT TIẾN HÓA 6
1.2 GIẢI THUẬT DI TRUYỀN 7
1.3 LẬP TRÌNH GEN 9
1.3.1 Lập trình Gen chuẩn có cấu trúc cây 10
1.3.2 Một số vấn đề với lập trình Gen chuẩn có cấu trúc cây 14

3.3.2 Thử nghiệm 74
KẾT LUẬN CHƯƠNG 78
CHƯƠNG 4. ỨNG DỤNG 79
4.1 BÀI TOÁN HỌC XẤP XỈ HÀM Q VÀ HÀM NGƯỢC Q 79
4.1.1 Hàm Q 79
4.1.2 Một số dạng xấp xỉ do chuyên gia đề xuất 81
4.1.3 Hàm ngược Q 82
4.2 ỨNG DỤNG HỌC XẤP XỈ HÀM Q 83
4.2.1 Xác định hàm thích nghi với bài toán học xấp xỉ hàm Q 83
4.2.2 Thiết kế thí nghiệm 87
4.2.3 Kết quả và nhận xét 89
4.3 ỨNG DỤNG HỌC XẤP XỈ HÀM NGƯỢC Q 93
v

4.3.1 Xác định hàm thích nghi với bài toán học xấp xỉ hàm ngược Q 93
4.3.2 Thiết kế thí nghiệm và kết quả 94
KẾT LUẬN CHƯƠNG 98
KẾT LUẬN 99
HƯỚNG NGHIÊN CỨU VÀ PHÁT TRIỂN CỦA LUẬN ÁN 101
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 102
TÀI LIỆU THAM KHẢO 103

vi

LỜI CAM ĐOAN
Qua đây, cho phép tác giả xin cảm ơn Quỹ Phát triển Khoa học và Công
nghệ Quốc gia đã tài trợ một phần cho nghiên cứu này.
Tác giả xin cảm ơn các Thầy, Cô trong Bộ môn Hệ thống thông tin - Viện
Công nghệ thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội.
Luận án này, như một món quà tinh thần, xin đáp lại những niềm quan
tâm, mong mỏi của mọi thành viên trong gia đình, đó là một trong những nguồn
động viên để tác giả nỗ lực học tập, nghiên cứu.

viii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Ký hiệu
viết tắt
Ký hiệu đầy đủ Diễn giải
EA Evolutionary Algorithms Giải thuật tiến hóa
ES Evolutionary Strategies Chiến lược tiến hóa
GA Genetic Algorithm Giải thuật di truyền
EP Evolutionary Programming Lập trình tiến hóa
GP Genetic Programming Lập trình Gen
GGGP
Grammar-guided genetic
programming
Lập trình Gen định hướng bởi
văn phạm
CFG Context Free Grammars Văn phạm phi ngữ cảnh
TAG Tree-Adjoining Grammars Văn phạm nối cây
TAG3P

Bảng 3.2 Cấu hình thí nghiệm 63
Bảng 3.3. Số lần chạy thí nghiệm thành công 64
Bảng 3.4. Trung bình độ tốt của 100 lần chạy thí nghiệm 65
Bảng 3.5. Trung bình thay đổi độ tốt sau khi thực hiện lai ghép 66
Bảng 3.6. Cấu hình thí nghiệm 67
Bảng 3.7. Số lần chạy thí nghiệm thành công 68
Bảng 3.8. Trung bình độ tốt của 100 lần chạy thí nghiệm 70
Bảng 3.9. Trung bình thay đổi độ tốt sau khi thực hiện lai ghép 70
Bảng 3.10. Cấu hình thí nghiệm 75
Bảng 3.11. Số lần chạy thí nghiệm thành công 76
Bảng 3.12. Trung bình độ tốt của 100 lần chạy thí nghiệm 77
Bảng 4.1. Bảng thông số được cài đặt cho mỗi thí nghiệm 88
Bảng 4.2. Kết quả thí nghiệm học xấp xỉ hàm Q 90
Bảng 4.3. Cấu hình thí nghiệm 95
Bảng 4.4. Kết quả thí nghiệm học xấp xỉ hàm ngược Q 97
x

DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ

Hình vẽ 1.1. Sơ đồ khối của thuật giải EA 7
Hình vẽ 1.2. Biểu diễn cá thể trong GA 7
Hình vẽ 1.3 Các toán tử cơ bản trong GA chuẩn 8
Hình vẽ 1.4. Biểu diễn chương trình GP 11
Hình vẽ 1.5. Thao tác lai ghép trong GP 13
Hình vẽ 1.6. Thao tác đột biến trong GP 14
Hình vẽ 1.7. Kiểu Gen và kiểu hình trong GEP 15
Hình vẽ 1.8. Ví dụ về việc thay đổi hoàn toàn của kiểu hình 16

Hình vẽ 4.2. Lỗi tương đối của các xấp xỉ tìm được khi sử dụng hàm
thích nghi MAE và xấp xỉ OPBCS
85
Hình vẽ 4.3. Lỗi tương đối của các xấp xỉ tìm được khi sử dụng hàm
thích nghi RAE và xấp xỉ OPBCS
86
Hình vẽ 4.4. Văn phạm LTAG của TAP3P cho bài toán học xấp xỉ
hàm Q với dạng hàm mũ
89
Hình vẽ 4.5. So sánh lỗi tương đối của xấp xỉ hàm Q 92
Hình vẽ 4.6. Đồ thị hàm ngược Q 93
Hình vẽ 4.7. Văn phạm LTAG của TAP3P cho bài toán xấp xỉ hàm
ngược Q
96 1

GIỚI THIỆU CHUNG
Trong mục này, luận án sẽ giới thiệu khái quát về mục đích của việc
nghiên cứu, mục tiêu, phương pháp nghiên cứu, các đóng góp chính của luận án
và cuối cùng là bố cục các phần của luận án.
MỤC ĐÍCH
Lập trình Gen (Genetic Programming – GP) được đề xuất bởi Koza [1], từ
khi ra đời đã được xem như một phương pháp học máy có tiềm năng. Chính vì
vậy GP đã được áp dụng rộng rãi để giải quyết thành công nhiều bài toán, trong
đó phần nhiều là các bài toán liên quan đến học máy. GP có thể dùng để giải
quyết những bài toán học khi độ phức tạp cấu trúc của lời giải là không biết
trước, GP đòi hỏi ít tri thức nền của bài toán, và cho lời giải dưới dạng tường
minh (cách tiếp cận hộp trắng) cho người dùng.

nhưng ngược lại thì không chắc là như vậy. Một ví dụ đơn giản như sau đây, nếu
xét về cú pháp thì hai chương trình khác nhau về cú pháp. Nhưng xét về ngữ
nghĩa thì hai chương trình là có cùng ngữ nghĩa.
Trong thời gian gần đây, vấn đề nghiên cứu ngữ nghĩa và áp dụng ngữ
nghĩa trong các hệ lập trình Gen là hướng nghiên cứu rất được quan tâm để
cải tiến, định hướng cho quá trình tiến hóa của các cá thể.
Mặc dù vậy, khái niệm ngữ nghĩa chưa được nghiên cứu và đề xuất trong
hệ lập trình Gen định hướng bởi văn phạm nối cây. Do đó, đây là hướng nghiên
cứu cần tiếp tục được thực hiện đối với TAG3P như: nghiên cứu về ngữ nghĩa
cây con, thiết kế toán tử di truyền dựa trên ngữ nghĩa.
Trong lĩnh vực viễn thông, các nhà nghiên cứu giả thuyết rằng hệ thống
nhiễu có dạng biến Gaussian ngẫu nhiên. Tuy nhiên, hàm Q chỉ duy nhất được
định nghĩa dưới dạng tích phân suy rộng, điều này sẽ gây nhiều khó khăn cho
những phân tích sau này đối với với các hệ thống viễn thông. Do đó, rất cần thiết
phải tìm ra các biểu diễn tường minh (dạng giải tích) của hàm Q. Đến thời điểm
3

này, chưa có giải pháp chính xác tuyệt đối cho dạng tường minh của hàm Q, và
do đó, các hàm xấp xỉ là lựa chọn duy nhất.
Mặc dù có nhiều hàm xấp xỉ dạng tường minh của hàm Q đã được đề xuất
bởi các chuyên gia, nhưng do tính chất quan trọng và phổ biến của hàm Q trong
lĩnh vực viễn thông, việc tìm kiếm các hàm xấp xỉ tốt hơn, có dạng giải tích và
có nhiều đặc điểm quan trọng (chẳng hạn như sự đơn giản, tính khả tích,…) vẫn
tiếp tục được thực hiện. Thực tế cho thấy, các nhà khoa học vẫn không ngừng
tìm kiếm các dạng xấp xỉ mới, đơn giản hơn, tốt hơn của hàm Q, cụ thể là
trong những năm gần đây, các công trình khoa học tiếp tục đăng tải các dạng
xấp xỉ mới tìm thấy.
Với đặc điểm của hệ lập trình Gen nói chung và hệ TAG3P sẽ phù hợp với
bài toán tìm xấp xỉ, do đó, trong luận án sẽ ứng dụng các kết quả nghiên cứu
mới để tìm kiếm các dạng xấp xỉ mới, đơn giản hơn, tốt hơn của hàm Q. Đây là

ngữ nghĩa thu được kết quả cải tiến so với toán tử thông thường trên TAG3P.
3. Ứng dụng các kết quả nghiên cứu mới của luận án vào bài toán thực tế là
học xấp xỉ hàm Q và học xấp xỉ hàm ngược Q, trong đó:
- Nghiên cứu đề xuất hàm thích nghi phù hợp với đặc điểm của bài toán
học xấp xỉ hàm Q, hàm ngược Q.
- Tìm ra được xấp xỉ hàm Q ở dạng tường minh với cấu trúc rất đơn giản
và đặc biệt là có độ chính xác rất cao. Điều này rất có ý nghĩa bởi bài
toán tìm các dạng xấp xỉ của hàm Q có một vai trò quan trọng trong lĩnh
vực viễn thông, nó cũng được các nhà khoa học không ngừng nghiên
cứu nhằm tìm ra các xấp xỉ mới tốt hơn, đơn giản hơn. Kết quả này rất
quan trọng vì kể từ khi xấp xỉ OPBCS được đưa ra năm 1979 đến nay
chưa có một xấp xỉ nào tốt hơn được tìm ra. Hơn thế nữa, xấp xỉ tìm
được này lại có dạng hàm mũ nên rất đơn giản trong quá trình tính toán,
phù hợp với đặc điểm sử dụng trong phân tích hệ thống viễn thông.
- Tìm ra được xấp xỉ hàm ngược Q ở dạng tường minh, hiện chưa có
những công bố về dạng tường minh của hàm ngược này.
5

Các kết quả của luận án đã được công bố bao gồm: 02 bài đăng tại các tạp
chí có uy tín (trong đó có 01 tạp chí nước ngoài thuộc danh mục ISI), 03 bài báo
được đăng tại kỷ yếu hội thảo quốc tế (trong đó có 02 hội nghị quốc tế thuộc
danh mục ISI Proceeding). Ngoài ra, một số công trình nghiên cứu thuộc lĩnh
vực viễn thông đã trích dẫn và sử dụng các kết quả nghiên cứu này.
TỔNG QUAN VỀ CẤU TRÚC CỦA LUẬN ÁN
Luận án sẽ được trình bày như sau:
Giới thiệu chung: phần này sẽ trình bày mục đích của việc nghiên cứu,
các mục tiêu của luận án đặt ra, phương pháp nghiên cứu, các kết quả đóng góp
chính của luận án và cấu trúc các chương trong luận án.
Chương 1: các nội dung lý thuyết và các nghiên cứu trước đây có liên
quan sẽ được trình bày, bao gồm: những lý thuyết và các nghiên cứu có liên

Sự mô phỏng này được thực hiện theo ba mặt: một là EA sử dụng quần
thể gồm tập hợp các cá thể; hai là các cá thể đó cạnh tranh với nhau, dựa trên
thuyết chọn lọc tự nhiên của Darwin để tái tạo; ba là quá trình tiến hóa được
thực hiện ngẫu nhiên.
EA dựa trên quan niệm "Quá trình tiến hoá 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". Quá trình tiến hoá thể hiện tính
tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước.
Năm 1975, giải thuật Gen do John Holland phát minh và được phát triển
bởi ông cùng với các đồng nghiệp. Đến năm 1992, Koza đã dùng GA để xây
dựng các chương trình giải quyết một số bài toán mà kích thước lời giải không
được xác định trước và gọi phương pháp này là "Lập trình Gen".
Mặc dù vậy, thuật toán của các EA đều rất giống nhau và được thể hiện
như hình vẽ sau:
7 Hình vẽ 1.1. Sơ đồ khối của thuật giải EA

1.2 GIẢI THUẬT DI TRUYỀN
Giải
thuật di truyền (GA) nguyên thủy đã được đề xuất bởi Holland
và là giải thuật tiến hóa khá phổ biến và được sử dụng rộng rãi. Đồng
thời, nó được nghiên cứu và áp dụng cho nhiều bài toán thực tế.
Hệ GA nguyên thủy có sử dụng chuỗi nhị phân tuyến tính và có độ
dài cố định để biểu diễn chuỗi Gen. Hình vẽ sau đây là ví dụ một chuỗi
Gen của hệ giải thuật di truyền:

Hình vẽ 1.2. Biểu diễn cá thể trong GA

8

chính là các chương trình máy tính có khả năng tự tiến hóa để thực hiện một
công việc nào đó, được đưa ra bởi Koza vào năm 1992 [1]. Kỹ thuật này cung
cấp một nền tảng cho việc tạo ra những chương trình máy tính một cách tự động.
Lập trình Gen đạt được mục đích này bằng việc phát sinh ra một quần thể các
chương trình máy tính, sử dụng thuyết tiến hóa của Darwin chọn ra chương trình
tốt nhất để thực hiện công việc.
GP khác những thuật toán tiến hóa khác ở phạm vi ứng dụng. Những
thuật toán tiến hóa khác thường được áp dụng cho các bài toán tìm lời giải tối
ưu, trong khi GP được xếp vào nhóm các thuật toán học máy để tìm mô hình
phù hợp nhất dựa trên dữ liệu đưa vào.
Sự khác biệt giữa GA và GP cơ bản nằm ở mục đích của nó, trong khi GA
chủ yếu sử dụng cho bài toán tối ưu thì GP lại được sử dụng cho việc học. GA
được sử dụng để thực hiện việc tối ưu hóa một hàm dựa trên định nghĩa của hàm
10

đó, trong khi GP được sử dụng để học một hàm dựa trên tập dữ liệu học. Đây là
điểm khác biệt nhất giữa GA và GP. Ngoài ra, còn một điểm phân biệt khác giữa
GA và GP là GP thường sử dụng biểu diễn chuỗi Gen linh hoạt với kích cỡ và
cấu trúc thay đổi. Điều này càng cho thấy rõ là GA phù hợp với tối ưu hóa tham
số khi mà cấu trúc đã được biết trước, trong khi GP phù hợp với bài toán học và
tìm kiếm về cả nội dung cùng cấu trúc của lời giải và GP đã thành công trong
việc giải quyết nhiều bài toán thực tế [7].
1.3.1 Lập trình Gen chuẩn có cấu trúc cây
Mặc dù đã có số lượng các nghiên cứu gần với GP, nhưng trong lĩnh vực
GP lần đầu tiên được đưa ra bởi Koza trong [1], là tài liệu đầu tiên trên thế giới
nói về khả năng của GP và đặt nền móng cho lĩnh vực nghiên cứu này. Trong tài
liệu này, Koza đã đưa ra hệ thống GP dựa trên cơ chế chọn lọc tự nhiên của
Darwin, trong tài liệu này sẽ được gọi là hệ GP chuẩn.
Quá trình tiến hóa của GP bắt đầu với việc tạo ra ngẫu nhiên quần thể gồm
các cá thể (chương trình). Ở mỗi thế hệ, độ tốt của mỗi cá thể chương trình được


Hình vẽ 1.4. Biểu diễn chương trình GP
b. Khởi tạo quần thể
Để tạo một cấu trúc cây, GP lựa chọn ngẫu nhiên một phép tính hay một ký
hiệu kết từ tập các phép tính và tập các ký hiệu kết thúc của bài toán. Tuy nhiên,
việc lựa chọn cũng phải dựa vào tập các tham số điều khiển và phương pháp để
phát sinh một cá thể. Có các phương pháp khởi tạo quần thể sau:
Full: Phương pháp này tạo nên những cây đầy đủ, là những cây có tất cả các
ký hiệu kết ở mức lớn nhất của cây.
12

Grow: Lựa chọn ngẫu nhiên các phép tính và các ký hiệu kết cho nút gốc.
Nếu nút gốc là một ký hiệu kết, một ký hiệu kết ngẫu nhiên sẽ được chọn. Nếu
nút gốc là một phép tính, một phép tính ngẫu nhiên sẽ được chọn, và nút này sẽ
có số lượng nhánh con bằng với số lượng đối số của phép tính. Với mỗi nhánh
con này, thật toán grow sẽ lại bắt đầu cho đến khi nhánh con ở mức lớn nhất của
cây. Trong trường hợp này, nhánh con sẽ được tạo thành bằng cách chọn một ký
hiệu kết ngẫu nhiên.
Half–and–Half: Phương pháp này là sự kết hợp của 2 phương pháp trên.
c. Hàm thích nghi:
Để lựa chọn các cá thể cho thao tác lai ghép, tái tạo và đột biến, cũng như
đánh giá độ thích nghi (độ tốt) của từng cá thể trong việc giải quyết bài toán,
hàm tính giá trị thích nghi (gọi tắt là hàm thích nghi) là phương pháp để đánh
giá độ thích nghi của từng cá thể trong quần thể.
Độ thích nghi này được xác định trên cơ sở đánh giá chương trình so với kết
quả tập dữ liệu học. Độ tốt của mỗi cá thể thường được chuẩn hóa trước khi
được lựa chọn cho các phép toán di truyền. Quá trình chuẩn hóa trong GP chuẩn
được trình bày trong [1].
d. Toán tử di truyền:
Theo thuyết tiến hóa của Darwin, một quần thể sẽ trải qua nhiều thế hệ, và

thể dựa vào giá trị thích nghi. Trong mỗi cấu trúc cây cha mẹ, một nút ngẫu
nhiên sẽ được chọn, và những nhánh con bên dưới nút được chọn sẽ được hoán
vị để tạo thành 2 cây mới. Như hình vẽ sau vị trí lại ghép là cây con được chỉ
bởi mũi tên có nét gạch đứt.

Hình vẽ 1.5a. Hai cây ban đầu Hình vẽ 1.5b. Hai cây mới tạo ra sau khi thực hiện thao tác lai ghép
Đột biến: Tạo ra một cá thể mới từ một cá thể có sẵn trong quần thể bằng
việc thay thế một nút của cây bằng một nút khác trong tập tương ứng.
14 Hình vẽ 1.6.a. Cây ban đầu Hình vẽ 1.6.b. Cây sau đột biến
e. Các tham số
Các tham số trong GP chuẩn bao gồm: kích cỡ quần thể, số thế hệ tối đa, độ
sâu tối đa của việc khởi tạo, của quá trình tiến hóa và xác xuất thực hiện các
toán tử di truyền.
Như đã trình bày ở trên, GP được sử dụng để học cách xác định một hàm
dựa trên dữ liệu mẫu. Hệ thống GP thường thể hiện dưới dạng chuỗi Gen phức
tạp với kích thước và hình dạng biến đổi. GP thành công trong giải quyết nhiều
bài toán trong thực tế bao gồm các bài toán xấp xỉ tích phân ký hiệu.
Ngoài ra, trong [1], Koza có đưa ra hai điều kiện mà GP phải đáp ứng để
phù hợp với một số vấn đề đặc biệt như tính đầy đủ và tính đóng. Tính đầy đủ
đòi hỏi GP phải có tập nguyên thủy đủ (tập hàm và tập kết) để biểu diễn giải
pháp. Tính đóng là yêu cầu tất cả các hàm, ký hiệu kết phải cùng kiểu để đảm
bảo kết quả toán tử luôn là biểu diễn hợp lệ. Do đó, miền các vấn đề giải quyết
bởi GP chuẩn hạn chế trong những vấn đề không liên quan đến kiểu. Hạn chế
này là cơ sở thúc đẩy cho lập trình Gen định hướng bởi văn phạm.