Nghiên cứu lập trình di truyền ổn định trạng thái cho lớp các bài toán hồi quy ký hiệu

NGHIÊN CỨU LẬP TRÌNH DI TRUYỀN ỔN ĐỊNH TRẠNG THÁI

CHO LỚP CÁC BÀI TOÁN HỒI QUY KÝ HIỆU

Pham Thi Thuong1

; Nguyễn Lan Oanh1

1University of Information and Communication Technology, Thai Nguyen University

TÓM TẮT —

Trong bài báo này chúng tôi đề xuất phương pháp mới để tránh hiện tượng hội tụ sớm, một vấn đề

phổ biến trong Lập trình di truyền, bằng cách tăng tính đa dạng của quần thể trong quá trình tiến

hóa. Phương pháp này xem tuổi và độ thích nghi của lời giải là các tiêu chí cần tối ưu. Quá trình tiến

hóa quần thể dựa trên mặt Pareto hai chiều gồm các cá thể có tuổi nhỏ nhất và độ thích nghi cao

nhất. Để đánh giá phương pháp, chúng tôi tiến hành thử nghiệm trên một số lớp các bài toán hồi quy

ký hiệu với độ phức tạp tăng dần về mặt cấu trúc. Kết quả thử nghiệm cho thấy lời giải tìm được của

phương pháp này tốt hơn so với Lập trình di truyền chuẩn (SGP) được đề xuất bởi Koza [6], phương

pháp lập trình di truyền phân tầng tuổi ALPS được đề xuất bởi Hornby [4].

Từ khóa — Bài toán hồi quy ký hiệu, Lập trình di truyền, Tối ưu đa mục tiêu Pareto.

I. GIỚI THIỆU

Một vấn đề thường gặp trong khi thực hiện các

giải thuật tiến hóa là hiện tượng chỉ đạt đến điểm

tối ưu cục bộ trong không gian các lời giải sau khi

tiến hóa đến một ngưỡng nào đó (Murphy and

Ryan, 2007). Hiện tượng này được gọi là hội tụ

sớm (Ryan, 1996; Louis and Rawlins, 1993). Mặc

dù người ta đã cố gắng khắc phục bằng cách tăng

số thế hệ, tăng thời gian huấn luyện, … nhưng

chưa đạt được hiệu quả như ý muốn. Trong bài

báo này chúng tôi đề xuất một phương pháp mới

để khắc phục hiện tượng này.

Trong các nghiên cứu hiện thời thường sử

dụng cách tiếp cận thực hiện nhiều lần tìm kiếm

tiến hóa, hay nói cách khác là thực hiện nhiều lần

chạy thử nghiệm, mỗi lần chạy tương ứng với

việc khởi động lại quá trình tiến hóa để tìm kiếm

lời giải tối ưu (Auger and Hánen, 2005; Jansen,

2002). Cách tiếp cận này thường gây lãng phí tài

nguyên và không hứa hẹn nhiều khả năng tìm

được lời giải tốt.

Một trong các phương pháp để tránh hiện

tượng hội tụ sớm này là phương pháp cấu trúc

quần thể phân tầng tuổi ALPS được đề xuất bởi

Hornby (Hornby, 2006; Hornby, 2009a; Hornby,

2009b). Phương pháp này xem tuổi của cá thể là

thời gian tồn tại của gen trong cấu trúc của lời

giải khi tiến hóa qua các thế hệ. Nó phân chia

quần thể thành các tầng, mỗi tầng chứa các cá thể

với độ tuổi nhất định. Các cá thể trong từng tầng

được tiến hóa một cách độc lập. Sau mỗi thế hệ

tiến hóa một cá thể ngẫu nhiên được thêm vào

tầng trẻ nhất để tăng tính đa dạng của quần thể.

Phương pháp này đạt được những kết quả cải tiến

đáng kể so với SGP, tuy nhiên nó yêu cầu phải

thêm các tham số điều khiển mới như số lượng cá

thể trên mỗi tầng, số lượng tầng.

Một câu hỏi đặt ra là: Liệu có cách nào mà

không cần sử dụng thêm các tham số điều khiển

đồng thời vẫn giữ nguyên được chất lượng của lời

giải. Để trả lời câu hỏi này, chúng tôi đề xuất

phương pháp mới với ý tưởng lựa chọn những cá

thể có tuổi ít và độ thích nghi cao (hay giá trị hàm

lỗi thấp) cho tham gia vào quá trình tiến hóa. Lựa

chọn lời giải có tuổi nhỏ, độ thích nghi cao sẽ làm

tăng tính đa dạng của quần thể, bảo quản các lời

giải cha mẹ có độ thích nghi cao trong quần thể.

Để triển khai ý tưởng này, chúng tôi sử dụng cách

tiếp cận tối ưu đa mục tiêu Pareto. Ở đây chúng

tôi tập trung vào hai mục tiêu cần tối ưu là tuổi và

độ thích nghi của lời giải. Tuổi của lời giải là thời

gian tồn tại của gen được tính tương tự như cách

tiếp cận của Horby [4]. Quá trình tiến hóa quần

thể dựa trên mặt Pareto hai chiều gồm các cá thể

có tuổi nhỏ nhất và độ thích nghi cao nhất.

Phần tiếp theo của bài báo được tổ chức

như sau: Trong phần II, chúng tôi trình bày ngắn

gọn các kiến thức cơ bản bao gồm GP và phương

pháp tối ưu đa mục tiêu. Phần III là phương pháp

mới mà chúng tôi đề xuất. Các thiết lập thực

nghiệm được trình bày trong phần IV. Cuối cùng

là các kết quả đạt được và phần thảo luận chỉ ra

những công việc sẽ được nghiên cứu trong tương

lai.

II. KIẾN THỨC CƠ SỞ

A.Lập trình di truyền và Lập trình di truyền

ổn định trạng thái

Lập trình di truyền (GP: Genetic Programming)

được phát triển một cách có hệ thống bởi Koza [6]

năm 1992. Dựa trên những quan sát về các hệ thống

sinh học. GP sử dụng thuyết tiến hóa của Darwin để

91

Phạm Thị Thương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 91 - 96

Nitro PDF Software

100 Portable Document Lane

Wonderland

Nitro PDF Software

100 Portable Document Lane

Wonderland