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 Thuong

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 Thuong 1 ; 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 để 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 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 trên độ thích nghi của chúng. Bước 3: Thực hiện các thao tác di truyền để thu được quần thể P(t+1) Lặp đến tận khi các điều kiện dừng thỏa mãn. Với lập trình di truyền ổn định trạng thái các lời giải con mới tạo ra được đưa vào quần thể hiện thời và chúng có thể cạnh tranh với cha mẹ trong quá trình tiến hóa. B.Tối ưu đa mục tiêu Tối ưu đa mục tiêu (Multi Object Optimization- MOO) nhằm tối ưu các mục tiêu xung đột là vấn đề thường gặp trong thực tế. Bài toán MOO được mô tả như một hàm vecto f nhằm ánh xạ một dãy gồm N tham biến (các biến quyết định) đến một dãy gồm M mục tiêu. Bài toán này được phát biểu một cách hình thức như sau: Tìm cực trị của hàm mục tiêu: ))(),...,(),(()( 21 xfxfxfxfy M , Xxxxx N  ),...,,( 21 Trong đó: - x là véc tơ quyết định, - y là véc tơ mục tiêu. Giả sử xét bài toán cực tiểu, với 2 véc tơ quyết định a, b trong X, chúng ta nói a ―trội‖ hơn (dominates) b: ba  khi và chỉ khi:    )(:,...,2,1)()(:,...,2,1 afMjbfafMi jii  < )(bf j Véc tơ quyết định mà không bị vượt trội bởi các véc tơ quyết định khác thì được gọi là véc tơ tối ưu Pareto. Một họ gồm tất cả các lời giải trội (y) hoặc không bị vượt trội bởi véc tơ khác được gọi là tập tối ưu Pareto (Pareto set) hoặc mặt tối ưu Pareto (Pareto-optimal front). Hình 1- Ví dụ cho mặt tối ưu Pareto. Hình 1- Mặt tối ưu Pareto 2 mục tiêu. Một số giải thuật tiến hóa đa mục tiêu thông thường để tìm mặt tối ưu Pareto thông dụng gồm [3]: - Niched Pareto GA (NPGA) - Non-dominated sorting GA (NSGA) - Elitist Non-dominated Sorting GA (NSGA II) - Strength – Pareto EA (SPEA) - Pareto – archived evolution strategy (PAES) Trong bài báo này chúng tôi sử dụng phương pháp NSGAII để triển khai ý tưởng đề xuất (chúng tôi gọi phương pháp mới này là AFMPGP – Age Fitness Multi Pareto Genetic Programming). III. PHƯƠNG PHÁP ĐỀ XUẤT Phần này mô tả chi tiết phương pháp do chúng tôi đề xuất. Phương pháp này cũng gồm các bước như trình bày trong mục II.A. 1.Tuổi của gen (Age) Khái niệm về tuổi của lời giải là thời gian tồn tại của gen trong cấu trúc của lời giải qua các thể hệ đã được sử dụng trong phương pháp ALPS. ALPS được xem là một trong các phương pháp tốt để tránh hiện tượng hội tụ sớm (Hornby, 2006). Phương pháp AFMPGP sử dụng phép đo tuổi tương tự như phương pháp của Hornby, và xem tuổi là một tiêu chí cần tối ưu. Trong quần thể ban đầu, tất cả các cá thể được khởi tạo với tuổi là một. Khi lai ghép và đột biến, giá trị tuổi của các lời giải con là tuổi của lời giải cha hoặc mẹ lớn nhất cộng với một, hay nói cách khác tuổi được đo bởi thời gian tồn tại của phần gen trong lời giải cha hoặc mẹ mà tồn tại lâu nhất trong quần thể cộng với một. 2. Quần thể Age-Fitness Pareto Quần thể được biểu diễn bởi mặt Pareto hai chiều gồm các lời giải có tuổi nhỏ nhất và độ thích nghi cao nhất. Nhiệm vụ học là xác định mặt Pareto tối ưu. Trong quá trình tiến hóa, mặt Pareto sẽ chứa các lời giải trội, mỗi lời giải trên mặt chỉ bị 92 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 thay thế hay bị loại bỏ bởi lời giải có độ thích nghi thấp hơn và tuổi trẻ hơn. Hơn nữa để góp phần khắc phục hiện tượng hội tụ sớm, trong quá trình tiến hóa chúng tôi bổ sung thêm vào quần thể hiện thời một lời giải được sinh ngẫu nhiên mới. 3. Biểu diễn lời giải Lời giải được biểu diễn bởi cấu trúc cây. Các nút trong của cây là các hàm và các lá là các ký hiệu kết thúc. Hình 2 là ví dụ minh họa cho cấu trúc cây lời giải. GP áp dụng cho bài toán hồi quy ký hiệu nhằm tìm mô hình khớp với tập dữ liệu cho trước. Hình 2. Cấu trúc cây lời giải GP 4. Khởi tạo quần thể Quần thể ban đầu chứa các cây lời giải với chiều cao nằm trong giới hạn [a, b] cho trước, với a, b là các số nguyên xác định giới hạn dưới, giới hạn trên. Các cây này được sinh ngẫu nhiên với 50% gồm các cây đầy đủ và 50% các cây thông thường. 5. Đánh giá độ thích nghi của lời giải Trong bài báo này chúng tôi sử dụng công thức đo giá trị lỗi là tổng giá trị tuyệt đối của sự chênh lệch giữa đầu ra thực sự của lời giải học được và giá trị mong đợi:    n i iip ope 1 || Trong đó: ep là giá trị lỗi của lời giải p trong quần thể. oi là đầu ra mong đợi của quan sát thứ i trong tập dữ liệu huấn luyện. pi là đầu ra thực tế của lời giải p của quan sát i trong tập huấn luyện. Độ thích nghi fp của lời giải được tính theo công thức: p p e f   1 1 6.Chọn lọc cạnh tranh Pareto Chúng tôi sử dụng phương pháp chọn lọc cạnh tranh để lựa chọn các lời giải cha mẹ. Các lời giải cha mẹ được lựa chọn phải thỏa mãn đồng thời hai tiêu chuẩn tối ưu đó là tuổi ít và có độ thích nghi cao: Tại mỗi thế hệ, k lời giải được lựa chọn ngẫu nhiên, trong k lời giải này, chọn 2 trong k lời giải theo cách chọn lọc cạnh tranh để đưa vào quần thể kế tiếp. 7. Các toán tử di truyền a. Phép lai ghép Cặp lời giải cha mẹ được lựa chon sẽ được lai ghép với nhau sử dụng phương pháp trao đổi chéo để sinh ra hai lời giải con: -Chọn ngẫu nhiên một nút trên cây cha 1 -Chọn ngẫu nhiên một nút trên cây cha 2 -Tráo đổi hai nút này cùng với các cây con của chúng. Hình 4 là ví dụ cho phép lai ghép. Bốn lời giải gồm hai cha và hai con được đưa vào quần thể hiện thời. Hình 4: Ví dụ phép lai ghép a) Cây lời giải cha 1 b) cây lởi giải cha 2, c) cây lời giải con 1, d) cây lời giải con 2. b. Phép đột biến Phép đột biến được tiến hành trên một cá thể cha bằng cách chọn ngẫu nhiên một cây con trên cây cha và thay cây con đó bởi cây con được sinh ngẫu nhiên mới. Lời giải cha và lời giải con sinh ra lại được đưa vào quần thể ban đầu. Hình 5 là ví dụ cho phép đột biến. + * ln 1 2 x * / - x 2 x * 7 4 + * ln 1 2 x * / x 2 * 1 2 a) + ln x - x * 7 4 c) b) d) 93 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 (a) (b) Hình 5: Ví dụ phép đột biến, (a) cây con trái được lựa chọn để đột biến, (b) thay thế cây con đột biến bởi cây con sinh ngẫu nhiên mới Chúng tôi xác định kích cỡ của quần thể ban đầu – tương tự như kích cỡ của quần thể của giải thuật tiến hóa truyền thống. Sau mỗi thế hệ tiến hóa, kích cỡ của quần thể là lớn hơn gấp đôi so với kích thước ban đầu. Chúng tôi thực hiện quá trình loại bỏ các cá thể bị vượt trội trong quần thể đến khi thu được kích thước quần thể ban đầu hoặc cho đến khi không tìm được các cá thể không trội được để loại bỏ chúng để thu được mặt tối ưu hai mục tiêu Pareto. Các cá thể trong mặt tối ưu này lại tiếp tục tham gia vào quá trình tiến hóa tại thế hệ tiếp theo và quy trình lại được lặp lại cho đến khi số thế hệ tối đa thỏa mãn hoặc tìm được lời giải đúng hoặc có độ thích nghi nhỏ hơn ngưỡng α cho phép. Chúng tôi đã tiến hành lập trình thử nghiệm phương pháp đề xuất trên 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ới nghiên cứu này, chúng tôi xem độ phức tạp của bài toán tăng khi cấu trúc của lời giải của bài toán tăng. Cấu trúc lời giải bài toán được biểu diễn như một cây lời giải với các nút trong là các hàm và các nút lá là các ký hiệu kết. Phương pháp đề xuất được so sánh với SGP – Lập trình di truyền gốc với các thao tác tiến hóa chuẩn, phương pháp ALPS được xem là phương pháp tốt để tránh hiện tượng hội tụ sớm. Kết quả thực nghiệm cho thấy phương pháp đề xuất tìm được giải pháp tốt hơn đáng kể so với SGP và phương pháp ALPS, thậm chí trong trường hợp độ phức tạp của bài toán tăng dần. IV. THIẾT LẬP THỰC NGHIỆM A. Lớp các bài toán Để đánh giá hiệu quả của phương pháp đề xuất, chúng tôi kiểm thử trên 2 bài toán hồi quy ký hiệu F1, F2. Trong đó bài toán F2 có cấu trúc hàm mục tiêu biến đổi từ đơn giản đến phức tạp. Bảng 1. Mô tả các bài toán này. Bảng 1: Một số bài toán hồi quy ký hiệu Lớp bài toán Các công thức với độ phức tạp giải pháp tăng dần F1 cos(x)+sin(x) + sin 2 (x) F2 1. x 2 +x (F1.1) 2. x3+x2+x (F1.2) 3. x4+x3+x2+x (F1.3) 4. x5+x4+x3+x2+x (F1.4) 5. x6+x5+x4+x3+x2+x (F1.5) B. Thiết lập tham số thực nghiệm Các tham số được sử dụng trong thực nghiệm được chỉ ra trong Bảng 2. Đây là các tham số với các giá trị thường được sử dụng trong các nghiên cứu và các thực nghiệm của GP [7]. Bảng 2: Bảng các tham số thực nghiệm Các tham số Các giá trị Kích cỡ quần thể 500 Số thể hệ, điều kiện dừng 100, α = 0.01 Phương pháp lựa chọn cạnh tranh Kích cỡ lựa chọn 2 Xác suất lai ghép 0.9 Xác suất đột biến 0.05 Chiều cao tối đa của các cây lời giải trong quần thể ban đầu 6 Chiều sâu tối đa của cây lời giải trong các quần thể 15 Các ký hiệu không kết thúc +, -, *, / (protected one), sin, cos, exp, log (protected one) Các ký hiệu kết thúc X Tập huần luyện 60 điểm ngẫu nhiên trong khoảng [-1,1] Công thức fitness Độ thích nghi của lời giải Số lần thử nghiệm 30 lần chạy V. KẾT QUẢ VÀ THẢO LUẬN Phần này mô tả các thông tin, kết quả thực nghiệm và một số trao đổi thảo luận. Trong các thực nghiệm này, độ thích nghi của cá thể tốt nhất trong tiến trình tiến hóa được tính trung bình qua 30 lần chạy và đồ thị kết quả tương ứng chỉ ra như Hình 6, Hình 7. Trong đó Hình 6 là trung bình fitness của cá thể tốt nhất của 30 lần chạy cho bài toán F1. Hình 7 là các kết quả trung bình của cá thể tốt nhất của 30 lần chạy cho bài toán F2. Các kết quả thực nghiệm cho thấy phương pháp đề xuất (AFMPGP, đường trên cùng) là hiệu + * - 1 2 3 4 + * - 1 2 x * 7 4 94 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 quả hơn so với SGP (đường thứ 3) và phương pháp ALPS (đường thứ 2), thậm chí khi học các bài toán với độ phức tạp tăng dần F2. Hình 6: Đồ thị trung bình fitness của lời giải tốt nhất với bài toán F1 Hình 7: Đồ thị trung bình fitness của lời giải tốt nhất với bài toán (F2) VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Trong bài báo này, chúng tôi đề xuất phương pháp mới (AFMPGP) dựa trên việc sử dụng phép đo tuổi của lời giải dựa trên thời gian tồn tại của các gen như phương pháp ALPS được đề xuất bởi Hornby. Chúng tôi xem tuổi và độ thích nghi của lời giải là hai tiêu chí tối ưu, lựa chọn các cá có tuổi ít và độ thích nghi cao tham gia vào quá trình tiến hóa. Điều này sẽ là tăng tính đa dạng trong quần thể và bảo quản được các lời giải tốt đã hoạc được trước đó. Mặt khác cách tiếp cận lập trình di truyền ổn định trạng thái được chúng tôi sử dụng trong bài báo này nhằm tăng tốc độ hội tụ nhằm đảm bảo khả năng sớm tìm được giải pháp tốt trong quá trình tiến hóa. Mặt khác, cách tiếp cận tối ưu đa mục tiêu Pareto NSGAII [3] được chúng tôi sử dụng để cài đặt AFMPGP. Tiếp theo AFMPGP được tiến hành thử nghiệm trên lớp bài toán có độ phức tạp cấu trúc lời giải tăng dần. Kết quả thử nghiệm chỉ ra AFMPGP có thể chất lượng lời giải tốt hơn so với SGP và ALPS, thậm chí khi độ phức tạp của bài toán cần học tăng dần về cấu trúc, điều này có nghĩa nó có tiềm năng trong việc tránh hiện tượng hội tụ sớm. Trong các nghiên cứu tiếp, chúng tôi sẽ tiến hành thử nghiệm phương pháp trên các bài toán có độ phức tạp tăng dần (số lượng biến tăng). Tiếp đó, đề xuất mô hình phức tạp hơn cho tối ưu đa mục tiêu. VII. TÀI LIỆU THAM KHẢO [1] Angeline, P. J. Pollack, ―Evolutionary Module Acquisition‖, Proceedings of the 2nd Annual Conference on Evolutionary Programming, pp. 154-163, MIT Press, 1993. [2] Andrew H. Wáton., Dr. Ian C. Parmee., Steady State Genetic Programming with Constrained Complexity Crossover, Processdings oF the Second Annual Conference July 13-16, 1997, Standford University. [3] Chun-Wei Seah, Yew-Soon Ong, Ivor W. Tsang, Siwei Jiang, ―Pareto Rank Learning in Multi- objective, WCCI 2012 IEEE World Congress on Computational Intelligence June, 10-15, 2012 - Brisbane, Australia [4] Gregory S. Hornby, ―A STEADY-STATE VERSION OF THE AGE-LAYERED POPULATION STRUCTURE EA‖, GENETIC PROGRAMMING THEORY AND PRACTICE VII, 2009. [5] Michael Schmidt and Hod Lipson, ―SYMBOLIC REGRESSION OF IMPLICIT EQUATIONS‖, Genetic Programming Theory and Practice VII, Genetic and Evolutionary Computation, DOI 10.1007/978-1-4419-1626-6_5, 2010. [6] John R. Koza, "Genetic Programming On the Programming of Computers by Means of Natural Selection", The MIT Press Cambridge, Massachusetts London, England, 1998 [7] Riccardo Poli, William B. Langdon, Nicholas F. McPhee, "A Field Guide to Genetic Programming", ISBN 978-1-4092-0073-4 (softcover), 2008 F1 F2 95 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 SUMMARY A STUDY OF STEADY – STATE GENETIC PROGRAMMING FOR A CLASS OF SYMBOLIC REGRESSION PROBLEMS Pham Thi Thuong 1 ; Nguyen Lan Oanh 1 In this paper we propose a new method to avoid premature convergence, a common problem in genetic programming, by increasing the diversity of the population in the process of evolution. This method considered age and adaptability of the solution is the criteria to opimize. Evolution populations based on two-dimensional Pareto includes individuals has the smallest age and highest adaptability. To evaluate the method, we conducted experiments on several classes of symbolic regression problems with increasing complexity in terms of structure. Test results show that the solution found by this method is better than the standard genetic programming (SGP) was proposed by Koza [6], genetic programming method stratified by age ALPS proposed Hornby [4]. Key words: Symbolic Regression Problem, Genetic Programming, MultiObjective Pareto Optimization. * Tel: 0912838646, email: ptthuong@ictu.edu.vn 91 91 96 Phạm Thị Thương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 91 - 96 Ngày nhận bài:30/10/2014; Ngày phản biện:25/11/2014; Ngày duyệt đăng: 31/5/2015 Phản biện khoa học: TS. Vũ Mạnh Xuân – Trường Đại học Sư phạm - ĐHTN Nitro PDF Software 100 Portable Document Lane Wonderland