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<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 135(05): 91 - 96<br /> <br /> NGHIÊN CỨU LẬP TRÌNH DI TRUYỀN ỔN ĐỊNH TRẠNG THÁI<br /> CHO LỚP CÁC BÀI TOÁN HỒI QUY KÝ HIỆU<br /> Pham Thi Thuong1; Nguyễn Lan Oanh1<br /> 1<br /> <br /> University of Information and Communication Technology, Thai Nguyen University<br /> <br /> TÓM TẮT —<br /> 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 đề<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> pháp lập trình di truyền phân tầng tuổi ALPS được đề xuất bởi Hornby [4].<br /> 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.<br /> I. GIỚI THIỆU<br /> <br /> Một vấn đề thường gặp trong khi thực hiện các<br /> giải thuật tiến hóa là hiện tượng chỉ đạt đến điểm<br /> tối ưu cục bộ trong không gian các lời giải sau khi<br /> tiến hóa đến một ngưỡng nào đó (Murphy and<br /> Ryan, 2007). Hiện tượng này được gọi là hội tụ<br /> sớm (Ryan, 1996; Louis and Rawlins, 1993). Mặc<br /> dù người ta đã cố gắng khắc phục bằng cách tăng<br /> số thế hệ, tăng thời gian huấn luyện, … nhưng<br /> chưa đạt được hiệu quả như ý muốn. Trong bài<br /> báo này chúng tôi đề xuất một phương pháp mới<br /> để khắc phục hiện tượng này.<br /> Trong các nghiên cứu hiện thời thường sử<br /> dụng cách tiếp cận thực hiện nhiều lần tìm kiếm<br /> tiến hóa, hay nói cách khác là thực hiện nhiều lần<br /> chạy thử nghiệm, mỗi lần chạy tương ứng với<br /> việc khởi động lại quá trình tiến hóa để tìm kiếm<br /> lời giải tối ưu (Auger and Hánen, 2005; Jansen,<br /> 2002). Cách tiếp cận này thường gây lãng phí tài<br /> nguyên và không hứa hẹn nhiều khả năng tìm<br /> được lời giải tốt.<br /> Một trong các phương pháp để tránh hiện<br /> tượng hội tụ sớm này là phương pháp cấu trúc<br /> quần thể phân tầng tuổi ALPS được đề xuất bởi<br /> Hornby (Hornby, 2006; Hornby, 2009a; Hornby,<br /> 2009b). Phương pháp này xem tuổi của cá thể là<br /> thời gian tồn tại của gen trong cấu trúc của lời<br /> giải khi tiến hóa qua các thế hệ. Nó phân chia<br /> quần thể thành các tầng, mỗi tầng chứa các cá thể<br /> với độ tuổi nhất định. Các cá thể trong từng tầng<br /> được tiến hóa một cách độc lập. Sau mỗi thế hệ<br /> tiến hóa một cá thể ngẫu nhiên được thêm vào<br /> tầng trẻ nhất để tăng tính đa dạng của quần thể.<br /> Phương pháp này đạt được những kết quả cải tiến<br /> đáng kể so với SGP, tuy nhiên nó yêu cầu phải<br /> <br /> thêm các tham số điều khiển mới như số lượng cá<br /> thể trên mỗi tầng, số lượng tầng.<br /> Một câu hỏi đặt ra là: Liệu có cách nào mà<br /> không cần sử dụng thêm các tham số điều khiển<br /> đồng thời vẫn giữ nguyên được chất lượng của lời<br /> giải. Để trả lời câu hỏi này, chúng tôi đề xuất<br /> phương pháp mới với ý tưởng lựa chọn những cá<br /> thể có tuổi ít và độ thích nghi cao (hay giá trị hàm<br /> lỗi thấp) cho tham gia vào quá trình tiến hóa. Lựa<br /> chọn lời giải có tuổi nhỏ, độ thích nghi cao sẽ làm<br /> tăng tính đa dạng của quần thể, bảo quản các lời<br /> giải cha mẹ có độ thích nghi cao trong quần thể.<br /> Để triển khai ý tưởng này, chúng tôi sử dụng cách<br /> tiếp cận tối ưu đa mục tiêu Pareto. Ở đây chúng<br /> tôi tập trung vào hai mục tiêu cần tối ưu là tuổi và<br /> độ thích nghi của lời giải. Tuổi của lời giải là thời<br /> gian tồn tại của gen được tính tương tự như cách<br /> tiếp cận của Horby [4]. Quá trình tiến hóa quần<br /> thể dựa trên mặt Pareto hai chiều gồm các cá thể<br /> có tuổi nhỏ nhất và độ thích nghi cao nhất.<br /> Phần tiếp theo của bài báo được tổ chức<br /> như sau: Trong phần II, chúng tôi trình bày ngắn<br /> gọn các kiến thức cơ bản bao gồm GP và phương<br /> pháp tối ưu đa mục tiêu. Phần III là phương pháp<br /> mới mà chúng tôi đề xuất. Các thiết lập thực<br /> nghiệm được trình bày trong phần IV. Cuối cùng<br /> là các kết quả đạt được và phần thảo luận chỉ ra<br /> những công việc sẽ được nghiên cứu trong tương<br /> lai.<br /> II. KIẾN THỨC CƠ SỞ<br /> <br /> A.Lập trình di truyền và Lập trình di truyền<br /> ổn định trạng thái<br /> <br /> Lập trình di truyền (GP: Genetic Programming)<br /> được phát triển một cách có hệ thống bởi Koza [6]<br /> năm 1992. Dựa trên những quan sát về các hệ thống<br /> sinh học. GP sử dụng thuyết tiến hóa của Darwin để<br /> Nitro PDF Software<br /> 91<br /> <br /> 100 Portable Document Lane<br /> Wonderland<br /> <br /> Phạm Thị Thương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 135(05): 91 - 96<br /> <br /> tiến hóa quần thể các lời giải cho bài toán [5, 6]. GP<br /> có thể xem là một phương pháp máy học nhằm tối<br /> ưu quần thể các chương trình máy tính để thực hiện<br /> một nhiệm vụ tính toán cho trước. Giải thuật lập<br /> trình di truyền gồm các bước như sau:<br /> Bước 0: Khởi tạo quần thể ban đầu, P(0).<br /> Lặp:<br /> Bước1: Đánh giá độ thích nghi (độ tốt) của<br /> mỗi lời giải trong quần thể P(t).<br /> Bước 2: Lựa chọn 2 lời giải cha trong quần<br /> thể P(t) dựa trên độ thích nghi của<br /> chúng.<br /> Bước 3: Thực hiện các thao tác di truyền để<br /> thu được quần thể P(t+1)<br /> Lặp đến tận khi các điều kiện dừng thỏa<br /> mãn.<br /> Với lập trình di truyền ổn định trạng thái<br /> các lời giải con mới tạo ra được đưa vào quần thể<br /> hiện thời và chúng có thể cạnh tranh với cha mẹ<br /> trong quá trình tiến hóa.<br /> B.Tối ưu đa mục tiêu<br /> Tối ưu đa mục tiêu (Multi Object OptimizationMOO) nhằm tối ưu các mục tiêu xung đột là vấn<br /> đề thường gặp trong thực tế. Bài toán MOO được<br /> mô tả như một hàm vecto f nhằm ánh xạ một dãy<br /> gồm N tham biến (các biến quyết định) đến một<br /> dãy gồm M mục tiêu. Bài toán này được phát biểu<br /> một cách hình thức như sau: Tìm cực trị của hàm<br /> mục tiêu:<br /> y  f ( x)  ( f1 ( x), f 2 ( x),..., f M ( x)) ,<br /> <br /> x  ( x1 , x2 ,..., x N )  X<br /> Trong đó:<br /> - x là véc tơ quyết định,<br /> - y là véc tơ mục tiêu.<br /> Giả sử xét bài toán cực tiểu, với 2 véc tơ<br /> quyết định a, b trong X, chúng ta nói a ―trội‖ hơn<br /> (dominates) b: a  b khi và chỉ khi:<br /> <br /> i  1,2,..., M : f i (a)  f i (b)  j  1,2,..., M : f j (a)<br /> <br /> < f j (b)<br /> Véc tơ quyết định mà không bị vượt trội<br /> bởi các véc tơ quyết định khác thì được gọi là véc<br /> tơ tối ưu Pareto. Một họ gồm tất cả các lời giải<br /> trội (y) hoặc không bị vượt trội bởi véc tơ khác<br /> được gọi là tập tối ưu Pareto (Pareto set) hoặc mặt<br /> tối ưu Pareto (Pareto-optimal front). Hình 1- Ví<br /> dụ cho mặt tối ưu Pareto.<br /> <br /> 92<br /> <br /> Hình 1- Mặt tối ưu Pareto 2 mục tiêu.<br /> <br /> Một số giải thuật tiến hóa đa mục tiêu thông<br /> thường để tìm mặt tối ưu Pareto thông dụng gồm<br /> [3]:<br /> - Niched Pareto GA (NPGA)<br /> - Non-dominated sorting GA (NSGA)<br /> - Elitist Non-dominated Sorting GA (NSGA II)<br /> - Strength – Pareto EA (SPEA)<br /> - Pareto – archived evolution strategy (PAES)<br /> Trong bài báo này chúng tôi sử dụng<br /> phương pháp NSGAII để triển khai ý tưởng đề<br /> xuất (chúng tôi gọi phương pháp mới này là<br /> AFMPGP – Age Fitness Multi Pareto Genetic<br /> Programming).<br /> III.<br /> <br /> PHƯƠNG PHÁP ĐỀ XUẤT<br /> <br /> Phần này mô tả chi tiết phương pháp do chúng tôi<br /> đề xuất. Phương pháp này cũng gồm các bước<br /> như trình bày trong mục II.A.<br /> 1.Tuổi của gen (Age)<br /> Khái niệm về tuổi của lời giải là thời gian tồn tại<br /> của gen trong cấu trúc của lời giải qua các thể hệ<br /> đã được sử dụng trong phương pháp ALPS.<br /> ALPS được xem là một trong các phương pháp<br /> tốt để tránh hiện tượng hội tụ sớm (Hornby,<br /> 2006). Phương pháp AFMPGP sử dụng phép đo<br /> tuổi tương tự như phương pháp của Hornby, và<br /> xem tuổi là một tiêu chí cần tối ưu.<br /> Trong quần thể ban đầu, tất cả các cá thể<br /> được khởi tạo với tuổi là một. Khi lai ghép và đột<br /> biến, giá trị tuổi của các lời giải con là tuổi của lời<br /> giải cha hoặc mẹ lớn nhất cộng với một, hay nói<br /> cách khác tuổi được đo bởi thời gian tồn tại của<br /> phần gen trong lời giải cha hoặc mẹ mà tồn tại lâu<br /> nhất trong quần thể cộng với một.<br /> 2. Quần thể Age-Fitness Pareto<br /> Quần thể được biểu diễn bởi mặt Pareto hai chiều<br /> gồm các lời giải có tuổi nhỏ nhất và độ thích nghi<br /> cao nhất. Nhiệm vụ học là xác định mặt Pareto<br /> tối ưu. Trong quá trình tiến hóa, mặt Pareto sẽ<br /> chứa các lời giải trội, mỗi lời giải trên mặt chỉ bị<br /> <br /> Nitro PDF Software<br /> 100 Portable Document Lane<br /> Wonderland<br /> <br /> Phạm Thị Thương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> thay thế hay bị loại bỏ bởi lời giải có độ thích<br /> nghi thấp hơn và tuổi trẻ hơn. Hơn nữa để góp<br /> phần khắc phục hiện tượng hội tụ sớm, trong quá<br /> trình tiến hóa chúng tôi bổ sung thêm vào quần<br /> thể hiện thời một lời giải được sinh ngẫu nhiên<br /> mới.<br /> 3. Biểu diễn lời giải<br /> Lời giải được biểu diễn bởi cấu trúc cây.<br /> Các nút trong của cây là các hàm và các lá là các<br /> ký hiệu kết thúc. Hình 2 là ví dụ minh họa cho<br /> cấu trúc cây lời giải. GP áp dụng cho bài toán hồi<br /> quy ký hiệu nhằm tìm mô hình khớp với tập dữ<br /> liệu cho trước.<br /> <br /> 135(05): 91 - 96<br /> <br /> Chúng tôi sử dụng phương pháp chọn lọc cạnh<br /> tranh để lựa chọn các lời giải cha mẹ. Các lời giải<br /> cha mẹ được lựa chọn phải thỏa mãn đồng thời<br /> hai tiêu chuẩn tối ưu đó là tuổi ít và có độ thích<br /> nghi cao: Tại mỗi thế hệ, k lời giải được lựa chọn<br /> ngẫu nhiên, trong k lời giải này, chọn 2 trong k<br /> lời giải theo cách chọn lọc cạnh tranh để đưa vào<br /> quần thể kế tiếp.<br /> 7. Các toán tử di truyền<br /> <br /> Phép lai ghép<br /> <br /> a.<br /> <br /> Cặp lời giải cha mẹ được lựa chon sẽ được lai<br /> ghép với nhau sử dụng phương pháp trao đổi chéo<br /> để sinh ra hai lời giải con:<br /> -Chọn ngẫu nhiên một nút trên cây cha 1<br /> <br /> +<br /> <br /> -Chọn ngẫu nhiên một nút trên cây cha 2<br /> *<br /> <br /> 1<br /> <br /> -Tráo đổi hai nút này cùng với các cây con của<br /> chúng.<br /> <br /> ln<br /> <br /> 2<br /> <br /> Hình 4 là ví dụ cho phép lai ghép. Bốn lời<br /> giải gồm hai cha và hai con được đưa vào quần<br /> thể hiện thời.<br /> <br /> x<br /> <br /> *<br /> <br /> Hình 2. Cấu trúc cây lời giải GP<br /> <br /> +<br /> <br /> 4. Khởi tạo quần thể<br /> Quần thể ban đầu chứa các cây lời giải với chiều<br /> cao nằm trong giới hạn [a, b] cho trước, với a, b<br /> là các số nguyên xác định giới hạn dưới, giới hạn<br /> trên. Các cây này được sinh ngẫu nhiên với 50%<br /> gồm các cây đầy đủ và 50% các cây thông<br /> thường.<br /> <br /> *<br /> 1<br /> <br /> ln<br /> <br /> /<br /> *<br /> <br /> 7<br /> <br /> fp <br /> <br /> 1<br /> 1 ep<br /> <br /> 6.Chọn lọc cạnh tranh Pareto<br /> <br /> *<br /> <br /> x<br /> x<br /> <br /> ep là giá trị lỗi của lời giải p trong quần thể.<br /> <br /> Độ thích nghi fp của lời giải được tính theo<br /> công thức:<br /> <br /> 4<br /> <br /> *<br /> -<br /> <br /> c)<br /> <br /> pi là đầu ra thực tế của lời giải p của quan sát i<br /> trong tập huấn luyện.<br /> <br /> *<br /> <br /> x<br /> 7<br /> <br /> i 1<br /> <br /> oi là đầu ra mong đợi của quan sát thứ i trong tập<br /> dữ liệu huấn luyện.<br /> <br /> 2<br /> <br /> +<br /> <br /> x<br /> <br /> Trong đó:<br /> <br /> -<br /> <br /> b)<br /> <br /> a)<br /> <br /> Trong bài báo này chúng tôi sử dụng công thức<br /> đo giá trị lỗi là tổng giá trị tuyệt đối của sự chênh<br /> lệch giữa đầu ra thực sự của lời giải học được và<br /> giá trị mong đợi:<br /> <br /> e p   | p i  oi |<br /> <br /> x<br /> <br /> x<br /> <br /> 2<br /> <br /> 5. Đánh giá độ thích nghi của lời giải<br /> <br /> n<br /> <br /> /<br /> <br /> ln<br /> <br /> 4<br /> <br /> 2<br /> <br /> 1<br /> <br /> 2<br /> <br /> d)<br /> <br /> Hình 4: Ví dụ phép lai ghép a) Cây lời giải cha 1<br /> b) cây lởi giải cha 2, c) cây lời giải con 1, d) cây<br /> lời giải con 2.<br /> b. Phép đột biến<br /> Phép đột biến được tiến hành trên một cá thể cha<br /> bằng cách chọn ngẫu nhiên một cây con trên cây<br /> cha và thay cây con đó bởi cây con được sinh<br /> ngẫu nhiên mới. Lời giải cha và lời giải con sinh<br /> ra lại được đưa vào quần thể ban đầu. Hình 5 là ví<br /> dụ cho phép đột biến.<br /> <br /> Nitro PDF Software<br /> 100 Portable Document Lane<br /> Wonderland<br /> <br /> 93<br /> <br /> Phạm Thị Thương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 135(05): 91 - 96<br /> <br /> +<br /> <br /> +<br /> <br /> Bảng 1: Một số bài toán hồi quy ký hiệu<br /> *<br /> <br /> 1<br /> <br /> *<br /> <br /> -<br /> <br /> 2<br /> <br /> 3<br /> <br /> (a)<br /> <br /> 4<br /> <br /> 1<br /> <br /> Lớp<br /> bài<br /> toán<br /> F1<br /> F2<br /> <br /> -<br /> <br /> 2<br /> <br /> *<br /> <br /> x<br /> <br /> 7<br /> <br /> (b)<br /> <br /> 4<br /> <br /> Hình 5: Ví dụ phép đột biến, (a) cây con trái được<br /> lựa chọn để đột biến, (b) thay thế cây con đột biến<br /> bởi cây con sinh ngẫu nhiên mới<br /> Chúng tôi xác định kích cỡ của quần thể<br /> ban đầu – tương tự như kích cỡ của quần thể của<br /> giải thuật tiến hóa truyền thống. Sau mỗi thế hệ<br /> tiến hóa, kích cỡ của quần thể là lớn hơn gấp đôi<br /> so với kích thước ban đầu. Chúng tôi thực hiện<br /> quá trình loại bỏ các cá thể bị vượt trội trong quần<br /> thể đến khi thu được kích thước quần thể ban đầu<br /> hoặc cho đến khi không tìm được các cá thể<br /> không trội được để loại bỏ chúng để thu được mặt<br /> tối ưu hai mục tiêu Pareto. Các cá thể trong mặt<br /> tối ưu này lại tiếp tục tham gia vào quá trình tiến<br /> hóa tại thế hệ tiếp theo và quy trình lại được lặp<br /> lại cho đến khi số thế hệ tối đa thỏa mãn hoặc tìm<br /> được lời giải đúng hoặc có độ thích nghi nhỏ hơn<br /> ngưỡng α cho phép.<br /> Chúng tôi đã tiến hành lập trình thử nghiệm<br /> phương pháp đề xuất trên lớp các bài toán hồi quy<br /> ký hiệu với độ phức tạp tăng dần. Với nghiên cứu<br /> này, chúng tôi xem độ phức tạp của bài toán tăng<br /> khi cấu trúc của lời giải của bài toán tăng. Cấu<br /> trúc lời giải bài toán được biểu diễn như một cây<br /> lời giải với các nút trong là các hàm và các nút lá<br /> là các ký hiệu kết. Phương pháp đề xuất được so<br /> sánh với SGP – Lập trình di truyền gốc với các<br /> thao tác tiến hóa chuẩn, phương pháp ALPS được<br /> xem là phương pháp tốt để tránh hiện tượng hội tụ<br /> sớm. Kết quả thực nghiệm cho thấy phương pháp<br /> đề xuất tìm được giải pháp tốt hơn đáng kể so với<br /> SGP và phương pháp ALPS, thậm chí trong<br /> trường hợp độ phức tạp của bài toán tăng dần.<br /> IV.<br /> <br /> THIẾT LẬP THỰC NGHIỆM<br /> <br /> A. Lớp các bài toán<br /> Để đánh giá hiệu quả của phương pháp đề xuất,<br /> chúng tôi kiểm thử trên 2 bài toán hồi quy ký hiệu<br /> F1, F2. Trong đó bài toán F2 có cấu trúc hàm mục<br /> tiêu biến đổi từ đơn giản đến phức tạp. Bảng 1.<br /> Mô tả các bài toán này.<br /> 94<br /> <br /> Các công thức với độ phức tạp<br /> giải pháp tăng dần<br /> cos(x)+sin(x) + sin2(x)<br /> 1. x2+x<br /> (F1.1)<br /> 2. x3+x2+x (F1.2)<br /> 3. x4+x3+x2+x (F1.3)<br /> 4. x5+x4+x3+x2+x (F1.4)<br /> 5. x6+x5+x4+x3+x2+x (F1.5)<br /> <br /> B. Thiết lập tham số thực nghiệm<br /> Các tham số được sử dụng trong thực nghiệm được<br /> chỉ ra trong Bảng 2. Đây là các tham số với các giá<br /> trị thường được sử dụng trong các nghiên cứu và<br /> các thực nghiệm của GP [7].<br /> Bảng 2: Bảng các tham số thực nghiệm<br /> Các tham số<br /> Các giá trị<br /> Kích cỡ quần thể<br /> 500<br /> Số thể hệ, điều kiện dừng 100, α = 0.01<br /> Phương pháp lựa chọn<br /> cạnh tranh<br /> Kích cỡ lựa chọn<br /> 2<br /> Xác suất lai ghép<br /> 0.9<br /> Xác suất đột biến<br /> 0.05<br /> Chiều cao tối đa của các 6<br /> cây lời giải trong quần thể<br /> ban đầu<br /> Chiều sâu tối đa của cây 15<br /> lời giải trong các quần thể<br /> Các ký hiệu không kết +, -, *, / (protected<br /> thúc<br /> one), sin, cos, exp,<br /> log (protected one)<br /> Các ký hiệu kết thúc<br /> X<br /> Tập huần luyện<br /> 60 điểm ngẫu nhiên<br /> trong khoảng [-1,1]<br /> Công thức fitness<br /> Độ thích nghi của<br /> lời giải<br /> Số lần thử nghiệm<br /> 30 lần chạy<br /> V. KẾT QUẢ VÀ THẢO LUẬN<br /> <br /> Phần này mô tả các thông tin, kết quả thực<br /> nghiệm và một số trao đổi thảo luận. Trong các<br /> thực nghiệm này, độ thích nghi của cá thể tốt nhất<br /> trong tiến trình tiến hóa được tính trung bình qua<br /> 30 lần chạy và đồ thị kết quả tương ứng chỉ ra<br /> như Hình 6, Hình 7. Trong đó Hình 6 là trung<br /> bình fitness của cá thể tốt nhất của 30 lần chạy<br /> cho bài toán F1. Hình 7 là các kết quả trung bình<br /> của cá thể tốt nhất của 30 lần chạy cho bài toán<br /> F2.<br /> Các kết quả thực nghiệm cho thấy phương<br /> pháp đề xuất (AFMPGP, đường trên cùng) là hiệu<br /> <br /> Nitro PDF Software<br /> 100 Portable Document Lane<br /> Wonderland<br /> <br /> Phạm Thị Thương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> quả hơn so với SGP (đường thứ 3) và phương<br /> pháp ALPS (đường thứ 2), thậm chí khi học các<br /> bài toán với độ phức tạp tăng dần F2.<br /> <br /> F1<br /> <br /> 135(05): 91 - 96<br /> <br /> trong quá trình tiến hóa. Mặt khác, cách tiếp cận<br /> tối ưu đa mục tiêu Pareto NSGAII [3] được chúng<br /> tôi sử dụng để cài đặt AFMPGP. Tiếp theo<br /> AFMPGP được tiến hành thử nghiệm trên lớp bài<br /> toán có độ phức tạp cấu trúc lời giải tăng dần. Kết<br /> quả thử nghiệm chỉ ra AFMPGP có thể chất<br /> lượng lời giải tốt hơn so với SGP và ALPS, thậm<br /> chí khi độ phức tạp của bài toán cần học tăng dần<br /> về cấu trúc, điều này có nghĩa nó có tiềm năng<br /> trong việc tránh hiện tượng hội tụ sớm.<br /> Trong các nghiên cứu tiếp, chúng tôi sẽ tiến<br /> hành thử nghiệm phương pháp trên các bài toán<br /> có độ phức tạp tăng dần (số lượng biến tăng).<br /> Tiếp đó, đề xuất mô hình phức tạp hơn cho tối ưu<br /> đa mục tiêu.<br /> <br /> Hình 6: Đồ thị trung bình fitness của lời giải<br /> tốt nhất với bài toán F1<br /> <br /> F2<br /> <br /> Hình 7: Đồ thị trung bình fitness của lời giải<br /> tốt nhất với bài toán (F2)<br /> VI.<br /> <br /> KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN<br /> <br /> Trong bài báo này, chúng tôi đề xuất phương<br /> pháp mới (AFMPGP) dựa trên việc sử dụng phép<br /> đo tuổi của lời giải dựa trên thời gian tồn tại của<br /> các gen như phương pháp ALPS được đề xuất bởi<br /> Hornby. Chúng tôi xem tuổi và độ thích nghi của<br /> lời giải là hai tiêu chí tối ưu, lựa chọn các cá có<br /> tuổi ít và độ thích nghi cao tham gia vào quá trình<br /> tiến hóa. Điều này sẽ là tăng tính đa dạng trong<br /> quần thể và bảo quản được các lời giải tốt đã hoạc<br /> được trước đó. Mặt khác cách tiếp cận lập trình di<br /> truyền ổn định trạng thái được chúng tôi sử dụng<br /> trong bài báo này nhằm tăng tốc độ hội tụ nhằm<br /> đảm bảo khả năng sớm tìm được giải pháp tốt<br /> <br /> VII.<br /> <br /> TÀI LIỆU THAM KHẢO<br /> <br /> [1] Angeline, P. J. Pollack, ―Evolutionary Module<br /> Acquisition‖, Proceedings of the 2nd Annual<br /> Conference on Evolutionary Programming, pp.<br /> 154-163, MIT Press, 1993.<br /> [2] Andrew H. Wáton., Dr. Ian C. Parmee., Steady<br /> State Genetic Programming with Constrained<br /> Complexity Crossover, Processdings oF the<br /> Second Annual Conference July 13-16, 1997,<br /> Standford University.<br /> [3] Chun-Wei Seah, Yew-Soon Ong, Ivor W. Tsang,<br /> Siwei Jiang, ―Pareto Rank Learning in Multiobjective, WCCI 2012 IEEE World Congress on<br /> Computational Intelligence June, 10-15, 2012 Brisbane, Australia<br /> [4] Gregory S. Hornby, ―A STEADY-STATE<br /> VERSION<br /> OF<br /> THE<br /> AGE-LAYERED<br /> POPULATION STRUCTURE EA‖, GENETIC<br /> PROGRAMMING THEORY AND PRACTICE<br /> VII, 2009.<br /> [5] Michael Schmidt and Hod Lipson, ―SYMBOLIC<br /> REGRESSION OF IMPLICIT EQUATIONS‖,<br /> Genetic Programming Theory and Practice VII,<br /> Genetic and Evolutionary Computation, DOI<br /> 10.1007/978-1-4419-1626-6_5, 2010.<br /> [6] John R. Koza, "Genetic Programming On the<br /> Programming of Computers by Means of Natural<br /> Selection",<br /> The<br /> MIT<br /> Press<br /> Cambridge,<br /> Massachusetts London, England, 1998<br /> [7] Riccardo Poli, William B. Langdon, Nicholas F.<br /> McPhee, "A Field Guide to Genetic Programming",<br /> ISBN 978-1-4092-0073-4 (softcover), 2008<br /> <br /> 95<br /> <br /> Nitro PDF Software<br /> 100 Portable Document Lane<br /> Wonderland<br /> <br />