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
Số trang: 6
Loại file: pdf
Dung lượng: 3.72 MB
Lượt xem: 7
Lượt tải: 0
Xem trước 2 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
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.
Nội dung trích xuất từ tài liệ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 Phạm Thị Thương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 91 - 96 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 1 University 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 để Nitro PDF Software 91 100 Portable Document Lane Wonderland Phạm Thị Thương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 91 - 96 tiến hóa quần thể các lời giải cho bài toán [5, 6]. GP có thể xem là một phương pháp máy học nhằm tối ưu quần thể các chương trình máy tính để thực hiện một nhiệm vụ tính toán cho trước. Giải thuật lập trình di truyền gồm các bước như sau: Bước 0: Khởi tạo quần thể ban đầu, P(0). Lặp: Bước1: Đánh giá độ thích nghi (độ tốt) của mỗi lời giải trong quần thể P(t). Bước 2: Lựa chọn 2 lời giải cha trong quần thể P(t) dựa t ...
Nội dung trích xuất từ tài liệ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 Phạm Thị Thương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 91 - 96 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 1 University 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 để Nitro PDF Software 91 100 Portable Document Lane Wonderland Phạm Thị Thương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 91 - 96 tiến hóa quần thể các lời giải cho bài toán [5, 6]. GP có thể xem là một phương pháp máy học nhằm tối ưu quần thể các chương trình máy tính để thực hiện một nhiệm vụ tính toán cho trước. Giải thuật lập trình di truyền gồm các bước như sau: Bước 0: Khởi tạo quần thể ban đầu, P(0). Lặp: Bước1: Đánh giá độ thích nghi (độ tốt) của mỗi lời giải trong quần thể P(t). Bước 2: Lựa chọn 2 lời giải cha trong quần thể P(t) dựa t ...
Tìm kiếm theo từ khóa liên quan:
Lập trình di truyền ổn định trạng thái Lập trình di truyền Bài toán hồi quy ký hiệu Tối ưu đa mục tiêu Pareto Hồi quy ký hiệuGợi ý tài liệu liên quan:
-
7 trang 117 1 0
-
Mô hình dự báo chấn động nổ mìn trên mỏ lộ thiên dựa trên phương pháp lập trình di truyền
10 trang 28 0 0 -
Dự báo lượng mưa tại một số trạm quan trắc Việt Nam dựa trên lập trình di truyền
10 trang 20 0 0 -
Trùng lặp cá thể trong lập trình di truyền
8 trang 17 0 0 -
Áp dụng học máy dựa trên lập trình di truyền trong tìm kiếm web xuyên ngữ
5 trang 14 0 0 -
Nghiên cứu về học chuyển đổi trong GP (genetic programming)
7 trang 12 0 0 -
8 trang 11 0 0
-
Phương pháp dự báo nước biển dâng do bão dựa trên lập trình di truyền
11 trang 10 0 0