Tài liệu Nghiên cứu ngữ nghĩa trong hệ lập trình gen định hướng bởi văn phạm nối cây và ứng dụng trong xấp xỉ hàm q

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI -------***------- ĐÀO NGỌC PHONG TÊN ĐỀ TÀI LUẬN ÁN NGHIÊN CỨU NGỮ NGHĨA TRONG HỆ LẬP TRÌNH GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM NỐI CÂY VÀ ỨNG DỤNG TRONG XẤP XỈ HÀM Q CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 62480104 LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN Hà Nội - 2014 i BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI -------***------- ĐÀO NGỌC PHONG TÊN ĐỀ TÀI LUẬN ÁN NGHIÊN CỨU NGỮ NGHĨA TRONG HỆ LẬP TRÌNH GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM NỐI CÂY VÀ ỨNG DỤNG TRONG XẤP XỈ HÀM Q CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 62480104 LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC 1. GS.TS NGUYỄN THANH THỦY 2. PGS.TS NGUYỄN XUÂN HOÀI Hà Nội - 2014 ii MỤC LỤC LỜI CAM ĐOAN ............................................................................................. vi LỜI CẢM ƠN .................................................................................................. vii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ....................................... viii DANH MỤC CÁC BẢNG ................................................................................ ix DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ .......................................................... x GIỚI THIỆU CHUNG ....................................................................................... 1 MỤC ĐÍCH .................................................................................................... 1 MỤC TIÊU NGHIÊN CỨU............................................................................ 3 PHƯƠNG PHÁP NGHIÊN CỨU ................................................................... 3 CÁC ĐÓNG GÓP CHÍNH ............................................................................. 4 TỔNG QUAN VỀ CẤU TRÚC CỦA LUẬN ÁN .......................................... 5 CHƯƠNG 1. TỔNG QUAN .............................................................................. 6 1.1 GIẢI THUẬT TIẾN HÓA ..................................................................... 6 1.2 GIẢI THUẬT DI TRUYỀN................................................................... 7 1.3 LẬP TRÌNH GEN.................................................................................. 9 1.3.1 Lập trình Gen chuẩn có cấu trúc cây .............................................. 10 1.3.2 Một số vấn đề với lập trình Gen chuẩn có cấu trúc cây .................. 14 1.3.3 GP với biểu diễn tuyến tính............................................................ 15 1.4 LẬP TRÌNH GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM ........................ 18 1.4.1 GGGP với biểu diễn dạng cây........................................................ 20 1.4.2 GGGP với biểu diễn tuyến tính ...................................................... 22 1.4.3 Một số vấn đề gặp phải với GGGP................................................. 24 1.5 VĂN PHẠM NỐI CÂY VÀ LẬP TRÌNH GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM NỐI CÂY (TAG3P) .......................................................................... 25 1.5.1 Văn phạm nối cây (Tree-Adjoining Grammar – TAG) ................... 25 1.5.2 Hệ lập trình Gen định hướng bởi văn phạm nối cây ....................... 29 KẾT LUẬN CHƯƠNG ................................................................................ 37 CHƯƠNG 2. NGỮ NGHĨA TRÊN HỆ TAG3P ............................................... 39 iii 2.1 NGỮ NGHĨA TRONG LẬP TRÌNH TIẾN HÓA ................................ 39 2.1.1 Sử dụng văn phạm để biểu diễn ngữ nghĩa ........................................ 41 2.1.2 Sử dụng phương pháp hình thức ....................................................... 43 2.1.3 Sử dụng ngữ nghĩa dựa trên biểu diễn của GP ................................... 43 2.2 NGỮ NGHĨA TRONG TAG3P ........................................................... 45 2.2.1 Định nghĩa ngữ nghĩa của cây con trong TAG3P ........................... 45 2.2.2 Đặc điểm ngữ nghĩa cây con trong TAG3P .................................... 51 KẾT LUẬN CHƯƠNG ................................................................................ 52 CHƯƠNG 3. TOÁN TỬ DI TRUYỀN DỰA TRÊN NGỮ NGHĨA ................ 54 3.1 TỔNG QUAN TOÁN TỬ DI TRUYỀN DỰA TRÊN NGỮ NGHĨA . 54 3.2 TOÁN TỬ LAI GHÉP DỰA TRÊN NGỮ NGHĨA TRONG TAG3P .. 58 3.2.1 Toán tử lai ghép dựa trên ngữ nghĩa trong TAG3P............................ 58 3.2.2 Thử nghiệm....................................................................................... 61 3.2.3 Toán tử lai cặp cây con có tổng giá trị ngữ nghĩa dương lớn nhất ..... 67 3.2.4 SO SÁNH KẾT QUẢ VỚI CÁC TOÁN TỬ TƯƠNG TỰ ............... 67 3.3 TOÁN TỬ ĐỘT BIẾN DỰA TRÊN NGỮ NGHĨA TRONG TAG3P . 71 3.3.1 Toán tử đột biến dựa trên ngữ nghĩa trong TAG3P ........................... 71 3.3.2 Thử nghiệm....................................................................................... 74 KẾT LUẬN CHƯƠNG ................................................................................ 78 CHƯƠNG 4. ỨNG DỤNG .............................................................................. 79 4.1 BÀI TOÁN HỌC XẤP XỈ HÀM Q VÀ HÀM NGƯỢC Q .................. 79 4.1.1 Hàm Q .............................................................................................. 79 4.1.2 Một số dạng xấp xỉ do chuyên gia đề xuất......................................... 81 4.1.3 Hàm ngược Q.................................................................................... 82 4.2 ỨNG DỤNG HỌC XẤP XỈ HÀM Q ................................................... 83 4.2.1 Xác định hàm thích nghi với bài toán học xấp xỉ hàm Q ................... 83 4.2.2 Thiết kế thí nghiệm ........................................................................... 87 4.2.3 Kết quả và nhận xét........................................................................... 89 4.3 ỨNG DỤNG HỌC XẤP XỈ HÀM NGƯỢC Q .................................... 93 iv 4.3.1 Xác định hàm thích nghi với bài toán học xấp xỉ hàm ngược Q ........ 93 4.3.2 Thiết kế thí nghiệm và kết quả .......................................................... 94 KẾT LUẬN CHƯƠNG ................................................................................ 98 KẾT LUẬN...................................................................................................... 99 HƯỚNG NGHIÊN CỨU VÀ PHÁT TRIỂN CỦA LUẬN ÁN ...................... 101 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN............ 102 TÀI LIỆU THAM KHẢO .............................................................................. 103 v LỜI CAM ĐOAN Tôi xin cam đoan luận án là công trình nghiên cứu của riêng tác giả. Các kết quả được công bố với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các kết quả trong luận án là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác. Tác giả Đào Ngọc Phong vi LỜI CẢM ƠN Luận án được hoàn thành tại Viện Công nghệ thông tin và Truyền thông, trường Đại học Bách khoa Hà Nội. Để hoàn thành luận án này, tác giả đã nhận được sự chỉ bảo tận tình, sự động viên khích lệ, cùng những yêu cầu của GS.TS Nguyễn Thanh Thủy và PGS.TS Nguyễn Xuân Hoài, những người Thầy đã truyền đạt rất nhiều kiến thức quí báu cũng như những kinh nghiệm nghiên cứu khoa học trong suốt thời gian tác giả theo học nghiên cứu sinh. Lời đầu tiên, tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới các Thầy. Tác giả xin chân thành gửi lời cảm ơn về sự chia sẻ kiến thức khoa học của GS Bob McKay, GS Costi và TS Nguyễn Quang Uy đã giúp ích và hỗ trợ rất nhiều cho tác giả trong suốt quá trình nghiên cứu. Tác giả xin chân thành cảm ơn Ban lãnh đạo Viện Công nghệ thông tin và Truyền thông, Viện Đào tạo Sau đại học, trường Đại học Bách khoa Hà Nội, Ban giám đốc Sở Thông tin và Truyền thông Hà Nội đã tạo điều kiện thuận lợi cho tác giả trong quá trình học tập, nghiên cứu để hoàn thành luận án. Qua đây, cho phép tác giả xin cảm ơn Quỹ Phát triển Khoa học và Công nghệ Quốc gia đã tài trợ một phần cho nghiên cứu này. Tác giả xin cảm ơn các Thầy, Cô trong Bộ môn Hệ thống thông tin - Viện Công nghệ thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội. Luận án này, như một món quà tinh thần, xin đáp lại những niềm quan tâm, mong mỏi của mọi thành viên trong gia đình, đó là một trong những nguồn động viên để tác giả nỗ lực học tập, nghiên cứu. vii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Ký hiệu Ký hiệu đầy đủ Diễn giải EA Evolutionary Algorithms Giải thuật tiến hóa ES Evolutionary Strategies Chiến lược tiến hóa GA Genetic Algorithm Giải thuật di truyền EP Evolutionary Programming Lập trình tiến hóa GP Genetic Programming Lập trình Gen Grammar-guided genetic Lập trình Gen định hướng bởi programming văn phạm CFG Context Free Grammars Văn phạm phi ngữ cảnh TAG Tree-Adjoining Grammars Văn phạm nối cây Tree-Adjunct Grammar Guided Lập trình Gen định hướng bởi Genetic Programming văn phạm nối cây Semantic Similarity based Toán tử lai ghép dựa trên ngữ Crossover nghĩa tương tự The Most Semantic Similarity Toán tử lai ghép dựa trên ngữ based Crossover nghĩa tương tự nhất RAE Relative Absolute Error Lỗi tương đối MAE Mean Absolute Error Lỗi tuyệt đối Q Q-Function Hàm Q Q-Inver Q-Inversion-Function Hàm ngược Q Lexicalised Tree-Adjoining Văn phạm nối cây cấu trúc Grammars từ vựng viết tắt GGGP TAG3P SSC MSSC LTAG viii DANH MỤC CÁC BẢNG Bảng 3.1. Tập hợp các bài toán làm thí nghiệm 62 Bảng 3.2 Cấu hình thí nghiệm 63 Bảng 3.3. Số lần chạy thí nghiệm thành công 64 Bảng 3.4. Trung bình độ tốt của 100 lần chạy thí nghiệm 65 Bảng 3.5. Trung bình thay đổi độ tốt sau khi thực hiện lai ghép 66 Bảng 3.6. Cấu hình thí nghiệm 67 Bảng 3.7. Số lần chạy thí nghiệm thành công 68 Bảng 3.8. Trung bình độ tốt của 100 lần chạy thí nghiệm 70 Bảng 3.9. Trung bình thay đổi độ tốt sau khi thực hiện lai ghép 70 Bảng 3.10. Cấu hình thí nghiệm 75 Bảng 3.11. Số lần chạy thí nghiệm thành công 76 Bảng 3.12. Trung bình độ tốt của 100 lần chạy thí nghiệm 77 Bảng 4.1. Bảng thông số được cài đặt cho mỗi thí nghiệm 88 Bảng 4.2. Kết quả thí nghiệm học xấp xỉ hàm Q 90 Bảng 4.3. Cấu hình thí nghiệm 95 Bảng 4.4. Kết quả thí nghiệm học xấp xỉ hàm ngược Q 97 ix DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ Hình vẽ 1.1. Sơ đồ khối của thuật giải EA 7 Hình vẽ 1.2. Biểu diễn cá thể trong GA 7 Hình vẽ 1.3 Các toán tử cơ bản trong GA chuẩn 8 Hình vẽ 1.4. Biểu diễn chương trình GP 11 Hình vẽ 1.5. Thao tác lai ghép trong GP 13 Hình vẽ 1.6. Thao tác đột biến trong GP 14 Hình vẽ 1.7. Kiểu Gen và kiểu hình trong GEP 15 Hình vẽ 1.8. Ví dụ về việc thay đổi hoàn toàn của kiểu hình 16 Hình vẽ 1.9. Một cá thể 17 Hình vẽ 1.10 Một ví dụ về ánh xạ giữa kiểu Gen và kiểu hình trong GE 23 Hình vẽ 1.11 Một ví dụ về TAG 26 Hình vẽ 1.12. Phép nối cây trong TAG 27 Hình vẽ 1.13. Phép thế cây trong TAG 28 Hình vẽ 1.14. Ví dụ về cây dẫn xuất và cây phân tích trong TAG 29 Hình vẽ 1.15. Quá trình ánh xạ 31 Hình vẽ 1.16. Thao tác lai ghép trong TAG3P 32 Hình vẽ 1.17. Thao tác đột biến trong TAG3P 33 Hình vẽ 1.18. Toán tử chèn 34 Hình vẽ 1.19 Toán tử xóa 34 Hình vẽ 1.20. Toán tử thay thế 35 Hình vẽ 1.21. Toán tử di chuyển 35 Hình vẽ 1.22. Toán tử sao lưu 36 Hình vẽ 1.23. Toán tử cắt bỏ 36 Hình vẽ 2.1 Văn phạm thuộc tính 41 Hình vẽ 2.2 Văn phạm logic 42 Hình vẽ 2.3. Ngữ cảnh có được bằng cách loại bỏ cây con 44 Hình vẽ 2.4. Ngữ nghĩa trong GP biểu diễn dạng cây biểu thức 46 x Hình vẽ 2.5. Một ví dụ về cây cơ bản trong văn phạm TAG 47 Hình vẽ 2.6. Kiểu Gen và kiểu hình trong TAG3P 47 Hình vẽ 2.7. Tính toán độ đóng góp của cây con 48 Hình vẽ 2.8. Quá trình tính toán ngữ nghĩa cây con 49 Hình vẽ 3.1. Cây con tương đồng được lựa chọn 57 Hình vẽ 3.2. Cây con được tạo ra bởi lai ghép hai cây con tương đồng 57 Hình vẽ 4.1. Đồ thị của hàm Q 79 Hình vẽ 4.2. Lỗi tương đối của các xấp xỉ tìm được khi sử dụng hàm 85 thích nghi MAE và xấp xỉ OPBCS Hình vẽ 4.3. Lỗi tương đối của các xấp xỉ tìm được khi sử dụng hàm 86 thích nghi RAE và xấp xỉ OPBCS Hình vẽ 4.4. Văn phạm LTAG của TAP3P cho bài toán học xấp xỉ 89 hàm Q với dạng hàm mũ Hình vẽ 4.5. So sánh lỗi tương đối của xấp xỉ hàm Q 92 Hình vẽ 4.6. Đồ thị hàm ngược Q 93 Hình vẽ 4.7. Văn phạm LTAG của TAP3P cho bài toán xấp xỉ hàm 96 ngược Q xi GIỚI THIỆU CHUNG Trong mục này, luận án sẽ giới thiệu khái quát về mục đích của việc nghiên cứu, mục tiêu, phương pháp nghiên cứu, các đóng góp chính của luận án và cuối cùng là bố cục các phần của luận án. MỤC ĐÍCH Lập trình Gen (Genetic Programming – GP) được đề xuất bởi Koza [1], từ khi ra đời đã được xem như một phương pháp học máy có tiềm năng. Chính vì vậy GP đã được áp dụng rộng rãi để giải quyết thành công nhiều bài toán, trong đó phần nhiều là các bài toán liên quan đến học máy. GP có thể dùng để giải quyết những bài toán học khi độ phức tạp cấu trúc của lời giải là không biết trước, GP đòi hỏi ít tri thức nền của bài toán, và cho lời giải dưới dạng tường minh (cách tiếp cận hộp trắng) cho người dùng. Có nhiều phương pháp học máy được sử dụng như: cây quyết định, mạng nơron nhân tạo, máy vectơ hỗ trợ,…. Các phương pháp được tiếp cận theo hai mô hình là hộp đen (Blackbox) và hộp trắng (Whitebox) hoặc lai ghép giữa hai mô hình trên. Mạng nơ-ron hay máy véctơ hỗ trợ là một ví dụ về mô hình hộp đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu được. Trong khi đó, lập trình Gen tiếp cận theo mô hình hộp trắng với lời giải có tính giải thích và ở dạng đóng. So với các mô hình học máy khác thì GP có khá nhiều lợi điểm. Thứ nhất, GP là phương pháp học quan hệ có khả năng học các tri thức dưới dạng các chương trình máy tính. Thứ hai, GP sử dụng cách tiếp cận hộp trắng cung cấp lời giải dưới dạng tường minh, dễ hiểu hơn đối với người dùng (so với các kỹ thuật học dùng hộp đen như mạng Neural, máy vector hỗ trợ, mô hình đồ thị,…, trong đó lời giải thường ẩn trong các trọng số hay xác suất). Sự tường minh của lời giải trong nhiều trường hợp là cần thiết. Thứ ba, khi so sánh với các mô hình học hộp trắng, GP sử dụng ít tri thức nền của bài toán hơn (trong nhiều trường hợp tri thức này không thể thu nạp dễ 1 dàng) và tìm kiếm rộng (toàn cục) hơn trên không gian tìm kiếm. Hệ lập trình Gen định hướng bởi văn phạm nối cây TAG3P (Tree-Adjunct Grammar Guided Genetic) được đề xuất trong [2] là hệ thống sử dụng văn phạm nối cây để định hướng quá trình tiến hóa. TAG3P sử dụng văn phạm nối cây cùng với văn phạm phi ngữ cảnh để đặt ra những ràng buộc về cú pháp cũng như những sai lệch khi tìm kiếm của chương trình tiến hóa. Hệ thống TAG3P có tất cả những thuộc tính của các hệ thống GP thông thường dựa trên các biểu diễn dạng hình cây khác. Ngữ nghĩa là một khái niệm khá rộng được nghiên cứu trong xử lý ngôn ngữ tự nhiên, khoa học máy tính. Trong khoa học máy tính, ngữ nghĩa được định nghĩa một cách không chính thức là ý nghĩa của một chương trình hoặc một hàm có cú pháp đúng. Hai chương trình có cùng cú pháp thì sẽ có cùng ngữ nghĩa, nhưng ngược lại thì không chắc là như vậy. Một ví dụ đơn giản như sau đây, nếu xét về cú pháp thì hai chương trình khác nhau về cú pháp. Nhưng xét về ngữ nghĩa thì hai chương trình là có cùng ngữ nghĩa. Trong thời gian gần đây, vấn đề nghiên cứu ngữ nghĩa và áp dụng ngữ nghĩa trong các hệ lập trình Gen là hướng nghiên cứu rất được quan tâm để cải tiến, định hướng cho quá trình tiến hóa của các cá thể. Mặc dù vậy, khái niệm ngữ nghĩa chưa được nghiên cứu và đề xuất trong hệ lập trình Gen định hướng bởi văn phạm nối cây. Do đó, đây là hướng nghiên cứu cần tiếp tục được thực hiện đối với TAG3P như: nghiên cứu về ngữ nghĩa cây con, thiết kế toán tử di truyền dựa trên ngữ nghĩa. Trong lĩnh vực viễn thông, các nhà nghiên cứu giả thuyết rằng hệ thống nhiễu có dạng biến Gaussian ngẫu nhiên. Tuy nhiên, hàm Q chỉ duy nhất được định nghĩa dưới dạng tích phân suy rộng, điều này sẽ gây nhiều khó khăn cho những phân tích sau này đối với với các hệ thống viễn thông. Do đó, rất cần thiết phải tìm ra các biểu diễn tường minh (dạng giải tích) của hàm Q. Đến thời điểm 2 này, chưa có giải pháp chính xác tuyệt đối cho dạng tường minh của hàm Q, và do đó, các hàm xấp xỉ là lựa chọn duy nhất. Mặc dù có nhiều hàm xấp xỉ dạng tường minh của hàm Q đã được đề xuất bởi các chuyên gia, nhưng do tính chất quan trọng và phổ biến của hàm Q trong lĩnh vực viễn thông, việc tìm kiếm các hàm xấp xỉ tốt hơn, có dạng giải tích và có nhiều đặc điểm quan trọng (chẳng hạn như sự đơn giản, tính khả tích,…) vẫn tiếp tục được thực hiện. Thực tế cho thấy, các nhà khoa học vẫn không ngừng tìm kiếm các dạng xấp xỉ mới, đơn giản hơn, tốt hơn của hàm Q, cụ thể là trong những năm gần đây, các công trình khoa học tiếp tục đăng tải các dạng xấp xỉ mới tìm thấy. Với đặc điểm của hệ lập trình Gen nói chung và hệ TAG3P sẽ phù hợp với bài toán tìm xấp xỉ, do đó, trong luận án sẽ ứng dụng các kết quả nghiên cứu mới để tìm kiếm các dạng xấp xỉ mới, đơn giản hơn, tốt hơn của hàm Q. Đây là là kết quả ứng dụng thực tế và rất có ý nghĩa, đặc biệt trong lĩnh vực viễn thông. MỤC TIÊU NGHIÊN CỨU Đề tài nghiên cứu được triển khai trên cơ sở hệ TAG3P với mục tiêu: - Nghiên cứu, đề xuất khái niệm ngữ nghĩa cây con trong hệ TAG3P làm cơ sở để định hướng quá trình tiến hóa của các cá thể. - Nghiên cứu, đề xuất và thử nghiệm các toán tử di truyền mới dựa trên “Ngữ nghĩa”. - Thử nghiệm hệ TAG3P với toán tử mới để giải quyết các bài toán thực tế có tính ứng dụng cao là bài toán học xấp xỉ hàm Q và hàm ngược Q. PHƯƠNG PHÁP NGHIÊN CỨU Đề tài nghiên cứu được triển khai trên với phương pháp nghiên cứu sau: - Phương pháp nghiên cứu lý thuyết: tham khảo các công trình nghiên cứu có liên quan từ đó nghiên cứu, đề xuất các nội dung nghiên cứu lý thuyết mới. 3 - Phương pháp thực nghiệm kết hợp đối chiếu, so sánh: tiến hành các thử nghiệm để so sánh kết quả, và đánh giá hiệu quả ứng dụng trong bài toán thực tế. CÁC ĐÓNG GÓP CHÍNH Các đóng góp chính của luận án bao gồm: 1. Đề xuất khái niệm “Ngữ nghĩa” của các cây con trong hệ TAG3P. Trong hệ TAG3P trước đây khái niệm ngữ nghĩa chưa được nghiên cứu, đề xuất, chính vì vậy, việc nghiên cứu và đề xuất khái niệm ngữ nghĩa là sự mở rộng của hệ TAG3P. 2. Dựa trên định nghĩa về ngữ nghĩa trong TAG3P, luận án thiết kế và đề xuất toán tử lai ghép, toán tử đột biến dựa trên ngữ nghĩa. Việc thiết kế với các toán tử mới sẽ giúp quá trình tiến hóa được định hướng tốt hơn dựa trên ngữ nghĩa. Kết quả thực nghiệm cho thấy, toán tử di truyền được thiết kế dựa trên ngữ nghĩa thu được kết quả cải tiến so với toán tử thông thường trên TAG3P. 3. Ứng dụng các kết quả nghiên cứu mới của luận án vào bài toán thực tế là học xấp xỉ hàm Q và học xấp xỉ hàm ngược Q, trong đó: - Nghiên cứu đề xuất hàm thích nghi phù hợp với đặc điểm của bài toán học xấp xỉ hàm Q, hàm ngược Q. - Tìm ra được xấp xỉ hàm Q ở dạng tường minh với cấu trúc rất đơn giản và đặc biệt là có độ chính xác rất cao. Điều này rất có ý nghĩa bởi bài toán tìm các dạng xấp xỉ của hàm Q có một vai trò quan trọng trong lĩnh vực viễn thông, nó cũng được các nhà khoa học không ngừng nghiên cứu nhằm tìm ra các xấp xỉ mới tốt hơn, đơn giản hơn. Kết quả này rất quan trọng vì kể từ khi xấp xỉ OPBCS được đưa ra năm 1979 đến nay chưa có một xấp xỉ nào tốt hơn được tìm ra. Hơn thế nữa, xấp xỉ tìm được này lại có dạng hàm mũ nên rất đơn giản trong quá trình tính toán, phù hợp với đặc điểm sử dụng trong phân tích hệ thống viễn thông. - Tìm ra được xấp xỉ hàm ngược Q ở dạng tường minh, hiện chưa có những công bố về dạng tường minh của hàm ngược này. 4 Các kết quả của luận án đã được công bố bao gồm: 02 bài đăng tại các tạp chí có uy tín (trong đó có 01 tạp chí nước ngoài thuộc danh mục ISI), 03 bài báo được đăng tại kỷ yếu hội thảo quốc tế (trong đó có 02 hội nghị quốc tế thuộc danh mục ISI Proceeding). Ngoài ra, một số công trình nghiên cứu thuộc lĩnh vực viễn thông đã trích dẫn và sử dụng các kết quả nghiên cứu này. TỔNG QUAN VỀ CẤU TRÚC CỦA LUẬN ÁN Luận án sẽ được trình bày như sau: Giới thiệu chung: phần này sẽ trình bày mục đích của việc nghiên cứu, các mục tiêu của luận án đặt ra, phương pháp nghiên cứu, các kết quả đóng góp chính của luận án và cấu trúc các chương trong luận án. Chương 1: các nội dung lý thuyết và các nghiên cứu trước đây có liên quan sẽ được trình bày, bao gồm: những lý thuyết và các nghiên cứu có liên quan trong lĩnh vực lập trình Gen, lập trình Gen định hướng bởi văn phạm và đặc biệt là hệ lập trình Gen định hướng bởi văn phạm nối cây – TAG3P. Hệ TAG3P sẽ được sử dụng là nền tảng cho các hướng nghiên cứu của luận án. Chương 2: Chương này sẽ trình bày khái quát về các định nghĩa ngữ nghĩa và các toán tử di truyền dựa trên ngữ nghĩa trong một số nghiên cứu gần đây. Trên cơ sở đó, khái niệm về ngữ nghĩa của cây con trong hệ TAG3P được đề xuất. Các đặc điểm của ngữ nghĩa trong hệ TAG3P cũng được phân tích trong chương này. Chương 3: Dựa trên ngữ nghĩa, các toán tử di truyền mới đã được thiết kế và một số thí nghiệm đã được tiến hành để đánh giá kết quả và so sánh hiệu quả của toán tử di truyền dựa trên ngữ nghĩa so với toán tử di truyền thông thường trên TAG3P và với hệ GP khác. Chương 4: Ứng dụng những kết quả nghiên cứu mới để giải quyết bài toán ứng dụng thực tế là: bài toán học xấp xỉ hàm Q và hàm ngược của Q. Tiếp theo là danh mục các kết quả đã công bố, hướng nghiên cứu tiếp theo, danh mục tài liệu tham khảo. 5 CHƯƠNG 1. TỔNG QUAN Chương này sẽ trình bày tổng quan những nghiên cứu trước đây trong lĩnh vực lập trình Gen, lập trình Gen định hướng bởi văn phạm và đặc biệt sẽ trình bày chi tiết về hệ lập trình Gen định hướng bởi văn phạm nối cây. Trên cơ sở đó, luận án đưa ra một số hướng nghiên cứu mở rộng cũng như khả năng áp dụng vào các bài toán thực tế. 1.1 GIẢI THUẬT TIẾN HÓA Giải thuật tiến hóa (Evolutionary Algorithms – EA) là tập các giải thuật tìm kiếm mô phỏng quá trình tiến hóa [3]. Sự mô phỏng này được thực hiện theo ba mặt: một là EA sử dụng quần thể gồm tập hợp các cá thể; hai là các cá thể đó cạnh tranh với nhau, dựa trên thuyết chọn lọc tự nhiên của Darwin để tái tạo; ba là quá trình tiến hóa được thực hiện ngẫu nhiên. EA dựa trên quan niệm "Quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu". Quá trình tiến hoá thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước. Năm 1975, giải thuật Gen do John Holland phát minh và được phát triển bởi ông cùng với các đồng nghiệp. Đến năm 1992, Koza đã dùng GA để xây dựng các chương trình giải quyết một số bài toán mà kích thước lời giải không được xác định trước và gọi phương pháp này là "Lập trình Gen". Mặc dù vậy, thuật toán của các EA đều rất giống nhau và được thể hiện như hình vẽ sau: 6 Hình vẽ 1.1. Sơ đồ khối của thuật giải EA 1.2 GIẢI THUẬT DI TRUYỀN Giải thuật di truyền (GA) nguyên thủy đã được đề xuất bởi Holland và là giải thuật tiến hóa khá phổ biến và được sử dụng rộng rãi. Đồng thời, nó được nghiên cứu và áp dụng cho nhiều bài toán thực tế. Hệ GA nguyên thủy có sử dụng chuỗi nhị phân tuyến tính và có độ dài cố định để biểu diễn chuỗi Gen. Hình vẽ sau đây là ví dụ một chuỗi Gen của hệ giải thuật di truyền: Hình vẽ 1.2. Biểu diễn cá thể trong GA 7 Từ khi Holland [4] phát minh ra hệ GA đầu tiên, đến nay đã có một số biến thể GA được đề xuất và sử dụng các biểu diễn khác nhau như: sử dụng mã thực, mã gray, chuỗi Gen với độ dài thay đổi và tương tự như vậy. Hình vẽ 1.3 Các toán tử cơ bản trong GA chuẩn Điều quan trọng cần lưu ý ở đây là tất cả các biểu diễn trên đều sử dụng biểu diễn chuỗi Gen dạng tuyến tính. Tính tuyến tính này tạo thuận lợi cho việc thiết kế các toán tử di truyền khác nhau. Với ba toán tử ban đầu, ngày nay nhiều 8 toán tử di truyền mới và phỏng sinh học đã được đưa ra [4] [5] [6]. Hơn nữa, sẽ không khó khăn đối với GA khi sử dụng biểu diễn chuỗi Gen tuyến tính để thiết kế ra các toán tử mà tạo ra các thay đổi nhỏ khi áp dụng. Nói cách khác, nếu có một cấu trúc đồ thị trong chuỗi Gen biểu diễn tuyến tính, nó dễ dàng thiết kế toán tử di truyền để duy trì cấu trúc này. Ví dụ như trong GA sử dụng biểu diễn nhị phân tuyến tính, nếu chúng ta sử dụng khoảng cách Hamming để định nghĩa cấu trúc lân cận trong không gian biểu diễn Gen của GA, toán tử đột biết sẽ làm thay đổi nhỏ về khoảng cách Hamming. 1.3 LẬP TRÌNH GEN Lập trình Gen (GP) được định nghĩa như là phương pháp học máy để tạo ra các chương trình thông qua quá trình tiến hóa [7], là một công nghệ tính toán tiến hóa tự động giải quyết bài toán, không đòi hỏi phải biết dạng thức hay cấu trúc của lời giải [8] [2] [9] [10]. GP được kế thừa từ GA và đôi khi được xem như là một nhánh nghiên cứu của GA. GP có thể khái quát là phương thức có hệ thống và độc lập với bài toán để tự động giải quyết bài toán từ những định nghĩa cấp cao. GP dựa trên ý tưởng chính là các chương trình máy tính có khả năng tự tiến hóa để thực hiện một công việc nào đó, được đưa ra bởi Koza vào năm 1992 [1]. Kỹ thuật này cung cấp một nền tảng cho việc tạo ra những chương trình máy tính một cách tự động. Lập trình Gen đạt được mục đích này bằng việc phát sinh ra một quần thể các chương trình máy tính, sử dụng thuyết tiến hóa của Darwin chọn ra chương trình tốt nhất để thực hiện công việc. GP khác những thuật toán tiến hóa khác ở phạm vi ứng dụng. Những thuật toán tiến hóa khác thường được áp dụng cho các bài toán tìm lời giải tối ưu, trong khi GP được xếp vào nhóm các thuật toán học máy để tìm mô hình phù hợp nhất dựa trên dữ liệu đưa vào. Sự khác biệt giữa GA và GP cơ bản nằm ở mục đích của nó, trong khi GA chủ yếu sử dụng cho bài toán tối ưu thì GP lại được sử dụng cho việc học. GA được sử dụng để thực hiện việc tối ưu hóa một hàm dựa trên định nghĩa của hàm 9