Nghiên cứu về học chuyển đổi trong GP (genetic programming)

Bài viết trình bày việc đề xuất mô hình cài đặt học chuyển đổi trong GP. Mô hình học chuyển đổi trong GP được xây dựng bằng cách sao chép các giải pháp tốt từ bài toán nguồn (source) sang dân số của bài toán đích (targe).
Nội dung trích xuất từ tài liệu:
Nghiên cứu về học chuyển đổi trong GP (genetic programming) TẠP CHÍ KHOA HỌC − SỐ 14/2017 79 NGHIÊN CỨU VỀ HỌC CHUYỂN ĐỔI TRONG GP (GENETIC PROGRAMMING) Ngô Thúy Ngân1 Trường Đại học Thủ đô Hà Nội Tóm tắt tắt: ắt Trong báo cáo này, chúng tôi đề xuất mô hình cài đặt học chuyển đổi trong GP. Mô hình học chuyển đổi trong GP được xây dựng bằng cách sao chép các giải pháp tốt từ bài toán nguồn (source) sang dân số của bài toán đích (targe). Mô hình này được kiểm thử trên một số lớp các bài toán Hồi quy ký hiệu có cấu trúc và các kết quả thực nghiệm chỉ ra rằng sử dụng Học chuyển đổi giúp GP thực thi tốt hơn trên một lớp các bài toán liên quan. Tuy nhiên, chuyển đổi quá nhiều tri thức cũng có thể làm giảm mức độ thực thi của GP do chuyển đổi các tri thức không cần thiết sẽ ảnh hưởng xấu đến chất lượng của giải pháp tìm được, hiện tượng này còn được gọi là negative transfer. Do đó, nghiên cứu trả lời câu hỏi bao nhiêu tri thức cần chuyển từ bài toán nguồn sang bài toán đích đóng vai trò quan trọng. Trong báo cáo này, chúng tôi cố gắng cung cấp kết quả trả lời ban đầu cho câu hỏi này. Từ khóa: khóa Lập trình di truyền, học chuyển đổi. 1. MỞ ĐẦU Bài báo này đề xuất mô hình cài đặt học chuyển đổi trong GP. Mô hình học chuyển đổi trong GP được xây dựng bằng cách sao chép các lời giải tốt từ bài toán nguồn sang quần thể của bài toán đích. Mô hình này được kiểm thử trên một số lớp các bài toán và các kết quả thực nghiệm chỉ ra rằng sử dụng Học chuyển đổi giúp GP thực thi tốt hơn trên một lớp các bài toán liên quan. Tuy nhiên, chuyển đổi quá nhiều tri thức cũng có thể làm giảm mức độ thực thi của GP do chuyển đổi các tri thức không cần thiết sẽ ảnh hưởng xấu đến chất lượng của giải pháp tìm được. Do đó, nghiên cứu trả lời câu hỏi bao nhiêu tri thức cần chuyển từ bài toán nguồn sang bài toán đích đóng vai trò quan trọng. Học chuyển đổi là một trong những chủ đề nghiên cứu thu hút nhiều chú ý nhất trong lĩnh vực học máy trong thời gian gần đây. Học chuyển đổi cố gắng làm theo quá trình học của con người. Tuy nhiên, các kỹ thuật học máy phổ biến không được thiết kế để làm như 1 Nhận bài ngày 11.2.2017; chỉnh sửa, gửi phản biện và duyệt đăng ngày 20.3.2017 Liên hệ tác giả: Ngô Thúy Ngân; Email: ntngan@daihocthudo.edu.vn 80 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI vậy. Nói cách khác, các thuật toán học máy thường được áp dụng riêng lẻ với các bài toán mới. Điều này càng đúng hơn khi học máy được áp dụng cho các môi trường động trong đó các mục tiêu và các tham số thay đổi trong quá trình học. Kết quả từ nghiên cứu trước đây cho thấy các cách tiếp cận học chuyển đổi có thể cải thiện và mở rộng khả năng học máy trong việc giải quyết các bài toán thực tế. Trong lĩnh vực các thuật toán tiến hoá, Lập trình Di truyền là một thuật toán được đề xuất gần đây. GP là một cơ chế được thiết kế cho phép một quần thể các chương trình máy tính có thể tiến hoá. Từ khi xuất hiện, GP đã được áp dụng vào nhiều bài toán thực tế. Bài báo đề xuất một phương pháp cài đặt học chuyển đổi trong GP. Cụ thể, cố gắng trả lời ba câu hỏi quan trọng khi cài đặt một phương pháp học chuyển đổi. Các câu hỏi này gồm: 1. Chúng ta nên chuyển đổi gì từ bài toán nguồn sang bài toán đích? 2. Làm sao chúng ta có thể chuyển đổi kiến thức từ bài toán nguồn sang bài toán đích? 3. Nên chuyển đổi bao nhiêu kiến thức? 2. NỀN TẢNG 2.1. Học chuyển đổi Học chuyển đổi là quá trình trong đó hệ thống có thể nhận dạng và áp dụng kiến thức, kỹ năng đã học trong các công việc trước vào các công việc mới. Các phương pháp học chuyển đổi dựa trên một số kỹ thuật học máy như là mạng nơron. Có nhiều ứng dụng lớn áp dụng thành công học chuyển đổi bao gồm phân loại văn bản, phân loại trang web, xác định vị trí wi-fi trong nhà. Học chuyển đổi thậm chí còn được dùng cho một vài lĩnh vực thị giác, xử lý ngôn ngữ tự nhiên, phân loại ảnh. Tuy nhiên, học chuyển đổi vẫn chưa được xây dựng cho Lập trình Di truyền. 2.2. Lập trình di truyền Lập trình di truyền (GP) được phát triển bởi Koza vào năm 1992. Dựa trên quan sát hệ thống sinh học, nó sử dụng cơ chế lựa chọn tự nhiên của Darwin để tiến hoá quần thể lời giải bài toán. Nó cũng đã được xem là một phương pháp học máy để tối ưu một quần thể các chương trình máy tính để thực hiện một công việc tính toán nào đó. Để áp dụng GP giải một bài toán, các bước sau cần được xử lý. 1. Chọn cách biểu diễn, 1 tập các chức năng và kết thúc và 1 hàm thích nghi cho bài toán. 2. Khởi tạo một quẩn thể các cá thể. 3. Đánh giá thích nghi (tốt ở mức nào) các cá thể trong quần thể. 4. Nếu điều kiện dừng thoả mãn, kết thúc. Ngược lại chuyển sang bước 5. TẠP CHÍ KHOA HỌC − SỐ 14/2017 81 5. Chọn một số cá thể (lời giải ứng viên) sử dụng phương pháp chọn nào đó. 6. Áp dụng một số toán tử di truyền trên các lời giải đã chọn để sinh 1 quần thể mới. 7. Lặp lại bước 3 tới bước 6. 3. PHƯƠNG PHÁP Phương pháp này nhằm trả lời ba câu hỏi sau về học chuyển đổi: 1. Chúng ta nên chuyển đổi gì từ bài toán nguồn sang bài toán đích? 2. Làm sao chúng ta có thể chuyển đổi kiến thức từ bài toán nguồn sang bài toán đích? 3. Nên chuyển đổi bao nhiêu kiến thức? Câu hỏi thứ nhất và thứ hai đơn giản. Chúng ta chuyển đổi kiến thức từ bài toán nguồn vào bài toán đích bằng cách lựa chọn một số lời giải tốt từ quần thể ở thế hệ gần nhất trong bài toán nguồn và copy chúng sang quần thể thế hệ đầu tiên của bài toán đích. Câu hỏi thứ ba khó trả lời hơ ...