Thạc Sĩ Dùng Genetic Programming giải bài toán SYMBOLIC REGRESSION

DÙNG GENETIC PROGRAMMING GIẢI BÀI TOÁN SYMBOLIC REGRESSION

TÓM TẮT

Trong đề tài này, tác giả tìm hiểu và áp dụng Genetics Programming (GP) giải bài toán Symbolic Regression (SR). Các thử nghiệm trên bảy hàm một biến thực đã chỉ ra rằng có thể giải bài toán này bằng GP. Tiếp theo đó, tác giả áp dụng chiến lược động vào phép lai chuẩn nhằm khắc phục nhược điểm tìm kiếm cục bộ của phép lai này. Kết qủa chạy 6 thử nghiệm khi xấp xỉ hai hàm một biến được chọn từ bảy hàm trên đã chỉ ra: phép lai chuẩn có áp dụng chiến lược động đạt được độ chính xác cao hơn và ổn định hơn trong khoảng thời gian ít hơn.

Mở đầu

Genetic Programming (GP) là một nhánh của Genetics Algorithm được nghiên cứu đầu tiên bởi John Koza từ năm 1972, sau đó bởi William Langdon, Ricardo Poli, . GP là một phương pháp tối ưu ký hiệu dựa trên biểu diễn cây – cây là cấu trúc linh hoạt có thể biểu diễn các chương trình máy tính, các biểu thức, phương trình toán học, GP có nhiều ứng dụng quan trọng như lập trình tự động, giải bài toán hồi quy ký hiệu (Symbolic Regression).
Phần 2 giới thiệu bài toán SR và mô hình áp dụng GP giải bài toán SR.
Phần 3 áp dụng chiến lược động vào phép lai chuẩn trong GP nhằm tăng độ chính xác của lời giải.
Phần 4 là giao diện chương trình thử nghiệm và kết qủa thử nghiệm. Phần 5 là các vấn đề cần nghiên cứu thêm.
2. Mô hình GP giải bài toán SR
2.1 Bài toán SR
Cho trước tập các điểm
D x y i N x R yi R
M
= i i = i {( , ) 1, ., }, , ,
tập các hàm cơ sở2
F = {+,ư,*, /, pow,ln, exp, abs,sin, cos,tan,sqrt .}
và tập các toán hạng T = { , , ., , , .} 1 2
1 2
x x cons cons . Bài toán đặt ra là tìm một hàm
f R R
M
*: , f* được tạo bởi các hàm trong F và các toán hạng trong T sao cho
0
*100%
* ( )
( *, )
1
ư
=
=
N
y
f x y
E f D
N
i i
i i
. (1)